針對Kmeans初始聚類中心優(yōu)化的PCATDKM算法

劉榮凱 孫忠林

摘要：Kmeans算法在聚類過程中隨機(jī)選取k個初始聚類中心，容易造成聚類結(jié)果不穩(wěn)定。針對該問題，提出PCATDKM算法：使用主成分分析法對數(shù)據(jù)對象集合的屬性進(jìn)行降維，提取出主屬性，去掉無關(guān)屬性，從而加速聚類過程;基于最小生成樹算法及樹的剪枝方法將數(shù)據(jù)對象劃分為k個初始聚類簇，然后進(jìn)行剪枝生成k棵子樹，計算每棵子樹中所有數(shù)據(jù)對象的均值，作為初始聚類中心;利用基于密度與最大最小距離的算法思想進(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

中圖分類號：TP312

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

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

1主成分分析算法

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

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

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

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

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

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

定義2數(shù)據(jù)xi與其它每一個數(shù)據(jù)點的距離和定義為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是樣本空間所有對象的平方誤差之和，x是數(shù)據(jù)庫中屬于類ci的數(shù)據(jù)樣本，mi是類ci中所有樣本的平均值。

2.2PCATDKM算法步驟

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

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

算法步驟：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3最小生成樹算法步驟

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

Procedure genMST（U，B）

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

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

（3）repeat。

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

（5）將dist[i，j]加入樹中。

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

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

（8）return T。

3實驗及結(jié)果分析

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

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

由表1可得，基于PCA的PCATDKM算法聚類效果穩(wěn)定;對于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個數(shù)據(jù)集上，PCATDKM算法的誤差平方和小于其它3種算法，說明PCATDKM算法的聚類效果比其它3種算法好。

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

4結(jié)語

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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