劉建花

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

1 問(wèn)題提出背景

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

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

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

2.1 算法思想

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

算法分以下幾個(gè)步驟：

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

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

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

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

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

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

2.2 算法優(yōu)缺點(diǎn)

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

3 算法改進(jìn)

針對(duì)傳統(tǒng)K-means聚類算法的缺點(diǎn)聚類中心隨機(jī)選取，提出改進(jìn)辦法如下：增加新變量密度的方法確立初始的聚類中心點(diǎn)，密度變量定義是以數(shù)據(jù)值為圓心r為半徑數(shù)據(jù)對(duì)象的總個(gè)數(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中任意取兩個(gè)的數(shù)目.

定義2點(diǎn)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方法：初始兩點(diǎn)：選距離最遠(yuǎn)的兩數(shù)據(jù).

確定第三個(gè)點(diǎn)：與初始兩點(diǎn)的最小距離中選擇大的.

確定第四個(gè)點(diǎn)：與已確定的三個(gè)點(diǎn)的最小距離中選擇最大的.重復(fù)一直選出K個(gè)點(diǎn).

3.2 改進(jìn)后選擇K的算法步驟：

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

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

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

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

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

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

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

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

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

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

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

通過(guò)實(shí)驗(yàn)來(lái)對(duì)比傳統(tǒng)K-means算法和改進(jìn)K-means算法的聚類效果，并對(duì)結(jié)果進(jìn)行統(tǒng)計(jì)與分析，下面的實(shí)驗(yàn)是先將學(xué)校校園網(wǎng)上的熱點(diǎn)話題進(jìn)行聚類然后對(duì)學(xué)校輿情進(jìn)行預(yù)測(cè)和分析.

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

實(shí)驗(yàn)評(píng)價(jià)指標(biāo)采用TDP評(píng)價(jià)標(biāo)準(zhǔn)：

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

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

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

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

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

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

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

表1 實(shí)驗(yàn)結(jié)果對(duì)比

由表1得出F1值對(duì)比圖,如圖1.

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

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

5 總結(jié)

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