劉儒衡

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

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

中圖分類號(hào)：TP181 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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ù)分成若干個(gè)類，使得同一個(gè)類中樣本相似度較高，不同類中的樣本相似度較低。目前，聚類方法在很多領(lǐng)域都有應(yīng)用，包括圖像模式挖掘、商務(wù)推薦、生物基因研究等[2]。常用的聚類算法可以分為基于劃分的聚類、基于層次的聚類、基于密度的聚類、基于網(wǎng)格的聚類和基于模型的聚類等。

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

2 相關(guān)工作

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

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

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

3 相似度指標(biāo)

3.1 相似度指標(biāo)

樣本x到中心點(diǎn)集合C的相似度：

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

3.2 MC-KM算法思想

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)：

[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]. 計(jì)算機(jī)工程， 2014， 40（8）： 205-211.

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

[10] 尹成祥， 張宏軍， 張睿， 等. 一種改進(jìn)的K-Means算法[J]. 計(jì)算機(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.