邱保志，王志林

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

0 引 言

聚類是數(shù)據(jù)挖掘的主要技術(shù)，它將相似的對象聚在一起，不相似的對象分離開來。聚類技術(shù)廣泛用于醫(yī)學(xué)、互聯(lián)網(wǎng)、金融、天氣預(yù)報等領(lǐng)域的數(shù)據(jù)分析。通常情況下，實際領(lǐng)域的數(shù)據(jù)對象是既包含數(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ù)對于實際領(lǐng)域的數(shù)據(jù)分析有重要的作用。

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

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

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

2 算法描述

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

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

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

若某個連續(xù)屬性，值域為[value1，valuez]，有z個不重復(fù)的屬性值：value1、value2、 …、valuez， (value10)。

記區(qū)間個數(shù)為h， 1≤h≤n，n是樣本總個數(shù)，根據(jù)定義1計算熵為H(h)。然后選擇兩個相鄰區(qū)間進行合并，使得H(h)-H(h-1)最小，即合并前后熵差最小，若合并前后的區(qū)間使得H(h)-H(h-1)最小超過一對，則隨機合并一對，然后重置劃分點，接著對此步進行迭代，目標(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ū)間個數(shù)，H(h0)為初次劃分區(qū)間的熵。離散化算法具體步驟如下：

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

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

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

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

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

h=z;

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

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

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

while(flag){

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

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

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

h--;

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

else{

h--;

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

flag=FLASE;}

} }

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

2.2 算法步驟

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

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

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

(2)

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

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

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

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

輸出：聚類結(jié)果

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

步驟2 從離散化后的D中隨機選取k個對象作為初始簇中心。

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

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

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

3 實驗結(jié)果及分析

實驗環(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ù)據(jù)集進行預(yù)處理：①刪除含有缺失值的數(shù)據(jù)，先刪除數(shù)據(jù)對象中某維數(shù)據(jù)缺失過多的維，再刪除某些維數(shù)據(jù)缺失的數(shù)據(jù)對象；②使用整數(shù)來代替分類屬性數(shù)據(jù)，例如對于性別屬性，0代表男性，1代表女性。

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

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

表2 對照實驗結(jié)果

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

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

為了驗證本文算法對混合屬性數(shù)據(jù)集聚類的有效性，選取了UCI中的Post Operative Patient、Heart Disease、Zoo和Hepatitis數(shù)據(jù)集，對比的混合屬性聚類算法為K-prototypes[6]、EKP[8]、FKP-MD[8]和DP-MD-FN[11]，實驗結(jié)果見表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)均高于對比算法，主要原因是：對比算法在混合屬性數(shù)據(jù)對象中，對數(shù)值屬性與分類屬性使用不同的距離度量對象相似性，這樣存在的度量的差異會造成聚類準(zhǔn)確率(ACC)不佳，本文算法引入熵離散化技術(shù)，將數(shù)值屬性轉(zhuǎn)換為分類屬性，僅使用二元化距離度量相似性，解決了混合屬性中數(shù)值屬性相似性與分類屬性相似性度量的差異問題，進而提高了聚類效果。

3.3 可擴展性

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

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

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

從圖1可以看出隨著數(shù)值屬性中不重復(fù)的屬性值個數(shù)的增加，算法運行時間會快速增加，呈近指數(shù)形式，主要是因為本文采用熵對數(shù)值屬性離散化，其離散化過程不需要人為添加參數(shù)，因此計算量較大，耗時增多。

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

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

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

4 結(jié)束語

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