基于網格密度的K—均值算法簇中心點識別的研究

劉利康

摘 要：傳統的K-均值聚類算法只能通過人工參數設定K值和初始簇中心點，而人工方式選擇的K值和初始簇中心點往往有較大偏差，直接導致錯誤的分簇結果.基于上述問題，本文提出了一種基于網格和密度的K值與最佳初始簇類中心自動識別的方法。經理論和實驗證明，該方法在很大程度提高了聚類結果的質量和算法的效率。

關鍵詞：K-均值 網格聚類 簇中心點 密度峰值

一、引言

K-均值算法是目前聚類分析算法中應用歷史較久、范圍較廣泛的一種。傳統的K-均值以平方誤差準則較好的實現了空間聚類，對處理大規模數據集有較大優勢。但K-均值太依賴于K值、初始簇中心點的設定。由于大多數情況下，聚類數K和簇的大致中心位置無法事先確定，因此需要通過優化算法對聚類數K和最佳初始簇中心點進行估計。但對于如何確定K和各個簇中心的位置范圍，目前尚無明確的理論指導，本文則針對此問題展開討論。

本文結合K-均值算法和網格、密度算法的優點，提出一種新的K-均值算法中K值和最優初始簇中心點自動識別的方法。經過理論和實驗分析驗證了該方法可以通過計算分析自動給出K值和較佳的初始簇中心點，很大程度改善了K-均值需要人工設置參數的問題，有效提高了聚類精度和效率。

二、典型基于劃分方法—K-均值算法

k-均值算法由J.B.MacQueen于1967年提出[4]，是經典聚類算法之一。近幾十年來被廣泛應用于生物統計、圖像處理、信息檢索、客戶分類等各領域。針對該算法的完善、改進和擴展，人們做了大量的長時間研究工作。

設待分析數據集合D的屬性數為d，數據對象數量為N，以歐式距離作為數據對象的差異程度的度量，則D可看作d維歐式空間Rd中的數據點集。設每個數據點為Xi，則D= {Xi，i=1，2，...，N}。

k-均值算法以k為參數，其核心思想是將N個數據點分為k個簇，使得每個簇中的數據點到該簇中心點的平方和最小，算法的流程如下：

1.從N個數據點中任意選取k個作為初始的簇類中心點；

2.分別計算每個數據點到各簇中心點的距離，以最近鄰原則，將該數據點分配到距離最近的簇中；

3.所有數據點分配完畢后，重新計算k個聚類的中心位置；

4.與前一次計算所得的k個聚類中心點的位置比較，若中心點位置變化的程度小于某閥值（即準則函數收斂），那么算法結束；否則轉步驟2繼續執行。

k-均值算法的優點包括：執行效率高、伸縮性強、設計思路簡單明了等。但同樣k-均值算法也存在著一定缺點，主要有：

1.算法擅長處理球狀簇的數據集，對于任意形狀的數據往往效果較差；

2.算法的k值需要人工指定，而這個k值是很難估計的。很多情況下，我們事先并不知道數據集應該分為幾類；

3.算法的初始簇中心點是隨機選取的，選取點不同，結果也可能不同，這種依賴性導致聚類結果的不穩定。且k-均值算法常采用誤差平方和準則函數作為聚類準則函數，導致結果容易陷入局部最優，難以獲取全局最優解；

4.算法需要不斷計算調整后的新的簇中心位置，然后不斷對數據點的分簇進行調整，因此在數據量大時，時間開銷非常大；

5.對噪聲點和孤立點敏感。

本文針對k-均值的k值和初始簇中心點的依賴性問題，提出一種通過網格化方法自動確定k值和選取最佳初始簇中心點的新思路，在此基礎上給出了改進的K-均值算法。

三、利用網格的貢獻值進行網格劃分

為便于空間定位和網格統計量的計算，改進的算法先對數據作歸一化，然后采用均勻劃分方法。設每一維上劃分長度相同的P個區間，則劃分產生Pd個網格。那么P值該取多大呢？這里引入網格貢獻值的概念來獲取最佳的網格劃分。

我們將網格看做盒子，網格中的數據點看作盒子中的小球，則最均勻的狀態是一個盒子裝一個球，這時數據集沒有簇產生，聚類沒有意義。但該狀態是小概率事件，現實中幾乎不可能出現。實際上數據分布往往是不均的，一個盒子可能裝好幾個球，也可能是空的。

我們在盒子和球的數量一一對應的條件下考察二者的關系。一個盒子是空的意味著另一個盒子多一個球，空盒子越多說明另外有盒子裝得越滿，分布越不均勻，聚類越容易，因此對聚類的貢獻越大。另外換個角度看，盒子裝得越滿，說明空盒子變的更多，有球的盒子之間的空盒子越多，空隙越大，聚類變容易，對聚類的貢獻也越大。

自然的引入單元網格貢獻值的概念，用C表示。容易想到將包含數據點數為1（基數為1）的單元網格貢獻值設0。因為均勻狀態的單元網格基數全部為1，對形成密度差沒有任何貢獻。直觀上看，一個盒子一個球是常態，正常情況應該就是這樣，談不上貢獻。把球從一個盒子拿到另一個盒子的運動為改變常態做了“功”，這里稱為“貢獻”。使狀態偏離常態越遠，“貢獻”就越大。

描述貢獻值最簡單的方式將貢獻值函數設置為線性函數C=|n-1|，將空盒子的貢獻值設為1，基數為1的盒子設為0，基數大于1的盒子設為n-1。為更符合貢獻值的變化曲線，一般采用Sigmoid核函數的變化形式進行描述：

稱基數為n的網格為n-網格，則n-網格的貢獻值為S（|n-1|）。這里將1-網格稱為臨界網格，易知當網格劃分和臨界網格確定后，全部網格的貢獻值總和越大，簇之間的空隙越大，類別特征越明顯。

我們稱基數大于臨界網格的網格為稠密網格，基數小于或等于臨界網格則稱為稀疏網格。臨界網格也可選擇基數為2，3，…，n的網格擔當，實踐證明，在數據量較大的時候，基數在1到4之間選擇常得到聚類效果佳的劃分。文中我們設臨界網格為1-網格，即網格數盡量與數據點數一致。令hd=N，則每一維劃分數P=[h]，這里為提高聚類效率，讓P向下取整。

確定P值之后，將每維劃分成P個小區間，由于數據已歸一化，于是每維的取值范圍為[0，1]，為保證每個數據點落到唯一的網格中，設第1個劃分區間為閉區間，其他情況下為左開右閉區間，…，。然后遍歷數據點集，將數據點依次放入所屬的網格中，并統計網格基數。遍歷完成后，將稠密網格按基數降序排序生成稠密網格降序列表G。