Clustering using a random walk based distance measure
Luh Yen, Denise J. VanVyve, Fabien Wouters, François Fouss, Michel Verleysen, Marco Saerens · 2005
This work proposes a simple way to improve a clustering algo- rithm. The idea is to exploit a new distance metric called the \Euclidian Commute Time (ECT) distance, based on a random walk model on a graph derived from the data. Using this distance measure instead of the usual Euclidean distance in a k-means algorithm allows to retrieve well- separated clusters of arbitrary shape, without working hypothesis about their data distribution. Experimental results show that the use of this new distance measure signiflcantly improves the quality of the clustering on the tested data sets.