邱保志，王志林

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

0 引 言

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

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

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

1 相關分析及定義

2 算法描述

2.1 數值屬性離散化

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

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

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

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

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

(1)

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

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

輸入： 數據集D

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

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

對于z個不重復的屬性值， 初始劃分區(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ū)間對應的屬性值個數以及總屬性值個數;}

else{

h--;

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

flag=FLASE;}

} }

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

2.2 算法步驟

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

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

K-modes算法迭代時的目標函數[10]定義為

(2)

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

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

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

輸入：數據集D，聚類個數k

輸出：聚類結果

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

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

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

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

步驟5 重復步驟3和步驟4，當目標函數F不再發(fā)生變化算法結束。

3 實驗結果及分析

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

表1 數據集的基本信息

實驗前對數據集進行預處理：①刪除含有缺失值的數據，先刪除數據對象中某維數據缺失過多的維，再刪除某些維數據缺失的數據對象；②使用整數來代替分類屬性數據，例如對于性別屬性，0代表男性，1代表女性。

3.1 離散化對聚類結果的影響

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

表2 對照實驗結果

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

3.2 混合屬性數據集

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

表3 混合屬性數據集的聚類結果比較

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

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

3.3 可擴展性

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

圖1 運行時間與數值屬性中不重復的屬性值個數的關系

圖2 運行時間與維度數目的關系

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

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

3.4 算法時間復雜度分析

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

4 結束語

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