融入密度和距離的K-means初始簇中心優(yōu)選方法研究

馮 勇，張學(xué)理，王嶸冰，徐紅艷

(遼寧大學(xué) 信息學(xué)院，沈陽(yáng) 110036) E-mail ：xuhongyan@lnu.edu.cn

1 引 言

大數(shù)據(jù)時(shí)代產(chǎn)生了海量數(shù)據(jù)，對(duì)這些數(shù)據(jù)進(jìn)行聚類分析是一個(gè)比較重要的研究方向[1].聚類就是將目標(biāo)對(duì)象分成為簇，簇內(nèi)對(duì)象相似度盡可能大，而簇間對(duì)象相似度盡可能小[2].其被廣泛應(yīng)用于醫(yī)藥、交通、銀行等諸多領(lǐng)域[3-5].在眾多聚類算法中，K-means算法作為基于劃分的聚類算法，具有效率高、原理簡(jiǎn)單、收斂速度快等優(yōu)點(diǎn).但由于K-means算法初始簇中心是隨機(jī)選取的，易出現(xiàn)局部最優(yōu)、聚類結(jié)果不穩(wěn)定、影響收斂速度等問(wèn)題[6].

近年來(lái)，針對(duì)K-means算法的優(yōu)化研究引起學(xué)術(shù)界的廣泛關(guān)注.文獻(xiàn)[7]構(gòu)造最小生成樹并利用樹的剪枝技術(shù)基于數(shù)據(jù)樣本分布情況動(dòng)態(tài)的選取初始簇類中心，考慮了數(shù)據(jù)樣本密度分布對(duì)聚類的影響，改善了聚類性能，但是構(gòu)造最小生成樹較大程度上增加了算法的開銷.文獻(xiàn)[8]選取簇內(nèi)高密度分布的點(diǎn)作為初始簇中心，進(jìn)一步提高了聚類效率.但是搜索高密度點(diǎn)的范圍比較大，增加了算法的復(fù)雜度.文獻(xiàn)[9]基于平均密度選取初始簇中心，減少聚類次數(shù)的同時(shí)一定程度上避免了選取點(diǎn)為噪聲點(diǎn)，增強(qiáng)了算法的穩(wěn)定性.以上各文獻(xiàn)都沒(méi)有考慮到真實(shí)聚類中心周圍密度都比較大的問(wèn)題，選取點(diǎn)可能會(huì)集中在這個(gè)點(diǎn)的周圍，易陷入局部最優(yōu)[10].文獻(xiàn)[11]和文獻(xiàn)[12]基于距離最遠(yuǎn)的點(diǎn)最不可能分到同一個(gè)簇中這一事實(shí)，不斷選取距離最遠(yuǎn)的點(diǎn)作為初始簇中心，避免了陷入局部最優(yōu)解的問(wèn)題，得到了穩(wěn)定的聚類結(jié)果，但是沒(méi)有考慮樣本點(diǎn)的密度分布，選取的點(diǎn)很有可能是孤立的噪聲點(diǎn)，影響最終聚類結(jié)果.

針對(duì)上述文獻(xiàn)中僅考慮樣本對(duì)象密度分布，選取高密度點(diǎn)容易陷入局部最優(yōu)，以及僅從最大距離選取最遠(yuǎn)點(diǎn)容易選取噪聲點(diǎn)的問(wèn)題.本文從樣本密度分布和距離兩個(gè)方面進(jìn)行考慮，提出了一種基于密度和距離的K-means初始簇中心優(yōu)選方法.本文所提方法不斷選取距離最遠(yuǎn)的樣本對(duì)象，并且基于最遠(yuǎn)樣本對(duì)象進(jìn)行限定規(guī)模的貪心策略密度聚類形成初始簇，在初始簇中選取支持度最大的核心點(diǎn)對(duì)象，作為初始簇中心對(duì)象.所提方法限定了密度聚類的最大簇內(nèi)個(gè)數(shù)，避免了時(shí)間復(fù)雜度過(guò)高，密度聚類中的支持度對(duì)樣本對(duì)象噪聲進(jìn)行了過(guò)濾，同時(shí)最遠(yuǎn)距離選取樣本對(duì)象，也一定程度上避免了陷入局部最優(yōu)的可能.實(shí)驗(yàn)結(jié)果表明所提方法具有更好的穩(wěn)定性、更高的準(zhǔn)確率，同時(shí)聚類收斂速度更快.

2 K-means聚類算法

K-means聚類算法是一種基于劃分的聚類算法，一般采用歐式距離作為聚類對(duì)象的距離，算法實(shí)現(xiàn)較為簡(jiǎn)單，被廣泛的應(yīng)用在各行各業(yè).該算法的主要流程：

1)從聚類對(duì)象中隨機(jī)選取K個(gè)對(duì)象作為初始簇中心.

2)分別計(jì)算剩余各對(duì)象到這K個(gè)初始對(duì)象的歐式距離，把各對(duì)象劃分到距離初始簇中心最近的類中去.

3)重新計(jì)算各類中簇中心，把質(zhì)心作為簇中心.

4)迭代步驟2、步驟3直到簇中心不再發(fā)生變化或者小于指定閾值，算法結(jié)束.

K-means是一種易于實(shí)現(xiàn)同時(shí)處理效率較高的聚類算法，比較廣泛的應(yīng)用在需要指定聚類個(gè)數(shù)K的情景中.但是初始簇中心的隨機(jī)選取易導(dǎo)致聚類不穩(wěn)定、準(zhǔn)確率低等問(wèn)題，為了解決這個(gè)問(wèn)題，大部分改進(jìn)方法都是從單一維度對(duì)其進(jìn)行改進(jìn)，例如最大距離選取初始簇中心或者選取高密度區(qū)域的數(shù)據(jù)對(duì)象作為初始簇中心，取得了一些較好的效果，但僅僅從單一維度確定初始簇不能有效的的解決上述問(wèn)題.

3 相關(guān)工作

3.1 DBSCAN算法

DBSCAN算法可以自動(dòng)確定簇的數(shù)量，能夠發(fā)現(xiàn)任意形狀的簇，是一種基于密度的聚類算法[13].以下是對(duì)DBSCAN相關(guān)定義的表述：

定義1.(鄰域)樣本集合D中的一點(diǎn)p，p的鄰域表示為NEps(p)，其表示的含義是以p為核心，以Eps為半徑的d維超球體區(qū)域.

定義2.(核心點(diǎn))對(duì)于樣本點(diǎn)p∈D，如果p鄰域范圍內(nèi)樣本點(diǎn)的個(gè)數(shù)大于等于最小支持度minPts，則p為核心點(diǎn)，否則p不為核心點(diǎn).

定義3.(直接密度可達(dá)) 給定數(shù)據(jù)集D，其中p，q∈D，如果p在q的鄰域并且q為核心點(diǎn)，則稱對(duì)象p是從q出發(fā)直接密度可達(dá).

定義4.(密度可達(dá))假設(shè)對(duì)象集D中存在一個(gè)鏈p1，p2…,pm，如果pj+1到pj直接密度可達(dá)，則稱對(duì)象pm從p1接密度可達(dá).

DBSCAN聚類過(guò)程是首先需要掃描數(shù)據(jù)集，找到未處理的對(duì)象，如果該對(duì)象是核心點(diǎn)那么找出該對(duì)象的密度可達(dá)對(duì)象，如果是非核心點(diǎn)那么繼續(xù)掃描，直到所有點(diǎn)被處理.DBSCAN算法優(yōu)點(diǎn)是能夠基于密度分布發(fā)現(xiàn)任意形狀的類，這些類內(nèi)對(duì)象分布在一定程度上反應(yīng)聚類對(duì)象的密度分布情況.缺點(diǎn)也很明顯，DBSCAN密度聚類對(duì)掃描半徑Eps和最小支持度minPts的設(shè)定比較敏感.

3.2 基于最遠(yuǎn)距離的K-means聚類

基于最遠(yuǎn)距離選取初始簇中心，首先需要計(jì)算樣本集的N個(gè)樣本點(diǎn)兩兩之間的距離，選取距離最遠(yuǎn)的兩個(gè)樣本點(diǎn)作為初始簇中心；接著在其余樣本點(diǎn)中，尋找距離已選初始簇中心最遠(yuǎn)的第三個(gè)樣本點(diǎn)作為新的初始簇中心；不斷迭代直到找到K個(gè)初始簇中心.

基于最遠(yuǎn)距離尋找初始簇中心，雖然依據(jù)最遠(yuǎn)的點(diǎn)最不可能分到同一個(gè)簇中這一情況，但是忽略了實(shí)際聚類中心點(diǎn)周圍的密度往往要比類中其他點(diǎn)的周圍密度大這一事實(shí)，僅僅從距離考慮會(huì)對(duì)后續(xù)聚類效果產(chǎn)生較大影響.

4 融入密度和距離的K-means初始簇中心的優(yōu)化選取方法

4.1 基本思想

本文參照文獻(xiàn)[14]采用貪心策略不斷的自適應(yīng)尋找樣本對(duì)象的Eps半徑，對(duì)樣本對(duì)象進(jìn)行密度聚類，該方法的好處是能夠有效識(shí)別多密度的簇，更好的了解樣本對(duì)象的密度分布；文獻(xiàn)[12]不斷選取距離最大的樣本對(duì)象進(jìn)行聚類，該方法能夠有效的避免局部最優(yōu)；本文綜合以上兩種方法的優(yōu)點(diǎn)通過(guò)不斷迭代選取最遠(yuǎn)點(diǎn)進(jìn)行貪心策略的密度聚類，直到形成K個(gè)臨時(shí)初始簇，最后在每個(gè)臨時(shí)初始簇中選取支持度最高的核心點(diǎn)為初始簇中心.具體步驟如下：

1)首先在樣本集的N個(gè)樣本點(diǎn)中選取距離最遠(yuǎn)的兩個(gè)樣本點(diǎn)p、q，再分別選取樣本點(diǎn)p、q距離自身最近的K個(gè)點(diǎn)，使得點(diǎn)p、q成為核心點(diǎn).接下來(lái)分別計(jì)算與p、q臨近的K個(gè)點(diǎn)兩兩間的距離，選取至兩核心點(diǎn)第K長(zhǎng)的距離rp、rq，確定p、q分別以rp、rq為半徑的鄰域NEps(p)、NEps(q).

2)點(diǎn)p、q鄰域內(nèi)其它點(diǎn)分別以距離自身第K長(zhǎng)的距離為半徑，不斷迭代動(dòng)態(tài)向外擴(kuò)散.如果鄰域內(nèi)的點(diǎn)也為核心對(duì)象，即為p、q的直接密度可達(dá)點(diǎn)，那么合并這兩個(gè)核心點(diǎn)所在的鄰域內(nèi)的所有點(diǎn)，以此類推，當(dāng)達(dá)到設(shè)定最大簇內(nèi)個(gè)數(shù)或者初始點(diǎn)周圍對(duì)象過(guò)于稀疏，掃描半徑范圍內(nèi)點(diǎn)個(gè)數(shù)小于支持度minPts時(shí)，聚類結(jié)束，形成臨時(shí)初始簇c1、c2.

3)把簇c1、c2各自的質(zhì)心作為起始點(diǎn)，接著在其余樣本點(diǎn)中不斷迭代尋找到起始點(diǎn)距離乘積值最大的點(diǎn)，進(jìn)行基于貪心策略方法的密度聚類，形成新的臨時(shí)初始簇；依次類推，直到形成K個(gè)臨時(shí)初始簇，最后在每個(gè)臨時(shí)初始簇中選取支持度最大的點(diǎn)作為初始簇中心，優(yōu)選結(jié)束.

這里需要說(shuō)明一點(diǎn)，如果最初選取的距離最遠(yuǎn)的點(diǎn)是一個(gè)離群的噪聲點(diǎn)，那么它同樣能夠找到距離其最近的 K個(gè)點(diǎn)，并不斷合并其鄰域范圍內(nèi)直接密度可達(dá)點(diǎn)鄰域內(nèi)的樣本點(diǎn)形成臨時(shí)初始簇，最終選取初始簇中心.但這個(gè)噪聲點(diǎn)作為初始簇中心點(diǎn)在邏輯上是錯(cuò)誤的，會(huì)對(duì)最終的聚類結(jié)果造成較大影響.為了解決此問(wèn)題，本文對(duì)噪聲點(diǎn)進(jìn)行檢測(cè)和標(biāo)記.在選取最遠(yuǎn)距離初始點(diǎn)時(shí)，首先要計(jì)算該點(diǎn)t臨近的K個(gè)點(diǎn)的平均密度，如公式(1)、公式(2)所示：

(1)

(2)

其中公式(1)是歐式距離計(jì)算的公式，Dis(t)表示核心點(diǎn)所在初始簇的平均歐式距離.dis(t，qi)為樣本點(diǎn)t和qi之間的歐式距離.

如果核心點(diǎn)t的第K長(zhǎng)距離rK遠(yuǎn)大于平均距離，那么標(biāo)記點(diǎn)t為噪聲點(diǎn).重新選取次遠(yuǎn)距離的點(diǎn)做噪聲點(diǎn)判別，如果為非噪聲點(diǎn)則開始聚類形成臨時(shí)初始簇，否則繼續(xù)選取次遠(yuǎn)的點(diǎn)直到找到非噪聲點(diǎn)，開始聚類形成臨時(shí)初始簇.這樣避免了選取最遠(yuǎn)距離的初始點(diǎn)為噪聲點(diǎn)的問(wèn)題.

4.2 算法描述

現(xiàn)將上述基于密度和距離的K-means初始簇中心優(yōu)選方法過(guò)程用算法的形式描述如下：

輸入：數(shù)據(jù)集DB的n個(gè)樣本點(diǎn)，要聚類的個(gè)數(shù)K，形成初始簇的最大簇內(nèi)個(gè)數(shù)cmax，最小支持度minPts.

輸出：K個(gè)初始簇中心點(diǎn)

1. for i=1 tonfromDBdo //n為數(shù)據(jù)庫(kù)DB樣本內(nèi)最大的樣本個(gè)數(shù)

2.Dis←caculate_p_distance(DB)//計(jì)算數(shù)據(jù)庫(kù)中每個(gè)兩個(gè)樣本點(diǎn)的歐式距離Dis

3.OrderDis←order(Dis)//對(duì)歐式距離按照升序排序得到升序序列OrderDis

4. end for

5. for j=1 tonformDBdo

6. if k<=K//其中k為初始簇的個(gè)數(shù)

7.Maxdisp←select_maxOrderDis(OrderDis)

//選取相距最遠(yuǎn)的點(diǎn)Maxdisp

8. 根據(jù)公式(2)判斷改點(diǎn)Maxdisp是不是噪聲點(diǎn)

如果是噪聲點(diǎn)刪除該噪聲點(diǎn)回到步驟8如果不是執(zhí)行步驟10

9. if c<=cmax//c為簇內(nèi)個(gè)數(shù)

10.Dbscan_clusters←greedy_Dbscan(Maxdisp，minPts)

//根據(jù)Dbscan貪心密度聚類形成臨時(shí)初始簇Dbscan_clusters

11. end if

12. end if

13. end for

14.init_clusterceter←initcenter(Dbscan_clusters，K)

//在每個(gè)初始簇中選取支持度最大的核心點(diǎn)作為初始簇中心init_clusterceter

15. end

5 實(shí)驗(yàn)與分析

本文實(shí)驗(yàn)環(huán)境包括CPU為Intel Pentium G645，內(nèi)存為8G，硬盤為500G，Windows7操作系統(tǒng).首先驗(yàn)證所提方法的有效性，本文選取UCI數(shù)據(jù)庫(kù)中的數(shù)據(jù)量較大的Letter數(shù)據(jù)集為實(shí)驗(yàn)數(shù)據(jù)，Letter數(shù)據(jù)集上含有20000條數(shù)據(jù)，每條數(shù)據(jù)包含17個(gè)屬性，分為26類.在Letter 數(shù)據(jù)集上隨機(jī)選擇條數(shù)為500，1000，2000，5000，10000，20000的6組數(shù)據(jù)進(jìn)行算法有效性驗(yàn)證實(shí)驗(yàn).

5.1 實(shí)驗(yàn)描述

根據(jù)實(shí)驗(yàn)需求，本文在Letter 數(shù)據(jù)集上進(jìn)行50次聚類實(shí)驗(yàn)，從運(yùn)行時(shí)長(zhǎng)、準(zhǔn)確率、以及召回率三個(gè)方面分別將所提方法優(yōu)選的初始簇中心與文獻(xiàn)[9]基于密度優(yōu)選和文獻(xiàn)[12]基于最大距離優(yōu)選以及文獻(xiàn)[15]基于KD樹優(yōu)選的初始簇中心進(jìn)行K-means聚類對(duì)比實(shí)驗(yàn).

圖1 K-means聚類運(yùn)行時(shí)長(zhǎng)對(duì)比Fig.1 Contrast of running time in K-means cluster

考慮優(yōu)選初始簇中心本身也耗費(fèi)時(shí)間，圖2是加入優(yōu)選過(guò)程的四種算法時(shí)間對(duì)比圖.首先比較運(yùn)行時(shí)長(zhǎng).圖1是選取K=26在不同數(shù)據(jù)量下四種方法進(jìn)行K-means聚類運(yùn)行時(shí)長(zhǎng)的對(duì)比圖.

圖2 加入優(yōu)選過(guò)程的算法時(shí)間對(duì)比Fig.2 Contrast of running time with optimization process

其次是比較準(zhǔn)確率.圖3是選取K=26在不同數(shù)據(jù)量下四種方法優(yōu)選初始簇中心K-means聚類準(zhǔn)確率對(duì)比圖.

圖3 聚類準(zhǔn)確率對(duì)比Fig.3 Contrast of clustering accuracy

最后是比較召回率.圖4是選取K=26在不同數(shù)據(jù)量下三種方法優(yōu)選初始簇中心K-means聚類召回率的對(duì)比圖.

圖4 聚類召回率對(duì)比Fig.4 Contrast of clustering recall rate

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

傳統(tǒng)K-means 算法選擇的初始簇中心具有很大的隨機(jī)性，初始簇中心的選取不同導(dǎo)致算法迭代次數(shù)差異很大，得到的聚類結(jié)果也不同.圖1所示，本文選基于密度和距離優(yōu)選初始簇中心的K-means(以下用KM簡(jiǎn)寫)聚類在Letter數(shù)據(jù)集上聚類時(shí)間最短.這是由于本文優(yōu)選的初始簇類中心，從樣本密度分布和樣本距離兩個(gè)方面優(yōu)選初始簇中心，避免了選取集中的局部最密點(diǎn)，以及選取噪聲點(diǎn)的可能，更接近實(shí)際簇類中心，加速了聚類迭代過(guò)程.從圖2我們可以看到綜合優(yōu)選過(guò)程時(shí)間的四種方法的KM聚類在數(shù)據(jù)量較小時(shí)本文算法在迭代時(shí)間與文獻(xiàn)[9]基于密度優(yōu)選初始簇中心的KM聚類和文獻(xiàn)[12]基于距離優(yōu)選初始簇中心的KM聚類以及文獻(xiàn)[15]基于KD樹優(yōu)選初始簇中心的KM聚類差不多，但是隨著數(shù)據(jù)量的增大，本文算法迭代時(shí)間比其他算法聚類時(shí)間都短.這是由于基于密度優(yōu)初始簇中心需要計(jì)算所有樣本點(diǎn)的距離，同時(shí)計(jì)算各個(gè)樣本點(diǎn)的平均密度，所以計(jì)算量最大、時(shí)間復(fù)雜度最高.而基于距離選取初始簇中心僅需計(jì)算數(shù)據(jù)對(duì)象的距離，時(shí)間復(fù)雜度最低，但是選取的初始簇中心，是噪聲點(diǎn)的可能性很大，選取的初始簇中心與實(shí)際簇中心存在較大偏差，而基于KD樹優(yōu)選初始簇中心，建樹需要花費(fèi)大量的時(shí)間.而本文方法優(yōu)選的初始簇中心與實(shí)際簇中心更為接近，加速了迭代速度，所以隨著數(shù)據(jù)量的增加，迭代時(shí)間反而最短.圖3和圖4所示，本文基于優(yōu)選初始簇中心的KM聚類在準(zhǔn)確率和召回率上比其他方法選取初始簇中心的KM聚類算法都高，這是由于基于距離選取初始簇中心沒(méi)有考慮選取點(diǎn)周圍數(shù)據(jù)對(duì)象的密度情況，而實(shí)際上聚類中心點(diǎn)的密度往往要大于簇中其它點(diǎn)的密度；基于密度選取初始簇中心的方法沒(méi)有考慮距離情況，實(shí)際上距離越遠(yuǎn)的點(diǎn)越不可能屬于同一簇；KD樹優(yōu)選初始簇中心，在一定程度上提高了準(zhǔn)確率和召回率，但是建樹過(guò)程需要消耗大量的時(shí)間.本文所提優(yōu)選方法綜合了基于密度和基于距離兩種方法的優(yōu)勢(shì)同時(shí)避免了建樹帶來(lái)的時(shí)間開銷，提高了聚類的準(zhǔn)確度，加速了聚類的過(guò)程，也一定程度上增加了穩(wěn)定性，取得了較好的效果.

6 總結(jié)與討論

本文針對(duì)傳統(tǒng)的K-means算法中初始簇中心的隨機(jī)選取易導(dǎo)致陷入局部最優(yōu)、聚類不穩(wěn)定、收斂速度慢等問(wèn)題，提出了一種基于密度和距離的K-means初始簇中心優(yōu)選方法.該方法不斷選取距離最遠(yuǎn)的樣本點(diǎn)進(jìn)行基于貪心策略自適應(yīng)確定掃描半徑的密度聚類，從距離和密度兩個(gè)方面選取初始簇中心.本文方法能夠在一定程度上克服所選取初始簇中心是噪聲點(diǎn)以及陷入局部最優(yōu)解對(duì)聚類效果的不良影響，實(shí)驗(yàn)結(jié)果表明本文優(yōu)化選取的初始簇中心，能夠加速聚類迭代過(guò)程，減少迭代次數(shù)，同時(shí)具有更好的穩(wěn)定性、更高的準(zhǔn)確率.