王鵬飛，楊余旺，柯亞琪

(1.南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,江蘇 南京 210094; 2.南京農(nóng)業(yè)大學(xué)園藝學(xué)院，江蘇 南京 210095)

1 引言

近年來(lái)隨著數(shù)據(jù)的不斷增長(zhǎng)和累積，如何從這些大數(shù)據(jù)中挖掘出有用的信息成為了當(dāng)前的研究熱點(diǎn)，聚類就是一種能夠從大數(shù)據(jù)中挖掘出有用信息的有效方法[1]。聚類是聚類分析的簡(jiǎn)稱，是一種無(wú)監(jiān)督的學(xué)習(xí)過(guò)程[2]。聚類是在無(wú)先驗(yàn)認(rèn)知的條件下，根據(jù)發(fā)現(xiàn)的數(shù)據(jù)對(duì)象的相似性，將對(duì)象分組，從而達(dá)到對(duì)數(shù)據(jù)的深刻理解，獲得有用信息或者壓縮數(shù)據(jù)的目的[3,4]。

聚類分析現(xiàn)在已經(jīng)應(yīng)用于諸多領(lǐng)域，如：數(shù)據(jù)庫(kù)知識(shí)發(fā)現(xiàn)、計(jì)算機(jī)視覺(jué)、圖像處理、生物信息學(xué)等[5]。正因?yàn)榫垲惙治龅膶?shí)用性，許多聚類算法已經(jīng)被人們提出，其中比較經(jīng)典的有K-means算法、模糊C-means算法、具有噪聲的基于密度的聚類方法DBSCAN(Density-Based Spatial Clustering of Applications with Noise)算法等，近幾年又提出了近鄰傳播AP(Affinity Propagation)算法和CFSFDP(Clustering by Fast Search and Find of Density Peaks)算法[6]。這些聚類算法都旨在解決不同情況下的大數(shù)據(jù)聚類問(wèn)題。K-means算法是一種基于距離的迭代式算法，其旨在將數(shù)據(jù)點(diǎn)劃分到距離最近的聚類中心所在的簇中，但K-means算法需要提前指定聚類中心的個(gè)數(shù)，且對(duì)于非球形的數(shù)據(jù)集很難取得令人滿意的聚類結(jié)果[7]?；跀?shù)據(jù)點(diǎn)的密度進(jìn)行聚類的算法，如經(jīng)典的DBSCAN算法，則擺脫了對(duì)數(shù)據(jù)集形狀要求的束縛，它可以得到任意形狀的類簇。DBSCAN算法需選擇一個(gè)密度閾值，密度高于該閾值的點(diǎn)則成為“核心點(diǎn)”，之后將所有“密度相連”的點(diǎn)聚合為一個(gè)類[8]。DBSCAN算法不需要事先確定聚類中心的個(gè)數(shù)，且能夠很好地排除噪聲點(diǎn)和離群點(diǎn)。但是，該算法對(duì)于密度分布不均勻的數(shù)據(jù)集所取得的效果并不理想，且該算法最終的結(jié)果對(duì)所選擇的密度閾值十分敏感，這使得對(duì)于密度閾值的選擇有一定的困難。除了上述兩個(gè)問(wèn)題外，DBSCAN算法的計(jì)算復(fù)雜度也很高，這也導(dǎo)致它很難運(yùn)用于高維數(shù)據(jù)環(huán)境[9]。

Rodriguez等人[10]于2014年在《Science》上提出了一種基于密度峰值的空間聚類算法，該算法可以對(duì)任何無(wú)規(guī)則的數(shù)據(jù)集進(jìn)行聚類[11]?？焖賹ふ颐芏葮O點(diǎn)聚類算法CFSFDP算法首先通過(guò)使用一截?cái)嗑嚯x來(lái)計(jì)算每個(gè)點(diǎn)的局部密度，然后計(jì)算各數(shù)據(jù)點(diǎn)與局部密度高于它們的數(shù)據(jù)點(diǎn)之間的最小距離；然后根據(jù)計(jì)算出的每個(gè)點(diǎn)的局部密度和最小距離繪制決策圖，接著在決策圖中人工選取聚類的中心，之后將剩余的非聚類中心的數(shù)據(jù)點(diǎn)劃分到與之距離最近的聚類中心所在的簇中；最后再將所得到的各個(gè)簇劃分為簇核心和簇光暈，從而得到最終的聚類結(jié)果。使用CFSFDP算法進(jìn)行聚類時(shí)只需要計(jì)算一次距離，并且不需要進(jìn)行迭代，因此算法的計(jì)算速度很快。但是，該算法選擇聚類中心的時(shí)候需要在決策圖中人工選取，這增加了算法的冗余性，不利于算法的自動(dòng)化，且在最后將簇劃分為簇核心和簇光暈時(shí)會(huì)將簇邊緣的本屬于簇核心的一些點(diǎn)劃分到簇光暈中，影響最終的聚類效果。

針對(duì)CFSFDP算法上述兩個(gè)不足點(diǎn)，本文引入了一種聚類中心的自動(dòng)選擇策略，通過(guò)使用異常檢測(cè)的思想自動(dòng)計(jì)算得到數(shù)據(jù)集的聚類中心，從而避免了CFSFDP算法需要在決策圖中人工選擇聚類中心，影響算法自動(dòng)化的問(wèn)題。并且在得到初步的聚類結(jié)果后進(jìn)行簇核心和簇光暈的劃分時(shí)，引入了簇內(nèi)局部密度的概念，改進(jìn)了CFSFDP算法原本的劃分方法，使得簇核心和簇光暈點(diǎn)劃分結(jié)果更為合理。實(shí)驗(yàn)結(jié)果表明，本文提出的算法可以有效地提高CFSFDP算法的自動(dòng)化程度，并且最終得到的聚類結(jié)果與CFSFDP算法相比更為準(zhǔn)確合理。

2 CFSFDP算法

CFSFDP算法進(jìn)行聚類時(shí)首先需要確定類的中心點(diǎn)，其假設(shè)簇的聚類中心的局部密度高于其周圍數(shù)據(jù)點(diǎn)的局部密度，并且聚類中心與那些局部密度更高的數(shù)據(jù)點(diǎn)之間的距離較大。對(duì)于一個(gè)給定的數(shù)據(jù)集，CFSFDP算法需要為每個(gè)數(shù)據(jù)點(diǎn)計(jì)算兩個(gè)量化值：數(shù)據(jù)點(diǎn)的局部密度ρi和它與局部密度比其高的數(shù)據(jù)點(diǎn)之間的距離δi。

數(shù)據(jù)點(diǎn)xi的局部密度ρi有兩種計(jì)算方式：基于截?cái)嗪说挠?jì)算方式和基于高斯核的計(jì)算方式。使用截?cái)嗪擞?jì)算局部密度ρi的公式為:

χ(δij-dc)

(1)

使用高斯核計(jì)算局部密度ρi的公式為:

(2)

其中,δij為數(shù)據(jù)點(diǎn)之間的距離，Is為i的值域，dc為截?cái)嗑嚯x即距離閾值。使用該計(jì)算方式得到的局部密度ρi仍然滿足與數(shù)據(jù)點(diǎn)xi的距離小于dc的點(diǎn)越多，局部密度ρi就越大的結(jié)論。使用截?cái)嗪擞?jì)算局部密度和使用高斯核計(jì)算局部密度這兩種計(jì)算方式的區(qū)別在于使用截?cái)嗪擞?jì)算得到的結(jié)果為離散值而使用高斯核計(jì)算得到的結(jié)果為連續(xù)值。因此，相對(duì)而言，使用高斯核計(jì)算得到的數(shù)據(jù)點(diǎn)具有相同的局部密度的概率比使用截?cái)嗪擞?jì)算得到的數(shù)據(jù)點(diǎn)具有相同的局部密度的概率要小，使用高斯核計(jì)算局部密度ρi更方便比較數(shù)據(jù)點(diǎn)局部密度之間的大小關(guān)系。

數(shù)據(jù)點(diǎn)之間的距離δi是通過(guò)計(jì)算數(shù)據(jù)點(diǎn)xi與比該數(shù)據(jù)點(diǎn)局部密度高的其他數(shù)據(jù)點(diǎn)的距離得到的，數(shù)據(jù)點(diǎn)之間的距離δi可以根據(jù)公式(3)計(jì)算得到。

(3)

一般而言，數(shù)據(jù)點(diǎn)之間的距離δi為數(shù)據(jù)點(diǎn)i與比該數(shù)據(jù)點(diǎn)局部密度ρi更高的其他數(shù)據(jù)點(diǎn)的所有距離中的最小值，但對(duì)于局部密度ρi最高的點(diǎn)，數(shù)據(jù)點(diǎn)之間的距離δi為其他數(shù)據(jù)點(diǎn)與之距離的最大值。

CFSFDP算法根據(jù)數(shù)據(jù)點(diǎn)之間的距離δi與數(shù)據(jù)點(diǎn)的局部密度ρi的各自的大小關(guān)系繪制決策圖，通過(guò)在決策圖中人工選取簇的聚類中心，其決策圖如圖1所示。算法將δi值大且ρi值較大的點(diǎn)認(rèn)定為簇的聚類中心，即在決策圖中處于右上角與其他點(diǎn)分離明顯的部分點(diǎn)。在確定簇的聚類中心之后，便將其他剩余的數(shù)據(jù)點(diǎn)劃分到局部密度比其高且與之距離最近的聚類中心所在的簇中。

Figure 1 Decision graph of CFSFDP圖1 CFSFDP算法決策圖

CFSFDP算法不同于DBSCAN等聚類算法，其對(duì)于較低密度的簇類點(diǎn)沒(méi)有引入噪聲的概念，而是為每一個(gè)簇引入了一個(gè)光暈的概念，簇的光暈中則包含了其他算法中所定義的噪聲以及數(shù)據(jù)集中的離散點(diǎn)。CFSFDP算法將一個(gè)簇劃分為簇核心和簇光暈，屬于簇核心中的數(shù)據(jù)點(diǎn)的局部密度ρi較大，而屬于簇光暈中的數(shù)據(jù)點(diǎn)的局部密度ρi較小，局部密度ρi較小的點(diǎn)則包含了簇的噪聲點(diǎn)以及數(shù)據(jù)集的離散點(diǎn)。為了劃分簇的簇核心與簇光暈，CFSFDP算法引入了“邊界區(qū)域”的概念，它的定義為：數(shù)據(jù)點(diǎn)屬于該簇，但在與該數(shù)據(jù)點(diǎn)的距離小于dc的范圍內(nèi)存在屬于其他簇的數(shù)據(jù)點(diǎn)，由這些點(diǎn)構(gòu)成的區(qū)域范圍稱為該簇的“邊界區(qū)域”。在取得每個(gè)簇的“邊界區(qū)域”后，將“邊界區(qū)域”中局部密度最大的點(diǎn)的局部密度值作為該簇的簇核心與簇光暈的分割閾值ρb。最后根據(jù)該簇中的數(shù)據(jù)點(diǎn)的局部密度ρi與該簇的密度閾值ρb的關(guān)系將該簇?cái)?shù)據(jù)點(diǎn)劃分到簇核心或者簇光暈中，若該簇內(nèi)的數(shù)據(jù)點(diǎn)的局部密度ρi大于ρb，則該數(shù)據(jù)點(diǎn)劃分到該簇的簇核心中，否則將其劃分到該簇的簇光暈中。經(jīng)過(guò)將各簇進(jìn)行簇核心與簇光暈的劃分之后便得到了CFSFDP算法最終的聚類結(jié)果。

3 CFSFDP算法改進(jìn)

CFSFDP算法在選擇聚類中心時(shí)需要人工輔助選擇，選擇方式為在決策圖中，將右上角的點(diǎn)作為起點(diǎn)，向左下方拉矩形，利用矩形框選擇與其它點(diǎn)差異最大的一組點(diǎn)，該組點(diǎn)即為聚類中心。該過(guò)程因?yàn)樾枰斯⑴c，使得算法的冗余性增加，并且人工選擇具有一定的主觀性，選擇結(jié)果的不同將會(huì)影響最終聚類的結(jié)果，這不利于最終結(jié)果的準(zhǔn)確性以及算法的自動(dòng)化。除此之外，CFSFDP算法在劃分簇核心和簇光暈時(shí)，會(huì)將一些處于簇邊緣的數(shù)據(jù)點(diǎn)劃分到簇光暈中，使得最終得到的聚類結(jié)果的準(zhǔn)確性降低。本節(jié)針對(duì)CFSFDP算法上述兩個(gè)不足點(diǎn)提出了優(yōu)化方案，使得算法可以自動(dòng)選擇聚類中心且對(duì)于簇核心與簇光暈的劃分更為合理，從而獲得更合理的聚類效果。

3.1 聚類中心的自動(dòng)選擇

通過(guò)對(duì)CFSFDP算法的介紹可知，CFSFDP算法有兩個(gè)基本立足點(diǎn)：

(1)聚類中心的局部密度很大。

(2)聚類中心與其他局部密度更大的數(shù)據(jù)點(diǎn)之間的距離相對(duì)較大。

根據(jù)這兩個(gè)基本立足點(diǎn)可知，聚類中心的局部密度ρi和與局部密度比其高的數(shù)據(jù)點(diǎn)之間的距離δi這兩個(gè)值都是比較大的。鑒于此，本文提出的聚類中心自動(dòng)選擇的策略為：使用標(biāo)準(zhǔn)化的局部密度ρi和相鄰距離δi的乘積來(lái)評(píng)測(cè)聚類點(diǎn)之間的差異度，然后對(duì)于該乘積使用高斯分布進(jìn)行異常檢測(cè)的方法得出其中的異常點(diǎn)，對(duì)于需要進(jìn)行聚類的數(shù)據(jù)集而言，這些異常點(diǎn)即為聚類中心。高斯分布是非常適合做異常檢測(cè)的一個(gè)模型，分布在兩端的小概率事件可認(rèn)為是異常點(diǎn)，利用這一點(diǎn)可以得到數(shù)據(jù)集的聚類中心。

首先引入一個(gè)簇中心權(quán)值的概念，定義一個(gè)數(shù)據(jù)點(diǎn)的簇中心權(quán)值γi為:

(4)

(5)

(6)

接著對(duì)于每個(gè)γi，根據(jù)公式(7)分別計(jì)算它們各自的概率密度。

(7)

最后根據(jù)p(γi)與給定的一個(gè)閾值ε的關(guān)系來(lái)判斷數(shù)據(jù)點(diǎn)是否為異常點(diǎn)即聚類中心，ε為一個(gè)較小的常數(shù)，本文選取的閾值為0.005。對(duì)于交叉驗(yàn)證集可以嘗試多個(gè)ε，并基于該ε計(jì)算交叉驗(yàn)證集上的F1值，取最高者返回。F1的定義如下：

(8)

Figure 2 3-spiral dataset圖2 三螺旋數(shù)據(jù)集

Figure 3 Clustering center obtained from anomaly detection圖3 異常檢測(cè)所得的聚類中心圖

算法1給出了聚類過(guò)程中簇的聚類中心自動(dòng)選擇的具體步驟。

算法1聚類中心自動(dòng)選擇策略

步驟1將每個(gè)數(shù)據(jù)點(diǎn)的局部密度ρi和數(shù)據(jù)點(diǎn)間的距離δi標(biāo)準(zhǔn)化。

步驟2求取每個(gè)點(diǎn)的簇中心權(quán)值γi。

步驟4求取每個(gè)點(diǎn)的概率密度p(γi)。

步驟5判斷p(γi)與閾值ε的大小關(guān)系，若滿足p(γi)<ε，則該數(shù)據(jù)點(diǎn)為簇中心，否則不是聚類中心。

3.2 簇核心與簇光暈的分割優(yōu)化

χ(διj-dc),ci=cj

(9)

算法2給出了在得到初步的聚類結(jié)果后，所得到的簇的簇核心與簇光暈分割的具體步驟。

算法2簇核心與簇光暈分割策略

步驟1確定簇的“邊界區(qū)域”。

步驟2求取“邊界區(qū)域”內(nèi)每個(gè)數(shù)據(jù)點(diǎn)的簇內(nèi)局部密度。

步驟3計(jì)算“邊界區(qū)域”的平均簇內(nèi)局部密度。

Figure 4 Three types of classical datasets圖4 三種典型的數(shù)據(jù)集

4 仿真實(shí)驗(yàn)

為了表明本文所提算法的有效性，使用Matlab進(jìn)行數(shù)據(jù)仿真得到聚類結(jié)果。選用三個(gè)具有代表性的數(shù)據(jù)集：數(shù)據(jù)集1來(lái)自文獻(xiàn)[13]，是一組模擬的二維數(shù)據(jù)集，如圖4a所示，共有788個(gè)數(shù)據(jù)點(diǎn)，該數(shù)據(jù)集的數(shù)據(jù)分布較為密集，各區(qū)域間的分隔較為明顯，一般該數(shù)據(jù)集根據(jù)數(shù)據(jù)點(diǎn)的聚集情況被劃分為7類；數(shù)據(jù)集2來(lái)自文獻(xiàn)[14]，是一組由15個(gè)相似的二維高斯分布組成的模擬數(shù)據(jù)集，如圖4b所示，共有600個(gè)數(shù)據(jù)點(diǎn)，該數(shù)據(jù)集中，四周的數(shù)據(jù)分布較為稀疏，中間部分的數(shù)據(jù)分布較為密集且各區(qū)域之間粘連較多，一般該數(shù)據(jù)集根據(jù)數(shù)據(jù)點(diǎn)的聚集情況被劃分為15類；數(shù)據(jù)集3是一組選自O(shè)livetti人臉數(shù)據(jù)集(Olivetti Face Database)中的部分圖像，圖中每一行為同一個(gè)人的不同表情的圖像，同一個(gè)人的不同圖像之間有細(xì)微的差別，是一組真實(shí)的數(shù)據(jù)集，如圖4c所示。

圖5為使用原始CFSFDP算法對(duì)數(shù)據(jù)集1和數(shù)據(jù)集2進(jìn)行聚類時(shí)得到的決策圖，圖中灰色的點(diǎn)為人工選擇得出的數(shù)據(jù)集的聚類中心，點(diǎn)的個(gè)數(shù)即為數(shù)據(jù)集聚類時(shí)類的個(gè)數(shù)，這些點(diǎn)是多次人工選擇聚類中心進(jìn)行實(shí)驗(yàn)后選出的最為合理的聚類中心點(diǎn)。圖6為使用本文所提出的異常檢測(cè)方法所得到的數(shù)據(jù)集中的聚類中心，圖中灰色的點(diǎn)為算法自動(dòng)計(jì)算得出的聚類中心。

Figure 5 Decision graphs obtained by CFSFDP圖5 利用原始CFSFDP算法獲得的決策圖

Figure 6 Clustering center obtained from improved CFSFDP anomaly detection圖6 改進(jìn)的CFSFDP算法異常檢測(cè)得到的聚類中心圖

Figure 7 Comparison of decision graph and anomaly detection of datasets 1圖7 數(shù)據(jù)集1決策圖法與異常檢測(cè)法實(shí)驗(yàn)結(jié)果對(duì)比

Figure 8 Experimental result comparison between decision graph and anomaly detection of datasets 2圖8 數(shù)據(jù)集2決策圖法與異常檢測(cè)法實(shí)驗(yàn)結(jié)果對(duì)比

圖7和圖8為對(duì)數(shù)據(jù)集1和數(shù)據(jù)集2使用CFSFDP決策圖方法得到的聚類結(jié)果與使用改進(jìn)的CFSFDP算法的異常檢測(cè)方法得到的聚類結(jié)果，圖中每種灰度代表一個(gè)簇，黑色的點(diǎn)則為各簇的簇光暈部分。圖7和圖8中使用異常檢測(cè)法得到的聚類結(jié)果中，簇核心與簇光暈的劃分使用的是原始CFSFDP算法中簇核心與簇光暈的劃分方法。從圖7和圖8對(duì)比可以看出，使用改進(jìn)的常檢測(cè)方法得到的聚類結(jié)果與使用原始決策圖法得到的聚類結(jié)果完全相同，這表明使用改進(jìn)的CFSFDP算法得到的聚類中心較為準(zhǔn)確，可以代替使用原始CFSFDP算法的決策圖法人工選擇聚類中心，實(shí)現(xiàn)對(duì)CFSFDP算法的進(jìn)一步自動(dòng)化。

在得到初步的聚類結(jié)果后，對(duì)得到的簇進(jìn)行簇核心與簇光暈分割優(yōu)化后的實(shí)驗(yàn)結(jié)果如圖9所示，圖中黑色的點(diǎn)為分割后的簇的簇光暈部分。通過(guò)圖9a與圖7a的對(duì)比以及圖9b與圖8a的對(duì)比可以看出，使用本文提出的簇核心與簇光暈優(yōu)化分割方法得到的實(shí)驗(yàn)結(jié)果，將簇的邊緣部分本屬于簇核心部分的數(shù)據(jù)點(diǎn)劃入簇光暈中的幾率變小，只有簇之間粘連部分的數(shù)據(jù)點(diǎn)以及數(shù)據(jù)集中的離散點(diǎn)被劃入了簇光暈中，得到的最終實(shí)驗(yàn)結(jié)果與CFSFDP算法得到的實(shí)驗(yàn)結(jié)果相比更為合理。

Figure 9 Division optimization results of cluster core and cluster halo圖9 簇核心與簇光暈分割優(yōu)化實(shí)驗(yàn)結(jié)果圖

圖10為對(duì)數(shù)據(jù)集3的Olivetti人臉數(shù)據(jù)集聚類后的結(jié)果，圖10a為使用CFSFDP算法得到的聚類結(jié)果，圖10b為使用本文改進(jìn)的CFSFDP算法得到的聚類結(jié)果。圖10中的人臉小圖的右上角使用圓點(diǎn)標(biāo)記的為算法所選擇的聚類中心，人臉小圖左下角的每種小圖標(biāo)代表一個(gè)簇，左下角未被小圖標(biāo)標(biāo)記的人臉小圖則不屬于任何一個(gè)簇。從實(shí)驗(yàn)結(jié)果可以看出，本文改進(jìn)的CFSFDP算法自動(dòng)選取的聚類中心與原始CFSFDP算法人工選取的聚類中心相同，從聚類的結(jié)果來(lái)看本文改進(jìn)的方法略優(yōu)于原始的CFSFDP算法。

Figure 10 Clustering result comparison between CFSFDP and the optimized CFSFDP 圖10 原始CFSFDP算法與本文改進(jìn)的CFSFDP算法對(duì)Olivetti人臉數(shù)據(jù)集進(jìn)行聚類的實(shí)驗(yàn)結(jié)果圖

從上述對(duì)比實(shí)驗(yàn)可以看出，本文提出的方法可以有效地提高CFSFDP算法的自動(dòng)化程度，且聚類效果更準(zhǔn)確有效。

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

本文提出的算法是對(duì)CFSFDP算法的兩點(diǎn)不足進(jìn)行的優(yōu)化改進(jìn)。針對(duì)CFSFDP算法需要在決策圖中人工選擇聚類中心，導(dǎo)致算法的準(zhǔn)確性和自動(dòng)化受到影響，本文采用改進(jìn)的CFSFDP算法的異常檢測(cè)方法自動(dòng)計(jì)算出聚類中心，針對(duì)CFSFDP算法最后進(jìn)行簇核心與簇光暈分割時(shí)會(huì)將簇的邊緣數(shù)據(jù)點(diǎn)劃入簇光暈中，影響實(shí)驗(yàn)結(jié)果，本文通過(guò)引入簇內(nèi)局部密度，根據(jù)簇內(nèi)數(shù)據(jù)點(diǎn)的局部密度與簇內(nèi)局部密度的平均值的關(guān)系劃分簇核心和簇光暈。仿真實(shí)驗(yàn)對(duì)比結(jié)果表明，本文提出的算法是有效可行的，其實(shí)驗(yàn)結(jié)果比原始CFSFDP算法的實(shí)驗(yàn)結(jié)果更為準(zhǔn)確合理。