陳賢宇，李有強(qiáng)，呂苗苗，盧建成，陳文強(qiáng)

(安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230039)

基于二分法的K-means算法的實(shí)現(xiàn)

陳賢宇，李有強(qiáng)，呂苗苗，盧建成，陳文強(qiáng)

(安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230039)

在圖像處理大領(lǐng)域內(nèi)，對(duì)特征值的處理尤為重要，而K-means算法是被運(yùn)用于特征值聚類的重要方法之一，該方法簡(jiǎn)單快捷，聚類效果較佳，因而被學(xué)術(shù)界廣泛使用。針對(duì)傳統(tǒng)的K-means算法在進(jìn)行數(shù)據(jù)集劃分過(guò)程中的不足之處，提出了一種基于二分法的K-means聚類算法，該算法對(duì)數(shù)據(jù)集進(jìn)行劃分來(lái)選擇出下次劃分的數(shù)據(jù)集，以此來(lái)形成迭代，實(shí)驗(yàn)表明該算法相比于傳統(tǒng)算法在劃分方面有了明顯的改進(jìn)。

K均值；二分法；聚類中心

0 引言

在數(shù)據(jù)處理與查詢領(lǐng)域，專家學(xué)者們提出過(guò)很多種有效的方法，其中傳統(tǒng)的K-means方法是早期一個(gè)基于中心的經(jīng)典的聚類方法，因其理論研究可靠，算法簡(jiǎn)單，時(shí)間復(fù)雜度低而被廣泛應(yīng)用。當(dāng)然，傳統(tǒng)k-means在數(shù)據(jù)處理方面存在一定缺陷[1-3]：傳統(tǒng)的K-means聚類算法對(duì)聚類中心的選取有一定的局限性，其過(guò)分依賴于聚類中心的選?。粚?shí)驗(yàn)之前，往往無(wú)法確定聚類參數(shù)K的取何值時(shí)可使得聚類效果更好。所以在實(shí)際應(yīng)用中，就很難獲得一個(gè)適當(dāng)?shù)腒值來(lái)使聚類效果更佳，這樣便增加了用戶的負(fù)擔(dān)。由上可知傳統(tǒng)k-means的這些缺陷使得學(xué)者對(duì)聚類算法的研究仍在繼續(xù)，試圖找出一種可以代替或者改進(jìn)傳統(tǒng)K-means算法的優(yōu)質(zhì)聚類算法。

考慮到傳統(tǒng)K-means算法在某些方面的局限性，學(xué)者們做過(guò)一系列的研究，例如，在離散數(shù)據(jù)的快速聚類方面，有學(xué)者提出k-modes算法，這種算法在保留K-means算法效率的同時(shí)又實(shí)現(xiàn)了對(duì)離散數(shù)據(jù)的處理，使得實(shí)驗(yàn)的應(yīng)用范圍有所擴(kuò)大。其次，在K-modes算法方面有所延伸的k-Prototype算法，該算法不僅考慮到了離散數(shù)據(jù)的特殊情況，還考慮到了數(shù)據(jù)集的數(shù)據(jù)屬性，將這2種情況加以融合即得到k-Prototype算法，該算法提出了相異性度量標(biāo)準(zhǔn)的概念，使實(shí)驗(yàn)效果有所提高。

本文從整體數(shù)據(jù)集出發(fā)，試圖找出二分后的數(shù)據(jù)對(duì)K-means聚類的幫助作用，這樣就可以克服K均值算法收斂于局部的問(wèn)題，可以使得實(shí)驗(yàn)效果更佳。

1 傳統(tǒng)K-means算法

1.1 具體步驟

從文獻(xiàn)[4-6]中可以歸納出傳統(tǒng)的K-means算法步驟。輸入：聚類數(shù)值K和含有N個(gè)對(duì)象的數(shù)據(jù)集X=x1,x2,x3,...xn。輸出：K個(gè)聚類簇s1,s2,s3...sk實(shí)驗(yàn)效果是使目標(biāo)函數(shù)最小。

①?gòu)?數(shù)據(jù)集X中隨機(jī)選擇K個(gè)對(duì)象作為初始聚類中心c1,c2,c3,...ck；

② 重復(fù)；

③ 逐個(gè)將對(duì)象xii=1,2,3...n按照歐式距離分配給最近的一個(gè)聚類中心cj，1≤j≤k1≤j≤K,則：

(m為數(shù)據(jù)屬性的個(gè)數(shù))；

④ 重新計(jì)算每個(gè)簇中新的聚類中心cj,cj=1/Nj∑xi,j=1,2,3...kj,Nj是第j個(gè) 簇sj中對(duì)象的個(gè)數(shù)；

⑤ 直到K個(gè)聚類中心不在變化，準(zhǔn)則函數(shù)收斂。

傳統(tǒng)K-means算法的基本流程圖如圖1所示。

圖1 傳統(tǒng)K-means算法流程圖

據(jù)此專家學(xué)者們通過(guò)大量實(shí)驗(yàn)驗(yàn)證該算法的可行性，同時(shí)可以看到K-means算法淺顯易懂，可以通過(guò)圖2了解K-means算法的核心思想:從數(shù)據(jù)集中隨機(jī)選擇K個(gè)對(duì)象作為初始聚類中心，然后計(jì)算數(shù)據(jù)集中每個(gè)對(duì)象與這些中心對(duì)像的距離，距離符合條件的劃分一類，不斷調(diào)整檢測(cè)標(biāo)準(zhǔn)重復(fù)上述步驟即可完成實(shí)驗(yàn)。

圖2 K-means算法圖示

1.2 傳統(tǒng)K-means算法的優(yōu)缺點(diǎn)

K-Means聚類算法的優(yōu)點(diǎn)簡(jiǎn)單來(lái)說(shuō)有以下幾點(diǎn)[7-9]:① 算法快速、簡(jiǎn)單；② 該算法對(duì)大數(shù)據(jù)集有較高的效率；③ 時(shí)間復(fù)雜度近于線性，而且適合挖掘大規(guī)模數(shù)據(jù)集。K-means聚類算法的時(shí)間復(fù)雜度是on*k*m,其中n為數(shù)據(jù)中數(shù)據(jù)對(duì)象的個(gè)數(shù)，m為算法迭代的次數(shù)，k為認(rèn)為設(shè)定的聚類初值。

相比較而言，傳統(tǒng)K-means算法有以下幾個(gè)主要的不足之處:① 在 K-means 算法中K是事先給定的，這個(gè)K值的選定是非常難以估計(jì)的，因而事先不知道該選取何值來(lái)進(jìn)行聚類；② 該算法在每一次迭代過(guò)程中都會(huì)產(chǎn)生新的聚類中心，因而數(shù)據(jù)量比較大，導(dǎo)致算法的時(shí)間開(kāi)銷(xiāo)加大；③ 該算法對(duì)數(shù)據(jù)集中的噪聲點(diǎn)和孤立點(diǎn)比較敏感，這將會(huì)導(dǎo)致均值偏離嚴(yán)重；④ 初始聚類中心對(duì)后期的實(shí)驗(yàn)影響比較大，一旦初始值選擇的不好，可能無(wú)法得到有效的聚類結(jié)果等等。

2 改進(jìn)算法的研究與實(shí)現(xiàn)

2.1 改進(jìn)算法的引入

在基礎(chǔ)階段本研究小組通過(guò)閱讀大量文獻(xiàn)資料，梳理了傳統(tǒng)K-means算法的核心思想以及實(shí)現(xiàn)步驟，通過(guò)實(shí)驗(yàn)可以獲得較好的聚類效果圖?；趧?chuàng)新的概念，思考了幾種可能的改進(jìn)措施：在圖像特征值聚類方面，思考能否通過(guò)一幅圖像的局部?jī)?nèi)在聯(lián)系進(jìn)行聚類[10]，以人臉為例，每個(gè)人都有一張互不相同的臉，但是人臉上的基本構(gòu)造卻是相同的，嘴巴都是位于鼻子下面，而鼻子位于眼睛下面等等，諸如此類圖像內(nèi)在聯(lián)系可以找出很多。在不存在內(nèi)在聯(lián)系的數(shù)據(jù)集中，又該怎樣改進(jìn)算法以獲得更好的效果呢？結(jié)合數(shù)學(xué)中的相關(guān)知識(shí)，提出基于二分法的K-means算法，類似求方程的解，在求解中通過(guò)對(duì)固定區(qū)間進(jìn)行二分法來(lái)逼近零點(diǎn)可以求得方程的解，運(yùn)用到聚類中，如何定義區(qū)間和零點(diǎn)顯得格外重要，通過(guò)分析發(fā)現(xiàn)，對(duì)于二分區(qū)間可以直接取自數(shù)據(jù)集，將整個(gè)數(shù)據(jù)集當(dāng)作區(qū)間來(lái)進(jìn)行劃分符合要求，其次將K值類比為零點(diǎn)，通過(guò)無(wú)限劃分將數(shù)據(jù)集的個(gè)數(shù)無(wú)限逼近K值即可完成聚集。

在對(duì)基于圖像局部聯(lián)系的聚類算法的實(shí)現(xiàn)過(guò)程中，發(fā)現(xiàn)其中困難多多，對(duì)于不同的圖像，必須首先定義不同的局部聯(lián)系關(guān)系，而自然界中的圖像無(wú)窮無(wú)盡，對(duì)每一類圖像都定義局部聯(lián)系會(huì)使工作量成倍增加，有時(shí)又因?yàn)閳D像保存時(shí)間、像素以及圖像內(nèi)容的復(fù)雜性等原因使得實(shí)驗(yàn)極其復(fù)雜，實(shí)驗(yàn)效果較差，甚至無(wú)法得出實(shí)驗(yàn)結(jié)果。為此，改用二分法對(duì)數(shù)據(jù)集進(jìn)行聚類研究，二分法實(shí)驗(yàn)原理簡(jiǎn)單易行，又涉及傳統(tǒng)K-means算法的使用，故比較容易實(shí)現(xiàn)，所以通過(guò)對(duì)實(shí)驗(yàn)的基本思想、實(shí)驗(yàn)內(nèi)容、實(shí)驗(yàn)步驟以及實(shí)驗(yàn)效果進(jìn)行的系統(tǒng)的設(shè)計(jì)與操作，提出基于二分法的K-means聚類算法。

2.2 改進(jìn)算法的基本思想與主要步驟

對(duì)于一個(gè)原始的數(shù)據(jù)集，把它看成一個(gè)整體，類比與二分法求解中的區(qū)間整體，這里將這個(gè)整體命名為簇(cluster)，然后將該簇利用K-means算法一分為二即得2個(gè)數(shù)據(jù)集(簇)，然后選擇其中一個(gè)簇進(jìn)行再次二分劃分，以此類推，從而形成迭代，直至數(shù)據(jù)集的數(shù)目等于用戶指定的數(shù)目K為止。

在實(shí)驗(yàn)思想的指導(dǎo)下，結(jié)合傳統(tǒng)K-means算法提出本次實(shí)驗(yàn)的基本步驟如下：① 把所有的數(shù)據(jù)集初始化為一個(gè)簇；② 對(duì)第1步中得到的簇執(zhí)行K-means算法劃分為2個(gè)簇(初始化時(shí)只有一個(gè)簇)，然后一直重復(fù)第2步的劃分(選某個(gè)簇進(jìn)劃分為2個(gè))，直到得到K個(gè)簇為止。

2.3 改進(jìn)算法的實(shí)現(xiàn)

這里觀察到選擇不同的數(shù)據(jù)集進(jìn)行下次聚類所得到的效果是不同的，那么如何進(jìn)行數(shù)據(jù)集的選擇呢？起初考慮總是向同一個(gè)方向進(jìn)行數(shù)據(jù)集的選擇，簡(jiǎn)單的說(shuō)就是總是選擇上半方的數(shù)據(jù)集或者下半方的數(shù)據(jù)集，通過(guò)對(duì)這個(gè)方案的實(shí)驗(yàn)，發(fā)現(xiàn)聚類效果不佳，無(wú)法考慮到至關(guān)重要的特征向量，聚類效果存在極端現(xiàn)象。緊接著轉(zhuǎn)換思想，跳躍選取下一次要聚類的數(shù)據(jù)集，也即每進(jìn)行一次聚類就轉(zhuǎn)換一次選取方向，這樣可以中和實(shí)驗(yàn)效果，此方法相對(duì)于前一種方法有了明顯的改進(jìn)，消除了部分的極端現(xiàn)象。

圖3 改進(jìn)算法的示意圖

由圖3所示，假設(shè)初始數(shù)據(jù)集含有10個(gè)特征向量，在第一次選擇之后得到2個(gè)分別為4和6個(gè)特征向量的聚類簇，這時(shí)執(zhí)行二分選擇算法，選擇具有6個(gè)特征向量的聚類簇行下次劃分，因?yàn)閿?shù)據(jù)集所含特征向量越多就表明該簇聚類越不好，這時(shí)就應(yīng)該選擇該聚類簇進(jìn)行下一次聚類，以此類推。改進(jìn)算法的流程圖如圖4所示。

由圖4可知，改進(jìn)算法在傳統(tǒng)K-means算法的基礎(chǔ)上添加了二分選擇這一實(shí)驗(yàn)步驟，其目的是為了選出適合后期進(jìn)行二次聚類的聚類簇。

圖4 改進(jìn)算法的流程圖

改進(jìn)算法的效果圖如圖5所示。

(a) K=4時(shí)聚類的特征值向量矩陣

(b) 特征值匹配效果圖 圖5 改進(jìn)算法的效果圖

2.4 改進(jìn)算法與原始算法的比較

在傳統(tǒng)K-means算法中，用戶需要自行選取聚類中心，這無(wú)疑給實(shí)驗(yàn)增加了不確定性，也使得實(shí)驗(yàn)結(jié)果無(wú)法快速達(dá)到最好的聚類效果，而改進(jìn)的基于二分法的K-means算法中，不存在隨機(jī)點(diǎn)的選取，不受初始化問(wèn)題的影響，故誤差較小，實(shí)驗(yàn)效果較好。其次，二分K-means算法的時(shí)間復(fù)雜度有所減小，因?yàn)樵撍惴ㄏ啾扔趥鹘y(tǒng)K均值算法而言，它減少了特征值的相似度計(jì)算等等。

3 結(jié)束語(yǔ)

傳統(tǒng)的K-means算法是一種在數(shù)據(jù)集聚類方面應(yīng)用比較廣泛的聚類算法，但它存在一定的局限性和不確定性。本文提出的基于二分法的K-means聚類算法是對(duì)傳統(tǒng)算法的改進(jìn)，有效性分析和實(shí)驗(yàn)表明，基于二分法的K-means聚類算法較大的提高聚類性能，但仍存在著局部聚類效果不佳的問(wèn)題，故仍需進(jìn)一步研究。

[1] Papadopoulos G T,Mezaris V,Kompatsiaris I,et al. Probabilistic Combination of Spatial Context with Visual and Co-occurrence Information for Semantic Image Analysis[C]∥ Proc.IEEE International Conference on Image Processing (ICIP 2010),Hong Kong,China,2010:3205-3208.

[2] Escalante H J,Montes-y-Gómez M，Sucar L E.An Energy-based Model for Region-labeling[J].Computer Vision and Image Understanding，2011，115(6)：787-803.

[3] Fergus R,Perona P,Zisserman A. Object Class Recognition by Unsupervised Scale-invariant Learning[J].Cvpr,2003,2(2):264.

[4] 張建民.一種改進(jìn)的K-means聚類算法[J].微計(jì)算機(jī)信息，2010(9):233-234.

[5] 朱玉金，孫蕾.數(shù)據(jù)挖掘技術(shù)[M].南京：東南大學(xué)出版社,2006.

[6] 張?jiān)茲?龔玲.數(shù)據(jù)挖掘原理與技術(shù)[M].北京:電子工業(yè)出版社,2004.

[7] 李芳.K-Means算法的k值自適應(yīng)優(yōu)化方法研究[D].合肥:安徽大學(xué),2015.

[8] 李薈嬈.K-means聚類方法的改進(jìn)及其應(yīng)用[D].哈爾濱：東北農(nóng)業(yè)大學(xué),2014.

[9] 崔衛(wèi)東.K-means算法研究[J].數(shù)字化用戶,2013,19(11):35-40.

[10] 李正兵,羅斌,翟素蘭,等.基于關(guān)聯(lián)圖劃分的K-means算法[J].計(jì)算機(jī)工程與應(yīng)用,2013,(21):141-144，151.

[11] Michael S,George K,Vipin K.A Comparison of Document Clustering Techniques[J].International Transactions in Operational Research,2017，24(3):537-558.

[12] 陳姍姍.基于Hadoop的用戶行為分析方法的應(yīng)用研究[D].南京：南京郵電大學(xué),2016.

ImplementationofK-meansAlgorithmBasedonDichotomy

CHEN Xian-yu,LI You-qiang,LU Miao-miao,LU Jian-cheng,CHEN Wen-qiang

(School of Computer Science and Technology,Anhui University,Hefei Anhui 230039,China)

The eigenvalue processing is very important in the field of image processing. The K-means algorithm is one of the most important methods used in eigenvalue clustering. This algorithm is simple and quick,and the clustering effect is better,so it is widely used by academic community. In view of the deficiencies of conventional K-means algorithms in data set partition,this paper puts forward a K-means clustering algorithm based on the dichotomy. By partitioning the data set,this algorithm selects the data set to be partitioned for iterations. The experimental results show that the proposed algorithm has significantly improved in terms of partitioning compared with conventional algorithms.

K-means; dichotomy; clustering center

TP391

A

1003-3114(2017)06-37-4

10. 3969/j.issn. 1003-3114. 2017.06.09

陳賢宇，李有強(qiáng)，呂苗苗，等. 基于二分法的K-means算法的實(shí)現(xiàn)[J].無(wú)線電通信技術(shù),2017,43(6): 37-40.

[CHEN Xianyu,LI Youqiang,LU Miaomiao,et al. Implementation of K-means Algorithm Based on Dichotomy [J]. Radio Communications Technology,2017,43(6): 37-40.]

2017-05-25

安徽大學(xué)創(chuàng)新創(chuàng)業(yè)項(xiàng)目(J10118515835)

陳賢宇(1996—),男,本科,主要研究方向：模式識(shí)別。李友強(qiáng)(1997—),男,本科，主要研究方向：圖像檢索。