蔡宇浩，梁永全，樊建聰，李　璇，劉文華

?

加權(quán)局部方差優(yōu)化初始簇中心的K-means算法*

蔡宇浩，梁永全，樊建聰+，李璇，劉文華

山東科技大學(xué)信息科學(xué)與工程學(xué)院，山東青島266590

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2016/10(05)-0732-10

http://www.ceaj.org Tel: +86-10-89056056

* The National Natural Science Foundation of China under Grant No. 61203305 (國家自然科學(xué)基金). Received 2015-09,Accepted 2015-11.

CNKI網(wǎng)絡(luò)優(yōu)先出版: 2015-11-24, http://www.cnki.net/kcms/detail/11.5602.TP.20151124.1354.002.htm l

CAI Yuhao, LIANG Yongquan, FAN Jiancong, et al. Optim izing initial cluster centroids by weighted local variance in K-meansalgorithm. Journal of Frontiersof Computer Scienceand Technology, 2016, 10(5)：732-741.

摘要：在傳統(tǒng)K-means算法中，初始簇中心選擇的隨機(jī)性，導(dǎo)致聚類結(jié)果隨不同的聚類中心而不同。因此出現(xiàn)了很多簇中心的選擇方法，但是很多已有的簇中心選擇算法，其聚類結(jié)果受參數(shù)調(diào)節(jié)的影響較大。針對這

一問題，提出了一種新的初始簇中心選擇算法，稱為WLV-K-means（weighted local variance K-means）。該算法采用加權(quán)局部方差度量樣本的密度，以更好地發(fā)現(xiàn)密度高的樣本，并利用改進(jìn)的最大最小法，啟發(fā)式地選擇簇初始中心點(diǎn)。在UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，WLV-K-means算法不僅能夠取得較好的聚類結(jié)果，而且受參數(shù)變化的影響較小，有更加穩(wěn)定的表現(xiàn)。

關(guān)鍵詞：K-means算法；方差；加權(quán)；最大最小法；簇初始中心點(diǎn)

1 引言

聚類是一種無監(jiān)督的學(xué)習(xí)方法，主要目的是把數(shù)據(jù)對象劃分為多個不同的簇或者子集，使得同一簇內(nèi)的樣本彼此之間具有較高的相似度，而不同簇的樣本之間相似度較低。聚類的實(shí)用性得到了非常廣泛的認(rèn)可，應(yīng)用領(lǐng)域也很多，包括商務(wù)智能、圖像識別、Web搜索、生物學(xué)和信息安全等。常用的聚類方法根據(jù)其特性可以被劃分為劃分方法、層次方法、基于密度的方法、基于網(wǎng)格的方法等[1]。

K-means算法[2]是一種應(yīng)用廣泛的基于劃分的聚類方法，具有簡潔、通用以及快速等優(yōu)點(diǎn)。然而傳統(tǒng)K-means算法中，初始中心點(diǎn)的隨機(jī)選取，將導(dǎo)致聚類結(jié)果隨初始點(diǎn)的不同而不同。如果選擇的初始中心點(diǎn)導(dǎo)致算法收斂至局部最優(yōu)，聚類結(jié)果可能會很不理想[3]。

針對K-means算法的缺點(diǎn)，以及K中心點(diǎn)選擇優(yōu)化算法中存在的問題[4]，本文從兩個方面進(jìn)行改進(jìn)：（1）定義了加權(quán)局部方差作為樣本密度衡量的標(biāo)準(zhǔn)；（2）改進(jìn)了最大最小法，進(jìn)一步選擇密度大且分隔較遠(yuǎn)的初始中心點(diǎn)。

本文組織結(jié)構(gòu)如下：第2章介紹優(yōu)化初始中心點(diǎn)K-means算法近期的相關(guān)工作；第3章介紹本文算法的基本概念；第4章介紹基于加權(quán)局部方差的改進(jìn)K-means算法（weighted local variance K-means，WLV-K-means）；第5章給出實(shí)驗(yàn)結(jié)果及分析比較；第6章為結(jié)束語。

2 相關(guān)工作

為克服傳統(tǒng)K-means算法的這一不足，很多研究者對其進(jìn)行不斷改進(jìn)。Katsavounidis等人[5]提出基于最大最小法的初始中心點(diǎn)選擇方法。該方法首先選擇具有最大歐幾里德范數(shù)的對象作為第一個初始中心點(diǎn)，利用最大最小法逐個找到初始中心點(diǎn)。Wang[6]利用相異度矩陣構(gòu)造哈夫曼樹，從而選擇K-means算法的初始中心點(diǎn)。Erisoglu等人[7]通過選擇兩個樣本坐標(biāo)的主軸，從而計算出樣本在這兩個主軸對應(yīng)分量的均值。初始中心由兩個主軸確定，第一個初始中心為到主軸均值距離最大的樣本，第二個為主軸分量距離第一個初始中心距離最大的樣本。后續(xù)聚類中心為與已經(jīng)選中的初始中心距離之和最大的樣本，重復(fù)該過程，直到獲得指定個數(shù)的初始中心。Khan和Ahmad[8]提出了一種新的初始中心點(diǎn)方法（cluster center initialization algorithm，CCIA）。該方法通過對樣本每一維分別進(jìn)行聚類，發(fā)現(xiàn)K′(K′>K)類具有相同模式的點(diǎn)，分別得到K′類的中心點(diǎn)，再利用文獻(xiàn)[9]的數(shù)據(jù)壓縮方法，通過合并高密度樣本的鄰域，最終得到K個初始中心點(diǎn)。Rahman等人[10]提出了一種新的初始中心點(diǎn)選擇技術(shù)DenClust。Den-Clust利用密度的方法，將距樣本最小距離的樣本數(shù)作為該樣本的密度，進(jìn)而選擇高質(zhì)量的初始種子集作為K-means算法的初始聚類中心。汪中等人[11]采用敏感的相似性度量來計算點(diǎn)的密度，找到K個初始中心，并以均衡化函數(shù)準(zhǔn)則為標(biāo)準(zhǔn)，自動生成聚類數(shù)目。熊忠陽等人[12]提出了最大距離積法，根據(jù)密度參數(shù)找到高密度集合，分別找到兩個聚類中心，搜索到聚類中心集合距離乘積最大的點(diǎn)作為下一個聚類中心，直到聚類中心的個數(shù)達(dá)到K。陳光平等人[13]提出了一種改進(jìn)的初始中心點(diǎn)選擇方法。該方法利用距離最大的兩個樣本作為初始的聚類中心，將剩余樣本按距離劃分。樣本數(shù)較多的一簇，再找出相距最遠(yuǎn)的兩個樣本作為聚類中心，劃分該簇。以此類推，直到找到K個聚類中心為止。曹永春等人[14]提出一種基于K-means的人工蜂群聚類算法，在每次迭代過程中，利用改進(jìn)人工蜂群算法優(yōu)化各聚類中心，分別對每個聚類中心進(jìn)行K-means聚類。兩個算法交替進(jìn)行，直到聚類結(jié)束。文獻(xiàn)[15-18]分別采用計算樣本密度的不同方法，選擇距離最遠(yuǎn)并且具有高密度的樣本作為K-means算法的初始中心點(diǎn)。其中，文獻(xiàn)[15]和[18]采用設(shè)定閾值的方式計算鄰域密度，并選擇相互距離最遠(yuǎn)的高密度區(qū)域作為初始中心點(diǎn)。文獻(xiàn)[17]利用全局方差計算樣本的鄰域密度，選擇方差小且相距一定距離的樣本作為初始中心點(diǎn)。對K-means算法中的K值進(jìn)行設(shè)定同樣也是一個重要問題，孫鎮(zhèn)江等人[19]提出了基于密度的循環(huán)首次適應(yīng)K值優(yōu)化算法。該算法通過設(shè)置密度閾值，將樣本劃分為多個簇集，從而確定K的個數(shù)。本文假設(shè)K已知。

3 基本概念

3.1 K-means算法

K-means算法的目的是為了使各簇中的樣本到其簇中心的誤差平方之和最小，算法首先從數(shù)據(jù)集D中隨機(jī)選擇K個樣本，每個對象代表一個簇的初始中心點(diǎn)，分別計算D中剩余對象到各簇中心點(diǎn)的歐式距離，并將其分配到最相近的簇中，然后更新各簇的中心點(diǎn)，重新分配D中對象，迭代該過程直至收斂。K-means算法偽代碼如下所示。

算法1 K-means算法

輸入：聚類簇的數(shù)目K；包含n個對象的數(shù)據(jù)集D。輸出：聚類結(jié)果集。

從D中任意選出K個對象作為初始中心點(diǎn)；

repeat

將每個對象劃分到距離它最近的簇中心所在的簇中；重新計算每個簇中對象的均值，更新中心點(diǎn)；

until簇中點(diǎn)不再發(fā)生變化；

3.2樣本方差

通過計算數(shù)據(jù)和期望之間的偏離程度得到方差，用于度量數(shù)據(jù)之間的離散程度，計算方法為求取各數(shù)據(jù)與期望之差的平方和的平均值，方差s2如式（1）所示：

其中，n為樣本個數(shù)；xi為第i個樣本；為樣本均值，如式（2）所示：

方差越大，說明樣本數(shù)據(jù)越分散，反之則說明越密集。在已知每個樣本鄰域的情況下，樣本到其鄰域內(nèi)各樣本距離的方差，能夠反映出該樣本鄰域內(nèi)密度的大小。

3.3最大最小法

最大最小法是文獻(xiàn)[5]提出的初始聚類中心點(diǎn)選擇方法，中心點(diǎn)的選擇過程為：首先選擇第一個中心點(diǎn)c1，然后計算數(shù)據(jù)集D中其他對象與c1之間的歐式距離，選擇距離最大的對象作為下一個中心點(diǎn)c2。選擇第i(i>2)個中心點(diǎn)ci時，計算數(shù)據(jù)集中剩余對象與之前中心點(diǎn)之間距離，將最近的歐式距離作為該對象的最大最小值，然后將最大最小值最大的對象作為下個中心點(diǎn)。重復(fù)該過程，直至選擇出指定個數(shù)的初始中心點(diǎn)，如式（3）所示：

其中，mj為樣本j的最大最小值；N為樣本個數(shù)；mj如式（4）所示：

其中，ct為初始中心點(diǎn)集合T中的對象；d(ct,xj)為初始中心點(diǎn)ct與樣本xj之間的歐式距離。

最大最小法可以找到相距較遠(yuǎn)的初始中心點(diǎn)，然而僅從距離判斷，很有可能會將離群點(diǎn)作為初始中心點(diǎn)，從而導(dǎo)致K-means算法局部收斂。

4 W LV-K-means算法

4.1算法思想

在傳統(tǒng)的K-means算法中，初始中心點(diǎn)選擇的隨機(jī)性，導(dǎo)致了聚類結(jié)果的不穩(wěn)定性。由于中心點(diǎn)在迭代過程中不斷更新，如果初始中心點(diǎn)選擇不理想，會導(dǎo)致更新簇時，中心點(diǎn)偏離簇的真實(shí)值，從而最終收斂于局部最優(yōu)解。因此中心點(diǎn)選擇的主要問題是，除去噪聲數(shù)據(jù)以及離群點(diǎn)，并發(fā)現(xiàn)分散且具有高密度鄰域的初始點(diǎn)。

為度量樣本鄰域的密度，文獻(xiàn)[11,18]通過設(shè)定參數(shù)調(diào)節(jié)樣本的鄰域半徑，并計算鄰域內(nèi)樣本數(shù)目作為鄰域的密度。這類方法存在參數(shù)調(diào)節(jié)缺少客觀性的問題。文獻(xiàn)[16]將全部樣本之間距離的平均值作為鄰域半徑，計算鄰域內(nèi)樣本數(shù)作為鄰域密度。該方法對各類分布均勻的樣本效果較好，然而對于分布不均勻的樣本，更應(yīng)考慮局部的相關(guān)信息。文獻(xiàn)[9]定義樣本與距其第N近的樣本之間距離作為該樣本的密度，距離越小密度越大。然而該方法只考慮樣本與距其第N近的樣本之間的距離，而忽略與其他N-1個樣本之間的距離。文獻(xiàn)[17]通過計算樣本到所有樣本的距離方差，從而判斷其鄰域密度大小。然而對于鄰域過于緊密或者過于稀疏的點(diǎn)均會被認(rèn)為方差較大，將會忽略一些密集區(qū)域，影響聚類精度。

針對上述問題，本文提出了WLV-K-means算法，計算樣本的鄰域半徑以及半徑內(nèi)樣本至中心距離的方差，將加權(quán)局部方差作為新的密度度量標(biāo)準(zhǔn)。方差作為一種度量樣本分布的概率統(tǒng)計量，可以客觀地反映樣本的離散程度。本文采用局部方差，一方面比計算全局變量的方法更具有適用性，另一方面方差的引入提高了密度計算的準(zhǔn)確性。參數(shù)調(diào)節(jié)被映射到(0,1)范圍內(nèi)的子區(qū)間，因此更具客觀性。局部方差的加權(quán)進(jìn)一步提高了算法的抗噪能力。加權(quán)局部方差綜合考慮樣本分布問題及客觀性等問題，將其作為密度度量標(biāo)準(zhǔn)更具合理性。

計算得到樣本的加權(quán)局部方差后，對其排序，將最小值對應(yīng)的樣本作為第一個初始中心點(diǎn)。利用改進(jìn)的最大最小法，在計算最大最小值時，將加權(quán)局部方差的倒數(shù)作為密度系數(shù)，對最大最小值加權(quán)，使得算法優(yōu)先選擇具有高密度的樣本。逐個找出其他初始中心點(diǎn)，最終將初始中心點(diǎn)用到K-means算法中。

在改進(jìn)的最大最小法中，密度系數(shù)的加入雖然提高了最大最小法的抗噪能力，但同時會增加算法的計算量，從而增加算法的時間復(fù)雜度。存儲各樣本的密度系數(shù)也會帶來算法空間復(fù)雜度的增加。

4.2基本定義

對于一個數(shù)目為n的樣本集(x1,x2,…,xn)，每個樣本xi為m維空間數(shù)據(jù)(xi1,xi2,…,xim)。

定義1樣本xi的鄰域半徑ri如式（5）所示：

其中，D為樣本集的距離矩陣；Di為樣本xi到其他樣本的距離按照從小到大排序后的行向量。因此Di?θ×n ?表示樣本xi到其他樣本距離中第?θ×n ?近的距離，θ為鄰域半徑調(diào)節(jié)系數(shù)，取值范圍為(0,1)。由上式可以得出，每個樣本的鄰域半徑都是不同的，鄰域半徑小的樣本處于高密度區(qū)域的可能性更大。

定義2樣本xi的加權(quán)局部方差ρi如式（6）所示：

ρi=ωi×vi（6）

其中，vi為鄰域半徑內(nèi)的局部方差；ωi為樣本xi局部方差的權(quán)重。ρi越小，說明樣本鄰域內(nèi)密度越大，vi和ωi如式（7）及式（8）所示：

其中，Ni為樣本xi鄰域半徑內(nèi)的樣本集合；d(xi,xj)表示樣本xi與xj的歐式距離。

其中，R表示樣本集的鄰域半徑向量，將樣本xi的鄰域半徑ri歸一化，使ωi∈[0,1]。

定義3加權(quán)最大最小值gi如式（9）所示：

其中，T為初始中心點(diǎn)集合；ρi為式（6）求得的加權(quán)局部方差。樣本xi的最大最小值gi為xi到中心點(diǎn)集中最近的距離乘以xi的加權(quán)局部方差的倒數(shù)1 ρi，加權(quán)局部方差越小，樣本密度越大，則被選中的可能性越大。

4.3算法描述

算法中初始中心點(diǎn)選擇主要分為兩個階段：第一個階段是計算加權(quán)局部方差，判斷樣本的密度，并找出密度最大，即加權(quán)局部方差最小的樣本。此過程中加入權(quán)值，能夠進(jìn)一步減小誤選噪音點(diǎn)或者離群點(diǎn)的可能性。第二階段為了防止所選中心點(diǎn)出現(xiàn)在同一類簇中，同樣在最大最小法中利用密度加權(quán)，從而更有效地避免K-means算法中最終收斂于局部最優(yōu)值。算法的偽代碼如下所示。

算法2 WLV-K-means算法

輸入：聚類簇的數(shù)目K；包含n個對象的數(shù)據(jù)集D；鄰域半徑調(diào)節(jié)參數(shù)θ。

輸出：聚類結(jié)果集。

For D中的每個對象xi

根據(jù)式（5）計算xi的鄰域半徑ri；

將xi鄰域半徑內(nèi)對象x′加入到集合Ni中；根據(jù)式（6）～（8）計算xi的加權(quán)局部方差ρi；end for

選擇具有最小ρi的數(shù)據(jù)點(diǎn)p作為第一個初始中心點(diǎn)，加入集合T，并將p從D中刪除；將p鄰域內(nèi)的對象從集合D中刪除；while集合T中元素的個數(shù)小于K

for D每個對象x

根據(jù)式（9）計算x的加權(quán)最大最小值g；

end for

選擇具有最大g對應(yīng)的數(shù)據(jù)點(diǎn)p′作為下一個初

始中心點(diǎn)，加入集合T，并將p′從D中刪除;

將p′鄰域內(nèi)的對象從集合D中刪除；

end while

集合T作為初始中心點(diǎn)；

repeat

將數(shù)據(jù)集中對象劃分到距其最近的中心點(diǎn)所在的簇中；

將各簇的均值作為更新的中心點(diǎn)；

until聚類的誤差平方和不再發(fā)生變化；

4.4算法分析

傳統(tǒng)K-means算法的時間復(fù)雜度為O(nKT)，其中n為數(shù)據(jù)集中樣本個數(shù)，K為簇數(shù)，T為迭代次數(shù)。本文提出的WLV-K-means算法由兩部分組成，分別是計算加權(quán)局部方差以及利用改進(jìn)最大最小法選擇初始中心點(diǎn)。其中計算加權(quán)局部方差部分，由于需要計算樣本間的距離矩陣，其時間復(fù)雜度為O(n2)。為計算距離樣本第K近的距離，需對樣本到其他樣本距離進(jìn)行排序，每個樣本距其他樣本距離的最優(yōu)排序時間復(fù)雜度為O(n lb n)，總的排序時間復(fù)雜度為O(n2lb n)。因此，計算加權(quán)局部方差的時間復(fù)雜度為O(n2(1+lb n))。利用改進(jìn)最大最小法選擇初始中心點(diǎn)部分的時間復(fù)雜度為O(K2n)。由于K，T?n，算法整體的時間復(fù)雜度為O(n2(1+lb n))，空間復(fù)雜度為O(n2)。

為提高算法整體的效率，減少時間空間復(fù)雜度，可以將距第K近樣本計算問題轉(zhuǎn)化為K近鄰查詢，利用數(shù)據(jù)結(jié)構(gòu)k-d樹，計算距查詢樣本第K近的樣本。從而減少計算距離矩陣的時間復(fù)雜度和存儲距離矩陣的空間復(fù)雜度，進(jìn)而降低算法整體的時間及空間復(fù)雜度。

5 實(shí)驗(yàn)分析

為驗(yàn)證WLV-K-means算法的聚類效果及穩(wěn)定性，在UCI數(shù)據(jù)集上進(jìn)行測試，并與傳統(tǒng)K-means算法、文獻(xiàn)[5]提出的算法Generalized Lloyd Iteration （GLI-K-means）、文獻(xiàn)[11]提出的優(yōu)化初始中心點(diǎn)的K-means算法（optim ized initial center points，OICP-K-means）、文獻(xiàn)[15]提出的初始聚類中心優(yōu)化的K-means算法（optim ization study on initial center，OS-K-means）以及文獻(xiàn)[17]提出的最小方差優(yōu)化初始聚類中心的K-means算法（m inimum deviation initialized clustering centers，MD-K-means）進(jìn)行對比。

為更客觀地對比，取100次實(shí)驗(yàn)的平均值作為傳統(tǒng)K-means算法的聚類評價結(jié)果，其他幾種對比算法的聚類結(jié)果，均取調(diào)參后的最佳結(jié)果。

實(shí)驗(yàn)結(jié)果的評價指標(biāo)采用聚類準(zhǔn)確率、聚類的誤差平方和以及標(biāo)準(zhǔn)化互信息（normalized mutual information，NM I）[20]。

設(shè)樣本集X包括k個類，聚類準(zhǔn)確率的表示如式（10）所示：

其中，ai表示被正確劃分到類Ci中的樣本數(shù)；|| X表示樣本總數(shù)。

聚類的誤差平方和（sum of squared errors, SSE）的表示如式（11）所示：

其中,‖·‖為2-范數(shù)，C={ck,k=1,2,…,K}為K個簇集；xi為第k簇中的樣本；μk為第k簇的簇中心。

NM I的表示如式（12）所示：

其中，X、Y為隨機(jī)變量；I(X,Y)為X和Y之間的互信息；H(X)和H(Y)分別表示X和Y的熵，如式（13）～ （15）所示：

其中，p(x,y)為x和y的聯(lián)合概率函數(shù)；p(x)和p(y)分別為x和y的概率函數(shù)。

5.1數(shù)據(jù)集描述

本文采用10個UCI數(shù)據(jù)庫中聚類常用的數(shù)據(jù)集，如表1所示。

5.2實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)的準(zhǔn)確率、誤差平方和以及NM I的對比結(jié)果如表2、表3和表4所示，其中加粗部分為最佳的聚類結(jié)果。

Table 2 Comparison of accuracy on UCI datasets between each algorithm表2 各算法在UCI數(shù)據(jù)集的準(zhǔn)確率比較

Table 1 Description of UCI datasets表1 UCI數(shù)據(jù)集描述

分析表2可以得出，WLV-K-means算法在Seed、Pima、New thyroid和Soybean-small數(shù)據(jù)集上的聚類準(zhǔn)確率要高于其他5種算法，在Soybean-small數(shù)據(jù)集上的聚類準(zhǔn)確率達(dá)到了100%。在Iris、seed和Ionosphere數(shù)據(jù)集上聚類準(zhǔn)確率與GLI-K-means算法相同，高于其他4種算法。在W ine、Haberman和Art數(shù)據(jù)集上聚類準(zhǔn)確率與其他對比算法的最大聚類準(zhǔn)確率相等。

由表3誤差平方和比較可以得出，WLV-K-means算法在Iris和Haberman數(shù)據(jù)集上的聚類誤差平方和優(yōu)于其他5種算法。在New thyroid，Soybean-small數(shù)據(jù)集上的誤差平方和與MD-K-means算法相等，優(yōu)于其他4種算法。在其他數(shù)據(jù)集上除Soybean-small、Unart及Ionosphere上聚類誤差平方和略大于最優(yōu)值，其他結(jié)果不差于傳統(tǒng)K-means算法以及另外4種優(yōu)化算法。

從表4中NM I的比較結(jié)果可以看出，WLV-K-means算法在除Unart數(shù)據(jù)集之外的其他UCI數(shù)據(jù)集上都有較好的聚類結(jié)果。

WLV-K-means算法對密度的計算以及中心點(diǎn)選取兩個階段進(jìn)行改進(jìn)。從實(shí)驗(yàn)結(jié)果可以得出，WLVK-means算法及對比算法在3種指標(biāo)的比較中，在大多數(shù)數(shù)據(jù)集上都有較好的表現(xiàn)。

Table 3 Comparison of sum square error on UCI datasets between each algorithm表3 各算法在UCI數(shù)據(jù)集的誤差平方和比較

Table 4 Comparison of NM I on UCI datasets between each algorithm表4 各算法在UCI數(shù)據(jù)集的NM I比較

5.3參數(shù)調(diào)節(jié)

數(shù)據(jù)集中樣本的數(shù)目及分布不同，WLV-K-means算法中最優(yōu)半徑調(diào)節(jié)參數(shù)θ也相應(yīng)不同。半徑調(diào)節(jié)參數(shù)θ取值范圍為(0,1)，而且其取值與數(shù)據(jù)集的個數(shù)N以及簇數(shù)K有關(guān)。對各類數(shù)據(jù)個數(shù)接近N/ K的數(shù)據(jù)集，最理想狀態(tài)為樣本鄰域內(nèi)樣本數(shù)為N/ K，此時合適的中心點(diǎn)可以分別表示各個類簇。為了防止不同數(shù)據(jù)集中存在一定的偏差，將θ的取值范圍設(shè)置為[N/ K -0.15,N/ K]。對于各類數(shù)據(jù)比例相差較大的數(shù)據(jù)集，如果取θ接近N/ K，個數(shù)較少類中的樣本會被忽略。因此θ將從最小值開始逐步遞增，取值范圍為[0.01,0.15]。在兩種取值范圍內(nèi)，以0.01為步長，在UCI數(shù)據(jù)集上，不同參數(shù)對應(yīng)的聚類準(zhǔn)確率如圖1所示。

從圖1中可以得出，各數(shù)據(jù)集在對應(yīng)的區(qū)間中均能找到最優(yōu)準(zhǔn)確率。第一類數(shù)據(jù)集在N/ K處，準(zhǔn)確率達(dá)到收斂狀態(tài)。第二類數(shù)據(jù)集中，當(dāng)θ取較小值時的聚類效果要優(yōu)于其取較大值的聚類效果。聚類準(zhǔn)確率在參數(shù)變化區(qū)間內(nèi)的變動幅度較小，說明本文算法的穩(wěn)定性更好，不會出現(xiàn)由于參數(shù)選擇不合適而導(dǎo)致聚類結(jié)果過大的變化。

數(shù)據(jù)集Soybean-small的實(shí)驗(yàn)中，當(dāng)θ取值較小時，聚類效果更理想。在計算樣本的加權(quán)局部方差時，樣本的鄰域半徑依賴于θ。由于數(shù)據(jù)集Soybeansmall的數(shù)據(jù)量較小且各類數(shù)據(jù)量分布不均勻，當(dāng)θ取較小值時才能保證樣本的鄰域半徑處于較小范圍內(nèi)，從而更好地發(fā)現(xiàn)分布密集的區(qū)域，并且能夠找到樣本數(shù)較少的類的中心點(diǎn)。如果θ取值過大，會導(dǎo)致鄰域半徑過大，一方面使得樣本鄰域半徑內(nèi)部包含其他類的樣本或者噪聲數(shù)據(jù)，另一方面在利用加權(quán)最大最小法選擇中心時會將樣本數(shù)較少的類忽略，從而不能準(zhǔn)確地發(fā)現(xiàn)各類的初始中心點(diǎn)。

Fig.1 Variation trend of clustering accuracy on UCI datasets w ith the change of parameter圖1 UCI數(shù)據(jù)集聚類準(zhǔn)確率隨參數(shù)變化趨勢

6 結(jié)束語

傳統(tǒng)K-means算法過程中，初始中心點(diǎn)選擇的隨機(jī)性，使得聚類結(jié)果不穩(wěn)定，并且容易使聚類結(jié)果達(dá)到局部最優(yōu)，難以得到理想的聚類結(jié)果。而已有的基于密度選擇中心點(diǎn)的優(yōu)化算法，算法的聚類效果過度依賴閾值的設(shè)定，具有一定的局限性。本文提出了一種基于加權(quán)局部方差的密度計算方法，并利用改進(jìn)的最大最小法，啟發(fā)式地選擇初始中心點(diǎn)。在UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果證明了本文算法提高了聚類的質(zhì)量，具有較好的穩(wěn)定性。

References:

[1] Han Jiawei, Kamber M, Pei Jian. Data mining concepts and techniques[M]. 3rd ed. Fan M ing, Meng Xiaofeng. Beijing: China Machine Press, 2012: 288-290.

[2] Jain A K. Data clustering: 50 years beyond K-means[J]. Pattern Recognition Letters, 2010, 31(8): 651-666.

[3] Sun Jigui, Liu Jie, Zhao Lianyu. Clustering algorithm research[J]. Journal of Software, 2008, 19(1): 48-61.

[4] 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 w ith Applications, 2012, 40 (1): 200-210.

[5] Katsavounidis I, Jay Kuo C C, Zhang Zhen. A new initialization technique for generalized Lloyd iteration[J]. Signal Processing Letters, 1994, 1(10): 144-146.

[6] Wang Shunye. An improved k-means clustering algorithm based on dissim ilarity[C]//Proceedings of the 2013 International Conference on Mechatronic Sciences, Electric Engineering and Computer, Shengyang, China, Dec 20-22, 2013. Piscataway, USA: IEEE, 2013: 2629-2633.

[7] 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.

[8] Khan S S, Ahmad A. Cluster center initialization algorithm for K-means clustering[J]. Pattern Recognition Letters, 2004, 25(11): 1293-1302.

[9] Mitra P, Murthy C A, Pal S K. Density-based multiscale data condensation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(6): 734-747.

[10] Rahman M A, Islam M Z, Bossomaier T. DenClust: a density based seed selection approach for K-means[C]//LNCS 8468: Proceedings of the 13th International Conference on Artificial Intelligence and Soft Computing, Zakopane, Poland, Jun 1-5, 2014. [S.l.]: Springer International Publishing, 2014: 784-795.

[11] Wang Zhong, Liu Guiquan, Chen Enhong. A K-means algorithm based on optim ized initial center points[J]. Pattern Recognition and Artificial Intelligence, 2009, 22(2): 299-304. [12] Xiong Zhongyang, Chen Ruotian, Zhang Yufang. Effective method for cluster center?s initialization in K-means clustering[J]. Application Research of Computers, 2011, 28 (11): 4188-4190.

[13] Chen Guangping, Wang Wenpeng, Huang Jun. Improved initial clustering center selection method for K-means algorithm[J]. Journal of Chinese Computer Systems, 2012, 33 (6): 1320-1323.

[14] Cao Yongchun, Cai Zhengqi, Shao Yabin. Improved artificial bee colony clustering algorithm based on K-means[J]. Journal of Computer Applications, 2014, 34(1): 204-207.

[15] Lai Yuxia, Liu Jianping. Optim ization study on initial center of K-means algorithm[J]. Computer Engineering and Applications, 2008, 44(10): 147-149.

[16] Han Lingbo, Wang Qiang, Jiang Zhengfeng, et al. Improved K-means initial clustering center selection algorithm[J]. Computer Engineering and Applications, 2010, 46(17): 150-152.

[17] Xie Juanying, Wang Yan ?e. K-means algorithm based on minimum deviation initialized clustering centers[J]. Computer Engineering, 2014, 40(8): 205-211.

[18] Fu Desheng, Zhou Chen. Improved K-means algorithm and its implementation based on density[J]. Journal of Computer Applications, 2011, 31(2): 432-434.

[19] Sun Zhenjiang, Liang Yongquan, Fan Jiancong. Optimization study and application on the K value of K-means algorithm[J]. Journal of Bioinformatics and Intelligent Control, 2013, 2(3): 223-227.

[20] Fan Jiancong. OPE-HCA: an optimal probabilistic estimation approach for hierarchical clustering algorithm[J]. Neural Computing and Applications, 2015.

附中文參考文獻(xiàn)：

[1] Han Jiawei, Kamber M，Pei Jian.數(shù)據(jù)挖掘概念與技術(shù)[M].范明,孟小峰. 3版.北京:機(jī)械工業(yè)出版社, 2012: 288-290.

[3]孫吉貴,劉杰,趙連宇.聚類算法研究[J].軟件學(xué)報, 2008, 19(1): 48-61.

[11]汪中,劉貴全,陳恩紅.一種優(yōu)化初始中心點(diǎn)的K-means算法[J].模式識別與人工智能, 2009, 22(2): 299-304.

[12]熊忠陽,陳若田,張玉芳.一種有效的K-means聚類中心初始化方法[J].計算機(jī)應(yīng)用研究, 2011, 28(11): 4188-4190.

[13]陳光平,王文鵬,黃俊.一種改進(jìn)初始聚類中心選擇的K-means算法[J].小型微型計算機(jī)系統(tǒng), 2012, 33(6): 1320-1323.

[14]曹永春,蔡正琦,邵亞斌.基于K-means的改進(jìn)人工蜂群聚類算法[J].計算機(jī)應(yīng)用, 2014, 34(1): 204-207.

[15]賴玉霞,劉建平. K-means算法的初始聚類中心的優(yōu)化[J].計算機(jī)工程與應(yīng)用, 2008, 44(10): 147-149.

[16]韓凌波,王強(qiáng),蔣正鋒,等.一種改進(jìn)的K-means初始聚類中心選取算法[J].計算機(jī)工程與應(yīng)用,2010,46(17):150-152.

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

[18]傅德勝,周辰.基于密度的改進(jìn)K均值算法及實(shí)現(xiàn)[J].計算機(jī)應(yīng)用, 2011, 31(2): 432-434.

CAI Yuhao was born in 1990. He is an M.S. candidate at College of Information Science and Engineering, Shandong University of Science and Technology. His research interests include machine learning and data m ining, etc.

蔡宇浩（1990—），男，山東青州人，山東科技大學(xué)信息科學(xué)與工程學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，數(shù)據(jù)挖掘等。

LIANG Yongquan was born in 1968. He is a professor at College of Information Science and Engineering, Shandong University of Science and Technology, and the senior member of CCF. His research interests include machine learning, data mining, distributed artificial intelligence and intelligent multimedia information processing, etc.

梁永全（1968—），男，山東聊城人，博士，山東科技大學(xué)信息科學(xué)與工程學(xué)院教授，CCF高級會員，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，數(shù)據(jù)挖掘，分布式人工智能，多媒體信息智能處理等。

FAN Jiancong was born in 1977. He is an associate professor at College of Information Science and Engineering, Shandong University of Science and Technology, and the member of CCF. His research interests include machine learning, data m ining, evolutionary computation and mass data processing, etc.

樊建聰（1977—），男，山東青島人，博士，山東科技大學(xué)信息科學(xué)與工程學(xué)院副教授，CCF會員，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，數(shù)據(jù)挖掘，演化計算，海量信息處理等。

LI Xuan was born in 1993. She is an M.S. candidate at College of Information Science and Engineering, Shandong University of Science and Technology. Her research interests include machine learning and data m ining, etc.

李璇（1993—），女，山東寧陽人，山東科技大學(xué)信息科學(xué)與工程學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，數(shù)據(jù)挖掘等。

LIU Wenhua was born in 1990. She is an M.S. candidate at College of Information Science and Engineering, Shandong University of Science and Technology. Her research interests include machine learning and data mining, etc.

劉文華（1990—），女，山東煙臺人，山東科技大學(xué)信息科學(xué)與工程學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，數(shù)據(jù)挖掘等。

Optim izing Initial Cluster Centroidsby Weighted Local Variance in K-means Algorithm?

CAI Yuhao, LIANG Yongquan, FAN Jiancong+, LI Xuan, LIU Wenhua
College of Information Science and Engineering, Shandong University of Science and Technology, Qingdao, Shandong 266590, China
+ Corresponding author: E-mail: fanjiancong@sdust.edu.cn

Key words:K-means algorithm; variance; weighting; max-m in method; initial cluster centroids

Abstract:The selection of initial cluster centroids in the classical K-means algorithm is random, which causes that the clustering results vary w ith different selections of cluster centroids. Thereby many selection approaches of initial centroids are devised and applied. However, most of them are affected by parameters design and parameter values. To overcome this problem, this paper proposes a novel initial cluster centroids selection algorithm, called WLV-K-means (weighted local variance K-means). The WLV-K-means algorithm employs the weighted local variance to measure the density of each sample, which can find samples w ith higher density. This algorithm also uses the improved max-min method to select cluster centroid heuristically. The experiments are made on UCI datasets and the results show that the WLV-K-means algorithm outperforms some improved K-means algorithms and is more stable and robust.

doi:10.3778/j.issn.1673-9418.1509024 E-mail: fcst@vip.163.com

文獻(xiàn)標(biāo)志碼：A

中圖分類號：TP181