張魯營，趙曉凡

（北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，北京　100044）

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

張魯營，趙曉凡

（北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，北京100044）

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

數(shù)據(jù)挖掘；k均值聚類；初始中心

0　引 言

數(shù)據(jù)挖掘是一種可在不同類型數(shù)據(jù)集上發(fā)現(xiàn)、并提取隱藏有用信息的過程。同時(shí)，聚類則是一種無監(jiān)督的分類學(xué)習(xí)算法。而聚類分析即在數(shù)據(jù)挖掘中發(fā)揮著重要作用，已然廣泛進(jìn)入各種實(shí)際應(yīng)用領(lǐng)域，如工程、生物學(xué)、心理學(xué)、醫(yī)學(xué)和計(jì)算機(jī)視覺等［1］。聚類算法的主要任務(wù)是依據(jù)相似性進(jìn)行分類，以便使得相似的數(shù)據(jù)在同一類，不相似的數(shù)據(jù)在不同類。一個(gè)優(yōu)秀的聚類分析算法會(huì)產(chǎn)生比較合適的聚類結(jié)果，在這個(gè)結(jié)果中類內(nèi)有很高的相似性而類間的相似性比較低。

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

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

1　常用的初始化算法

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

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

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

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

基于此，針對現(xiàn)有聚類中心初始化方法計(jì)算復(fù)雜度高、對離群點(diǎn)敏感等問題，本文提出了一種新的基于貢獻(xiàn)率的聚類中心初始化方法：CRCC算法。這種初始化的方法時(shí)間復(fù)雜性比較小而且不會(huì)因?yàn)殡x群點(diǎn)而影響實(shí)驗(yàn)結(jié)果。該初始化方法可以幫助k均值聚類的算法得到一個(gè)更好的聚類結(jié)果。

2　優(yōu)化初始質(zhì)心k均值聚類

2.1相關(guān)分析

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

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

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

2.2優(yōu)化初始質(zhì)心k均值聚類

2.2.1CRCC算法

新方法的步驟為：首先對數(shù)據(jù)點(diǎn)的貢獻(xiàn)進(jìn)行排序，再將排序后的數(shù)據(jù)集分成若干個(gè)子集，并以此為基礎(chǔ)計(jì)算每個(gè)子集的平均值，選擇這些平均值作為初始聚類中心。

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

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

輸出：k個(gè)初始質(zhì)心

1）計(jì)算數(shù)據(jù)集合中每一列的和，將數(shù)據(jù)點(diǎn)此列對應(yīng)值除以這一列的總和獲得單列貢獻(xiàn)率；然后將這一行所有的貢獻(xiàn)率的絕對值相加即獲得這個(gè)數(shù)據(jù)點(diǎn)的貢獻(xiàn)率；

2）根據(jù)貢獻(xiàn)率的值將數(shù)據(jù)集合進(jìn)行排列；

3）將排列好的數(shù)據(jù)集合分成k個(gè)子集；

4）計(jì)算每一個(gè)子集的均值；

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

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

2.2.2分配數(shù)據(jù)點(diǎn)到聚類

分配數(shù)據(jù)點(diǎn)的算法［13］可以描述如下：

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

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

1）計(jì)算聚類中心和數(shù)據(jù)集合中數(shù)據(jù)點(diǎn)之間的歐式距離；

“S就是這樣跟小說家說的?，F(xiàn)在，他們的婚姻進(jìn)入了倒計(jì)時(shí)，卻在身體上放縱如世界末日之前的狂歡。S很心虛，不敢拒絕，擔(dān)心激怒曲，又憐惜她?；橐龃髲B的柱礎(chǔ)已斷裂，墻基在下陷，屋瓦在抖落，隨時(shí)都會(huì)分崩離析，而她還要在大廈將傾之際，醉生夢死，一絲不茍地完成性事。曲說，你不是喜歡這個(gè)嗎？把欠你的全補(bǔ)上?！?/p>

2）將數(shù)據(jù)向量分配給對應(yīng)的聚類，在該聚類中數(shù)據(jù)向量和聚類中心有最小距離；

3）重新選擇聚類中心；

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

3　實(shí)驗(yàn)結(jié)果

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

3.1數(shù)據(jù)集合的介紹

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

3.2實(shí)驗(yàn)結(jié)果和討論

在本節(jié)中，研究將使用不同的初始化方法實(shí)現(xiàn)聚類結(jié)果的比較。具體來講，k均值采用了隨機(jī)初始聚類中心的聚類算法、k-均值++算法、SSE方法、最近鄰的方法還有新提出的初始化方法。對于原始的隨機(jī)算法則將采用10次的平均值作為實(shí)驗(yàn)的結(jié)果，因?yàn)槌跏假|(zhì)心的隨機(jī)性使得若采用平均值，就可以提升實(shí)驗(yàn)結(jié)果的準(zhǔn)確性。實(shí)驗(yàn)結(jié)果如表2所示。

下面，研究又用Rand Index的值來驗(yàn)證新的初始化方法的有效性，實(shí)驗(yàn)結(jié)果如表3、表4所示。

表1　數(shù)據(jù)集合Tab.1 Dataset

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

表3　指數(shù)Tab.3 Rand Index

表4　執(zhí)行時(shí)間Tab.4 Execution time

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

從實(shí)驗(yàn)過程的發(fā)生和完成中，能夠發(fā)現(xiàn)新的初始化方法的優(yōu)點(diǎn)。首先，原始k均值聚類算法的初始質(zhì)心是隨機(jī)選擇的，并不能保證實(shí)驗(yàn)的穩(wěn)定性，但新算法的初始聚類中心的選擇是自動(dòng)計(jì)算的，而且又是唯一的，從而提高了k均值聚類算法實(shí)驗(yàn)結(jié)果的穩(wěn)定性。其次，新初始質(zhì)心的實(shí)驗(yàn)過程簡潔易懂，降低了時(shí)間復(fù)雜性，同時(shí)更能保證獲得較好的實(shí)驗(yàn)結(jié)果。此外，新提出的初始化方法不需要任何參數(shù)作為輸入得到的結(jié)果，因此，這就可以提高k均值聚類算法的實(shí)驗(yàn)結(jié)果的準(zhǔn)確性和穩(wěn)定性。最后，以新提出的方法來選擇初始聚類中心在實(shí)現(xiàn)上具有高度可行性，而其特性呈現(xiàn)則是一個(gè)線性方法?？傊?，新提出的初始化算法是非常有效的，可以精準(zhǔn)選擇并確定k均值聚類的初始中心。

4　結(jié)束語

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

進(jìn)一步地，后續(xù)工作主要是針對k均值聚類算法的另一個(gè)缺點(diǎn)，就是標(biāo)準(zhǔn)的k均值算法的結(jié)果受輸入k值的影響而需要展開深入研究設(shè)計(jì)。在聚類過程中，研究必須預(yù)先定義k的值。預(yù)計(jì)未來將可找到一個(gè)新方法來計(jì)算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，F(xiàn)ULL 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-），女，碩士研究生，主要研究方向：數(shù)據(jù)挖掘；趙曉凡（1981-），女，博士研究生，主要研究方向：數(shù)據(jù)挖掘。