K-means聚類算法的改進與應用

劉建花

(晉中師范高等?？茖W校 數(shù)理科學系,山西 晉中 030600)

1 問題提出背景

隨著計算機技術(shù)和網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，我們身邊大量的數(shù)據(jù)不斷生成，如何利用這些數(shù)據(jù)顯得尤為重要，數(shù)據(jù)挖掘就是我們要利用的工具.數(shù)據(jù)挖掘也稱知識發(fā)現(xiàn)，采用科學的方法或手段，為人們從數(shù)據(jù)庫中找出對自己有益信息或感興趣的信息提供幫助.聚類分析屬于數(shù)據(jù)挖掘技術(shù)的一種，在模式識別、圖像處理等領(lǐng)域都有廣泛應用，當中的聚類算法也有很多，如BRICCH，ROCK， DASCAN算法等.

基于K-means聚類算法屬于聚類分析中基于劃分的一種.它具有簡潔高效和收斂性好的特點.K-means聚類算法中對初始聚類中心選擇是非常重要的，選擇不同的中心會造成完全不一樣的聚類結(jié)果.此外在已有條件上分析確定聚類數(shù)目也很重要，事先給定的聚類數(shù)目同預期多多少少會有偏差，傳統(tǒng)的K-means算法的選取中心點是隨機的，如果選的不合適，有可能產(chǎn)生的是局部最優(yōu)解，影響聚類正確性.為了彌補此缺陷，迫切需要對傳統(tǒng)K-means聚類算法通過分析研究進行優(yōu)化.

2 傳統(tǒng)K-means聚類算法

2.1 算法思想

該算法的作用是解決聚類問題，把數(shù)據(jù)集的數(shù)據(jù)對象按照同一簇中的數(shù)據(jù)具有高相似度和與其他簇中的數(shù)據(jù)對象是低相似度劃分條件將數(shù)據(jù)對象歸類到不同的簇中[1].

算法分以下幾個步驟：

第一步：首先輸入n個數(shù)據(jù)對象.

第二步：先確定K，即聚類中簇的個數(shù)，然后從數(shù)據(jù)對象中隨機選擇聚類中心點K個.

第三步：計算其余數(shù)據(jù)對象與K個聚類中心點之間的距離，比較距離并將其歸類到與之距離最近的聚類中心的簇當中.

第四步：通過計算，把K個聚類簇中所有數(shù)據(jù)對象的均值作為新的聚類中心.

第五步：判斷是否滿足收斂條件，滿足則結(jié)束，輸出結(jié)果，否則回到第三步循環(huán)[2].

對K-means聚類算法而言，初始聚類中心的選擇是非常重要的，選擇不同的初始聚類中心會造成完全不一樣的聚類結(jié)果.此外在已有條件上分析確定聚類數(shù)目也很重要，事先給定聚類數(shù)目同預期會有偏差，傳統(tǒng)的K-means算法的選取初始聚類中心點是隨機的，如果選的不合適，不僅會降低算法效率，而且會導致錯誤的結(jié)果.

2.2 算法優(yōu)缺點

該算法優(yōu)點：1)實現(xiàn)簡單；2)效率高；3)輸入數(shù)據(jù)的順序不會對結(jié)果造成影響.缺點：1)聚類集群數(shù)目需提前確定，數(shù)據(jù)分析困難時，比較難確定;2)聚類中心點的隨機選取會影響聚類結(jié)果；3)采用歐式距離的方法適合球狀簇的聚類分析.

3 算法改進

針對傳統(tǒng)K-means聚類算法的缺點聚類中心隨機選取，提出改進辦法如下：增加新變量密度的方法確立初始的聚類中心點，密度變量定義是以數(shù)據(jù)值為圓心r為半徑數(shù)據(jù)對象的總個數(shù)[3].

3.1 定義

定義1領(lǐng)域半徑Eps=Avg(X)=1/(c_n^2)×∑[d(x_i，x_j)],Avg(X)是數(shù)據(jù)集x中所有數(shù)據(jù)距離的平均值，c_n2是n中任意取兩個的數(shù)目.

定義2點x_i密度p(x_i)=∣x_i∣d(x_i，x_j)≤Eps，公式含義是與x_i之間的距離小于Eps的數(shù)據(jù)數(shù).

定義3平均密度Ap(n)=(∑_(i=1)n[p(x_i)])/n

選擇K方法：初始兩點：選距離最遠的兩數(shù)據(jù).

確定第三個點：與初始兩點的最小距離中選擇大的.

確定第四個點：與已確定的三個點的最小距離中選擇最大的.重復一直選出K個點.

3.2 改進后選擇K的算法步驟：

第一步：輸入n個數(shù)據(jù).

第二步：計算數(shù)據(jù)兩兩之間的距離d(x_i，x_j)，組成一個n*n矩陣.

第三步：求出每個數(shù)據(jù)的點密度p(x_i)和平均密度Ap(n)，把所有點密度大于平均密度的數(shù)據(jù)歸到新集合Y中，作為聚類中心的參考點.

第四步：在集合Y中選擇密度最大的對象，標記為y_1，放入集合Z中,Y中刪去y_1.

第五步：在矩陣中找與y_1距離最大的數(shù)據(jù)對象.

第六步：判斷此對象是否在集合Y中，是則標記為y2,放入集合Z中，執(zhí)行第七步，不在，將對應的值從矩陣中刪去,重復執(zhí)行第五步.

第七步：在矩陣中找與Z中數(shù)據(jù)對象最小距離中的最大的.

第八步：根據(jù)上一步求出的數(shù)據(jù)對象判斷是否在Y中，是標記為yj，放入集合Z中，否則循環(huán)到第七步，直到Z中個數(shù)為K.

第九步：將集合Z中的數(shù)據(jù)作為初始聚類中心.

第十步：聚類分析，輸出結(jié)果[4].

4 實驗分析

通過實驗來對比傳統(tǒng)K-means算法和改進K-means算法的聚類效果，并對結(jié)果進行統(tǒng)計與分析，下面的實驗是先將學校校園網(wǎng)上的熱點話題進行聚類然后對學校輿情進行預測和分析.

首先要進行數(shù)據(jù)采集，借助API文本抓取工具，在校園網(wǎng)上的論壇、貼吧、微博等系統(tǒng)上抓取數(shù)據(jù)，接著對抓取的數(shù)據(jù)進行文本去噪后存入數(shù)據(jù)庫，然后利用NLPIR分詞系統(tǒng)進行分詞，停用詞過濾、詞性過濾，刪去介詞、連詞、語氣詞之類的虛詞只留下名詞和動詞，預處理結(jié)束后，為了將文本變?yōu)橛嬎銠C可識別的格式，用于輸入算法中.采用向量空間模型vsm的方法表示文本.

實驗評價指標采用TDP評價標準：

準確率(P)：指正確歸類的樣本數(shù)據(jù)與全部樣本數(shù)據(jù)的比例，P=TP/TP+FP.

召回率(R)指正確歸類的樣本數(shù)據(jù)在全部歸類樣本數(shù)據(jù)中所占比重，R=TP/TP+FN.

準確率和召回率加權(quán)調(diào)和平均(F1)：F1=2PR/(P+R).

TP：事實相關(guān),結(jié)果相關(guān)的文檔.

FP：事實不相關(guān),結(jié)果為相關(guān)的文檔.

FN：事實相關(guān),結(jié)果為不相關(guān)的文檔.

TN：事實不相關(guān)，結(jié)果不相關(guān)的文檔[5].

表1 實驗結(jié)果對比

由表1得出F1值對比圖,如圖1.

改進K-means算法F1值比傳統(tǒng)K-means算法大，F(xiàn)1值高意味著召回率和準確率都比較高.由此得出結(jié)論改進K-means算法聚類效果好.

對結(jié)果再進一步地分析，看出學生感興趣的項目有游戲、晚自習、曠課、美食、戀愛和周邊游.學生對學習方面關(guān)注的太少，今后學校老師應注重學生對待學習態(tài)度的正確引導，學生對待愛情也很迷茫，也要注重學生培養(yǎng)正確的戀愛觀.

5 總結(jié)

本文在傳統(tǒng)K-means算法的基礎(chǔ)上經(jīng)過分析提出增加密度變量方法選取聚類中心的改進方法使算法提高了準確性，避免了孤立點的影響，但仍存在不足：K-means算法的K值確定困難，合適K值的選擇，需要進一步的研究.