一種有效的均值聚類初始化方法

張魯營，趙曉凡

（北京交通大學計算機與信息技術學院，北京　100044）

一種有效的均值聚類初始化方法

張魯營，趙曉凡

（北京交通大學計算機與信息技術學院，北京100044）

聚類算法是用來提取有用信息的重要技術，k均值聚類算法是其中應用最為普遍的聚類分析算法。然而，這種聚類算法的主要問題是，最終的聚類結果高度依賴于初始聚類中心。標準的k均值聚類算法使用隨機初始中心會得到很差的聚類結果。因此，為了克服標準k-均值聚類算法的不足，本文提出一種基于貢獻率的方法來優化初始中心的選擇，以便得到一個好的聚類結果。將新提出的初始化方法應用到一些知名的數據集，將其與幾種傳統的初始化算法相比較，證明新提出的初始化方法具有良好的性能。本文所提出的方法不僅容易理解，而且聚類的迭代次數和執行時間也明顯下降。本文的初始化方法可以保證得到一個比較好的聚類結果。

數據挖掘；k均值聚類；初始中心

0　引 言

數據挖掘是一種可在不同類型數據集上發現、并提取隱藏有用信息的過程。同時，聚類則是一種無監督的分類學習算法。而聚類分析即在數據挖掘中發揮著重要作用，已然廣泛進入各種實際應用領域，如工程、生物學、心理學、醫學和計算機視覺等［1］。聚類算法的主要任務是依據相似性進行分類，以便使得相似的數據在同一類，不相似的數據在不同類。一個優秀的聚類分析算法會產生比較合適的聚類結果，在這個結果中類內有很高的相似性而類間的相似性比較低。

近年來，聚類分析已成為學界研究熱點［2］。因此，大量的聚類算法［3-5］即獲提出，并用于數據分析，從而提取有用的信息。傳統的聚類分析方法主要有以下幾種：層次聚類算法，網格聚類算法、基于密度的聚類算法和基于劃分的聚類算法。具體地，層次聚類是將數據集合進行層次的分解，建立一個層次結構，但層次聚類算法的時間復雜性太高。網格聚類算法則是使用有限數量的數據元素，最終形成一個網格結構。此外，基于密度的算法卻必須定義參數的閾值，因而難以保證獲得一個滿意的聚類結果。然而，基于劃分的聚類算法有較低的復雜度，不需要定義許多參數。因此，該算法隨即成為具有高度普適性的實用聚類算法。

k-均值聚類分析算法是時下居于主導的常用劃分聚類算法［6］。k均值聚類算法的主要優點是簡單和快速，而且適用于大部分的數據集合。但k均值聚類算法也有如下缺點與不足。首先，必須預先確定集群的數量。然而，集群的數量確定通常來說卻并不容易。其次，k均值聚類算法的結果受初始聚類中心的影響，不同初始值的選擇將出現多重各異的聚類結果。因此有必要針對k均值聚類算法的缺點展開深入改進研究。本文主要討論了如何選擇有效的初始中心，基于此而使得k均值聚類算法能夠獲得最佳聚類結果。

1　常用的初始化算法

k均值聚類算法的實現主要分為2個步驟：首先，必須選擇k個中心，然后是把給定的數據集中每個數據點分配到與其關聯的最近的聚類中心。但仍需指出，這種聚類算法的主要缺點是算法結果高度依賴于初始聚類中心的選擇。k-均值聚類算法的關鍵是對初始聚類中心的選擇。在這一部分中，則將重點介紹幾種常用的初始化方法。

在數據挖掘中，k-means++是一個選擇初始聚類中心的算法。這是一個基于密度的初始化方法，并于2007年由戴維亞瑟和謝爾蓋首次提出［7］。該算法的設計實現過程是先隨機選擇第一個初始聚類中心，隨后的每個聚類中心均是選擇剩余的數據點的距離概率較大的點。實施此種改進的目的是避免選擇2個彼此接近的聚類中心。但是，該初始化方法的缺點經過研究可知卻是，聚類結果將是不唯一的，因為第一個初始聚類中心是由隨機選擇而得。如此，將無法保證每個初始化質心的聚類都能得到最佳結果。

另有一種選擇初始中心的新方法叫做KKZ方法［8］，這種初始化質心的方法選擇最寬的距離作為第一個初始聚類中心的向量，然后計算剩余的訓練數據集，并選擇距離最小的、直至滿足要求的K個初始聚類中心。這種方法具有相當的優勢：一方面，這種初始選擇質心的方法很容易理解，因而可以簡捷實現這個初始化方法。另一方面，還可以適用于廣泛的數據集。而且，這種方法并不需要定義閾值。只是，如果一旦使用這個初始化方法，可能會發現比較差的初始聚類中心，因為選擇的數據集合有時會有離群數據向量。

不僅如此，拉赫曼等人［9］又介紹了計算k均值聚類算法初始中心的新方法。這是基于排序算法的初始化的方法。首先，計算數據集上的每個數據點每一行的總和，然后依據得分和的大小排列數據集合，將排序后的數據集合分成k個子集，計算每個子集中的均值作為初始質心，這種初始化的方法不僅可以得到優良的初始質心，而且時間復雜度也比較低。此外，依據最近鄰來選擇初始質心也是一種常見的方法［10］，但是依據最近鄰選擇初始質心的時間復雜度比較高，并且對大量的數據集合也并不適用。

基于此，針對現有聚類中心初始化方法計算復雜度高、對離群點敏感等問題，本文提出了一種新的基于貢獻率的聚類中心初始化方法：CRCC算法。這種初始化的方法時間復雜性比較小而且不會因為離群點而影響實驗結果。該初始化方法可以幫助k均值聚類的算法得到一個更好的聚類結果。

2　優化初始質心k均值聚類

2.1相關分析

聚類分析是機器學習的經典問題之一［11］。k均值聚類分析算法更是當下最為典型的基于劃分的聚類算法，具體是在1967年由杰姆斯等人［12］最初提出的。k均值聚類算法旨在劃分N個數據點X=｛x1，x2，…，xn｝，分成k個子集S=｛s1，s2，…，sk｝，以減少平方誤差和。平方誤差和的定義可做如下表述：

其中，uj是Sj的均值。k均值聚類算法性能的關鍵就是初始聚類中心的合理選取。但目前對于初始聚類中心的選擇并未研發推出一個最佳方法來解決這個問題，即不能保證全局最優并且得到最好的聚類結果。同時，這是一個NP問題。在本文中，研究將引入一個新的啟發式方法來選擇初始聚類中心，并會產生更好的聚類結果。

綜上研究可知，在已有的k-均值聚類算法中，使用初始聚類中心是隨機的，而k-均值聚類算法的性能較差。為此，本文提出了一種基于貢獻率的初始化新方法用來確定k均值聚類算法的初始質心，以便得到一個優質高效的聚類結果。新算法重點是基于排序，并且可以選擇更好的初始聚類中心，而不是隨機選擇。

2.2優化初始質心k均值聚類

2.2.1CRCC算法

新方法的步驟為：首先對數據點的貢獻進行排序，再將排序后的數據集分成若干個子集，并以此為基礎計算每個子集的平均值，選擇這些平均值作為初始聚類中心。

初始質心的選擇算法執行流程可做如下概括描述：

輸入：X=｛x1，x2，…，xn｝，k

輸出：k個初始質心

1）計算數據集合中每一列的和，將數據點此列對應值除以這一列的總和獲得單列貢獻率；然后將這一行所有的貢獻率的絕對值相加即獲得這個數據點的貢獻率；

2）根據貢獻率的值將數據集合進行排列；

3）將排列好的數據集合分成k個子集；

4）計算每一個子集的均值；

上述算法主要是用于選擇初始質心，該方法與已有的k均值算法選擇初始質心不同，該初始聚類中心是根據排序算法計算所得。新方法的性能比已有的k均值聚類算法要更顯優越，使用該方法進行聚類能夠獲得更快的收斂速度。此外，這是一個線性確定初始聚類中心的方法，相對于其他的初始化方法，時間復雜性將會顯著降低。

在使用上述初始質心的選擇算法得到初始質心之后，接下來數據點則要分配到對應的數據聚類中。分配后，每個數據點和對應類中的聚類中心有著最小的距離。因此數據點和聚類中心之間要根據距離來計算相似性，歐式距離是一種常見實用的聚類計算方法。假設有2個數據向量X=｛x11，x12，…，x1n｝，Y=｛y12，y22，…，yn2｝，歐式距離的計算公式如式（2）所示。

2.2.2分配數據點到聚類

分配數據點的算法［13］可以描述如下：

輸入：X=｛x1，x2，…，xn｝，C=｛c1，c2，…，ck｝（初始質心）

輸出：S=｛s1，s2，…，sk｝

1）計算聚類中心和數據集合中數據點之間的歐式距離；

“S就是這樣跟小說家說的。現在，他們的婚姻進入了倒計時，卻在身體上放縱如世界末日之前的狂歡。S很心虛，不敢拒絕，擔心激怒曲，又憐惜她。婚姻大廈的柱礎已斷裂，墻基在下陷，屋瓦在抖落，隨時都會分崩離析，而她還要在大廈將傾之際，醉生夢死，一絲不茍地完成性事。曲說，你不是喜歡這個嗎？把欠你的全補上。”

2）將數據向量分配給對應的聚類，在該聚類中數據向量和聚類中心有最小距離；

3）重新選擇聚類中心；

4）重復步驟2）和3），直到滿足誤差平方和最小。

3　實驗結果

在這一節中，主要是仿真實現本文提出的初始化新方法，并將這種初始化方法的聚類結果與其他幾種較為常用的初始化方法聚類結果進行比較。其中，使用的實驗工具是MATLAB R2008a，實驗數據是UCI上頻繁選用的實驗數據集合。在實驗中，首先，必須定義數量集群的量值，無論是標準的k均值聚類算法還是優化的初始質心的聚類算法，下面將通過逐步分析驗證提出的初始化質心新方法的有效性。

3.1數據集合的介紹

本文中，數據集是用來比較初始化算法的有效性。主要是將新提出的初始化算法和其他常用的初始化算法形成結果參照。如表1所示，即將本文算法中使用的數據集給出了一個整體介紹，重點列出了4個方面來描述數據集合：數據集的名稱、數據點的個數、屬性的數目和類別數目。

3.2實驗結果和討論

在本節中，研究將使用不同的初始化方法實現聚類結果的比較。具體來講，k均值采用了隨機初始聚類中心的聚類算法、k-均值++算法、SSE方法、最近鄰的方法還有新提出的初始化方法。對于原始的隨機算法則將采用10次的平均值作為實驗的結果，因為初始質心的隨機性使得若采用平均值，就可以提升實驗結果的準確性。實驗結果如表2所示。

下面，研究又用Rand Index的值來驗證新的初始化方法的有效性，實驗結果如表3、表4所示。

表1　數據集合Tab.1 Dataset

表2　誤差平方和的結果Tab.2 Sum of squared errors

表3　指數Tab.3 Rand Index

表4　執行時間Tab.4 Execution time

在上述實驗過程中，k均值使用新提出的初始化方法與原方法及其他的初始化方法展開了結果比較和處理分析。k均值聚類算法和k均值++算法運行10次取均值作為實驗結果，保證了聚類算法在實驗過程中的準確性。在表2～表4中，分別通過不同的聚類標準針對新提出的方法進行了有效性驗證，從實驗結果表中可以看到新提出的初始化方法進行k均值聚類所得的實驗結果比其他的初始化的方法得到的實驗結果要呈現明顯優勢，不僅可以減少聚類時間降低時間復雜度，還可以得到更好的聚類結果。由此可知，新提出的k均值聚類質心的選擇方法是有效、且可行的。

從實驗過程的發生和完成中，能夠發現新的初始化方法的優點。首先，原始k均值聚類算法的初始質心是隨機選擇的，并不能保證實驗的穩定性，但新算法的初始聚類中心的選擇是自動計算的，而且又是唯一的，從而提高了k均值聚類算法實驗結果的穩定性。其次，新初始質心的實驗過程簡潔易懂，降低了時間復雜性，同時更能保證獲得較好的實驗結果。此外，新提出的初始化方法不需要任何參數作為輸入得到的結果，因此，這就可以提高k均值聚類算法的實驗結果的準確性和穩定性。最后，以新提出的方法來選擇初始聚類中心在實現上具有高度可行性，而其特性呈現則是一個線性方法。總之，新提出的初始化算法是非常有效的，可以精準選擇并確定k均值聚類的初始中心。

4　結束語

本文給出了一個新的初始化算法，k均值聚類分析算法是一種在數據挖掘中成功、且普及常用的聚類算法。標準的k均值聚類的初始聚類中心是隨機選擇的，使得聚類結果高度依賴于初始聚類中心，因此，標準的k均值聚類算法的性能仍有待提升。需要研制提出新的方法來選擇初始聚類中心得到了學界高度重視，也必將提高k-均值聚類算法的有效性并獲得良好的聚類結果。在本文中，提出了一種新的基于貢獻率的方法來尋找聚類中心。利用該方法選擇不同的數據集合進行測試，并采用不同的評價標準分析實驗結果，結果表明所提出的初始化方法對聚類結果實現了明顯改進，而且新提出的初始化的方法還表現了諸多優點，主要有復雜性比較低、簡單易懂、不受離群點的影響等。

進一步地，后續工作主要是針對k均值聚類算法的另一個缺點，就是標準的k均值算法的結果受輸入k值的影響而需要展開深入研究設計。在聚類過程中，研究必須預先定義k的值。預計未來將可找到一個新方法來計算k的值。

［1］KATHIRESAN V，SUMATHI P.An efficient clustering algorithm based on z-score ranking method［C］//International Conference on ComputerCommunicationandInformatics（ICCCI）2012. Coimbatore，INDIA：IEEE，2012：1-4.

［2］CELEBI M E，KINGRAVI H A，VELA P A.A comparative study of efficient initialization methods for the k-means clustering algorithm［J］.Expert Systems with Applications，2013，40（1）：200-210.

［3］RUNKLER T A.Partially supervised k-harmonic means clustering［C］//Computational Intelligence and Data Mining（CIDM）2011. Paris：IEEE，2011：96-103.

［4］BEZDEK J C，EHRLICH R，FULL W.Fcm：The fuzzy c-means clustering algorithm［J］.Computers&Geosciences，1984，10（2）：191-203.

［5］SHI Na，LIU Xumin，GUAN Yong.Research on k-means clustering algorithm：An improved k-means clustering algorithm［C］//Third International Symposium on Intelligent Information Technology and Security Informatics（IITSI）2010.Jian，China：IEEE，2010：63-67.［6］FAHIM A M，SALEM A M，TORKEY F A，et al.An efficient kmeans with good initial starting points［J］.Georgian Electronic ScientificJournal：ComputerScienceandTelecommunications，2009，2（19）：47-57.

［7］ARTHUR D，VASSILVITAKII S.k-means++：The advantages of careful seeding［C］//Proceedings of the eighteenth annual ACMSIAM symposium on Discrete algorithms 2007.USA：Society for Industrial and Applied Mathematics，2007：1027-1035.

［8］KATSAVOUNIDIS I，KUO C C J，ZHANG Zhen.A new initialization technique for generalized lloyd iteration［J］.Signal Processing Letters，IEEE，1994，1（10）：144-146.

［9］RAHMAN M M，AKHTAR M N.A modified approach for selecting optimal initial centroids to enhance the performance of k-means［C］//NCICIT 2013.Bangladesh：CUET，2013：117-121.

［10］KETTANI O，TADILI B，RAMDANI F.A deterministic k-means algorithm based on nearest neighbor search［J］.International Journal of Computer Applications，2013，63（15）：33-37.

［11］ONODA T，SAKAI M，YAMADA S.Careful seeding method based on independent components analysis for k-means clustering［J］. Journal of Emerging Technologies in Web Intelligence，2012，4（1）：51-59.

［12］MACQUEEN J.Some methods for classification and analysis of multivariate observations［C］//Proceedings of the fifth Berkeley symposium on mathematical statistics and probability 1967.Oakland：IEEE，1967：281-297.

［13］MARIAMMA D，GOWTHAMI M，SINDHUJAA N.New algorithm to get the initial centroids of clusters on multidimensional data［J］. IJREAT International Journal of Research in Engineering&Advanced Technology，2013，1（1）：1-4.

An efficient initialization method for the K-means clustering algorithm

ZHANG Luying，ZHAO Xiaofan
（School of Computer and Information Technology，Beijing Jiaotong University，Beijing 100044，China）

Cluster analysis is one of the important data mining techniques to extract useful information and the k-means clustering algorithm is one of the most common used cluster analysis algorithms for many practical applications.However，the main problem of this clustering algorithm is that the final clustering result highly depends on the initial cluster centers.Standard k-means clustering algorithm using random initial centers has a poor performance.Hence，to overcome the sensible of standard k-means clustering algorithm，this paper proposes a new algorithm for optimizing the selection of initial centers to make the k-means clustering algorithm more effective.The new proposed initialization method of k-means clustering algorithm is tested on some well-known data sets which are taken from UCI machine learning repository.According to the comparision of experiment results between standard k-means clustering algorithm and new proposed method，it shows that the new proposed method has a good performance.The results of proposed method are not only easy to understand but also the number of iterations and the execution time have been significantly reduced.It proves that the new proposed initialization method makes the original k-means clustering algorithm more effective.

data mining；k-means clustering algorithm；initial centers

TP391

A

2095-2163（2016）03-0017-04

2016-04-04

張魯營（1990-），女，碩士研究生，主要研究方向：數據挖掘；趙曉凡（1981-），女，博士研究生，主要研究方向：數據挖掘。