K-means初始聚類中心選取優(yōu)化算法

孫　佳，　胡　明，　趙　佳

(長春工業(yè)大學 計算機科學與工程學院， 吉林 長春　130012)

?

K-means初始聚類中心選取優(yōu)化算法

孫佳，胡明*，趙佳

(長春工業(yè)大學 計算機科學與工程學院， 吉林 長春130012)

摘要：提出了一種利用重心優(yōu)化初始聚類中心的算法BKM(Barycenter K-Means)。首先將每個候選點臨域內(nèi)所有數(shù)據(jù)點的重心作為初始聚類中心，然后引入MapReduce進行并行處理計算。結(jié)果表明，BKM算法選取的初始聚類中心更為合理，取得了較好的聚類效果。

關(guān)鍵詞：聚類; K-means算法; 初始聚類中心; 算法優(yōu)化

0引言

隨著數(shù)據(jù)時代的到來，數(shù)據(jù)挖掘技術(shù)已經(jīng)成為當前的研究熱點之一[1-4]。聚類分析[5]是數(shù)據(jù)挖掘領(lǐng)域中一個重要的研究方向，它是將數(shù)據(jù)集劃分成若干個子集，使得每個子集內(nèi)部的對象相似度較高，而不同子集之間差異性較大。聚類算法大致可分為五類[6]：基于劃分的方法、基于層次的方法、基于密度的方法、基于網(wǎng)格的方法和基于模型的方法。其中，K-means算法是基于劃分的經(jīng)典聚類算法之一[7-8]，由于其操作簡單、收斂速度快等特點，得到了廣泛的應用。但是傳統(tǒng)的K-means算法也存在著一些不足之處，首先算法對初始的k個聚類中心有較大依賴性，不同的初始聚類中心得到的聚類結(jié)果也不一樣，使得初始聚類中心的選取成為影響聚類結(jié)果的質(zhì)量的重要因素之一，傳統(tǒng)的K-means算法的初始聚類中心是隨機選取的，容易陷入局部最優(yōu)；再者算法對噪音和離群點敏感；另外，從K-means 算法框架可以看出，該算法需要不斷地根據(jù)計算后的聚類中心進行分類調(diào)整，因此當數(shù)據(jù)量非常大時，算法有較大的時間開銷。

目前，很多研究者對K-means算法進行了改進[9-13]。文獻[14]提出了一種基于最大最小距離法選取初始聚類中心的方法，算法能夠計算出K值，并找出K個合理的聚類中心，但是算法容易選定邊緣數(shù)據(jù)作為初始聚類中心，而且需要較大時間消耗。文獻[15]用密度函數(shù)法求得樣本空間的多個聚類中心，并結(jié)合小類合并運算，避免局部最小，但是算法具有較大的時間開銷。文獻[16]根據(jù)聚類對象分布密度函數(shù)來確定多個初始聚類中心，但是算法的時間復雜度較高。

針對上述問題，文中提出了一種新的基于初始聚類中心選取的改進算法KMM，通過對候選點μ范圍的數(shù)據(jù)點的重心進行選取，作為初始聚類中心，采用MapReduce并行框架對提出的算法進行實現(xiàn)。實驗結(jié)果表明，KMM算法能夠有效地排除噪聲點和孤立點，選取合理的初始聚類中心，從而得到較佳的聚類結(jié)果，減少算法迭代次數(shù)，并且應用MapReduce并行處理框架，使算法的運行更為高效。

1理論基礎(chǔ)

定義1兩個數(shù)據(jù)對象間的歐氏距離

(1)

其中，xi=[xi1,xi2,…,xin],xj=[xj1,xj2,…,xjn]是具有n個屬性的兩個數(shù)據(jù)對象。

定義2 簇均值

(2)

定義3 誤差平方和準則函數(shù)

(3)

式中：Mk----簇Ck中數(shù)據(jù)對象的中心;

q----簇Ck中的數(shù)據(jù)對象。

定義4 重心公式

(4)

式中：pi----候選點μ范圍的數(shù)據(jù)點。

2K-means算法基本思想

傳統(tǒng)的K-means算法基本思想：首先從數(shù)據(jù)集中隨機選取k個數(shù)據(jù)作為初始聚類中心，計算數(shù)據(jù)集中其他的數(shù)據(jù)對象到k個初始聚類中心的距離，并將其劃分到離它最近的聚類中心所在的簇中；然后計算每個簇的均值作為新的聚類中心，不斷重復這一過程，直至誤差平方準則函數(shù)收斂，迭代終止。

傳統(tǒng)K-means算法過程如下：

輸入：數(shù)據(jù)集D={x1,x2,…,xn}，初始k值，迭代終止條件ε。

輸出：滿足終止條件的K個簇以及迭代次數(shù)n。

1)在數(shù)據(jù)集D中隨機選擇k個對象作為初始聚類中心。

2)計算D中剩余對象到每個初始聚類中心的距離，并將其劃分到距離最近的聚類中心所在的簇中。

3)重新計算每個簇的均值作為新的聚類中心。

4)計算此時的誤差平方和準則函數(shù)，若滿足|Jc(I)-Jc(I-1)|<ε,其中ε為設(shè)定的一個極小參數(shù)，算法終止。

5)否則，繼續(xù)執(zhí)行步驟2)。

3一種新的K-means聚類中心選取算法

傳統(tǒng)的K-means算法的初始聚類中心是隨機選擇的，然而通過對K-means算法的分析發(fā)現(xiàn)，初始聚類中心的選擇會對聚類結(jié)果造成較大影響。文中提出的算法首先選取某數(shù)據(jù)點作為候選點，計算該候選點μ范圍的數(shù)據(jù)點的重心作為第1個初始聚類中心，然后選取離該聚類中心最遠的點作為第2個候選點，重復計算重心的過程，依次類推，直到選完k個初始聚類中心。這樣選取初始聚類中心的優(yōu)勢在于一方面通過對候選點μ范圍數(shù)據(jù)的篩選，能夠排除離群點和噪音數(shù)據(jù)，另一方面將一定范圍內(nèi)的數(shù)據(jù)的重心作為初始聚類中心，能夠降低算法的迭代次數(shù)，并且取得較好的聚類效果。

算法描述如下：

輸入：數(shù)據(jù)集D={x1,x2,…,xn}，初始k值。

輸出：k個初始聚類中心。

(a)設(shè)數(shù)據(jù)集D中有n個對象，D={x1,x2,…,xn}，從中任取一個數(shù)據(jù)點,如xi作為初始候選點，計算xi與其他數(shù)據(jù)點的距離。

(b)選取與xj距離小于μ的數(shù)據(jù)點，若存在，計算的范圍內(nèi)所有數(shù)據(jù)點的重心G1作為第一個聚類中心點，否則，返回步驟(a)。

(c)選取距離G1最遠的數(shù)據(jù)點xj作為第二個候選點，并計算xj與其他剩余數(shù)據(jù)點的距離。

(d)重復步驟(b)，直到選取k個初始聚類中心。

4實驗

4.1實驗描述

實驗是在搭建的hadoop2.0平臺上運行的，實驗環(huán)境中的集群共9個節(jié)點，其中，1個master節(jié)點和8個slave節(jié)點。在集群的眾多節(jié)點中，每臺機器的配置均是相同的(CPU主頻3.4 GHz、2.0 G內(nèi)存、1 T硬盤)，為了測試算法的性能，文中選取UCI機器學習數(shù)據(jù)庫中的Iris和KDD Cup 1999 Data Set兩個不同規(guī)模的數(shù)據(jù)集作為實驗數(shù)據(jù)進行測試。

將文中提出的算法與原始K-means算法進行以下性能方面的對比分析：

1)聚類結(jié)果的準確率方面的對比；

2)算法運行的迭代次數(shù)方面的對比；

3)算法的運行時間的對比。

4.2結(jié)果及分析

兩種算法在Iris數(shù)據(jù)集上的測試結(jié)果見表1。

表1　兩種算法在Iris數(shù)據(jù)集的測試結(jié)果

表1中可以清楚地看到，原始K-means算法的準確率最高為88.52%，最低為52.44%，平均值為74.85%，準確率的范圍波動很大，這也是由于原始K-means算法在選取初始聚類中心點時采用隨機選取的方法，并不能保證每次選取的聚類中心都是合理的，當初始聚類中心點選取不當時，就容易導致聚類結(jié)果的準確性較低。而文中提出的改進算法準確率最高為89.28%，最低為72.34%，平均值為84.756%。算法在準確率方面總體高于原始K-means算法，說明提出的改進算法選取的初始中心點更為合理，得到的聚類結(jié)果更為準確。

將兩種算法分別運行10次。Iris數(shù)據(jù)集有150條數(shù)據(jù)，每條數(shù)據(jù)包含4個屬性，數(shù)據(jù)集分為3類。將兩種算法在準確率方面進行對比，這里準確率表示為：

式中：c----能夠被正確分配到指定類的數(shù)據(jù)對象的個數(shù)；

N----全部數(shù)據(jù)對象個數(shù)。

兩種算法在Iris數(shù)據(jù)集上運行時的迭代次數(shù)比較依然是在Iris數(shù)據(jù)集上進行的測試。如圖1所示。

圖1　兩種算法在Iris數(shù)據(jù)集上運行時的迭代次數(shù)比較

從圖1可以看出，選擇的初始聚類中心不同，那么算法的迭代次數(shù)也不相同，原始K-means算法的迭代次數(shù)較為不穩(wěn)定，波動幅度很大。這種現(xiàn)象說明，如果選取的初始聚類中心離實際各簇中心點較遠，會導致目標函數(shù)收斂速度慢，造成算法迭代次數(shù)的增加。從圖1很容易看出，文中提出的改進算法在迭代次數(shù)方面明顯少于原始K-means算法。說明改進的算法得到了與實際數(shù)據(jù)的簇中心點較為接近的初始聚類中心點，使得算法收斂速度更快，加快了聚類的過程，得到了較為穩(wěn)定的聚類結(jié)果。

兩種算法的運行時間和數(shù)據(jù)量的關(guān)系如圖2所示。

圖2　算法的運行時間和數(shù)據(jù)量的關(guān)系圖

隨機選取KDD Cup 1999 Data Set的2 000～10 000條數(shù)據(jù)進行算法驗證。從圖2可以看出，我們提出的改進算法在數(shù)據(jù)量少的時候和原始K-means算法的運行時間相差較少。而隨著數(shù)據(jù)量的不斷增加，原始K-means算法的執(zhí)行時間呈幾何增長趨勢，說明原始K-means算法對數(shù)據(jù)集的變化較為敏感，當數(shù)據(jù)規(guī)模增長時，它的執(zhí)行時間也會大幅度增長，這并不利于大規(guī)模數(shù)據(jù)的處理。相比較而言，文中提出的改進算法的執(zhí)行時間雖然也呈增長的趨勢，但是相對原始K-means算法來說，幅度增長較為緩慢，算法整體的運行時間少于原始K-means算法。這是由于改進的算法應用MapReduce并行處理框架，能夠更快速高效地處理大規(guī)模數(shù)據(jù)集。

5結(jié)語

研究了基于初始聚類中心的優(yōu)化算法BKM，將候選點μ范圍內(nèi)的數(shù)據(jù)點的重心作為初始聚類中心進行聚類。有效地解決了原始算法中對離群點和噪音數(shù)據(jù)敏感的問題，并且，算法每次都選取距離較遠的點作為初始聚類中心，有效解決了算法容易陷入局部最優(yōu)的缺陷。并將MapReduce并行編程框架引入算法改進中，提高了算法的運行時間。文中所提到的μ，它的取值是一個開放性問題，需要根據(jù)具體的數(shù)據(jù)集的特點進行設(shè)定。對于初始K值的選定，將是進一步的研究內(nèi)容。

參考文獻：

[1]Witten, Ian H, Frank, et al. Data Mining:Practical machine learning tools and techniques[J]. Biomedical Engineering Online,2011,51(1):95-97.

[2]Wu X, Zhu X, Wu G Q, et al. Data mining with big data[J]. Knowledge & Data Engineering IEEE Transactions on,2014,26(1):97-107.

[3]Wang S, Shi W. Data mining and knowledge discovery[J]. Springer Handbook of Geographic Information,2011,25(3):545-576.

[4]Yin Y, Kaku I, Tang J, et al. Privacy-preserving data mining[J]. Decision Engineering,2011,2(3):86-92.

[5]朱林,雷景生,畢忠勤,等.一種基于數(shù)據(jù)流的軟子空間聚類算法[J].軟件學報,2014,24(11):2610-2627.

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

[7]陳小全,張繼紅.基于改進粒子群算法的聚類算法[J].計算機研究與發(fā)展,2012,49(z1):287-291.

[8]周煒奔,石躍祥.基于密度的K-means聚類中心選取的優(yōu)化算法[J].計算機應用研究,2012,29(5):1726-1728.

[9]于海濤,賈美娟,王慧強,等.基于人工魚群的優(yōu)化K-means聚類算法[J].計算機科學,2012,39(12):60-64.

[10]Silva A D, Chiky R, Hébrail G. A clustering approach for sampling data streams in sensor networks[J]. Knowledge & Information Systems,2012,32(1):1-23.

[11]畢曉君,宮汝江.一種結(jié)合人工蜂群和K-均值的混合聚類算法[J].計算機應用研究,2012,29(6):2040-2042.

[12]Cui X, Zhu P, Yang X, et al. Optimized big data K-means clustering using MapReduce[J]. Journal of Supercomputing,2014,70(3):1249-1259.

[13]王金永，董玉民.改進粒子群算法在數(shù)據(jù)聚類中的應用[J].長春工業(yè)大學學報：自然科學版,2015,36(6):664-672.

[14]Zhang Z P, Wang A J. Easy and efficient algorithm to determine number of clusters[J]. Computer Engineering & Applications,2009,45(15):166-168.

[15]ZHOU Shi bing, XU Zhen yuan. New method for determining optimal number of clusters in K-means clustering algorithm[J]. Computer Engineering & Applications,2010，46(16)：1995-1998.

[16]申曉勇,雷英杰,蔡茹,等.一種基于密度函數(shù)的直覺模糊聚類初始化方法[J].計算機科學,2009,36(5):197-199.

An optimal algorithm for K-means initial clustering center selection

SUN Jia,HU Ming*,ZHAO Jia

(School of Computer Science & Engineering, Changchun University of Technology, Changchun 130012， China)

Abstract：A Barycenter K-Means (BKM) algorithm with optimized center as initial clustering center is proposed in the paper. At first, the center of all data in the selected region are taken as initial centers and then the parallel MapReduce Processing Framework is introduced into the algorithm. The experimental results show that the selected initial clustering center of the BKM algorithm is reasonable and better clustering results are obtained.

Key words：clustering; K-Means algorithm; initial clustering center; optimized algorithm.

中圖分類號：TP 39

文獻標志碼：A

文章編號：1674-1374(2016)01-0025-05

DOI:10.15923/j.cnki.cn22-1382/t.2016.1.06

作者簡介：孫佳(1991-)，女，漢族，吉林舒蘭人，長春工業(yè)大學碩士研究生，主要從事數(shù)據(jù)挖掘方向研究，E-mail:sunjia_207@126.com. *通訊作者：胡明(1963-)，男，漢族，吉林長春人，長春工業(yè)大學教授，博士，主要從事分布式計算、數(shù)據(jù)挖掘方向研究,E-mail:huming@ccut.edu.cn.

基金項目：國家自然科學基金重點項目(61133011)

收稿日期：2015-10-11