針對Kmeans初始聚類中心優化的PCATDKM算法

劉榮凱 孫忠林

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

關鍵詞：

Kmeans算法;主成分分析法;聚類;聚類準確率

DOIDOI：10.11907/rjdk.182064

中圖分類號：TP312

文獻標識碼：A文章編號文章編號：16727800（2018）009008503

英文標題PCATDKM Algorithm for Kmeans Initial Clustering Center Optimization

——副標題

英文作者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.

英文關鍵詞Key Words：Kmeans algorithm; principal component analysis; clustering; accuracy of clustering

0引言

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

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

1主成分分析算法

主成分分析算法[16]的思想是：對各維數據進行分析，提取并合成數據對象中無相關性的主要屬性，用主要屬性代表數據對象集中的原有屬性。使用主成分分析法能夠有效降低數據對象集合中的無關屬性，大幅提高聚類運算效率及聚類準確率。

標準化變換公式：

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

其中，xj=∑pi=1xijp，sj=∑pi=1（xij-xj）p-1。xij表示矩陣中每個樣本值，zij表示標準化矩陣，xj表示列均值，sj表示列標準差。

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

其中，rij=∑zkj.zkjp-1，i，j=1，2…m;R為相關系數矩陣;x為隨機向量;m為維數;zT表示標準化矩陣z的轉置。

2PCATDKM算法

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

2.1PCATDKM算法相關定義

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

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

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

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

定義2數據xi與其它每一個數據點的距離和定義為sum[xi][19]：

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

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

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

定義4誤差平方和函數：

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

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

2.2PCATDKM算法步驟

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

輸出：根據數據對象特征分成的k個類別。

算法步驟：

（1）UP×m按式（1）、式（2）計算相關系數矩陣R。

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

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

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

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

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

（7）調用genMST（U1，B1），構造最小生成樹T。

（8）根據權值降序的方法對構造出的最小生成樹T進行剪枝，剪枝出k-1個樹分支，得到k棵子樹。

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

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

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

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

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

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

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

2.3最小生成樹算法步驟

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

Procedure genMST（U，B）

（1）T=NULL;n是U中對象數據個數。

（2）Flag[]數組表示n個對象點的訪問狀態，置為false，Flag[0]=true。

（3）repeat。

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

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

（6）將找出的新節點訪問狀態標記為true。

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

（8）return T。

3實驗及結果分析

3.1PCATDKM算法與各改進Kmeans算法對比

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

由表1可得，基于PCA的PCATDKM算法聚類效果穩定;對于yeast、abalone、skin數據集，PCATDKM算法的聚類準確率都達到了85.35%以上，高于其它3種算法;在magic數據集上，PCATDKM算法聚類準確率也達到了80.63%，優于其它3種算法。

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

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

4結語

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

參考文獻參考文獻：

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

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

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

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

[5]王宏杰，師彥文.結合初始中心優化和特征加權的Kmeans聚類算法[J].計算機科學，2017，44（S2）：457459+502.

[6]陳小雪，尉永清，任敏，等.基于螢火蟲優化的加權Kmeans算法[J].計算機應用研究，2018，35（2）：466470.

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

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

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

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

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

[12]熊開玲，彭俊杰，楊曉飛，等.基于核密度估計的Kmeans聚類優化[J].計算機技術與發展，2017，27（2）：15.

[13]張雪鳳，張桂珍，劉鵬.基于聚類準則函數的改進Kmeans算法[J].計算機工程與應用，2011，47（11）：123127.

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

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

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

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

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

[19]張靖， 段富.優化初始聚類中心的改進kmeans算法[J].計算機工程與設計， 2013， 34（5）：16911694.

[20]傅德勝，周辰.基于密度的改進K均值算法及實現[J].計算機應用，2011，31（2）：432434.

責任編輯（責任編輯：何麗）