基于直方圖峰值優化的階梯k-means 聚類算法

文/李芝峰 景源

1 引言

K-means 是無監督學習中最為常用的經典算法，也是數據挖掘算法中很經典的算法之一。K-means 算法和初始聚類中心點的選擇有很大的關系，合理的初始聚類中心點不僅能夠增加分類的準確率，而且還能夠減少迭代次數，縮短運算時間。傳統的K-means 算法原理簡單，但是有一下幾個四個缺陷：

（1）傳統算法對于噪音點敏感，對異常點不穩定，而且傳統算法比較容易陷入局部最優解中，得到的結果和我們理想的結果有些差距。

（2）初始聚類中心是隨機選擇，每次都會選擇不同的初始聚類中心，算法的計算效率時好時壞。

（3）只能發現球狀簇規則的分布。

（4）K-means 算法是屬于無監督學習算法的一種，K 值需要根據研究人員的經驗事先指定，在多種類別混合的數據中，不能夠很好的確定分類K 值。

K-means 聚類算法可以應用在不同的領域，文獻[3]對K-means 算法改進并應用在音頻處理中。該算法適合應用在音頻分離上，階梯K-means 算法對多維數據進行降維處理，通過直方圖分布能夠得到數據的峰值區間，也就是高密度分布區域，初始聚類中心點大多都屬于這個峰值區間，從這個峰值區間選取的初始聚類中心點很接近聚類的中心區域，很顯然通過峰值得到的K 個初始聚類中心點能夠很大程度上減少計算量。

2 常用K-means算法介紹

2.1 傳統K-means算法

傳統K-means 算法是一個無監督學習，它把數據分成若干類，統一類中的數據相似性應可能的大，不同類中的數據的差異性應盡可能的大。傳統K-means 算法是在人工指定K值的情況下，隨機選擇K 個點作為初始聚類中心。

傳統K-means 算法的步驟分為：

（1）隨機選取K 個點，作為K 類的初始聚類中心點，記做C={c1, c2…ck,}

（2）遍歷所有的數據點vj，計算歐式距離，找到距離C={c1,c2…ck,}最近的聚類并加入

（3）分別計算K 類所有數據的中心點，作為該類新的聚類中心

（4）重復進行（2）（3）步驟，直到每一類的聚類中心不再發生變化

傳統K-means 聚類算法是基于局部最優

2.2 K-means++算法

K-means++算法主要改善了傳統K-means算法初始聚類中心點選擇，對初始聚類中心的選擇比較符合人類的直覺：中心點之間的距離越遠越好。

K-means++算法的具體步驟為：

（1）隨機選取一個點，作為初始聚類中心點，記做c1；

（2）遍歷所有的數據點vj，找到距離已有聚類中心C={c1,c2…ck,}之間最近距離，用D(x)表示；

（4）重復進行（2）（3）步驟，直到選出K 個聚類中心C={c1,c2…ck,}

K-means++聚類算法還是隨機第一個初始聚類中心點，花費了額外的時間來計算初始聚類中心點，但是減少了迭代的次數，本身能夠快速的收斂。

3 直方圖峰值優化的K-means算法

從密度集中區域選擇的點作為初始中心點，可以很好的區分各個聚類集合，并能夠減少一定的計算迭代次數。在統計數據的時候，按照頻數的分布表，在二維坐標體系中，橫坐標代表每組的端點，縱坐標代表頻數，這樣的統計圖叫做頻數分布直方圖。先對N 維數據XN(1,2,…n)進行初步的處理，將多維數據XN(1,2,…n)降維成一維數據Xi（i=1……j）并排序，這樣我們能夠得到開始點Xs和結束點Xe，求的這兩個點之間的距離dx=Xe-Xs，文獻[4]默認分組的數量為s=3*K，每一組的距離是d=dx/s。

改進后算法的步驟：

（1）對全體數據集XN 進行維度拆分，拆分成一維數據集Xi（i=1……j），默認分組數量為常數s

（2）取一維數據集作為X1i（i=1……m）進行排序，得到Xs和Xe，并計算得到dx

（3）根據步驟2，得到組間距d，生成分組為s 的直方圖H1，得到直方圖H1峰值Fi1，把峰值后的數據作為新的數據集X2i（i=1……n），重新生成分組為s 的直方圖H2，得到直方圖H2峰值Fi2，以此類推得到K 個峰值

表1：三種數據的聚類性能比較

圖1：iris_sepal length 直方圖統計

圖2：iris_sepal width 直方圖統計

（4）重復進行（2）（3）步驟，得到峰值集合F，取F 相同列得到K 個初始中心點

優化后的K-means 算法一次得到一個峰值，共計算K 步，稱之為階梯K-means 算法。直方圖峰值的搜尋是對密度區間的預估計，通過上述方法得到的初始中心點，大多數是分布于聚類中心位置，遠離聚類集合的邊緣。

4 實驗分析

本篇論文中的數據來自UCI 數據庫的 Iris數據，進行了實驗分析。

UCI 數據庫的數據均為真實數據，常用來檢驗聚類算法的優劣。Iris 數據是鳶尾花的四個屬性，分別是萼片長度（sepal length），萼片寬度（sepal width），花瓣長度（petal length）和花瓣寬度（petal width），分別使用 第1、2 維sepal 數 據，第3、4 維petal 數據和一共四維Iris 數據三組實驗數據。直方圖的分組數為s=9，對于傳統K-means 算法、K-means++算法以及優化后的K-means 算法對上述三種數據進行聚類。聚類迭代次數和聚類正確率是聚類性能指標判斷的標準。由于傳統K-means 算法和k-means++算法隨機選取初始聚類點，每次算法運行的結果有很大的不同，所以仿真150 次，取迭代次數和正確率的平均值。實驗結果如表1所示。

由表1可以很明顯的看出，在Iris 實驗數據上，優化了初始聚類中心點后，迭代次數明顯減少，對于高維度的數據，聚類正確率也有提高。圖1、圖2分別展示了iris sepal 在長度和寬度上的直方圖的繪制情況，其中橫坐標代表irissepal 的長度，縱坐標代表頻數。

5 結束語

本文算法能夠根據給定的K 值，較快的得到初始聚類中心，能夠很有效的減少迭代次數，得到的聚類結果很接近真實數據。在較低維度下迭代次數的減少不是好很明顯，在高維度下能夠很明顯的減少迭代次數，減少復雜運算。從上面的結果看，雖然能夠減少迭代次數，但是在準確率上還是有改進空間。