一種基于AP 的三支聚類改進(jìn)算法

孫 暖，曹小平，劉 軍

（重慶科創(chuàng)職業(yè)學(xué)院 人工智能學(xué)院，重慶 永川 402160）

0 概述

聚類分析是數(shù)據(jù)挖掘的重要手段之一，聚類分析是把相似性大的對(duì)象歸為一類，同一類之間的相似度比較大，不同類之間的相似度越小越好，也就是說差異性越大越好，聚類技術(shù)現(xiàn)在已經(jīng)廣泛應(yīng)用于生物學(xué)、心理學(xué)、醫(yī)學(xué)地質(zhì)學(xué)等各種領(lǐng)域。

Affinity Propagation 聚類算法又叫近鄰傳播算法，簡稱AP[1]，基本思想是基于因子圖的信念傳播和最大化算法。它根據(jù)N 個(gè)數(shù)據(jù)點(diǎn)之間的相似度進(jìn)行聚類，這些相似度可以是對(duì)稱的（即兩個(gè)數(shù)據(jù)點(diǎn)互相之間的相似度一樣，如歐氏距離），也可以是不對(duì)稱的（即兩個(gè)數(shù)據(jù)點(diǎn)互相之間的相似度不等）。AP 算法不需要事先指定聚類數(shù)目，而是將所有的數(shù)據(jù)點(diǎn)都作為潛在的聚類中心，稱之為exemplar。但是AP 聚類對(duì)非團(tuán)狀數(shù)據(jù)集的聚類效果并不好，因此許多專家學(xué)者對(duì)AP 算法進(jìn)行了改進(jìn)。如Li, Peixin，Gu, Wei 等將AP算法應(yīng)用于光伏電站群建模[2]，提出了一種動(dòng)態(tài)親和力傳播（DAP）聚類算法。然后，根據(jù)該算法的動(dòng)態(tài)特性，對(duì)光伏集群中的光伏電站進(jìn)行分組。最后，通過對(duì)同一組光伏電站的參數(shù)匯總和網(wǎng)絡(luò)簡化等效，得到光伏集群的動(dòng)態(tài)等效模型。Liu, Zhihan[3]等將AP 算法應(yīng)用于共享單車服務(wù)方面，提出了一種通過聚類確定倉庫位置的優(yōu)化方法，利用AP 聚類算法的出租車OD 點(diǎn)，通過分析AP 聚類算法，對(duì)基于管理區(qū)域分割進(jìn)行了分層優(yōu)化，考慮出租車OD 點(diǎn)的稀疏相似度矩陣，對(duì)AP 聚類的輸入?yún)?shù)進(jìn)行了調(diào)整。Guojun Gan[4]等在AP聚類算法中引入屬性權(quán)重，提出了一種子空間聚類算法，屬性權(quán)重的相對(duì)大小可用于標(biāo)識(shí)嵌入集群的子空間。針對(duì)AP 聚類算法對(duì)流形數(shù)據(jù)集的聚類效果并不理想，本文提出利用類之間的緊致度來進(jìn)行類的合并，對(duì)緊致度大于閾值的相鄰類采取合并措施，文本引入新的相似度矩，陣實(shí)驗(yàn)表明合并后類的數(shù)量減少，聚類結(jié)果更加合理。

1 AP 聚類概述

相似度矩陣是AP 算法的基礎(chǔ)，相似度矩陣可以是對(duì)稱的，也可以是不對(duì)稱的，能否得到合適的相似度矩陣決定了聚類效果的優(yōu)劣。本文利用無向加權(quán)圖，構(gòu)造相似度矩陣Sij，將每個(gè)樣本看作無向圖的每個(gè)頂點(diǎn)來構(gòu)建無向加權(quán)圖，構(gòu)造公式如下：

dij表示xi和xj的歐氏距離，σ 是平衡因子，

在相似度矩陣中，S (i , j )表示樣本j 多大程度上適合作為樣本i 所屬類的中心，對(duì)角線上的元素S ( )k , k 稱為偏向參數(shù)，S ( k , k )的值越大，則k 作為類代表點(diǎn)的可能性就越大。通常設(shè)定所有的偏向參數(shù)為p，聚類的數(shù)量受p 影響，若p 值為相似度中的最小值，則得到的聚類數(shù)最小，若p 為相似度的最大值則聚類數(shù)最多，得到的類數(shù)越多，通常取相似度均值作為p 值，計(jì)算公式為[5]：

AP 算法中引入兩個(gè)信息參數(shù)，吸引度信息r (i , j )和歸屬度信息a ( i , j )，對(duì)任意樣本i，在其他樣本中選擇對(duì)其吸引度和歸屬度最大的樣本作為其類代表點(diǎn)，AP 算法的核心就是這兩個(gè)值的交替更新，為避免發(fā)生震蕩我們引入阻尼系數(shù)λ[6]，（取值為0.1），假設(shè)t 是當(dāng)前迭代次數(shù)，更新公式為如下：

吸引度更新：

SAP-Algorithm 算法1

輸入：S 表示相似度矩陣，X 為數(shù)據(jù)集合，M 表示最大迭代次數(shù)，r(0), a(0)表示初始的吸引度和歸屬度，P 偏向參數(shù)，聚類中心集合V ={v1, v2, ..., vt}，計(jì)數(shù)器m

輸出：類別{v1, v2, ..., vt}

begin

①M(fèi)=500，m=0，r(0)=0，a(0)=0，V = ?；

②P = p ( S ) //根據(jù)式（2）計(jì)算偏向參數(shù)；

③while m 〈 M do；

④for xk, xi∈X do；

⑤if makx { a (i , k ) + r (i , k )}do；

⑥v ←k; //xi類代表點(diǎn)是xk；

⑦m++；

⑧for others ( xi) do；

⑨v ←xi;///分配給各自的最優(yōu)類代表點(diǎn)end；

算法分析：本算法在已知相似度矩陣的基礎(chǔ)上進(jìn)行，由于相似度矩陣已經(jīng)計(jì)算出，所以不必算相似度矩陣，算法在while 循環(huán)內(nèi)，對(duì)元素xi，計(jì)算該元素與其他元素的吸引度與歸屬度的和，并求出最大值，找到該元素的類代表點(diǎn)。最后對(duì)于其他的元素分配給最大的類代表點(diǎn)。SAP 算法不需要事先指定聚類數(shù)目，將所有點(diǎn)作為聚類中心。盡管AP算法對(duì)一些結(jié)構(gòu)簡單的數(shù)據(jù)其聚類效果好，但是對(duì)一些結(jié)構(gòu)比較復(fù)雜（如非團(tuán)狀）的數(shù)據(jù)集，它卻往往得不到很好的聚類效果。對(duì)于這一缺陷本文提出了基于ε 鄰域的類合并，其主要思想是將對(duì)象的ε 鄰域定義為結(jié)構(gòu)算子，然后利用結(jié)構(gòu)算子對(duì)SAP 算法s 的結(jié)果進(jìn)行融合，合并原本屬于同一類的結(jié)果。

2 類的合并

定 義 1（ε 鄰 域 ） 設(shè) 數(shù) 據(jù) 集 U ={ x1, x2, …, xn} 中 ， xi∈U， 稱 Nε( )xi={y ∈U:d ( y , xi) ≤ε} 。

定 義 2（q 近 鄰 距 離 ） 設(shè)C = { c1, c2, …, ck}[8]，是DPC 算法的聚類結(jié)果，xe∈Ci(i = 1 , 2 , …, k )，QNN ( )xe是在Ci中距離xe的最近的q 個(gè)點(diǎn)的集合，xt∈QNN (xe)，稱為點(diǎn)xe的q 近鄰距離；為 類Ci的q 近鄰距離。

定 義 3相 鄰 類 對(duì) 于 類 Ci[9]，任 取xb∈Cj( i ≠j )，取ε = p ?avg ( Cj)，考慮xb的ε鄰域，若Nε( xb)?Ci≠?，則xb為臨界點(diǎn)。Ci與Cj屬于相鄰類。

類的合并,如果一個(gè)類中的元素的鄰域包含其他類中的元素，則此元素為該類的臨界點(diǎn)，我們可以根據(jù)臨界點(diǎn)與另外類的緊密聯(lián)系程度，來決定兩個(gè)類是否進(jìn)行合并。對(duì)于相鄰類的臨界點(diǎn)我們采取的策略是：對(duì)于相鄰類計(jì)算兩個(gè)相鄰類的類臨界點(diǎn)之間的緊致度Tij，計(jì)算公式如下：

SAP-Algorithm 算法2

輸入：聚類的結(jié)果C = {c1, c2, …, ck}，臨界閾值α。

輸出類簇:合并后的類C = {c1, c2, …, cm}。

①根據(jù)定義3 求出相鄰類（如Ci和Cj相鄰，則Ci，Cj是相鄰類）；

②如果相鄰類的Tij′大于閾值α,則對(duì)兩個(gè)類進(jìn)行合并，否則不進(jìn)行合并；

③ 重 新 輸 出 新 的 聚 類 結(jié) 果 C ={c1, c2, …, cm}；

上述算法是基于算法一的聚類結(jié)果的基礎(chǔ)上；利用T′ij對(duì)類進(jìn)行合并，算法二只計(jì)算類的臨界點(diǎn)集合，并不是計(jì)算類的所有點(diǎn)，大大的降低算法的時(shí)間復(fù)雜度，提高了算法的效率。

3 實(shí)驗(yàn)

本節(jié)通過實(shí)驗(yàn)對(duì)所提的算法進(jìn)行性能分析，本文算法的思想為：通過AP 聚類算法得到初始的類簇中心點(diǎn)和初始類，使得初始化聚類中心和類簇得到確定，由于類的個(gè)數(shù)自動(dòng)生成，有時(shí)可能會(huì)產(chǎn)生過多的類別個(gè)數(shù)，其中一些類可以合并，聚類結(jié)果不準(zhǔn)確所以用類的相異度計(jì)算確定需要合并的類。仿真環(huán)境：軟件Python3.8，操作系統(tǒng)win10 64 位，硬件CPU2.0GHz，內(nèi)存8GB，硬盤500G。

用自定義數(shù)據(jù)集進(jìn)行聚類，該數(shù)據(jù)集為流形數(shù)據(jù)集，共兩類，使用原始的AP 算法得到的結(jié)果分成四類，因?yàn)樵糀P 基于歐氏距離對(duì)環(huán)形數(shù)據(jù)集的效果并不理想。為了解決這種問題，我們把相似度較高的類別重新結(jié)合在一起，便會(huì)得到更好的聚類結(jié)果，采用類與類之間的合并來處理這種情況。

圖1 AP 算法的聚類結(jié)果

圖2 SAP 算法的額聚類結(jié)果

圖2 我們得到的最終聚類結(jié)果，已經(jīng)成功的把許多能合并的類別合并在一起，把原本誤分的類已經(jīng)合并，合并之后的聚類結(jié)果比較合理，從圖中清楚的看到分為兩類。

接下來對(duì)環(huán)形數(shù)據(jù)集分別用K-means 和SAP進(jìn)行對(duì)比實(shí)驗(yàn)，圖三是對(duì)Kmeans 的聚類結(jié)果，該算法把環(huán)形數(shù)據(jù)集分成四部分，聚類的結(jié)果數(shù)目并不準(zhǔn)確，圖4 是SPA 算法的聚類結(jié)果，該結(jié)果很好的把環(huán)形數(shù)據(jù)集分為兩類，內(nèi)環(huán)和外環(huán)，相比K-means 聚類結(jié)果更加準(zhǔn)確。

圖3 k-means 算法的聚類結(jié)果

圖4 SAP 算法的額聚類結(jié)果

為了準(zhǔn)確的描述聚類的結(jié)果優(yōu)劣，引入以下三個(gè)指標(biāo)評(píng)價(jià)聚類結(jié)果的優(yōu)劣Purity 評(píng)價(jià)法[10～13]、RI 評(píng)價(jià)法、F 值評(píng)價(jià)法、ACC 我們用這四個(gè)指標(biāo)來衡量算法的準(zhǔn)確度和精度，求得四個(gè)指標(biāo)的均值和標(biāo)準(zhǔn)差。把AP 算法、K-means 算法[14]，DBSCAN 算法[15]、SAP 算法進(jìn)行對(duì)比。從表1 可以看出，K-means 和原始AP 聚類算法采用的是歐氏距離作為度量，所以對(duì)這種流形數(shù)據(jù)集聚類的數(shù)目多于實(shí)際的聚類數(shù)目，而DBSCN 是基于密度的聚類，得到的類別數(shù)正確，但是在ACC、Purity、RI、F 方面指標(biāo)不如SAP，因?yàn)镾AP 對(duì)相似度矩陣進(jìn)行了改進(jìn)，并且對(duì)能合并的類進(jìn)行了合并，綜上所述，SAP 算法要優(yōu)于其他幾種算法。

表1 算法對(duì)比

接下來采用UCI 數(shù)據(jù)集中的準(zhǔn)確率對(duì)比實(shí)驗(yàn)，本文對(duì)上述四個(gè)算法進(jìn)行準(zhǔn)確率對(duì)比實(shí)驗(yàn)，在UCI 數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果如表2 所示，從表中可以看出，SPA 算法在所有的數(shù)據(jù)集上的聚類準(zhǔn)確率明顯高于其他的三個(gè)算法。因?yàn)楸疚牟扇☆惻c類之間的緊致度，進(jìn)行了類的合并，例如，Iris 有三個(gè)類，其中兩個(gè)類之間有交叉，采用本文的方法可以有效解決這種情況。

表2 準(zhǔn)確率對(duì)比試驗(yàn)（%）

表3 是對(duì)時(shí)間耗時(shí)方面的分析，從中可以看到AP 和K-means 耗時(shí)比SPA 要少，因?yàn)樵妓惴ú恍枰M(jìn)行類的合并等所以時(shí)間最少，但是本文的算法采用了只對(duì)臨界的集合進(jìn)行計(jì)算，因此時(shí)間耗時(shí)并沒有相差很大，而DBSAN 算法由于對(duì)整個(gè)數(shù)據(jù)集進(jìn)行計(jì)算所以時(shí)間的相對(duì)與本文算法來說很高，綜上所述本文的算法在精確度上比其他算法要高，耗時(shí)也是本文算法的優(yōu)點(diǎn)。

表3 時(shí)間對(duì)比試驗(yàn)（s）

4 結(jié)束語

本文在針對(duì)AP 聚類算法不能對(duì)流形數(shù)據(jù)集進(jìn)行聚類，采用一種基于無向加權(quán)圖的相似度矩陣，并且提出類與類之間緊致度的概念，對(duì)大于閾值的類進(jìn)行合并，試驗(yàn)結(jié)果表明，不管在時(shí)間復(fù)雜度還是準(zhǔn)確率方面，本文的算法都有優(yōu)勢(shì)。由于不同的數(shù)據(jù)集閾值不同，后續(xù)研究的重點(diǎn)是對(duì)閾值的選取進(jìn)行研究。