加權局部方差優化初始簇中心的K-means算法*

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

?

加權局部方差優化初始簇中心的K-means算法*

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

山東科技大學信息科學與工程學院，山東青島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 (國家自然科學基金). Received 2015-09,Accepted 2015-11.

CNKI網絡優先出版: 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.

摘要：在傳統K-means算法中，初始簇中心選擇的隨機性，導致聚類結果隨不同的聚類中心而不同。因此出現了很多簇中心的選擇方法，但是很多已有的簇中心選擇算法，其聚類結果受參數調節的影響較大。針對這

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

關鍵詞：K-means算法；方差；加權；最大最小法；簇初始中心點

1 引言

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

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

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

本文組織結構如下：第2章介紹優化初始中心點K-means算法近期的相關工作；第3章介紹本文算法的基本概念；第4章介紹基于加權局部方差的改進K-means算法（weighted local variance K-means，WLV-K-means）；第5章給出實驗結果及分析比較；第6章為結束語。

2 相關工作

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

3 基本概念

3.1 K-means算法

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

算法1 K-means算法

輸入：聚類簇的數目K；包含n個對象的數據集D。輸出：聚類結果集。

從D中任意選出K個對象作為初始中心點；

repeat

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

until簇中點不再發生變化；

3.2樣本方差

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

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

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

3.3最大最小法

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

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

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

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

4 W LV-K-means算法

4.1算法思想

在傳統的K-means算法中，初始中心點選擇的隨機性，導致了聚類結果的不穩定性。由于中心點在迭代過程中不斷更新，如果初始中心點選擇不理想，會導致更新簇時，中心點偏離簇的真實值，從而最終收斂于局部最優解。因此中心點選擇的主要問題是，除去噪聲數據以及離群點，并發現分散且具有高密度鄰域的初始點。

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

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

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

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

4.2基本定義

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

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

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

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

ρi=ωi×vi（6）

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

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

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

定義3加權最大最小值gi如式（9）所示：

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

4.3算法描述

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

算法2 WLV-K-means算法

輸入：聚類簇的數目K；包含n個對象的數據集D；鄰域半徑調節參數θ。

輸出：聚類結果集。

For D中的每個對象xi

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

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

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

for D每個對象x

根據式（9）計算x的加權最大最小值g；

end for

選擇具有最大g對應的數據點p′作為下一個初

始中心點，加入集合T，并將p′從D中刪除;

將p′鄰域內的對象從集合D中刪除；

end while

集合T作為初始中心點；

repeat

將數據集中對象劃分到距其最近的中心點所在的簇中；

將各簇的均值作為更新的中心點；

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

4.4算法分析

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

為提高算法整體的效率，減少時間空間復雜度，可以將距第K近樣本計算問題轉化為K近鄰查詢，利用數據結構k-d樹，計算距查詢樣本第K近的樣本。從而減少計算距離矩陣的時間復雜度和存儲距離矩陣的空間復雜度，進而降低算法整體的時間及空間復雜度。

5 實驗分析

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

為更客觀地對比，取100次實驗的平均值作為傳統K-means算法的聚類評價結果，其他幾種對比算法的聚類結果，均取調參后的最佳結果。

實驗結果的評價指標采用聚類準確率、聚類的誤差平方和以及標準化互信息（normalized mutual information，NM I）[20]。

設樣本集X包括k個類，聚類準確率的表示如式（10）所示：

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

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

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

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

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

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

5.1數據集描述

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

5.2實驗結果及分析

實驗的準確率、誤差平方和以及NM I的對比結果如表2、表3和表4所示，其中加粗部分為最佳的聚類結果。

Table 2 Comparison of accuracy on UCI datasets between each algorithm表2 各算法在UCI數據集的準確率比較

Table 1 Description of UCI datasets表1 UCI數據集描述

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

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

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

WLV-K-means算法對密度的計算以及中心點選取兩個階段進行改進。從實驗結果可以得出，WLVK-means算法及對比算法在3種指標的比較中，在大多數數據集上都有較好的表現。

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

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

5.3參數調節

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

從圖1中可以得出，各數據集在對應的區間中均能找到最優準確率。第一類數據集在N/ K處，準確率達到收斂狀態。第二類數據集中，當θ取較小值時的聚類效果要優于其取較大值的聚類效果。聚類準確率在參數變化區間內的變動幅度較小，說明本文算法的穩定性更好，不會出現由于參數選擇不合適而導致聚類結果過大的變化。

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

Fig.1 Variation trend of clustering accuracy on UCI datasets w ith the change of parameter圖1 UCI數據集聚類準確率隨參數變化趨勢

6 結束語

傳統K-means算法過程中，初始中心點選擇的隨機性，使得聚類結果不穩定，并且容易使聚類結果達到局部最優，難以得到理想的聚類結果。而已有的基于密度選擇中心點的優化算法，算法的聚類效果過度依賴閾值的設定，具有一定的局限性。本文提出了一種基于加權局部方差的密度計算方法，并利用改進的最大最小法，啟發式地選擇初始中心點。在UCI數據集上的實驗結果證明了本文算法提高了聚類的質量，具有較好的穩定性。

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.

附中文參考文獻：

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

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

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

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

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

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

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

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

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

[18]傅德勝,周辰.基于密度的改進K均值算法及實現[J].計算機應用, 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—），男，山東青州人，山東科技大學信息科學與工程學院碩士研究生，主要研究領域為機器學習，數據挖掘等。

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—），男，山東聊城人，博士，山東科技大學信息科學與工程學院教授，CCF高級會員，主要研究領域為機器學習，數據挖掘，分布式人工智能，多媒體信息智能處理等。

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—），男，山東青島人，博士，山東科技大學信息科學與工程學院副教授，CCF會員，主要研究領域為機器學習，數據挖掘，演化計算，海量信息處理等。

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—），女，山東寧陽人，山東科技大學信息科學與工程學院碩士研究生，主要研究領域為機器學習，數據挖掘等。

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—），女，山東煙臺人，山東科技大學信息科學與工程學院碩士研究生，主要研究領域為機器學習，數據挖掘等。

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

文獻標志碼：A

中圖分類號：TP181