結(jié)合代表點(diǎn)和密度峰的增量動(dòng)態(tài)聚類算法

鄭河榮，陳 懇，潘 翔

(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023)

結(jié)合代表點(diǎn)和密度峰的增量動(dòng)態(tài)聚類算法

鄭河榮，陳 懇，潘 翔

(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023)

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

時(shí)效性；在線聚類；代表點(diǎn)；密度均值

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

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

1 算法架構(gòu)

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

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

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

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

2) 截?cái)嗑嚯xdc(Cutoff distance)：判斷一個(gè)數(shù)據(jù)點(diǎn)是否在另一個(gè)數(shù)據(jù)點(diǎn)周?chē)膮?shù)，若兩個(gè)數(shù)據(jù)點(diǎn)的距離小于截?cái)嗑嚯x，則這兩個(gè)數(shù)據(jù)點(diǎn)相距很近.

3) 截?cái)嗑嚯x參數(shù)t：是確定截?cái)嗑嚯x的參數(shù)，由用戶事先確定，將所有點(diǎn)與點(diǎn)之間的距離進(jìn)行升序排序后取第t%的距離作為截?cái)嗑嚯x且t∈(0,100)，經(jīng)實(shí)驗(yàn)證明當(dāng)t取1至3的區(qū)間內(nèi)時(shí)聚類結(jié)果比較準(zhǔn)確.

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

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

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

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

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

2.1 聚類初始化

有一個(gè)待聚類的樣本集：

(1)

對(duì)于P中任意的一個(gè)數(shù)據(jù)點(diǎn)xi，都有它的局部密度，即

(2)

式中：dc為截?cái)嗑嚯x，很明顯與xi的距離小于dc的數(shù)據(jù)點(diǎn)越多，局部密度也就越大；dij為數(shù)據(jù)點(diǎn)xi與xj之間的距離.

ρq1≥ρq2≥…≥ρqN

(3)

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

(4)

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

γi=δiρi,i∈IP

(5)

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

(6)

2.2 代表點(diǎn)選擇

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

(7)

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

(8)

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

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

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

2.3 密度峰聚類

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

P=P代表點(diǎn)+P新增-P失效

(9)

(10)

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

1) 給定用于確定新截?cái)嗑嚯xdc的參數(shù)t∈(0,100).

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

(11)

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

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

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

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

3.1 算法聚類效果分析

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

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

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

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

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

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

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

(a) 基礎(chǔ)密度峰聚類和代表點(diǎn)增量聚類時(shí)間的比較

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

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

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

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

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

(b) 對(duì)應(yīng)圖5(a)的ρ值與δ值的分布

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

3.3 在人臉聚類分析中的應(yīng)用

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

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

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

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

4 結(jié) 論

提出了一種基于密度峰的動(dòng)態(tài)聚類算法對(duì)大數(shù)據(jù)集進(jìn)行聚類.該算法使用代表點(diǎn)算法和簇群的密度均值來(lái)實(shí)現(xiàn)對(duì)動(dòng)態(tài)大數(shù)據(jù)集聚類的優(yōu)化，在保證聚類準(zhǔn)確率的同時(shí)大大提高了收斂速度，可適用增量大數(shù)據(jù)量的聚類分析.但是該算法研究只是考慮對(duì)大數(shù)據(jù)的增量聚類，并沒(méi)有考慮流式數(shù)據(jù)的聚類分析.在后續(xù)工作中可以進(jìn)一步提高該算法的實(shí)時(shí)性，對(duì)流數(shù)據(jù)進(jìn)行實(shí)時(shí)增量聚類，提取出流數(shù)據(jù)的內(nèi)在規(guī)則.另外一方面，可在聚類算法應(yīng)用上做進(jìn)一步研究，特別是和深度學(xué)習(xí)的特征提取相結(jié)合，可進(jìn)行大數(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] 李潔，高新波，焦李成.一種新的特征加權(quán)模糊聚類算法[J].電子學(xué)報(bào),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è)大學(xué)學(xué)報(bào),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].軟件學(xué)報(bào),2002,13(1):1-7.

[12] 黃永平,鄒力鹍.數(shù)據(jù)倉(cāng)庫(kù)中基于密度的批量增量聚類算法[J].計(jì)算機(jī)工程與應(yīng)用,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] 張忠平，陳麗萍.基于自適應(yīng)模糊C-均值的增量式聚類算法[J].計(jì)算機(jī)工程，2009，35(6):60-65.

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

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

[18] 於躍成,生佳根.基于高斯混合模型的增量式聚類[J].江蘇科技大學(xué)學(xué)報(bào),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.

(責(zé)任編輯：陳石平)

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

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

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

TP3

A

1006-4303(2017)04-0427-07