基于mRMR的多關系樸素貝葉斯分類

張　晶　畢佳佳　劉　爐

(合肥工業大學計算機與信息學院　安徽 合肥 230009)

?

基于mRMR的多關系樸素貝葉斯分類

張晶畢佳佳*劉爐

(合肥工業大學計算機與信息學院安徽 合肥 230009)

在分類任務中，特征選擇是一種提高分類效果的重要方法?，F實生活中的數據都是存儲在多關系數據庫中的。多關系數據庫的數據中有許多不相關的且冗余的特征，這些特征對分類任務的貢獻很小，甚至沒有貢獻。如何有效地將特征選擇應用到多關系分類中是比較重要的。因此，將最大相關最小冗余的特征選擇方法應用到多關系分類中，對關系數據庫中的每個關系表進行特征選擇，選擇出對分類影響較好的特征集，再用多關系樸素貝葉斯分類算法對進行特征選擇后的多關系數據庫進行分類測試。實驗結果表明了該算法的性能有了一定的提高。

多關系分類特征選擇

0　引　言

二十世紀末到二十一世紀，全球的數據以爆炸式規模急劇增長。例如，到2005年底，已經有了82億的網頁收錄到Google中，中國的百度搜索引擎中的網頁也增加到了10億左右[1]。許多重要的知識內容規律就隱藏在這些數據的背后，人們可以利用這些重要的信息給決策者在進行科學分析時提供重要的依據。雖然，人們可以從這些信息中獲取到了價值，帶來方便，但是也產生了許多問題[2]，如信息真假難辨，安全難以保證，信息過量，難以消化等問題。為了解決這些問題，必須找到一種有效的方法。數據挖掘技術能夠從海量的數據中提取有價值的內容進行分析和理解學習，是一種有效的方法。

在現實生活中，數據基本上都是以二維表的形式存儲在關系數據庫中。每個數據表中都包含著各種對分類有影響的信息。因此，要想從多關系數據庫中提取有價值的信息，就需要利用多關系數據挖掘技術對多關系表中的數據進行分析。多關系分類就是以多個相互聯系的關系表為對象對其挖掘分類。根據前人已有的研究方法中，多關系分類可以總結為以下兩種：一種是利用傳統的分類方法Propositional Learning對多關系數據進行處理。但是傳統的分類算法都是在單個表的基礎上實現的，所以為了處理多關系數據，就需要將多關系數據轉化成單個關系。然而，在轉化過程中容易造成信息丟失[3]，可能會丟失對分類影響比較重要的信息。另一種是結合多關系對傳統的分類方法擴展更新，與傳統的分類方法不同，這種方法不需要將多個關系表轉化成單個關系，便能夠直接處理多關系數據[4-6]。這種方法主要包含兩個方面：一種是基于選擇圖的多關系分類，是從多關系數據挖掘的框架中得出ILP方法，并把表與表之間的關系轉換成直觀的選擇圖，如TILDE[7]、MRDTL[8]；另外一方面是基于元組ID傳播[4]的多關系分類，如CrossMine[9]、Graph-NB[10]、FAFS[11]等。

隨著大型數據庫的建立和機器學習的需要條件，新的問題開始出現了。特征選擇作為機器學習的一個比較重要的預處理步驟，在分類任務中起著重要作用[12]。它根據某一個評價準則從原始特征集中選擇出有效的子集，在之后的數據處理過程中能夠提高處理性能，如分類聚類的性能[13]。在實際的應用中，多關系數據庫的關系中有許多不相關的且冗余的屬性，這些屬性對分類任務的貢獻很小，甚至沒有貢獻。因此，特征選擇是多關系數據挖掘中一個必要的數據處理步驟。通過利用特征選擇方法，我們能夠提高分類的效果以及分類模型的可理解性。

1　多關系數據庫知識

關系數據庫描述了一組實體DB={E1,E2,…,En}以及實體之間的關系。這些實體是由一個目標表和若干個背景表或者非目標表，其定義如下：

定義1在一個關系表R中，若存在一個屬性C，且對于C的每個分量ci都代表著一個實例的類標簽，則把C稱為R的類屬性，由R.C表示。那么具有類屬性的關系R就被稱作目標關系，記為Rt，其余的則稱為非目標表或背景表。

在關系數據庫中，每兩個表之間都能通過連接屬性直接或者間接的相連。由于每一個關系表中都存在著一個主碼，要想使得另一個表與該表直接相連，則在這個表中一定存在著相對應的外碼。對于兩個間接相連的關系表，它們之間是通過外碼與外碼的方式相連。以PKDD CUP99金融數據為例，圖1是其數據庫中各關系的連接結構。在此多關系數據庫中， loan為目標表，其余的七個表則是背景表，背景表根據連接屬性直接或者間接地與目標表相連。

不同于單表結構的簡單性，多關系數據庫的結構設計、關系模式等都是非常復雜的，尤其是關系數據庫中各表之間復雜的關系對分類任務有很大的影響。根據圖1可以看出，每條邊可能會導致許多重復的連接操作，沒有意義的語義關系。

為了能夠簡單明了地表示各關系表之間的關系，我們使用語義關系圖來表示。

定義2語義關系圖SGR是一種有向無環圖SRG(V,E,W),其中，V是對應于數據庫中關系表的頂點集合。E是有向邊，并且每個邊(v，w)代表通過直接連接這兩個表把表w連接到v表上。W是關系表中所有屬性的集合，其中每個屬性連接兩個表。我們把這種屬性稱為連接屬性。

語義關系圖以目標表為起點，表與表之間的連接路徑有兩種：一種是主碼到外碼的連接；另一種是外碼到主碼的連接。總的來說，語義關系圖不僅描述了數據庫中關系表之間的關系，而且使這種關系更加的簡單明了。它的總體形狀類似于數據庫中的ER圖。圖2就是圖1對應的語義關系圖，促進了關系間虛擬連接的過程，就像整個算法的一個流程圖。

圖2　PKDD CUP99金融數據庫的語義關系圖

2　特征選擇

特征選擇的研究始于20世紀60年代初，在對其研究的過程中，通常假設特征與特征之間是相互獨立的。由于當初設計的特征數目比較少，很多操作都憑借人為的經驗來進行的，這樣不僅具有很大的盲目性和局限性，而且花費代價還比較高，所得出來的結果也很不理想。20世紀90年代以來，人們已經進入一個信息化社會化的時代，信息技術的快速發展使得數據規模變得非常龐大，數據的維數也非常大。這使得信息處理的要求越來越高，人為經驗的評價方法已經不能適應大規模數據了。因此，需要找到能夠適應大數據且能夠保證準確率等綜合性能較好的特征選擇方法。為了獲得更好的結果，許多學者基于傳統算法并結合相關領域對特征選擇方法進行了改造，但是由于特征選擇方法本身的多樣性以及處理問題的復雜性，至今還沒有一個固定的選擇模式和有效的方法。

在以往的對特征選擇的研究中，Yang等人[14]通過利用線性最小方差匹配法LLSF，并根據各個特征的取值情況對樣本空間進行學習劃分，其實驗結果驗證了該方法只適用于特征分布平衡的時候，而對于特征分布和類屬性分布不平衡時，分類結果很不理想。Q.H.Hu[15]在信息論的基礎上提出了基于信息熵的混合數據簡約方法。L.Yu等在2003年提出的Fast Correlation Based Filter (FCBF)[16]，該算法結合選擇最優子集和特征相關權重法，來降低特征集之間的冗余性。He Jun等人在2008年提出的Feature and Relation Selection(FARS)[11]是通過關系表的不確定性評價(TSU)評估的。它同時采用特征選擇和關系選擇，有效的選擇了一組小的相關特征集。

以上所描述的各種特征選擇方法考慮到了特征與類標簽的相關度，但忽略了特征之間的冗余度，這樣不僅會降低分類的時間性能，精確度也有可能會降低。因此，本文提出了基于mRMR的多關系樸素貝葉斯分類算法MNB-mRMR。該算法通過利用基于互信息的最大相關最小冗余mRMR[17]的特征選擇算法對多關系數據庫中的多關系表進行特征選擇，在每個關系表中都選擇出對分類幫助最大的特征子集。在如何選擇出最佳特征子集問題上，本文通過計算最大相關度與最小冗余度之間的信息差算子，并根據給定閾值對訓練集進行訓練，訓練出最優子集，最后利用多關系樸素貝葉斯分類算法對選擇后的多關系數據庫進行分類驗證。

3　基于mRMR的多關系樸素貝葉斯分類

3.1相關知識

由于最大相關最小冗余的特征選擇算法是在互信息的基礎上提出的方法，本節將介紹互信息的相關知識。首先介紹信息熵的概念。熵這個術語源于熱力學領域，而香農把熵這個概念引入信息理論中，故又被稱為香農熵[18]。它是衡量信息的一種度量，在信息論的發展歷程中起著非常重大的意義。

(1)

定義4如果(ζ,η)～p(x,y)，那么η關于ζ的條件熵定義為:

(2)

互信息源于信息論，是衡量兩個特征之間關聯度的一個重要標準，其定義如下：

對于兩個隨機變量ζ與η，它們的聯合分布為p(x,y)，邊際分布分別為p(x)和p(y)，那么ζ與η的互信息I(ζ,η)為：

I(ζ,η)=H[p(x,y),p(x)q(y)]

(3)

且互信息與聯合熵、條件熵的關系有:

I(ζ,η)=H(ζ)+H(η)-H(ζ,η)；

I(ζ,η)=H(ζ)+H(ζ|η)；

I(ζ,η)=H(η)+H(η|ζ)。

3.2最大相關與最小冗余

在機器學習與模式識別中，特征選擇的目的是為了尋找最具有代表的特征集以使得分類的錯誤最小化。要得到最小誤差通常需要通過計算類標簽c與子空間Rm的最大統計相關量，就是所謂的最大相關。由于是基于互信息的特征選擇算法，所以首先要解決的問題就是互信息計算，根據3.1節的介紹，對于兩個隨機變量X和Y:

=H(Y)-H(Y|X)

(4)

根據式(1)、式(2)、式(4)就可以得到特征xi與類標簽c的互信息I(xi,c)，即特征與類標簽的相關度。最大相關則是選出滿足下面等式的特征的方法:

(5)

依據式(4)和式(5)便可以實現最大相關。最大相關最小冗余算法就是對于給定的原始特征集，依據最大相關最小冗余準則對原始特征集X中的特征與類標簽之間的互信息大小進行排序并把結果放入目標集R。

將最大相關與最小冗余結合起來就是所謂的“最大最小冗余準則”，于是便產生如下算子maxΦ(D,R),Φ=D-R，即信息差(MID)算子▽MID。其中Φ(D,R)用來表示D和R的聯合關系。現在把最大相關最小冗余準則問題轉化為了最大化信息差算子▽MID的問題，假設S中已經包含了m-1個特征，那么S的第m個特征就是那個能使下面算子最大的那個特征:

(6)

即mRMR特征選擇問題轉化為了計算信息差算子▽MID的問題。因此，利用mRMR算法進行特征選擇的過程就是依據▽MID的大小來對各個特征進行排序然后進行篩選的過程。

由于在多關系數據庫中，只有目標表有類標簽，而非目標表中沒有類標簽，要想計算非目標表中特征的互信息以及信息差算子▽MID，必須利用元組ID傳播技術[9]。通過這種虛擬連接技術，元組IDs以及類標簽才能從目標表傳遞到非目標表中。在計算出每個關系表中特征的最大相關最小冗余的信息差算子▽MID之后，根據信息差算子對每個關系表的特征進行選擇，選擇出最終用于分類的最優特征集。這些選擇出來的特征集被用于多關系樸素貝葉斯分類。

3.3多關系樸素貝葉斯分類

樸素貝葉斯是利用統計學中的貝葉斯定理來對樣本進行分類的一種簡單概率的分類方法。它的原理簡單，易于理解。其思想基礎是對于一個待分類的樣本，通過計算它屬于各個類別的概率值來確定概率值最大的那個類別就是該樣本的最終類別。貝葉斯分類應用非常廣泛，可應用到各種領域，如對垃圾郵件的過濾[19]、人臉識別[20]等。起初，樸素貝葉斯分類只應用于單表數據，后來被擴展到直接處理多個關系表。

對于多關系的樸素貝葉斯，假設t是目標表，s則是與其相連的另外一個關系表，對于表t中的一個元組x：X=(x1,x2,…,xn)，s中有p個元組能夠與x相連接。這些p個元組是(yk1,yk2,…,ykp)，其中每個元組ykl由r個值表示：ykl=(ykl1,ykl2,…,yklr)，然后，元組x的類標簽的計算如下：

CMAP=argmaxci∈CP(ci|X)

=argmaxci∈Cp(ci)p(x1,…,xn,yk11,…,yk1r,…,ykp1,…,ykpr|ci)

(7)

3.4MNB-mRMR算法描述

本節將對基于最大相關最小冗余的多關系樸素貝葉斯分類算法MNB-mRMR進行詳細的描述。首先給出該算法中所涉及的一些符號和函數的意義及功能：D表示的是關系數據庫；Rt表示目標表，Ri表示其他關系表即非目標表；集合S是空集，用來存放所選的最優特征集；μ表示的是給定的有關信息差算子▽MID的閾值；CreateRelationGraph(G)函數的功能是根據多關系數據庫的連接關系構建語義關系圖，該語義關系圖使得這些多關系表之間的關系更加清楚明了。Propagate(Ri,Rt)函數表示將目標表中的類標簽和ID傳遞到非目標表中以便對非目標表中的特征進行評估。SRi表示關系表Ri最終所選的特征集。

MNB-mRMR算法的具體描述如下：

算法: MNB-mRMR

輸入：目標表Rt，其它關系表Ri(i=1, 2,…,n)，集合S，閾值μ

輸出：SRi，每個關系表所選的特征集

step1: CreateRelationGraph (G)；

step 2: Propagate (Ri, Rt)；

step3:

a) 對于每個關系表Ri，根據式(4)計算每個特征與類標簽的互信；

b) 將具有最大互信息值的特征加入S中；

c) 根據式(4)和式(6)計算其余特征的信息差算子▽MID；

d) 根據每個特征的▽MID值與給定閾值μ刪除小于μ的特征，得到SRi；

step 4: 利用多關系樸素貝葉斯分類算法對最終進行特征選擇后的關系表進行分類驗證。

本文利用mRMR進行特征選擇的過程轉化成了根據特征信息差算子的大小進行篩選的過程。在step3中，首先計算各個特征與類標簽之間的互信息，代表了各個特征與類標簽之間的相關度。而我們的目標是為了得到相關度高且冗余性小的特征集，因此，首先將關系表中與類標簽互信息最大的那個特征加入空集S中，在計算加入其余特征時計算該特征的信息差算子，之后根據最大相關與最小冗余的信息差算子的大小與給定閾值大小，刪除小于給定閾值的特征，將大于閾值的特征加入集合S中。最后利用多關系樸素貝葉斯分類算法進行測試驗證。

4　實驗結果與分析

為了驗證MNB-mRMR算法的有效性，實驗是在windows XP操作系統完成的，CPU是Intel(R) Core(TM)2 Duo E75000 2.93 GHz，內存是1.96 GB。開發環境為Java平臺，編譯運行環境是jdk1.6。數據存儲工具使用的是Mysql數據庫。數據集使用的是PKDD CUP 99金融數據集，該金融數據庫是多關系挖掘中常使用的數據集，能夠有效地對算法進行實驗驗證。數據集共有幾百萬條記錄，共包含8個關系表，一個目標表loan，具有是否貸款的類標簽，另外7個表示輔助表，與目標表直接或者間接相連。

4.1閾值設定

在本節中，主要討論實驗室中所涉及的參數設置問題。本節中所要討論的參數是特征的最大相關與最小冗余的信息差算子μ，因為在MNB-mRMR算法中，需要根據最大相關與最小冗余的信息差算子的大小與給定閾值μ的大小，刪除小于給定閾值的特征。為了選出最優特征集以得到高的分類精確度，本文通過手動設定不同閾值，選擇那些信息差算子▽MID大于給定閾值的特征集。對于不同的閾值，整個算法的分類準確率和時間性能也會有不同。圖3表示了在信息差算子μ取不同的值時，該算法的分類精確度的變化。該分類精確度基本上處于一個先上升后下降的趨勢，并在μ=-0.01左右，分類精確度最高。因此，在本文的實驗中，我們選取-0.01作為信息差算子的閾值，根據各個特征的信息差算子的值選出大于-0.01的特征集。

圖3　不同μ值下的分類準確率的比較

4.2分類性能比較

為了驗證MNB-mRMR算法的有效性，本文將該算法與TILDE算法、Graph-NB算法進行了比較，實驗結果如表1所示。在表1中，可以看出MNB-mRMR算法相較于TILDE算法、Graph-NB算法以及FARS算法，分類準確率都要高。MNB-mRMR算法既考慮到特征與類標簽的相關度，又考慮到特征與特征之間的冗余度，將這兩者結合起來能更充分、更準確地評估特征。因此，MNB-mRMR算法在分類準確度上會高于另外三種分類算法。

表1　PKDD CUP 99的準確率

5　結　語

本文提出了基于mRMR的多關系樸素貝葉斯分類算法。特征選擇一直是提高分類效果的有效方法，本文中將基于互信息的最大相關最小冗余的特征選擇方法應用到多關系分類中，剔除了與類標簽不相關且冗余度高的特征，選出了最優特征集。在選擇最優特征集的過程中，根據特征的最大相關最小冗余的信息差算子的大小進行選擇，該信息差算子綜合了特征的最大相關度與最小冗余度，能夠有效地表示該特征對分類效果的影響力。根據給定的信息差算子的閾值，反復實驗訓練，訓練出分類效果最好的特征集。最后用多關系樸素貝葉斯分類算法進行了驗證。該方法主要解決了不相關特征與冗余的特征對分類任務產生不好影響的問題。實驗結果表明了該算法提高了分類精確度且加強了分類模型的可理解性。

[1] 鄧彩鳳.中文文本分類中的互信息特征選擇方法研究[D]. 重慶:西南大學，2011.

[2] 劉海燕. 基于信息論的特征選擇算法研究[D]. 上海:復旦大學，2012.

[3] Horvath T, Wrobel S, Bohnebeck U. Relational instance-based learning with lists and terms[J]. Machine Learning, 2001,43(1-2):53-80.

[4] Kramer S, Lavrac N, Flach P. Propositionalization approaches to relational data mining[M]. Germany: Springer-Verlag, 2001:262-291.

[5] Taskar B, Segal E, Koller D. Probabilistic classification and clustering in relational data[C]//Proceedings of 17th International Joint Conference on Artificial Intelligence, San Francisco, 2001:870-876.

[6] Neville J, Jensen D, Friedl, et al. Learning relational probability trees[C]//Proceedings of the ninth ACM STGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2002:625-630.

[7] Blockeel H, Raedt L De. Top-down induction of first logical decision trees[C]//Proceedings of 1998 International Conference of Machine Learning (ICML’98), Essex, 1998:285-297.

[8] Leiva H A, Gadia S. MRDTL: a multi-relational decision tree learning algorithm[C]//Proceedings of the 13th International Conference on Inductive Logic Programming, Springer, 2002:38-56.

[9] Yin Xiaoxin, Han Jiawei, Yang Jiong, et al. CrossMine: Efficient classification across multiple data relations[C]//Proceedings 2004 International Conference on Data Engineering (ICDE’04), Heidelberg, 2004:172-195.

[10] Liu Hongyan, Yin Xiaoxin, Han Jiawei. An efficient multi-relational naive Bayesian classifier based on semantic relationship graph[C]//Proceedings of the 4th International Workshop on Multi-Relational Data Mining, Chicago, 2005:68-76.

[11] He Jun, Liu Hongyan, Hu Bo, et al. Selecting effective features and relations for efficient multi-relational classification[J]. Computational Intelligence, 2010, 26(3):258-280.

[12] Ouardighi A, Akadi A, Aboutajdine D. Feature selection on supervised classification using Wilk’s Lambda statistic[C]//Proceedings of 2007 Computational Intelligence and Intelligent Informatics (ISCIII’07), Agadir, 2007:51-55.

[13] Sha C, Qiu X, Zhou A. Feature selection based on a new dependency measure[C]//Proceedings of 2008 International Conference on Fuzzy Systems and Knowledge Discovery (FSKD’08), Shandong, 2008:266-270.

[14] Yang Y, Pedersen J O. A comparative study on feature selection in text categorization[C]//Proceedings of 14th International Conference on Machine Learning, Nashville, US, 1997,26(1):15-39.

[15] Hu Qinghua, Yu Daren, Xie Zongxia. Information-preserving hybrid data reduction based on fuzzy-rough techniques[J]. Pattern Recognition Letters, 2006,27(5):414-423.

[16] Yu L, Liu H. Feature selection for high-dimensional data: A fast correlation based filter solution[C]//Proceedings of 12th International Conference on Machine Learning (ICML-03), Washington, 2003:856-863.

[17] Peng H, Long F, Ding C. Feature selection based on mutual information: criteria of max-dependency, max-relevance, and min-redundancy[J]. IEEE transactions on pattern analysis and machine intelligence, 2005,27(8):1226-1238.

[18] 沈世鎰, 陳魯生. 信息論與編碼理論[M]. 北京: 科學出版社, 2005:18-31.

[19] 惠孛, 吳躍. 基于全局的即時垃圾郵件過濾模型的研究[J]. 電子測量與儀器學報,2009, 23(5):46-51.

[20] Ouarda W, Trichili H. Combined Local Features Selection for Face Recognition Based on Naive Bayesian Classification[C]//Proceedings of 2013 International Conference on Hybrid Intelligent Systems (HIS’13), Gammarth, 2013:240-245.

MULTI-RELATIONAL NAIVE BAYESIAN CLASSIFICATION BASED ON MRMR

Zhang JingBi Jiajia*Liu Lu

(SchoolofComputerandInformation,HefeiUniversityofTechnology,Hefei230009，Anhui,China)

In classification task, feature selection is an important method to improve classification effect. In real life, data is stored in multiple relational databases. There are many irrelevant and redundant features in multiple relational database, and they have little or even no contribution to classification task. How to effectively apply the feature selection to multi-relational classification is rather important. Therefore, we applied the feature selection method of maximum relevance minimum redundancy to multi-relation classification, the feature selection is carried out on every relation table in database and to pick out the feature sets with better effect on classification. Then, we used the multi-relational naive Bayesian classification algorithm to classifying and testing the multi-relational database with the features selected. Experimental results also showed that the performance of the algorithm has been improved.

Multi-relationalClassificationFeature selection

2015-03-14。國家自然科學基金項目(61273292，6130 5063)。張晶，副教授，主研領域：數據挖掘，人工智能。畢佳佳，碩士生。劉爐，碩士生。

TP311

A

10.3969/j.issn.1000-386x.2016.08.013