Clustering Algorithm Based on Local Random Walkwith Distance Measure

Cluster analysis is widely used in the field of data mining. However, the K-means algorithm which is widely used has a strong sensitivity for the initial values. Namely, the parameters such as clustering coefficient and centroid should be determined when the cluster is initialized. In the paper, we propose a K-means algorithm that based on link information and regard KL divergence distance as the objective function. This method not only introduces the way of the local random walk with the shortest path, but also uses the link information to convert the distance space. In other word, we utilize the local random walk with the shortest path to convert the distance between data into the transition probability of the random walk. Then, we use the random walk realize the conversion of the distance space. The core concept is the distance of converting node pair that refers to the node to the whole network node distance. The experimental results show that the proposed algorithm can improve the cluster result efficiently.