基于K均值算法增強(qiáng)初始中心的研究

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

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

3、法和增強(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)單、快速、高效的用來(lái)處理數(shù)據(jù)聚類(lèi)問(wèn)題的k均值算法。k均值算法主要思想是將數(shù)據(jù)集合劃分為k個(gè)類(lèi)簇。首先隨機(jī)選取k個(gè)點(diǎn)作為初始聚類(lèi)中心，然后計(jì)算數(shù)據(jù)集合中各個(gè)數(shù)據(jù)對(duì)象到各聚類(lèi)中心距離，按照每個(gè)數(shù)據(jù)對(duì)象距離最近的原則歸到對(duì)應(yīng)的類(lèi)中；新的分類(lèi)中心形成后，重新計(jì)算得到新的k個(gè)點(diǎn)作為每個(gè)類(lèi)新的中心，重新計(jì)算各個(gè)數(shù)據(jù)對(duì)象與新的中心的距離，再次按照距離最近的原則歸整新的類(lèi)3。此過(guò)程一直循環(huán)，倘若相鄰兩次的聚類(lèi)中心不再發(fā)生任何變化，說(shuō)明數(shù)據(jù)對(duì)象歸類(lèi)結(jié)

4、束。式中，k表示類(lèi)簇個(gè)數(shù)，s表示簇ci的數(shù)據(jù)對(duì)象，mi表示簇ci的中心（均值）。|s-mi|2可計(jì)算出數(shù)據(jù)對(duì)象到所屬類(lèi)中心的距離。k均值算法不能保證標(biāo)準(zhǔn)的全局最小值，這導(dǎo)致對(duì)初始質(zhì)心的高敏感度。本文提出通過(guò)消除初始質(zhì)心的隨機(jī)選擇來(lái)提高算法性能。k均值聚類(lèi)算法的聚類(lèi)結(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é)

5、生4（500，400）。我們的目標(biāo)是根據(jù)這兩個(gè)特征將這些學(xué)生分成k=2（通過(guò)和未通過(guò)的學(xué)生）的聚類(lèi)，以確定四名學(xué)生的學(xué)業(yè)成績(jī)。在這個(gè)例子中，平時(shí)測(cè)試成績(jī)滿分是500，書(shū)面考試成績(jī)滿分是400。在k均值算法的原始方法中，隨著初始質(zhì)心的隨機(jī)選擇，我們假設(shè)學(xué)生1的質(zhì)心1為（100，100），質(zhì)心2為（200，100）。下面使用歐幾里德距離公式對(duì)每個(gè)學(xué)生的質(zhì)心1進(jìn)行樣本計(jì)算?；谧钚【嚯x的對(duì)象聚類(lèi)的結(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+4

6、00+500）/3，（100+300+400）/3 =（366.67，266.67）。第二次迭代后，聚類(lèi)結(jié)果為：組1=學(xué)生1和2組2=學(xué)生3和4以下表格是重復(fù)k均值算法原始方法的主要步驟的結(jié)果：（1）確定質(zhì)心/質(zhì)心（2）使用歐幾里得距離計(jì)算物體中心距離（3）對(duì)象聚類(lèi)。用新成員，計(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）三次迭代后的最后分組如下所示?？梢钥闯觯瑐鹘y(tǒng)k均值算法隨機(jī)選擇初始質(zhì)心導(dǎo)致了三次

7、迭代。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ì)算聚類(lèi)，如果數(shù)據(jù)當(dāng)前不在具有最接近原型的簇中，則將其重新分配給距離其最近的簇；更新步驟：如果發(fā)生重新分配，則更新簇，并使用當(dāng)前聚類(lèi)重新計(jì)算質(zhì)心；3.1.3 重復(fù)迭代，直到產(chǎn)生收斂由于質(zhì)心是數(shù)據(jù)集中指示相等權(quán)重的所有點(diǎn)的平均位置，因此加權(quán)平均值是指定數(shù)據(jù)集中點(diǎn)的實(shí)際權(quán)重，其中最

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

9、00/1200=83.33x3=400*500/1200=166.66x4=500*500/1200=208.33對(duì)于屬性y（書(shū)面考試），其最高點(diǎn)是400。y的每個(gè)點(diǎn)的加權(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，這是通過(guò)加權(quán)平均獲得的兩個(gè)初始質(zhì)心。因此，初始質(zhì)心是質(zhì)心1=（100，100），質(zhì)心2 =（500，400）。通過(guò)歐幾里德距離的公式來(lái)計(jì)算群集中心到每個(gè)對(duì)象之間的距離。迭代1：使用歐幾里德距離知道質(zhì)心1（100，100）之

10、間的距離的樣本計(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ì)象聚類(lèi)是檢查對(duì)象到兩個(gè)質(zhì)心的最小距離的過(guò)程。初步計(jì)算后，增強(qiáng)型k均值組1的迭代1已經(jīng)有2名成員，1名和2名學(xué)生，與第2組相同， 只有一名成員，第2組有3名成員。在新方法中，由于組1和組2各有2個(gè)成員，

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

12、始質(zhì)心如表所示。使用增強(qiáng)初始質(zhì)心的k均值算法進(jìn)行聚類(lèi)的最終結(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)確的分類(lèi)結(jié)果，這是我們下一步研究的方向，著力解決該問(wèn)題?！緟⒖嘉墨I(xiàn)】1j han j，kamber m.范明，孟小峰，等譯：數(shù)據(jù)挖掘概念與技術(shù).第一版.北京：機(jī)械工業(yè)出版社.2006，185-217.2t.kanungo，d.m mount，n.s.netanyahu，etal.an efficient k-means clusteringalgorithm：analysis and implementation.ieee transactions on