郭 婧,耿海軍,吳 勇

(1.晉中職業(yè)技術(shù)學(xué)院 電子信息系,山西 晉中 030600;2.山西大學(xué) 自動化與軟件學(xué)院,山西 太原 030013)

伴隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展,互聯(lián)網(wǎng)應(yīng)用正朝著精細(xì)化的方向發(fā)展。通過對連入網(wǎng)絡(luò)的數(shù)據(jù)進行深入挖掘分析,可以獲得潛在價值數(shù)據(jù),為互聯(lián)網(wǎng)創(chuàng)新應(yīng)用提供技術(shù)支持。但是萬物互聯(lián)的發(fā)展必然引起互聯(lián)網(wǎng)數(shù)據(jù)的規(guī)?；鲩L,從海量數(shù)據(jù)中獲取價值數(shù)據(jù)的難度提升,數(shù)據(jù)挖掘的方法顯得尤為重要[1]。聚類作為數(shù)據(jù)挖掘算法的一種,能夠通過抽象方法將多維數(shù)據(jù)特征進行有效計算,分析數(shù)據(jù)之間的相似屬性和差異特性[2],從而將海量的看似無關(guān)無序的數(shù)據(jù)進行有效歸類,為數(shù)據(jù)的多樣化應(yīng)用提供了有效保證。

數(shù)據(jù)聚類挖掘有2個方面的特點:一方面是待聚類的數(shù)據(jù)量大,對聚類算法的效率有一定要求;另一方面是待聚類的數(shù)據(jù)維度高,聚類運算復(fù)雜度高。因此數(shù)據(jù)聚類挖掘算法應(yīng)著重解決這2個方面的問題?；贙均值(K-means)聚類的數(shù)據(jù)挖掘在處理多維數(shù)據(jù)樣本時存在聚類精度低的缺點,這是因為傳統(tǒng)K均值聚類存在局部尋優(yōu)陷阱和全局尋優(yōu)不理想的問題。當(dāng)前,研究人員嘗試使用群體智能算法來解決上述問題。劉云恒[3]對云計算環(huán)境的數(shù)據(jù)挖掘算法展開了研究,主要研究了多種群體智能算法在數(shù)據(jù)挖掘中的適用性,分析了不同智能算法在數(shù)據(jù)挖掘中的優(yōu)劣,并闡述了群體智能算法在數(shù)據(jù)挖掘中的應(yīng)用價值。Karimi等人[4]分析了遺傳算法在數(shù)據(jù)挖掘中的應(yīng)用情況,通過聚類分析有效解決了云計算環(huán)境的服務(wù)質(zhì)量(Quality of services,QoS)問題。尹芳等人[5]針對K均值聚類在數(shù)據(jù)聚類中的不足進行了有效改進,采用動態(tài)分配聚類中心點的方法解決了K均值聚類效率對初始中心點依賴程度高的問題。但是,基于群體智能算法的數(shù)據(jù)挖掘大多存在局部過擬合和全局尋優(yōu)的能力不夠理想的問題,準(zhǔn)確度和穩(wěn)定性有待進一步提高。

菌群優(yōu)化算法作為一種新型仿生智能優(yōu)化算法,具有比傳統(tǒng)優(yōu)化算法更快的收斂速度和更強的魯棒性。因此,本文采用K均值聚類來完成數(shù)據(jù)挖掘,建模簡單,復(fù)雜度低,并且引入菌群算法對其進行優(yōu)化,以便進一步提高其聚類性能。通過將菌群算法和K均值聚類相結(jié)合的方法,來解決傳統(tǒng)數(shù)據(jù)聚類挖掘不穩(wěn)定的問題,從而最終獲得較高的聚類準(zhǔn)確率。

1 基于K均值聚類的數(shù)據(jù)挖掘原理

K均值聚類的核心思想是根據(jù)待聚類點至中心點的距離來判斷待聚類點的類別[6]。K均值聚類的復(fù)雜度和效率取決于待聚類點的維度。一般而言,聚類的準(zhǔn)確率和效率隨著待聚類樣本的維度增加而降低。因此,聚類在數(shù)據(jù)挖掘中的應(yīng)用遇到了困難。在數(shù)據(jù)挖掘中,待挖掘的數(shù)據(jù)一般都是高維數(shù)據(jù),而且樣本容量大,因此多維數(shù)據(jù)的聚類精度問題和聚類時間問題都是數(shù)據(jù)挖掘急需解決的關(guān)鍵問題。

除了待聚類的維度外,K均值聚類算法初始中心點的選擇也很重要,它影響著聚類的效率。在樣本類別相似判別時,設(shè)定所屬類別距離閾值,然后計算待聚類點和所有中心點距離來劃分該聚類點的類別。具體數(shù)學(xué)描述為:設(shè)第i個中心點xi,待聚類的點與xi的距離為[7]

(1)

設(shè)中心點xi包含n個屬性,表示方法為[xi1xi2xi3…xin],和待聚類點xj[xj1xj2xj3…xjn]的距離為

(2)

根據(jù)式(2)可以計算所有待聚類的樣本點至中心點的距離集,根據(jù)距離dij來判定xi與xj是否同類。然后根據(jù)距離集建立聚類目標(biāo)函數(shù),求解式(3)的最小值[8]

(3)

將式(3)進一步展開得[9]

(4)

最后得到目標(biāo)函數(shù)為

(5)

2 菌群優(yōu)化算法分析

(6)

式中:Pmax和Pmin分別表示菌群邊界上下限。

第i個細(xì)菌的第j次趨化、k次復(fù)制、l次驅(qū)散的行為之后,其位置Pi(j,k,l)變化為Pi(j+1,k,l),方法為[10]

(7)

式中:C(i)為步長,Δ(i)表示細(xì)菌運動的方向向量。

在趨化運動過程中,其適應(yīng)度函數(shù)J(Pi)為[11]

(8)

式中:dattract和wattract為引力深度和寬度,hrepellant和wrepellant為斥力深度和寬度。

從第j至(j+1)次趨化后的適應(yīng)度更新方法為[12]

Ji(j+1,k,l)=Ji(j,k,l)+J(Pi)

(9)

經(jīng)過復(fù)制后

(10)

式中:Nc表示趨化總次數(shù)。對適應(yīng)度值較低的個體按一定概率驅(qū)散,重新求解所有個體適應(yīng)度,繼續(xù)重復(fù)復(fù)制和趨化操作。

3 基于菌群優(yōu)化的K均值聚類算法

根據(jù)數(shù)據(jù)樣本建立K均值聚類模型。根據(jù)參與聚類各節(jié)點和各自中心點的距離值建立適應(yīng)度函數(shù)。初始化菌群算法,通過菌群算法優(yōu)化各節(jié)點至中心點距離,獲得穩(wěn)定的樣本所屬類別,其具體流程如圖1所示。

圖1 基于菌群優(yōu)化的K均值聚類的數(shù)據(jù)挖掘流程圖

在實際操作時,可以根據(jù)需要調(diào)節(jié)驅(qū)散和趨化的次數(shù)。驅(qū)散次數(shù)過少,可能獲得局部最優(yōu)解;而趨化次數(shù)過少,不利于快速搜索到聚類適應(yīng)度最優(yōu)值;但是兩者次數(shù)過大,會導(dǎo)致聚類效率過低。因此,在實際操作中,應(yīng)當(dāng)合理設(shè)置驅(qū)散和趨化次數(shù)。

4 實例仿真

為了驗證基于菌群優(yōu)化的K均值聚類在數(shù)據(jù)挖掘中的性能,分別對實驗數(shù)據(jù)集和UCI(University of California,Irvine)數(shù)據(jù)集進行實例仿真。選擇的實驗數(shù)據(jù)集為某在線學(xué)習(xí)平臺,該平臺主要面向初、高中階段的英語教學(xué)領(lǐng)域,其運行時間已經(jīng)長達6 a,共積累了12萬注冊用戶的各種數(shù)據(jù)信息,日平均活躍用戶數(shù)達到4 000人,課程種類十分豐富。

根據(jù)學(xué)習(xí)者的學(xué)習(xí)習(xí)慣進行聚類并推薦關(guān)聯(lián)類別的學(xué)習(xí)資源,根據(jù)學(xué)習(xí)者反饋驗證聚類準(zhǔn)確率。選擇常用UCI 5種數(shù)據(jù)集進行聚類準(zhǔn)確率仿真,并驗證菌群優(yōu)化對K均值聚類的性能提升程度。最后采用常用聚類算法和本文算法對UCI 5種數(shù)據(jù)集分別進行實例仿真,驗證不同聚類算法的聚類性能。

菌群算法主要參數(shù)dattract=0.1,wattract=0.2,hrepellant=0.1,wrepellant=10,驅(qū)散次數(shù)l=20,趨化總次數(shù)Nc=200。菌群算法主要參數(shù)是參照菌群算法的相關(guān)文獻,多次實驗的經(jīng)驗結(jié)果。

4.1 基于實驗數(shù)據(jù)集的聚類性能

半年時間內(nèi)每個月從在線學(xué)習(xí)平臺抽取3 000個數(shù)據(jù)樣本,構(gòu)建6個數(shù)據(jù)集,其樣本量共計18 000個,訓(xùn)練和測試比例為3∶1。根據(jù)用戶在平臺上的學(xué)習(xí)習(xí)慣,選擇屬性重要度排名前6名的屬性進行聚類。4 500個測試樣本的聚類結(jié)果如表1所示。

表1 測試樣本的用戶聚類準(zhǔn)確率表

從表1可得,4 500個測試樣本被劃分成6個類別,其聚類準(zhǔn)確率最低值為92.518%,最高值為95.613%,標(biāo)準(zhǔn)差性能差距不大。對比發(fā)現(xiàn),A和F類的聚類準(zhǔn)確率高于B、C、D和E類,這與屬性值差異有較大關(guān)系。當(dāng)屬性差異較小時,容易出現(xiàn)聚類誤差,造成聚類準(zhǔn)確率降低的情況。

為了驗證菌群優(yōu)化對聚類準(zhǔn)確率的影響,分別采用K均值和基于菌群優(yōu)化的K均值聚類算法對6個不同數(shù)據(jù)集進行聚類仿真。表2為2種算法的聚類準(zhǔn)確率性能表。

表2 2種算法的聚類準(zhǔn)確率性能表 %

從表2得,對于6種不同數(shù)據(jù)集,引入菌群算法對K均值聚類進行優(yōu)化后,聚類準(zhǔn)確率得到明顯提升,所有數(shù)據(jù)集的平均聚類準(zhǔn)確率都高于92%,數(shù)據(jù)集6獲得了最高的平均聚類準(zhǔn)確率95.538%。

4.2 基于菌群優(yōu)化的K均值聚類算法處理UCI數(shù)據(jù)集

為了進一步驗證基于菌群優(yōu)化的K均值聚類算法在UCI數(shù)據(jù)集挖掘中的性能,對常用UCI數(shù)據(jù)集進行聚類仿真,UCI數(shù)據(jù)集結(jié)構(gòu)如表3所示。

表3 UCI仿真數(shù)據(jù)集結(jié)構(gòu)表

4.2.1 聚類準(zhǔn)確率

對表3的數(shù)據(jù)集按照3∶1進行訓(xùn)練和測試樣本數(shù)分配,分別采用K均值和基于菌群優(yōu)化的K均值算法進行聚類準(zhǔn)確率仿真。表4為菌群算法的聚類優(yōu)化性能對比表。

表4 2種算法的聚類優(yōu)化性能對比表

由表4對比得到,經(jīng)過了菌群算法優(yōu)化后,K均值聚類的性能得到了較大改善。K均值的聚類準(zhǔn)確率最高為82.301%,標(biāo)準(zhǔn)差最優(yōu)值為1.927×10-6;經(jīng)過了菌群算法優(yōu)化后,聚類準(zhǔn)確率最高為85.465%,標(biāo)準(zhǔn)差最優(yōu)值為1.252×10-6。其中Iris數(shù)據(jù)集的聚類準(zhǔn)確率提升了7.043%,提升幅度最大,提升幅度最小的Seeds數(shù)據(jù)集為3.844%,其他3類數(shù)據(jù)集的準(zhǔn)確率提升均保持在6%以上。相比于準(zhǔn)確率,標(biāo)準(zhǔn)差的提升幅度更加明顯,這表明經(jīng)過菌群優(yōu)化后,對UCI 5種數(shù)據(jù)集的聚類穩(wěn)定性提升效果大幅改善。

4.2.2 聚類時間

分別從表3的5種數(shù)據(jù)集中各選取1 000個數(shù)據(jù)樣本,構(gòu)成UCI混合數(shù)據(jù)集。對混合數(shù)據(jù)集分別進行K均值和基于菌群優(yōu)化的K均值聚類仿真,聚類準(zhǔn)確率設(shè)定閾值為70%,聚類時間仿真結(jié)果如圖2所示。

圖2 2種算法的優(yōu)化時間圖

從圖2得,當(dāng)聚類達到穩(wěn)定時,本文算法的聚類標(biāo)準(zhǔn)差性能明顯優(yōu)于K均值聚類算法。而且本文算法對5 000個混合樣本完成聚類消耗的時間更短,大約需要70 s,而K均值聚類算法大約需要93 s。而且在運行時間為[20,25]的時間段內(nèi),K均值聚類算法有一段時間的標(biāo)準(zhǔn)差未發(fā)生變化,收斂性能較差。

4.3 不同聚類算法的聚類性能

下文對常用聚類算法進行聚類性能比較,分別采用層次聚類[13]、DBSCAN(Density based spatial clustering of applications with noise)[14]、粒子群優(yōu)化(Particle swarm optimization,PSO)K均值聚類算法[15]和基于菌群優(yōu)化的K均值聚類算法對表3中的Iris和Seeds樣本進行仿真,結(jié)果如圖3所示。

圖3 聚類準(zhǔn)確率圖

從圖3可以看出,對于Iris和Seeds數(shù)據(jù)集,基于菌群優(yōu)化的K均值聚類準(zhǔn)確率最高,層次聚類次之。從聚類效率方面來看,本文算法低于層次聚類排在第2位。對比圖3(a)、(b)發(fā)現(xiàn),4種算法在Seeds數(shù)據(jù)集上的聚類性能明顯優(yōu)于Iris數(shù)據(jù)集,這可能是因為Iris樣本包含22個屬性,遠(yuǎn)大于Seeds數(shù)據(jù)集的13個屬性,屬性過多導(dǎo)致聚類運算復(fù)雜度提升而造成了聚類精度不高。而對比聚類效率,Seeds數(shù)據(jù)集優(yōu)于Iris數(shù)據(jù)集,這主要是在因為參與聚類的樣本數(shù)量上Iris數(shù)據(jù)集要遠(yuǎn)大于Seeds數(shù)據(jù)集,且Iris屬性個數(shù)偏多。

5 結(jié)束語

本文提出了一種基于菌群優(yōu)化的K均值聚類的數(shù)據(jù)挖掘方法。該方法采用菌群算法優(yōu)化K均值聚類中各節(jié)點至中心點距離,通過合理設(shè)置菌群的趨化和驅(qū)散次數(shù),優(yōu)化引力和斥力參數(shù),不斷提高數(shù)據(jù)聚類的適應(yīng)度,從而獲得最佳且穩(wěn)定的樣本所屬分類判別。后續(xù)研究將進一步優(yōu)化菌群算法參數(shù),或者引入并行運算機制,提高算法的聚類效率,增強基于菌群優(yōu)化的K均值聚類算法在大規(guī)模數(shù)據(jù)挖掘中的適用性。