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

古險峰,湯永利

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

1 引言

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

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

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

2 混合屬性數據聚類

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

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

(1)

圖1 混合屬性數據分段融合聚類框架

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

(2)

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

(3)

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

(4)

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

(5)

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

(6)

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

(7)

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

3 群體智能算法

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

3.1 編碼方式

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

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

圖2 編碼結構

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

3.2 評價指標

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

(8)

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

(9)

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

3.3 改進粒子群算法聚類

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

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

(10)

(11)

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

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

Step2:根據相異度計算出適應度值。

Step4:迭代終止,重復Step2和Step3。

Step5:將聚類結果輸出、評價。

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

(12)

4 仿真與結果分析

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

表1 數據集描述

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

(13)

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

圖3 聚類準確率對比結果

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

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

圖4 目標函數值對比結果

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

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

表2 總體精度對比結果

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

5 結束語

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

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