馮 勇，張學理，王嶸冰，徐紅艷

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

1 引 言

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

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

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

2 K-means聚類算法

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

1)從聚類對象中隨機選取K個對象作為初始簇中心.

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

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

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

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

3 相關(guān)工作

3.1 DBSCAN算法

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

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

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

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

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

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

3.2 基于最遠距離的K-means聚類

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

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

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

4.1 基本思想

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

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

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

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

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

(1)

(2)

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

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

4.2 算法描述

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

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

輸出：K個初始簇中心點

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

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

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

4. end for

5. for j=1 tonformDBdo

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

7.Maxdisp←select_maxOrderDis(OrderDis)

//選取相距最遠的點Maxdisp

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

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

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

10.Dbscan_clusters←greedy_Dbscan(Maxdisp，minPts)

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

11. end if

12. end if

13. end for

14.init_clusterceter←initcenter(Dbscan_clusters，K)

//在每個初始簇中選取支持度最大的核心點作為初始簇中心init_clusterceter

15. end

5 實驗與分析

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

5.1 實驗描述

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

圖1 K-means聚類運行時長對比Fig.1 Contrast of running time in K-means cluster

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

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

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

圖3 聚類準確率對比Fig.3 Contrast of clustering accuracy

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

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

5.2 實驗結(jié)果與分析

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

6 總結(jié)與討論

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