陳 敏，余曉平*，左文英

(1.石河子大學(xué)信息科學(xué)與技術(shù)學(xué)院，新疆 石河子832000;2.上海石化工業(yè)學(xué)校，上海201512)

0 引 言

隨著人們對(duì)數(shù)據(jù)挖掘的深入研究和算法的應(yīng)用過(guò)程中，人們發(fā)現(xiàn)針對(duì)不同的應(yīng)用范圍和領(lǐng)域需要的算法不同，某些算法可能在某些數(shù)據(jù)的可行性、效率、精度或簡(jiǎn)單性上具有一定的優(yōu)勢(shì)，但當(dāng)數(shù)據(jù)類(lèi)型轉(zhuǎn)變或者應(yīng)用領(lǐng)域不同，可能這種算法就不一定有優(yōu)勢(shì)了.所以，在使用算法之前我們需要對(duì)算法的優(yōu)缺點(diǎn)和應(yīng)用領(lǐng)域有一定了解，根據(jù)具體的情況選取合適的算法進(jìn)行數(shù)據(jù)挖掘.

1 K－means 的算法分析

K－means 算法是數(shù)據(jù)挖掘技術(shù)中一種經(jīng)典的基于劃分的聚類(lèi)算法，由于該算法的理論嚴(yán)謹(jǐn)、算法簡(jiǎn)單，并且收斂速度快而被廣泛使用［1］.Kmeans 算法采用的是迭代更新的思想，首先在數(shù)據(jù)集合中隨機(jī)地選擇k 個(gè)對(duì)象作為初始點(diǎn)來(lái)代表聚類(lèi)或簇的中心，然后再根據(jù)"就近原則"對(duì)剩余的每個(gè)對(duì)象與各個(gè)簇的中心的距離將它重新賦給最近的簇，分配完畢后，重新計(jì)算每個(gè)簇的中心作為下一次迭代的聚類(lèi)中心，再次進(jìn)行所有對(duì)象的分配，不斷重復(fù)這個(gè)計(jì)算簇中心后分配各對(duì)象的過(guò)程直到各聚類(lèi)中心不再變化時(shí)終止［2］.迭代使得選取的聚類(lèi)中心越來(lái)越接近真實(shí)的簇中心，所以聚類(lèi)效果越來(lái)越好，最后把所有對(duì)象劃分為k 個(gè)簇.

K－means 算法的具體步驟［3］:

輸出:k 個(gè)簇{s1，s2，…，sk}目標(biāo)函數(shù)最小.

(1)聚類(lèi)個(gè)數(shù)k;

(2)從數(shù)據(jù)集中隨機(jī)選定k 個(gè)對(duì)象作為初始聚類(lèi)中心c1，c2，…，ck;

(3)逐個(gè)將對(duì)象xi(i=l，2，...，n)按歐式距離分配給距離最近的一個(gè)聚類(lèi)中心cj，1 ＜j ＜k

其中m 是數(shù)據(jù)屬性的個(gè)數(shù);

(4)計(jì)算各個(gè)聚類(lèi)新的中心Cj

其中Nj是第j 個(gè)聚類(lèi)sj中所包含的對(duì)象個(gè)數(shù).

《中等職業(yè)學(xué)校語(yǔ)文教學(xué)大綱》中提出語(yǔ)文課程的目標(biāo)是掌握日常生活和職業(yè)崗位需要的語(yǔ)文能力。這種能力是指能適應(yīng)生活需要的、整合的、具有可持續(xù)發(fā)展前景的能力。要培養(yǎng)這種能力，必須將教育與生活緊密相連。因此在課堂教學(xué)中應(yīng)將教學(xué)活動(dòng)置于現(xiàn)實(shí)的生活背景之中，從而激發(fā)學(xué)生作為生活主體參與活動(dòng)的強(qiáng)烈愿望，同時(shí)將教學(xué)的目的要求轉(zhuǎn)化為學(xué)生作為生活主體的內(nèi)在需要，讓他們?cè)谏钪袑W(xué)習(xí)，在學(xué)習(xí)中更好地生活，從而獲得有活力的知識(shí)，并使情操得到真正的陶冶。

(5)如果聚類(lèi)中心不再變化，目標(biāo)函數(shù)最小，算法終止，否則轉(zhuǎn)步驟3.

K－means 算法的流程圖如圖1 所示.

2 改進(jìn)的K－means 聚類(lèi)算法

改進(jìn)的K－means 主要能夠根據(jù)對(duì)象間的相異度，基于歐氏距離度量的方法得出較為合適的聚類(lèi)參數(shù)K 值.改進(jìn)后算法的具體流程如圖2 所示.

算法的開(kāi)始需要從數(shù)據(jù)集合中選出距離最遠(yuǎn)的兩個(gè)數(shù)據(jù)對(duì)象，傳統(tǒng)的算法需要比較兩兩之間的距離，效率較為低下，針對(duì)這些不足，本文給出了另一種計(jì)算方法，首先計(jì)算出數(shù)據(jù)集中所有的邊界點(diǎn)，即對(duì)于每一維來(lái)說(shuō)找出最大值和最小值，然后找到數(shù)據(jù)集中所對(duì)應(yīng)的每一個(gè)數(shù)據(jù)點(diǎn)，相對(duì)于數(shù)據(jù)量大的數(shù)據(jù)集來(lái)說(shuō)，邊界點(diǎn)的數(shù)量會(huì)顯得少很多，如此以來(lái)數(shù)據(jù)的處理量會(huì)大量的減少.步驟實(shí)施過(guò)程的詳細(xì)描述如下:

(1)針對(duì)一個(gè)數(shù)據(jù)集Sn= {X1，X2，X3，…，Xn}，其中包含了n 個(gè)數(shù)據(jù)對(duì)象，首先從數(shù)據(jù)集Sn中找出所有邊界點(diǎn)，組成一個(gè)小的數(shù)據(jù)集，再?gòu)倪吔琰c(diǎn)的數(shù)據(jù)集中找出距離最遠(yuǎn)的兩個(gè)點(diǎn)作為初始的聚類(lèi)中心，即C1和C2.

(2)將數(shù)據(jù)集中的每一個(gè)對(duì)象Xi分別計(jì)算出到上述兩個(gè)初始聚類(lèi)中心的歐式距離di，根據(jù)就近原則，即為Xi到聚類(lèi)中心距離值小的點(diǎn)Min(di)，將給數(shù)據(jù)點(diǎn)劃分為該聚類(lèi)中心，從而將所有的數(shù)據(jù)點(diǎn)劃分成為以C1和C2為中心的兩大類(lèi).同時(shí)，在將所有節(jié)點(diǎn)分配到各個(gè)簇中心節(jié)點(diǎn)時(shí)，如果出現(xiàn)某一個(gè)簇心只有它自身一個(gè)節(jié)點(diǎn)，則將該節(jié)點(diǎn)列入孤立點(diǎn)，不作為簇中心出現(xiàn).

圖1 K－means 算法的流程圖

(3)計(jì)算出以上兩大類(lèi)中所有數(shù)據(jù)點(diǎn)距離中心點(diǎn)的最大距離，即為Max(di)，同時(shí)查找出該數(shù)據(jù)點(diǎn)Xj.

(4)檢驗(yàn)該數(shù)據(jù)點(diǎn)Xj能否成為下一個(gè)聚類(lèi)中心點(diǎn)C3.如果可以則轉(zhuǎn)入步驟2 中繼續(xù)聚類(lèi)，然后找下一個(gè)聚類(lèi)中心點(diǎn)C4，C5…等，一直到找不出滿足條件的中心點(diǎn)為止，否則，得出該數(shù)據(jù)集Sn的聚類(lèi)個(gè)數(shù)K 值.

圖2 改進(jìn)K－means 算法的基本流程

這里需要重點(diǎn)分析的是距離已有中心點(diǎn)距離最遠(yuǎn)的一個(gè)點(diǎn)Xj成為聚類(lèi)中心點(diǎn)的判定，如果Xj到其所在中心的距離為dj，且dj得值為各個(gè)聚類(lèi)中心點(diǎn)平均距離的大于等于0.5［4］，并且小于1，文獻(xiàn)中參數(shù)的經(jīng)驗(yàn)值一般取為0.5，則該點(diǎn)Xj可獨(dú)立成為一個(gè)中心聚點(diǎn).避免了將距離某一個(gè)已有的聚類(lèi)中心比較臨近而離其它聚類(lèi)中心都遠(yuǎn)的點(diǎn)作為侯選對(duì)象的可能.因此，采用該算法可以保證每次取到的新的聚類(lèi)中心離已有的聚類(lèi)中心的距離都比較遠(yuǎn).而且該算法不需要預(yù)先給出聚類(lèi)個(gè)數(shù)，它可以根據(jù)一定的計(jì)算規(guī)則自動(dòng)地確定初始聚類(lèi)中心的個(gè)數(shù).該算法的偽代碼如下:

3 改進(jìn)算法與K－means 算法性能對(duì)比

為了評(píng)價(jià)改進(jìn)后的K－means 算法與Kmeans 算法的優(yōu)良，采用了IRIS 數(shù)據(jù)集作為測(cè)試數(shù)據(jù)，通過(guò)大量的聚類(lèi)算法實(shí)驗(yàn)已經(jīng)證明，IRIS 數(shù)據(jù)集對(duì)測(cè)試聚類(lèi)算法中的K－means 算法有很好的驗(yàn)證效果，所以該數(shù)據(jù)集經(jīng)常被用作檢驗(yàn)聚類(lèi)算法的性能的標(biāo)準(zhǔn)數(shù)據(jù).IRIS 數(shù)據(jù)集即為鳶尾花數(shù)據(jù)集，該數(shù)據(jù)集可以從加州大學(xué)厄文分校的(UCI)的機(jī)器學(xué)習(xí)庫(kù)中得到.鳶尾花數(shù)據(jù)集包含150 種鳶尾花的信息，每50 種取自三個(gè)鳶尾花種之一:Setosa、Versicolour 和Virginica.每個(gè)花的特征用下面5 種屬性描述:萼片長(zhǎng)度(厘米)、萼片寬度(厘米)、花瓣長(zhǎng)度(厘米)、花瓣寬度(厘米)和類(lèi)(Setosa，Versicolour，Virginica)，在這些樣本中的Setosa 樣本與其它兩類(lèi)間是完全分離，而在Versicolor 樣本和Virginica 樣本間有部分的數(shù)據(jù)交叉.

圖3 改進(jìn)前后算法正確率比較圖

圖4 K－means 聚類(lèi)正確率分布圖

IRIS 數(shù)據(jù)集共有5 個(gè)屬性集和150 個(gè)樣本數(shù)據(jù)，一方面在屬性方面既不至于過(guò)于繁瑣，另一方面又保證了一定的數(shù)據(jù)量和代表性，并且Hathaway(1995)給出的IRIS 數(shù)據(jù)的每一類(lèi)的實(shí)際類(lèi)中心位置:Setosa 類(lèi)為(5.00，3.42，1.46，0.24)，Versicolour 類(lèi)為(5.93，2.77，4.26，1.32)和Virginica 類(lèi)為(6.58，2.97，5.55，2.02)，有了這些明確的數(shù)據(jù)對(duì)我們測(cè)試新算法進(jìn)行參數(shù)的比對(duì)很有幫助.實(shí)驗(yàn)結(jié)果和對(duì)比分析

(1)聚類(lèi)個(gè)數(shù)的比較

由于IRIS 數(shù)據(jù)集每50 個(gè)對(duì)象為一類(lèi)，所以在取樣本集時(shí)考慮到每一類(lèi)均衡將實(shí)驗(yàn)數(shù)據(jù)集劃分為6 次樣本集，樣本集1 為IRIS 數(shù)據(jù)集中序號(hào)為偶數(shù)的數(shù)據(jù)共75 條，樣本集2 為IRIS 數(shù)據(jù)集中序號(hào)為奇數(shù)的數(shù)據(jù)共75 條，樣本集3 為IRIS 數(shù)據(jù)集中序號(hào)不能整除3 后數(shù)據(jù)共100 條，樣本集4 為IRIS 數(shù)據(jù)集中刪除序號(hào)不能整除4 的數(shù)據(jù)共113條，樣本集5 為IRIS 數(shù)據(jù)集中序號(hào)不能整除5 的數(shù)據(jù)共120 條，樣本集6 為IRIS 數(shù)據(jù)集共150 條.這6 個(gè)樣本集覆蓋了數(shù)據(jù)集中的所有數(shù)據(jù)，實(shí)驗(yàn)過(guò)程中分別用K－means 算法和改進(jìn)后算法進(jìn)行了實(shí)驗(yàn).

經(jīng)典的K－means 算法需要事先用戶指定好聚類(lèi)個(gè)參數(shù)K 值，根據(jù)用戶指定的K 參數(shù)可以得到不同的聚類(lèi)，這里根據(jù)聚類(lèi)的經(jīng)驗(yàn)對(duì)IRIS 數(shù)據(jù)集進(jìn)行K 值的設(shè)定，測(cè)試聚類(lèi)分別將聚類(lèi)K 值設(shè)定為2、3、4 和5，然后通過(guò)對(duì)6 個(gè)樣本執(zhí)行不同的K 值后，聚類(lèi)后的Setosa、Versicolour 和Virginica 三類(lèi)的正確率各不相同，算法的執(zhí)行聚類(lèi)結(jié)果如表1所示:

表1 改進(jìn)后K－means 聚類(lèi)結(jié)果

通過(guò)以上的樣本測(cè)試，正確率因聚類(lèi)K 值不同而不同，通過(guò)求平均值得出以下每個(gè)K 值對(duì)應(yīng)的平均正確率如表2 所示.由此可以看出，當(dāng)K 取值為3 時(shí)正確率為最高，所以在K－means 算法過(guò)程中如何確定合適的K 值對(duì)于用戶來(lái)說(shuō)是一個(gè)較為難解決的問(wèn)題.

表2 K－means 算法平均正確率表

這里對(duì)改進(jìn)后的K－means 算法也進(jìn)行同一個(gè)數(shù)據(jù)集的測(cè)試，由于改進(jìn)后的算法是由程序自動(dòng)生成合適的K 值，所以這里不需要進(jìn)行輸入，并且當(dāng)程序首先找出邊界點(diǎn)時(shí)，得到共有14 條記錄屬于邊界點(diǎn)內(nèi)，這樣效率遠(yuǎn)遠(yuǎn)高于求150 個(gè)數(shù)據(jù)對(duì)象之間的距離.改進(jìn)后的K－means 算法在運(yùn)行時(shí)驗(yàn)證參數(shù)值的范圍介于0.45 與0.55 之間，6 個(gè)樣本的程序結(jié)果均顯示自動(dòng)生成了3 簇，而IRIS 數(shù)據(jù)集的最佳聚類(lèi)結(jié)果也是3 簇，具體的結(jié)果如表1－3 所示，這首先保證了K 值與標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)的一致性，并且在6 個(gè)樣本中首先對(duì)于Setosa 樣本中的50 條記錄能保證100%的正確率，對(duì)Versicolour 類(lèi)的正確率也達(dá)到99%，Virginica 和Versicolour 類(lèi)部分?jǐn)?shù)據(jù)本身就有交叉，所以在Virginica 類(lèi)的正確率低.

表3 改進(jìn)聚類(lèi)結(jié)果

樣本1 25 0 100% 25 0 100% 15 10 60%樣本2 25 0 100% 25 0 100% 16 9 64%樣本3 33 0 100% 32 1 97% 20 14 59%3 樣本4 37 0 100% 37 1 97% 24 14 63%樣本5 40 0 100% 40 0 100% 22 18 55%樣本6 50 0 100% 50 0 100% 28 22 56%

通過(guò)計(jì)算得到改進(jìn)K－means 算法的平均正確率為86.17%，高于K－means 算法中最高的正確率83.67%.根據(jù)算法改進(jìn)前后的正確率對(duì)比圖3 ～7 我們能夠很明顯的看出，K－means 算法的正確率首先波動(dòng)很大，樣本結(jié)果出現(xiàn)正確率不穩(wěn)定，最低的正確率是56%.因?yàn)楫?dāng)初始點(diǎn)的隨機(jī)產(chǎn)生對(duì)聚類(lèi)的結(jié)果影響很大，如果初始點(diǎn)隨機(jī)都產(chǎn)生的距離很近或者在一個(gè)簇中，聚類(lèi)的結(jié)果不僅迭代次數(shù)多，同時(shí)分類(lèi)的結(jié)果也產(chǎn)生很大的差異.而改進(jìn)后的算法正確率波動(dòng)范圍比較小.對(duì)于6 個(gè)樣本正確率都相當(dāng)，比對(duì)后得出改進(jìn)后的算法不僅能自動(dòng)得出生成合適的聚簇個(gè)數(shù)，同時(shí)聚類(lèi)的正確率也高于經(jīng)典的K－means 算法，如圖3 所示.

(2)對(duì)于孤立點(diǎn)和噪聲的比較

由于K－means 算法對(duì)于噪聲和孤立點(diǎn)的數(shù)據(jù)很敏感，這些孤立點(diǎn)和噪聲會(huì)對(duì)計(jì)算平均值產(chǎn)生巨大的影響，造成平均值有很大的偏離，所以在改進(jìn)的K－means 算法中對(duì)孤立點(diǎn)和噪聲進(jìn)行了改造，當(dāng)數(shù)據(jù)庫(kù)掃描完畢后，如果聚簇結(jié)果中出現(xiàn)了孤立點(diǎn)，則將該數(shù)據(jù)點(diǎn)剔除后繼續(xù)掃描庫(kù).這里為了檢驗(yàn)兩種算法對(duì)孤立點(diǎn)的敏感性，仍然使用原有的IRIS 數(shù)據(jù)集，在數(shù)據(jù)集中加入一條記錄萼片長(zhǎng)度、萼片寬度、花瓣長(zhǎng)度和花瓣寬度均為15，K 值仍然為3.由于K－means 算法首先隨機(jī)取K 個(gè)對(duì)象生成了簇中心，所以在測(cè)試時(shí)候?yàn)榱私Y(jié)果準(zhǔn)確且有一定代表性，反復(fù)調(diào)用K－means 算法10 次得到的結(jié)果正確率如圖4 所示.

使用改進(jìn)后的K－means 算法首先在數(shù)據(jù)集中找出最遠(yuǎn)的兩個(gè)數(shù)據(jù)點(diǎn)，分別為第14 條記錄(4.3，3，1.1，0.1)和第151 條記錄(15，15，15，15)，同時(shí)所有的記錄產(chǎn)生兩類(lèi)，前150 條記錄都以第14 條記錄為中心的簇中，而第151 條記錄單獨(dú)成為一簇，這樣程序?qū)⑹紫葮?biāo)記出第151 條記錄，并且從IRIS 表中剔除，繼續(xù)在重新聚類(lèi)，結(jié)果的顯示正確率為86.17%，高于K－means 算法中得到的72.79%的正確率，同時(shí)也能夠判斷出獨(dú)立點(diǎn).

4 小 結(jié)

通過(guò)以上的對(duì)比可發(fā)現(xiàn)，改進(jìn)后的算法首先可以自動(dòng)得出K 值，而不需要用戶指定值，降低了用戶的進(jìn)行聚類(lèi)的工作難度，同時(shí)對(duì)數(shù)據(jù)集中存在異常點(diǎn)能夠判斷讀出后，不再進(jìn)行聚類(lèi)，這樣不會(huì)對(duì)聚類(lèi)的結(jié)果產(chǎn)生影響，對(duì)大量數(shù)據(jù)進(jìn)行聚類(lèi)過(guò)程中計(jì)算最遠(yuǎn)點(diǎn)之間距離采用先生成邊界集合的方法，大大降低了程序運(yùn)行的時(shí)間，提高了工作效率，因而可以說(shuō)改進(jìn)后的算法應(yīng)用效果要優(yōu)于K－means算法.

［1］ FAHIM A.M，SALEM A.M，TORKEY F.A.An efficient enhanced k－means clustering algorithm［J］.2006，7(10)，22－24.

［2］ 張雪鳳，張桂珍，劉鵬.基于聚類(lèi)準(zhǔn)則函數(shù)的改進(jìn)K－means算法［J］.計(jì)算機(jī)工程與應(yīng)用，2011，11:123－127.

［3］ 張靖，段富.優(yōu)化初始聚類(lèi)中心的改進(jìn)k－means 算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2013，05:1691－1694+1699.

［4］ 毛韶陽(yáng)，林肯立.優(yōu)化k－means 初始聚類(lèi)中心研究［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43(22):179－181.