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

陳賢宇，李有強，呂苗苗，盧建成，陳文強

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

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

陳賢宇，李有強，呂苗苗，盧建成，陳文強

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

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

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

0 引言

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

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

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

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

1.1 具體步驟

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

①從 數(shù)據(jù)集X中隨機選擇K個對象作為初始聚類中心c1,c2,c3,...ck；

② 重復(fù)；

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

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

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

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

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

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

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

圖2 K-means算法圖示

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語

傳統(tǒng)的K-means算法是一種在數(shù)據(jù)集聚類方面應(yīng)用比較廣泛的聚類算法，但它存在一定的局限性和不確定性。本文提出的基于二分法的K-means聚類算法是對傳統(tǒng)算法的改進(jìn)，有效性分析和實驗表明，基于二分法的K-means聚類算法較大的提高聚類性能，但仍存在著局部聚類效果不佳的問題，故仍需進(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].微計算機信息，2010(9):233-234.

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

[6] 張云濤,龔玲.數(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].計算機工程與應(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

陳賢宇，李有強，呂苗苗，等. 基于二分法的K-means算法的實現(xiàn)[J].無線電通信技術(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è)項目(J10118515835)

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