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

楊黎明　屈曉旭

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

【關鍵詞】聚類；K均值；誤差平方和準則

0 引言

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

1 傳統K均值算法

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

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

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

在數學中，二維區域的質心或幾何中心是形狀中所有點的算術平均位置。隨機初始選擇不是基于任何計算或算法，因此會導致不適當的結果。

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

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

基于最小距離的對象聚類的結果是：

組1為學生1

組2為學生2、3、4。

基于新成員的每組的計算新質心是：

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

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

第二次迭代后，聚類結果為：

組1=學生1和2

組2=學生3和4

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

（1）確定質心/質心

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

（3）對象聚類。

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

質心1的樣本計算=（150，100）

質心2的樣本計算=（450，350）

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

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

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

3.1 主要步驟

3.1.1 初始化

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

3.1.2 分簇

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

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

3.1.3 重復迭代，直到產生收斂

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

3.2 實例驗證

加權平均值是按權重大小進行分配的平均值，以下是加權平均數S的公式：

s=∑wx/∑w（3）

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

對于屬性X（平時測驗），其最高點（即最高成績）是500。根據給定的權重得到每個點的加權平均值，權重將等于給定屬性的最高點。

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的每個點的加權平均值為：

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，這是通過加權平均獲得的兩個初始質心。因此，初始質心是質心1=（100，100），質心2 =（500，400）。通過歐幾里德距離的公式來計算群集中心到每個對象之間的距離。

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

質心1的樣本計算=（100，100）

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

質心2的樣本計算=（500，400）

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

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

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

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

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

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

質心1的樣本計算=（150，100）

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

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

質心2的樣本計算=（450，350）

比較原始的K均值算法和迭代，修改的K均值算法已達到穩定，不需要更多的迭代。與以前的K均值算法相比，迭代次數減少了。基于增強初始質心的K均值算法獲得的初始質心如表所示。

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

4 小結

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

【參考文獻】

[1]J Han J，Kamber M.范明，孟小峰，等譯：數據挖掘概念與技術.第一版.北京：機械工業出版社.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].慶：重慶大學汁算機系統結構，2006.endprint