劉榮凱 孫忠林

摘要：Kmeans算法在聚類過(guò)程中隨機(jī)選取k個(gè)初始聚類中心，容易造成聚類結(jié)果不穩(wěn)定。針對(duì)該問(wèn)題，提出PCATDKM算法：使用主成分分析法對(duì)數(shù)據(jù)對(duì)象集合的屬性進(jìn)行降維，提取出主屬性，去掉無(wú)關(guān)屬性，從而加速聚類過(guò)程;基于最小生成樹(shù)算法及樹(shù)的剪枝方法將數(shù)據(jù)對(duì)象劃分為k個(gè)初始聚類簇，然后進(jìn)行剪枝生成k棵子樹(shù)，計(jì)算每棵子樹(shù)中所有數(shù)據(jù)對(duì)象的均值，作為初始聚類中心;利用基于密度與最大最小距離的算法思想進(jìn)行聚類。將PCATDKM算法與Kmeans、KNEKM、QMCKM、CFSFDPKM在UCI數(shù)據(jù)集上進(jìn)行聚類比較，結(jié)果表明該算法聚類結(jié)果穩(wěn)定、聚類準(zhǔn)確率高。

關(guān)鍵詞：

Kmeans算法;主成分分析法;聚類;聚類準(zhǔn)確率

DOIDOI：10.11907/rjdk.182064

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2018）009008503

英文標(biāo)題PCATDKM Algorithm for Kmeans Initial Clustering Center Optimization

——副標(biāo)題

英文作者LIU Rongkai， SUN Zhonglin

英文作者單位（College of Computer Science and Engineering， Shandong University of Science and Technology， Qingdao 266590， China）

英文摘要Abstract：The Kmeans algorithm selects cluster centers randomly， which is likely to cause unstable clustering results.To solve this problem， this paper proposes the PCATDKM algorithm.Which uses principal component analysis to reduce the dimension of the data set and extract the main attribute. The data object is divided into k initial clusters based on the minimum spanning tree algorithm and the tree pruning method， and then pruning is performed to generate k subtrees and the average value of each subtree is calculated as the initial clustering center; the PCATDKM algorithm uses clustering algorithms based on density and maximum and minimum distances for clustering. The algorithm is clustered with Kmeans， KNEKM， QMCKM and CFSFDPKM on the UCI dataset. The results show that the clustering results are stable and the clustering accuracy is high.

英文關(guān)鍵詞Key Words：Kmeans algorithm; principal component analysis; clustering; accuracy of clustering

0引言

許多學(xué)者從算法初始k個(gè)聚類中心選擇、數(shù)據(jù)對(duì)象相似度計(jì)算、聚類質(zhì)量評(píng)價(jià)函數(shù)三方面對(duì)算法進(jìn)行改進(jìn)，使算法聚類效果得到了一定改善。馮波等[1]利用對(duì)象的距離矩陣生成最小生成樹(shù)，將k個(gè)樹(shù)分支中所包含點(diǎn)的均值作為初始聚類中心進(jìn)行聚類;鄭丹等[2]基于密度選取各主要密度水平曲線上的第一個(gè)點(diǎn)作為k個(gè)初始聚類中心;石文峰等[3]提出一種用個(gè)體輪廓系數(shù)作為聚類有效性評(píng)估參數(shù)的改進(jìn)算法;周煒奔等[4]提出利用均衡函數(shù)自動(dòng)生成最優(yōu)簇?cái)?shù)k值的算法;王宏杰等[5]結(jié)合初始中心優(yōu)化和特征加權(quán)改進(jìn)Kmeans聚類算法;陳小雪等[6]提出一種基于螢火蟲(chóng)優(yōu)化的加權(quán)Kmeans算法;王賽芳等[7]提出基于點(diǎn)密度的初始聚類中心選擇方法;李海洋等[8]提出一種改進(jìn)人工蜂群和K均值聚類的圖像分割算法IABCK;朱曉峰等[9]提出一種基于文本平均相似度的Kmeans算法;李敏等[10]提出密度峰值優(yōu)化初始中心的Kmeans算法;莊瑞格等[11]提出基于擬蒙特卡洛的Kmeans聚類算法;熊開(kāi)玲等[12]提出基于核密度估計(jì)的Kmeans聚類優(yōu)化算法;張雪鳳等[13]通過(guò)調(diào)整Kmeans算法運(yùn)行中數(shù)據(jù)對(duì)象被重新分配時(shí)的策略以提高數(shù)據(jù)對(duì)象集合的聚類質(zhì)量;翟東海等[14]提出用最大距離法選取初始簇中心的kmeans文本聚類算法;趙將等[15]提出一種推薦算法IKC（Improved Kmeans Clustering Recommendation Method）用來(lái)改進(jìn)Kmeans聚類。

以上算法分別針對(duì)聚類中心以及聚類質(zhì)量評(píng)價(jià)函數(shù)進(jìn)行優(yōu)化，在一定程度上提高了聚類準(zhǔn)確率，但是仍然存在聚類中心不穩(wěn)定、聚類效果不佳等缺點(diǎn)。因此，本文提出一種基于傳統(tǒng)Kmeans算法改進(jìn)的PCATDKM（Principal Component AnalysisTree Distribution KMeans）算法。實(shí)驗(yàn)證明：PCATDKM算法在UCI數(shù)據(jù)集上得到的聚類結(jié)果比Kmeans算法準(zhǔn)確度高，聚類結(jié)果更穩(wěn)定。

1主成分分析算法

主成分分析算法[16]的思想是：對(duì)各維數(shù)據(jù)進(jìn)行分析，提取并合成數(shù)據(jù)對(duì)象中無(wú)相關(guān)性的主要屬性，用主要屬性代表數(shù)據(jù)對(duì)象集中的原有屬性。使用主成分分析法能夠有效降低數(shù)據(jù)對(duì)象集合中的無(wú)關(guān)屬性，大幅提高聚類運(yùn)算效率及聚類準(zhǔn)確率。

標(biāo)準(zhǔn)化變換公式：

zij=xij-xjsji=1，2…p;j=1，2…m（1）

其中，xj=∑pi=1xijp，sj=∑pi=1（xij-xj）p-1。xij表示矩陣中每個(gè)樣本值，zij表示標(biāo)準(zhǔn)化矩陣，xj表示列均值，sj表示列標(biāo)準(zhǔn)差。

R=[rij]mxm=zTzp-1（2）

其中，rij=∑zkj.zkjp-1，i，j=1，2…m;R為相關(guān)系數(shù)矩陣;x為隨機(jī)向量;m為維數(shù);zT表示標(biāo)準(zhǔn)化矩陣z的轉(zhuǎn)置。

2PCATDKM算法

PCATDKM算法的思想是：用主成分分析法提取集合中主要屬性進(jìn)行降維，去除無(wú)關(guān)屬性，從而提高運(yùn)算效率、加速聚類。利用數(shù)據(jù)對(duì)象集合的距離矩陣構(gòu)造出一棵最小生成樹(shù)[17]。對(duì)構(gòu)造出的最小生成樹(shù)進(jìn)行剪枝，將其劃分為k棵子樹(shù)，每棵子樹(shù)中所包含的數(shù)據(jù)對(duì)象代表一個(gè)類別（共k個(gè)類別），計(jì)算每棵子樹(shù)中所包含數(shù)據(jù)對(duì)象的算術(shù)均值作為初始聚類中心，然后選取其中一個(gè)算術(shù)均值作為第一個(gè)聚類中心，利用最大最小距離算法選取剩下的k-1個(gè)初始聚類中心。進(jìn)行k次操作，選取使誤差平方和函數(shù)值最小的一組作為最終聚類結(jié)果[18]。

2.1PCATDKM算法相關(guān)定義

假設(shè)數(shù)據(jù)對(duì)象集合U含有N個(gè)樣本數(shù)據(jù)，樣本數(shù)據(jù)有m個(gè)屬性——m維，則數(shù)據(jù)對(duì)象x可以表示為：x=（x1，x2…xm）。

定義1兩個(gè)m維數(shù)據(jù)對(duì)象x、y的歐式距離公式為：

d[x，y]=（x1-y1）2+…+（xm-ym）2（3）

其中：x1，x2…xm和y1，y2…ym分別表示數(shù)據(jù)對(duì)象x、y的各維數(shù)據(jù);d（x，y）表示數(shù)據(jù)對(duì)象x和y的距離。

定義2數(shù)據(jù)xi與其它每一個(gè)數(shù)據(jù)點(diǎn)的距離和定義為sum[xi][19]：

sum[xi]=∑Nj=1dist[xi，xj]（4）

定義3集合U中的距離和均值定義為avg[U]：

avg[U]=∑Ni=1sum[xi]/N（5）

定義4誤差平方和函數(shù)：

E=∑ki=1∑x=ci|x-mi|2（6）

其中，E是樣本空間所有對(duì)象的平方誤差之和，x是數(shù)據(jù)庫(kù)中屬于類ci的數(shù)據(jù)樣本，mi是類ci中所有樣本的平均值。

2.2PCATDKM算法步驟

輸入：包含N個(gè)對(duì)象的數(shù)據(jù)對(duì)象集合UP×m、聚類個(gè)數(shù)k。

輸出：根據(jù)數(shù)據(jù)對(duì)象特征分成的k個(gè)類別。

算法步驟：

（1）UP×m按式（1）、式（2）計(jì)算相關(guān)系數(shù)矩陣R。

（2）根據(jù)|R-λIm|=0計(jì)算m個(gè)特征值λi。

（3）由貢獻(xiàn)率λi∑mi=1λi確定n個(gè)主成分，得到Dp×n。

（4）利用式（3）計(jì)算兩數(shù)據(jù)點(diǎn)的距離d[x，y]，生成數(shù)據(jù)集合的距離矩陣B;然后利用式（4）計(jì)算出每個(gè)數(shù)據(jù)對(duì)象之間的距離和，用式（5）計(jì)算樣本之間距離和的均值。

（5）從Dp×n中刪除樣本間距離之和大于其均值的噪聲點(diǎn)（孤立點(diǎn)），從而得到新的樣本集合。

（6）更新Dp×n和新生成樣本集合中樣本的距離矩陣B，得到最終的樣本集U1與樣本之間距離的矩陣B1。

（7）調(diào)用genMST（U1，B1），構(gòu)造最小生成樹(shù)T。

（8）根據(jù)權(quán)值降序的方法對(duì)構(gòu)造出的最小生成樹(shù)T進(jìn)行剪枝，剪枝出k-1個(gè)樹(shù)分支，得到k棵子樹(shù)。

（9）計(jì)算所構(gòu)造最小生成樹(shù)T剪枝的k-1棵子樹(shù)中每棵子樹(shù)的算術(shù)均值，記作數(shù)據(jù)中心C[i]，完成初始聚類中心k個(gè)數(shù)據(jù)中心的選取。

（10）選取C[1]加入初始聚類中心集合M中，作為第一個(gè)初始聚類中心k1，計(jì)算數(shù)據(jù)對(duì)象集合U1中所有對(duì)象與k1的距離d。從對(duì)象集合U1中，找出距離初始聚類中心集合M中所有數(shù)據(jù)對(duì)象最遠(yuǎn)的數(shù)據(jù)對(duì)象k2，將k2從集合U1中刪除，并將k2加入到集合M中。

（10）從U1中找出距離初始聚類中心集合M中所有數(shù)據(jù)對(duì)象距離最遠(yuǎn)的數(shù)據(jù)對(duì)象k3，從集合U1中刪除k3，將k3加入到集合M中。

（11）從集合U1中找距離集合M距離最遠(yuǎn)的對(duì)象，直到找到k個(gè)初始中心為止。

（12）從集合M中的k個(gè)中心出發(fā)，將其它對(duì)象分到距離最近的簇，用Kmeans算法進(jìn)行聚類，計(jì)算誤差平方和函數(shù)值E。

（13）從數(shù)據(jù)中心C中選取第二個(gè)均值C[2]作為第一個(gè)聚類中心k1，重復(fù)步驟（6）-步驟（12），直到選取C[k]為第一個(gè)初始聚類中心結(jié)束。

（14）算法結(jié)束。比較每次的誤差平方和函數(shù)值E，從中選取最小的一組作為結(jié)果。

2.3最小生成樹(shù)算法步驟

本文提出的算法基于最小生成樹(shù)以及樹(shù)的剪枝方法將數(shù)據(jù)對(duì)象劃分為k個(gè)類別，其中最小生成樹(shù)算法步驟如下：

Procedure genMST（U，B）

（1）T=NULL;n是U中對(duì)象數(shù)據(jù)個(gè)數(shù)。

（2）Flag[]數(shù)組表示n個(gè)對(duì)象點(diǎn)的訪問(wèn)狀態(tài)，置為false，F(xiàn)lag[0]=true。

（3）repeat。

（4）搜索所有已訪問(wèn)節(jié)點(diǎn)，找出與各個(gè)節(jié)點(diǎn)鏈接的各個(gè)權(quán)值中最小的一條邊dist[i，j]。

（5）將dist[i，j]加入樹(shù)中。

（6）將找出的新節(jié)點(diǎn)訪問(wèn)狀態(tài)標(biāo)記為true。

（7）until搜索出n-1條邊。

（8）return T。

3實(shí)驗(yàn)及結(jié)果分析

3.1PCATDKM算法與各改進(jìn)Kmeans算法對(duì)比

實(shí)驗(yàn)描述：采用專為機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘算法設(shè)計(jì)的公共數(shù)據(jù)庫(kù)UCI數(shù)據(jù)庫(kù)進(jìn)行實(shí)驗(yàn)[20]。在UCI數(shù)據(jù)集中選取4個(gè)數(shù)據(jù)集：yeast、abalone、magic和skin。將PCATDKM算法分別與CFSFDPKM算法、QMCKM聚類算法、KNEKM聚類優(yōu)化算法進(jìn)行聚類準(zhǔn)確率及聚類誤差平方和比較。通過(guò)實(shí)驗(yàn)得到聚類精度、誤差平方和的比較結(jié)果（見(jiàn)表1、表2）。其中HIG表示最高聚類準(zhǔn)確率，LOW表示最低聚類準(zhǔn)確率，AVG表示平均聚類準(zhǔn)確率。

由表1可得，基于PCA的PCATDKM算法聚類效果穩(wěn)定;對(duì)于yeast、abalone、skin數(shù)據(jù)集，PCATDKM算法的聚類準(zhǔn)確率都達(dá)到了85.35%以上，高于其它3種算法;在magic數(shù)據(jù)集上，PCATDKM算法聚類準(zhǔn)確率也達(dá)到了80.63%，優(yōu)于其它3種算法。

由表2可得，在4個(gè)數(shù)據(jù)集上，PCATDKM算法的誤差平方和小于其它3種算法，說(shuō)明PCATDKM算法的聚類效果比其它3種算法好。

綜上所述，PCATDKM算法在傳統(tǒng)的Kmeans算法中增加了PCA、TD與最大最小距離算法。PCA算法能夠?qū)?shù)據(jù)對(duì)象集合進(jìn)行降維，加速聚類過(guò)程。TD算法能夠在選擇初始聚類中心時(shí)根據(jù)數(shù)據(jù)對(duì)象的實(shí)際分布情況進(jìn)行動(dòng)態(tài)選擇，使得通過(guò)聚類算法得到的初始k個(gè)聚類中心與實(shí)際聚類相對(duì)應(yīng)。利用最大最小距離算法在聚類過(guò)程中選取聚類中心使得聚類中心選擇穩(wěn)定，提高了聚類準(zhǔn)確率。PCATDKM算法在數(shù)據(jù)對(duì)象集合聚類過(guò)程中，加速聚類過(guò)程的同時(shí)減少了聚類中的迭代次數(shù)，使得聚類中心更加穩(wěn)定，提高了聚類準(zhǔn)確率和聚類效率，增強(qiáng)了算法的穩(wěn)定性。

4結(jié)語(yǔ)

針對(duì)Kmeans算法在初始k個(gè)聚類中心選取時(shí)采用隨機(jī)選取方法具有聚類結(jié)果不穩(wěn)定的缺陷，本文提出了改進(jìn)PCATDKM算法。改進(jìn)算法利用PCA算法對(duì)數(shù)據(jù)對(duì)象集合進(jìn)行降維，加速聚類過(guò)程。然后利用最小生成樹(shù)算法，在聚類過(guò)程中根據(jù)數(shù)據(jù)對(duì)象的實(shí)際分布情況動(dòng)態(tài)選取k個(gè)初始聚類中心，找出數(shù)據(jù)對(duì)象中分布比較密集的區(qū)域，使得采用本文算法得到的初始聚類中心更具有代表性。利用最大最小距離算法進(jìn)行k次實(shí)驗(yàn)，選取最優(yōu)解，進(jìn)一步提高了聚類準(zhǔn)確率。PCATDKM算法克服了孤立數(shù)據(jù)和噪音數(shù)據(jù)點(diǎn)帶來(lái)的聚類結(jié)果不穩(wěn)定影響。實(shí)驗(yàn)結(jié)果證實(shí)，PCATDKM算法能夠得到較高且穩(wěn)定的準(zhǔn)確率，更適用于對(duì)實(shí)際數(shù)據(jù)的聚類。

參考文獻(xiàn)參考文獻(xiàn)：

[1]馮波，郝文寧，陳剛，等.Kmeans算法初始聚類中心選擇的優(yōu)化[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（14）：182185+192.

[2]鄭丹，王潛平.Kmeans初始聚類中心的選擇算法[J].計(jì)算機(jī)應(yīng)用，2012，32（8）：21862188+2192.

[3]石文峰，商琳.一種基于決策粗糙集的模糊C均值聚類數(shù)的確定方法[J].計(jì)算機(jī)科學(xué)，2017，44（9）：4548+66.

[4]周煒奔，石躍祥.基于密度的Kmeans聚類中心選取的優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究，2012，29（5）：17261728.

[5]王宏杰，師彥文.結(jié)合初始中心優(yōu)化和特征加權(quán)的Kmeans聚類算法[J].計(jì)算機(jī)科學(xué)，2017，44（S2）：457459+502.

[6]陳小雪，尉永清，任敏，等.基于螢火蟲(chóng)優(yōu)化的加權(quán)Kmeans算法[J].計(jì)算機(jī)應(yīng)用研究，2018，35（2）：466470.

[7]王賽芳，戴芳，王萬(wàn)斌，等.基于初始聚類中心優(yōu)化的K均值算法[J].計(jì)算機(jī)工程與科學(xué)，2010，32（10）：105107+116.

[8]李海洋，何紅洲.改進(jìn)人工蜂群優(yōu)化的K均值圖像分割算法[J].智能計(jì)算機(jī)與應(yīng)用，2018，8（3）：4549.

[9]朱曉峰，陳楚楚，尹嬋娟.基于微博輿情監(jiān)測(cè)的Kmeans算法改進(jìn)研究[J].情報(bào)理論與實(shí)踐，2014，37（1）：136140.

[10]李敏，張桂珠.密度峰值優(yōu)化初始中心的Kmeans算法[J].計(jì)算機(jī)應(yīng)用與軟件，2017，34（3）：212217.

[11]莊瑞格，倪澤邦，劉學(xué)藝.基于擬蒙特卡洛的K均值聚類中心初始化方法[J].濟(jì)南大學(xué)學(xué)報(bào)：自然科學(xué)版，2017，31（1）：3541.

[12]熊開(kāi)玲，彭俊杰，楊曉飛，等.基于核密度估計(jì)的Kmeans聚類優(yōu)化[J].計(jì)算機(jī)技術(shù)與發(fā)展，2017，27（2）：15.

[13]張雪鳳，張桂珍，劉鵬.基于聚類準(zhǔn)則函數(shù)的改進(jìn)Kmeans算法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（11）：123127.

[14]翟東海，魚(yú)江，高飛，等.最大距離法選取初始簇中心的Kmeans文本聚類算法的研究[J].計(jì)算機(jī)應(yīng)用研究，2014，31（3）：713715+719.

[15]趙將.基于改進(jìn)Kmeans聚類的推薦方法研究[D].武漢：華中科技大學(xué)，2016.

[16]林海明，杜子芳.主成分分析綜合評(píng)價(jià)應(yīng)該注意的問(wèn)題[J].統(tǒng)計(jì)研究，2013，30（8）：2531.

[17]歐陽(yáng)浩，陳波，黃鎮(zhèn)謹(jǐn)，等.基于Kmeans的最小生成樹(shù)聚類算法[J].組合機(jī)床與自動(dòng)化加工技術(shù)，2014（4）：4144+52.

[18]周海洋，余劍，張衛(wèi)濤.基于最小誤差平方和的無(wú)線傳感器網(wǎng)絡(luò)多邊定位算法[J].傳感器與微系統(tǒng)，2014，33（7）：126128+132.

[19]張靖， 段富.優(yōu)化初始聚類中心的改進(jìn)kmeans算法[J].計(jì)算機(jī)工程與設(shè)計(jì)， 2013， 34（5）：16911694.

[20]傅德勝，周辰.基于密度的改進(jìn)K均值算法及實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用，2011，31（2）：432434.

責(zé)任編輯（責(zé)任編輯：何麗）