安 寧，江思源，唐 晨，楊矯云

1.合肥工業(yè)大學 國家智慧養(yǎng)老國際科技合作基地，合肥230601

2.合肥工業(yè)大學 計算機與信息學院，合肥230601

1 引言

聚類分析的主要目的是發(fā)現數據中隱藏的類結構，并將物理或抽象的數據集劃分成不同類的過程，使類內對象間的相似度較大，而類間對象間的相似度較小[1]。對于同時包含數值型和分類型屬性的混合數據集，其相似性度量方式與單一類型的度量方式存在較大差異。現有的聚類算法多用于解決單一類型（分類型或數值型）數據集的聚類問題[2-4]，不適用于混合數據集。例如K-Means 算法[5]、EM 算法[6]等局限于數值型數據集聚類，K-Modes[7]、Rock 算法[8]等局限于分類型數據集聚類?？紤]到同時具有分類型屬性和數值型屬性的混合數據集存在于許多領域中，如醫(yī)學、生物學等，設計高效的混合數據聚類算法是非常迫切的[9]。

目前，研究者們已經提出了一些用于混合數據集的聚類算法[10]，這些算法可以分為兩種類別。第一種類別的算法為分類型數據和數值型數據分別設計不同的相似性度量，然后將這兩部分加權求和。例如，Huang 結合K-Means 算法和K-Modes 算法提出用于混合數據集聚類的K-Prototypes 算法[4]，Cheung 和Jia 提出了OCIL算法[11]，該算法是基于對象與簇的相似性度量的迭代聚類算法。第二種類別的算法將分類型屬性轉換為數值型屬性，或將數值型屬性轉換為分類型屬性，然后應用單一屬性的聚類算法。最直接的方法是將分類值映射到數值向量中，如果分類型屬性包含n 個不相同的值，則每個值都映射到v 維向量。David 和Averbuch 提出的SpectralCAT 算法[12]，自動將高維數值型數據轉換為分類型數據，然后應用譜聚類算法，通過自動非線性轉換降低了數據集的維度。

在設計聚類算法時，相似性或相異性度量起著重要作用。數值型數據使用連續(xù)變量來表示每個屬性的值，使用數值距離，例如歐幾里德距離，來度量數值對象間的相似性。而分類型數據的值沒有大小之分，用數值距離度量分類型數據對象間的相似性，會丟失相似性信息[13]，因此，漢明距離常用于分類型數據的相似度度量。由于這兩種不同類型數據的性質存在較大差異，為單一類型數據集設計的方法無法直接應用于其他類型的數據集，應該設計不同的相似性度量或在相似性度量之前將數據轉換為同一類型。例如，在K-Prototypes 算法的相異性度量過程中，數值型數據采用歐幾里德距離，而分類型數據采用漢明距離。該算法還通過用戶定義的參數對這兩部分的相異性進行加權求和，用參數控制分類型屬性和數值型屬性對于聚類結果的貢獻。K-Proto‐types 算法簡單易行，因此廣泛用于混合數據集聚類。但是，漢明距離進行分類型數據的相似性度量是比較粗略的，并且聚類結果對于該參數的設置非常敏感。隨后，研究者們提出了一些改進的分類型數據的相似性度量，通過基于分類值的頻率、共現、條件概率估計等方法提高相似性度量的合理性[14-15]。例如，OCIL算法使用分類型對象值在簇中出現的頻率用于分類型數據的相似性度量，并使用歸一化的歐幾里德距離用于數值型數據的相似性度量。

在實際應用中，各個屬性通常對所需的聚類結果有不同的貢獻，在相似性度量時應該考慮為不同屬性分配不同的權重。例如，在乳房X 線照相腫塊數據集中，希望數據集分為良性和惡性這兩類。在聚類過程中，年齡屬性比腫塊密度屬性起更重要的作用[16]。因此，識別不同的屬性的貢獻程度可以提高聚類效果。實際上，一些研究者已經意識到這個問題并提出了幾種策略，但大多數研究側重于單一類型的數據集。例如，在分類型數據的相似性度量過程中，Chen 和Guo 提出根據屬性值的整體分布來分配權重[17]，Bai 等提出基于類中心出現的頻率和對象與聚類中心之間的平均距離的加權機制[18]。OCIL 算法基于信息熵僅為每個分類型屬性分配權重，并將所有數值型屬性視為一個整體，削弱了數值型屬性的重要性。Ahmad 和Dey 通過僅為數值型屬性分配權重[19]，提出用于混合數據集的聚類算法。實際上，在設計相似性度量的加權策略時應該同時考慮分類型屬性和數值型屬性。

本文提出一種融合單純形映射與熵加權的聚類方法，用于具有分類型屬性和數值型屬性的混合數據集聚類。首先，通過單純形理論將分類型屬性映射到高維數值型向量，使任意兩個值間的歐幾里德距離相同，且向量間的夾角相同，使得映射后的數據集可直接應用數值型屬性聚類算法；然后，基于信息熵理論為不同的屬性分配不同的權重以便反映不同屬性的信息量差異；最后，結合權重設計相似性度量并應用于K-Means框架得到聚類算法。在UCI 混合數據集上與傳統(tǒng)映射聚類算法和K-Prototype算法進行了比較。實驗結果表明，基于提出的聚類算法優(yōu)于這兩種方法。

2 問題定義

聚類指根據特定標準將未給定標簽的對象分為若干類，使相似的對象分到同一類，而不相似的對象分到不同類中。假設混合數據集X 由m 個對象組成，表示為[x1,x2,…,xm]。假 設 X 包 含dc個 分 類 型 屬 性和du個數值型屬性，則對 象 xi(i=1,2,…,m)可 表 示 為，其 中，表示對象在分類型屬性上的取值，表示對象在數值型屬性上的取值。假設數據集X 經過聚類算法得到的聚類結果為C1,C2,…,Ck共k個類，即C={C1,C2,…,Ck}，且Ci?Cj=?，通過目標函數可以找到最佳分配矩陣T*：

根據公式（1），只要確定了相似性度量函數s(xi,Cj)，就可以獲得聚類情況。在相似性度量過程中，考慮到各個屬性對于聚類結果的貢獻程度，本文定義了一種新的混合數據相似性度量函數，為每個屬性分配權重，滿足0 ≤w r

3 融合單純形映射與熵加權的聚類

3.1 單純形映射

對于分類型屬性，值域中的值沒有自然順序，因此任意兩個值之間的距離被認為是相同的。而數值型屬性的每對值具有數值距離。由于分類型屬性和數值型屬性具有不同的特性，使用歐幾里德距離來進行分類型屬性上的相似性度量是不合適的。因此，本文采用向量映射策略，將分類型屬性的值映射到高維向量上，并確保各向量之間的歐幾里德距離相等。這樣，在相似性度量過程中，分類型屬性與數值型屬性就可以統(tǒng)一處理。

對于一個分類型屬性A，值域用dom(A)表示，由屬性A可以取的所有值的集合構成，ag(g=1,2,…,|A|)表示值域中的一個值，|A|表示屬性A值域中不同值的數目。則dom(A)可以表示為dom(A)={a1,a2,…,a|A|}。如果將值ag映射到一個向量vg上，則屬性A映射后包含|A|個向量。為了保證任意兩向量間距離相等，必須要求映射后的向量滿足下面的方程：

該方程有很多解，因此需要找出維度最小的向量。該方程的解中維度最小的向量是基于正則單純形構造的向量，因此屬性A的各個分類值可以映射到|A|-1維空間中，即各分類值映射后的向量的維數為|A|-1[20]。

圖1 展示了2 維正則單純形和3 維正則單純形，可以看出2 維正則單純形是一個等邊三角形，3 維正則單純形是一個正四面體。

圖1 2維正則單純形和3維正則單純形

分類型屬性A 的值ag映射到一個向量vg上，g=1,2,…,|A|，且vg是 一 個|A|-1 維 向 量，表 示 為，其中表示向量vg在第i 維上的分量，i=1,2,…,|A|-1。分類型屬性A的各分類值映射的向量構成映射矩陣V|A|，矩陣的第g 行表示值ag的映射向量vg。

包含n 個值的分類型屬性的映射矩陣Vn可以用n×(n-1)的矩陣來表示，矩陣的每一行對應一個向量。

綜上所述，通過應用單純形映射策略，將數據集X轉換為純數值型數據集Y 的程序如下：

算法1 向量映射策略

輸入：X

輸出：Y

算法1中，第1～9行，根據分類型屬性取值數目最多的值n 構造n-1維映射矩陣Vn。第10～16 行在屬性的值域中找到與值相等的值，在Vn中獲得向量表 示 矩 陣Vn的 第g 行 的1 到列組成的向量。第17～19 行保持數值型屬性值不變。將數據集中的分類型屬性值替換為映射向量，數值型屬性值不變，就得到新的數據集Y。

由于數據集Y 的屬性均為數值型，可以用對象xi與類Cj的聚類中心間的歐幾里德距離來定義相似度。

3.2 基于信息熵的屬性加權策略

3.2.1 分類型屬性信息熵計算

為屬性分配合適的權重可以提高聚類效果。在信息論中，信息熵是一種度量系統(tǒng)不確定性的方法，可以用于評估信息量的大小。根據文獻[22]中提出的Mea‐sure III，屬性的不確定性越高，該屬性提供的信息量越高。屬性提供的信息量越高，該屬性的重要性也就越高。信息熵作為一種有效的度量機制，在聚類分析、不確定性度量等領域得到廣泛的研究和應用。本文根據各分類型屬性的信息熵度量其在聚類過程中的重要程度，分配相似性度量中的權重。

定義1（信息熵公式）由于分類型屬性的值域是確定的，因此值域中的值可以視為離散和獨立的。數據集X 中任意分類型屬性A的重要性可以用信息熵公式度量：

其中，p(ag)表示值ag在數據集X 中對于屬性A的概率密度函數。若由公式（5）的熵值作為屬性權重，則一個屬性的值域越大，該屬性的權重就越高。然而，在實際應用中，并不是屬性值域越大，重要性就越高。例如，銀行客戶信息中的客戶編號和客戶姓名，每個對象的客戶編號均不同，客戶姓名也基本不同，這兩個屬性包含的信息量大，但對聚類的貢獻程度卻很小[11]。為了避免為這種信息量特別大的屬性被分配較高的權重，向公式（5）中增加一個分母，分母設為該屬性的取值個數|A|，這樣，屬性取值個數較多，信息熵也會相應減小。因此，將公式（5）調整為公式（6），得到調整信息熵：

將數據集X 中所有屬性的調整信息熵的值進行歸一化，得到各分類型屬性的權重公式：

其中，H_sum 表示所有屬性的權重之和，計算過程將在

3.2.2 小節(jié)介紹。

3.2.2 數值型屬性上的信息熵計算

由于3.2.1 小節(jié)中提出的基于熵的加權策略不適用于數值型屬性，因此可以根據離散化的數值數據應用加權策略。數值數據離散化的方法有很多，文獻[23]提出的等寬離散化方法，根據用戶指定的區(qū)間數目h，將屬性值域劃分為h 個等寬的區(qū)間。由于等寬離散化方法簡單易實現，本文采用該方法用于數值型屬性數據的離散化。

對數據集X 中的每個數值型屬性數據Xl(l=1,2,…,du)重復離散化過程。因此，上一節(jié)中定義的基于信息熵加權策略可以應用于離散化后的數據。數值型屬性的權重可以用公式（8）計算：

3.3 混合數據上的相似性度量

結合3.1節(jié)和3.2節(jié)，混合數據上的相似性度量可以定義為：

根據公式（10），將基于加權單純形映射的相似性度量應用于K-Means算法框架，得到加權單純形映射聚類算法，實施過程描述如下：

算法2 加權單純形映射聚類算法

輸入：數據集X，idxold={0,0,...,0}，聚類數k；

輸出：idxnew={idx1,idx2,...,idxm}

1.for r=1 to dcdo

3.Y=VectorMap(X)

4.for l=1 to dudo

7.for r=1 to dcdo

9.for r=1 to dcdo

11.隨機選取k個聚類中心：{c1,c2, ,ck}

12.noChange=true；

13.repeat

14.for i=1 to m do

17.if idxnew≠idxold

18. noChange=false；

19. 更新k個類的聚類中心；

20.until（noChange=true）

21.return idxnew

在算法2 中，1、2 行計算分類型屬性的調整信息熵，第3 行調用算法1 的向量映射策略，將數據集X 中的分類型屬性映射為數值向量，以便分類型屬性可以與數值型屬性統(tǒng)一處理。4～6 行計算數值型屬性的調整信息熵，其中第5 行調用3.2.2 小節(jié)數值型數據離散化過程，根據離散化結果計算調整信息熵。7～10 行根據調整信息熵計算各屬性的權重。11～21 行為應用K-means算法框架的聚類過程，其中，第15 行運用本文設計的相似性度量計算樣本與類間的相似度。

4 實驗結果

為了測試基于所提出的加權單純形映射聚類算法的有效性，本文從UCI 機器學習數據庫（URL：http：//archive.ics.uci.edu/ml/）中選擇了6 個混合數據集，將加權單純形映射聚類算法與現有的聚類算法進行了比較，包括K-Prototypes 算法、傳統(tǒng)映射聚類算法和K-modes算法。

在實驗中，考慮到聚類結果受所選初始聚類中心的影響，在每次測試期間為所有方法設置相同的初始聚類中心，并且以下實驗結果均為算法隨機運行100次的平均值。另外，數值型數據離散化過程中的區(qū)間個數h 設為10。從UCI 中選取的6 個混合數據集的信息如表1 所示，包括樣本數，兩種類型屬性的數目、類數以及類分布。其中，類分布表示不同類中樣本的概率分布。

表1 混合數據集的信息描述

為了評估所提出的聚類算法的性能，將其聚類結果與K-Prototype和傳統(tǒng)映射聚類算法進行了比較，這些聚類算法的聚類誤差的平均值和標準差如表2 所示。在實驗中，對于K-Prototypes 算法，權重參數γ根據作者建議設置為1.5。

表2 迭代聚類算法在混合型數據集上與傳統(tǒng)映射算法和K-Prototype算法的比較

從表2可以看出，在Ticdata數據集上，三種算法的聚類準確度相同，這可能與數據本身的特性有關，該數據集包含2類，且類的分布差異過大，樣本基本上為第1類，第2類的樣本量只占5.98%。在其他5個數據集上，基于所提出的加權單純形映射聚類算法均優(yōu)于K-Prototype 和傳統(tǒng)映射聚類算法，盡管不同數據集的分類型屬性的數量與數值型屬性的數量差異很大，與其他兩種方法相比，加權單純形映射聚類算法將聚類結果的準確度分別提高2.70%和18.33%。特別是在Dermatology 數據集中，加權單純形映射聚類算法將準確度分別提高了10.21%和44.42%。

為了分析所提出的聚類算法能提高聚類準確度的原因，將聚類過程中各屬性的調整信息熵繪制成箱線圖。箱線圖[25]是一個簡單的數據探索性分析工具，主要利用數據中的6 個統(tǒng)計量定量描述數據的分布情況，從大到小依次為：上邊緣、上四分位數(Q3)、中位數、下四分為數(Q1)、下邊緣和異常值。其中，Q3和Q1是中間50%的數據里的最大值和最小值，中位數是指中間50%的 數 據 的 中 位 數 。四 分 位 距I QR=Q3-Q1,Q3+1.5IQR 和Q1-1.5IQR 稱 為 內 限，Q3+3IQR和Q1-3IQR稱為外限。上邊緣為數據在Q3到Q3+1.5IQR 間的最大值，下邊緣為數據在Q1 到Q1-1.5IQR 間的最小值。內限以外的值均為異常值，內限與外限之間的值稱為溫和的異常值，外限以外的值稱為極端的異常值。圖2 為各屬性的調整信息熵的箱線圖，其中，上四分位數與下四分為數構成盒子，盒子中間的紅色豎線為中位數，盒子左右兩邊的黑色豎線分別為上邊緣和下邊緣，內限與外限在圖中沒有標出，異常值用紅點表示。從圖2 中可以看出，Credit Approval、Cylinder Bands 和Dermatology 數據集的屬性熵值的分布差異較大。其他三個數據集熵值的分布比較集中。

圖2 屬性調整熵箱線圖

圖3 、圖4 和 圖5 分 別 為Dermatology、Credit Ap‐proval 和Tae 數據集上各屬性熵值的折線圖，橫坐標為屬性編號，縱坐標為屬性的調整信息熵。

圖3 Dermatology數據集中屬性熵值折線圖

圖4 Credit Approval數據集中屬性熵值折線圖

圖5 Tae數據集中屬性熵值折線圖

從圖3中可以看出，Dermatology數據集的屬性數目較多，且熵值的差異較大，可能是由于該數據集各屬性根據信息量的大小分配的權重比較合理，重要的屬性被分配了較高的權重，導致所提出的聚類算法在該數據集上的準確度較高。從圖4 中可以看出，Credit Approval數據集雖然屬性個數不多，但屬性的權重差異較大，這可能是該數據集準確度提高的原因。從圖5 中可以看出，Tae數據集的屬性數目較少，且熵值的差異在0.15之內，因此，沒有較大發(fā)揮重要屬性的作用，這可能是該數據集準確度沒有明顯提高的原因。

該結果表明所提出的加權單純形映射聚類算法能將分類型屬性數據映射為數值型數據，從而可以將分類型屬性數據與數值型屬性數據統(tǒng)一處理。并且，所提出的加權單純形映射聚類算法可以根據各屬性信息量的大小合理分配權重，尤其在數據集屬性數目較多時表現出較大的優(yōu)勢，對于樣本分布不平均的數據集同樣適用。

5 結束語

本文提出了一種用于混合數據集聚類的融合單純形映射和熵加權的聚類方法。首先，提出單純形向量映射策略，將分類型屬性映射到數值向量，使分類型屬性和數值型屬性可以統(tǒng)一處理。單純形向量映射策略將具有n個分類值的分類型屬性映射到n-1維向量上，使任意兩個分類值間的歐幾里德距離相等。由于不同屬性包含信息量的不同，基于信息熵理論為分類型屬性和數值型屬性分別提出屬性加權策略。然后，結合單純形映射策略和信息熵加權策略設計相似性度量，并應用于K-means 算法框架。最后，在UCI 混合數據集上與傳統(tǒng)映射聚類算法和K-prototype 算法進行了比較。實驗結果表明，本文提出的融合單純形映射和熵加權的聚類方法可以實現更高的聚類準確度，優(yōu)于現有的兩種聚類算法。