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

溫愛紅 徐草草

摘 要： 鄰近傳播（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聚類將所有數據集對象視為聚類中心，因此通過在數據點之間傳遞基于偏向參數的真實值消息來進行數據點分簇，直到獲得一組中心和聚類結果。通過上述分析，可以得出偏向參數用于確定聚類的數量，通常以相似度的中間值作為偏好值。通過逐漸調整偏向參數，可以獲得不同數量的聚類結果。

1 相關工作分析

近年來，AP聚類被廣泛應用于醫學圖像分割、網絡定位等領域[5-6]。例如，在醫學圖像分割方面，AP聚類被用來在功能磁共振成像（Functional magnetic resonance imaging，FMRI）中對大腦區域進行聚類。AP聚類也可以用于檢測動態對比增強磁共振成像中的動脈輸入功能。此外，AP聚類通過選擇最佳閾值實現分割正電子發射斷層掃描圖像中的區域。

然而，大多數文獻采用了歐幾里德距離（歐氏距離）作為相似性度量，這影響了AP聚類的性能。這是因為歐幾里德距離度量對變形具有很高的敏感度，具體來說就是歐幾里德距離沒有考慮數據點之間的空間關系。近期有研究人員開始嘗試使用不同的相似性度量方法來取代傳統的歐幾里德距離，以便改善AP聚類性能。在文獻[7]中，引入了一種模糊統計相似性度量（fuzzy statistical similarity measure，FSS）來評價像素矢量之間的相似性。而文獻[8]通過引入非對稱相似性度量，擴展了基于余弦指數的相似性度量。在文獻[9]中，使用兩個不同數據點之間的歐幾里德距離的組合來尋找相似度矩陣。

借鑒上述研究的思路，本文對AP聚類算法進行了改進，提出了采用兩種不同的相似性度量來計算數據集中數據點之間的相似度，以提高其聚類精度。

2 鄰近傳播聚類存在的問題

與其他聚類方法相比，AP聚類算法實現起來更加簡單、快速，能夠獲得更低的聚類誤差。雖然它有一定優勢，但在兩個方面仍具有局限性[6]：

1） 相似性度量;

2） 尋找最佳偏向參數。

3 提出的改進相似性度量的方法

在這一部分中，提出將明可夫斯基和切比雪夫相似性度量引入到AP聚類中，來構建不同的相似性矩陣，其目的是定義一個相似度函數（x，y），函數的值表示兩點之間的“相似”程度。

3.1 基于明可夫斯基度量的相似矩陣

明可夫斯基距離被認為是包含其他特殊距離（如歐幾里得距離）的廣義距離。近年來，許多關于聚類的研究都將明可夫斯基距離納入到他們的研究中。已有不少模糊聚類方法采用了明可夫斯基距離函數。文獻[10]利用明可夫斯基距離函數對模糊c-均值算法的性能進行了改進研究。因此，明可夫斯基距離是一種簡明的參數化距離，通過調整明可夫斯基參數p可以適應任何應用場景。

3.2 基于切比雪夫度量的相似矩陣

切比雪夫距離用于檢查數據點對之間的絕對差值。切比雪夫距離定義如式（9）。DChebyshev（p，q）=maxpi-qi

（9） ?為了正確分割圖像，在文獻[24]中將切比雪夫度量引入到輪廓模型中。切比雪夫距離是具有L范數的明可夫斯基距離的特例，其主要優點是確定數據集之間距離時所需時間較短，因此本文將其引入到AP聚類。本文提出了一種基于切比雪夫的方法來構造相似度矩陣。方程式中的契比雪夫。公式（9）中的切比雪夫將提供成對數據點之間的最大距離。然后，當應用于AP聚類時，切比雪夫將被轉換為負值，如式（10）。s（i，k）=-maxxi-ki

（10） ?使用切比雪夫相似性度量的AP聚類流程與圖1一致。

4 實驗結果

4.1 數據集

在從UCI機器學習庫獲得的IRIS數據集、Wine和Ionoshpere數據集[10]上對所提出的改進進行了評估，以驗證所提出的算法。其中，IRIS數據集包含150個實例，具有4個特征，具有3個簇。Wine數據集包含178個實例，具有13個特征，并分為3個簇。Ionosphere數據集包含351個實例，具有34個特征，具有2個簇。這些數據集的詳細信息、大小、維度和簇的數量，如表1所示。

4.3 聚類結果可視化

直觀顯示IRIS上采用明可夫斯基距離度量的AP聚類結果，如圖2所示。

IRIS上采用切比雪夫距離度量的AP聚類結果，如圖3所示。

從圖2和圖3可以看出，以萼片長度和寬度，花瓣長度為坐標軸的三維聚類可視化驗證了兩種方法的有效性。

4.4 性能對比

使用來自UCI的3個數據集進行了AP聚類測試，以評估所提出的方法的準確性。該方法是通過改變傳統AP算法的距離度量來實現的。如表2—表4所示。

分別顯示了使用歐氏距離、歐氏距離組合[9]、明可夫斯基和切比雪夫四種不同距離度量的AP聚類結果。表2給出了四種不同距離度量方法在Iris數據集上的聚類結果，表中粗體表示最佳聚類結果。

從表2可以看出，采用明可夫斯基的AP聚類準確率最高，Jaccard指數T為0.80，Fowlkes-Mlowers指數FM為0.89。采用切比雪夫的AP聚類準確率次之，分別為0.78和0.88。采用歐氏距離組合的AP聚類準確率稍差，分別為0.76和0.85。采用的AP聚類準確率最低。表3給出了四種不同距離度量方法在Ionoshpere數據集上的聚類結果，準確率結果排名第一的為切比雪夫距離，其次為明可夫斯基距離。

表4給出了4種不同距離度量方法在Wine數據集上的聚類結果。對于Iris和Ionoshpere數據集，使用明可夫斯基和切比雪夫距離度量確實適度提高了聚類質量和精度。然而，使用歐氏距離和歐氏距離組合的AP聚類在Wine數據集中的表現優于明可夫斯基和切比雪夫。之所以會出現這種情況，是因為Wine數據集的不同簇中有一些數據點聚集過于緊密。

對于不同的p值，基于明可夫斯基度量的AP聚類結果也有不同。當 p=2時，其結果與采用歐氏距離的AP聚類結果相同。當p=3時，其聚類性能更低。

結果表明，由于明可夫斯基距離的靈活性和通用性，在AP聚類中采用明可夫斯基距離更為可取。盡管切比雪夫距離確實產生了很好的結果，但它仍然只是明可夫斯基距離的一個特例。

5 總結

本文提出了基于明可夫斯基距離和切比雪夫距離的AP聚類方法，并在對UCI數據集上進行驗證。實驗結果表明，選擇不同距離度量方法對聚類結果有很大的影響。與歐氏距離和歐氏距離組合相比，基于明可夫斯基距離和切比雪夫距離的AP聚類方法的總體精度更高。因此，在選擇距離度量時應給予相當的重視。但是對于在緊密程度較高的數據集，使用歐幾里德距離的AP聚類表現更好，后期將對該問題進行進一步研究。

參考文獻

[1] 謝娟英， 屈亞楠. 密度峰值優化初始中心的K-medoids聚類算法[J]. 計算機科學與探索， 2016， 10（2）：230-247.

[2] 周潤物， 李智勇， 陳少淼，等. 面向大數據處理的并行優化抽樣聚類K-means算法[J]. 計算機應用， 2016， 36（2）：311-315.

[3] 羅恩韜， 王國軍， 李超良. 大數據環境中多維數據去重的聚類算法研究[J]. 小型微型計算機系統， 2016， 37（3）：438-442.

[4] Chidean M I， Morgado E， Sanromán-Junquera M， et al. Energy Efficiency and Quality of Data Reconstruction Through Data-Coupled Clustering for Self-Organized Large-Scale WSNs[J]. IEEE Sensors Journal， 2016， 16（12）：5010-5020.

[5] 谷瑞軍， 汪加才， 陳耿.面向大規模數據集的近鄰傳播聚類[J]. 計算機工程， 36（23）：22-24.

[6] 劉璐， 靳少輝， 焦李成. 采用流形近鄰傳播聚類的極化SAR圖像分類[J]. 信號處理， 2016， 32（2）：135-141.

[7] Yang C， Bruzzone L， Sun F， et al. A Fuzzy-Statistics-Based Affinity Propagation Technique for Clustering in Multispectral Images[J]. IEEE Transactions on Geoscience & Remote Sensing， 2010， 48（6）：2647-2659.

[8] 董俊， 王鎖萍， 熊范綸. 可變相似性度量的近鄰傳播聚類[J]. 電子與信息學報（3）：5-10.

[9] Zhirong Yang， Jukka Corander， Erkki Oja. Low-Rank Doubly Stochastic Matrix Decomposition for Cluster Analysis[J]. Journal of Machine Learning Research， 2016， 17（187）：1-25.

[10] Punit Rathore， James C. Bezdek， Sarah M. Erfani. Ensemble Fuzzy Clustering Using Cumulative Aggregation on Random Projections[J]. IEEE Transactions on Fuzzy Systems， 2018， 26（3）：1510-1524.

（收稿日期： 2020.04.01）