溫愛紅 徐草草

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

關(guān)鍵詞： 數(shù)據(jù)聚類; 鄰近傳播算法; 歐氏距離; 相似性度量; 聚類中心

中圖分類號： TP 393 ? ? ?文獻(xiàn)標(biāo)志碼： 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 引言

作為數(shù)據(jù)挖掘的常用技術(shù)方法之一，聚類分析技術(shù)出現(xiàn)的頻度較高，聚類方法被廣泛應(yīng)用于計(jì)算機(jī)視覺、市場分析、生物信息學(xué)等不同領(lǐng)域[1-3]。聚類方法的目標(biāo)是將一個(gè)數(shù)據(jù)集劃分成不同的子簇，將具有相似特征的數(shù)據(jù)點(diǎn)劃分到一個(gè)簇中。

作為一種新的無監(jiān)督聚類技術(shù)，鄰近傳播（Affinity Propagation，AP）聚類是Frey和Dueck[4] 提出的一種基于消息傳遞的聚類算法，表現(xiàn)出比傳統(tǒng)聚類方法更好的性能。不同于傳統(tǒng)的聚類方法，AP聚類使用了相似性矩陣和偏向參數(shù)。前者用于實(shí)現(xiàn)相似性度量從而獲得數(shù)據(jù)點(diǎn)之間相似性的真實(shí)值。由于AP聚類將所有數(shù)據(jù)集對象視為聚類中心，因此通過在數(shù)據(jù)點(diǎn)之間傳遞基于偏向參數(shù)的真實(shí)值消息來進(jìn)行數(shù)據(jù)點(diǎn)分簇，直到獲得一組中心和聚類結(jié)果。通過上述分析，可以得出偏向參數(shù)用于確定聚類的數(shù)量，通常以相似度的中間值作為偏好值。通過逐漸調(diào)整偏向參數(shù)，可以獲得不同數(shù)量的聚類結(jié)果。

1 相關(guān)工作分析

近年來，AP聚類被廣泛應(yīng)用于醫(yī)學(xué)圖像分割、網(wǎng)絡(luò)定位等領(lǐng)域[5-6]。例如，在醫(yī)學(xué)圖像分割方面，AP聚類被用來在功能磁共振成像（Functional magnetic resonance imaging，F(xiàn)MRI）中對大腦區(qū)域進(jìn)行聚類。AP聚類也可以用于檢測動(dòng)態(tài)對比增強(qiáng)磁共振成像中的動(dòng)脈輸入功能。此外，AP聚類通過選擇最佳閾值實(shí)現(xiàn)分割正電子發(fā)射斷層掃描圖像中的區(qū)域。

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

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

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

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

1） 相似性度量;

2） 尋找最佳偏向參數(shù)。

3 提出的改進(jìn)相似性度量的方法

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

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

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

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

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

（9） ?為了正確分割圖像，在文獻(xiàn)[24]中將切比雪夫度量引入到輪廓模型中。切比雪夫距離是具有L范數(shù)的明可夫斯基距離的特例，其主要優(yōu)點(diǎn)是確定數(shù)據(jù)集之間距離時(shí)所需時(shí)間較短，因此本文將其引入到AP聚類。本文提出了一種基于切比雪夫的方法來構(gòu)造相似度矩陣。方程式中的契比雪夫。公式（9）中的切比雪夫?qū)⑻峁┏蓪?shù)據(jù)點(diǎn)之間的最大距離。然后，當(dāng)應(yīng)用于AP聚類時(shí)，切比雪夫?qū)⒈晦D(zhuǎn)換為負(fù)值，如式（10）。s（i，k）=-maxxi-ki

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

4 實(shí)驗(yàn)結(jié)果

4.1 數(shù)據(jù)集

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

4.3 聚類結(jié)果可視化

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

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

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

4.4 性能對比

使用來自UCI的3個(gè)數(shù)據(jù)集進(jìn)行了AP聚類測試，以評估所提出的方法的準(zhǔn)確性。該方法是通過改變傳統(tǒng)AP算法的距離度量來實(shí)現(xiàn)的。如表2—表4所示。

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

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

表4給出了4種不同距離度量方法在Wine數(shù)據(jù)集上的聚類結(jié)果。對于Iris和Ionoshpere數(shù)據(jù)集，使用明可夫斯基和切比雪夫距離度量確實(shí)適度提高了聚類質(zhì)量和精度。然而，使用歐氏距離和歐氏距離組合的AP聚類在Wine數(shù)據(jù)集中的表現(xiàn)優(yōu)于明可夫斯基和切比雪夫。之所以會出現(xiàn)這種情況，是因?yàn)閃ine數(shù)據(jù)集的不同簇中有一些數(shù)據(jù)點(diǎn)聚集過于緊密。

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

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

5 總結(jié)

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

參考文獻(xiàn)

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

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

[3] 羅恩韜， 王國軍， 李超良. 大數(shù)據(jù)環(huán)境中多維數(shù)據(jù)去重的聚類算法研究[J]. 小型微型計(jì)算機(jī)系統(tǒng)， 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] 谷瑞軍， 汪加才， 陳耿.面向大規(guī)模數(shù)據(jù)集的近鄰傳播聚類[J]. 計(jì)算機(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]. 電子與信息學(xué)報(bào)（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）