一種新的選取K-means初始聚類中心算法

張嘉龍

（華南農(nóng)業(yè)大學(xué)數(shù)學(xué)與信息學(xué)院，廣州510642）

0 引言

機(jī)器學(xué)習(xí)是目前非常熱門的一門學(xué)科，它包含多種快捷實(shí)用的算法，給人們帶來了極大的便利，其中包含的聚類算法是一種無監(jiān)督的學(xué)習(xí)算法，K-means算法則是最常用的聚類算法之一。

K-means算法目前廣泛應(yīng)用[1-4]于聚類劃分，是一種經(jīng)典的聚類算法，但由于該算法選取初始聚類中心的隨機(jī)性，經(jīng)常出現(xiàn)數(shù)據(jù)聚類不穩(wěn)定的結(jié)果，且結(jié)果容易陷入局部最優(yōu)。因此，研究一種具有穩(wěn)定聚類效果和有較高準(zhǔn)確率以及低迭代次數(shù)的聚類算法具有重要意義。

針對傳統(tǒng)的K-means聚類算法的初始聚類中心選取問題，本文借鑒文獻(xiàn)[5-7]所提出的相異度及相異度矩陣的概念，通過建立相異度矩陣，并計(jì)算總體平均相異度以及行平均相異度，同時構(gòu)造集合S，通過類似Dijkstra算法的思想，隨相異度增長趨勢不斷遴選合適的樣本點(diǎn)進(jìn)入集合S，最終通過對S內(nèi)對應(yīng)樣本點(diǎn)的屬性求平均得到K-means算法的初始聚類中心，隨后在數(shù)據(jù)集中刪除集合S內(nèi)包含的樣本點(diǎn)，利用得到的新數(shù)據(jù)集重新執(zhí)行算法，最終可以得到K個初始聚類中心，隨之采用K-means算法得到聚類結(jié)果。實(shí)驗(yàn)表明，相比于傳統(tǒng)聚類算法，新的算法擁有穩(wěn)定的聚類效果，且有較高的聚類準(zhǔn)確率和較少的迭代次數(shù)，同時對比于文獻(xiàn)[8]和文獻(xiàn)[9]的算法所得結(jié)果，新算法在保持聚類結(jié)果準(zhǔn)確率不變的情況下，迭代次數(shù)大幅下降。

1 新的初始聚類中心選擇算法

1.1 算法相關(guān)概念

定義7：集合S={c1,c2,…,cn}，表示遴選的第ci個樣本點(diǎn)的下標(biāo)集合，i∈{1,2,…,n}，其中ci為小于n的任意正整數(shù)，且集合中任意兩個元素之間互不相等，記RS為S中已選樣本點(diǎn)所對應(yīng)的相異度矩陣的行組成的矩陣。

1.2 算法思想

設(shè)需要聚類的類別數(shù)為K，本文算法通過計(jì)算樣本點(diǎn)間的相異度，然后根據(jù)相異度建立相異度矩陣。同時，為了得到最密集的一群樣本點(diǎn)，首先計(jì)算相異度矩陣中每一行的平均值，并選取平均值最小的一行，將該行對應(yīng)的樣本點(diǎn)作為起點(diǎn)，尋找離該樣本點(diǎn)最近的另外一個樣本點(diǎn)，即尋找相異度矩陣中該行非對角線上元素（對角線為該樣本點(diǎn)本身的相異度）的最小值，將該最小值對應(yīng)的樣本點(diǎn)與最初的一個樣本點(diǎn)所對應(yīng)的下標(biāo)加入集合S。

然后借鑒Dijkstra算法的思想，再尋找離集合S中對應(yīng)樣本點(diǎn)距離之和最近的下一個樣本點(diǎn)，同時為了讓集合S中的最終樣本點(diǎn)數(shù)量取得合適的值，該樣本點(diǎn)需與集合S中對應(yīng)的任一樣本點(diǎn)的相異度不能超過總體平均相異度。按如上方法不斷遴選樣本點(diǎn)，最后得到飽和的集合S，將S中對應(yīng)的所有樣本點(diǎn)的屬性取平均，該平均值即作為第一個初始聚類中心。

隨之將集合S內(nèi)對應(yīng)的樣本點(diǎn)從數(shù)據(jù)集X中刪除，得到新的數(shù)據(jù)集，根據(jù)新的數(shù)據(jù)集重新建立相異度矩陣，按相同的方法得到剩余的初始聚類中心，直到初始聚類中心個數(shù)達(dá)到K，然后采用K-means算法得到聚類結(jié)果。

1.3 算法步驟

遴選K個初始聚類中心的方法步驟：

（1）已選初始聚類中心個數(shù)記為num，num初始化為0；

（2）根據(jù)樣本集X建立相異度矩陣R，同時構(gòu)造空集S；

（3）根據(jù)R計(jì)算總體平均相異度Mean_r以及各行平均相異度，找到行最小平均相異度MMR，并記錄其所在的行row；

（4）將R中對角線上的元素賦值為無窮；

（5）在Rrow中找到最小值rrowj，將下標(biāo)row和j加入集合S，同時將R中的rrowj和rjrow兩個元素賦值為無窮，根據(jù)R和S建立矩陣RS；

（6）對RS中的每列，若該列任一元素的值均小于Mean_r，則對該列進(jìn)行求和，若任一列中的任意一個值均不小于Mean_r或者S中的元素個數(shù)等于n，進(jìn)入（7），否則，在所有進(jìn)行求和的列當(dāng)中找到和最小的列k，將k加入集合S，同時將R中的rxk和rkx均賦值為無窮，其中x∈S，根據(jù)R和S重建矩陣RS，重新執(zhí)行（6）；

（7）計(jì)算集合S中所有對應(yīng)樣本點(diǎn)屬性的平均值，將該平均值作為下一個初始聚類中心，同時令num=num+1，若此時num==K，結(jié)束遴選算法，否則進(jìn)入（8）；

（8）將集合S中所對應(yīng)的所有樣本點(diǎn)從數(shù)據(jù)集X中刪除，重新執(zhí)行（2）。

根據(jù)以上方法步驟，可以得到K個初始聚類中心，然后調(diào)用K-means算法，得到聚類結(jié)果。

1.4 K-means算法思想

首先選取K個初始聚類中心（本文采用上述算法得到的初始聚類中心），計(jì)算每個樣本點(diǎn)到每個聚類中心的距離，將樣本點(diǎn)分到距離最近的聚類中心，形成K個簇。在每個簇當(dāng)中，計(jì)算該簇中所有樣本點(diǎn)的平均值，以該值作為新的聚類中心，重新計(jì)算樣本點(diǎn)到新的聚類中心的距離并重新分配，直到新的初始聚類中心位置不再變化或變化小于某個閾值時停止算法，最終得到分類最佳的K類樣本點(diǎn)。

2 實(shí)驗(yàn)結(jié)果

本文采用UCI數(shù)據(jù)集中的三種數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，分別為Iris、Wine、Seeds，其對應(yīng)的屬性描述如表1所示。同時將新算法得到的實(shí)驗(yàn)結(jié)果與傳統(tǒng)K-means算法、文獻(xiàn)[8]算法以及文獻(xiàn)[9]的算法得到的結(jié)果進(jìn)行比較。

表1 數(shù)據(jù)集描述

由于K-means算法的不穩(wěn)定性，本文實(shí)驗(yàn)中將對其運(yùn)行五次得到的結(jié)果取平均，以此與其他算法得到的結(jié)果進(jìn)行比較。

運(yùn)用不同的算法進(jìn)行實(shí)驗(yàn)，得到的實(shí)驗(yàn)結(jié)果如表2-表4所示。

表2 Iris數(shù)據(jù)集實(shí)驗(yàn)結(jié)果對比

表3 Wine數(shù)據(jù)集實(shí)驗(yàn)結(jié)果對比

表4 Seeds數(shù)據(jù)集實(shí)驗(yàn)結(jié)果對比

由表2-表4可以看出，相比于傳統(tǒng)的K-means算法，本文算法能夠得到穩(wěn)定的聚類結(jié)果，同時在迭代次數(shù)上有明顯的下降，且準(zhǔn)確率也較高，在Iris數(shù)據(jù)集中，迭代次數(shù)平均下降2.6次，準(zhǔn)確率平均提高12.93%。在Wine數(shù)據(jù)集中，迭代次數(shù)平均下降3.6次，準(zhǔn)確率提高2.47%。而在Seeds數(shù)據(jù)集中，平均迭代次數(shù)下降最多，為6次，且準(zhǔn)確率也提升了0.28%。

而對比于文獻(xiàn)[8]和文獻(xiàn)[9]的算法，本文算法在保持準(zhǔn)確率的情況下，迭代次數(shù)有較大的下降，特別是在Iris數(shù)據(jù)集和Seeds數(shù)據(jù)集上，對于Iris數(shù)據(jù)集，由原來的7次和8次下降到3次，而對于Seeds數(shù)據(jù)集，由原來的8次和12次下降到2次，下降的程度較大。

3 結(jié)語

本文針對傳統(tǒng)K-means算法聚類不穩(wěn)定的缺陷，提出了一種新的算法，通過建立相異度矩陣，利用MM R和R E得到K個初始聚類中心。實(shí)驗(yàn)結(jié)果表明，新的算法具有穩(wěn)定的聚類效果，且有較高的分類準(zhǔn)確率，同時迭代次數(shù)有明顯的下降。