基于改進K-means 算法的研究與分析?

楊俊成 李淑霞

（1.武漢大學計算機學院 武漢 430072）（2.河南工業職業技術學院電子信息工程學院 南陽 473000）

1 引言

隨著大數據的發展，數據挖掘迎來了機遇，聚類挖掘在數據挖掘技術中起著關鍵作用。K-means 算法作為聚類挖掘算法中的熱門算法之一，具有效果好、思想簡單的優點，同時也具有聚簇個數K 難確定、聚類中心隨機性等缺點，為了解決這些問題，它的改進算法越來越受相關研究學者的青睞。

K-means 算法是一種在聚類算法中較為流行的無監督機器學習算法。該算法由MacQueen［1］首次提出，應用廣泛，如市場分析［2~3］、特征學習［4~5］、文檔聚類［6~7］、圖像分割［8~10］，具有效果好、思想簡單、聚類速度快等優點。文獻［11］提出基于K-means的矩陣分解算法（Matrix Decompositon Based on K-means，KMMD），即將K-means 算法與矩陣分解算法相結合，從而提高算法的精度。文獻［12］引入歐氏距離，提出基于大數據K-means 的優化算法，解決傳統模糊K-means 算法中局部最優解的缺陷問題，提高聚類的準確性和速度。

層次聚類中的典型算法之一BIRCH（Balanced Iterative Reducing and Clustering using Hierarchies）是1996 年由Tian Zhang［13］提出的，目前一些學者分別從改進聚類特征的計算方式、閾值以及與其它聚類算法結合等方面對BIRCH 算法進行改進，本文結合K-means 算法和BIRCH 算法構建核心樹，完善核心樹的各個特征數據，用于解決用戶的推薦問題。

2 傳統K-means算法和BIRCH算法

2.1 傳統的K-means算法

K-means 算法是一種基于目標函數的硬聚類算法［14~16］，被廣泛應用在數據挖掘和機器學習，該算法可以使用函數求極值的方法對目標函數進行規則調整，該目標函數以距離作為優化，該算法以評價函數最少為目標，以誤差平方和的基準為依據，采用歐氏距離作為相似度計算，以初始距離中心開始進行分類，準則函數采用誤差平方進行聚類。當聚類類別數已知時，K-means算法可以通過計算，將雜亂無章的數據集合成為K 個類別簇，其中包含所有類別數據樣本。

K-means算法是一種基于聚類數k的硬聚類算法，其具體過程如下：首先，隨機選擇k 個聚類簇中心，并計算數據點與簇中心的相似度，將每個數據點分配給最近的簇中心。然后，重新計算每個簇的中心點，并再次計算數據點與簇中心的相似度，重新分配數據點。這個過程不斷迭代，直到聚類結果穩定不再變化，最終得到每個數據點所屬的聚類簇。文獻［17~18］中有關于該算法的詳細討論。

K-means算法以既定的K值進行簇的聚類［17~18］，隨機選擇k 個聚類簇中心，將數據點分配到最近的簇中心，重新計算簇中心并重新分配數據點，不斷迭代，直到聚類結果穩定不變。詳細描述如下：

1）從數據集中隨機抽取一定數量K 個文檔作為初始聚類中心；

2）確定歸類的條件，將剩余文檔與聚類中心的歐式距離作為歸類條件；

3）根據歐式距離的測量方式，將每個文檔與最近的聚類中心進行比較，將其分配到距離最近的簇中；

4）對每個簇中的數據點進行重新計算，即每個簇中文檔對象均值，同時計算所有簇的聚類結果好壞SSE；

5）如果SSE 值發生變化，重復2），否則算法結束，給出聚類結果。

以同樣的方式計算提取到的所有數據，即計算數據特征間的相似性，使用均值算法對不同的數據樣本進行迭代，以確定它們所屬的不同類別。最終，我們可以根據提取到的用戶數據所屬的類別，為用戶提供符合其習慣的個性化推薦服務。

2.2 BIRCH算法

BIRCH算法是層次聚類算法之一［19］，也是根據平衡迭代規約和聚類的典型方法。該算法通過掃描數據集構建聚類特征樹，根據聚類特征樹的類別判斷匯總數據信息，聚類數據的分布數據集很容易受離群點的影響，從而影響距離中心的計算結果。該算法適用于大數據集的處理，可以通過單遍掃描數據集進行有效聚類，最小化數據集的輸入輸出，算法描述如下：

1）掃描整個數據集，建立盡可能包含所有屬性信息的初始化聚類特征樹。建立聚類特征樹中插入對象的過程類似于B+樹的插入和分裂過程，通過簇的半徑和閾值的比較來確定葉節點是否被分割（Split）［20］。

2）利用聚類算法對聚類特征進行聚類。

3 改進K-means算法

3.1 改進K-means算法原理

K-means 算法的第一步是計算數據點與聚類中心之間的距離，只有定義了距離度量，才能使用該算法進行數據聚類。若無法定義距離，則數據與聚類中心間不能建立聯系，也會使K-means算法不能更新聚類中心。該算法輸入是聚類類別，在很多應用場景的海量數據中，聚類類別不好確定，一般只能以歷史經驗為依據給出聚類類別，這種方式得到的結果不太準確，但K-means算法可以通過選擇適當的距離度量方式降低離群點對聚類中心的影響，從而提高數據聚類的準確性和精度。

BIRCH算法容易受到離群點的影響，導致聚類結果不準確。影響距離中心的計算結果，難以準確展現匯總信息，所以此算法不適宜處理數據分類。傳統BIRCH 算法由三元組表示，并將聚類信息集合到下面的三元組中CF=(N,LS,SS)。該三元組中N 代表聚類數據個數，LS 代表N 個對象的線性和，SS代表N個對象的平方和。

BIRCH算法和K-means算法各有優劣，結合兩者算法構建核心樹，利用BIRCH 算法樹形結構對時間復雜度較低的數據進行運算處理，利用K-means 算法對離群點干擾較大的數據進行運算處理，以獲得更好的聚類效果，并基于此算法完成對用戶的數據推薦。另外本文通過對數據變量的研究，結合傳統BIRCH 算法的表示形式，將聚類特征定義為CF=(n,I,S)。其中n表示要分類的數據量總和，I表示所有對象的類別集合。S表示數據樣本的個數。

由于用戶數據量與集合I 呈現正比關系，所以很難通過常規模式表示大量數據集合，因此需要用聚類特征替代原有海量數據，具體過程可以描述如下：

1）確定最佳中心點，即處于特征數據最中央位置的特征數據點；

2）確定次中心點，即接近中心點的數據點，次中心點能夠最大程度輔助確定最佳中心點；

3）確定亞中心點，亞中心點對于最佳中心點的確定也能起到輔助計算作用；

4）確定核心數據，這些核心數據是一種壓縮形式，可以統計表示出的某些特征；

5）確定核心樹，由子類類別中心構成平衡樹，由聚類特征構成增量距離算法，有效完成算法的構造與執行效率。

3.2 核心樹的初始化過程

從葉節點或根節點開始構造樹形結構，利用K-means算法進行聚類，使用歐式距離計算節點間的距離，以距離為依據判斷節點之間的相似性，并得到核心數據。之后，使用BIRCH 算法構造樹形結構，并將K 個類別的中點作為核心樹的葉節點，依據葉節點構造核心樹，具體構建核心樹的過程可以描述如下：

1）提取中點數據，若此中點符合拓展節點條件，則將中點插入到當前節點中，否則轉2）。

2）對已知CI 個中點進行判斷，若符合葉子節點特征轉為3），否則轉為4）。

3）計算中點距離，以最小距離的中點為選項，持續運行節點搜索，搜索的流程重新以1）開始進行。

4）該節點Ci 是葉子節點，使用最遠距離對該葉子節點進行分裂，使之分裂成為兩個葉子節點。第一以Floyd 算法為依據計算葉子節點的中點，挑選兩個相似度最小的點，即為距離最遠的兩個中心點；第二將其他的中點進行距離計算，并將其分裂到相似度最小的兩個中點中。最后比較中心點個數與閾值，若小于則完成構建，否則轉到第4）步。

3.3 特征迭代完善樹

完成了核心樹的構建后，還需要完善核心樹的各個特征數據，分為以下幾個步驟：

1）對于新讀入的對象要計算它與每個類別中點之間的距離，并選擇距離最近的類別中點作為聚類路徑。

2）如果特征數據與葉子節點的距離接近，則計算該葉子節點到根節點的距離，將此距離數值與已設定的閾值進行對比，若距離數值小于閾值，則可以將此特征數據與葉子節點聚為一類，轉到3），若距離數值超出閾值則轉2）重新計算。

3）如果距離數值小于中心半徑，則判斷特征數據是本類別的核心數據，反之則不是。然后對核心數據進行排序，并將其存儲到鏈表中。

4）判斷聚類中心是否更新，當類別發散度（即數據到聚類中心點的距離）大于2，說明該聚類的所有數據出現了松散，該聚類中心發生了變化，根據式（1）重新計算該聚類中心，以便確定新的距離中心。

其中，core表示核心特征數據的個數，num為總的特征數據個數，參數p 為聚類類別發散度，p 越小說明數據到聚類中心點的距離越小，聚類半徑越小；而p越大則說明數據到聚類中心點的距離越大，聚類半徑也很大。

3.4 改進的K-means算法

使用增量聚類方法處理輸入的特征數據，并為了避免葉子節點全部依賴聚類結果，則需要改進葉子節點。為了得到更好的效果，本文將每個葉子節點與對應的核心樹連接起來，形成一個鏈表結構，如圖1所示。

圖1 鏈表結構圖

由圖1 可知，鏈接起核心數據與各個葉子節點的聚類中心和核心數據，為了避免劇烈算法過于依賴輸入順序，重置葉子節點的聚類中心位置算法。為了準確地確定是否需要更新聚類中心點，應該通過對比核心數據和非核心數據來確定是否需要更新聚類中心確保葉子節點的聚類中心不過于依賴輸入數據的順序。

本文使用核心數據和聚類中心數據來構建葉子節點聚類中心鏈表。對于相鄰的每個葉子節點，使用它們的數據進行聚類，并定義新的聚類中心。然后，重新將數據源的數據分配到對應的聚類中心中。最后，根據式（2）計算出的方差結果來決定是否重置聚類中心點。

4 實驗分析

本文基于python3.6 實現魯棒性的核心樹聚類算法，對養老用戶相關數據進行聚類，把分析后的數據分配到與其對應的類別當中，為用戶的選擇給出決策依據。

本文通過測試6 組養老服務護理文本數據，驗正傳統算法和改進算法的運行時間，相關結果顯示如圖2。

圖2 算法運行時間趨勢

根據圖2 的結果，本文驗證了改進算法在計算相同樣本數據時具有更短的平均耗時，進而證明了其有效性。因此，本文在養老服務護理系統的聚類模塊中采用改進后的K-means算法，并對護理方案模塊進行了分析，以滿足定制化需求的要求。

5 結語

K-means 算法是無監督學習的聚類算法，存在K 值不好選擇、凸數據集較難收斂、并對噪音和異常點比較敏感，本文結合K-means 算法和BIRCH算法構建核心樹，可以用較少的時間內完成用戶的數據推薦。