基于熵的混合屬性聚類算法

邱保志，王志林

(鄭州大學(xué) 信息工程學(xué)院，河南 鄭州 450001)

0 引 言

聚類是數(shù)據(jù)挖掘的主要技術(shù)，它將相似的對(duì)象聚在一起，不相似的對(duì)象分離開(kāi)來(lái)。聚類技術(shù)廣泛用于醫(yī)學(xué)、互聯(lián)網(wǎng)、金融、天氣預(yù)報(bào)等領(lǐng)域的數(shù)據(jù)分析。通常情況下，實(shí)際領(lǐng)域的數(shù)據(jù)對(duì)象是既包含數(shù)值屬性又包含分類屬性的混合屬性數(shù)據(jù)。傳統(tǒng)聚類算法大多都只能處理單一屬性的數(shù)據(jù)，例如K-means[1]、DBSCAN[2]、DPC[3]等算法只能處理數(shù)值屬性的數(shù)據(jù)，而K-modes[4]、Fuzzy K-modes[5]等只能處理分類屬性的數(shù)據(jù)。所以，研究混合屬性數(shù)據(jù)聚類技術(shù)對(duì)于實(shí)際領(lǐng)域的數(shù)據(jù)分析有重要的作用。

相似性的度量對(duì)聚類的研究有著非常重要的作用。文獻(xiàn)[6]提到的K-prototypes算法以及文獻(xiàn)[7]和文獻(xiàn)[8]的算法是將混合屬性相似性度量拆分為數(shù)值屬性相似性和分類屬性相似性分別度量，然后再組合成混合屬性的相似性，但這樣存在一個(gè)問(wèn)題：數(shù)值屬性相似性和分類屬性相似性度量的差異會(huì)造成聚類效果不佳。例如在UCI數(shù)據(jù)集Credit approval中，前兩個(gè)對(duì)象的第一個(gè)分類屬性“A1”的二元化距離為1，而這兩個(gè)對(duì)象的第15個(gè)數(shù)值屬性“A15”的歐式距離為560,由于數(shù)值屬性間的距離遠(yuǎn)大于分類屬性之間的距離，導(dǎo)致數(shù)值屬性之間的相似性權(quán)重很小，甚至?xí)雎缘魯?shù)值屬性所體現(xiàn)的相似性特征，進(jìn)而導(dǎo)致聚類質(zhì)量的下降。其中，文獻(xiàn)[7]中對(duì)使用歐式距離度量相似性的數(shù)值屬性采用標(biāo)準(zhǔn)化來(lái)處理這個(gè)問(wèn)題，但是這樣做仍然不能消除數(shù)值屬性相似性度量和分類屬性相似性度量的差異帶來(lái)的聚類效果不佳問(wèn)題，其算法中使用的二元化距離度量分類屬性相似性會(huì)使得分類屬性相似性的權(quán)重縮小。

針對(duì)混合屬性中數(shù)值屬性與分類屬性相似性度量的差異問(wèn)題，本文引入熵離散化技術(shù)，對(duì)混合屬性數(shù)據(jù)集中的數(shù)值屬性進(jìn)行離散化，將數(shù)值屬性轉(zhuǎn)化為分類屬性，在度量相似性時(shí)僅使用二元化距離度量，從而解決由于混合屬性中數(shù)值屬性相似性度量和分類屬性相似性度量的差異而造成的聚類效果不佳問(wèn)題，在聚類中通過(guò)隨機(jī)選取初始簇中心并劃分對(duì)象，然后迭代選擇新的簇中心繼續(xù)劃分對(duì)象，直至目標(biāo)函數(shù)收斂，形成最終聚類。

1 相關(guān)分析及定義

2 算法描述

2.1 數(shù)值屬性離散化

離散化是指將連續(xù)屬性的值域劃分為若干個(gè)子區(qū)間，每個(gè)子區(qū)間對(duì)應(yīng)一個(gè)離散值，最后將原始數(shù)據(jù)轉(zhuǎn)化為離散值，其關(guān)鍵在于如何確定區(qū)間個(gè)數(shù)和劃分點(diǎn)位置。

為了消除混合屬性中數(shù)值屬性與分類屬性相似性度量的差異，引入熵離散化技術(shù)，將混合屬性中的數(shù)值屬性離散化，使用離散值來(lái)表示離散化后的數(shù)據(jù)，這樣將數(shù)值屬性轉(zhuǎn)換為分類屬性，從而使用一種相似性度量方式度量對(duì)象之間的相似性，消除度量差異。本文離散值選取離散劃分的每個(gè)區(qū)間的最大值作為離散值，即f((a,b])=b，(a

若某個(gè)連續(xù)屬性，值域?yàn)閇value1，valuez]，有z個(gè)不重復(fù)的屬性值：value1、value2、 …、valuez， (value10)。

記區(qū)間個(gè)數(shù)為h， 1≤h≤n，n是樣本總個(gè)數(shù)，根據(jù)定義1計(jì)算熵為H(h)。然后選擇兩個(gè)相鄰區(qū)間進(jìn)行合并，使得H(h)-H(h-1)最小，即合并前后熵差最小，若合并前后的區(qū)間使得H(h)-H(h-1)最小超過(guò)一對(duì)，則隨機(jī)合并一對(duì)，然后重置劃分點(diǎn)，接著對(duì)此步進(jìn)行迭代，目標(biāo)函數(shù)為[9]

G(h)=(h0-1)H(h)-H(h0)(h-1)

(1)

當(dāng)滿足G(h-1)≤G(h)停止迭代。式(1)中h0為初次劃分的區(qū)間個(gè)數(shù)，H(h0)為初次劃分區(qū)間的熵。離散化算法具體步驟如下：

算法名稱： 基于熵的離散化算法

輸入： 數(shù)據(jù)集D

輸出：D中所有數(shù)值屬性的區(qū)間劃分點(diǎn)以及離散值

for(每個(gè)連續(xù)屬性){

對(duì)于z個(gè)不重復(fù)的屬性值， 初始劃分區(qū)間， 保存劃分點(diǎn);

h=z;

利用定義1計(jì)算熵H(h);

令flag=TRUE;h0=h;H(h0)=H(h);

G(h)=(h0-1)*H(h) -H(h0)*(h-1);

while(flag){

選擇兩個(gè)相鄰區(qū)間進(jìn)行合并， 使合并前后的熵差最小， 并重置劃分點(diǎn)， 保存合并后的熵;

計(jì)算G(h-1)=(h0-1)*H(h-1) -H(h0)*((h-1)-1);

ifG(h-1)>G(h){

h--;

重新計(jì)算每個(gè)區(qū)間對(duì)應(yīng)的屬性值個(gè)數(shù)以及總屬性值個(gè)數(shù);}

else{

h--;

保存區(qū)間劃分點(diǎn)， 選取區(qū)間最大值作為離散值;

flag=FLASE;}

} }

輸出所有數(shù)值屬性的區(qū)間劃分點(diǎn)以及離散值;

2.2 算法步驟

K-means算法只針對(duì)數(shù)值屬性數(shù)據(jù)集，其選擇簇中心的策略是初始隨機(jī)選取，迭代時(shí)選取每個(gè)簇的屬性值均值作為簇中心，當(dāng)滿足目標(biāo)函數(shù)時(shí)停止迭代。K-modes算法只針對(duì)分類屬性數(shù)據(jù)集，其選擇簇中心的策略是初始隨機(jī)選取，迭代時(shí)選取簇中頻率最大的屬性值作為新的簇中心，當(dāng)滿足目標(biāo)函數(shù)時(shí)停止迭代。K-prototypes針對(duì)混合屬性數(shù)據(jù)集，其選擇簇中心的策略結(jié)合了K-means與K-modes的簇中心選取策略，其策略是初始隨機(jī)選取，迭代時(shí)分為選取數(shù)值屬性簇中心和分類屬性簇中心，數(shù)值屬性簇中心選取每個(gè)簇中的屬性值均值作為簇中心，分類屬性簇中心選取每個(gè)簇中屬性值中出現(xiàn)頻率最高的值作為簇中心，進(jìn)而將兩個(gè)簇中心組合形成混合屬性的簇中心，當(dāng)滿足目標(biāo)函數(shù)時(shí)停止迭代。

在上述算法選取簇中心策略的啟示下，本文選取簇中心的策略是：先使用熵離散化技術(shù)將混合屬性中的數(shù)值屬性離散化，使得數(shù)值屬性轉(zhuǎn)換為分類屬性，然后初始隨機(jī)選取簇中心，迭代時(shí)選取每個(gè)屬性的屬性值在簇中頻率最大的作為新的簇中心，當(dāng)滿足目標(biāo)函數(shù)時(shí)停止迭代。

K-modes算法迭代時(shí)的目標(biāo)函數(shù)[10]定義為

(2)

在K-modes算法進(jìn)行迭代的時(shí)候，式(2)不再發(fā)生變化時(shí)停止迭代。式(2)是K-modes算法針對(duì)分類型數(shù)據(jù)時(shí)使用的目標(biāo)函數(shù)，本文算法在混合屬性數(shù)據(jù)中對(duì)數(shù)值屬性進(jìn)行離散化，完成了混合屬性數(shù)據(jù)到單一的分類屬性數(shù)據(jù)的轉(zhuǎn)換，故在迭代時(shí)也使用式(2)作為本文算法的目標(biāo)函數(shù)。

本文算法包括離散化、初始化簇中心、劃分對(duì)象和迭代4個(gè)步驟。離散化使用熵進(jìn)行離散區(qū)間劃分，選取離散劃分的每個(gè)區(qū)間的最大值作為離散值。在離散化后的數(shù)據(jù)集中隨機(jī)選取k個(gè)對(duì)象初始化簇中心，使用定義2來(lái)度量對(duì)象的相似性并劃分對(duì)象。然后選取新的簇中心進(jìn)行迭代，當(dāng)式(2)不再發(fā)生變化時(shí)停止迭代。

算法名稱：基于熵的混合屬性聚類算法

輸入：數(shù)據(jù)集D，聚類個(gè)數(shù)k

輸出：聚類結(jié)果

步驟1 使用熵對(duì)D中數(shù)值屬性劃分離散區(qū)間，選取區(qū)間最大值作為離散值。

步驟2 從離散化后的D中隨機(jī)選取k個(gè)對(duì)象作為初始簇中心。

步驟3 使用定義2度量每個(gè)對(duì)象與簇中心的距離，并將每個(gè)對(duì)象劃分到距離最小的簇中。

步驟4 重新計(jì)算簇中心，選擇每個(gè)簇中數(shù)據(jù)屬性中頻率最高的屬性值作為新的簇中心的屬性取值。

步驟5 重復(fù)步驟3和步驟4，當(dāng)目標(biāo)函數(shù)F不再發(fā)生變化算法結(jié)束。

3 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)環(huán)境：CPU為Intel(R)core(TM)i5-4200M,內(nèi)存為8 GB，操作系統(tǒng)windows10，編譯環(huán)境為matlab2018a與java 1.8.0_221。

表1 數(shù)據(jù)集的基本信息

實(shí)驗(yàn)前對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理：①刪除含有缺失值的數(shù)據(jù)，先刪除數(shù)據(jù)對(duì)象中某維數(shù)據(jù)缺失過(guò)多的維，再刪除某些維數(shù)據(jù)缺失的數(shù)據(jù)對(duì)象；②使用整數(shù)來(lái)代替分類屬性數(shù)據(jù)，例如對(duì)于性別屬性，0代表男性，1代表女性。

3.1 離散化對(duì)聚類結(jié)果的影響

本文算法主要分為熵離散化、選取聚類中心、分派數(shù)據(jù)對(duì)象和迭代。為了驗(yàn)證在混合屬性數(shù)據(jù)集中對(duì)數(shù)值屬性進(jìn)行離散化能提高聚類效果的有效性。本節(jié)將本文算法去掉熵離散化這一過(guò)程作為對(duì)照組和本文算法進(jìn)行對(duì)照實(shí)驗(yàn)。選取的數(shù)據(jù)集為UCI中的Post Operative Patient、Heart Disease、Zoo和Hepatitis數(shù)據(jù)集，實(shí)驗(yàn)結(jié)果見(jiàn)表2。

表2 對(duì)照實(shí)驗(yàn)結(jié)果

在Heart Disease、Zoo和Hepatitis數(shù)據(jù)集中，本文算法聚類準(zhǔn)確率(ACC)均高于對(duì)照組，這驗(yàn)證了在混合屬性數(shù)據(jù)集中對(duì)數(shù)值屬性進(jìn)行離散化能夠提高聚類效果的有效性。在Post Operative Patient數(shù)據(jù)集中。主要是因?yàn)樵赑ost Operative Patient數(shù)據(jù)集中數(shù)值屬性的不重復(fù)的屬性值較少，在離散化之前可以視其為已經(jīng)離散化后的數(shù)據(jù)集，故而本文算法聚類準(zhǔn)確率(ACC)均與對(duì)照組持平。

3.2 混合屬性數(shù)據(jù)集

為了驗(yàn)證本文算法對(duì)混合屬性數(shù)據(jù)集聚類的有效性，選取了UCI中的Post Operative Patient、Heart Disease、Zoo和Hepatitis數(shù)據(jù)集，對(duì)比的混合屬性聚類算法為K-prototypes[6]、EKP[8]、FKP-MD[8]和DP-MD-FN[11]，實(shí)驗(yàn)結(jié)果見(jiàn)表3。

表3 混合屬性數(shù)據(jù)集的聚類結(jié)果比較

在Post Operative Patient數(shù)據(jù)集中，本文算法聚類準(zhǔn)確率(ACC)比K-prototypes高出0.092，比EKP高出0.035，比FKP-MD高0.18，比DP-MD-FN高0.012。在Heart Disease數(shù)據(jù)集中，本文算法聚類準(zhǔn)確率(ACC)比K-prototypes高出0.23，比EKP高出0.283，比FKP-MD高0.283，比DP-MD-FN高0.049。在Zoo數(shù)據(jù)集中，本文算法聚類準(zhǔn)確率(ACC)比K-prototypes高出0.128，比EKP高出0.247，比FKP-MD高0.029，比DP-MD-FN高0.019。在Hepatitis數(shù)據(jù)集中，本文算法聚類準(zhǔn)確率(ACC)比K-prototypes高出0.186，比EKP高出0.05，比FKP-MD高0.06，比DP-MD-FN高0.05。

本文算法聚類準(zhǔn)確率(ACC)均高于對(duì)比算法，主要原因是：對(duì)比算法在混合屬性數(shù)據(jù)對(duì)象中，對(duì)數(shù)值屬性與分類屬性使用不同的距離度量對(duì)象相似性，這樣存在的度量的差異會(huì)造成聚類準(zhǔn)確率(ACC)不佳，本文算法引入熵離散化技術(shù)，將數(shù)值屬性轉(zhuǎn)換為分類屬性，僅使用二元化距離度量相似性，解決了混合屬性中數(shù)值屬性相似性與分類屬性相似性度量的差異問(wèn)題，進(jìn)而提高了聚類效果。

3.3 可擴(kuò)展性

本節(jié)檢測(cè)本文算法在數(shù)據(jù)對(duì)象的增多與數(shù)據(jù)維度增加的情況下的運(yùn)行效率。但本文算法在數(shù)據(jù)對(duì)象增加時(shí)的運(yùn)行效率主要被熵離散化的過(guò)程影響，而在這個(gè)離散化過(guò)程中的運(yùn)行效率主要是被數(shù)值屬性中不重復(fù)的屬性值個(gè)數(shù)影響。因此本節(jié)可擴(kuò)展性主要是檢測(cè)算法在數(shù)值屬性中不重復(fù)的屬性值個(gè)數(shù)的增加和數(shù)據(jù)集維度增加時(shí)的運(yùn)行效率。選取UCI數(shù)據(jù)集中的Adult數(shù)據(jù)集來(lái)抽取樣本用來(lái)檢測(cè)。Adult數(shù)據(jù)集中的第三條屬性“fnlwgt”(數(shù)值屬性)用來(lái)測(cè)量算法運(yùn)行效率與在數(shù)值屬性中不重復(fù)的屬性值個(gè)數(shù)的關(guān)系，對(duì)“fnlwgt”屬性值按照升序排列，然后選取不同的不重復(fù)屬性值個(gè)數(shù)進(jìn)行實(shí)驗(yàn)，結(jié)果如圖1所示。選取Adult中前1000個(gè)對(duì)象的第二條屬性“workclass”(分類屬性)為樣本，并將其擴(kuò)充為高維度來(lái)檢驗(yàn)算法在數(shù)據(jù)集維度增加時(shí)的運(yùn)行效率，結(jié)果如圖2所示。

圖1 運(yùn)行時(shí)間與數(shù)值屬性中不重復(fù)的屬性值個(gè)數(shù)的關(guān)系

圖2 運(yùn)行時(shí)間與維度數(shù)目的關(guān)系

從圖1可以看出隨著數(shù)值屬性中不重復(fù)的屬性值個(gè)數(shù)的增加，算法運(yùn)行時(shí)間會(huì)快速增加，呈近指數(shù)形式，主要是因?yàn)楸疚牟捎渺貙?duì)數(shù)值屬性離散化，其離散化過(guò)程不需要人為添加參數(shù)，因此計(jì)算量較大，耗時(shí)增多。

從圖2可以看出，數(shù)據(jù)集隨著維度的增加并沒(méi)有使得運(yùn)行時(shí)間快速增加，可以得出本文算法運(yùn)行效率被單一的維度增加影響并不大。

3.4 算法時(shí)間復(fù)雜度分析

對(duì)于數(shù)據(jù)對(duì)象個(gè)數(shù)為n的數(shù)據(jù)集D，本文算法的時(shí)間復(fù)雜度主要與熵離散化、計(jì)算聚類中心、分派數(shù)據(jù)對(duì)象以及迭代次數(shù)有關(guān)。熵離散化的時(shí)間復(fù)雜度為O(Nr×n2)，Nr為數(shù)值屬性的個(gè)數(shù)。計(jì)算聚類中心的時(shí)間復(fù)雜度為O(n×q)，其中q為數(shù)據(jù)的維數(shù)個(gè)數(shù)。分派的時(shí)間復(fù)雜度為O(n×q×k)，k為聚類中心個(gè)數(shù)。根據(jù)上述分析算法的時(shí)間復(fù)雜度為O(Nn×n2+t×(n×q×k+n×q))，由于n×q×k>n×q，因此算法的時(shí)間復(fù)雜度為O(Nn×n2+t×(n×q×k))，t為迭代次數(shù)，本文算法主要在對(duì)數(shù)值屬性進(jìn)行離散化時(shí)會(huì)耗時(shí)較大，當(dāng)數(shù)值屬性中不重復(fù)的屬性值個(gè)數(shù)越多，算法在運(yùn)行過(guò)程中會(huì)耗時(shí)越多。

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

本文應(yīng)用熵離散化技術(shù)，提出了基于熵的混合屬性聚類算法。算法將混合屬性中的數(shù)值屬性轉(zhuǎn)化為分類屬性，使用單一的二元化距離度量對(duì)象之間的相似性，解決了因混合屬性中數(shù)值屬性與分類屬性相似性度量的差異而造成的聚類效果不佳問(wèn)題，實(shí)驗(yàn)驗(yàn)證了算法的有效性，與同類算法相比，有較高的聚類精度。該思想可為混合屬性數(shù)據(jù)集的數(shù)據(jù)分析提供一種技術(shù)參考。