曲福恒, 宋劍飛, 楊 勇,2, 胡雅婷, 潘曰濤

(1. 長春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院, 長春 130022;2. 長春師范大學(xué) 教育學(xué)院, 長春 130032; 3. 吉林農(nóng)業(yè)大學(xué) 信息技術(shù)學(xué)院, 長春 130118)

聚類分析是一種將數(shù)據(jù)集按相似性進(jìn)行分組的方法, 其目的是為使組內(nèi)的數(shù)據(jù)更相似, 同時(shí)使組間的數(shù)據(jù)差異更大[1]. 聚類常用于數(shù)據(jù)挖掘、 模式識別、 決策支持、 機(jī)器學(xué)習(xí)和圖像分割等領(lǐng)域[2].k-means是最流行的聚類算法之一, 具有實(shí)現(xiàn)簡單、 執(zhí)行效率高等優(yōu)點(diǎn), 但易陷入局部最優(yōu)解[3], 導(dǎo)致聚類性能不佳.

針對上述問題, 目前已提出了多種改進(jìn)方案. Likas等[4]提出了全局k-means算法, 首先使用數(shù)據(jù)集的質(zhì)心作為第一個(gè)簇中心, 然后逐個(gè)增加簇中心并使用k-means算法找到收斂位置, 以提高算法的聚類精度; Nayak等[5]提出了一種基于粒子群優(yōu)化的k-means聚類算法, 以獲得最優(yōu)的聚類中心; 為選取合適的聚類中心, Erisoglu等[6]提出了一種根據(jù)變異系數(shù)和相關(guān)系數(shù)計(jì)算k-means初始聚類中心的算法; Rahman等[7]提出了一種基于遺傳算法的聚類技術(shù), 通過改進(jìn)初始種群的選擇方法產(chǎn)生高質(zhì)量的聚類中心; 邢長征等[8]提出了一種基于平均密度優(yōu)化初始聚類中心的k-means算法, 有效提高了算法的聚類精度; Tzortzis等[9]提出了根據(jù)方差為簇分配權(quán)重的方法, 限制了大方差簇的出現(xiàn), 并且提高了求解精度; Malinen等[10]在k-means算法分配階段通過匈牙利算法解決各簇分配問題, 使簇之間達(dá)到平衡; Pham等[11]提出了一種增量式搜索策略減少算法對初始中心的依賴性; Bagirov[12]通過最小化提出的輔助聚類函數(shù)計(jì)算新增聚類中心的起點(diǎn), 有效提升了全局k-means算法的精度.

上述算法雖然精度提升明顯, 但與k-means算法相比時(shí)間復(fù)雜度較高. Ismkhan[13]以k-means為基礎(chǔ)提出了一種新的迭代聚類(I-k-means-+)算法. I-k-means-+算法時(shí)間復(fù)雜度較低, 與k-means算法基本相當(dāng), 且在一定程度上提高了k-means算法的聚類精度. I-k-means-+算法利用數(shù)據(jù)點(diǎn)到有用中心的距離選擇k個(gè)初始中心, 然后通過不斷地劃分、 刪除簇優(yōu)化k-means算法的目標(biāo)函數(shù)值. 但因隨機(jī)劃分方式導(dǎo)致聚類結(jié)果不穩(wěn)定, 聚類精度仍有較大提升空間. 針對I-k-means-+算法存在的問題, 本文提出一種基于min-max準(zhǔn)則與區(qū)域劃分的I-k-means-+聚類算法. 該算法在選擇初始中心時(shí), 計(jì)算數(shù)據(jù)到最近中心的距離, 優(yōu)先選擇距離較遠(yuǎn)的數(shù)據(jù)點(diǎn)作為新的聚類中心, 以避免初始中心過于密集的情況; 采用多區(qū)域劃分的策略增加候選中心的多樣性; 通過重新選擇分裂簇, 并與原刪除簇再次配對提高配對成功率.

1 I-k-means-+算法

假設(shè)給定一組具有N個(gè)樣本的數(shù)據(jù)集X={x1,x2,…,xN},xi∈D(i=1,2,…,N), 聚類的目的是將數(shù)據(jù)集劃分為k個(gè)互不相交的子集(簇){S1,S2,…,Sk}, 聚類中心集合為C={C1,C2,…,Ck}.

k-means算法使用誤差平方和(SSE)作為衡量聚類效果的指標(biāo). 對于給定的解S=(S1,S2,…,Sk), SSE的計(jì)算公式為

(1)

(2)

其中dis(p,Ci)為樣本點(diǎn)p到所屬聚類中心Ci的歐氏距離.I-k-means-+算法首先計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的有用中心.

定義1如果不存在中心Cy滿足如下條件:

(dis(p,Cy)

則稱中心Cx為數(shù)據(jù)點(diǎn)p的有用中心.

先通過

(3)

計(jì)算每個(gè)數(shù)據(jù)點(diǎn)p的權(quán)重, 即V1(p,C), 根據(jù)權(quán)重選擇k個(gè)初始聚類中心, 并使用k-means算法收斂為解S, 其中Hp是數(shù)據(jù)點(diǎn)p的有用中心集合; 然后選擇增益較大的簇Si與損失較小的簇Sj, 刪除簇Sj并劃分簇Si, 使用t-k-means[13]收斂為解S′; 最后保留S和S′中精度最高的解.增益(Gain)和損失(Cost)的計(jì)算公式分別為

(4)

(5)

其中Zp是數(shù)據(jù)點(diǎn)p的次近中心。在實(shí)際應(yīng)用中, 各中心之間的分布并非絕對均勻, 不同區(qū)域的聚類中心密集程度不同.由I-k-means-+算法過程可知, 該算法的初始中心選擇方法僅考慮有用中心對數(shù)據(jù)點(diǎn)權(quán)重的影響, 當(dāng)有用中心與所有中心的數(shù)量差距較大時(shí), 有用中心很難反應(yīng)出所有中心的分布情況.從而導(dǎo)致算法選擇的多個(gè)初始中心在同一個(gè)簇中, 而有的簇沒有聚類中心, 如圖1所示.I-k-means-+算法的聚類精度易受初始中心影響, 圖1的初始解較差更易使算法陷入局部最優(yōu)解, 降低算法的求解精度.

圖1 I-k-means-+算法在k=8時(shí)選擇的初始中心Fig.1 Initial center chosen by I-k-means-+ algorithm when k=8

此外, I-k-means-+算法中只有分裂簇與刪除簇配對成功時(shí), 才能提高聚類精度, 而I-k-means-+算法中每次迭代僅進(jìn)行一次分裂簇與刪除簇的配對, 且易出現(xiàn)配對失敗的情況, 影響算法收斂精度. I-k-means-+算法的劃分與刪除簇步驟中通過隨機(jī)選擇分裂簇中的一個(gè)數(shù)據(jù)點(diǎn)作為新中心, 該方法的隨機(jī)性較大且選擇不同的新中心其解的收斂結(jié)果不同, 從而導(dǎo)致聚類結(jié)果的穩(wěn)定性變差.

2 I-k-means-+算法的優(yōu)化改進(jìn)

針對I-k-means-+算法聚類精度有待優(yōu)化與聚類結(jié)果不穩(wěn)定的問題, 本文提出一種基于min-max準(zhǔn)則與區(qū)域劃分的I-k-means-+聚類算法, 即MR-k-means-+算法(I-k-means-+clustering algorithm based on min-max criterion and region division). 算法提出min-max準(zhǔn)則, 在式(3)中引入數(shù)據(jù)到最近中心的距離并計(jì)算數(shù)據(jù)點(diǎn)的權(quán)重, 選擇權(quán)重最大的作為新的聚類中心, 以此避免初始聚類中心密集的情況. 當(dāng)配對失敗時(shí)重新選擇分裂簇與原刪除簇再次配對, 以提高配對成功率, 進(jìn)一步提高聚類精度. 針對I-k-means-+聚類結(jié)果不穩(wěn)定的情況, 本文算法通過多區(qū)域劃分的策略選擇多個(gè)候選中心, 以增加解的多樣性, 從而提高聚類的精度與穩(wěn)定性.

2.1 基于min-max準(zhǔn)則的中心選擇策略

I-k-means-+聚類算法的中心選擇策略可能會(huì)導(dǎo)致初始聚類中心分布不均, 即存在多個(gè)中心聚集在同一簇中, 而有的簇沒有聚類中心的問題. 從而降低初始解的精度, 導(dǎo)致算法的聚類精度較差. 為避免初始聚類中心分布不均的問題, 本文算法在新中心的選擇中考慮了其他中心的分布情況. 若參與計(jì)算的中心數(shù)量過多, 雖能改善聚類中心的分布效果, 但極大降低了算法的效率. 本文提出min-max準(zhǔn)則, 該準(zhǔn)則選擇新的聚類中心時(shí), 會(huì)先計(jì)算每個(gè)數(shù)據(jù)點(diǎn)到最近中心的距離(minimum distance), 然后優(yōu)先選擇距離最大(maximum distance)的數(shù)據(jù)點(diǎn)作為新的聚類中心. 令Q(p,C)表示數(shù)據(jù)點(diǎn)p與中心集合C中各中心距離的最小值計(jì)算公式為

(6)

將Q(p,C)代入式(3)得到本文的中心評價(jià)公式為

V2(p,C)=V1(p,C)×α+Q(p,C)×β.

(7)

如圖2所示, 利用式(7)可較大程度地避免兩個(gè)中心在同一個(gè)簇中的情況, 保證中心分布更均勻.與I-k-means-+初始化方法相比, 本文初始化方法在圖1數(shù)據(jù)集上, 避免了多個(gè)中心聚集在同一個(gè)簇的情況, 選擇的中心分布更均勻, 且初始解的精度較前者有較大提升. 此外, I-k-means-+初始化方法提出有用中心的概念是為減少初始化部分的計(jì)算量, 本文利用I-k-means-+算法已有的距離信息, 在不增加初始化方法時(shí)間復(fù)雜度的前提下改進(jìn)其初始中心的選擇策略, 并提高聚類精度.

在式(7)中通過參數(shù)α和β分別調(diào)整有用中心和最近中心在最終結(jié)果中所占的比例,α和β都在[0,1]內(nèi).當(dāng)β=0時(shí), 式(7)等價(jià)于式(3); 當(dāng)α=0時(shí), 式(7)等價(jià)于式(6).

2.2 多區(qū)域劃分刪除策略

為避免只選擇一個(gè)隨機(jī)數(shù)據(jù)點(diǎn)作為候選中心導(dǎo)致的聚類結(jié)果不穩(wěn)定與精度較低的問題, 本文提出多區(qū)域劃分的策略獲取更多的候選中心, 通過增加解的多樣性提高聚類精度與穩(wěn)定性.

該策略將分裂簇Si中的數(shù)據(jù)點(diǎn)分割到不同的區(qū)域, 從每個(gè)區(qū)域挑選一個(gè)候選中心.分割區(qū)域的數(shù)量對本文算法的效率和精度有重要影響, 分割的區(qū)域過多, 會(huì)增加距離計(jì)算次數(shù), 導(dǎo)致算法的時(shí)間復(fù)雜度過高; 分割的區(qū)域過少, 會(huì)降低算法的精度.因此, 需要在精度與時(shí)間復(fù)雜度之間做一個(gè)平衡.本文將分裂簇Si的數(shù)據(jù)點(diǎn)分割到兩個(gè)不同的區(qū)域中, 第一個(gè)區(qū)域以中心Ci為圓心, 以Ci到簇內(nèi)最遠(yuǎn)點(diǎn)距離的1/2為半徑, 劃分成一個(gè)圓形區(qū)域.在簇Si中, 除第一區(qū)域外的其他數(shù)據(jù)點(diǎn)作為第二區(qū)域的數(shù)據(jù)點(diǎn), 然后分別在第一和第二區(qū)域中選擇距離Ci最遠(yuǎn)的點(diǎn)作為候選中心M1和M2, 如圖3所示.最后隨機(jī)從Si中選擇一個(gè)數(shù)據(jù)點(diǎn)作為第三個(gè)候選中心M3.與原算法只有一個(gè)候選中心相比, 該策略增加了解的多樣性.

本文將Ci作為第一個(gè)中心, 依次從候選中心集中選出一個(gè)候選中心作為第二個(gè)中心, 然后使用簇Si中包含的所有數(shù)據(jù)點(diǎn), 運(yùn)行2-k-means(k=2的k-means算法)迭代一次, 選擇分裂后SSE值最小的中心, 替換原來簇中心Ci和Cj.此時(shí), SSE的下降幅度和迭代次數(shù)呈衰減趨勢, 本文為節(jié)省迭代時(shí)間且能找到收斂效果較好的中心, 故2-k-means只迭代一次.

2.3 基于SSE的簇對再匹配方法

I-k-means-+算法中僅進(jìn)行一次分裂簇與刪除簇的配對, 而配對的成功率對聚類精度有較大影響. 本文提出基于SSE的簇對再匹配方法, 當(dāng)配對失敗時(shí)重新選擇分裂簇與原刪除簇再次配對, 以提高配對成功率, 進(jìn)而提高聚類精度.

本文在簇Si和Sj配對失敗后, 即SSE(X,S′)>SSE(X,S), 重新選擇增益最大的簇Sm(Sm≠Si), 再次執(zhí)行劃分Sm與刪除Sj的操作, 并使用Hamerly[14]的方法收斂為解S″.若SSE(X,S″)

2.4 算法流程

MR-k-means-+算法整體流程如下.

輸入: 數(shù)據(jù)集X, 聚類個(gè)數(shù)k;

輸出: 解S;

步驟1) 簇的初始狀態(tài)均設(shè)為允許劃分與刪除, 在數(shù)據(jù)集X中選擇第一維度最小的數(shù)據(jù)點(diǎn)作為中心C1;

步驟2) 用式(7)計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的權(quán)重V1(p,C), 選擇權(quán)重最大的數(shù)據(jù)點(diǎn)為中心Cm(m=2,3,…,k-1), 并使用Hamerly收斂為解S;

步驟3) 選擇增益最大的簇Si且該簇應(yīng)允許劃分, 若沒有該簇或有k/2個(gè)簇的增益大于Si, 則結(jié)束;

步驟4) 在滿足下列3個(gè)條件的簇中, 找到損失最小的簇Sj; 若沒有, 則結(jié)束:

①Si≠Sj且Cost(Sj)

②Si與Sj可以配對且Si與Sj互不為鄰簇[13];

③Sj應(yīng)允許刪除;

步驟5) 若有k/2個(gè)簇的損失小于Sj, 則Si設(shè)為不可劃分的簇, 并轉(zhuǎn)步驟3);

步驟6) 設(shè)置C′=C后, 按多區(qū)域劃分刪除策略劃分簇Si, 并選擇候選中心M1,M2,M3, 將簇中心Ci作為第一中心, 分別將候選中心作為第二中心, 使用2-k-means迭代一次, 保留精度最高的一組替換Ci和Cj;

步驟7) 根據(jù)步驟6)的中心集C, 使用Hamerly將數(shù)據(jù)集X收斂為解S′, 若SSE(X,S)>SSE(X,S′), 則執(zhí)行如下操作:

①Si和Sj標(biāo)記為不可刪除且設(shè)置Sj的強(qiáng)鄰簇[13]為不可刪除;

②S=S′且設(shè)置Si和Sj的強(qiáng)鄰簇為不可刪除;

步驟8) 若SSE(X,S)

① 找到增益最大簇Sz(Sz≠Si),C=C′并選擇簇Sz中一個(gè)隨機(jī)點(diǎn)替換Cj, 使用Hamerly收斂為解S″;

② 若SSE(X,S″)

步驟9) 若成功配對的數(shù)量大于k/2, 則算法結(jié)束; 否則, 重復(fù)執(zhí)行步驟3)～9).

2.5 計(jì)算復(fù)雜度分析

本文算法主要由三部分組成: 第一部分為基于min-max準(zhǔn)則的中心選擇策略, 該部分通過式(7)計(jì)算數(shù)據(jù)點(diǎn)的權(quán)重并選擇初始聚類中心, 其時(shí)間復(fù)雜度為O(nkd+k2d); 第二部分為多區(qū)域劃分刪除策略, 其中劃分階段時(shí)間復(fù)雜度為O(lnd), 刪除階段時(shí)間復(fù)雜度為O(ld), 該部分時(shí)間復(fù)雜度為O(lnd); 第三部分為基于SSE的簇對再匹配方法, 該部分的時(shí)間復(fù)雜度為O(lkdn+lk2d).所以本文算法的時(shí)間復(fù)雜度為O(lkdn+lk2d), 其中l(wèi)表示劃分刪除步驟的迭代次數(shù),n表示樣本數(shù),k表示聚類中心個(gè)數(shù),d表示樣本維度.

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

3.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)

實(shí)驗(yàn)環(huán)境配置為Intel(R) Core(TM) i5-6200U CPU @ 2.30 GHz 2.40 GHz, Windows10 64 位操作系統(tǒng), 內(nèi)存12 GB, VS 2013開發(fā)平臺, 所有算法均使用C++語言編程實(shí)現(xiàn).

為驗(yàn)證MR-k-means-+算法的有效性, 實(shí)驗(yàn)選用5個(gè)UCI數(shù)據(jù)集(https://archive.ics.uci.edu/ml/index.php), 將本文算法與其他3種算法進(jìn)行性能對比. 選取數(shù)據(jù)集的信息列于表1.

表1 5個(gè)UCI數(shù)據(jù)集信息Table 1 Information of five UCI datasets

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

實(shí)驗(yàn)中的對比算法為k-means算法、 聚類中心初始化算法k-means++[15]、 I-k-means-+(IK-+)算法及本文的MR-k-means-+(MRK-+)算法. 為避免聚類中心數(shù)量過大導(dǎo)致的無意義聚類, 本文對數(shù)據(jù)個(gè)數(shù)小于1 000的k值設(shè)置為5,10,15,20, 數(shù)據(jù)個(gè)數(shù)大于1 000的k值設(shè)置為5,10,20,50. 本文算法參數(shù)設(shè)置:α=0.5,β=0.5. 為避免算法中聚類精度與運(yùn)行時(shí)間的隨機(jī)性, 所有算法均運(yùn)行50次取平均值.

3.2.1 求解精度測試

算法的求解精度以收斂后的SSE衡量. 對于一個(gè)給定的算法, 為量化其相對于IK-+算法的精度提升效果, 其精度提升百分?jǐn)?shù)U的計(jì)算公式可表示為

U=(E1-E2)/E1×100%,

(8)

其中E1表示IK-+算法的目標(biāo)函數(shù)值,E2表示對比算法的目標(biāo)函數(shù)值.

不同算法在測試數(shù)據(jù)集上的運(yùn)行結(jié)果列于表2. 由表2可見, 在20次對比實(shí)驗(yàn)中, 有16次本文算法是所有算法中精度最高的. 各優(yōu)化算法精度提升百分?jǐn)?shù)列于表3. 由表3可見, 與IK-+算法相比,k-means算法的精度平均下降了149.64%,k-means++算法下降了5.69%, 而本文算法的聚類精度與IK-+算法相比平均提升了6.47%, 當(dāng)k=50時(shí)提升了18.6%, 本文算法有效提升了IK-+算法的聚類精度.

表2 不同算法在測試數(shù)據(jù)集上的運(yùn)行結(jié)果Table 2 Running results of different algorithms on test datasets

表3 各優(yōu)化算法精度提升百分?jǐn)?shù)Table 3 Accuracy improvement percentage of each optimization algorithm %

3.2.2 穩(wěn)定性測試

為測試聚類結(jié)果的穩(wěn)定性, 本文采用方差進(jìn)行衡量. 在不同數(shù)據(jù)集下, 將本文提出的MRK-+算法與IK-+算法使用不同k值分別運(yùn)行50次, 并根據(jù)SSE計(jì)算不同k值下運(yùn)行結(jié)果的方差, 其方差對比結(jié)果如圖4所示. 由圖4可見, 與IK-+算法相比, 除數(shù)據(jù)集Iris中k=10和k=20外, 本文算法的方差均可忽略不計(jì). 在20次方差對比中, 其中有17次本文算法的方差優(yōu)于IK-+算法, 并有2次方差相等, 表明本文算法與IK-+算法相比聚類結(jié)果更穩(wěn)定.

圖4 本文算法與IK-+算法的方差對比結(jié)果Fig.4 Variance comparison results between proposed algorithm and IK-+ algorithm

3.2.3 運(yùn)行效率對比

令T1表示IK-+算法的運(yùn)行時(shí)間,T2表示某個(gè)給定算法的運(yùn)行時(shí)間, 則該算法相對于IK-+算法的時(shí)間加速百分?jǐn)?shù)L計(jì)算公式為

(9)

圖5為本文算法相對于IK-+算法的時(shí)間加速比結(jié)果. 由圖5可見, 本文算法在k較小時(shí)速度提升明顯,k較大時(shí)速度略有下降, 平均速度與I-k-means-+算法基本相當(dāng).

圖5 本文算法相對于IK-+算法的時(shí)間加速比Fig.5 Time speedup ratio of proposed algorithm compared to IK-+ algorithm

綜上所述, 針對I-k-means-+算法聚類結(jié)果不穩(wěn)定, 并且求解精度有待提高的問題, 本文提出了一種基于min-max準(zhǔn)則與區(qū)域劃分的I-k-means-+聚類算法. 提出min-max準(zhǔn)則, 以避免初始化中心過度密集的情況, 提高初始解的精度; 將分裂簇分割為不同區(qū)域, 從中選擇多個(gè)候選中心, 增加解的多樣性, 提高聚類結(jié)果的穩(wěn)定性; 當(dāng)配對失敗后, 重新選擇分裂簇與原刪除簇再次配對, 以提高配對成功率, 進(jìn)一步提高算法的求解精度. 實(shí)驗(yàn)結(jié)果表明, 與I-k-means-+算法相比, 本文算法與前者的運(yùn)行效率基本相當(dāng), 聚類精度平均提升6.47%, 多次運(yùn)行結(jié)果的目標(biāo)函數(shù)值波動(dòng)更小、 聚類結(jié)果更穩(wěn)定.