一種局部概率引導(dǎo)的優(yōu)化K-means++算法

王海燕,崔文超,許佩迪,李 闖

(1.長(zhǎng)春大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院,長(zhǎng)春 130022；2.吉林大學(xué) 理論化學(xué)研究所,長(zhǎng)春 130021;3.吉林師范大學(xué) 計(jì)算機(jī)學(xué)院,吉林 四平 136000)

1 引言與預(yù)備知識(shí)

聚類分析(cluster analysis)[1]又稱群分析,是研究分類問(wèn)題的一種統(tǒng)計(jì)分析方法,是數(shù)據(jù)挖掘領(lǐng)域中重要的無(wú)監(jiān)督機(jī)器學(xué)習(xí)方法.聚類算法用途廣泛,如區(qū)分消費(fèi)群體、獲取消費(fèi)趨勢(shì)、輿情分析及幫助市政規(guī)劃等.常見(jiàn)的聚類算法有劃分法、層次法、密度法、圖論法、網(wǎng)格法和模型法等,其中劃分法應(yīng)用廣泛.K-means聚類是經(jīng)典的劃分聚類算法,具有方法簡(jiǎn)單、效率高的特點(diǎn).

隨著K-means算法的廣泛應(yīng)用,其缺陷逐漸凸顯[2]：1) 聚類中心數(shù)目K需要在聚類分析前確定,而這在實(shí)際應(yīng)用中很難估計(jì)；2) 初始聚類中心需要人為選取,而不同的初始聚類可能導(dǎo)致不同的聚類結(jié)果.針對(duì)K-means算法的不足,目前已有許多改進(jìn)算法：成衛(wèi)青等[3]基于數(shù)據(jù)實(shí)例間的最大最小距離選取初始聚類中心,基于誤差平方和(SSE)選擇相對(duì)最稀疏的簇分裂,并根據(jù)SSE變化趨勢(shì)停止簇分裂從而自動(dòng)確定簇?cái)?shù)；蔣麗等[4]提出了一種改進(jìn)的K-means聚類算法,先根據(jù)類簇指標(biāo)確定需要聚類的個(gè)數(shù)K,再采用基于密度的思想,實(shí)驗(yàn)證明改進(jìn)后的算法比原K-means聚類算法準(zhǔn)確性更高；針對(duì)第二項(xiàng)不足,周愛(ài)武等[5]通過(guò)基于評(píng)價(jià)距離確定初始聚類中心,優(yōu)化后的算法針對(duì)存在孤立點(diǎn)的數(shù)據(jù)效果明顯；Gu[6]采用減法聚類的算法確定初始聚類中心；鮑雷[7]針對(duì)傳統(tǒng)K-means聚類算法在數(shù)據(jù)聚類分析時(shí)受初始聚類中心的影響,提出了將遺傳算法嵌入到K-means算法中的混合式聚類算法.

K-means++是一種針對(duì)K-means算法第二類不足提出的優(yōu)化算法[8].在K-means算法中,初始中心是以隨機(jī)方式產(chǎn)生的,而K-means++算法則是在選取初始中心前對(duì)所有的數(shù)據(jù)進(jìn)行一次計(jì)算,使選擇的初始聚類中心間的相互距離盡可能遠(yuǎn),以減少計(jì)算的過(guò)程量.如果隨機(jī)產(chǎn)生的中心點(diǎn)過(guò)于相似,則會(huì)導(dǎo)致需要多次迭代才能將聚類劃分開(kāi).而如果選擇的初始中心點(diǎn)距離較大,則其屬于同一個(gè)聚簇的可能性極小,使得聚類在最開(kāi)始時(shí)就能很好地分開(kāi),因此計(jì)算量也會(huì)相應(yīng)減少.假設(shè)數(shù)據(jù)集合X={x1,x2,…,xn},聚類數(shù)目為K,D(x)表示從數(shù)據(jù)點(diǎn)到已選取的最近聚類中心的最短距離.K-means++算法工作流程如下：

步驟1) 從數(shù)據(jù)集合X中隨機(jī)取一點(diǎn)作為第一個(gè)聚類中心c1；

步驟2) 通過(guò)某種特定方式,在數(shù)據(jù)集合X中選取x作為下一個(gè)聚類中心ci；

步驟3) 重復(fù)步驟2),直到選取K個(gè)聚類中心；

步驟4) 繼續(xù)使用標(biāo)準(zhǔn)K-means算法進(jìn)行下一步計(jì)算.

在對(duì)K-means++算法研究的過(guò)程中,工作流程中步驟2)選取初始聚類中心點(diǎn)的特定方式有很多種,最經(jīng)典的主要有以下幾種：

2) 計(jì)算每個(gè)數(shù)據(jù)樣本的密度,并按密度大小排序,將密度最大的數(shù)據(jù)樣本點(diǎn)與其最接近樣本點(diǎn)的中點(diǎn)作為初始聚類中心,最后使用圓域進(jìn)行劃分[10]；

3) 先選取一個(gè)種子點(diǎn),再計(jì)算檢測(cè)節(jié)點(diǎn)與最近種子節(jié)點(diǎn)間的距離D(xi,yi),求取sum(D(xi,yi)),再取可以落在sum(D(xi,yi))中的隨機(jī)值random,計(jì)算random-=D(xi,yi),直至random<0,此時(shí)的點(diǎn)即為新的簇中心點(diǎn),重復(fù)操作直到全部選取出K個(gè)種子節(jié)點(diǎn)[11].

但K-means++算法初始聚類中心選取方式計(jì)算出的誤差平方和值上下波動(dòng)明顯,會(huì)出現(xiàn)誤差平方和過(guò)大或過(guò)小的情形.為了改善該不足,本文提出一種局部概率引導(dǎo)的PK-means++算法,借助局部概率對(duì)選取初始聚類中心點(diǎn)的方式進(jìn)行改進(jìn).為說(shuō)明PK-means++算法的優(yōu)勢(shì),本文將改進(jìn)算法應(yīng)用在具有代表性的分散數(shù)據(jù)集上,在針對(duì)同一K值的情形下聚類時(shí),聚類后的誤差平方和較原K-means++算法更穩(wěn)定,保證了隨機(jī)實(shí)驗(yàn)取值的穩(wěn)定性.

2 K-means++算法優(yōu)化

2.1 問(wèn)題描述

圖1 西瓜數(shù)據(jù)集4.0誤差平方和曲線Fig.1 Curve of sum squared error on watermelon data set 4.0

在K-means++算法3種選取初始聚類中心方式中,最常見(jiàn)的是最后一種.但在使用第三種方式進(jìn)行多次聚類實(shí)驗(yàn)時(shí),誤差平方和間有明顯波動(dòng).即常用的K-means++算法得到的誤差平方和受實(shí)驗(yàn)隨機(jī)性的影響較大.

本文以西瓜數(shù)據(jù)集4.0為例進(jìn)行聚類.首先,將數(shù)據(jù)集的聚類個(gè)數(shù)設(shè)為4,然后使用常見(jiàn)的選取初始聚類中心的方式將西瓜數(shù)據(jù)集4.0的30個(gè)二維數(shù)據(jù)向量進(jìn)行K-means++聚類.圖1為西瓜數(shù)據(jù)集4.0誤差平方和曲線.由圖1可見(jiàn),誤差平方和的取值不穩(wěn)定,上下波動(dòng)較明顯,最大值超過(guò)0.45,最小值接近0.25,這種波動(dòng)會(huì)嚴(yán)重影響聚類的精度和速度.

2.2 PK-means++算法

為進(jìn)一步縮小誤差、減少工作量,本文針對(duì)K-means++算法在誤差平方和取值時(shí)遇到的問(wèn)題進(jìn)行優(yōu)化.主要思想是通過(guò)K-means++算法計(jì)算每個(gè)點(diǎn)所占的概率區(qū)間,距離越遠(yuǎn)的點(diǎn)在(0,1)中占有概率段比例越大,隨機(jī)取到該區(qū)間的概率就越大.

假設(shè)將輸入設(shè)置為：一個(gè)包含n個(gè)對(duì)象的集合D；聚類個(gè)數(shù)K；距離數(shù)組D[n],D[i]表示第i個(gè)點(diǎn)到最近簇中心的距離；概率數(shù)組P[n]； 概率點(diǎn)數(shù)組PK[n].

將輸出設(shè)置為K個(gè)聚類中心點(diǎn)集合.則PK-means++算法步驟如下：

1) 在數(shù)組中,隨機(jī)取一點(diǎn),作為第一個(gè)簇中心點(diǎn)；

2) 迭代集合D中所有的點(diǎn),計(jì)算所有點(diǎn)到最近簇中心點(diǎn)的距離,并將數(shù)據(jù)記錄到距離數(shù)組中,記為D[1],D[2],…,D[n]；

3) 將所有的D[i](i=1,2,…,n)疊加,得到距離和Sum(D[n]),并分別計(jì)算D[i]在Sum(D[n])中的概率,記為P[i];將概率P[i]通過(guò)概率段的形式在(0,1)中表示,將概率段的起始點(diǎn)存入數(shù)組PK中；

4) 取隨機(jī)數(shù)rP(0

5) 重復(fù)步驟2)～步驟4),直至K個(gè)聚類初始中心全部選出；

6) 繼續(xù)使用標(biāo)準(zhǔn)的K-means算法進(jìn)行下一步計(jì)算.

圖2 數(shù)據(jù)組P和數(shù)據(jù)組PKFig.2 Data group P and data group PK

以第一個(gè)初始聚類中心下標(biāo)為4的聚類為例,將各數(shù)據(jù)點(diǎn)到第一個(gè)聚類中心的距離概率表示在(0,1)區(qū)間上,結(jié)果如圖2所示.其中,數(shù)據(jù)組P存儲(chǔ)的各數(shù)據(jù)表示各點(diǎn)到第一個(gè)初始聚類中心距離的概率段,其中P[4]=0.數(shù)據(jù)組PK存儲(chǔ)的是概率段在(0,1)內(nèi)的實(shí)際點(diǎn)數(shù)據(jù),若隨機(jī)取的rP值在區(qū)間(PK[n-1],PK[n]]內(nèi),則把第n個(gè)數(shù)據(jù)點(diǎn)作為下一個(gè)聚類中心.

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

3.1 數(shù)據(jù)集

圖3 20個(gè)(1,5)區(qū)間的隨機(jī)點(diǎn)Fig.3 Twenty random points of zone (1,5)

為了驗(yàn)證算法PK-means++在誤差平方和方面的優(yōu)勢(shì),本文將數(shù)據(jù)集合鎖定在分散數(shù)據(jù)集上,為保證是相對(duì)分散的數(shù)據(jù)集,隨機(jī)取5×5正方形(橫坐標(biāo)x∈(0,5),縱坐標(biāo)y∈(0,5))內(nèi)的20個(gè)二維數(shù)據(jù)點(diǎn)作為數(shù)據(jù)集Ⅰ,數(shù)據(jù)點(diǎn)可視化效果如圖3所示.隨機(jī)取10×10正方形內(nèi)的20個(gè)二維數(shù)據(jù)點(diǎn)作為數(shù)據(jù)集Ⅱ,數(shù)據(jù)點(diǎn)可視化效果如圖4所示；隨機(jī)取10×10正方形內(nèi)的50個(gè)二維數(shù)據(jù)點(diǎn)作為數(shù)據(jù)集Ⅲ,數(shù)據(jù)點(diǎn)可視化效果如圖5所示.由圖3～圖5可見(jiàn),研究選取的數(shù)據(jù)非常分散.

圖4 20個(gè)(1,10)區(qū)間的隨機(jī)點(diǎn)Fig.4 Twenty random points of zone (1,10)

圖5 50個(gè)(1,10)區(qū)間的隨機(jī)點(diǎn)Fig.5 Fifty random points of zone (1,10)

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

在上述選取分散數(shù)據(jù)的基礎(chǔ)上,為充分說(shuō)明PK-means++算法的優(yōu)越性,下面分別對(duì)K-means++算法和PK-means++算法進(jìn)行多次對(duì)比聚類實(shí)驗(yàn).參考文獻(xiàn)[12],實(shí)驗(yàn)環(huán)境為：Intel(R) CoreTMi5-7200處理器,主頻為2.50 GHz,內(nèi)存為8.00 GB.分別做10次實(shí)驗(yàn),記錄10次實(shí)驗(yàn)的誤差平方和,并針對(duì)不同的數(shù)據(jù)集給出兩種算法的對(duì)比曲線.

選取數(shù)據(jù)集Ⅰ,對(duì)比K-means++和PK-means++算法聚類計(jì)算得出的誤差平方和,結(jié)果如圖6所示.由圖6可見(jiàn),PK-means++算法計(jì)算得出的誤差平方和變化較平穩(wěn),而原始K-means++算法計(jì)算的誤差平方和上下浮動(dòng)相對(duì)較大.這是因?yàn)镵-means++算法先隨機(jī)選取一個(gè)小于距離和的數(shù),然后將隨機(jī)數(shù)作為被減數(shù)依次做減距離操作,最后取差小于0時(shí)的點(diǎn)作為下一個(gè)初始聚類點(diǎn),而PK-means++算法是在距離概率(0,1)內(nèi)取點(diǎn).在聚類較明顯的數(shù)據(jù)集中這兩種算法對(duì)誤差平方和都無(wú)太大影響.說(shuō)明PK-means++算法對(duì)聚類效果較明顯的數(shù)據(jù)集聚類后不會(huì)產(chǎn)生太大影響.而對(duì)較分散的數(shù)據(jù)集,數(shù)據(jù)點(diǎn)之間的距離較平均,距離差異較小,PK-means++算法隨機(jī)取數(shù)的范圍較K-means++取數(shù)的范圍小,取數(shù)的波動(dòng)性較小導(dǎo)致取點(diǎn)的波動(dòng)性較小,每次實(shí)驗(yàn)取點(diǎn)的結(jié)果較接近,從而保證了誤差平方和的上下波動(dòng)較小,進(jìn)而呈現(xiàn)一種穩(wěn)定的狀態(tài).

為進(jìn)一步證明PK-means++算法的優(yōu)勢(shì),本文將實(shí)驗(yàn)規(guī)模擴(kuò)大到數(shù)據(jù)集Ⅱ和數(shù)據(jù)集Ⅲ上,K-means++算法和PK-means++算法計(jì)算得出的誤差平方和曲線分別如圖7和圖8所示.由圖7和圖8可見(jiàn),PK-means++算法在平穩(wěn)程度上仍有絕對(duì)優(yōu)勢(shì),而K-means++算法波動(dòng)幅度仍較大,隨機(jī)取值得到的不一定是最佳實(shí)際數(shù)據(jù).

圖6 兩種算法對(duì)數(shù)據(jù)集Ⅰ誤差平方和的對(duì)比Fig.6 Comparison of two algorithms for sum squared error on data set Ⅰ

圖7 兩種算法對(duì)數(shù)據(jù)集Ⅱ誤差平方和的對(duì)比 Fig.7 Comparison of two algorithms for sum squared error on data set Ⅱ

為證明PK-means++算法的優(yōu)越性,本文選擇在西瓜數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),并將實(shí)驗(yàn)基數(shù)設(shè)為10次.圖9為西瓜數(shù)據(jù)集使用K-means++算法和PK-means++算法實(shí)驗(yàn)10次得到的誤差平方和對(duì)比曲線.由圖9可見(jiàn),PK-means++算法計(jì)算得出的誤差平方和較K-means++算法上下浮動(dòng)較小,結(jié)果較平均,表明PK-means++c有優(yōu)勢(shì).

圖8 兩種算法對(duì)數(shù)據(jù)集Ⅲ誤平方和的對(duì)比Fig.8 Comparison of two algorithms for sum squared error on data set Ⅲ

圖9 兩種算法對(duì)西瓜數(shù)據(jù)集4.0誤差平方和的對(duì)比Fig.9 Comparison of two algorithms for sum squared error on watermelon data set 4.0

4 PK-means++算法應(yīng)用

本文將PK-means++算法應(yīng)用到Seeds數(shù)據(jù)集上,計(jì)算Seeds數(shù)據(jù)集組內(nèi)的誤差平方和(SSE).由于已經(jīng)驗(yàn)證了PK-means++算法在計(jì)算誤差平方和方面的穩(wěn)定性,因此,在對(duì)Seeds數(shù)據(jù)集的實(shí)驗(yàn)過(guò)程中,本文針對(duì)每個(gè)K僅進(jìn)行單次實(shí)驗(yàn)即可,即通過(guò)誤差平方的方式確定聚類數(shù)K的最佳數(shù)值.利用PK-means++算法分別計(jì)算K=2,3,4,5時(shí)的誤差平方和,結(jié)果列于表1.

表1 PK-means++算法計(jì)算不同K值的SSE

手肘法[13]的核心指標(biāo)是誤差平方和,該方法可獲得較準(zhǔn)確的聚類數(shù),最終圖形為手肘的形狀.隨著聚類數(shù)K的增大,樣本劃分更精細(xì),每個(gè)簇的聚合程度逐漸提高,則SSE會(huì)逐漸變小,整個(gè)過(guò)程的SSE可歸結(jié)為下列3個(gè)階段[14]：

1) 當(dāng)K小于真實(shí)聚類數(shù)時(shí),K的增大會(huì)大幅度增加每個(gè)簇的聚合程度,故SSE的下降幅度會(huì)很大；

2) 當(dāng)K到達(dá)真實(shí)聚類數(shù)時(shí),此時(shí)是一個(gè)過(guò)渡期,若繼續(xù)增加K,則所得到的聚合程度回報(bào)會(huì)迅速變小,故SSE的下降幅度會(huì)驟減；

3) 當(dāng)K值大于真實(shí)聚類數(shù)時(shí),SSE會(huì)隨K的增大而趨于平緩.

最終的誤差平方和SSE和K的關(guān)系圖是一個(gè)手肘形狀,而肘部對(duì)應(yīng)的K值即為數(shù)據(jù)的真實(shí)聚類數(shù),如圖10所示.由圖10可見(jiàn),聚類數(shù)K=3是Seeds的最佳聚類個(gè)數(shù).利用PK-means++算法聚類后的效果如圖11所示.由圖11可見(jiàn),PK-means++算法將Seeds數(shù)據(jù)集成功聚類為3個(gè)類別.

圖10 Seeds數(shù)據(jù)集手肘圖Fig.10 Elbow diagram of Seeds data set

圖11 Seeds使用PK-means++算法的聚類效果Fig.11 Clustering effect of PK-means++ algorithm on Seeds

綜上所述,針對(duì)K-means++算法在使用常見(jiàn)的選取初始聚類中心方式對(duì)較分散數(shù)據(jù)集進(jìn)行誤差平方和計(jì)算時(shí),聚類結(jié)果的誤差平方和影響波動(dòng)較大的問(wèn)題,本文提出了一種PK-means++算法,該算法在進(jìn)行較分散數(shù)據(jù)集聚類時(shí),借助局部概率引導(dǎo)聚類中心的選取,選取初始聚類中心的方式在同一K值的情形下對(duì)較分散的數(shù)據(jù)集可取到較穩(wěn)定的誤差平方和,即PK-means++算法提高了誤差平方和的準(zhǔn)確度,聚類后的誤差平方和比K-means++算法更穩(wěn)定,從而更好地保證了隨機(jī)實(shí)驗(yàn)取值的穩(wěn)定性.