2006 · 22 citations · 6 references
ComputingComputer ScienceData ScienceData MiningData VisualizationMachine LearningCluster DetectionCluster VisualizationClustered Data AnalysisGraph-based LearningRandom WalksClusteringProbabilistic ClusteringRandom Walk ModelsTransition Probability AnalysisTransition Probability MatrixTransition Probability Models
We consider the problem of clustering in its most basic form where only a local metric on the data space is given. No parametric statistical model is assumed, and the number of clusters is learned from the data. We introduce, analyze and demonstrate a novel approach to clustering where data points are viewed as nodes of a graph, and pairwise similarities are used to derive a transition probability matrix P for a Markov random walk between them. The algorithm automatically reveals structure at increasing scales by varying the number of steps taken by this random walk. Points are represented as rows of Pt, which are the t-step distributions of the walk starting at that point; these distributions are then clustered using a KL-minimizing iterative algorithm. Both the number of clusters, and the number of steps that 'best reveal' it, are found by optimizing spectral properties of P.
6
On Spectral Clustering: Analysis and an algorithm
Andrew Y. Ng, Michael I. Jordan, Yair Weiss · 2001 · 7.8K citations
A Random Walks View of Spectral Segmentation.
Marina Meilă, Jianbo Shi · 2001 · 638 citations
On clusterings-good, bad and spectral
Ramachandran Kannan, S. Vempala, A. Veta · 2002 · 380 citations