基于密度的K-means初始聚類中心點選取算法

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

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

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

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

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

一、改進K-means算法

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

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

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

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

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

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

輸出：K個聚類

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

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

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

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

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

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

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

二、實驗結(jié)果及分析

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

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

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

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

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

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

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

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

三、結(jié)語

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