基于改進相似性度量的鄰近傳播聚類算法

溫愛紅 徐草草

摘 要： 鄰近傳播（Affinity Propagation，AP）聚類將數據集中所有數據點均視為潛在的聚類中心，并采用歐氏距離法計算輸入相似度矩陣，導致其性能對變形十分敏感。針對這一缺陷，提出了采用兩種不同的相似性度量方法來計算數據集中兩個數據點之間的相似度。分別將明可夫斯基（Minkowski）和切比雪夫（Chebychev）相似性度量引入到AP聚類中，替換原有的歐氏距離度量來構建相似性矩陣。在UCI機器學習數據集上，利用Jaccard指數和Fowlkes-Mlowers對提出方法進行了量化評估。實驗結果表明，基于明可夫斯基距離和切比雪夫距離的AP聚類方法在總體精度上優于現有的歐氏距離。

關鍵詞： 數據聚類; 鄰近傳播算法; 歐氏距離; 相似性度量; 聚類中心

中圖分類號： TP 393 ? ? ?文獻標志碼： A

Abstract： Affinity propagation （AP） clustering treats all data points in the dataset as potential cluster centers， and uses the Euclidean distance method to calculate the input similarity matrix， which results in its performance being very sensitive to deformation. In view of this defect， two different similarity measurement methods are proposed to calculate the similarity between two data points in the data set. Minkowski and Chebychev similarity measures are introduced into the AP cluster， respectively， and the original Euclidean distance measure is replaced to construct the similarity matrix. On the UCI machine learning data set， the proposed method is quantitatively evaluated using Jaccard index and Fowlkes-Mlowers. The experimental results show that the AP clustering method based on Minkowski distance and Chebyshev distance has better overall accuracy than the existing Euclidean distance.

Key words： data clustering; proximity propagation algorithm; Euclidean distance; similarity measure; cluster center

0 引言

作為數據挖掘的常用技術方法之一，聚類分析技術出現的頻度較高，聚類方法被廣泛應用于計算機視覺、市場分析、生物信息學等不同領域[1-3]。聚類方法的目標是將一個數據集劃分成不同的子簇，將具有相似特征的數據點劃分到一個簇中。

作為一種新的無監督聚類技術，鄰近傳播（Affinity Propagation，AP）聚類是Frey和Dueck[4] 提出的一種基于消息傳遞的聚類算法，表現出比傳統聚類方法更好的性能。不同于傳統的聚類方法，AP聚類使用了相似性矩陣和偏向參數。前者用于實現相似性度量從而獲得數據點之間相似性的真實值。由于AP聚類將所有數據集對象視為聚類中心，因此通過在數據點之間傳遞基于偏向參數的真實值消息來進行數據點分簇，直到獲得一組中心和聚類結果。……