古險(xiǎn)峰,湯永利

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

1 引言

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

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

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

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

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

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

(1)

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

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

(2)

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

(3)

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

(4)

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

(5)

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

(6)

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

(7)

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

3 群體智能算法

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

3.1 編碼方式

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

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

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

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

3.2 評(píng)價(jià)指標(biāo)

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

(8)

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

(9)

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

3.3 改進(jìn)粒子群算法聚類

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

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

(10)

(11)

為了提高算法的速度,對(duì)粒子群算法進(jìn)行改進(jìn)。具體步驟為:

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

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

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

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

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

(12)

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

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

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

為了對(duì)聚類質(zhì)量進(jìn)行評(píng)估,采用的評(píng)價(jià)指標(biāo)為聚類準(zhǔn)確率,公式可表示為

(13)

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

圖3 聚類準(zhǔn)確率對(duì)比結(jié)果

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

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

圖4 目標(biāo)函數(shù)值對(duì)比結(jié)果

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

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

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

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

5 結(jié)束語(yǔ)

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

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