結合代表點和密度峰的增量動態(tài)聚類算法

鄭河榮，陳 懇，潘 翔

(浙江工業(yè)大學 計算機科學與技術學院，浙江 杭州 310023)

結合代表點和密度峰的增量動態(tài)聚類算法

鄭河榮，陳 懇，潘 翔

(浙江工業(yè)大學 計算機科學與技術學院，浙江 杭州 310023)

為了解決增量大數(shù)據(jù)聚類速度緩慢問題，提出了一種結合密度峰和代表點分析的快速聚類算法.先對樣本集進行初始化聚類，然后根據(jù)刪除失效的聚類數(shù)據(jù)調節(jié)聚類簇群的密度均值，再利用代表點的算法對樣本集進行更新，最后采用密度峰算法進行重復聚類從而更新聚類核心點.通過實驗分析表明：該算法可有效提高算法收斂速度.在應用方面，將這種聚類算法引用到大數(shù)據(jù)量的人臉聚類工作中，優(yōu)化人臉聚類的效果.

時效性；在線聚類；代表點；密度均值

在日益信息化的社會中，聚類分析已經(jīng)成為一種被廣泛應用的數(shù)據(jù)處理算法.通過聚類分析，可以發(fā)現(xiàn)數(shù)據(jù)的統(tǒng)計規(guī)則，為統(tǒng)計決策做出參考.特別是隨著大數(shù)據(jù)時代的到來，更是需要通過高效聚類進行數(shù)據(jù)分析.聚類是將數(shù)據(jù)對象按其性質特征進行分組，使得組內數(shù)據(jù)的相似度相對較大，而組內各個元素之間的相似度較小[1].

最常用的算法是層次聚類算法[2-3]和劃分聚類算法[4-5].其中層次聚類就是通過對數(shù)據(jù)集按照某種方法進行層次分解，直到滿足某種條件為止，按照分類原理的不同，可以分為凝聚和分裂兩種算法，Guha等[6]在1998年提出了CURE算法，該算法不用單個中心或對象來代表一個聚類，而是選擇數(shù)據(jù)空間中固定數(shù)目的、具有代表性的一些點共同來代表相應的類.而常見的k-means[7]算法是一種典型的劃分聚類算法，是一種迭代的算法，采用距離作為相似性的評價指標，即認為兩個對象的距離越近，其相似度就越大.該算法認為簇是由距離靠近的對象組成的，因此把得到緊湊且獨立的簇作為最終目標，但是k-means算法僅適合于數(shù)值屬性數(shù)據(jù)的聚類，基于這些基礎算法的局限性，又提出了許多改進的聚類算法，例如Sun Y[8]提出了一種適合于分類屬性數(shù)據(jù)聚類的K-modes算法.吳天虹等[9]也在DBSCAN算法的基礎上，針對其聚類缺點提出了基于維度距離的混合屬性密度聚類算法.而動態(tài)聚類算法是在基本聚類算法基礎上發(fā)展起來的，文獻[10]提出的增量式DBSCAN算法就是在DBSCAN算法的基礎上提出的，針對數(shù)據(jù)倉庫環(huán)境中增量式數(shù)據(jù)加載要求，此算法是將數(shù)據(jù)進行逐一操作，沒有分析數(shù)據(jù)之間的關聯(lián).文獻[11]提出了基于網(wǎng)格的增量聚類，其算法類似于增量型的DBSCAN.黃永平和鄒力鹍[12]采用批量處理的基于密度的增量聚類來克服一個個處理數(shù)據(jù)的特點，但這種算法也由于計算量過大不太能用于大數(shù)據(jù)集的聚類.文獻[13]依據(jù)物理學中重力理論提出一種增量式的層次聚類，即GRIN算法，使用樹狀圖的算法優(yōu)化聚類效果.Charikar等[14]基于信息檢索的需求，提出基于層次凝聚的增量聚類算法，即當以增量數(shù)據(jù)提交給算法時，要么分配給已知簇，要么形成一新簇同時合并已知簇.張忠平等[15]在C均值聚類算法的基礎上引入簡單的干擾數(shù)據(jù)過濾，實現(xiàn)了對增量數(shù)據(jù)的處理.還有基于不確定性數(shù)據(jù)而提出的基于三角模糊函數(shù)的聚類算法[16]和基于數(shù)據(jù)場和單次劃分的聚類算法[17].這些基于基礎聚類算法的增量聚類算法都比較耗時且聚類效果也得不到保證，可擴展性差，沒有起到壓縮數(shù)據(jù)的作用.受於躍成等[18]基于高斯混合模型的增量式聚類算法的啟發(fā)，提出一種在基于密度峰的聚類算法的基礎上，對增量和失效的數(shù)據(jù)用代表點的算法進行處理，其核心在于用少量的數(shù)據(jù)來描述原有樣本的結構信息，在對增量后的樣本集進行再聚類時利用這些代表點信息結合新增數(shù)據(jù)點信息進行聚類，從而達到動態(tài)聚類的效果.

1 算法架構

對于大規(guī)模數(shù)據(jù)增量聚類，在數(shù)據(jù)集合發(fā)生變化時需要考慮快速完成聚類更新，在線聚類算法流程圖如圖1所示.算法首先采用已有數(shù)據(jù)集合進行初始化聚類.對于增量數(shù)據(jù)，為了保證更新后的數(shù)據(jù)聚類過程能夠快速收斂，在這里，根據(jù)已有聚類結果對已有數(shù)據(jù)進行代表點選擇，過濾掉干擾點和異常點，提高收斂速度.最后把增量數(shù)據(jù)和過濾后的數(shù)據(jù)進行合并，通過密度峰做聯(lián)合聚類，得到新的聚類結果.

圖1 算法的流程圖Fig.1 Flow chart of algorithm

為了描述方便，在這里給出聚類算法所需的各種定義：

1) 樣本集：待聚類的數(shù)據(jù)點集.

2) 截斷距離dc(Cutoff distance)：判斷一個數(shù)據(jù)點是否在另一個數(shù)據(jù)點周圍的參數(shù)，若兩個數(shù)據(jù)點的距離小于截斷距離，則這兩個數(shù)據(jù)點相距很近.

3) 截斷距離參數(shù)t：是確定截斷距離的參數(shù)，由用戶事先確定，將所有點與點之間的距離進行升序排序后取第t%的距離作為截斷距離且t∈(0,100)，經(jīng)實驗證明當t取1至3的區(qū)間內時聚類結果比較準確.

4) 聚類核心點：是在聚類后能被劃分到簇群的數(shù)據(jù)點(包括聚類中心點)，其特點是局部密度相對較大，而且與比它密度大且距離最近的點之間的距離相對較近.

5) 干擾點：在聚類完成后無法被劃分進簇群的點，其特點是局部密度小，而且與比它密度大且距離最近的點之間的距離相對較遠.在一次聚類后干擾點會被去除，不會帶入下次的聚類.

6) 失效點：指在一次聚類和下一次聚類的間歇期中由于時效過期“死亡”的數(shù)據(jù)點、出現(xiàn)異常的點和人為刪除的點.

7) 聚類簇群：是以聚類中心點為核心、分布相對集中的數(shù)據(jù)點集，并且有明確的邊界劃分.由聚類核心點組成，每個數(shù)據(jù)點能且僅能被劃分到一個簇群.

2 在線聚類算法細節(jié)

2.1 聚類初始化

有一個待聚類的樣本集：

(1)

對于P中任意的一個數(shù)據(jù)點xi，都有它的局部密度，即

(2)

式中：dc為截斷距離，很明顯與xi的距離小于dc的數(shù)據(jù)點越多，局部密度也就越大；dij為數(shù)據(jù)點xi與xj之間的距離.

ρq1≥ρq2≥…≥ρqN

(3)

可將這個數(shù)據(jù)點與比其密度大且距離最近的數(shù)據(jù)點的距離表示為

(4)

可知當xi具有最大的局部密度時，δi表示P中與xi距離最大的數(shù)據(jù)點與xi之間的距離；否則δi表示在所有的局部密度大于xi的數(shù)據(jù)點中，與xi距離最小的數(shù)據(jù)點與xi之間的距離.至此，對于每個P中的數(shù)據(jù)點都存在(δi，ρi)，可以從這兩個值來確定該點是否為聚類中心，但是往往實驗中更多會使用決策圖的算法手工劃分中心點，這種手工的方式不太適用于動態(tài)聚類的實際要求，所以使用γi作為劃分中心點的依據(jù)為

γi=δiρi,i∈IP

(5)

式中IP={1,2,3,…,N}為相應的指標集.將所有的γi從大到小降序，取前若干個數(shù)據(jù)點作為中心點，取的個數(shù)由實際數(shù)據(jù)決定.

(6)

2.2 代表點選擇

根據(jù)密度峰聚類算法的特性，使用代表點算法對來處理增量的數(shù)據(jù)，核心在于使用相對較少的數(shù)據(jù)點來描述原有數(shù)據(jù)點集的特點，希望利用這些代表聚類簇的代表點，并結合新增樣本進行再聚類.

(7)

式中：L為該CK簇的樣本總數(shù)；ρj為在這個簇群內每個數(shù)據(jù)點的局部密度.在一個簇群內有數(shù)據(jù)被刪除時，對它們所在簇群的密度均值進行調節(jié)：

(8)

這樣就能從簇群密度上體現(xiàn)這些數(shù)據(jù)點的流失，而這個密度均值會參加到后面的增量聚類中.例如，原本一個簇群在進行增量聚類時用若干個代表點來代表，而當該簇群中有失效的數(shù)據(jù)時，在下一次聚類的工作中，由于該簇群的密度均值變小，所以取到代表點的個數(shù)也相應減少.

接下來需要選取簇群的代表點，首先先確定每個簇群代表點的個數(shù)，設存在閾值nc(用戶指定)，若一個簇群的核心數(shù)據(jù)點個數(shù)不超過nc，將取該簇群中所有的點作為代表點，因為這個簇群內的數(shù)據(jù)點數(shù)量原本就很小，若再選取較少的數(shù)據(jù)點來代表該簇群，就很有可能失去這個簇群的密度屬性.而當簇群內數(shù)據(jù)點的個數(shù)大于nc時，簇群代表點的個數(shù)是根據(jù)簇群核心區(qū)域的面積M和簇群的密度均值m確定的，密度大且面積小的可以取相對較少的代表點，而密度小但面積大的則可以適當多取代表點，最終確定的個數(shù)在該簇群內數(shù)據(jù)點總數(shù)的40%～60%比較合適.

確定每個簇群代表點的個數(shù)后，在簇群區(qū)域內隨機取點，使得取到的代表點能基本體現(xiàn)這個簇群的密度分布和基本形狀.

2.3 密度峰聚類

采用密度峰算法[19]進行聚類核心點的更新，這種聚類算法的優(yōu)勢在于在已知所有數(shù)據(jù)點之間相互“距離”的情況下可以快速地查找出聚類中心點，由于其中的“距離”是歐式距離，適用的情況也比較多.在得到代表點以后，對于新增數(shù)據(jù)點，算法將原有簇群代表點結合增量數(shù)據(jù)，形成新的樣本集，即

P=P代表點+P新增-P失效

(9)

(10)

式中L′為簇群加入新增數(shù)據(jù)后數(shù)據(jù)點的個數(shù).這樣無論要處理新增數(shù)據(jù)還是失效數(shù)據(jù)都可以動態(tài)調節(jié)每個簇群的密度均值，動態(tài)取到代表點加入到以后的重復聚類.然后完成密度峰聚類如下：

1) 給定用于確定新截斷距離dc的參數(shù)t∈(0,100).

2) 計算新數(shù)據(jù)集所有的距離dij，并令dji=dij，i

(11)

7) 然后將每一個生成的簇群中的數(shù)據(jù)進一步的劃分，劃分為核心點和干擾點.

9) 最后在各個簇群的核心數(shù)據(jù)點中繼續(xù)獲取代表點，等待下一次新增數(shù)據(jù)的到來.

3 實驗結果與分析

為了能夠驗證算法的有效性，此章節(jié)對算法和已有典型聚類算法進行實驗比較分析.首先對算法的聚類效果進行可視化分析，驗證代表點算法在提高算法效率的同時，能夠保證聚類效果.然后對算法效率進行分析，驗證在數(shù)據(jù)集增加的前提下，算法效率要明顯優(yōu)于已有聚類算法.最后，討論了算法在人臉大數(shù)據(jù)中的應用.

3.1 算法聚類效果分析

首先使用以往比較常用的聚類數(shù)據(jù)集進行密度峰的聚類結果分析，例如圖2(a)的分布情況，可以看到：圖2(a)中中間部分的數(shù)據(jù)點相距比較緊密，其中有15個簇群，比較難劃分,若使用k-means算法對該數(shù)據(jù)點集進行聚類，k的參數(shù)取到7以上時，其算法已經(jīng)難以收斂，聚類效果也很差，無法將該數(shù)據(jù)點集進行良好的劃分.而使用密度峰聚類算法，計算數(shù)據(jù)點集中所有點的ρ和δ值，將這些值投影到一個坐標軸上，可以看到：圖2(b)中還是明顯分離出了這幾個γ值較大的點，選取這幾個點為聚類中心點，之后將其他的數(shù)據(jù)點按局部密度大小依次劃分到密度比它們大且離它們最近的點.從圖2(c)中的結果可以看到：不管是外圍的數(shù)據(jù)點還是中間比較密集的數(shù)據(jù)點都可以得到很好的劃分.圖2(d)為其他數(shù)據(jù)點集的聚類效果圖.

圖2 實驗數(shù)據(jù)點集的聚類效果及每個點ρ值與δ值的分布Fig.2 Clustering effect of experimental data set, the ρ and δ of each point

然后使用高斯分布的數(shù)據(jù)點對dc的參數(shù)進行實驗，圖3(a)中使用的是t取1的參數(shù)，黑色的小點為離群點，“×”的簇群范圍過大，簇群的邊界不明顯.圖3(c)是將參數(shù)t取2，聚類的結果可以通過圖3(b,d)看出：當dc距離變大，點的局部密度也增大了，而聚類核心的區(qū)域變小了，凸顯出了這個簇群，效果會更好.

圖3 不同dc的聚類效果圖和分布圖Fig.3 Clustering effect diagrams and distribution graphs for different dc

3.2 增量大數(shù)據(jù)的聚類效果分析

傳統(tǒng)的聚類算法由于沒有針對變動的數(shù)據(jù)集采取優(yōu)化處理，往往導致聚類速度緩慢，特別是當有新增數(shù)據(jù)加入數(shù)據(jù)集時，之前已聚類的數(shù)據(jù)還會參加到下一次的聚類中，這嚴重影響了聚類效率.基本的密度峰聚類算法時間復雜度為O(n2)，是計算所有點兩兩之間的距離，同時計算所有點的局部密度，也需要遍歷到所有點，所以當一次聚類的數(shù)據(jù)點個數(shù)不斷增多時，如圖4(a)中圓型的線段，所耗的時間會呈現(xiàn)一個指數(shù)的上漲，而三角形的線段是使用代表點的增量聚類算法，算法的速度很大程度取決于每次增加的數(shù)據(jù)點數(shù)量和每次聚類后干擾點的數(shù)量，可以看到運行的時間得到比較好的優(yōu)化.圖4(c)是由圖4(b)使用代表點算法后的數(shù)據(jù)點分布，可以看到圖4(c)中基本表達了圖4(b)中簇群的形狀特征和密度分布.因為密度峰的聚類算法的本質是根據(jù)各個數(shù)據(jù)點的距離關系進行聚類的，所以我們可以使用盡量少但能凸顯集群中距離關系的代表點對數(shù)據(jù)集進行再聚類，從而在保證聚類效果的基礎上達到時間上的優(yōu)化.

之后在圖3(c)的基礎上選擇代表點后進行再聚類，而圖4(d)再聚類后的效果圖，可以看到已經(jīng)聚類過的簇群可以良好地進行增量再聚類，而圖4中中心區(qū)域是新聚類的簇群，得到了較好的聚類效果，達到了預計的增量聚類效果.

(a) 基礎密度峰聚類和代表點增量聚類時間的比較

(b) 已聚類完成的數(shù)據(jù)點集

(c) 由圖4(b)得到的代表點數(shù)據(jù)點

(d) 圖3(c)數(shù)據(jù)集動態(tài)改變后的聚類效果圖

在實驗圖3(c)的基礎上增加隨機的數(shù)據(jù)點、減少原有的實驗數(shù)據(jù)點來模擬動態(tài)聚類的情況，如圖5(a)所示，隨機增加了整體數(shù)據(jù)點的數(shù)量，大量減少了原來右下角“+”簇群的個數(shù)，得到ρ和δ值的分布圖，如圖5(b)所示.

(a) 圖3(c)改變后的數(shù)據(jù)點集

(b) 對應圖5(a)的ρ值與δ值的分布

可以看出在圖5(a)中左側“×”簇群和圓點簇群基本不變，只是少量增加了隨機添加的數(shù)據(jù)點，而右下角“+”簇群顯然減少了許多的數(shù)據(jù)點，其中心點的密度大幅減小，簇群的邊界的范圍也被壓縮地很小，若每次聚類后其中心點的局部密度過低，則不會再將其聚類成一個簇群.動態(tài)的聚類在有數(shù)據(jù)失效后，簇群將失效的數(shù)據(jù)排除，并調整其整體密度均值，之后重復聚類時取得代表點個數(shù)也會相應減少.

3.3 在人臉聚類分析中的應用

現(xiàn)如今越來越多的聚類分析已經(jīng)能廣泛地應用在人們的生活中，根據(jù)增量聚類算法的特性，可以應用到許多生活中的數(shù)據(jù)處理.例如，現(xiàn)在幾乎所有人通過很多的電子設備進行照相留念，久而久之會有越來越多的照片存放在手機或者是電腦上，如何對這些照片進行清理，將有人臉的照片進行分類是具有實際價值的.

實驗希望通過在線的聚類算法來對人臉照片進行清洗，但在做照片聚類之前需要先對照片進行預處理；實驗使用卷積神經(jīng)網(wǎng)絡的算法提取人臉特征值，卷積神經(jīng)網(wǎng)絡是近年發(fā)展起來，并引起廣泛重視的一種高效識別算法.20世紀60年代，在研究貓腦皮層中用于局部敏感和方向選擇的神經(jīng)元時發(fā)現(xiàn)其獨特的網(wǎng)絡結構可以有效地降低反饋神經(jīng)網(wǎng)絡的復雜性，繼而提出了卷積神經(jīng)網(wǎng)絡(Convolutional neural networks，簡稱CNN)，借鑒了這種算法，其優(yōu)點是輸入的值是圖片，可以比較快速地提取特征值.從人臉照片中提取出相應的特征值后，需要計算不同特征值之間的差異程度，實驗使用的是聯(lián)合貝葉斯算法Joint Bayesian，至此，對照片的初始化完成.

實驗使用了1 340張各類的初始人臉圖片進行在線聚類，也在其中添加了一些干擾圖片，包括一些不含人臉的照片.從實驗結果來看：能較好較快地實現(xiàn)人臉聚類，將不同人的照片區(qū)分開來，而隨著時間的累積，會有新的照片集進入也會有一些人工刪除的照片來模擬用戶日常的操作，實驗結果也達到我們預期的目標.圖6是取聚類后的部分實驗結果.可以看出，同一個人的照片能夠很好地聚類在一起，并且不受樣本數(shù)目的影響.

圖6 人臉聚類效果Fig.6 Face clustering effect diagram

4 結 論

提出了一種基于密度峰的動態(tài)聚類算法對大數(shù)據(jù)集進行聚類.該算法使用代表點算法和簇群的密度均值來實現(xiàn)對動態(tài)大數(shù)據(jù)集聚類的優(yōu)化，在保證聚類準確率的同時大大提高了收斂速度，可適用增量大數(shù)據(jù)量的聚類分析.但是該算法研究只是考慮對大數(shù)據(jù)的增量聚類，并沒有考慮流式數(shù)據(jù)的聚類分析.在后續(xù)工作中可以進一步提高該算法的實時性，對流數(shù)據(jù)進行實時增量聚類，提取出流數(shù)據(jù)的內在規(guī)則.另外一方面，可在聚類算法應用上做進一步研究，特別是和深度學習的特征提取相結合，可進行大數(shù)據(jù)的特征分析.

[1] JING L, NING M K, HUANG J Z. An entropy weightingk-means algorithm for subspace clustering of high-dimensional sparse data[J]. IEEE transactions on knowledge and data engineering,2007,19(8):1026-1041.

[2] WILLIAMS C. A mcmc approach to hierarchical mixture modeling[J]. Advances in neural information processing systems,2000，45(15):680-686.

[3] FRALEY C. Algorithms for model-based Gaussian hierarchical clustering[J]. Siam journal on scientific computing,1998,20(1):270-281.

[4] DING C, HE X. K-nearest-neighbor consistency in data clustering: incorporating local information into global optimization[C]//ACM Symposium on Applied Computing. New York, USA: DBLP,2004:584-589.

[5] 李潔，高新波，焦李成.一種新的特征加權模糊聚類算法[J].電子學報,2006,34(1):412-420.

[6] GUHA S, RASTOGI R, SHIM K, et al. CURE: an efficient clustering algorithm for large databases[J]. Information systems,1998,26(1):35-58.

[7] RIGELSFORD J. Pattern recognition: concepts, methods and applications[J]. Assembly automation,2002,22(4):318.

[8] SUN Y, ZHU Q M, CHEN Z X. An iterative initial-points refinement algorithm for categorical data clustering[J]. Pattern recognition letters,2002,23(7):875-884.

[9] 吳天虹，黃德才，翁挺，等.基于維度距離的混合屬性密度聚類算法研究[J].浙江工業(yè)大學學報,2009,37(4):445-448.

[10] ESTER M, KRIEGEL H P, SANDER J, et al. Incremental clustering for mining in a data warehousing environment[C]//International Conference on Very Large Data Bases. San Francisco, USA: Morgan Kaufmann Publishers Inc,1998:323-333.

[11] 陳寧，陳安.基于密度的增量式網(wǎng)格聚類算法[J].軟件學報,2002,13(1):1-7.

[12] 黃永平,鄒力鹍.數(shù)據(jù)倉庫中基于密度的批量增量聚類算法[J].計算機工程與應用,2004,29:206-208.

[13] CHEN C Y, HWANG S C, OYANG Y J. An incremental hierarchical data clustering algorithm based on gravity theory[C]//Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining. Taiwan: Springer-Verlag,2002:237-250.

[14] CHARIKAR M, CHEKURI C, FEDER T, et al. Incremental clustering and dynamic information retrieval[C]//ACM Symposium on the Theory of Computing. New York，USA: ACM,1997:626-635.

[15] 張忠平，陳麗萍.基于自適應模糊C-均值的增量式聚類算法[J].計算機工程，2009，35(6):60-65.

[16] 陸億紅，翁純佳.基于三角模糊數(shù)的不確定性數(shù)據(jù)聚類算法[J].浙江工業(yè)大學學報，2016,44(4):405-409.

[17] 張霓，陳天天，何熊熊.基于數(shù)據(jù)場和單次劃分的聚類算法[J].浙江工業(yè)大學學報，2016,44(1):52-57.

[18] 於躍成,生佳根.基于高斯混合模型的增量式聚類[J].江蘇科技大學學報,2011,25(6):591-601.

[19] RODRIGUEZ A, LAIO L. Clustering by fast search and find of density peaks[J]. Science,2014,27(344):1492-1496.

(責任編輯：陳石平)

An incremental dynamic clustering method based on the representative points and the density peaks

ZHENG Herong, CHEN Ken, PAN Xiang

(College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China)

In order to solve the speed slow problem of clustering the incremental large data, this paper proposes a fast clustering method based on the representative points and the density peaks. Firstly, this algorithm uses the method of representative points to achieve clustering the incremental large data. According to deleting the invalid cluster data, the average density of cluster is adjusted. Then the algorithm of representative points is used to update the samples. Finally, the algorithm of density peaks is used to repeat clustering in order to update the core point. The experimental results show that the algorithm can effectively improve the convergence speed of the algorithm. In the application aspect, this clustering algorithm can be used in face clustering work with the large amount of data and optimize the effect of face clustering.

timeliness; online clustering; representative points; density mean value

2016-12-12

浙江省科技廳項目(2016C31G2020061)；浙江省自然科學基金資助項目(LY15F020024)

鄭河榮(1971—)，男，浙江溫嶺人，教授，碩士生導師，主要從事計算機圖形學與圖像處理技術研究，E-mail：hailiang@zjut.edu.cn.

TP3

A

1006-4303(2017)04-0427-07