基于密度的優(yōu)化初始聚類中心K-MEANS算法研究

何佳知，謝穎華

（東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院，上海 201620）

0 引言

隨著“信息爆炸”時代的到來，數(shù)據(jù)挖掘領(lǐng)域得到人們越來越多的關(guān)注。聚類分析作為數(shù)據(jù)挖掘的重要分支，屬于無監(jiān)督的機(jī)器學(xué)習(xí)方法[1]?；谖镆灶惥鄣乃枷?，聚類分析把樣本點(diǎn)劃分為子簇，使得同一簇中的對象盡可能相似，而不同簇的對象盡可能相異[2]。目前，聚類已根植于許多應(yīng)用領(lǐng)域，包括商務(wù)智能、圖像模式識別、WEB搜索、生物學(xué)和安全等[3]。

K-means算法是目前聚類分析領(lǐng)域中基于劃分的熱門研究課題，具有理論可靠、算法簡單、收斂速度快、能有效處理大數(shù)據(jù)的特點(diǎn)[4]。但它也存在一些不可避免的問題[5]：（1）聚類數(shù)目k需要預(yù)先確定，經(jīng)驗(yàn)的缺乏導(dǎo)致對k的數(shù)值很難界定；（2）聚類結(jié)果隨初始聚類中心的不同而變化，容易陷入局部最優(yōu)解；（3）對局部極值點(diǎn)敏感，嚴(yán)重影響聚類結(jié)果的準(zhǔn)確性。

本文提出一種基于密度優(yōu)化初始聚類中心的方法，使其盡可能有代表性地反映數(shù)據(jù)的分布特征。利用數(shù)據(jù)集樣本的點(diǎn)密度，對樣本集劃分高低密度集，選取高密度集合中的k個相距較遠(yuǎn)、密度最大的樣本作為初始聚類中心，避免初始聚類中心位于同一類簇的缺陷，同時對噪聲點(diǎn)進(jìn)行單獨(dú)處理，減小其對聚類結(jié)果的影響。

1 K-means算法介紹及相關(guān)研究

K-means算法是基于劃分的聚類算法之一，基本思想[6]是：從包含n個對象的數(shù)據(jù)集中隨機(jī)選取k個樣本點(diǎn)作為初始聚類中心，對于剩下的每個對象，計算其與各個聚類中心的距離，將它分配到最近的聚類，并重新計算聚類中心，再將所有的樣本點(diǎn)依據(jù)最近距離原則分配到相應(yīng)的聚類簇中，不斷地迭代直到分配穩(wěn)定，即聚類誤差平方和E收斂。

K-means算法簡單，且適用于大規(guī)模數(shù)據(jù)量，但初始聚類中心的選取直接影響算法的聚類結(jié)果，算法的迭代次數(shù)依賴于初始聚類中心和實(shí)際聚類中心的偏差，因此，選取一組合適的初始聚類中心非常重要[7]。很多國內(nèi)外學(xué)者從不同角度對該算法聚類中心的選取進(jìn)行了改進(jìn)。陸林華[8]對遺傳算法進(jìn)行優(yōu)化，將遺傳算法的全局搜索能力與K-means算法的局部搜索能力相結(jié)合；KAUFMAN L等[9]提出一種啟發(fā)式方法，估計數(shù)據(jù)點(diǎn)的局部密度，并以此啟發(fā)選擇初始聚類中心；袁方等[10]提出給予樣本相似度和通過合適權(quán)值來初始化聚類的方法；Huang J[11]提出一種變量自動加權(quán)方法，ALSABTI[12]利用k-d樹結(jié)構(gòu)改進(jìn)K-means算法；汪中[5]等人采用密度敏感的相似性度量計算數(shù)據(jù)對象的密度，啟發(fā)式地生成初始聚類中心；韓凌波[13]等人通過計算每個數(shù)據(jù)對象的密度參數(shù)選取k個處于高密度分布的點(diǎn)作為初始聚類中心；賴玉霞[14]等人采用聚類對象分布密度方法，選擇相互距離最遠(yuǎn)的k個處于高密度區(qū)域的點(diǎn)作為初始聚類中心；王賽芳[15]等人通過計算點(diǎn)密度來選取初始聚類中心。

2 基于密度改進(jìn)的K-means算法

傳統(tǒng)的K-means算法對初始聚類中心敏感，聚類結(jié)果隨不同的初始中心而波動。隨機(jī)選取的初始聚類中心有可能是一些孤立點(diǎn)或噪聲點(diǎn)，或者不同類簇的初始聚類中心位于同一個類簇，導(dǎo)致聚類結(jié)果可能偏離樣本的真實(shí)分布，得到錯誤的聚類結(jié)果，使聚類的收斂速度緩慢甚至難以收斂。選取相距較遠(yuǎn)的樣本作為初始聚類中心，可避免初始聚類中心位于同一類簇的缺陷，但對噪聲點(diǎn)敏感；參考文獻(xiàn)[11-12]解決了噪聲點(diǎn)的問題，但由于涉及到密度調(diào)節(jié)系數(shù)或噪聲調(diào)節(jié)系數(shù)，聚類結(jié)果直接依賴于參數(shù)的選擇。主觀性強(qiáng)，如果參數(shù)選擇不好，聚類結(jié)果將變得很差。

針對上述局限性，本文提出一種基于點(diǎn)密度優(yōu)化初始聚類中心選取的方式。在樣本點(diǎn)空間中，一般認(rèn)為高密度區(qū)域的點(diǎn)會被低密度區(qū)域的點(diǎn)分割，而噪聲點(diǎn)往往處于低密度區(qū)域。同時，在以歐氏距離作為相似性度量標(biāo)準(zhǔn)的情況下，相互距離遠(yuǎn)的k個樣本點(diǎn)往往比隨機(jī)選取更具有代表性。因此，在劃分出含有噪聲點(diǎn)的低密度區(qū)域后，本文在高密度區(qū)域選取k個相互距離超過某閾值，且密度最大的樣本點(diǎn)作為初始聚類中心，即改進(jìn)K-means算法中的隨機(jī)選取初始聚類中心。

2.1 基本定義

設(shè)給定含有 n個樣本點(diǎn)的數(shù)據(jù)集合 X={xi|xi∈R，i=1，2，…，n}，k 個聚類類別 Cj（j=1，2，…，k，k＜n），k 個初始聚類中心 ncj（j=1，2，…，k）。 有如下定義：

定義1任意兩個樣本點(diǎn)間的歐氏距離

定義2 聚類中心（每個聚類簇的樣本點(diǎn)的均值）

定義3聚類誤差平方和

聚類誤差平方和是數(shù)據(jù)集所有對象與它所在簇的聚類中心的平方誤差的總和。聚類誤差平方和越大，說明對象與聚類中心的距離越大，簇內(nèi)的相似度越低，反之亦然。聚類誤差平方和應(yīng)盡可能小，從而使生成的結(jié)果簇盡可能緊湊和獨(dú)立。

定義4點(diǎn)密度

對數(shù)據(jù)集 X中的樣本點(diǎn) x，以 x為圓心，r（r＞0）為半徑的球域內(nèi)所包含的樣本點(diǎn)的個數(shù)稱為x的密度，記為D（x），即

式中，y（x，p）表示樣本點(diǎn) x與 p的距離。通過比較，本文選擇以歐氏距離作為距離度量，即 y（x，p）=d（x，p），r為設(shè)定的距離閾值。D（x）越大，樣本點(diǎn)所處區(qū)域密度越高。

定義5噪聲點(diǎn)

對于數(shù)據(jù)集 X 中的樣本點(diǎn) x，若 D（x）＜αMD（x），則稱x為噪聲點(diǎn)。其中，MD（x）為所有樣本點(diǎn)的密度平均值，即

2.2 初始聚類中心的優(yōu)化算法

基于密度優(yōu)化初始聚類中心的基本思想是：首先計算樣本集中每個樣本點(diǎn)的密度 D（x），并通過與整個樣本集平均密度MD（x）的比較，將其劃分給高密度集 M或低密度集N。選取集合M中密度最大的樣本點(diǎn)作為第一個初始聚類中心nc1，將其從集合M中剔除；接著從集合M中選取與nc1距離超過距離閾值r，且密度最大的點(diǎn)作為第二個初始聚類中心nc2，以此類推，直到選取了k個初始聚類中心。

基于密度優(yōu)化初始聚類中心算法的具體步驟如下：

輸入：聚類簇的數(shù)目k以及包含n個對象的數(shù)據(jù)集X

輸出：初始聚類中心集合nc，高密度集M和低密度集N

（1）根據(jù)式（1），計算樣本集兩兩樣本點(diǎn)間的距離，構(gòu)造距離矩陣D；

（2）根據(jù)式（4）和式（5），計算樣本集中每個樣本點(diǎn)的密度 D（x），以及整個樣本集的平均密度 MD（x）；

（3）根據(jù) MD（x），對樣本點(diǎn)進(jìn)行劃分，依次歸類進(jìn)高密度集M或低密度集N；

（4）選取M中密度最大的樣本點(diǎn)作為第一個初始聚類中心 nc1，并將其放入集合 nc中，即 nc=nc∪{nc1}；

（5）選取下一個初始聚類中心nc2，并將其放入集合nc 中，即 nc=nc∪{nc2}。 其中，nc2應(yīng)滿足：①d（nc1，nc2）≥r；②D（nc2）=max{D（x）|x∈X-nc}；

（6）重復(fù)步驟（5），直到選取 k個初始聚類中心。

2.3 噪聲點(diǎn)的處理

聚類過程中，本文將數(shù)據(jù)樣本劃分為高密度集和低密度集，其中，低密度集就是噪聲點(diǎn)集合。選取完k個初始聚類中心后，首先對集合M中的樣本點(diǎn)進(jìn)行K-means聚類，得到k個聚類和k個聚類中心。接著依據(jù)最小距離原則，將集合N中的噪聲點(diǎn)分配到各個聚類中，完成所有樣本點(diǎn)的分配聚類。由于避免了噪聲點(diǎn)對聚類過程的參與，減少了其對聚類中心的影響，改善了聚類效果。

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

為了驗(yàn)證本文算法的有效性，選用MATLAB語言編程環(huán)境，對 UCI數(shù)據(jù)集進(jìn)行測試，并與參考文獻(xiàn)[5，12，14]及傳統(tǒng)K-means算法的聚類結(jié)果進(jìn)行比較。對算法聚類結(jié)果的評價標(biāo)準(zhǔn)包含很多種，本文采用兩種度量指標(biāo)：聚類準(zhǔn)確率和聚類時間。利用聚類準(zhǔn)確率來度量算法的有效性，利用聚類時間來度量算法的執(zhí)行效率。

3.1 數(shù)據(jù)集描述及參數(shù)設(shè)定

UCI數(shù)據(jù)集是國際上專門用來測試機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘算法的公共數(shù)據(jù)庫，庫中的數(shù)據(jù)都有確定的分類，因此可以用準(zhǔn)確率來直觀地反映聚類算法的質(zhì)量。在此，本文選擇數(shù)據(jù)庫中的Iris、Wine、Balance-scale、Hayes-roth以及New-thyroid 5組數(shù)據(jù)作為測試數(shù)據(jù)，如表1。

表1 UCI數(shù)據(jù)描述

3.2 實(shí)驗(yàn)結(jié)果

根據(jù)經(jīng)驗(yàn)，將改進(jìn)算法的密度球域半徑r設(shè)為樣本點(diǎn)兩兩間的平均歐式距離；噪聲點(diǎn)劃分閾值 0＜α≤1，一般取值為1。所有算法均在表1給出的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，所有評價結(jié)果均為在數(shù)據(jù)集上實(shí)驗(yàn)執(zhí)行100次后取平均值。表2為選取五種不同初始聚類中心情況下算法在UCI數(shù)據(jù)集上的聚類準(zhǔn)確率的比較，表3為各算法的聚類時間比較。

表2 各算法在UCI數(shù)據(jù)集上的聚類準(zhǔn)確率比較（%）

表3 各算法在UCI數(shù)據(jù)集上的聚類時間比較 （s）

由表2聚類準(zhǔn)確率的比較可知，在Iris數(shù)據(jù)集上，本文算法的聚類準(zhǔn)確率與參考文獻(xiàn)[14]中的算法一致，高于傳統(tǒng) K-means算法和參考文獻(xiàn)[5，12]；在 Wine數(shù)據(jù)集上，本文算法的準(zhǔn)確率略低于參考文獻(xiàn)[5]，但高于參考文獻(xiàn)[12，14]及傳統(tǒng) K-means；在 Hayes-roth數(shù)據(jù)集上，本文算法的聚類準(zhǔn)確率與參考文獻(xiàn)[12]一致，高于參考文獻(xiàn)[5、14]及傳統(tǒng)算法；而在其他數(shù)據(jù)集上，文本算法的聚類準(zhǔn)確率高于其他四種算法。由此可見，本文算法相較于其他算法，聚類準(zhǔn)確性更高。

由表3各算法聚類時間的比較可知，傳統(tǒng)K-means算法的運(yùn)行時間最短；本文算法的聚類運(yùn)行時間優(yōu)于參考文獻(xiàn)[12，14]，具有更快的收斂速度；但與參考文獻(xiàn)[5]相比，在Scale和Wine數(shù)據(jù)集上，本文算法的聚類速度略有遜色。就總體時間分析而言，本文的算法優(yōu)于其他算法，但不如傳統(tǒng)K-means算法的速度快。這是因?yàn)楦倪M(jìn)后的算法增加了選擇初始中心這一環(huán)節(jié)，造成了一定的時間損耗，但優(yōu)化后的初始聚類中心能更好地表達(dá)數(shù)據(jù)的分布特征，有效縮短聚類過程，因此在一定程度上又能減少時間的損耗。

以上結(jié)果表明，相較于其他優(yōu)化初始聚類中心的K-means算法，本文算法不僅可以獲得更好的聚類效果，同時也能縮短聚類時間。

4 結(jié)束語

K-means算法應(yīng)用廣泛，但由于其過分依賴于初始化，聚類結(jié)果隨初始中心的變化而波動，難以保證優(yōu)良的性能。本文基于密度，有效改進(jìn)了初始中心點(diǎn)的選取，克服了傳統(tǒng)算法敏感且聚類效果容易陷入局部最優(yōu)的缺陷，同時在一定程度上避免了噪聲數(shù)據(jù)對聚類結(jié)果的影響。實(shí)驗(yàn)結(jié)果證明，該算法能大大提高聚類的準(zhǔn)確性。

[1]毛國君，段立娟，王實(shí)，等.數(shù)據(jù)挖掘原理與算法[M].北京：清華大學(xué)出版社，2005.

[2]朱明.數(shù)據(jù)挖掘[M].合肥：中國科學(xué)技術(shù)大學(xué)出版社，2002.

[3]Han Jiawei，KAMBER M.數(shù)據(jù)挖掘概念與技術(shù)[M].范明，孟小峰，譯.北京：機(jī)械工業(yè)出版社，2000.

[4]謝娟英，郭文娟.基于樣本空間分布密度的初始聚類中心優(yōu)化 K-均值算法[J].計算機(jī)應(yīng)用研究，2012，29（3）：888-890.

[5]汪中，劉貴全，陳恩紅.一種優(yōu)化初始中心點(diǎn)的K-means算法[J].模式識別與人工智能，2009，22（2）：300-302.

[6]莫錦萍，陳琴，馬琳，等.一種新的 K-Means蟻群聚類算法[J].廣西科學(xué)學(xué)院學(xué)報，2008，24（4）：284-286.

[7]柯良文，王靖.基于用戶相似度遷移的協(xié)同過濾推薦算法[J].微型機(jī)與應(yīng)用，2014，33（14）：71-74.

[8]陸林華，王波.一種改進(jìn)的遺傳聚類算法[J].計算機(jī)工程與應(yīng)用，2007，43（21）：170-172.

[9]KAUFMAN L，ROUSSEEUW P J.Finding groups in data：all intro-duction to cluster analysis[M].New York： Wileys，1990.

[10]袁方，孟增輝，于戈.對K-means聚類算法的改進(jìn)[J].計算機(jī)工程與應(yīng)用，2004，40（36）：177-178，232.

[11]HUANG J Z，NG M K，HONGQIALLG R，et al.Automated variable weighting in K-means type clustering[J].IEEE Trans on Pattern Analysis and Machine Intelligence，2005，27（5）：657-668.

[12]ALSABTI K，RANKA S，SINGH V.An efficient K-means clustering algorithm[C].IPPS/SPDP Workshop on High Performance Data Mining.Orlando，F(xiàn)lorida，1998：9-15.

[13]韓凌波，王強(qiáng)，蔣正峰，等.一種改進(jìn)的 K-means初始聚類中心選取算法 [J].計算機(jī)工程與應(yīng)用，2010，46（17）：150-152.

[14]賴玉霞，劉建平.K-means算法的初始聚類中心的優(yōu)化[J].計算機(jī)工程與應(yīng)用，2008，44（10）：147-149.

[15]王賽芳，戴芳，王萬斌，等.基于初始聚類中心優(yōu)化的K-均值算法 [J].計算機(jī)工程與科學(xué)，2010，32（10）：105-107.