梁鮮，曲福恒，楊勇，才華

（1.長春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長春 130022；2.長春理工大學(xué) 電子信息工程學(xué)院，長春 130022）

聚類［1］分析是一種無先驗(yàn)知識(shí)的機(jī)器學(xué)習(xí)過程，是數(shù)據(jù)挖掘一個(gè)重要的分支，遵循同一個(gè)集合中的樣本相似性最大，不同集合中的樣本相異性最大的理念［2］，把樣本集分為若干個(gè)集合，每個(gè)集合稱為一個(gè)聚簇。已有的經(jīng)典聚類算法大致可分為五種：基于層次的、基于劃分的、基于密度的、基于網(wǎng)格的和基于模型的。K-均值是一種基于劃分的聚類算法，因效率高，處理速度快等特點(diǎn)，適合對(duì)大數(shù)據(jù)集聚類。K-均值算法選擇初始聚類中心的隨機(jī)性，使聚類結(jié)果因不同初始聚類中心和不同初始數(shù)據(jù)輸入順序的影響而波動(dòng)，聚類結(jié)果僅能收斂到局部最優(yōu)。

針對(duì)K-均值算法的不足，很多學(xué)者提出一系列改進(jìn)算法。Grigorios Tzortzis選取相距最遠(yuǎn)的樣本作為前兩個(gè)初始聚類中心，按照最小最大原則選取下一個(gè)聚類中心，保證每次選擇的聚類中心距已有聚類中心較遠(yuǎn)，得到正確的初始聚類中心；Kong Dexi把核函數(shù)引入到K-均值算法中，把數(shù)據(jù)映射到高維空間（或核空間），在高維空間中使用K-均值對(duì)數(shù)據(jù)聚類，使用正定核（CPD）提高算法效率；Hassanzadeh提出螢火蟲算法和K-均值結(jié)合的算法，對(duì)數(shù)據(jù)集細(xì)化，找到子數(shù)據(jù)集的質(zhì)心，提高算法的精度和性能；但是這些算法沒有得到廣泛的認(rèn)可，Likas A等人在2003年提出全局K-均值算法［6］增量選擇初始聚類中心，得到全局最優(yōu)的聚類結(jié)果，但算法時(shí)間復(fù)雜度大，不適合對(duì)大數(shù)據(jù)集聚類。本文提出全局K-均值的改進(jìn)算法，在不影響聚類效果的基礎(chǔ)上，減少聚類時(shí)間。

1 K-均值

K-均值算法相關(guān)描述［7］：設(shè)樣本集X={xi|i=1,2,...,N}，K個(gè)類別為Cj（j=1,2,...,K），K個(gè)聚類中心為Aj（j=1,2,...,K）。

樣本間的歐式距離公式：

聚簇中心：

誤差平方準(zhǔn)則函數(shù)：

K-均值算法流程圖如圖1所示。

圖1 K-均值算法流程圖

2 全局K-均值

全局K-均值算法通過求解一系列子聚類問題來解決K個(gè)聚簇的問題。該算法使用K-均值算法局域搜索的能力得到全局優(yōu)化的聚類結(jié)果。為了克服初始值敏感的問題，該算法通過每一次傳統(tǒng)K-均值算法找出一個(gè)最佳聚簇中心，直到找出K個(gè)聚簇中心。該算法具體步驟是：首先從實(shí)現(xiàn)一個(gè)聚簇的聚類問題開始，設(shè)置K=1，即先找到第一個(gè)聚簇的最佳質(zhì)心。在這個(gè)基礎(chǔ)上，實(shí)現(xiàn)兩個(gè)聚簇的聚類問題，設(shè)置K=2，找到的K=1的聚簇質(zhì)心默認(rèn)為K=2時(shí)的一個(gè)最佳聚簇中心，迭代地讓剩余樣本假設(shè)為第二個(gè)聚簇中心，然后運(yùn)行K-均值算法，找到誤差平方準(zhǔn)則函數(shù)最小時(shí)對(duì)應(yīng)的樣本作為另一個(gè)最佳聚簇中心，重復(fù)該過程，直到找到K個(gè)最佳聚簇中心。算法描述如下：

（1）初始化：計(jì)算所有樣本的均值當(dāng)做第一個(gè)最佳聚簇中心，設(shè)置 t=1；

（2）結(jié)束條件：t=t+1，當(dāng)t＞K時(shí)，算法終止；

（3）查找下一個(gè)最佳聚簇中心：前t-1個(gè)最佳聚簇中心為m1，m2，...，mt-1迭代地讓剩余樣本作為最佳聚簇中心，運(yùn)行K-均值算法，找到誤差平方準(zhǔn)則函數(shù)最小時(shí)對(duì)應(yīng)的樣本作為第t個(gè)最佳聚簇中心，即K=t的最佳聚簇中心為b1,b2,...,bt；

（4）讓 mj=bj,j=1,2,...,t，轉(zhuǎn)到（2）。

3 快速全局K-均值

全局K-均值算法可以得到較好的聚類結(jié)果，但是計(jì)算量太大。Likas等人對(duì)全局K-均值算法進(jìn)行改進(jìn)，得到快速全局K-均值算法，該算法通過計(jì)算bn，選擇bn最大時(shí)對(duì)應(yīng)的樣本作為最佳聚簇中心，進(jìn)而減少計(jì)算量。

bn的定義如：

4 一種高效的全局K-均值算法

針對(duì)全局K-均值算法時(shí)間復(fù)雜度大的問題，提出改進(jìn)算法，繼承全局K-均值算法增量選擇初始聚簇中心的思想，定義目標(biāo)函數(shù)：

選擇正確的初始聚類中心，減少迭代次數(shù)，降低時(shí)間復(fù)雜度。定義目標(biāo)函數(shù)：

選擇數(shù)據(jù)集中周圍分布最密集的樣本作為第一個(gè)初始聚類中心，選擇使目標(biāo)函數(shù)：

取最小值的樣本（距離已有聚類中心遠(yuǎn)，形成的子簇包含樣本個(gè)數(shù)多并且凝聚度?。鳛橄乱粋€(gè)聚類中心，直到選出K個(gè)最佳聚類中心。實(shí)驗(yàn)證明算法在不影響聚類性能的基礎(chǔ)上減小聚類時(shí)間。

問題描述：把樣本集合A=（a1,a2,...,an）劃分K個(gè)聚簇，使誤差平方準(zhǔn)則函數(shù)E最小，該算法使用歐式距離度量兩個(gè)樣本的相似度。

算法描述：

（1）計(jì)算

其中，i=1，2，...，n。

最終M的取值對(duì)應(yīng)的樣本作為第一個(gè)最佳聚簇中心，設(shè)置w=1；

（2）另w=w+1，如果簇的個(gè)數(shù)w＞K，該算法結(jié)束，轉(zhuǎn)到Step4；

（3）選取下一個(gè)聚簇中心，對(duì)剩余樣本，計(jì)算

其中，Di是樣本ai為聚簇中心形成的子簇中樣本到簇心的距離之和，Ni是子簇中樣本個(gè)數(shù)，di是ai到已有最佳聚簇中心的距離和，F(xiàn)i最小時(shí)對(duì)應(yīng)的樣本ai作為下一個(gè)最佳聚簇中心，轉(zhuǎn)到Step2；

（4）用得到的K個(gè)聚簇中心作為K-均值算法的初始聚簇中心，按照就近原則分配樣本到距離最近的簇中，分配完畢，更新聚簇中心，直到目標(biāo)函數(shù)收斂。

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

實(shí)驗(yàn)?zāi)康氖亲C明改進(jìn)算法的性能。硬件運(yùn)行環(huán)境是Intel CPU，2.99G內(nèi)存，931G硬盤；軟件運(yùn)行環(huán)境是WindowsXP操作統(tǒng)，Visual Studio 2013開發(fā)平臺(tái)，算法使用C++作為編程語言。

選用Segmentation數(shù)據(jù)集、pixel averages數(shù)據(jù)集和Pendigits數(shù)據(jù)集作為測試數(shù)據(jù)集，在測試數(shù)據(jù)集上分別運(yùn)行10次改進(jìn)算法、全局K-均值算法、快速全局K-均值算法、K-Means++和Pifs K-均值算法，對(duì)測試數(shù)據(jù)集聚類個(gè)數(shù)分別為3、4、5、6、7、8、9、10比較平均聚類結(jié)果。測試數(shù)據(jù)集描述如表1所示，算法在Segmentation數(shù)據(jù)集上平均聚類誤差比較如圖2所示，平均聚類時(shí)間比較如圖3所示，算法在pixel averages數(shù)據(jù)集上平均聚類誤差比較如圖4所示，平均聚類時(shí)間比較如圖5所示，算法在Pendigits數(shù)據(jù)集上平均聚類誤差比較如圖6所示，平均聚類時(shí)間比較如圖7所示。

表1 測試數(shù)據(jù)集的描述

圖2 Segmentation測試數(shù)據(jù)集上聚類誤差比較

圖3 Segmentation測試數(shù)據(jù)集上聚類時(shí)間比較

圖4 pixel averages測試數(shù)據(jù)集上聚類誤差比較

圖5 在pixel averages測試數(shù)據(jù)集上聚類時(shí)間比較

圖6 Pendigits測試數(shù)據(jù)集上聚類誤差比較

圖7 在Pendigits測試數(shù)據(jù)集上聚類時(shí)間比較

由圖2、圖4和圖6可知，改進(jìn)算法與全局K-均值算法、快速全局K-均值算法相比，不影響聚類誤差，與K-Means++和Pifs K-均值相比，聚類誤差小，聚類效果更好。由圖3、5和7可知，改進(jìn)算法相比全局K-均值算法、快速全局K-均值算法減小了聚類時(shí)間，聚類個(gè)數(shù)為正確值時(shí)，聚類時(shí)間減小量最大，在Segmentation和Pendigits數(shù)據(jù)集上，改進(jìn)算法的聚類時(shí)間大于K-Means++算法，相比Pifs K-均值算法時(shí)間復(fù)雜度小。實(shí)驗(yàn)證明，改進(jìn)算法可以得到更好的聚類結(jié)果，與全局K-均值算法、快速全局K-均值算法相比，降低了時(shí)間復(fù)雜度，與優(yōu)化初始聚類中心的其它K-均值算法相比，得到更好的聚類效果，聚類時(shí)間上也有一定的優(yōu)勢，證明改進(jìn)算法是可行的。

6 結(jié)束語

為了解決全局K-均值算法時(shí)間復(fù)雜度大的問題，定義新的目標(biāo)函數(shù)，選擇最小化目標(biāo)函數(shù)貢獻(xiàn)大，并且和已有聚類中心距離遠(yuǎn)的樣本作為下一個(gè)聚類中心，選擇周圍分布較密集的樣本作為第一個(gè)初始聚類中心，得到一種高效的全局K-均值算法。實(shí)驗(yàn)證明，改進(jìn)算法相比全局K-均值算法、快速全局K-均值算法，在不影響聚類效果的基礎(chǔ)上，降低了時(shí)間復(fù)雜度，與優(yōu)化初始聚類中心的其它K-均值算法的比較結(jié)果表明，改進(jìn)算法選取正確的初始聚類中心，得到更好的聚類效果，聚類時(shí)間上也有一定的優(yōu)勢。

［1］Yukio Ohsawa，Katsutoshi Yada.Data mining for design and marketing［M］.CRC Rress，2009.

［2］Aswani K C，Srinivas S.Concept lattice reduction using fuzzy K-means clustering［J］.Expert System with Application，2010，37（3）：2696-2704.

［3］Grigorios Tzortzis，Aristidis Likas.The min max K-means clustering algorithm［J］.Pattern Recognition，2014：47（2）：2505-2516.

［4］Kong Dexi，Kong Rui.A fast and effective kernel based K-Means clustering Algorithm［C］.IEEE Intelligent Systems，2013：58-61.

［5］Hassanzadeh T，Meybodi，M R.A new hybrid approach fordata clustering using firefly algorithm and K-means［C］.IEEE Intelligent Systems，2012：7-11.

［6］Likas A，Vlassis M，Verbeek J.The global K-means clustering algorothm［J］.Pattern Recognition，2003，36（2）：451-461.

［7］Erisoglu M，Calis N，Sakallioglu S.A new algorithm for initial cluster centers in K-means algorithm.Pattern Recognition Letters，2011（32）：1701-1705.