孫　佳，　胡　明，　趙　佳

(長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 吉林 長(zhǎng)春　130012)

?

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

孫佳，胡明*，趙佳

(長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 吉林 長(zhǎng)春130012)

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

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

0引言

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

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

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

1理論基礎(chǔ)

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

(1)

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

定義2 簇均值

(2)

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

(3)

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

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

定義4 重心公式

(4)

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

2K-means算法基本思想

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

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

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

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

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

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

3)重新計(jì)算每個(gè)簇的均值作為新的聚類(lèi)中心。

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

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

3一種新的K-means聚類(lèi)中心選取算法

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

算法描述如下：

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

輸出：k個(gè)初始聚類(lèi)中心。

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

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

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

(d)重復(fù)步驟(b)，直到選取k個(gè)初始聚類(lèi)中心。

4實(shí)驗(yàn)

4.1實(shí)驗(yàn)描述

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

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

1)聚類(lèi)結(jié)果的準(zhǔn)確率方面的對(duì)比；

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

3)算法的運(yùn)行時(shí)間的對(duì)比。

4.2結(jié)果及分析

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

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

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

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

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

N----全部數(shù)據(jù)對(duì)象個(gè)數(shù)。

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

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

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

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

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

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

5結(jié)語(yǔ)

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

參考文獻(xiàn)：

[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ù)流的軟子空間聚類(lèi)算法[J].軟件學(xué)報(bào),2014,24(11):2610-2627.

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

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

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

[9]于海濤,賈美娟,王慧強(qiáng),等.基于人工魚(yú)群的優(yōu)化K-means聚類(lèi)算法[J].計(jì)算機(jī)科學(xué),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-均值的混合聚類(lèi)算法[J].計(jì)算機(jī)應(yīng)用研究,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]王金永，董玉民.改進(jìn)粒子群算法在數(shù)據(jù)聚類(lèi)中的應(yīng)用[J].長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版,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ù)的直覺(jué)模糊聚類(lèi)初始化方法[J].計(jì)算機(jī)科學(xué),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.

中圖分類(lèi)號(hào)：TP 39

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

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

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

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

基金項(xiàng)目：國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目(61133011)

收稿日期：2015-10-11