关键词: 聚类, 距离度量, 度量学习, 有效距离

Abstract:  Distance metric learning is a key step in clustering analysis, which is an important sub-domain of data mining. Euclidean distance metric is a quite commonly used local distance metric in clustering algorithms, which only focuses on the distance between two samples. This paper proposes a new global distance metric method, named as the effective distance metric. In the new method, the similarity between two samples is evaluated by using not only the distance between these two samples, but also distances between one specific sample and all the other related ones. Sparse reconstruction coefficients are employed to reflect such global relationship among samples. Then, this paper develops three effective distance-based clustering algorithms, including EK-means, EK-medoids and EFCM, by applying the effective distance to three classical clustering algorithms, i.e., K-means, K-medoids and FCM (fuzzy C-means), respectively. The experimental results on UCI benchmark datasets demonstrate the efficacy of the proposed methods.

Key words: clustering, distance metric, metric learning, effective distance