機(jī)器學(xué)習(xí)中自適應(yīng)k值的k均值算法改進(jìn)

鐘志峰，李明輝，張 艷

(湖北大學(xué) 計算機(jī)與信息工程學(xué)院，湖北 武漢 430062)

0 引 言

聚類算法[1-4]中的最常用的一種就是k-means算法[5]，該算法最大的特點是簡單、好理解、算法復(fù)雜度低、運算速度快，在處理大規(guī)模數(shù)據(jù)集時可以保持較好的伸縮性和高效性[6]。但是傳統(tǒng)的k-means算法也有很多的缺陷：①k值需要預(yù)先確定，但在實際中這個k值的選定是非常難以估計的，若k值過大，則類與類之間的相似度太小，若k值過小，則類與類之間的相似度過大，這兩種情況都會導(dǎo)致聚類結(jié)果不準(zhǔn)確[7]；②k-means算法中相似度是以歐氏距離來度量的，因此遠(yuǎn)離群點的存在對算法結(jié)果影響較大[8]。文獻(xiàn)[9]提出一種改進(jìn)k-means算法DMk-means(density mathematics k-means)，選取給定鄰域范圍內(nèi)最近鄰數(shù)據(jù)點最多的點為初始中心點，可以有效排除遠(yuǎn)離群點對初始聚類的干擾，但是對于高維數(shù)據(jù)集效果不佳。文獻(xiàn)[10]提出了一種以熱擴(kuò)散的方法來找到數(shù)據(jù)集的密度峰值，從而發(fā)現(xiàn)數(shù)據(jù)集的聚類中心，雖然提高了聚類效果，但比較復(fù)雜。文獻(xiàn)[11]提出了用最大距離法選取初始簇中心，使初始簇中心具有很強的區(qū)分性，但是初始時可能選取遠(yuǎn)離群點作為中心點。在分析已有的k-means改進(jìn)算法的基礎(chǔ)上，引進(jìn)肘部法則的思想對數(shù)據(jù)進(jìn)行優(yōu)化處理，找出遠(yuǎn)離群點；引入自適應(yīng)思想并結(jié)合誤差平方和SSE自動調(diào)整k值。結(jié)合這幾種方法提出一種自適應(yīng)調(diào)整k值的k-means改進(jìn)算法。最后還與傳統(tǒng)k-means算法進(jìn)行了實驗對比，實驗結(jié)果表明改進(jìn)后的k-means算法在準(zhǔn)確性上和聚類效果上更優(yōu)。

1 k-means算法改進(jìn)

眾所周知，k-means算法雖然原理非常簡單，但是應(yīng)用非常廣泛。而 k-means算法中相似度是以歐氏距離來度量的，因此遠(yuǎn)離群點的存在對算法結(jié)果影響較大。這些缺陷同時也限制了k-means算法的應(yīng)用。因此上述缺陷的研究是重點。

1.1 根據(jù)“肘部法則”的思想對遠(yuǎn)離群點的改進(jìn)

由于傳統(tǒng)的k-means算法相似度的判定是基于歐氏距離，所以遠(yuǎn)離群會增大對k值的估計值，增加算法的時間復(fù)雜度[12]。為了更加有效地檢測出數(shù)據(jù)集中的遠(yuǎn)離群點，從而解決遠(yuǎn)離群點對k-means算法的影響,從肘部法則得到啟發(fā)，根據(jù)其思想找出遠(yuǎn)離群點，從而達(dá)到對算法改進(jìn)的目的。具體實現(xiàn)如下：

設(shè)聚類樣本數(shù)據(jù)集為X={xi|i=1，2，…，m}，m為樣本數(shù)據(jù)個數(shù)，其中每個樣本數(shù)據(jù)均有n個特征(n>0)；將樣本數(shù)據(jù)劃分為不同的類別(簇)C={c1，c2，…，ck}，k為聚類的個數(shù)。

初始時，對樣本數(shù)據(jù)集進(jìn)行優(yōu)化處理：將樣本數(shù)據(jù)集X中所有的樣本數(shù)據(jù)當(dāng)成一個簇，則：

簇中心點

(1)

其中，Cj表示第j個簇所包含的樣本數(shù)據(jù)集合，N(Cj) 表示第j個簇中樣本數(shù)據(jù)點的個數(shù)。

計算出X中各個樣本數(shù)據(jù)點到簇中心點μj的歐氏距離集D，具體公式如下

(2)

其中，xi表示第i個樣本數(shù)據(jù)點 (1≤i≤m)。

則D={d1，d2，…，dm}， 根據(jù)“肘部法則”的思想，將D中的數(shù)據(jù)按照小到大排序并得到x-d二維折線圖(d為樣本數(shù)據(jù)點到中心點的距離，x為與d對應(yīng)的樣本數(shù)據(jù)點)，距離d增大過程中，畸變程度的改善效果上升幅度最大的位置對應(yīng)的值就是“肘部”，即“肘部”處滿足

Δd=max(di-di-1) (1

(3)

在“肘部”處進(jìn)行劃分(一般設(shè)“肘部”之后對應(yīng)的數(shù)據(jù)點個數(shù)一般占數(shù)據(jù)集個數(shù)的0%～10%)，將距離大于“肘部”點對應(yīng)距離的數(shù)據(jù)點暫時定義為遠(yuǎn)離群點。假設(shè)剔除遠(yuǎn)離群點后還有w個樣本數(shù)據(jù)點(w≦m)，則遠(yuǎn)離群點還有(m-w)個，將非遠(yuǎn)離群點存放于數(shù)據(jù)集X’中，并將數(shù)據(jù)點重新編號，即X’={x1，x2，…，xw}。 將遠(yuǎn)離群點存放于數(shù)據(jù)集Y中，并將數(shù)據(jù)點重新編號,即Y={xw+1，xw+2，…，xm}。 在算法過程中使用的數(shù)據(jù)集剔除Y中的數(shù)據(jù)點，即新的樣本數(shù)據(jù)集X’，在算法過程中使用X’數(shù)據(jù)集進(jìn)行聚類則可以在一定程度上消除遠(yuǎn)離群點的影響。

算法完成后簇劃分為C={c1，c2，…，cz} (z為簇的個數(shù)(算法完成后自適應(yīng)k值可能會改變))，設(shè)第j個簇中簇內(nèi)數(shù)據(jù)點到簇中心點的最大距離為maxdj

maxdj=max{dj1,dj2,dj3,…}

(4)

遍歷Y中的數(shù)據(jù)點xw+1，xw+2，…，xm，根據(jù)式(2)計算Y中數(shù)據(jù)點到各個簇中心點的距離 {(d(w+1)1，d(w+1)2，…，d(w+1)z)，(d(w+2)1，d(w+2)2，…，d(w+2)z)，…，(dm1，dm2，…，dmz)} (Y中的所有數(shù)據(jù)點到z個簇的歐氏距離的集合)。若存在第a個簇 (a∈(0，z])， 使集合Y中的數(shù)據(jù)點xb(b∈[w+1，m]) 滿足xb點到a個簇中心點的距離小于該簇中數(shù)據(jù)點到簇中心點的最大距離，即： (db1

則將xb劃分到a個簇中距離它最近的簇

j(xb)=min(db1,db2,…,dba)

(5)

若不存在這樣的簇，則將該點定義為遠(yuǎn)離群點。直到Y(jié)中所有的數(shù)據(jù)點遍歷完成，即可劃分出最終的遠(yuǎn)離群點。

1.2 根據(jù)自適應(yīng)的思想對k值選取的改進(jìn)

k-means聚類算法屬于非監(jiān)督的學(xué)習(xí)方法，傳統(tǒng) k-means 算法選取初始聚類中心是根據(jù)自身經(jīng)驗，而對初始聚類中心選取的優(yōu)化也會引入一定的參數(shù)，也會使聚類結(jié)果缺乏客觀性[13]。引入自適應(yīng)的思想提出一種自動調(diào)整k值的方法。具體實現(xiàn)如下：

聚類評估指標(biāo)：聚類評估指標(biāo)有多種多樣，選擇簇內(nèi)誤差平方和SSE，后文可以根據(jù)SSE得出單個簇內(nèi)聚類評估指標(biāo)Je，SSE計算公式如下

(6)

其中，k表示簇的個數(shù)，x表示樣本數(shù)據(jù)點，μj表示第j個簇的簇中心點，Cj表示第j個簇所包含的樣本數(shù)據(jù)集合。E為k-means算法根據(jù)樣本X’聚類得到的簇C劃分的平均誤差平方和，在一定程度上描述了各個簇樣本的緊密程度，通常E越小說明聚類效果越好。

由聚類評估指標(biāo)誤差平方和SSE得單個簇內(nèi)誤差平方和Je，公式如下

(7)

其中，xi為第j個簇中的簇內(nèi)數(shù)據(jù)點，N(Cj)表示第j個簇中樣本數(shù)據(jù)點的個數(shù)，μj為第j個簇的簇中心點。在一定程度上描述了簇內(nèi)數(shù)據(jù)的緊密程度，通常Jej越小說明第j個簇的簇內(nèi)聚類效果越好。

初始時設(shè)定簇內(nèi)聚類評估指標(biāo)Je和簇內(nèi)最小數(shù)據(jù)點個數(shù)的閾值N。在各個簇劃分完成之后，可以得到各個簇的簇內(nèi)數(shù)據(jù)點的個數(shù) (N1，N2，…，Nk)； 可以對各個簇根據(jù)式(7)進(jìn)行簇內(nèi)聚類評估，得到各簇的聚類評估值 (Je1，Je2，…，Jek)。 然后計算出第j個簇聚類評估指標(biāo)的誤差ΔJej和簇內(nèi)數(shù)據(jù)點個數(shù)與初值的差值ΔNj，具體公式如下

ΔJej=Jej-b

(8)

ΔNj=Nj-N

(9)

結(jié)合式(8)、式(9)得出第j個簇中k值變化量

(10)

其中，w為數(shù)據(jù)集X’中樣本數(shù)據(jù)點的個數(shù)，“sgn()”為符號函數(shù)，“θ()”為單位階躍函數(shù)，“∏”符號為向上取整。

(1)當(dāng)Jej>b時，則ΔJej為正數(shù)，單位階躍函數(shù)θ(ΔJej)=1， 所以Δkj=Π(logm(ΔJej+1))， 即Δkj>0，即需要在第j個簇中心點附近新增簇中心點來減小簇內(nèi)誤差評估指標(biāo)。一般0

(2)當(dāng)Jej

遍歷各個簇后，根據(jù)式(10)得出k值的變化量 (Δk1，Δk2，…，Δkk)， 則更新的k值k’為

(11)

若k’===k， 則終止循環(huán)(“===”符號為絕對等于，要求k’與k在數(shù)值上和簇中心點位置上都相同)；

若k’≠k，則繼續(xù)循環(huán)下去(“≠”要求k’與k在數(shù)值上或位置上不相同即可)。

注意：若更新后的k’值與原來的k值在數(shù)值上相同，但是簇中心點的位置改變，仍需繼續(xù)迭代下去。

1.3 改進(jìn)后的算法流程

基于以上兩點改進(jìn)提出一種基于“肘部法則”和自適應(yīng)調(diào)整k值的k-means改進(jìn)算法。該算法的基本思想是：通過“肘部法則”的思想對樣本數(shù)據(jù)集X進(jìn)行優(yōu)化處理，確定暫時的遠(yuǎn)離群點，算法過程中使用剔除暫時的遠(yuǎn)離群點的樣本數(shù)據(jù)集，并在算法完成后根據(jù)暫時的遠(yuǎn)離群點與各個簇間的相似度，確定最終的遠(yuǎn)離群點；通過自適應(yīng)的思想，在每次迭代完成之后，根據(jù)各個簇的簇內(nèi)聚類評估指標(biāo)的誤差來自動調(diào)整k值，直到滿足誤差范圍。

算法改進(jìn)算法流程如圖1所示。

圖1 改進(jìn)算法流程

算法改進(jìn)算法流程如下：

步驟1 數(shù)據(jù)優(yōu)化處理，根據(jù)“肘部法則”的思想找出暫時的遠(yuǎn)離群點并存放在數(shù)據(jù)集集Y中，得到數(shù)據(jù)優(yōu)處理化后新的樣本數(shù)據(jù)集X′={x1，x2，…，xi，…，xw} (具體參考1.1)；

步驟2 設(shè)定單個簇內(nèi)評估指標(biāo)Je和簇內(nèi)最小數(shù)據(jù)點個數(shù)N的閾值范圍；

步驟3 在w個樣本數(shù)據(jù)中，隨機(jī)選取k個樣本作為初始聚類中心 (1

步驟4 根據(jù)式(2)計算剩余每個樣本數(shù)據(jù)到聚類中心的歐式距離，并將每個樣本劃分到距離它最近的簇中；

步驟5 按照式(1)重新計算各個簇的新的簇中心點；

步驟6 若新的簇中心點與原來的中心點相同或者小于某個閾值(收斂定義參考文獻(xiàn)[14])，則至步驟7；若新的簇中心點發(fā)生改變，則繼續(xù)重復(fù)步驟4、步驟5直到收斂；

步驟7 計算各個簇中的簇內(nèi)聚類評估Jej和各個簇中數(shù)據(jù)點的個數(shù)Nj。將Jej和Nj與初始設(shè)定的閾值范圍比較，根據(jù)式(10)計算出Δkj。遍歷所有的簇后，根據(jù)式(11)計算出新的k值k’，若有中心點被刪除或新增加，則返回步驟4，直到不再有新增或刪除的簇中心點(具體參考1.2)；

步驟8 根據(jù)數(shù)據(jù)集Y中的數(shù)據(jù)點與各個簇的簇中心點的相似度大小來確定最終劃分的遠(yuǎn)離群點(具體參考1.1)；

步驟9 輸出最終的簇劃分C={c1，c2，…，cz}。

2 實驗分析

2.1 實驗數(shù)據(jù)

這里可以直接調(diào)用Python中的sklearn模塊[15]，其中包含toy數(shù)據(jù)集和圖像樣本數(shù)據(jù)集，toy數(shù)據(jù)集由一些小批量經(jīng)典數(shù)據(jù)集組成，如鳶尾花數(shù)據(jù)、手寫字符數(shù)據(jù)、糖尿病數(shù)據(jù)集、波士頓房價數(shù)據(jù)、健身數(shù)據(jù)集等等；圖像樣本數(shù)據(jù)集由一些小批量經(jīng)典圖像或者模型數(shù)據(jù)組成，如半環(huán)形數(shù)據(jù)集、圓形數(shù)據(jù)集、聚類模型隨機(jī)數(shù)據(jù)集、分類模型隨機(jī)數(shù)據(jù)集、高斯模型隨機(jī)數(shù)據(jù)集、回歸模型隨機(jī)數(shù)據(jù)集等等。采用的是聚類模型隨機(jī)數(shù)據(jù)集(make_blobs)來進(jìn)行驗證，見表1。

表1 實驗數(shù)據(jù)

2.2 實驗結(jié)果與分析

如圖2～圖10所示，圖2～圖4分別為聚類模型隨機(jī)數(shù)據(jù)集個數(shù)為20、30和50，由傳統(tǒng)的k-means算法和“肘部法則”結(jié)合得出的K-SSE折線圖；圖5～圖7分別為聚類模型隨機(jī)數(shù)據(jù)集個數(shù)為20、30和50，由傳統(tǒng)的k-means算法得出的聚類結(jié)果；圖8～圖10分別為聚類模型隨機(jī)數(shù)據(jù)集個數(shù)為20、30和50，由改進(jìn)的k-means算法得出的聚類結(jié)果。圖2、圖3和圖4是根據(jù)肘部法則得出最合適的k值(由圖可知k=4最佳)。對比相同數(shù)據(jù)情況下由改進(jìn)的 k-means 算法根據(jù)自適應(yīng)調(diào)整k值得出的聚類結(jié)果圖8～圖10，與圖2～圖4中的k值相同，表明這種自適應(yīng)k值方法可行。

圖2 K-SSE(blobs20)

圖3 K-SSE(blobs30)

圖4 K-SSE(blobs50)

圖5～圖7和圖8～圖10均是在k值相同的基礎(chǔ)上得到的，即在改進(jìn)的k-means算法自適應(yīng)得出k值之后，再由相同的k值得出傳統(tǒng)的k-means算法實驗結(jié)果，可以使實驗對比更加鮮明、實驗結(jié)果更加準(zhǔn)確。對比聚類模型隨機(jī)數(shù)據(jù)集且數(shù)據(jù)集個數(shù)均相同的實驗結(jié)果圖5和圖8，可以看出圖8中比圖5中多出了兩個遠(yuǎn)離群點(圖中的singular，菱形點)，而且簇中心點也有一定的變化，圖8中左邊兩個簇剔除遠(yuǎn)離群點后，各個簇中的數(shù)據(jù)更加緊密，聚類效果更優(yōu)。類似地，圖9和圖10中的簇中心點也有變化，也剔除了遠(yuǎn)離群點，明顯的改進(jìn)后的算法聚類后的簇聚合顯得更加密集，即改進(jìn)后的k-means算法的聚類效果比傳統(tǒng)的k-means算法更好。

圖5 k-means(blobs20)

圖6 k-means(blobs30)

圖7 k-means(blobs50)

圖8 改進(jìn)k-means(blobs20)

圖9 改進(jìn)k-means(blobs30)

圖10 改進(jìn)k-means(blobs50)

圖11是由傳統(tǒng)k-means算法和改進(jìn)后的k-means算法在相同數(shù)據(jù)集—聚類模型隨機(jī)數(shù)據(jù)集blobs，經(jīng)聚類評估指標(biāo)SSE得出聚類評估指標(biāo)的對比。圖11中可以看出改進(jìn)后的k-means算法SSE數(shù)據(jù)都要小于傳統(tǒng)的k-means算法，其主要原因是剔除了遠(yuǎn)離群點對聚類效果的影響，使得各個簇中的數(shù)據(jù)集之間聚合更加密集，說明了改進(jìn)后的 k-means 算法聚類更好。

圖11 blobs數(shù)據(jù)集聚類評估對比

3 結(jié)束語

主要是通過研究k-means算法的兩個缺陷——對于遠(yuǎn)離群點特別敏感和k值需要預(yù)先確定，在分析已有的k-means改進(jìn)算法的基礎(chǔ)上，對傳統(tǒng)的k-means算法進(jìn)行改進(jìn)，主要包括對遠(yuǎn)離群點的處理和自適應(yīng)的調(diào)整k值。并且通過Python中的sklearn模塊提供的真實數(shù)據(jù)集—聚類模型隨機(jī)數(shù)據(jù)集進(jìn)行實驗，并將實驗結(jié)果與傳統(tǒng)的k-means實驗結(jié)果相比較，結(jié)果表明改進(jìn)后的k-means算法中的剔除遠(yuǎn)離群點自適應(yīng)調(diào)整k值的方法均可行，而且在準(zhǔn)確性和聚類效果上有明顯的優(yōu)勢。不足的是，簇內(nèi)聚類評估指標(biāo)Je和簇內(nèi)最小數(shù)據(jù)點個數(shù)的閾值N需要根據(jù)經(jīng)驗設(shè)定，而且改進(jìn)的算法在循環(huán)中嵌套了循環(huán)，大大的提高了算法的迭代次數(shù)和算法的時間復(fù)雜度，對于大量數(shù)據(jù)的聚類消耗的時間可能過長，需要對數(shù)據(jù)進(jìn)行降維等數(shù)據(jù)優(yōu)化處理，希望以后能夠進(jìn)一步優(yōu)化。