基于K均值算法增強初始中心的研究

楊黎明　屈曉旭

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

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

0 引言

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

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

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

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

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

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

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

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

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

組1為學生1

組2為學生2、3、4。

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

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

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

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

組1=學生1和2

組2=學生3和4

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

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

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

（3）對象聚類。

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

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

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

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

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

3 增強初始中心K均值算法

3.1 主要步驟

3.1.1 初始化

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

3.1.2 分簇

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

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

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

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

3.2 實例驗證

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

s=∑wx/∑w（3）

將K均值算法的同樣應用在學生成績問題中，確定列中的最高點。

對于屬性X（平時測驗），其最高點（即最高成績）是500。根據(jù)給定的權(quán)重得到每個點的加權(quán)平均值，權(quá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

對于屬性Y（書面考試），其最高點是400。Y的每個點的加權(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)平均獲得的兩個初始質(zhì)心。因此，初始質(zhì)心是質(zhì)心1=（100，100），質(zhì)心2 =（500，400）。通過歐幾里德距離的公式來計算群集中心到每個對象之間的距離。

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

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

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

質(zhì)心2的樣本計算=（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）之間的距離。 基于計算，對象聚類是檢查對象到兩個質(zhì)心的最小距離的過程。

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

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

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

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

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

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

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

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

比較原始的K均值算法和迭代，修改的K均值算法已達到穩(wěn)定，不需要更多的迭代。與以前的K均值算法相比，迭代次數(shù)減少了?；谠鰪姵跏假|(zhì)心的K均值算法獲得的初始質(zhì)心如表所示。

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

4 小結(jié)

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

【參考文獻】

[1]J Han J，Kamber M.范明，孟小峰，等譯：數(shù)據(jù)挖掘概念與技術(shù).第一版.北京：機械工業(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]萬小軍，楊建武，陳曉鷗.文檔聚類中 K-means 算法的一種改進算法.計算機工程，2003，29（2）：102-103，157.

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