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

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

2、；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均值算

3、法和增強初始質(zhì)心的k均值算法，應(yīng)用于對學生的考試成績評價，在可靠性和迭代次數(shù)方面比較了它們的性能。1 傳統(tǒng)k均值算法1967年，j.b.macqueen提出了一種簡單、快速、高效的用來處理數(shù)據(jù)聚類問題的k均值算法。k均值算法主要思想是將數(shù)據(jù)集合劃分為k個類簇。首先隨機選取k個點作為初始聚類中心，然后計算數(shù)據(jù)集合中各個數(shù)據(jù)對象到各聚類中心距離，按照每個數(shù)據(jù)對象距離最近的原則歸到對應(yīng)的類中；新的分類中心形成后，重新計算得到新的k個點作為每個類新的中心，重新計算各個數(shù)據(jù)對象與新的中心的距離，再次按照距離最近的原則歸整新的類3。此過程一直循環(huán)，倘若相鄰兩次的聚類中心不再發(fā)生任何變化，說明數(shù)據(jù)對象歸類結(jié)

4、束。式中，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é)果。下面進行實例應(yīng)用計算，假設(shè)我們有4名學生，每個學生有兩個屬性（平時成績，考試成績）。學生1（100，100），學生2（200，100），學生3（400，300），學

5、生4（500，400）。我們的目標是根據(jù)這兩個特征將這些學生分成k=2（通過和未通過的學生）的聚類，以確定四名學生的學業(yè)成績。在這個例子中，平時測試成績滿分是500，書面考試成績滿分是400。在k均值算法的原始方法中，隨著初始質(zhì)心的隨機選擇，我們假設(shè)學生1的質(zhì)心1為（100，100），質(zhì)心2為（200，100）。下面使用歐幾里德距離公式對每個學生的質(zhì)心1進行樣本計算。基于最小距離的對象聚類的結(jié)果是：組1為學生1組2為學生2、3、4?；谛鲁蓡T的每組的計算新質(zhì)心是：組1僅具有一個成員，質(zhì)心保留在質(zhì)心1=（100，100）中。組2有三個成員，因此，質(zhì)心是三個成員之間的平均坐標：質(zhì)心2=（200+4

6、00+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）三次迭代后的最后分組如下所示?？梢钥闯觯瑐鹘y(tǒng)k均值算法隨機選擇初始質(zhì)心導致了三次

7、迭代。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)重，其中最

8、高加權(quán)平均和最低加權(quán)平均值用x，y來表示。該算法結(jié)果表明組間重疊被最小化，并且分離更明顯。增強質(zhì)心的k均值算法應(yīng)用數(shù)據(jù)集的加權(quán)平均值，能夠清楚地分離數(shù)據(jù)集，并且具有較少的迭代次數(shù)。它不僅消除了初始質(zhì)心的隨機選擇，而且減少了用于聚類的歐氏距離計算。endprint3.2 實例驗證加權(quán)平均值是按權(quán)重大小進行分配的平均值，以下是加權(quán)平均數(shù)s的公式：s=wx/w（3）將k均值算法的同樣應(yīng)用在學生成績問題中，確定列中的最高點。對于屬性x（平時測驗），其最高點（即最高成績）是500。根據(jù)給定的權(quán)重得到每個點的加權(quán)平均值，權(quán)重將等于給定屬性的最高點。x1=100*500/1200=41.67x2=200*5

9、00/1200=83.33x3=400*500/1200=166.66x4=500*500/1200=208.33對于屬性y（書面考試），其最高點是400。y的每個點的加權(quán)平均值為：x1=100*400/900=44.44x2=100*400/900=44.44y1=300*400/900=133.33y2=400*400/900=177.78x=41.57和y=44.44，這是通過加權(quán)平均獲得的兩個初始質(zhì)心。因此，初始質(zhì)心是質(zhì)心1=（100，100），質(zhì)心2 =（500，400）。通過歐幾里德距離的公式來計算群集中心到每個對象之間的距離。迭代1：使用歐幾里德距離知道質(zhì)心1（100，100）之

10、間的距離的樣本計算如下所示：質(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個成員，

11、因此我們必須計算對象分簇的新質(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均值算法獲得的初

12、始質(zhì)心如表所示。使用增強初始質(zhì)心的k均值算法進行聚類的最終結(jié)果如下所示。4 小結(jié)增強的初始質(zhì)心的k均值算法，由于對應(yīng)用數(shù)據(jù)集進行加權(quán)平均，消除了初始值的隨機選擇，減少了迭代步數(shù)，降低了計算復雜度。k均值必須預先輸入k值作為輸入?yún)?shù)，因為不適當?shù)膋選擇可能產(chǎn)生不準確的分類結(jié)果，這是我們下一步研究的方向，著力解決該問題?！緟⒖嘉墨I】1j han j，kamber m.范明，孟小峰，等譯：數(shù)據(jù)挖掘概念與技術(shù).第一版.北京：機械工業(yè)出版社.2006，185-217.2t.kanungo，d.m mount，n.s.netanyahu，etal.an efficient k-means clusteringalgorithm：analysis and implementation.ieee transactions on