儲德潤，周治平

（江南大學(xué) 物聯(lián)網(wǎng)技術(shù)應(yīng)用教育部工程研究中心，江蘇 無錫 214122）

聚類技術(shù)作為機(jī)器學(xué)習(xí)領(lǐng)域中的一種無監(jiān)督技術(shù)，在檢測數(shù)據(jù)的內(nèi)在結(jié)構(gòu)和潛在知識方面發(fā)揮著重要的作用。在過去的幾十年中，許多聚類方法得到了發(fā)展，如基于分區(qū)的方法(k-means)、基于模型的方法、基于密度的方法、層次聚類方法、模糊聚類方法(fuzzy c-means)和基于圖的方法(spectral clustering)[1]。由于譜聚類在處理非凸形結(jié)構(gòu)的數(shù)據(jù)集方面的高效性，譜聚類在圖像分割[2-4]、社區(qū)檢測[5]、人臉識別[6]等方面得到了廣泛的研究和應(yīng)用。

然而，傳統(tǒng)的譜聚類算法在使用高斯核函數(shù)構(gòu)造親和矩陣時，需要先驗(yàn)信息來設(shè)置合適的參數(shù)以控制鄰域的尺度；并且以距離來度量數(shù)據(jù)點(diǎn)之間的相似性，沒有考慮到整體數(shù)據(jù)點(diǎn)的變化情況，對于高維數(shù)據(jù)來說，較難得到更高的聚類精度。近年來有很多學(xué)者對譜聚類算法進(jìn)行了研究。趙曉曉等[7]結(jié)合稀疏表示和約束傳遞，提出一種結(jié)合稀疏表示和約束傳遞的半監(jiān)督譜聚類算法，進(jìn)一步提高了聚類準(zhǔn)確率。林大華等[8]針對現(xiàn)有子空間聚類算法沒有利用樣本自表達(dá)和稀疏相似度矩陣，提出了一種新的稀疏樣本自表達(dá)子空間聚類方法，所獲得的相似度矩陣具有良好的子空間結(jié)構(gòu)和魯棒性。Chang等[9]提出了一種通過嵌入標(biāo)簽傳播來改進(jìn)譜聚類的方法，通過密集的未標(biāo)記數(shù)據(jù)區(qū)域傳播標(biāo)簽。以上方法雖然一定程度上提高了譜聚類算法的聚類性能，但是，在大部分譜聚類算法中，高斯核函數(shù)中尺度參數(shù)的選取往往都是通過人工選取，對聚類結(jié)果有一定的影響。NJW算法[10]對預(yù)先給定幾個尺度參數(shù)進(jìn)行譜聚類，最后從這幾個聚類結(jié)果中選擇具有最佳聚類結(jié)果的作為尺度參數(shù)，該方法消除了尺度參數(shù)選擇的人為因素，但是也增加了計(jì)算時間。Ye等[11]在有向KNN圖中考慮了一種基于共享最近鄰的魯棒相似性度量，大大提高了譜聚類的聚類精度。Jia等[12]提出了一種基于共享近鄰的自校正p譜聚類算法，該算法利用共享最近鄰來度量數(shù)據(jù)間的相似性，然后應(yīng)用果蠅優(yōu)化算法找到p-laplacian矩陣的最優(yōu)參數(shù)p，從而更好地進(jìn)行數(shù)據(jù)分類。王雅琳等[13]提出一種基于密度調(diào)整的改進(jìn)自適應(yīng)譜聚類算法，通過樣本點(diǎn)的近鄰距離自適應(yīng)得到尺度參數(shù)，使算法對尺度參數(shù)相對不敏感。

傳統(tǒng)的譜聚類以及上述大部分改進(jìn)的譜聚類算法都是單一的針對距離度量或者尺度參數(shù)進(jìn)行調(diào)整，本文從一個新的角度出發(fā)，在公理化模糊集(AFS)理論的基礎(chǔ)上，結(jié)合局部密度估計(jì)和共享近鄰的定義，提出一種基于AFS理論的共享近鄰自適應(yīng)譜聚類算法——公理化模糊共享近鄰自適應(yīng)譜聚類算法。利用AFS理論提出了一種模糊相似性度量方法，并將其作為譜聚類算法輸入的親和矩陣。同時采用共享近鄰的方法發(fā)現(xiàn)密集區(qū)域樣本點(diǎn)分布的結(jié)構(gòu)和密度信息，并且根據(jù)每個點(diǎn)所處領(lǐng)域的稠密程度自適應(yīng)調(diào)節(jié)參數(shù)，與高斯核距離測度相比，本文的解決方案對參數(shù)具有較強(qiáng)的魯棒性，增強(qiáng)了對各種數(shù)據(jù)集的適應(yīng)性，減少了噪聲數(shù)據(jù)帶來的不良影響。

1 相關(guān)算法理論

1.1 譜聚類算法

作為一種簡單而有效的聚類準(zhǔn)則，歸一化割(Ncut)在文獻(xiàn)[14]中提出，其定義為

5)利用經(jīng)典的聚類算法如k-means對特征向量空間中的特征向量進(jìn)行聚類。

1.2 AFS理論

AFS理論是劉曉東[15-18]在1998年提出的一種基于AFS代數(shù)和AFS結(jié)構(gòu)的模糊理論，AFS理論放棄使用距離度量來計(jì)算數(shù)據(jù)之間的相似性關(guān)系，而是將觀測數(shù)據(jù)轉(zhuǎn)化為模糊隸屬函數(shù)，并實(shí)現(xiàn)其邏輯運(yùn)算。然后，可以從AFS空間而不是原始特征空間中提取信息。在AFS空間中利用模糊關(guān)系來構(gòu)建數(shù)據(jù)之間的相似性度量。采用模糊隸屬度來表示數(shù)據(jù)之間的距離關(guān)系，增強(qiáng)了在處理現(xiàn)實(shí)數(shù)據(jù)中對各種數(shù)據(jù)集的適應(yīng)性，為處理離群點(diǎn)提供了有效方法。

在文獻(xiàn)[15]中，根據(jù)EI代數(shù)的定義，對于任意概念集合，表示A中模糊概念的集合，為了更好地提取數(shù)據(jù)結(jié)構(gòu)，清楚地說明可將AFS理論結(jié)合以下場景：

這些基于簡單概念的EI代數(shù)運(yùn)算生成的概念被認(rèn)為復(fù)雜的概念。

其中，每個模糊集可以被唯一地分解：

2 所提算法

2.1 在模糊空間建立距離度量

本文提出的親和矩陣構(gòu)造方法是建立在AFS理論基礎(chǔ)上的，該過程允許我們在發(fā)現(xiàn)的判別模糊子空間中表示不同模糊項(xiàng)的樣本。這些子空間由模糊隸屬函數(shù)選擇，消除了不明顯或噪聲特征。因此，它們被認(rèn)為能夠改善內(nèi)部相似和減少相互相似。此外，利用AFS中定義的模糊隸屬度和邏輯運(yùn)算，放寬了歐氏假設(shè)對數(shù)據(jù)距離推斷的影響。更具體地說，本文使用一個樣本的隸屬度屬于另一個樣本的描述，用模糊集表示為距離度量。在最初的AFS聚類[19-21]基礎(chǔ)上，在AFS空間上構(gòu)建相似性度量。

首先建立隸屬度函數(shù)，需要定義以下有序關(guān)系：設(shè)X是一個樣本集合，M是X上的一組模糊集合。對于任意，，可以寫成：

在AFS理論的基礎(chǔ)上，為了更好地提取數(shù)據(jù)結(jié)構(gòu)，在AFS空間中建立了距離測量，公式為

2.2 所提算法

在2.1小節(jié)中雖然利用AFS理論在譜聚類算法中構(gòu)建了新的距離度量，即,但是高斯核函數(shù)中是一個人工指定的參數(shù)，為每個數(shù)據(jù)集指定一個合適的參數(shù)是一件很復(fù)雜的事，需要花費(fèi)大量的時間和精力。本文將數(shù)據(jù)點(diǎn)的領(lǐng)域信息加入相似度的計(jì)算中，并結(jié)合共享近鄰的思想，在AFS理論距離測量的基礎(chǔ)上定義了一個能夠自適應(yīng)得到尺度參數(shù)的高斯核函數(shù)——基于AFS理論的共享近鄰自適應(yīng)高斯核函數(shù)，其定義為

2.3 所提算法流程

算法 公理化模糊共享近鄰自適應(yīng)譜聚類算法(AFSSNNSC)

11)利用經(jīng)典的聚類算法如k-means對特征向量空間中的特征向量進(jìn)行聚類。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境及性能指標(biāo)

在UCI、USPS手寫數(shù)字的相同數(shù)據(jù)集上，采用本文提出的方法和文獻(xiàn)[10]的NJW譜聚類(SC)、文獻(xiàn)[21]的AFS聚類算法(AFS)、文獻(xiàn)[22]的self-tuning spectral clustering(STSC)算法、基于K均值的近似譜聚類(KASP)[23]、基于Nystrom近似譜聚類(Nystrom)[24]和基于地標(biāo)點(diǎn)譜聚類算法(LSC-R，LSC-K)[25]進(jìn)行對比實(shí)驗(yàn)。本文算法實(shí)驗(yàn)是在MATLAB 2014b，計(jì)算機(jī)的硬件配置為Intel i7-4770 CPU 3.40 GHz、16 GB RAM的平臺下進(jìn)行。為了評估所提算法的聚類性能，本文使用聚類誤差(CE)[26]和歸一化互信息(NMI)[27]2種性能指標(biāo)對本文算法與其他聚類方法的聚類結(jié)果進(jìn)行了比較。其中CE被廣泛用于評價聚類性能，CE越低聚類性能越好。NMI也是一種廣泛使用的評估算法聚類性能的測量標(biāo)準(zhǔn)，NMI越大性能越好。

3.2 UCI數(shù)據(jù)集實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證所提出算法的有效性，本文將所提的算法和其他方法應(yīng)用于UCI數(shù)據(jù)庫中的11個基準(zhǔn)數(shù)據(jù)集作為測試樣本，表1為這11類數(shù)據(jù)集的特征，分別是數(shù)據(jù)總量、維數(shù)以及類的個數(shù)。

表1 UCI實(shí)驗(yàn)數(shù)據(jù)集的特性Table 1 Characteristics of the UCI experimental datasets

基于聚類誤差(CE)的實(shí)驗(yàn)結(jié)果如表2所示，由表2可知所提的方法在大部分實(shí)驗(yàn)數(shù)據(jù)集上均獲得了優(yōu)于對比算法的CE值；所提出的方法在Heart、Hepatitis、Wdbc、Protein 和 Libras數(shù)據(jù)集上的CE分別為15.27%、27.14%、6.03%、51.12%、52.31%，相比較AFS算法而言均改進(jìn)了10%以上，在其他5個數(shù)據(jù)集上的CE相比較AFS也均有所提高。證明了利用譜理論對相似矩陣進(jìn)行劃分比之前提出的傳遞閉包理論好得多，考慮到傳遞閉包方法的驗(yàn)證循環(huán)，所提出的方法也相對更快、更容易實(shí)現(xiàn)。在Iris、Wine數(shù)據(jù)集中，所提算法的CE分別為7.42%和2.89%，相對聚類錯誤率略高于STSC算法。因?yàn)檫@兩個數(shù)據(jù)集中只有150個樣本和178個樣本，但是差異實(shí)際上只有一兩個樣本，但相對于總體而言，所提算法CE普遍低于其他算法在各數(shù)據(jù)集上的結(jié)果，仍具有較好的優(yōu)越性；與基于距離度量的方法相比所提算法在給出的所有數(shù)據(jù)集中都顯示出了優(yōu)越性，在Sonar數(shù)據(jù)集上更加改進(jìn)5%以上，本文算法與基于Nystrom近似譜聚類方法相比在所有數(shù)據(jù)集上均有1%以上的優(yōu)勢。本文算法與基于地標(biāo)點(diǎn)的譜聚類方法LSC-R和LSC-K相比也展現(xiàn)出較好的聚類性能。這是因?yàn)橥ㄟ^模糊隸屬函數(shù)代替距離度量數(shù)據(jù)之間的相似性，利用模糊語義結(jié)構(gòu)解釋數(shù)據(jù)之間的復(fù)雜的相互關(guān)系，增強(qiáng)了算法的魯棒性。對于Protein、Libras等多聚類數(shù)據(jù)集，AFS的聚類錯誤率偏高，因?yàn)锳FS聚類需要根據(jù)每個集群的邊界選擇最好的數(shù)據(jù)聚類分區(qū)。隨著集群規(guī)模數(shù)量的不斷增加，將很難去清晰地找到邊界，這樣聚類誤差也會隨之增高。總體而言，與對比文獻(xiàn)方法相比，所提算法的CE值在所有實(shí)驗(yàn)數(shù)據(jù)集上均得到了改善，降低了算法的聚類錯誤率。

表2 UCI數(shù)據(jù)集上的CE比較Table 2 Comparison of CE on the UCI datasets %

在歸一化互信息(NMI)中測量的聚類性能如表3所示。所提出的算法的聚類結(jié)果NMI與其他方法的NMI相比都得到了改善，尤其在Heart和Protein數(shù)據(jù)集上，所提算法相對于KASP、SC、STSC、AFS和Nystrom對比算法而言NMI均提高了5%以上。只是在Wine數(shù)據(jù)集上，所提算法的NMI為87.86%，與其他算法相當(dāng)，但在整個對比表格中為最好的聚類性能。由于所選Covertype數(shù)據(jù)集是一個從地圖變量預(yù)測森林覆蓋類型的數(shù)據(jù)集，它們都主要是在荒野地區(qū)發(fā)現(xiàn)的，所以覆蓋類型在實(shí)際地理上是非常接近的，相對于其他數(shù)據(jù)集而言，這個數(shù)據(jù)集數(shù)據(jù)特性更加復(fù)雜。所以在Covertype數(shù)據(jù)集下所有算法的NMI都普遍較低，但是所提算法獲得了比其他算法更好的聚類效果。

從實(shí)驗(yàn)結(jié)果可以看出，STSC不是很穩(wěn)定，它在Hepatitis和Sonar數(shù)據(jù)集上的NMI情況都非常差，由于在STSC和本文算法中都考慮到了數(shù)據(jù)之間的相互關(guān)系，利用到了數(shù)據(jù)鄰居的近鄰作用，所以可以從中得出結(jié)論，與考慮到數(shù)據(jù)樣本關(guān)系之間的傳統(tǒng)距離度量作為相似性度量相比，采用具有數(shù)據(jù)樣本模糊關(guān)系的模糊隸屬度作為距離度量，在相似性度量上更具有魯棒性?？傮w而言，所提算法相較于對比算法都具有明顯的改善。

表3 UCI數(shù)據(jù)集上的NMI比較Table 3 Comparison of NMI on the UCI datasets %

3.3 USPS數(shù)據(jù)集實(shí)驗(yàn)結(jié)果與分析

選擇兩個典型譜聚類算法SC和STSC與所提方法在廣泛使用的USPS數(shù)據(jù)庫中的手寫數(shù)字?jǐn)?shù)據(jù)集進(jìn)行對比實(shí)驗(yàn)。該數(shù)據(jù)集包含美國郵政總局通過掃描信封中的手寫數(shù)字獲得的數(shù)字?jǐn)?shù)據(jù)。原始掃描的數(shù)字是二進(jìn)制的，大小和方向不同。本文使用的圖像經(jīng)過了大小歸一化，得到了1 616張256維的灰度圖像。它包含7 291個訓(xùn)練實(shí)例和2 007個測試實(shí)例(總共9 298個)。為了展示該方法的可伸縮性，考慮了不同數(shù)量的集群。具體來說，數(shù)字子集{0,8}、{4,9}、{0,5,8}、{3,5,8}、{1,2,3,4}、{0,2,4,6,7}和整個集合{0,1,···,9}用于測試本文提出的算法。這些子集的詳細(xì)信息如表4所示。分別在每個子集上進(jìn)行實(shí)驗(yàn)，并使用CE和NMI來測量性能。

表4 USPS實(shí)驗(yàn)數(shù)據(jù)集的特性Table 4 Characteristics of the USPS experimental datasets

從圖1可以看出，在CE方面，所提算法在所有的情況下都優(yōu)于STSC和SC，尤其在{0,8}、{0,5,8}、{3,5,8}、{0,2,4，6,7}、{0,1,···,9}數(shù)據(jù)集上CE均改善了5%以上，甚至在{3,5,8}上CE相較于其他對比算法，所提算法改進(jìn)了10%以上。總體而言與SC和STSC相比，可以從圖1中看出所提出的方法均得到明顯的改善。

圖1 USPS數(shù)據(jù)集上CE的性能比較Fig. 1 Performance comparison of CE on the USPS datasets

圖2 顯示了基于NMI的USPS數(shù)據(jù)集的結(jié)果。從圖2中可以看出，所提出的方法在所有情況下都比SC和STSC有優(yōu)勢。在{0,8}、{1,2,3,4}、{0,1,···,9}上相較于其他對比算法，所提算法的NMI都提高了10%以上，特別是對于具有挑戰(zhàn)性的情況{3,5,8}和多類情況{1,2,3,4}、{0,2,4,6,7}、{0,1,···,9}，所提出的算法都具有一定的優(yōu)越性。

圖2 USPS數(shù)據(jù)集上NMI的性能比較Fig. 2 Performance comparison of NMI on the USPS datasets

4 結(jié)束語

本文提出了一種新的無監(jiān)督廣義數(shù)據(jù)親和圖的構(gòu)造方法，該方法具有更強(qiáng)的魯棒性和更有意義的數(shù)據(jù)親和圖，以提高譜聚類精度。采用模糊理論定義數(shù)據(jù)相似度，利用模糊隸屬度函數(shù)導(dǎo)出親和圖。此外，親和圖不是盲目地相信所有可用變量，而是通過捕捉和通過對每個樣本的模糊描述，確定了特征子空間中組合分布的微妙兩兩相似關(guān)系。同時采用共享近鄰的方法發(fā)現(xiàn)密集區(qū)域樣本點(diǎn)分布的結(jié)構(gòu)和密度信息，并且根據(jù)每個點(diǎn)所處領(lǐng)域的稠密程度自動調(diào)節(jié)參數(shù)，從而生成更強(qiáng)大的親和矩陣，進(jìn)一步提高聚類準(zhǔn)確率，證明了該方法對不同類型數(shù)據(jù)集的有效性。實(shí)驗(yàn)結(jié)果表明，該方法與其他先進(jìn)的方法相比具有一定的優(yōu)越性。數(shù)據(jù)大小的多樣性在一定程度上體現(xiàn)了該方法對于大數(shù)據(jù)集的可擴(kuò)展性。在未來將通過系統(tǒng)地將所提出的算法與一些采樣或量化策略相結(jié)合來處理一般的可伸縮性問題。