一種用于多類別劃分的中心點選擇算法

劉儒衡

摘要：傳統(tǒng)的 K-means 算法對初始聚類中心敏感，聚類結(jié)果隨不同的初始輸入而波動。當(dāng)類別數(shù)目較多時，較好的初始聚類中心點集合的選擇更為困難。針對K-means 算法存在的這一問題，該文提出一種用于多類別劃分的中心點選擇算法（MC-KM）。MC-KM通過放大中心點間長距離和短距離的影響的差距，增大短距離的比重，進而選擇一個距離其他中心點都較遠的樣本作為中心點，然后使用傳統(tǒng)K-means進行聚類。理論分析與實驗結(jié)果表明， MC-KM在類數(shù)目較多的數(shù)據(jù)集中能取得更好的聚類結(jié)果，并且具有較好的穩(wěn)定性。

關(guān)鍵詞：聚類；MC-KM；K-means算法；初始中心點；相似度

中圖分類號：TP181 文獻標(biāo)識碼：A 文章編號：1009-3044（2018）12-0188-03

Abstract： The traditional K-means algorithm is sensitive to the initial clustering center， and the clustering results fluctuate with different initial inputs. When the number of categories is large， it is more difficult to choose a good initial cluster center set. Aiming at the problem of K-means algorithm， a central point selection algorithm （MC-KM） for multi class partition is proposed in this paper. By enlarging the gap between the long distance and the short distance between the center points， MC-KM increases the proportion of the short distance， and then selects a sample which is far away from the other center points as the center point， and then uses the traditional K-means to cluster. Theoretical analysis and experimental results show that MC-KM can achieve better clustering results in a large number of data sets， and has better stability.

Key words：cluster； MC-KM；K-means algorithm； initialized clustering centers； similarity

1 背景

聚類[1]是一種無監(jiān)督學(xué)習(xí)方法，它將數(shù)據(jù)分成若干個類，使得同一個類中樣本相似度較高，不同類中的樣本相似度較低。目前，聚類方法在很多領(lǐng)域都有應(yīng)用，包括圖像模式挖掘、商務(wù)推薦、生物基因研究等[2]。常用的聚類算法可以分為基于劃分的聚類、基于層次的聚類、基于密度的聚類、基于網(wǎng)格的聚類和基于模型的聚類等。

K-means聚類是一種基于劃分的聚類方法。該算法采用自下而上的聚類結(jié)構(gòu)，具有簡單、速度快等優(yōu)點，但傳統(tǒng)K-means算法初始聚類中心的選擇對聚類結(jié)果有較大的影響，一旦初始中心點選擇的不好，可能無法得到有效的聚類結(jié)果。針對K-means算法的初始中心點選擇困難以及聚類過程中存在的問題，該文從三個方面進行改進，一是定義新的相似度指標(biāo)進行類中心點選擇；二是多次選擇中心點集合，選擇相似度最低的中心點集合作為初始中心點集合；三是在聚類過程中，根據(jù)相似度剔除錯誤中心點，并重新選擇更優(yōu)的中心點。

2 相關(guān)工作

傳統(tǒng)K-means 算法首先從數(shù)據(jù)集D中隨機選擇k個樣本，每個樣本代表一個類的初始中心點，根據(jù)距離將D中剩余樣本分配到最近的類中，然后以一類中所有樣本點均值作為各類新的中心點，重新分配D中對象，迭代該過程直到各個類的中心不再變化，得到k個互不相交的穩(wěn)定的類。

K-means算法是一個局部搜索過程，其聚類結(jié)果依賴于初始聚類中心以及初始劃分[2]， 并且 K-means算法的最終結(jié)果只是相對于初始劃分更好，未必是全局最優(yōu)的劃分[3]。為了找到更好的中心點，諸多學(xué)者做了許多研究。Katsavounidis等人[4]提出基于最大最小法的初始中心點選擇方法，該方法隨機選取第一個中心點，其他中心點通過定義的最大最小指標(biāo)進行選取。Erisoglu[5]等人通過定義的主軸進行中心點選擇，初始中心由兩個主軸確定，第一個初始中心為到主軸均值距離最大的樣本。Wang[6]利用相異度矩陣構(gòu)造哈夫曼樹，從而選擇 K-means算法的初始中心點。Bertalmio等[7]人提出確定性的聚類中心算法，根據(jù)樣本的局部密度進行中心點的選擇，取得了較好的效果。謝等人[8]通過樣本方差進行中心點的選擇。選擇方差小且相距一定距離的樣本作為初始中心點。錢等人[9]利用譜方法估計特征中心得到 K-means算法的初始聚類中心。尹等人[8]采取數(shù)據(jù)分段方法，將數(shù)據(jù)點根據(jù)距離分成k段，在每段內(nèi)選取一個中心作為初始中心點，進行迭代運算。為了自動確定中心點的個數(shù)， Haslbeck等人[12]基于不穩(wěn)定性方法進行估計類數(shù)目。?alik等人[9]考慮了數(shù)據(jù)的緊湊度和重疊度完成類別劃分。Capó等人[10]提出一種用于海量數(shù)據(jù)下的均值近似計算方法。等人將k均值算法應(yīng)用于圖像和視頻中文本信息挖掘。Khanmohammadi等人[11]提出了一個結(jié)合調(diào)和均值和重疊的混合方法k-均值的算法來解決醫(yī)療數(shù)據(jù)類別重疊的問題。Yeh等人[12]再KHM算法基礎(chǔ)上提出快速集中化策略來提高收斂速度和最小的運動策略，有效地搜索更好的解決方案，而不陷入局部最優(yōu)。Amorim等人[13]采用分布式加權(quán)質(zhì)心的方法進行分布式k均值聚類直觀的反應(yīng)不同程度的不同集群的關(guān)聯(lián)。Gan等人[14]采用k-mean進行離群點檢測。Oliveira等人[15]采用加權(quán)特征空間的k-均值算法進行Terahertz圖像的分割聚類。

通過點的密度、點的局部方差[16]、譜方法[17]進行中心點的選擇都是確定性的方法，算法需要計算額外的信息，將算法時間復(fù)雜度變?yōu)镺（n2）。在不改變時間復(fù)雜度情況下，單純使用距離[18]的算法穩(wěn)定性較差。該文提出DKM算法采用獨特的相似度指標(biāo)選擇進行初始中心點的選擇，在聚類的過程通過重選替換操作刪除錯誤選擇的中心點，來提高算法的容錯率。DKM初始中心點選擇與傳統(tǒng)K-means相比較，不但在準(zhǔn)確率等指標(biāo)有所提高，而且大幅提高了算法的穩(wěn)定性。在類別數(shù)目較多時，算法的聚類效果顯著提高且相對穩(wěn)定。

3 相似度指標(biāo)

3.1 相似度指標(biāo)

樣本x到中心點集合C的相似度：

其中，[dx，c=x-cTx-c]為樣本x到中心點c的距離。[λ]為放大倍數(shù)。相似度指標(biāo)是在每個距離倒數(shù)基礎(chǔ)上的進行[λ]倍放大。放大的目的是加大長短距離影響的差距，使長距離在求和中的作用變小，短距離在求和中的作用變大；當(dāng)樣本點距離某一中心點很近時，該距離在相似度指標(biāo)中的作用占據(jù)主導(dǎo)地位。

3.2 MC-KM算法思想

該節(jié)介紹提出的改進的中心點選擇算法MC-KM。MC-KM主要工作工作包括兩個部分，第一部分根據(jù)公式（1）中相似度進行初始中心點選擇；第二部分k次選擇中心點集合，選擇最優(yōu)的中心點集合作為初始中心點集合。

為了更好地描述，稱中心點集合中第一個被選擇的中心點為衍生點。由一個衍生點出發(fā)可以得到一個中心點集合。算法首先確定一個樣本x作為衍生點，并將x加入C，然后根據(jù)公式（1）計算每個樣本與C的相似度，選擇相似度最小的樣本點加入集合C，直至C容量為k。

由于第一個點的隨機選擇，因此不能保證C為最優(yōu)的中心點集合。為衡量集合的優(yōu)劣，該文提出集合C內(nèi)相似度指標(biāo)。定義集合C的內(nèi)部相似度為：

其中，C為容量k的中心點集合。該指標(biāo)描述中心點c∈C與集合C-{c}的相似度之和。

若要得到最優(yōu)的中心點集合，需要每個樣本點作為衍生點，衍生出中心點集合，選擇內(nèi)部相似度最小的中心點集合，但這種方法時間復(fù)雜度為O（k2n2）。該文算法進行k次中心點集合選擇，第1次衍生點隨機選擇，第i次衍生點為第i-1次衍生點距離最遠的樣本點，以此保證前后兩次選擇所采用衍生點屬于不同類。由此衍生k次得到k個中心點集合，選擇集合內(nèi)部相似度最小的作為初始中心點集合。初始中心點的選取步驟描述如表1所示：

3.3 合成數(shù)據(jù)集上實驗結(jié)果與分析

合成數(shù)據(jù)能夠比較直觀的表達展示算法的結(jié)果，本節(jié)采用三個類別相對較多的合成數(shù)據(jù)集來驗證上訴選擇和調(diào)整策略的有效性，并進行相應(yīng)的分析。實驗中采用的三個數(shù)據(jù)集分別為R15[19]、D31[19]、S-set1[20]，如圖1所示，R15有15個類，每個類別大小、形狀相似，且位置分布相對均勻；D31數(shù)據(jù)集有31個類，類別大小相差不大，位置分布相對雜亂；S-set1數(shù)據(jù)集有15個類，類別形狀差別相對較大。

圖1展示的是在數(shù)據(jù)集R15、D31、S-set1上選取的初始中心點。在R15數(shù)據(jù)集上，該文算法給每個類都選擇到了一個正確的初始中心點，對于類別明確的數(shù)據(jù)，算法很好的選擇出了初始中心點；在D31數(shù)據(jù)集和S-set1數(shù)據(jù)集上，雖然類比數(shù)目較多，分布雜亂，并且有些類距離很近，但是通過該文提出的指標(biāo)仍然給出很好的初始中心點。僅有個別點受邊界點和噪聲點影響，中心點選擇偏離相對較遠。

圖2展示的是在數(shù)據(jù)集R15、D31、S-set1上最終的聚類結(jié)果。在R15數(shù)據(jù)集上，由于正確選擇初始中心點，因此能夠正確聚類；在D31數(shù)據(jù)集和S-set1數(shù)據(jù)集上，雖然個別點選擇錯誤，但通過選擇調(diào)整策略，仍然得到正確的聚類結(jié)果。

3.4 真實數(shù)據(jù)集上實驗結(jié)果與分析

該節(jié)在準(zhǔn)確率、F值和標(biāo)準(zhǔn)化互信息NMI三個指標(biāo)上對算法（MC-KM）與傳統(tǒng)K-means算法（ORI-KM） 進行比較，來證明MC-KM的有效性。實驗使用的數(shù)據(jù)集均來自于UCI數(shù)據(jù)庫。

由圖表2 的實驗結(jié)果可以看出，MC-KM算法效果明顯優(yōu)于傳統(tǒng)K-means算法。其中，iris和wine數(shù)據(jù)集都有兩個類，MC-KM在三個指標(biāo)上略有提升；而在Computer Hardware數(shù)據(jù)集上有5個類，Dermatology數(shù)據(jù)集有6個類，optdigits數(shù)據(jù)集上有10個類，MC_KM算法在這三個數(shù)據(jù)集上算法效果大幅提升，說明MC-KM算法的有效性。

4 結(jié)束語

傳統(tǒng)K-means算法對于類別較多的數(shù)據(jù)初始中心點選擇困難，且算法穩(wěn)定性差，現(xiàn)有很多關(guān)于K-means的改進算法都需要獲取額外的數(shù)據(jù)信息，算法時間復(fù)雜度為O（n2）。該文針對這一問題，提出了基于新的相似度指標(biāo)的中心點選擇策略，提高了算法的穩(wěn)定性和準(zhǔn)確率。在經(jīng)典的人工數(shù)據(jù)集和UCI數(shù)據(jù)集上的實驗結(jié)果表明，算法在多類別數(shù)據(jù)上更容易得到較好聚類中心點和最終結(jié)果。

參考文獻：

[1] Han J， Kamber M. Data Mining： Concepts and Techniques， Morgan Kaufmann[J]. Machine Press， 2006， 5（4）： 394-395.

[2] Chan B T F， Shen J. Non-texture inpainting by curvature driven diffusions[C] （CDD）. J. Visual Comm. Image Rep， 2010.

[3] Pe?a J M，LozanoJ A，Larra?aga P. An empirical comparison of four initialization methods for the K-Means algorithm[J]. Pattern Recognition Letters， 1999， 20（10）： 1027-1040.

[4] Faber V. Clustering and the continuous K-means algorithm[J]. Los Alamos Science， 1994（22）： 138-144.

[5] Erisoglu M， Calis N， Sakallioglu S. A new algorithm for initial cluster centers in k-means algorithm[J]. Pattern Recognition Letters， 2011， 32（14）： 1701-1705.

[6] Wang S. An improved k-means clustering algorithm based on dissimilarity[C]// International Conference on Mechatronic Sciences， Electric Engineering and Computer， 2013： 2629-2633.

[7] Bertalmio M， Vese L， Sapiro G， et al. Simultaneous structure and texture image inpainting.[J]. IEEE Transactions on Image Processing A Publication of the IEEE Signal Processing Society， 2003， 12（8）： 882-900.

[8] 謝娟英， 王艷娥. 最小方差優(yōu)化初始聚類中心的K-means算法[J]. 計算機工程， 2014， 40（8）： 205-211.

[9] 錢線， 黃萱菁， 吳立德. 初始化K-means的譜方法[J]. Acta Automatica Sinica， 2007， 33（4）： 342-346.

[10] 尹成祥， 張宏軍， 張睿， 等. 一種改進的K-Means算法[J]. 計算機技術(shù)與發(fā)展， 2014（10）： 30-33.

[11] Yeh W C， Lai C M， Chang K H. A novel hybrid clustering approach based on K-harmonic means using robust design[J]. Neurocomputing， 2016， 173（P3）： 1720-1732.

[12] Haslbeck J M B， Wulff D U. Estimating the Number of Clusters via Normalized Cluster Instability[EB/OL].http：//sciencewise.info/articles/1608.07494/.

[13] ?alik K R， ?alik B. Validity index for clusters of different sizes and densities[J]. Pattern Recognition Letters， 2011， 32（2）： 221-234.

[14] Aradhya V N M， Pavithra M S. A comprehensive of transforms， Gabor filter and k -means clustering for text detection in images and video[J]. Applied Computing & Informatics， 2016， 12（2）： 109-116.

[15] Khanmohammadi S， Adibei N， Shanehbandy S. An Improved Overlapping k-Means Clustering Method for Medical Applications[J]. Expert Systems with Applications， 2017（67）： 12-18.

[16] Amorim R C D， Makarenkov V. Applying subclustering and L p， distance in Weighted K-Means with distributed centroids[J]. Neurocomputing， 2016， 173（3）： 700-707.

[17] Gan G， Ng K P. k-means clustering with outlier removal[M]. Elsevier Science Inc， 2017.

[18] Oliveira G V， Coutinho F P， Campello R J G B， et al. Improving k -means through distributed scalable metaheuristics[J]. Neurocomputing， 2017（246）： 45-57.

[19] Veenman C J， Reinders M J T， Backer E. A Maximum Variance Cluster Algorithm[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence， 2002， 24（9）： 1273-1280.

[20] Fr?nti P， Virmajoki O. Iterative shrinking method for clustering problems[J]. Pattern Recognition， 2006， 39（5）： 761-775.

[21] Capó M， Pérez A， Lozano J A. An efficient approximation to the K -means clustering for massive data[J]. Knowledge-Based Systems， 2017（117）： 56-69.