基于互信息與貝葉斯信念網(wǎng)絡(luò)的關(guān)系層次距離混合聚類算法

蔡金成，孫浩軍

（汕頭大學(xué)工學(xué)院，廣東 汕頭 515063）

0 引言

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

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

文章第1章介紹相關(guān)概念，包括互信息、貝葉斯信念網(wǎng)絡(luò)、關(guān)系層次距離的相關(guān)概念；第2章是本文算法的過程描述，包括構(gòu)建貝葉斯信念網(wǎng)絡(luò)、關(guān)系層次距離、聚類過程；第3章是實驗及結(jié)果情況；最后總結(jié)本文.

1 相關(guān)概念

1.1 互信息

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

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

在以上兩個式子中，n和m分別是隨機(jī)變量X和Y的離散狀態(tài)的數(shù)量；P（X＝xi，Y＝y(tǒng)j）則是隨機(jī)變量X和Y的聯(lián)合概率分布；隨機(jī)變量X和Y的互信息是對稱的，數(shù)學(xué)上表示為：I（X；Y）＝I（Y；X）.

兩個隨機(jī)變量X與Y的標(biāo)準(zhǔn)互信息（Normalized Mutual Information）定義為NMI（X；Y），其數(shù)學(xué)上定義為：

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

1.2 貝葉斯信念網(wǎng)絡(luò)

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

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

圖1 基于標(biāo)準(zhǔn)互信息構(gòu)建的diagnosis數(shù)據(jù)集的信念網(wǎng)絡(luò)

1.3 關(guān)系層次距離

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

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

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

圖2 屬性UP的概率表組成的層次結(jié)構(gòu)圖

圖3 屬性LP的概率表組成的層次結(jié)構(gòu)圖

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

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

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

W（Ri）表示第i條規(guī)則的權(quán)重；L（Ri，ROOT）表示結(jié)點N1所在的第i條規(guī)則到Root的層數(shù)，每層值為1；L（N2，ROOT）表示不受規(guī)則i所影響的結(jié)點N2到Root的層數(shù)，每層值為1.如圖5，兩個結(jié)點之間的距離為：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的概率表組成的層次結(jié)構(gòu)圖

圖5 屬性TP的概率表組成的層次結(jié)構(gòu)圖

1.4 代價函數(shù)

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

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

定義1兩個向量的數(shù)值型屬性之間的標(biāo)準(zhǔn)化曼哈頓距離的度量如下：

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

定義2分類型數(shù)據(jù)在同一個屬性中的兩種不同狀態(tài)之間的距離的度量如下：

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

定義3兩個向量的分類型屬性之間的標(biāo)準(zhǔn)化關(guān)系層次距離度量如下：

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

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

2 關(guān)系層次距離聚類算法（CRHD）

利用互信息構(gòu)建貝葉斯信念網(wǎng)絡(luò)度量分類型數(shù)據(jù)之間的相似性，利用標(biāo)準(zhǔn)化的曼哈頓距離來度量數(shù)值型數(shù)據(jù)的相似性，通過這兩種相似度的計算來設(shè)計用于混合型數(shù)據(jù)的聚類算法：關(guān)系層次距離聚類算法Clustering for Relation Hierarchies Distance（簡稱CRHD）.CRHD對于分類型屬性的計算是通過標(biāo)準(zhǔn)互信息計算屬性的相關(guān)性來構(gòu)建貝葉斯信念網(wǎng)絡(luò)，并利用貝葉斯信念網(wǎng)絡(luò)構(gòu)建關(guān)系層次距離，通過構(gòu)建關(guān)系層次距離來度量分類型屬性中各個狀態(tài)之間的距離，再根據(jù)公式（10）進(jìn)行標(biāo)準(zhǔn)化處理，而對于數(shù)值型數(shù)據(jù)則采用標(biāo)準(zhǔn)化的曼哈頓距離進(jìn)行度量其距離（公式8），最后結(jié)合分類型屬性與數(shù)值型屬性的距離度量方法（公式11）對整個數(shù)據(jù)集進(jìn)行聚類.

2.1 構(gòu)建貝葉斯信念網(wǎng)絡(luò)

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

1）利用標(biāo)準(zhǔn)互信息來度量分類型屬性之間的相關(guān)性程度；

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

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

4）通過條件概率、K2算法分?jǐn)?shù)評估[13]，再進(jìn)行方向的指派，形成有向無環(huán)圖.

2.2 關(guān)系層次距離的計算

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

（1）對于每個屬性都有貝葉斯信念網(wǎng)絡(luò)計算出來的概率表，包括規(guī)則對應(yīng)的概率表、規(guī)則的權(quán)重；

（2）根據(jù)公式（9）進(jìn)行計算各個屬性中狀態(tài)的距離，作為狀態(tài)間的相似度度量；

（3）根據(jù)公式（10）對分類型屬性的距離進(jìn)行度量.

2.3 聚類算法描述

關(guān)系層次距離聚類算法通過標(biāo)準(zhǔn)互信息對貝葉斯網(wǎng)絡(luò)的構(gòu)建，并利用其相關(guān)性構(gòu)建關(guān)系層次距離，再利用關(guān)系層次距離對分類型屬性進(jìn)行相似度計算并做標(biāo)準(zhǔn)化處理，最后結(jié)合數(shù)值型數(shù)據(jù)的標(biāo)準(zhǔn)化曼哈頓距離的度量進(jìn)行聚類.聚類的過程分成兩個階段：階段一，是通過數(shù)據(jù)相似性計算聚類中心點；階段二，是將剩余元素指派到子簇中心點的過程.

輸入：數(shù)據(jù)集 X＝{X1，X2，…，XN}，簇個數(shù) K

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

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

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

Step1：按比例從數(shù)據(jù)集X中隨機(jī)選擇樣本，記錄其下標(biāo)保存在S中；

Step2：從距離矩陣中距離最大的值對應(yīng)的兩個樣本下標(biāo)，記為p1及p2；

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

Step3：while K＞k：

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

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

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

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

階段二迭代剩下數(shù)據(jù)算法：

Step1：獲取已指派樣本的下標(biāo)，result保存當(dāng)前k個子簇的下標(biāo)；

Step2：獲取剩余的還沒被指派的下標(biāo)列表remainder；

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

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

3 實驗及結(jié)果

3.1 實驗數(shù)據(jù)

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

表1 兩個實驗數(shù)據(jù)集

3.2 評估函數(shù)

對于本文的聚類效果評估采用AC和ARI評估函數(shù)進(jìn)行評估，具體如下：

（1）Accuracy（簡稱 AC）

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

（2）Adjusted Rand index（簡稱 ARI）

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

3.3 結(jié)果及分析

下面分析CRHD算法在上述UCI的兩個數(shù)據(jù)集（diagnosis、covType）的實驗結(jié)果.表2中得出了CRHD算法在數(shù)據(jù)集diagnosis中的準(zhǔn)確率AC和ARI的值指標(biāo).三個算法的準(zhǔn)確率AC和ARI的指標(biāo)如表3和表4所示.

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

表2 CRHD算法在數(shù)據(jù)diagnosis上的實驗結(jié)果

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

表3 評估函數(shù)AC對三個算法在兩個數(shù)據(jù)上的聚類結(jié)果評估的結(jié)果

表4 評估函數(shù)ARI對三個算法在兩個數(shù)據(jù)上的聚類結(jié)果評估的結(jié)果

4 結(jié)束語

在傳統(tǒng)的聚類算法中大多都僅限于處理數(shù)值型數(shù)據(jù)或者分類型數(shù)據(jù).即使存在一些聚類算法是對混合型數(shù)據(jù)進(jìn)行聚類的，但是也存在諸多缺點，如不能保留分類型屬性本身的含義同時在處理過程也消耗大量內(nèi)存或者需要專業(yè)領(lǐng)域知識進(jìn)行概念分層附上層次距離等.本文CRHD算法通過計算屬性之間的互信息來構(gòu)建貝葉斯信念網(wǎng)絡(luò)，通過貝葉斯信念網(wǎng)絡(luò)來構(gòu)建關(guān)系層次結(jié)構(gòu)并附上距離來度量屬性中各個狀態(tài)的相似性，從而解決了以上提到的混合聚類算法中存在的缺點.最后通過采用UCI中的數(shù)據(jù)集進(jìn)行試驗，結(jié)果利用AC和ARI準(zhǔn)確率評估算法進(jìn)行評估，評估結(jié)果較有效，證明了本文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]周志華.機(jī)器學(xué)習(xí)[M].北京：清華大學(xué)出版社，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