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

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

（六盤水師范學院數學與計算機科學學院 貴州六盤水 553000）

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

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

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

一、改進K-means算法

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

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

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

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

（三）算法流程。基于以上思想，可以準確的確定K個密度最大的真實中心點，屏蔽離群點對算法穩定性的影響，改進后K-means算法流程如下所示：

輸入：數據集D{x1,x2,…,xn},假設聚類個數為K

輸出：K個聚類

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

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

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

Step4：從數據集D中刪除數據點xi，xi?U。

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

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

Step7：采用經典K-means算法，輸出結果。

二、實驗結果及分析

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

表1 數據集詳細信息表

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

準確率計算公式如下：

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

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

表2 聚類結果穩定性和準確性比較

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

三、結語

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