基于群體智能算法的混合屬性大數(shù)據(jù)聚類仿真

古險峰,湯永利

(1. 鄭州工業(yè)應(yīng)用技術(shù)學院信息工程學院,河南 鄭州 451100;2. 河南理工大學計算機科學與技術(shù)學院,河南 焦作454000)

1 引言

如何在大量的數(shù)據(jù)中找到需要的數(shù)據(jù)類別,提高數(shù)據(jù)的利用價值已成為當前網(wǎng)絡(luò)應(yīng)用的巨大挑戰(zhàn)[1]。聚類分析能夠?qū)?shù)據(jù)集劃分成眾多類別,在增加同簇對象相似度的同時,盡可能地減小不同簇對象的相似度[2]。目前有很多聚類方法,但因數(shù)據(jù)具有數(shù)值屬性和分類屬性,大多數(shù)的聚類方法只能對單一類型的數(shù)據(jù)進行處理。如果采用單一型處理的方法對數(shù)據(jù)進行聚類,會嚴重影響混合數(shù)據(jù)的聚類效果,導(dǎo)致數(shù)據(jù)中重要的信息丟失[3-5]。

由于生活中存在的數(shù)據(jù)大部分都是具有數(shù)值屬性與分類屬性的混合屬性數(shù)據(jù),因此混合屬性的數(shù)據(jù)是廣泛存在的,對混合屬性數(shù)據(jù)進行聚類研究具有重要意義。文獻[6]在混合屬性數(shù)據(jù)聚類中引入了聚類融合算法,通過聚類融合理論求解數(shù)據(jù)的聚類問題,把每類屬性作為一個聚類器的輸出,構(gòu)建出算法的框架,并建立了最大化共享信息的目標函數(shù),該方法大大提高了測試數(shù)據(jù)與客戶管理數(shù)據(jù)的穩(wěn)定性與準確性。文獻[7]設(shè)計了由網(wǎng)絡(luò)爬蟲、數(shù)據(jù)處理和數(shù)據(jù)分析等四部分模塊組成的硬件系統(tǒng),分別通過單機與分布式方法對大數(shù)據(jù)進行聚類處理,并在設(shè)計的硬件平臺上編寫數(shù)據(jù)處理與數(shù)據(jù)分析的程序,該方法對混合屬性的數(shù)據(jù)分析準確性較高。文獻[8]在自監(jiān)督學習群體智能算法中引入突變操作,優(yōu)化最優(yōu)解,同時計算出各個樣本的行為方程,采用K-means方法提高算法的收斂速度,該方法聚類質(zhì)量較高,收斂速度較快。

針對混合屬性數(shù)據(jù)聚類質(zhì)量不高的問題,對數(shù)據(jù)集中的數(shù)據(jù)點所包含的數(shù)值屬性和分類屬性進行分析,對數(shù)據(jù)集中的隨機數(shù)據(jù)點間的距離度量做響應(yīng)處理。利用信息熵確定數(shù)值屬性數(shù)據(jù)中的權(quán)重值,計算出類中心的相似度,并對粒子群算法進行改進。通過對真實數(shù)據(jù)集的仿真,驗證基于群體智能混合屬性數(shù)據(jù)聚類方法的有效性。

2 混合屬性數(shù)據(jù)聚類

針對混合屬性數(shù)據(jù)的聚類問題,主要有類型轉(zhuǎn)換、聚類融合、層次聚類和密度聚類等幾種方法,后兩種方法與數(shù)值屬性聚類方法思路相似,均將混合屬性數(shù)據(jù)點的距離度量與傳統(tǒng)聚類思路進行綜合分析處理,因此本文將混合屬性數(shù)據(jù)的相似性作為重點的度量方法進行研究。

聚類融合方法是混合屬性聚類的主要方法之一,主要思想是通過對一種算法進行多次運算或通過多種算法對一組對象進行劃分,并利用共識函數(shù)對得出的結(jié)果進行合并聚類處理。假設(shè)混合屬性數(shù)據(jù)集為X,每個數(shù)據(jù)對象為Xi,對數(shù)據(jù)集X按照a維屬性相似度進行聚類分析,將數(shù)據(jù)集a維屬性映射到一維分類屬性,該分類屬性用矩陣可表示為

(1)

圖1 混合屬性數(shù)據(jù)分段融合聚類框架

采用混合屬性數(shù)據(jù)分段融合框架不僅提高了對分類屬性子集的處理效率,還降低了信息的失真性。針對特定屬性值域,構(gòu)建相似屬性值集合,該集合中任意值在集合中貢獻的距離用公式可表示為

(2)

其中,fmk表示屬性值在值域中出現(xiàn)的頻率;n表示數(shù)據(jù)集中數(shù)據(jù)的點數(shù);k表示數(shù)據(jù)維度。那么任意兩個數(shù)據(jù)點(Xi,Xj)的距離用公式可表示為

(3)

其中,l表示兩個數(shù)據(jù)點(Xi,Xj)的共有維度;αk表示第k維分類屬性的熵權(quán)比值系數(shù)。在高維度下,通過設(shè)定相似度閾值β,來判斷兩個數(shù)據(jù)點是否在該維度上相等。每一維度數(shù)據(jù)點和簇的概率相似度稱為點簇相似度,用公式可表示為

(4)

其中,spoi＿clu＿i表示第i維度上的點簇維度概率相似度;k表示數(shù)據(jù)點的維度。為了更好地體現(xiàn)數(shù)值屬性數(shù)據(jù)聚類效果,利用信息熵對數(shù)值屬性數(shù)據(jù)加權(quán)處理,可以避免類中心數(shù)據(jù)一致導(dǎo)致的空簇問題。信息熵直接反映數(shù)據(jù)的有用程度,信息熵越小,表明數(shù)據(jù)集越有序;信息熵越大,表明數(shù)據(jù)集越雜亂。第s維屬性的信息熵用公式可表示為

(5)

其中,δis表示數(shù)據(jù)對象Xi的第s維數(shù)據(jù)屬性比重;n表示數(shù)據(jù)對象的個數(shù)。信息熵的權(quán)值用公式可表示為

(6)

為了克服數(shù)據(jù)集中任意兩個數(shù)據(jù)點選擇初始聚類中心造成聚類結(jié)果不穩(wěn)定的問題,采用平均差異度方法選擇每個數(shù)據(jù)對象的初始聚類中心。中心思想是:數(shù)據(jù)集中數(shù)據(jù)的初始聚類中心平均差異度應(yīng)該較大,且聚類中心的差異度要比數(shù)據(jù)集的總體平均差異度大。平均差異度和總體平均差異度用公式分別表示為

(7)

通過混合屬性距離及平均差異度的計算,在傳統(tǒng)方法的基礎(chǔ)上擴展了對數(shù)值屬性數(shù)據(jù)處理的限定,能夠更好得解決混合屬性數(shù)據(jù)的聚類問題。

3 群體智能算法

群體智能優(yōu)化算法采用并行搜索方式解決初始聚類中心敏感問題,將聚類分析作為優(yōu)化問題解的一種算法。群體智能算法具有無集中控制點和組織能力強等特點,本文主要從數(shù)據(jù)的編碼方式、評價指標數(shù)等方面入手,對群體智能算法進行優(yōu)化。

3.1 編碼方式

群體智能算法的優(yōu)化主要是對數(shù)據(jù)集的目標函數(shù)和編碼方式進行考慮。針對聚類問題,編碼方式不同,對應(yīng)的目標函數(shù)也不同,因此確定數(shù)據(jù)的編碼方式非常必要。

將數(shù)據(jù)點按順序進行標號1～N,那么聚類中心的搜索空間可表示為[1,N],選擇搜索空間中的m個數(shù)據(jù)點作為聚類中心{Y1,Y2,…,Ym},編碼結(jié)構(gòu)如圖2所示。

圖2 編碼結(jié)構(gòu)

通過對待分類數(shù)據(jù)樣本的聚類中心進行編碼,可以確定出可行域的范圍為[1,N],個體位置是可行域范圍內(nèi)數(shù)據(jù)集中數(shù)據(jù)點的組合,由于數(shù)據(jù)點的映射范圍是明確的,因此能夠大大提高搜索效率,減少群體智能算法中無效解的產(chǎn)生。

3.2 評價指標

為了衡量聚類問題的有效性,需要根據(jù)聚類結(jié)果的形態(tài)評價聚類效果,采用適應(yīng)度函數(shù)對個體的好壞進行評價。根據(jù)聚類中心與聚類方法求出適應(yīng)度函數(shù),最常見的適應(yīng)度函數(shù)為聚類誤差,聚類誤差平方用公式可表示為:

(8)

其中,k表示聚類個數(shù);Hl(Xj,Cj)表示數(shù)據(jù)點與聚類中心間的距離;|Ci|表示分類到第i類數(shù)據(jù)點的數(shù)目。按照本文方式進行實數(shù)編碼時,通過數(shù)據(jù)集的數(shù)據(jù)間相異度矩陣描述,聚類的適應(yīng)度函數(shù)表示為

(9)

其中,yi表示第i個聚類中心;p(j,n)表示數(shù)據(jù)點Xi和Xj的相異度值;N表示樣本總量。

3.3 改進粒子群算法聚類

為了解決聚類中心敏感、數(shù)據(jù)易陷入誤區(qū)等問題,利用粒子群智能優(yōu)化算法的全局搜索能力找到數(shù)據(jù)集中的最優(yōu)解,將聚類問題視為解的優(yōu)化問題。

粒子群聚類算法通過對粒子個體位置的不斷更新,來尋找全局最優(yōu)解。每個粒子不僅能夠記住搜索過程的最優(yōu)解,還能記住整個粒子群的最優(yōu)位置。假設(shè)每個粒子的速度為V,維度和個體位置為Q,那么粒子在下一時刻的速度用公式表示為:

(10)

(11)

為了提高算法的速度,對粒子群算法進行改進。具體步驟為:

Step1:對待分類數(shù)據(jù)樣本的聚類中心進行編碼,對粒子群初始化,保證速度為相同維度。

Step2:根據(jù)相異度計算出適應(yīng)度值。

Step4:迭代終止,重復(fù)Step2和Step3。

Step5:將聚類結(jié)果輸出、評價。

設(shè)種群的粒子數(shù)目為M,那么每次迭代后粒子的更新位置用公式可表示為:

(12)

4 仿真與結(jié)果分析

為了評估分段融合聚類框架和改進群體智能算法的有效性與可行性,實驗在MATLAB仿真平臺上實現(xiàn),實驗數(shù)據(jù)選取UCI數(shù)據(jù)庫中的Iris、Creditapproval、Heartdisease和Soybean具有代表性的4個數(shù)據(jù)集,這4個數(shù)據(jù)集中有3種數(shù)據(jù)類型,分別為數(shù)值型數(shù)據(jù)、混合型數(shù)據(jù)和分類型數(shù)據(jù)。數(shù)據(jù)集的描述如表1所示。

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

為了對聚類質(zhì)量進行評估,采用的評價指標為聚類準確率,公式可表示為

(13)

其中,n表示數(shù)據(jù)集總量;ri表示數(shù)據(jù)集被正確分類的數(shù)據(jù)點數(shù)量;k表示聚類數(shù)量。分別將本文方法與文獻[6]、文獻[7]和文獻[8]的方法進行對比,實驗結(jié)果如圖3所示。

圖3 聚類準確率對比結(jié)果

從圖中可以看出,采用本文算法對數(shù)據(jù)集進行聚類分析,無論是處理數(shù)值型數(shù)據(jù)、分類型數(shù)據(jù),還是混合型數(shù)據(jù),聚類準確率均高于其它算法,說明本文算法的聚類質(zhì)量較高。

為了進一步對數(shù)據(jù)的聚類質(zhì)量進行驗證,比較本文算法與文獻[6]、文獻[7]和文獻[8]的方法的聚類精度,結(jié)合Creditapproval數(shù)據(jù)集的聚類結(jié)果,對數(shù)據(jù)集依次進行迭代,比較不同算法的目標函數(shù)值,對比結(jié)果如圖4所示。

圖4 目標函數(shù)值對比結(jié)果

從圖中可以看出,當?shù)螖?shù)為1時,采用這4種方法,目標函數(shù)值均有降低趨勢,然而采用文獻[6]方法的下降趨勢不明顯,隨著迭代次數(shù)的增加,采用文獻[7]方法的目標函數(shù)值不穩(wěn)定,在相同情況下,很明顯本文算法的目標函數(shù)值小于其它算法,說明本文算法的聚類精度比其它方法都高。

為了驗證編碼方式與適應(yīng)度函數(shù)對聚類問題的影響程度,將本文方法與粒子群算法進行比較,總體精度對比結(jié)果如表2所示。

表2 總體精度對比結(jié)果

從表中可以看出,改進的粒子群算法具有較高的總體精度,聚類效果良好。改進的粒子群算法采用本文的編碼方式,在一定范圍內(nèi)可以限定住粒子的搜索,解決了粒子算法搜索超出空間,產(chǎn)生無效解的問題。本文算法不僅提高了搜索效率,還增強了算法的魯棒性,大大降低了算法的復(fù)雜度。

5 結(jié)束語

由于實際生活中產(chǎn)生大量的數(shù)據(jù),且大多數(shù)都是由數(shù)值屬性和分類屬性構(gòu)成的混合屬性數(shù)據(jù),為了對混合屬性數(shù)據(jù)的聚類進行研究,提出基于群體智能算法的混合屬性大數(shù)據(jù)聚類方法。

對初始聚類中心的選取方法進行優(yōu)化,并對混合屬性的數(shù)據(jù)度量方法進行改進,使數(shù)據(jù)集中的數(shù)據(jù)點在劃分過程中可以更加準確的與各種聚類集的相似度進行區(qū)分,并對群體智能優(yōu)化算法進行分析與改進。選取UCI數(shù)據(jù)庫中具有代表性的4個數(shù)據(jù)集,在MATLAB平臺上實現(xiàn)仿真,實驗結(jié)果表明,本文算法的聚類質(zhì)量和聚類精度均高于其它算法,驗證了本文算法的有效性與可行性。