基于互信息與貝葉斯信念網絡的關系層次距離混合聚類算法

蔡金成，孫浩軍

（汕頭大學工學院，廣東 汕頭 515063）

0 引言

聚類被廣泛應用于計算數據之間的相似性并通過其相似性將數據區分和分類，期間被劃分在同一組的數據相似性強，而劃分在不同組之間的數據相似性弱，這是一種沒有先驗知識指導的分類過程，屬于無監督的分類[1-2].在聚類中，很多算法只針對單一的分類型屬性[3-4]或者單一的數值性屬性[5-6]，然而數據在實際應用中不僅包含數值型屬性，同時包括類似顏色、幾何紋理等分類型屬性，而針對這種混合型數據的算法很少，主要原因是難以精確度量分類型數據之間的相似性.對于度量分類型數據相似性也有一些算法，但都存在著局限性與不足，如在文獻[7]中，通過將分類型數據轉換成為二進制數值，然后利用簡單的距離度量（如，歐氏距離等），并結合數值型屬性，統一按照數值型屬性進行聚類.然而在很多情況下會導致分類型屬性語義的丟失.另一些研究者通過對分類型數據進行概念分層[2]，以及在分層附上距離形成層次距離[8]來度量分類型數據之間的相似性[9].然而，概念分層需要專業的領域知識來分層，而且很多情況下分類型數據并沒有層次的概念（如，顏色、圖案等）.

這里我們提出一種基于互信息與貝葉斯信念網絡的方法來度量分類型數據之間的相似性，并結合標準化的曼哈頓距離來度量數值型數據的相似性，設計用于混合型數據的聚類算法，其主要思路是，對于分類型屬性，利用互信息構建貝葉斯信念網絡，利用貝葉斯信念網絡構建關系層次，繼而為層次附上距離，形成關系層次距離，而對于數值型屬性則利用標準化的曼哈頓距離來度量其相似性，最后結合分類型屬性與數值型屬性來對整個數據集進行相似性的度量，利用相似性聚類.我們通過UCI中的多個數據集進行仿真實驗，可以得到較好的聚類效果.

文章第1章介紹相關概念，包括互信息、貝葉斯信念網絡、關系層次距離的相關概念；第2章是本文算法的過程描述，包括構建貝葉斯信念網絡、關系層次距離、聚類過程；第3章是實驗及結果情況；最后總結本文.

1 相關概念

1.1 互信息

在概率論中，兩個隨機變量的互信息（Mutual Information）是變量間相互依賴性的量度.對于兩個隨機變量X與Y之間的互信息定義為I（X；Y），在數學上定義為：

其中H（X）是隨機變量X的信息熵，是給定隨機變量Y，X的條件信息熵.隨機變量的信息熵和條件信息熵在數學上分別定義為：

在以上兩個式子中，n和m分別是隨機變量X和Y的離散狀態的數量；P（X＝xi，Y＝yj）則是隨機變量X和Y的聯合概率分布；隨機變量X和Y的互信息是對稱的，數學上表示為：I（X；Y）＝I（Y；X）.

兩個隨機變量X與Y的標準互信息（Normalized Mutual Information）定義為NMI（X；Y），其數學上定義為：

隨機變量的標準互信息是對隨機變量的互信息的歸一化.隨機變量的互信息既可以表示為（1）式，同時由于其對稱性，也可以表示為 I（X；Y）＝H（X）+H（Y）-H（X，Y）.因此，當X與Y完全一樣時，I（X；Y）取得最大值為1，此時，H（X）＝H（Y）且其值為1，H（X，Y）值為 0，則 NMI（X；Y）取得最大值為 1.當 X 與 Y 完全不一樣時，I（X；Y）取得最小值為0，則NMI（X；Y）取得最小值為0，綜上所述NMI（X；Y）的取值范圍為[0，1].

1.2 貝葉斯信念網絡

貝葉斯信念網絡（Bayesian Belief Network）借助有向無環圖（Directed Acyclic graph，簡稱DAG）來描述屬性之間的依賴關系，并使用條件概率表（Conditional Probability Table，簡稱CPT）來描述屬性的聯合概率分布[10].

具體來說，一個貝葉斯信念網絡B由結構G和參數θ兩部分構成，即B＝＜G，θ＞，結構G是一個有向無環圖，每一個節點對應一個屬性，若兩個屬性有著直接的依賴關系，則它們由一條邊連接起來；參數θ定量描述了這種依賴關系.假設屬性ai在G中的父節點集為則θ包含了每個屬性的條件概率表下面我們就UCI中的diagnosis數據集[12]通過標準互信息構建貝葉斯網絡[13]，如圖1所示，其中TP屬性的四個狀態（P、W、G、N）是離散化的結果.

圖1 基于標準互信息構建的diagnosis數據集的信念網絡

1.3 關系層次距離

層次距離[8]是在概念分層[2]的基礎上擴展的，層次距離與概念分層相似，都是通過概念將不同的物體抽象成不同的層次，每個物體就是一個結點，并且通過邊連接起來.層次越高則物體的概念更加抽象，層次越底物體的概念越具體.此外，每個結點連接的邊都用一個權值表示距離.本文提出一種關系層次距離來度量分類型屬性之間的距離，即通過標準互信息構建貝葉斯信念網絡，再通過貝葉斯信念網絡構建關系層次結構，并對關系層次附上距離.圖2（屬性Urine pushing），圖3（屬性Lumbar pain），圖4（屬性Burning of urethra），圖5（屬性Temperature of patient）分別為圖1中每個屬性不同狀態的概率層次結構，而對于關系層次距離的定義分為多種情況，具體如下.

（1）如果所有結點間都只由一條規則（Rule）所影響，則該規則所影響的結點之間的關系距離定義為：

其中，N1表示結點，P（N1）表示在貝葉斯信念網絡中形成的概率表中在規則的影響下的結點N1概率，如圖2和圖3.其中圖2中兩個結點之間的距離為：d2（N1，N2）＝（1-0.67）+（1-0.33）＝1

圖2 屬性UP的概率表組成的層次結構圖

圖3 屬性LP的概率表組成的層次結構圖

（2）如果結點與結點間存在多條規則且每條規則都影響著屬性的所有狀態，則需要根據規則的影響能力來計算結點間的距離，并且按照路徑最短距離來計算（即計算路徑不需要經過ROOT），

W（Ri）表示第i條規則的權重.如圖4，兩個結點之間的距離為：d4（N1，N2）＝0.33*{[1-0.01]+[1-0.99]}+0.67*{[1-0.67]+[1-0.33]}＝1.

（3）如果結點與結點間存在多條規則且某些規則只影響了部分結點，則對于結點與結點之間的距離定義如下：

W（Ri）表示第i條規則的權重；L（Ri，ROOT）表示結點N1所在的第i條規則到Root的層數，每層值為1；L（N2，ROOT）表示不受規則i所影響的結點N2到Root的層數，每層值為1.如圖5，兩個結點之間的距離為：d5（P，G）＝0.25*{[1-0.67]+1+2}+0.17*{[1-0.23]+1+2}+0.33*{[1-0.50]+1+2}+0.25*{[1-0.33]+1+2}＝3.55

圖4 屬性BU的概率表組成的層次結構圖

圖5 屬性TP的概率表組成的層次結構圖

1.4 代價函數

代價函數表示的是對象間的相似程度.本文算法CRHD是混合聚類算法，因此是包含數值型屬性和分類型屬性的混合代價函數.

假設 X＝{X1，X2，…，XN}是包含 N 個數據元素的數據集；Xi＝{Xi1，Xi2，…，XiD}是一個包含D維的數據元素；Xnr是隨機變量的第r個數值型屬性，r＝1，…，p；Xcs是隨機變量的第s個分類型屬性，s＝1，…，q，并且p+q＝D.我們將數據集X分割成K個不相交的簇中，形成C1，…，Ck，其中K是提前先給定的.

定義1兩個向量的數值型屬性之間的標準化曼哈頓距離的度量如下：

其中表示第i個數據元素的第r個數值型屬性的值，n表示數值型數據；表示數據集的第r個數值型屬性中的最大值.

定義2分類型數據在同一個屬性中的兩種不同狀態之間的距離的度量如下：

式子（9-1）的使用條件是所有結點間都只由一條規則所影響；式子（9-2）的使用條件是結點與結點間存在多條規則且每條規則都影響著屬性的所有狀態；式子（9-3）的使用條件是結點與結點間存在多條規則且某些規則只影響了部分結點.其中P（N1）、P（N2）表示在某條規則影響下的概率；W（Ri）表示第i條規則的權重；L（Ri，ROOT）表示第i條規則到ROOT的層數，每層距離值為1；L（N2，ROOT）表示結點N2到ROOT的層數，每層距離值為1.

定義3兩個向量的分類型屬性之間的標準化關系層次距離度量如下：

其中max（d（Nis，Njs））表示在數據集的第s個屬性中不同狀態兩兩之間的距離的最大值；d（Nis，Njs）見公式（9）中的定義.

定義4兩個向量間的距離度量如下：

2 關系層次距離聚類算法（CRHD）

利用互信息構建貝葉斯信念網絡度量分類型數據之間的相似性，利用標準化的曼哈頓距離來度量數值型數據的相似性，通過這兩種相似度的計算來設計用于混合型數據的聚類算法：關系層次距離聚類算法Clustering for Relation Hierarchies Distance（簡稱CRHD）.CRHD對于分類型屬性的計算是通過標準互信息計算屬性的相關性來構建貝葉斯信念網絡，并利用貝葉斯信念網絡構建關系層次距離，通過構建關系層次距離來度量分類型屬性中各個狀態之間的距離，再根據公式（10）進行標準化處理，而對于數值型數據則采用標準化的曼哈頓距離進行度量其距離（公式8），最后結合分類型屬性與數值型屬性的距離度量方法（公式11）對整個數據集進行聚類.

2.1 構建貝葉斯信念網絡

貝葉斯信念網絡借助有向無環圖來描述屬性之間的依賴關系，使用條件概率表來描述屬性的聯合概率分布.貝葉斯信念網絡構建的主要步驟是構建無向圖，再通過剪枝形成無環圖，最后指派方向，其基本步驟如下：

1）利用標準互信息來度量分類型屬性之間的相關性程度；

2）對相關性程度在閾值范圍內的屬性用邊連接起來，形成無向圖；

3）對存在三角環的屬性利用維分割[14]和條件概率進行剪枝，形成無環連通圖或存在大于三結點的有環連通圖；

4）通過條件概率、K2算法分數評估[13]，再進行方向的指派，形成有向無環圖.

2.2 關系層次距離的計算

對于關系層次距離的定義，不同屬性有著不同的定義方式，主要跟屬性與屬性之間的關系有關，其主要的計算步驟如下：

（1）對于每個屬性都有貝葉斯信念網絡計算出來的概率表，包括規則對應的概率表、規則的權重；

（2）根據公式（9）進行計算各個屬性中狀態的距離，作為狀態間的相似度度量；

（3）根據公式（10）對分類型屬性的距離進行度量.

2.3 聚類算法描述

關系層次距離聚類算法通過標準互信息對貝葉斯網絡的構建，并利用其相關性構建關系層次距離，再利用關系層次距離對分類型屬性進行相似度計算并做標準化處理，最后結合數值型數據的標準化曼哈頓距離的度量進行聚類.聚類的過程分成兩個階段：階段一，是通過數據相似性計算聚類中心點；階段二，是將剩余元素指派到子簇中心點的過程.

輸入：數據集 X＝{X1，X2，…，XN}，簇個數 K

輸出：聚類結果 C＝{C1，C2，…CK}

階段一得到聚類中心點算法：

Step0：利用公式（8）、（9）、（10）計算數據集X中數據兩兩之間的距離矩陣；

Step1：按比例從數據集X中隨機選擇樣本，記錄其下標保存在S中；

Step2：從距離矩陣中距離最大的值對應的兩個樣本下標，記為p1及p2；

Step3：將p1及p2插入到result中，從S中刪除這兩個下標，并記k＝2；

Step3：while K＞k：

Step3-0：得到S中剩下的所有樣本與p1p2的距離矩陣；

Step3-1：從step3-0得到S中未分配的每個樣本，分別取與p1p2的最小距離的值；

Step3-2：從step3-1中所有距離最小的值中選取距離最大的值，并得到其下標，記為Pcount；

Step3-3：從X中刪除Pcount，并將Pcount作為第k個子簇的中心點，k＝k+1；

階段二迭代剩下數據算法：

Step1：獲取已指派樣本的下標，result保存當前k個子簇的下標；

Step2：獲取剩余的還沒被指派的下標列表remainder；

Step3：對于每個 remainder里面的每個樣本，利用公式（8）（9）（10）（11）計算它與當前每個子簇的相似度；

Step4：將每個remainder里面的每個樣本逐一分配給與當前子簇相似度最大的簇中；

3 實驗及結果

3.1 實驗數據

實驗數據采用UCI機器學習庫[15]中的兩個數據集（diagnosis、covType）做為實驗數據，表1是數據集的詳細描述，數據庫中有它們自己的分類，用于最后評價聚類的性能的參考.

表1 兩個實驗數據集

3.2 評估函數

對于本文的聚類效果評估采用AC和ARI評估函數進行評估，具體如下：

（1）Accuracy（簡稱 AC）

其中是數據集X的數據個數，K是測試數據集的類的個數，是表示第i的類中屬于同一類的對象最多的數據個數.

（2）Adjusted Rand index（簡稱 ARI）

給定 n 個對象的數據集，假設 U＝{u1，u2，…，us}和 V＝{v1，v2，…，vt}分別表示數據集的原始類分布以及算法聚類結果分布，nij表示同時在類ui和簇vi，然后Ui和Vi分別表示在類ui和類vi數據對象個數，則ARI計算如下：

3.3 結果及分析

下面分析CRHD算法在上述UCI的兩個數據集（diagnosis、covType）的實驗結果.表2中得出了CRHD算法在數據集diagnosis中的準確率AC和ARI的值指標.三個算法的準確率AC和ARI的指標如表3和表4所示.

數據集diagnosis包含了120個數據對象，有兩個類，域值都為{YES、NO}，即該數據集的分類閾值有四個{（NO、NO）、（NO、YES）、（YES、NO）、（YES、YES）}.如表2所示，CRHD可以在類（NO、NO）、（YES、YES）獲得比較好的結果.在其他兩個類分值也有較好的結果，其準確度AC為0.8333，ARI值為0.6341.

表2 CRHD算法在數據diagnosis上的實驗結果

如表3和表4可以看出通過三種算法對兩個數據（其中covType按比例選取1 645個數據）進行試驗.CRHD算法在兩個數據集的ARI評估上優于其他兩種（K-prototype、ROCK）算法，在數據集diagnosis上CRHD算法的AC準確率評估優于其他兩種算法，但在數據集covType上算法ROCK準確率AC優于其他算法，總而言之，本文提出的CRHD算法能夠獲得較好的效率和準確率.但是本算法CRHD也存在兩點不足：其一，CRHD算法在構建貝葉斯網絡時存在局限性，貝葉斯網絡的構建要求屬性之間存在相關性；其二，在高維數據集中構建貝葉斯信念網絡也存在較高的難度.

表3 評估函數AC對三個算法在兩個數據上的聚類結果評估的結果

表4 評估函數ARI對三個算法在兩個數據上的聚類結果評估的結果

4 結束語

在傳統的聚類算法中大多都僅限于處理數值型數據或者分類型數據.即使存在一些聚類算法是對混合型數據進行聚類的，但是也存在諸多缺點，如不能保留分類型屬性本身的含義同時在處理過程也消耗大量內存或者需要專業領域知識進行概念分層附上層次距離等.本文CRHD算法通過計算屬性之間的互信息來構建貝葉斯信念網絡，通過貝葉斯信念網絡來構建關系層次結構并附上距離來度量屬性中各個狀態的相似性，從而解決了以上提到的混合聚類算法中存在的缺點.最后通過采用UCI中的數據集進行試驗，結果利用AC和ARI準確率評估算法進行評估，評估結果較有效，證明了本文CRHD算法的廣泛性和有效性.

[1]DUNHAM M H.Data mining-introductory and advanced topics[M].New Jersey：Prentice-Hall，2003.

[2]HAN J，KAMBER M.Data mining concepts and techniques[M].San Francisco：Morgan Kaufmann，2001.

[3]BARBARA D，COUTO J，LI Y.COOLCAT：An entropy-based algorithm for categorical clustering[C/OL].Proceedings of the Eleventh International Conference on Information and Knowledge Management.2002：582-589[2018-02-20].https://cs.gmu.edu/～dbarbara/COOLCAT/coolcat.pdf

[4]GANTIV，GEHRKE J，RAMAKRISHNAN R.CACTUS clustering categorical data using summaries[C/OL].Proceedings of the ACMSIGKDD，International Conference on Knowledge Discovery and Data Mining，1999：113-120[2018-02-20].http://www.cs.cornell.edu/johannes/papers/1999/kdd1999-cactus.pdf

[5]JAINAK，DUBES R C.Algorithms for clustering data Englewood Cliffs[M].New Jersey： Prentice-Hall，1988.

[6]MACQUEEN J B.Some methods for classification and analysis of multivariate observations[C/OL].Proceedings of the 5th Berkeley Ymposium on Mathematical Statistics and Probability 1967：281-297[2018-02-20].http://citeseer.ist.psu.edu/viewdoc/download；jsessionid=E20C2D397F6BD55732573CDD 9C33575A?doi=10.1.1.308.8619&rep=rep1&type=pdf

[7]GUHA S，RASTOGI R，SHIM K.ROCK：A robust clustering algorithm for categorical attributes[C/OL].Proceedings of the 15thInternational Conference on Data Engineering.1999[2018-02-20].http://theory.stanford.edu/～sudipto/mypapers/categorical.pdf

[8]HSUCC.Generalizing self-organizing map for categorical data[J].IEEE Transactions on NeuralNetworks，2006，17（2）：294-304.

[9]HSU C C，CHEN Y C.Mining of mixed data with application to catalog marketing[J].Expert Systems with Applications，2007，32（1）：12-23.

[10]JENSEN F.An introduction to bayesian networks[M].London：UCL Press，1996.

[11]周志華.機器學習[M].北京：清華大學出版社，2016.

[12]UC irvine machine learning repository[DB/OL].[2018-02-20].http://archive.ics.uci.edu/ml/datasets/Acute+Inflammations

[13]CHEN X W，ANANTHA G，LIN X.Improving bayesian network structure learning with mutual information-based node ordering in the K2 Algorithm[J].IEEE Transactions on Knowledge&Data Engineering，2008，20（5）：628-640.

[14]BUTZ C J，YAN W，MADSEN A L.d-Separation：strong completeness of semantics in bayesian network inference[M]//Advances in Artificial Intelligence.Springer Berlin Heidelberg，2013：13-24.

[15]UC Irvine Machine Learning Repository[DB/OL].[2018-02-20].http://archive.ics.uci.edu/ml/index.php