基于密度的K-means初始聚類中心點(diǎn)選取算法

李 波 管彥允 龔維印 韋旭勤 薛 端

（六盤水師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院 貴州六盤水 553000）

聚類算法在目前數(shù)據(jù)挖掘領(lǐng)域使用非常廣泛的算法，其中基于劃分的聚類算法是聚類算法中非常重要的一個(gè)分支[1]，其算法核心思想是計(jì)算每個(gè)目標(biāo)數(shù)據(jù)與聚類中心點(diǎn)的距離，把該數(shù)據(jù)點(diǎn)劃分到離其最近的聚類。K-means算法是由J.B.MacQueen[2]提出的一種基于劃分的聚類算法，由于該算法簡單、有效，能快速把大量數(shù)據(jù)集劃分到正確的聚類中[3],因此K-means聚類算法目前依然在數(shù)據(jù)挖掘領(lǐng)域占用非常重要的地位[4]。雖然經(jīng)典K-means算法高效簡單，但也存在一定的局限性：如果數(shù)據(jù)存在分布不均勻或存在離群點(diǎn)的情況，經(jīng)典K-means算法會因?yàn)樗惴ǔ跏蓟瘯r(shí)隨機(jī)選擇K個(gè)聚類中心導(dǎo)致出現(xiàn)聚類效果不佳和聚類差異性很大的情況[5]。

近幾年國內(nèi)外很多學(xué)者針對K-means算法的不足提出了大量的優(yōu)化和改進(jìn)策略。Elad M等人[6]提出基于距離和密度的方式查找聚類初始中心點(diǎn)。X Liu等人[7]提出通過計(jì)算每個(gè)點(diǎn)的距離，選擇距離最大的點(diǎn)作為聚類初始中心點(diǎn)。Huang等人[8]提出了一種特征值加權(quán)的K-means算法，通過不同的權(quán)重在迭代過程中選擇中心點(diǎn)。周本金等人[9]提出了通過方差方式選擇初始聚類中心，解決聚類結(jié)果的不穩(wěn)定問題優(yōu)化K-means聚類。左進(jìn)等人[10]提出了通過密度剔除離散點(diǎn),選擇密度均勻點(diǎn)作為聚類中心，該方法解決初始點(diǎn)的選擇隨機(jī)性導(dǎo)致聚類不穩(wěn)定。ZHU E Z等人[11]提出選擇高密度數(shù)據(jù)點(diǎn)作為聚類初始中心點(diǎn)，但是數(shù)據(jù)集中有離群點(diǎn)的情況下算法效果不佳。郭永坤等人[12]提出高密度優(yōu)先聚類算法，針對密度差異大的數(shù)據(jù)集效果理想，同時(shí)增加聚類穩(wěn)定性,但未考慮離群點(diǎn)。Aharon M等人[13]提出了自動獲取最佳K值的算法，該方法在K值變化范圍很大時(shí)效果表現(xiàn)不佳。Chen Z等人[14]提出一種基于數(shù)據(jù)點(diǎn)最大距離算法，該方法通過聚類自動計(jì)算最優(yōu)K值，但聚類初始點(diǎn)的隨機(jī)性導(dǎo)致算法的不穩(wěn)定性。

針對K-means算法存在的聚類初始點(diǎn)的隨機(jī)性和不穩(wěn)定性，本文認(rèn)為數(shù)據(jù)點(diǎn)密度大的點(diǎn)才應(yīng)該是真實(shí)的聚類中心，根據(jù)這一思路提出了一種改進(jìn)算法，算法首先分析數(shù)據(jù)密度分布，定位數(shù)據(jù)密度最大的K個(gè)點(diǎn)作為聚類初始中心點(diǎn)，從而可以解決分布不均勻數(shù)據(jù)和離群點(diǎn)導(dǎo)致的聚類不穩(wěn)定性問題增加聚類穩(wěn)定性，同時(shí)使算法快速收斂減少迭代次數(shù)。實(shí)驗(yàn)結(jié)果表明，針對分布不均勻或存在離群點(diǎn)的數(shù)據(jù)集，本算法也能快速收斂，算法穩(wěn)定性和正確性也比較高，從而充分說明了本算法的高效性和合理性。

一、改進(jìn)K-means算法

（一）經(jīng)典K-means算法。經(jīng)典K-means算法基本思想：第一步，人工確定聚類個(gè)數(shù)，算法根據(jù)聚類個(gè)數(shù)隨機(jī)選擇K個(gè)聚類初始中心點(diǎn)。第二步，計(jì)算每個(gè)數(shù)據(jù)點(diǎn)到K個(gè)聚類中心點(diǎn)的距離，根據(jù)距離把每個(gè)數(shù)據(jù)點(diǎn)劃分到離該數(shù)據(jù)點(diǎn)最近的一個(gè)聚類中去。第三步計(jì)算出新生成的K個(gè)聚類中心點(diǎn)。重復(fù)執(zhí)行上述的第二步和第三步，直到算法滿足結(jié)束條件，生成K個(gè)最終聚類，算法結(jié)束。

（二）基于密度改進(jìn)的K-means初始中心點(diǎn)聚類算法。通過λi定義可以看出，Ai越小表示數(shù)據(jù)點(diǎn)Xi以MeanDist(D)為半徑的聚類平均距離越小,反映出Xi點(diǎn)附近的數(shù)據(jù)點(diǎn)比較密集,ρ(i)越大同時(shí)也反映出Xi點(diǎn)附近的數(shù)據(jù)點(diǎn)比較密集,因此λi可以很好的展現(xiàn)出數(shù)據(jù)集D的密度分布特征。

第一步，初始數(shù)據(jù)集U={}，選擇λi最大的點(diǎn)Xi（即選擇密度最大的點(diǎn)）作為第一個(gè)初始中心點(diǎn),把以Xi點(diǎn)為中心以MeanDist(D)為半徑包含點(diǎn)作為第一個(gè)聚類U1,這樣就能選出密度最大的聚類，把U1加入U(xiǎn)。從數(shù)據(jù)D中刪除包含U的數(shù)據(jù)點(diǎn)，重新計(jì)算λi，按照上述規(guī)則直到計(jì)算出k個(gè)集合或者max（ρ(i)）＜K/4n，生成U2…UK（K表示聚類個(gè)數(shù)）。

第二步，計(jì)算數(shù)據(jù)集合Ui中每個(gè)數(shù)據(jù)點(diǎn)的簇內(nèi)誤差平方Ei，選擇Ei最小的點(diǎn)作為該聚類的初始中心點(diǎn)Ki，通過該方法選出來的初始聚類中心有效的減少迭代次數(shù),可以避免孤立點(diǎn)、噪點(diǎn)的影響。

（三）算法流程?；谝陨纤枷?，可以準(zhǔn)確的確定K個(gè)密度最大的真實(shí)中心點(diǎn)，屏蔽離群點(diǎn)對算法穩(wěn)定性的影響，改進(jìn)后K-means算法流程如下所示：

輸入：數(shù)據(jù)集D{x1,x2,…,xn},假設(shè)聚類個(gè)數(shù)為K

輸出：K個(gè)聚類

Step1：初始數(shù)據(jù)集U=?，計(jì)算數(shù)據(jù)中任意兩個(gè)點(diǎn)Xi、Xj的距離d(xi,xj),計(jì)算結(jié)果保存在矩陣Dist[n][n ]中,同時(shí)計(jì)算出數(shù)據(jù)集D的平均MeanDist(D)。

Step2：遍歷Dist[n][n]求出所有樣本點(diǎn)的密度ρ(i),同時(shí)計(jì)算出數(shù)據(jù)點(diǎn)xi的簇類平均距離Ai和參數(shù)λi。

Step3：選擇λi最大的數(shù)據(jù)點(diǎn)，計(jì)算與xi距離d（xi,x）j小于等于MeanDist(D)的數(shù)據(jù)點(diǎn)xj加入到集合U0中。

Step4：從數(shù)據(jù)集D中刪除數(shù)據(jù)點(diǎn)xi，xi?U。

Step5：重復(fù)上述 Step1到 Step4，直到|U|＜=K 或者max（ρ(i)）＜K/4n。

Step6：遍歷U中的每個(gè)數(shù)據(jù)集，求出每個(gè)Ui數(shù)據(jù)集中Ei最小的數(shù)據(jù)點(diǎn)作為簇類初始中心點(diǎn)。

Step7：采用經(jīng)典K-means算法，輸出結(jié)果。

二、實(shí)驗(yàn)結(jié)果及分析

（一）實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集。本算法在處理器Intel（R）Core（TM）i5-1135G7@2.40GHz，內(nèi)存為 16.00GB，Microsoft Windows10的操作系統(tǒng)機(jī)器運(yùn)行，算法運(yùn)行環(huán)境為Python3.7。本算法中采用的是UCI下載的數(shù)據(jù)集,UCI是加州大學(xué)提出的一個(gè)專門用來測試聚類效果的標(biāo)準(zhǔn)測試數(shù)據(jù)集[15]。本實(shí)驗(yàn)選取UCI上三個(gè)維度信息差異較大的數(shù)據(jù)集來驗(yàn)證算法的效果，通過改進(jìn)算法和經(jīng)典聚類算法對數(shù)據(jù)進(jìn)行聚類,可以很好的說明本算法對在不同維度和不同數(shù)據(jù)集都可以表現(xiàn)非常好的性能。具有詳細(xì)數(shù)據(jù)集特征見表1。

表1 數(shù)據(jù)集詳細(xì)信息表

（二）實(shí)驗(yàn)結(jié)果。本文采用聚類算法常用的準(zhǔn)確率和評價(jià)函數(shù)值（總的誤差）作為評價(jià)聚類結(jié)果好壞的關(guān)鍵評價(jià)指標(biāo)。評價(jià)函數(shù)值計(jì)算如公式8,大部分文獻(xiàn)都將評價(jià)函數(shù)作為判斷聚類效果的標(biāo)準(zhǔn),其值越小效果越好。精準(zhǔn)率是指預(yù)測分類樣本個(gè)數(shù)和實(shí)際分類樣本的比例，值越大表示正確分類的數(shù)據(jù)越多，表示算法效果越好。

準(zhǔn)確率計(jì)算公式如下：

其中Ci是聚類i中數(shù)據(jù)樣本個(gè)數(shù)，C’i是表示通過算法預(yù)測為聚類i中樣本數(shù)據(jù)個(gè)數(shù)。

本次實(shí)驗(yàn),使用UCI三個(gè)數(shù)據(jù)集Iris、Wine和Breast對K-means經(jīng)典算法、K-means++和本文算法進(jìn)行測試，為了排除隨機(jī)性對算法的影響，取三個(gè)算法在上述數(shù)據(jù)集測試的平均值作為結(jié)果。表2為三個(gè)數(shù)據(jù)集在三種算法中準(zhǔn)確率和評價(jià)函數(shù)值的平均值。

表2 聚類結(jié)果穩(wěn)定性和準(zhǔn)確性比較

（三）實(shí)驗(yàn)分析。通過實(shí)驗(yàn)結(jié)果可知,K-means經(jīng)典算法在數(shù)據(jù)集分類類別和數(shù)據(jù)集屬性數(shù)量增加的情況下,聚類的準(zhǔn)確率下降明顯。本次實(shí)驗(yàn)采用UCI網(wǎng)站3個(gè)數(shù)據(jù)集使用經(jīng)典算法和本算法來進(jìn)行測試，實(shí)驗(yàn)采用準(zhǔn)確率和評價(jià)函數(shù)值作為聚類結(jié)果的評價(jià)標(biāo)準(zhǔn)。三種不同的聚類算法在Iris指標(biāo)最好，在Breast數(shù)據(jù)集指標(biāo)最差，主要原因在于Breast數(shù)據(jù)集的聚類個(gè)數(shù)和數(shù)據(jù)維度較Iris數(shù)據(jù)集有明顯的增加。本算法通過改進(jìn)傳統(tǒng)的K-means算法隨機(jī)產(chǎn)生三個(gè)聚類初始點(diǎn)，由于初始聚類中心的選擇會決定算法的迭代次數(shù)和聚類效果，如果初始聚類點(diǎn)選擇了離群點(diǎn)將會導(dǎo)致準(zhǔn)確率的下降。本論文通過數(shù)據(jù)密度和距離等條件能夠快速有效地找到密度最大的K個(gè)初始點(diǎn)作為聚類中心點(diǎn)。通過實(shí)驗(yàn)結(jié)果可以證明本算法確定的初始聚類點(diǎn)，能夠快速讓聚類算法收斂，減少迭代次數(shù)和保證聚類效果的穩(wěn)定性。通過表2可以看到針對三個(gè)數(shù)據(jù)集，本算法對傳統(tǒng)的K-means經(jīng)典算法準(zhǔn)確率都有一定的提升。綜上所述，本論文的改進(jìn)算法是有效和可行的，在準(zhǔn)確率方面有了很大的提升，同時(shí)與其他算法相比評價(jià)函數(shù)值也有一定的優(yōu)越性。

三、結(jié)語

傳統(tǒng)K-means算法高效且簡單，是目前聚類算法中使用非常廣泛的算法，但是由于傳統(tǒng)算法隨機(jī)動態(tài)的選擇聚類初始中心，特別是數(shù)據(jù)分布不均勻或數(shù)據(jù)出現(xiàn)離群點(diǎn)的情況下，這樣會導(dǎo)致聚類的不穩(wěn)定性，增加聚類迭代次數(shù)。本論文提出的算法能夠快速定位真實(shí)數(shù)據(jù)分布中聚類密度大的中心點(diǎn)作為K-means算法初始點(diǎn)，解決了K-means算法的不穩(wěn)定性和離群點(diǎn)對算法的影響。通過實(shí)驗(yàn)結(jié)果可知，改進(jìn)后的算法確定的聚類初始中心點(diǎn)較接近真實(shí)聚類中心點(diǎn)，能夠減少算法迭代次數(shù)，提升聚類準(zhǔn)確率，從而證明本算法的真實(shí)有效。本改進(jìn)算法使用UCI網(wǎng)站的小型數(shù)據(jù)進(jìn)行測試和驗(yàn)證，在數(shù)據(jù)維度和數(shù)據(jù)集都比較大得情況，如何降低算法復(fù)雜度，進(jìn)一步提升聚類準(zhǔn)確性，將是下一步需要解決的問題。