基于改進(jìn)相似性度量的鄰近傳播聚類(lèi)算法

溫愛(ài)紅 徐草草

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

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

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

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

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

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

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

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

2 鄰近傳播聚類(lèi)存在的問(wèn)題

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

1） 相似性度量;

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

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

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

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

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

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

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

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

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

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

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

在從UCI機(jī)器學(xué)習(xí)庫(kù)獲得的IRIS數(shù)據(jù)集、Wine和Ionoshpere數(shù)據(jù)集[10]上對(duì)所提出的改進(jìn)進(jìn)行了評(píng)估，以驗(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 聚類(lèi)結(jié)果可視化

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

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

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

4.4 性能對(duì)比

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

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

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

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

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

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

5 總結(jié)

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

參考文獻(xiàn)

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

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

[3] 羅恩韜， 王國(guó)軍， 李超良. 大數(shù)據(jù)環(huán)境中多維數(shù)據(jù)去重的聚類(lèi)算法研究[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ù)集的近鄰傳播聚類(lèi)[J]. 計(jì)算機(jī)工程， 36（23）：22-24.

[6] 劉璐， 靳少輝， 焦李成. 采用流形近鄰傳播聚類(lèi)的極化SAR圖像分類(lèi)[J]. 信號(hào)處理， 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] 董俊， 王鎖萍， 熊范綸. 可變相似性度量的近鄰傳播聚類(lèi)[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）