楊黎明　屈曉旭

【摘 要】隨著數(shù)據(jù)庫(kù)技術(shù)以及數(shù)據(jù)庫(kù)管理系統(tǒng)的迅速發(fā)展，人們積累的數(shù)據(jù)越來越多。聚類（clustering） 作為數(shù)據(jù)挖掘三大領(lǐng)域（關(guān)聯(lián)規(guī)則，聚類，分類）之一被廣泛應(yīng)用[1]。K-均值算法屬于聚類中最普遍快速方法，常采用誤差平方和準(zhǔn)則函數(shù)作為聚類準(zhǔn)則。但K均值算法不能保證標(biāo)準(zhǔn)的全局最小值，這導(dǎo)致對(duì)初始質(zhì)心的高敏感度。本文提出通過消除初始質(zhì)心的隨機(jī)選擇來提高算法性能。本文提出增強(qiáng)的初始質(zhì)心的K均值算法，由于對(duì)應(yīng)用數(shù)據(jù)集進(jìn)行加權(quán)平均，消除了初始值的隨機(jī)選擇，減少了迭代步數(shù)，降低了計(jì)算復(fù)雜度。

【關(guān)鍵詞】聚類；K均值；誤差平方和準(zhǔn)則

0 引言

K均值算法是一種常用的聚類技術(shù)，由于其簡(jiǎn)單性、快速的數(shù)學(xué)計(jì)算和記憶效率深受學(xué)者歡迎。K均值算法通過迭代對(duì)一組對(duì)象進(jìn)行聚類，使得同一組中的對(duì)象比其他組中的對(duì)象更相似[2]。K均值算法是一種聚類算法，它將數(shù)據(jù)集分為K個(gè)非空、非重疊和非從屬的簇。本文提出一種“增強(qiáng)初始質(zhì)心”的K均值算法，主要思想是修改選擇初始質(zhì)心的方法。在傳統(tǒng)的K均值算法中，初始質(zhì)心是隨機(jī)選擇的聚類點(diǎn)。而增強(qiáng)的方法是使用加權(quán)平均值作為質(zhì)心選擇。本研究的主要目的是消除初始質(zhì)心的隨機(jī)選擇，因?yàn)樗鼘?dǎo)致不太可靠的結(jié)果，并提高聚類效率。新方法在選擇初始質(zhì)心之前，計(jì)算每個(gè)屬性的每個(gè)點(diǎn)的加權(quán)平均值。本研究將原始K均值算法和增強(qiáng)初始質(zhì)心的K均值算法，應(yīng)用于對(duì)學(xué)生的考試成績(jī)?cè)u(píng)價(jià)，在可靠性和迭代次數(shù)方面比較了它們的性能。

1 傳統(tǒng)K均值算法

1967年，J.B.MacQueen提出了一種簡(jiǎn)單、快速、高效的用來處理數(shù)據(jù)聚類問題的K均值算法。K均值算法主要思想是將數(shù)據(jù)集合劃分為K個(gè)類簇。首先隨機(jī)選取K個(gè)點(diǎn)作為初始聚類中心，然后計(jì)算數(shù)據(jù)集合中各個(gè)數(shù)據(jù)對(duì)象到各聚類中心距離，按照每個(gè)數(shù)據(jù)對(duì)象距離最近的原則歸到對(duì)應(yīng)的類中；新的分類中心形成后，重新計(jì)算得到新的K個(gè)點(diǎn)作為每個(gè)類新的中心，重新計(jì)算各個(gè)數(shù)據(jù)對(duì)象與新的中心的距離，再次按照距離最近的原則歸整新的類[3]。此過程一直循環(huán)，倘若相鄰兩次的聚類中心不再發(fā)生任何變化，說明數(shù)據(jù)對(duì)象歸類結(jié)束。

式中，K表示類簇個(gè)數(shù)，S表示簇Ci的數(shù)據(jù)對(duì)象，mi表示簇ci的中心（均值）。||s-mi||2可計(jì)算出數(shù)據(jù)對(duì)象到所屬類中心的距離。

K均值算法不能保證標(biāo)準(zhǔn)的全局最小值，這導(dǎo)致對(duì)初始質(zhì)心的高敏感度。本文提出通過消除初始質(zhì)心的隨機(jī)選擇來提高算法性能。K均值聚類算法的聚類結(jié)果很大程度上取決于隨機(jī)選擇的初始質(zhì)心的可靠性。

在數(shù)學(xué)中，二維區(qū)域的質(zhì)心或幾何中心是形狀中所有點(diǎn)的算術(shù)平均位置。隨機(jī)初始選擇不是基于任何計(jì)算或算法，因此會(huì)導(dǎo)致不適當(dāng)?shù)慕Y(jié)果。

下面進(jìn)行實(shí)例應(yīng)用計(jì)算，假設(shè)我們有4名學(xué)生，每個(gè)學(xué)生有兩個(gè)屬性（平時(shí)成績(jī)，考試成績(jī)）。學(xué)生1（100，100），學(xué)生2（200，100），學(xué)生3（400，300），學(xué)生4（500，400）。我們的目標(biāo)是根據(jù)這兩個(gè)特征將這些學(xué)生分成K=2（通過和未通過的學(xué)生）的聚類，以確定四名學(xué)生的學(xué)業(yè)成績(jī)。在這個(gè)例子中，平時(shí)測(cè)試成績(jī)滿分是500，書面考試成績(jī)滿分是400。

在K均值算法的原始方法中，隨著初始質(zhì)心的隨機(jī)選擇，我們假設(shè)學(xué)生1的質(zhì)心1為（100，100），質(zhì)心2為（200，100）。下面使用歐幾里德距離公式對(duì)每個(gè)學(xué)生的質(zhì)心1進(jìn)行樣本計(jì)算。

基于最小距離的對(duì)象聚類的結(jié)果是：

組1為學(xué)生1

組2為學(xué)生2、3、4。

基于新成員的每組的計(jì)算新質(zhì)心是：

組1僅具有一個(gè)成員，質(zhì)心保留在質(zhì)心1=（100，100）中。

組2有三個(gè)成員，因此，質(zhì)心是三個(gè)成員之間的平均坐標(biāo)：質(zhì)心2=（200+400+500）/3，（100+300+400）/3 =（366.67，266.67）。

第二次迭代后，聚類結(jié)果為：

組1=學(xué)生1和2

組2=學(xué)生3和4

以下表格是重復(fù)K均值算法原始方法的主要步驟的結(jié)果：

（1）確定質(zhì)心/質(zhì)心

（2）使用歐幾里得距離計(jì)算物體中心距離

（3）對(duì)象聚類。

用新成員，計(jì)算另一個(gè)質(zhì)心群：質(zhì)心1=（100+200）/2，（100+100）/2=（150，100），質(zhì)心2=（400+500）/2，（300+400）/2=（450，350）。

質(zhì)心1的樣本計(jì)算=（150，100）

質(zhì)心2的樣本計(jì)算=（450，350）

三次迭代后的最后分組如下所示。

可以看出，傳統(tǒng)K均值算法隨機(jī)選擇初始質(zhì)心導(dǎo)致了三次迭代。

3 增強(qiáng)初始中心K均值算法

3.1 主要步驟

3.1.1 初始化

給定簇的數(shù)量K，增強(qiáng)初始質(zhì)心意味著給予對(duì)象屬性更準(zhǔn)確的加權(quán)平均值。計(jì)算得到的最高和最低加權(quán)平均值作為創(chuàng)建初始分簇的初始質(zhì)心。初始分簇使用計(jì)算的初始質(zhì)心，將對(duì)象劃分為K個(gè)群集。分簇和收斂步驟則相似于傳統(tǒng)的K均值算法。

3.1.2 分簇

分配步驟：使用歐幾里德距離計(jì)算聚類，如果數(shù)據(jù)當(dāng)前不在具有最接近原型的簇中，則將其重新分配給距離其最近的簇；

更新步驟：如果發(fā)生重新分配，則更新簇，并使用當(dāng)前聚類重新計(jì)算質(zhì)心；

3.1.3 重復(fù)迭代，直到產(chǎn)生收斂

由于質(zhì)心是數(shù)據(jù)集中指示相等權(quán)重的所有點(diǎn)的平均位置，因此加權(quán)平均值是指定數(shù)據(jù)集中點(diǎn)的實(shí)際權(quán)重，其中最高加權(quán)平均和最低加權(quán)平均值用X，Y來表示。該算法結(jié)果表明組間重疊被最小化，并且分離更明顯。增強(qiáng)質(zhì)心的K均值算法應(yīng)用數(shù)據(jù)集的加權(quán)平均值，能夠清楚地分離數(shù)據(jù)集，并且具有較少的迭代次數(shù)。它不僅消除了初始質(zhì)心的隨機(jī)選擇，而且減少了用于聚類的歐氏距離計(jì)算。endprint

3.2 實(shí)例驗(yàn)證

加權(quán)平均值是按權(quán)重大小進(jìn)行分配的平均值，以下是加權(quán)平均數(shù)S的公式：

s=∑wx/∑w（3）

將K均值算法的同樣應(yīng)用在學(xué)生成績(jī)問題中，確定列中的最高點(diǎn)。

對(duì)于屬性X（平時(shí)測(cè)驗(yàn)），其最高點(diǎn)（即最高成績(jī)）是500。根據(jù)給定的權(quán)重得到每個(gè)點(diǎn)的加權(quán)平均值，權(quán)重將等于給定屬性的最高點(diǎn)。

X[1]=100*500/1200=41.67

X[2]=200*500/1200=83.33

X[3]=400*500/1200=166.66

X[4]=500*500/1200=208.33

對(duì)于屬性Y（書面考試），其最高點(diǎn)是400。Y的每個(gè)點(diǎn)的加權(quán)平均值為：

X[1]=100*400/900=44.44

X[2]=100*400/900=44.44

Y[1]=300*400/900=133.33

Y[2]=400*400/900=177.78

X=41.57和Y=44.44，這是通過加權(quán)平均獲得的兩個(gè)初始質(zhì)心。因此，初始質(zhì)心是質(zhì)心1=（100，100），質(zhì)心2 =（500，400）。通過歐幾里德距離的公式來計(jì)算群集中心到每個(gè)對(duì)象之間的距離。

迭代1：使用歐幾里德距離知道質(zhì)心1（100，100）之間的距離的樣本計(jì)算如下所示：

質(zhì)心1的樣本計(jì)算=（100，100）

質(zhì)心2=（500，400）物體的歐氏距離的樣本計(jì)算如下所示：

質(zhì)心2的樣本計(jì)算=（500，400）

使用歐幾里德的第一次迭代的初始結(jié)果如下表所示。

質(zhì)心1（100，100）=（0.00，100.00，360.55，500.00）之間的距離。 質(zhì)心2（500 400）=（500，424.26，141.42，0.00）之間的距離。 基于計(jì)算，對(duì)象聚類是檢查對(duì)象到兩個(gè)質(zhì)心的最小距離的過程。

初步計(jì)算后，增強(qiáng)型K均值組1的迭代1已經(jīng)有2名成員，1名和2名學(xué)生，與第2組相同， 只有一名成員，第2組有3名成員。

在新方法中，由于組1和組2各有2個(gè)成員，因此我們必須計(jì)算對(duì)象分簇的新質(zhì)心。

迭代2：新質(zhì)心1將為（100 + 200）/ 2（100 + 100）2 =（150，100）

物體與質(zhì)心1的新計(jì)算距離為（50，50，320.15.460.97）。

質(zhì)心1的樣本計(jì)算=（150，100）

新質(zhì)心2將為（400 + 500）/，（300 + 400）/ 2 =（450，350）。

質(zhì)心2=（430.11，353.55，70.71，70.71）物體距離的樣本計(jì)算如下所示：

質(zhì)心2的樣本計(jì)算=（450，350）

比較原始的K均值算法和迭代，修改的K均值算法已達(dá)到穩(wěn)定，不需要更多的迭代。與以前的K均值算法相比，迭代次數(shù)減少了。基于增強(qiáng)初始質(zhì)心的K均值算法獲得的初始質(zhì)心如表所示。

使用增強(qiáng)初始質(zhì)心的K均值算法進(jìn)行聚類的最終結(jié)果如下所示。

4 小結(jié)

增強(qiáng)的初始質(zhì)心的K均值算法，由于對(duì)應(yīng)用數(shù)據(jù)集進(jìn)行加權(quán)平均，消除了初始值的隨機(jī)選擇，減少了迭代步數(shù)，降低了計(jì)算復(fù)雜度。K均值必須預(yù)先輸入K值作為輸入?yún)?shù)，因?yàn)椴贿m當(dāng)?shù)腒選擇可能產(chǎn)生不準(zhǔn)確的分類結(jié)果，這是我們下一步研究的方向，著力解決該問題。

【參考文獻(xiàn)】

[1]J Han J，Kamber M.范明，孟小峰，等譯：數(shù)據(jù)挖掘概念與技術(shù).第一版.北京：機(jī)械工業(yè)出版社.2006，185-217.

[2]T.Kanungo，D.M Mount，N.S.Netanyahu，etal.An efficient K-means clusteringalgorithm：analysis and implementation.IEEE Transactions on Pattern Ana1ysis and Machine Intelligence，2002， 24（7）：881-892.

[3]萬(wàn)小軍，楊建武，陳曉鷗.文檔聚類中 K-means 算法的一種改進(jìn)算法.計(jì)算機(jī)工程，2003，29（2）：102-103，157.

[4]周娟.基于最大最小距離法的多中心聚類算法研究[D].慶：重慶大學(xué)汁算機(jī)系統(tǒng)結(jié)構(gòu)，2006.endprint