噪聲環(huán)境下復(fù)雜流形數(shù)據(jù)的勢(shì)能層次聚類算法

于曉飛，葛洪偉

(1.江南大學(xué) 輕工過(guò)程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 無(wú)錫 214122；2. 江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無(wú)錫 214122)

0 引 言

聚類分析作為一種無(wú)監(jiān)督的學(xué)習(xí)方法，是數(shù)據(jù)挖掘中的一項(xiàng)重要任務(wù)，它按照一定的規(guī)則將數(shù)據(jù)劃分成若干類，使相同類數(shù)據(jù)盡可能相似，不同類數(shù)據(jù)盡可能相異[1]。聚類分析既可以作為獨(dú)立的數(shù)據(jù)挖掘工具來(lái)對(duì)數(shù)據(jù)進(jìn)行分析，也可以作為其他數(shù)據(jù)挖掘算法的預(yù)處理過(guò)程，其在生物信息、信息檢索、機(jī)器學(xué)習(xí)、人工智能等領(lǐng)域有著重要作用[2-3]。

目前聚類分析已經(jīng)吸引了大量的研究目光，有許多經(jīng)典的聚類算法被提出，如基于劃分方法的K-means[4-5]，K-mediods[6]等，這些算法雖然簡(jiǎn)單快速，但聚類結(jié)果對(duì)初始類簇中心的選取有一定的依賴；基于層次的聚類方法如Cure[7]，Chameleon[8]等，這些算法雖可檢測(cè)非球形簇，但算法過(guò)程相對(duì)復(fù)雜，在具體應(yīng)用中都存在一定的局限性；基于密度的聚類方法如DBSCAN[9]，OPTICS[10]等，這些算法雖然可以發(fā)現(xiàn)任意形狀的簇，但對(duì)于參數(shù)十分敏感；基于網(wǎng)格的聚類方法如STING[11]，WAVECLUSTER[12]等，這些聚類算法雖有較好的聚類效果，但處理時(shí)間與空間所劃分單元數(shù)有關(guān)，一定程度上降低了聚類的質(zhì)量和準(zhǔn)確度。

Yonggang Lu等[13]提出一種基于勢(shì)能的聚類(clustering by sorting potential values，CSPV) 算法，該算法雖提出了基于勢(shì)能的相似性度量準(zhǔn)則，但聚類效果完全依賴于對(duì)參數(shù)B的選取。針對(duì)這一問(wèn)題，Yonggang Lu等[14]于2013年在《Pattern Recognition》上提出了一種基于勢(shì)能的快速凝聚層次聚類(potential-based hierarchical agglomerative clustering，PHA)算法。該算法十分便捷高效，首先依據(jù)各點(diǎn)的勢(shì)能和與父節(jié)點(diǎn)的距離構(gòu)造邊緣加權(quán)樹(shù)，然后依據(jù)樹(shù)中權(quán)值大小使用層次聚類得到最終的聚類結(jié)果。PHA算法使用全新的相似性度量準(zhǔn)則，并與凝聚層次聚類相結(jié)合，在時(shí)間上更快速，在精度上可以得到更好的聚類效果。

PHA算法雖然具有上述優(yōu)點(diǎn)，但該算法只能處理一些結(jié)構(gòu)簡(jiǎn)單的、簇內(nèi)勢(shì)能大小分布明顯不同的球形簇，無(wú)法處理一些復(fù)雜的流形結(jié)構(gòu)簇，而且聚類結(jié)果易受到噪聲數(shù)據(jù)的影響。針對(duì)這一缺陷，本文提出了噪聲環(huán)境下復(fù)雜流形數(shù)據(jù)的勢(shì)能層次聚類算法 (hierarchical clustering based on potential in complex flow data with noise，HCPC)。首先，根據(jù)勢(shì)能遞增曲線確定勢(shì)能閾值，找到數(shù)據(jù)集中的噪聲點(diǎn)；其次，在非噪聲數(shù)據(jù)點(diǎn)上，定義出勢(shì)能最大、最小2層數(shù)據(jù)，并基于勢(shì)能的分布特點(diǎn)，提出分層聚類的方法，以確定類簇的大體框架；最后，在分層聚類結(jié)果的基礎(chǔ)上，對(duì)正常點(diǎn)使用層次聚類，同時(shí)將噪聲點(diǎn)聚到距離自身最近的類簇中去。實(shí)驗(yàn)表明，HCPC算法不僅可以識(shí)別噪聲點(diǎn)，而且能有效地處理復(fù)雜的流形數(shù)據(jù)集，同時(shí)在真實(shí)數(shù)據(jù)集上具有更優(yōu)的聚類效果。

1 PHA算法及其缺陷分析

1.1 PHA算法

PHA算法[14]認(rèn)為，數(shù)據(jù)點(diǎn)的勢(shì)能大小與其概率密度分布是密切相關(guān)的。該算法首先根據(jù)重力勢(shì)能的物理意義來(lái)計(jì)算每個(gè)數(shù)據(jù)的勢(shì)能。其中，每2點(diǎn)之間的勢(shì)能Φij定義為

(1)

(1)式中：rij是點(diǎn)i與點(diǎn)j之間的歐式距離；δ用來(lái)避免分母為零的情況出現(xiàn)。δ的計(jì)算方式為

(2)

δ=mean(MinDi)/S

(3)

(2)—(3)式中：MinDi是點(diǎn)i到其他各點(diǎn)的最短距離；N是數(shù)據(jù)點(diǎn)的個(gè)數(shù)；S是一個(gè)尺度因子[14]，一般設(shè)為10。

計(jì)算了每2點(diǎn)之間的勢(shì)能Φij后，每個(gè)點(diǎn)的勢(shì)能Φi定義為

(4)

文獻(xiàn)[14]中使用Parzen窗口函數(shù)[15]這一非參數(shù)估計(jì)方法來(lái)證明勢(shì)能和概率密度分布的關(guān)系。在Parzen窗口函數(shù)中概率密度的定義為

(5)

(5)式中，N表示數(shù)據(jù)點(diǎn)總數(shù)。

文獻(xiàn)[14]經(jīng)過(guò)證明得到

(6)

即勢(shì)能和概率密度函數(shù)成反比，其中，α是歸一化因子，它的主要作用是確保窗口函數(shù)在所有特征空間上的積分為1。因此，勢(shì)能可以反映數(shù)據(jù)點(diǎn)的分布情況，如勢(shì)能越小的點(diǎn)的周圍數(shù)據(jù)點(diǎn)分布越密集。

將勢(shì)能從小到大排序，并以勢(shì)能最小的點(diǎn)作為根節(jié)點(diǎn)，構(gòu)造邊緣加權(quán)樹(shù)，其他數(shù)據(jù)點(diǎn)尋找自身的父節(jié)點(diǎn)。其中，父節(jié)點(diǎn)定義為

(7)

即勢(shì)能小于點(diǎn)i且與i距離最近的點(diǎn)為其父節(jié)點(diǎn)。

點(diǎn)i到父節(jié)點(diǎn)parent[i]的距離ρi為

ρi=ri,parent[i]

(8)

在邊緣加權(quán)樹(shù)中，每個(gè)數(shù)據(jù)點(diǎn)與父節(jié)點(diǎn)之間的權(quán)值為兩者的距離。在樹(shù)構(gòu)造完成后，使用凝聚層次聚類算法進(jìn)行聚類，得到聚類結(jié)果。

1.2 PHA算法缺陷分析

PHA算法雖然十分便捷快速，但其只能處理一些簇內(nèi)勢(shì)能分布明顯不均勻的數(shù)據(jù)集如圖1所示。然而，針對(duì)一些復(fù)雜的流形數(shù)據(jù)集，PHA算法無(wú)法得到理想的聚類結(jié)果。

圖1 DS1數(shù)據(jù)集Fig.1 DS1 data set

其原因在于一些復(fù)雜的數(shù)據(jù)集簇內(nèi)勢(shì)能分布較均勻，無(wú)明顯差異，缺陷分析示例如圖2所示。圖2a中，該數(shù)據(jù)集中2個(gè)環(huán)形簇的簇內(nèi)勢(shì)能分布相對(duì)均勻，且中間的團(tuán)狀簇勢(shì)能整體偏小。PHA算法在構(gòu)建樹(shù)的過(guò)程中，環(huán)形簇上的點(diǎn)會(huì)錯(cuò)誤地選取中間的團(tuán)簇上的點(diǎn)作為父節(jié)點(diǎn)；圖2b中，以點(diǎn)a，b，c為例：Φ(a)<Φ(b)，Φ(a)<Φ(c)，但由于r(a,b)

圖2 缺陷分析示例Fig.2 Defect example analysis

同時(shí)，針對(duì)含噪聲的數(shù)據(jù)集，由于PHA算法在聚類過(guò)程中沒(méi)有對(duì)噪聲數(shù)據(jù)進(jìn)行處理，導(dǎo)致其聚類結(jié)果易受到噪聲數(shù)據(jù)的影響，無(wú)法得到正確的聚類結(jié)果。

2 含噪聲的復(fù)雜流形數(shù)據(jù)的勢(shì)能層次聚類

2.1 識(shí)別噪聲點(diǎn)

HCPC算法采用構(gòu)造勢(shì)能遞增曲線的方法識(shí)別噪聲點(diǎn)。一般情況下，由于各數(shù)據(jù)集中噪聲點(diǎn)的數(shù)量遠(yuǎn)少于正常數(shù)據(jù)點(diǎn)，且噪聲點(diǎn)的分布相對(duì)稀疏，因此其勢(shì)能較大。噪聲點(diǎn)判定如圖3所示，在勢(shì)能遞增曲線上，噪聲點(diǎn)與正常點(diǎn)之間存在一個(gè)拐點(diǎn)，圖3a中的點(diǎn)C即為圖3b中數(shù)據(jù)集的拐點(diǎn)，拐點(diǎn)之前的點(diǎn)為正常點(diǎn)，拐點(diǎn)之后的點(diǎn)為噪聲點(diǎn)，圖3b中的星型點(diǎn)為該數(shù)據(jù)集被識(shí)別的噪聲點(diǎn)。

圖3 噪聲點(diǎn)判定Fig.3 Determination of noise points

2.2 勢(shì)能的分層

基于對(duì)重力勢(shì)能物理意義的分析發(fā)現(xiàn)，勢(shì)能可以反映數(shù)據(jù)點(diǎn)的分布情況[14]。勢(shì)能分布圖如圖4所示，勢(shì)能大小由內(nèi)向外逐層遞增，邊緣點(diǎn)的勢(shì)能最大，中心點(diǎn)的勢(shì)能最小。與此同時(shí)，受文獻(xiàn)[16]中分層聚類的啟發(fā)，提出依據(jù)勢(shì)能將數(shù)據(jù)點(diǎn)分層聚類的方法。

圖4 勢(shì)能分布圖Fig.4 Graph ofpotential field

定義1勢(shì)能最大層數(shù)據(jù)集Smax定義為

Smax={i|Φi≥Φn}

(9)

定義2勢(shì)能最小層數(shù)據(jù)集Smin定義為

Smin={i|Φi≤Φp}

(10)

(9)—(10)式中：Φn為去除噪聲點(diǎn)后，勢(shì)能從大到小排序后，第?N′×0.25」個(gè)數(shù)據(jù)[16]；Φp為勢(shì)能從小到大排序后，第?N′×0.25」個(gè)數(shù)據(jù)[16]。

假設(shè)通過(guò)勢(shì)能遞增曲線確定的噪聲點(diǎn)總數(shù)為n，正常點(diǎn)總數(shù)為N′

N′=N-n

(11)

以圖1和圖2a所示的2個(gè)數(shù)據(jù)集為例，分別取勢(shì)能最大、最小2層數(shù)據(jù)，如圖5，圖6中星形點(diǎn)所示。由圖5，圖6可見(jiàn)，勢(shì)能最大層的數(shù)據(jù)一般處于類邊緣位置，或某類數(shù)據(jù)的勢(shì)能整體較大；而勢(shì)能最小層的數(shù)據(jù)一般處于中心位置，或某類數(shù)據(jù)的勢(shì)能整體較小。

圖5 DS1分層Fig.5 Layer of DS1

圖6 DS2分層Fig.6 Layer of DS2

基于上述分析，分別將最大、最小層數(shù)據(jù)進(jìn)行單獨(dú)聚類，可以確定類簇的大致輪廓。因此，依據(jù)文獻(xiàn)[17]中介紹的方法，通過(guò)勢(shì)能和與父節(jié)點(diǎn)距離的乘積γi來(lái)自動(dòng)聚類，其中，γi定義[17]為

γi=|Φi|·ρi=-Φi·ρ

(12)

2層數(shù)據(jù)的聚類結(jié)果如圖7所示，圖7中黑色圓點(diǎn)為未聚類數(shù)據(jù)點(diǎn)。

圖7 分層聚類結(jié)果Fig.7 Clustering result of hierarchy clustering

最后使用最小類間距離測(cè)度將得到的子簇與剩余數(shù)據(jù)進(jìn)行層次聚類，得到如圖8所示的聚類結(jié)果。

圖8 DS1與DS2聚類結(jié)果Fig.8 Clustering results of DS1 and DS2

綜上所述，HCPC算法通過(guò)依據(jù)勢(shì)能分層聚類，不僅可以自適應(yīng)地識(shí)別噪聲點(diǎn)，而且能夠有效處理復(fù)雜的流形數(shù)據(jù)集。

2.3 HCPC算法步驟

HCPC算法流程簡(jiǎn)單描述如下。

步驟1由(1)—(4)式計(jì)算出每個(gè)數(shù)據(jù)點(diǎn)的勢(shì)能Φi，并排序；

步驟2根據(jù)勢(shì)能大小構(gòu)造勢(shì)能遞增曲線，找到拐點(diǎn)，識(shí)別噪聲點(diǎn)；

步驟3由定義1、定義2確定最大、最小層數(shù)據(jù)；

步驟4分別在最大、最小2層數(shù)據(jù)內(nèi)依據(jù)(7)式確定每個(gè)數(shù)據(jù)點(diǎn)的父節(jié)點(diǎn)parent[i]，并由(8)式計(jì)算各層中的數(shù)據(jù)點(diǎn)到自身父節(jié)點(diǎn)的距離ρi；

步驟5分別在2層數(shù)據(jù)集內(nèi)由(12)式計(jì)算各點(diǎn)的γi值，使用文獻(xiàn)[17]中介紹的算法分別對(duì)2層數(shù)據(jù)進(jìn)行自動(dòng)聚類；

步驟6在步驟5的聚類結(jié)果基礎(chǔ)上，對(duì)整個(gè)數(shù)據(jù)集采用最小類間距離測(cè)度進(jìn)行層次聚類，直到所有正常數(shù)據(jù)點(diǎn)的類別都確定為止；

步驟7最后，將步驟2確定的噪聲數(shù)據(jù)分別聚到離其最近的類別中去。

2.4 算法復(fù)雜度分析

HCPC算法的時(shí)間復(fù)雜度主要由3部分組成：計(jì)算勢(shì)能和距離；在最大、最小層數(shù)據(jù)上對(duì)γi值分類；使用最小類間距離進(jìn)行層次聚類。假設(shè)數(shù)據(jù)點(diǎn)個(gè)數(shù)為n，則計(jì)算勢(shì)能和距離的時(shí)間復(fù)雜度為O(n2)，在最大、最小2層數(shù)據(jù)上對(duì)γi值分類的時(shí)間復(fù)雜度為O(n)，最后層次聚類的時(shí)間復(fù)雜度為O(n2)，因此，HCPC算法的時(shí)間復(fù)雜度為O(n2)。文獻(xiàn)[14]中介紹PHA算法的時(shí)間復(fù)雜度為O(n2)，可見(jiàn)，HCPC算法在沒(méi)有增加算法時(shí)間復(fù)雜度的同時(shí)，提高了算法的聚類效果。

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

為了驗(yàn)證HCPC算法的性能，分別在人工數(shù)據(jù)集和UCI[18]數(shù)據(jù)集上與PHA算法[14]，CSPV(基于排序勢(shì)能的聚類算法)[13]進(jìn)行對(duì)比實(shí)驗(yàn)。

3.1 人工數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果分析

表1 4個(gè)人工數(shù)據(jù)集信息

表1中，DS為Data Set的縮寫(xiě)，其中，DS1由3組服從標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù)構(gòu)成，各組的中心數(shù)據(jù)點(diǎn)分別為(0,0)，(3,5)和(6,0)，每組有300個(gè)數(shù)據(jù)，如1.2節(jié)中圖1；DS2由2個(gè)環(huán)狀簇和1個(gè)團(tuán)狀簇構(gòu)成，如1.2節(jié)中圖2a；DS3由1個(gè)流形簇和2個(gè)團(tuán)狀簇構(gòu)成，如圖9a；DS4為2個(gè)流形簇相互纏繞所構(gòu)成，如圖9b(為證實(shí)HCPC算法能夠處理噪聲環(huán)境的復(fù)雜流形數(shù)據(jù)，特在DS3，DS4數(shù)據(jù)集上添加噪聲點(diǎn))。

基于歐氏距離測(cè)度，分別使用PHA，HCPC，CSPV 3種算法對(duì)表1中的4個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。其中，圖10，圖11分別為PHA和CSPV算法得到的聚類結(jié)果，由圖10，圖11可知，PHA和CSPV算法只能在類似DS1的球形數(shù)據(jù)集上得到正確的聚類結(jié)果，而無(wú)法處理復(fù)雜的流形數(shù)據(jù)集，且針對(duì)含噪聲的數(shù)據(jù)集，聚類結(jié)果易受噪聲點(diǎn)的影響。

圖9 DS3，DS4數(shù)據(jù)集Fig.9 DS1 and DS2 data sets

圖10 PHA在人工數(shù)據(jù)集的聚類結(jié)果Fig.10 Clustering results onsynthetic datasets by PHA

圖12為HCPC算法得到的聚類結(jié)果，該算法首先識(shí)別噪聲數(shù)據(jù)，然后根據(jù)勢(shì)能分層聚類，確定了類簇的邊緣與中心部分，最后在不受噪聲數(shù)據(jù)的影響下得到正確的聚類結(jié)果。由圖12a可見(jiàn)，針對(duì)類內(nèi)勢(shì)能分布明顯不均勻的團(tuán)簇結(jié)構(gòu)，3種算法都可以得到正確的聚類結(jié)果；而針對(duì)PHA算法與CSPV算法無(wú)法處理的類內(nèi)勢(shì)能分布均勻、類間勢(shì)能分布差異明顯的DS2數(shù)據(jù)集，HCPC算法亦能得到正確的聚類結(jié)果。

針對(duì)含噪聲的復(fù)雜數(shù)據(jù)集DS3，DS4，PHA算法與CSPV算法無(wú)法識(shí)別噪聲點(diǎn)，而且受噪聲點(diǎn)的影響，最終沒(méi)有得到正確的聚類結(jié)果(見(jiàn)圖10，圖11)；但通過(guò)HCPC算法可以識(shí)別噪聲點(diǎn)并有效處理這一類數(shù)據(jù)集。

圖11 CSPV在人工數(shù)據(jù)集的聚類結(jié)果Fig.11 Clustering results on synthetic datasets by CSPV

圖12 HCPC在人工數(shù)據(jù)集的聚類結(jié)果Fig.12 Clustering results on synthetic datasets by HCPC

由此可見(jiàn)，HCPC算法不僅保留了PHA算法快速高效的優(yōu)點(diǎn)，還解決了該算法無(wú)法有效處理噪聲環(huán)境下復(fù)雜流形數(shù)據(jù)的缺陷。

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

為了進(jìn)一步驗(yàn)證HCPC算法的性能，選取了5個(gè)UCI[18]數(shù)據(jù)集與PHA算法、CSPV算法進(jìn)行實(shí)驗(yàn)對(duì)比，如表2所示。

表2 5個(gè)真實(shí)數(shù)據(jù)集信息

同時(shí)，使用FMIndex[19]，F(xiàn)1-measure[20]和ARI[21]3種聚類評(píng)價(jià)指標(biāo)來(lái)衡量種算法的聚類效果。3種指標(biāo)值的取值均為[0,1]，數(shù)值越大，表示聚類效果越好。實(shí)驗(yàn)結(jié)果如表3—表5所示(各指標(biāo)的最大值用下橫線標(biāo)出)。

表3 PHA算法在真實(shí)數(shù)據(jù)集上的聚類指標(biāo)值

表4 HCPC算法在真實(shí)數(shù)據(jù)集上的聚類指標(biāo)值

表5 CSPV算法在真實(shí)數(shù)據(jù)集上的聚類指標(biāo)值

由表3，表4中的數(shù)據(jù)可見(jiàn)，與PHA算法相比，在iris數(shù)據(jù)集上，2種算法的各聚類指標(biāo)值相等；在letter數(shù)據(jù)集上，雖然PHA算法的ARI聚類指標(biāo)值高于HCPC算法，但在其余2種聚類指標(biāo)值上均為HCPC算法更高；除此之外，在剩余的3個(gè)數(shù)據(jù)集上，HCPC的3種聚類指標(biāo)值均高于PHA算法。產(chǎn)生上述結(jié)果的原因：一方面，HCPC算法對(duì)噪聲數(shù)據(jù)進(jìn)行了識(shí)別，聚類結(jié)果不受噪聲數(shù)據(jù)的影響；另一方面，HCPC算法采用勢(shì)能分層的思想，可以得到更優(yōu)的聚類效果。

由表4，表5中的數(shù)據(jù)可見(jiàn)，與CSPV算法相比，在iris數(shù)據(jù)集上，2種算法的各聚類指標(biāo)值相等；在letter數(shù)據(jù)集上，雖然CSPV算法的3種聚類指標(biāo)值最高，但該算法是在選取了最優(yōu)參數(shù)B值的前提下得到上述聚類結(jié)果，且聚類數(shù)目遠(yuǎn)遠(yuǎn)高于HCPC算法；在vowel數(shù)據(jù)集上，雖然CSPV算法的ARI指標(biāo)值高于HCPC算法，但另外2種指標(biāo)值上均為HCPC算法更高；除此之外，在剩余的glass與wine數(shù)據(jù)集上，HCPC算法的3種聚類指標(biāo)值均為最高。

整體而言，HCPC算法能夠得到更優(yōu)的聚類結(jié)果，具有更高的準(zhǔn)確度。

4 結(jié)束語(yǔ)

針對(duì)PHA算法無(wú)法有效處理流形數(shù)據(jù)集且對(duì)噪聲數(shù)據(jù)敏感的缺陷，本文提出了HCPC算法。與PHA算法相比，HCPC算法在保留原算法快速高效的優(yōu)勢(shì)的前提下，不僅彌補(bǔ)了PHA算法的不足，而且可以得到更優(yōu)的聚類效果。然而，由于HCPC算法采用了歐氏距離的距離測(cè)度方法，不利于其處理一些維度較高的數(shù)據(jù)集。因此，如何使HCPC算法可以在高維數(shù)據(jù)集上得到更好的聚類結(jié)果，將是下一步的研究工作。