基于直方圖峰值優(yōu)化的階梯k-means 聚類算法

文/李芝峰 景源

1 引言

K-means 是無監(jiān)督學(xué)習(xí)中最為常用的經(jīng)典算法，也是數(shù)據(jù)挖掘算法中很經(jīng)典的算法之一。K-means 算法和初始聚類中心點(diǎn)的選擇有很大的關(guān)系，合理的初始聚類中心點(diǎn)不僅能夠增加分類的準(zhǔn)確率，而且還能夠減少迭代次數(shù)，縮短運(yùn)算時(shí)間。傳統(tǒng)的K-means 算法原理簡單，但是有一下幾個(gè)四個(gè)缺陷：

（1）傳統(tǒng)算法對于噪音點(diǎn)敏感，對異常點(diǎn)不穩(wěn)定，而且傳統(tǒng)算法比較容易陷入局部最優(yōu)解中，得到的結(jié)果和我們理想的結(jié)果有些差距。

（2）初始聚類中心是隨機(jī)選擇，每次都會(huì)選擇不同的初始聚類中心，算法的計(jì)算效率時(shí)好時(shí)壞。

（3）只能發(fā)現(xiàn)球狀簇規(guī)則的分布。

（4）K-means 算法是屬于無監(jiān)督學(xué)習(xí)算法的一種，K 值需要根據(jù)研究人員的經(jīng)驗(yàn)事先指定，在多種類別混合的數(shù)據(jù)中，不能夠很好的確定分類K 值。

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

2 常用K-means算法介紹

2.1 傳統(tǒng)K-means算法

傳統(tǒng)K-means 算法是一個(gè)無監(jiān)督學(xué)習(xí)，它把數(shù)據(jù)分成若干類，統(tǒng)一類中的數(shù)據(jù)相似性應(yīng)可能的大，不同類中的數(shù)據(jù)的差異性應(yīng)盡可能的大。傳統(tǒng)K-means 算法是在人工指定K值的情況下，隨機(jī)選擇K 個(gè)點(diǎn)作為初始聚類中心。

傳統(tǒng)K-means 算法的步驟分為：

（1）隨機(jī)選取K 個(gè)點(diǎn)，作為K 類的初始聚類中心點(diǎn)，記做C={c1, c2…ck,}

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

（3）分別計(jì)算K 類所有數(shù)據(jù)的中心點(diǎn)，作為該類新的聚類中心

（4）重復(fù)進(jìn)行（2）（3）步驟，直到每一類的聚類中心不再發(fā)生變化

傳統(tǒng)K-means 聚類算法是基于局部最優(yōu)

2.2 K-means++算法

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

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

（1）隨機(jī)選取一個(gè)點(diǎn)，作為初始聚類中心點(diǎn)，記做c1；

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

（4）重復(fù)進(jìn)行（2）（3）步驟，直到選出K 個(gè)聚類中心C={c1,c2…ck,}

K-means++聚類算法還是隨機(jī)第一個(gè)初始聚類中心點(diǎn)，花費(fèi)了額外的時(shí)間來計(jì)算初始聚類中心點(diǎn)，但是減少了迭代的次數(shù)，本身能夠快速的收斂。

3 直方圖峰值優(yōu)化的K-means算法

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

改進(jìn)后算法的步驟：

（1）對全體數(shù)據(jù)集XN 進(jìn)行維度拆分，拆分成一維數(shù)據(jù)集Xi（i=1……j），默認(rèn)分組數(shù)量為常數(shù)s

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

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

表1：三種數(shù)據(jù)的聚類性能比較

圖1：iris_sepal length 直方圖統(tǒng)計(jì)

圖2：iris_sepal width 直方圖統(tǒng)計(jì)

（4）重復(fù)進(jìn)行（2）（3）步驟，得到峰值集合F，取F 相同列得到K 個(gè)初始中心點(diǎn)

優(yōu)化后的K-means 算法一次得到一個(gè)峰值，共計(jì)算K 步，稱之為階梯K-means 算法。直方圖峰值的搜尋是對密度區(qū)間的預(yù)估計(jì)，通過上述方法得到的初始中心點(diǎn)，大多數(shù)是分布于聚類中心位置，遠(yuǎn)離聚類集合的邊緣。

4 實(shí)驗(yàn)分析

本篇論文中的數(shù)據(jù)來自UCI 數(shù)據(jù)庫的 Iris數(shù)據(jù)，進(jìn)行了實(shí)驗(yàn)分析。

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

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

5 結(jié)束語

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