基于mRMR的多關(guān)系樸素貝葉斯分類(lèi)

張　晶　畢佳佳　劉　爐

(合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院　安徽 合肥 230009)

?

基于mRMR的多關(guān)系樸素貝葉斯分類(lèi)

張晶畢佳佳*劉爐

(合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院安徽 合肥 230009)

在分類(lèi)任務(wù)中，特征選擇是一種提高分類(lèi)效果的重要方法?，F(xiàn)實(shí)生活中的數(shù)據(jù)都是存儲(chǔ)在多關(guān)系數(shù)據(jù)庫(kù)中的。多關(guān)系數(shù)據(jù)庫(kù)的數(shù)據(jù)中有許多不相關(guān)的且冗余的特征，這些特征對(duì)分類(lèi)任務(wù)的貢獻(xiàn)很小，甚至沒(méi)有貢獻(xiàn)。如何有效地將特征選擇應(yīng)用到多關(guān)系分類(lèi)中是比較重要的。因此，將最大相關(guān)最小冗余的特征選擇方法應(yīng)用到多關(guān)系分類(lèi)中，對(duì)關(guān)系數(shù)據(jù)庫(kù)中的每個(gè)關(guān)系表進(jìn)行特征選擇，選擇出對(duì)分類(lèi)影響較好的特征集，再用多關(guān)系樸素貝葉斯分類(lèi)算法對(duì)進(jìn)行特征選擇后的多關(guān)系數(shù)據(jù)庫(kù)進(jìn)行分類(lèi)測(cè)試。實(shí)驗(yàn)結(jié)果表明了該算法的性能有了一定的提高。

多關(guān)系分類(lèi)特征選擇

0　引　言

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

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

隨著大型數(shù)據(jù)庫(kù)的建立和機(jī)器學(xué)習(xí)的需要條件，新的問(wèn)題開(kāi)始出現(xiàn)了。特征選擇作為機(jī)器學(xué)習(xí)的一個(gè)比較重要的預(yù)處理步驟，在分類(lèi)任務(wù)中起著重要作用[12]。它根據(jù)某一個(gè)評(píng)價(jià)準(zhǔn)則從原始特征集中選擇出有效的子集，在之后的數(shù)據(jù)處理過(guò)程中能夠提高處理性能，如分類(lèi)聚類(lèi)的性能[13]。在實(shí)際的應(yīng)用中，多關(guān)系數(shù)據(jù)庫(kù)的關(guān)系中有許多不相關(guān)的且冗余的屬性，這些屬性對(duì)分類(lèi)任務(wù)的貢獻(xiàn)很小，甚至沒(méi)有貢獻(xiàn)。因此，特征選擇是多關(guān)系數(shù)據(jù)挖掘中一個(gè)必要的數(shù)據(jù)處理步驟。通過(guò)利用特征選擇方法，我們能夠提高分類(lèi)的效果以及分類(lèi)模型的可理解性。

1　多關(guān)系數(shù)據(jù)庫(kù)知識(shí)

關(guān)系數(shù)據(jù)庫(kù)描述了一組實(shí)體DB={E1,E2,…,En}以及實(shí)體之間的關(guān)系。這些實(shí)體是由一個(gè)目標(biāo)表和若干個(gè)背景表或者非目標(biāo)表，其定義如下：

定義1在一個(gè)關(guān)系表R中，若存在一個(gè)屬性C，且對(duì)于C的每個(gè)分量ci都代表著一個(gè)實(shí)例的類(lèi)標(biāo)簽，則把C稱(chēng)為R的類(lèi)屬性，由R.C表示。那么具有類(lèi)屬性的關(guān)系R就被稱(chēng)作目標(biāo)關(guān)系，記為Rt，其余的則稱(chēng)為非目標(biāo)表或背景表。

在關(guān)系數(shù)據(jù)庫(kù)中，每?jī)蓚€(gè)表之間都能通過(guò)連接屬性直接或者間接的相連。由于每一個(gè)關(guān)系表中都存在著一個(gè)主碼，要想使得另一個(gè)表與該表直接相連，則在這個(gè)表中一定存在著相對(duì)應(yīng)的外碼。對(duì)于兩個(gè)間接相連的關(guān)系表，它們之間是通過(guò)外碼與外碼的方式相連。以PKDD CUP99金融數(shù)據(jù)為例，圖1是其數(shù)據(jù)庫(kù)中各關(guān)系的連接結(jié)構(gòu)。在此多關(guān)系數(shù)據(jù)庫(kù)中， loan為目標(biāo)表，其余的七個(gè)表則是背景表，背景表根據(jù)連接屬性直接或者間接地與目標(biāo)表相連。

不同于單表結(jié)構(gòu)的簡(jiǎn)單性，多關(guān)系數(shù)據(jù)庫(kù)的結(jié)構(gòu)設(shè)計(jì)、關(guān)系模式等都是非常復(fù)雜的，尤其是關(guān)系數(shù)據(jù)庫(kù)中各表之間復(fù)雜的關(guān)系對(duì)分類(lèi)任務(wù)有很大的影響。根據(jù)圖1可以看出，每條邊可能會(huì)導(dǎo)致許多重復(fù)的連接操作，沒(méi)有意義的語(yǔ)義關(guān)系。

為了能夠簡(jiǎn)單明了地表示各關(guān)系表之間的關(guān)系，我們使用語(yǔ)義關(guān)系圖來(lái)表示。

定義2語(yǔ)義關(guān)系圖SGR是一種有向無(wú)環(huán)圖SRG(V,E,W),其中，V是對(duì)應(yīng)于數(shù)據(jù)庫(kù)中關(guān)系表的頂點(diǎn)集合。E是有向邊，并且每個(gè)邊(v，w)代表通過(guò)直接連接這兩個(gè)表把表w連接到v表上。W是關(guān)系表中所有屬性的集合，其中每個(gè)屬性連接兩個(gè)表。我們把這種屬性稱(chēng)為連接屬性。

語(yǔ)義關(guān)系圖以目標(biāo)表為起點(diǎn)，表與表之間的連接路徑有兩種：一種是主碼到外碼的連接；另一種是外碼到主碼的連接?？偟膩?lái)說(shuō)，語(yǔ)義關(guān)系圖不僅描述了數(shù)據(jù)庫(kù)中關(guān)系表之間的關(guān)系，而且使這種關(guān)系更加的簡(jiǎn)單明了。它的總體形狀類(lèi)似于數(shù)據(jù)庫(kù)中的ER圖。圖2就是圖1對(duì)應(yīng)的語(yǔ)義關(guān)系圖，促進(jìn)了關(guān)系間虛擬連接的過(guò)程，就像整個(gè)算法的一個(gè)流程圖。

圖2　PKDD CUP99金融數(shù)據(jù)庫(kù)的語(yǔ)義關(guān)系圖

2　特征選擇

特征選擇的研究始于20世紀(jì)60年代初，在對(duì)其研究的過(guò)程中，通常假設(shè)特征與特征之間是相互獨(dú)立的。由于當(dāng)初設(shè)計(jì)的特征數(shù)目比較少，很多操作都憑借人為的經(jīng)驗(yàn)來(lái)進(jìn)行的，這樣不僅具有很大的盲目性和局限性，而且花費(fèi)代價(jià)還比較高，所得出來(lái)的結(jié)果也很不理想。20世紀(jì)90年代以來(lái)，人們已經(jīng)進(jìn)入一個(gè)信息化社會(huì)化的時(shí)代，信息技術(shù)的快速發(fā)展使得數(shù)據(jù)規(guī)模變得非常龐大，數(shù)據(jù)的維數(shù)也非常大。這使得信息處理的要求越來(lái)越高，人為經(jīng)驗(yàn)的評(píng)價(jià)方法已經(jīng)不能適應(yīng)大規(guī)模數(shù)據(jù)了。因此，需要找到能夠適應(yīng)大數(shù)據(jù)且能夠保證準(zhǔn)確率等綜合性能較好的特征選擇方法。為了獲得更好的結(jié)果，許多學(xué)者基于傳統(tǒng)算法并結(jié)合相關(guān)領(lǐng)域?qū)μ卣鬟x擇方法進(jìn)行了改造，但是由于特征選擇方法本身的多樣性以及處理問(wèn)題的復(fù)雜性，至今還沒(méi)有一個(gè)固定的選擇模式和有效的方法。

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

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

3　基于mRMR的多關(guān)系樸素貝葉斯分類(lèi)

3.1相關(guān)知識(shí)

由于最大相關(guān)最小冗余的特征選擇算法是在互信息的基礎(chǔ)上提出的方法，本節(jié)將介紹互信息的相關(guān)知識(shí)。首先介紹信息熵的概念。熵這個(gè)術(shù)語(yǔ)源于熱力學(xué)領(lǐng)域，而香農(nóng)把熵這個(gè)概念引入信息理論中，故又被稱(chēng)為香農(nóng)熵[18]。它是衡量信息的一種度量，在信息論的發(fā)展歷程中起著非常重大的意義。

(1)

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

(2)

互信息源于信息論，是衡量?jī)蓚€(gè)特征之間關(guān)聯(lián)度的一個(gè)重要標(biāo)準(zhǔn)，其定義如下：

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

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

(3)

且互信息與聯(lián)合熵、條件熵的關(guān)系有:

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

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

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

3.2最大相關(guān)與最小冗余

在機(jī)器學(xué)習(xí)與模式識(shí)別中，特征選擇的目的是為了尋找最具有代表的特征集以使得分類(lèi)的錯(cuò)誤最小化。要得到最小誤差通常需要通過(guò)計(jì)算類(lèi)標(biāo)簽c與子空間Rm的最大統(tǒng)計(jì)相關(guān)量，就是所謂的最大相關(guān)。由于是基于互信息的特征選擇算法，所以首先要解決的問(wèn)題就是互信息計(jì)算，根據(jù)3.1節(jié)的介紹，對(duì)于兩個(gè)隨機(jī)變量X和Y:

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

(4)

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

(5)

依據(jù)式(4)和式(5)便可以實(shí)現(xiàn)最大相關(guān)。最大相關(guān)最小冗余算法就是對(duì)于給定的原始特征集，依據(jù)最大相關(guān)最小冗余準(zhǔn)則對(duì)原始特征集X中的特征與類(lèi)標(biāo)簽之間的互信息大小進(jìn)行排序并把結(jié)果放入目標(biāo)集R。

將最大相關(guān)與最小冗余結(jié)合起來(lái)就是所謂的“最大最小冗余準(zhǔn)則”，于是便產(chǎn)生如下算子maxΦ(D,R),Φ=D-R，即信息差(MID)算子▽MID。其中Φ(D,R)用來(lái)表示D和R的聯(lián)合關(guān)系?，F(xiàn)在把最大相關(guān)最小冗余準(zhǔn)則問(wèn)題轉(zhuǎn)化為了最大化信息差算子▽MID的問(wèn)題，假設(shè)S中已經(jīng)包含了m-1個(gè)特征，那么S的第m個(gè)特征就是那個(gè)能使下面算子最大的那個(gè)特征:

(6)

即mRMR特征選擇問(wèn)題轉(zhuǎn)化為了計(jì)算信息差算子▽MID的問(wèn)題。因此，利用mRMR算法進(jìn)行特征選擇的過(guò)程就是依據(jù)▽MID的大小來(lái)對(duì)各個(gè)特征進(jìn)行排序然后進(jìn)行篩選的過(guò)程。

由于在多關(guān)系數(shù)據(jù)庫(kù)中，只有目標(biāo)表有類(lèi)標(biāo)簽，而非目標(biāo)表中沒(méi)有類(lèi)標(biāo)簽，要想計(jì)算非目標(biāo)表中特征的互信息以及信息差算子▽MID，必須利用元組ID傳播技術(shù)[9]。通過(guò)這種虛擬連接技術(shù)，元組IDs以及類(lèi)標(biāo)簽才能從目標(biāo)表傳遞到非目標(biāo)表中。在計(jì)算出每個(gè)關(guān)系表中特征的最大相關(guān)最小冗余的信息差算子▽MID之后，根據(jù)信息差算子對(duì)每個(gè)關(guān)系表的特征進(jìn)行選擇，選擇出最終用于分類(lèi)的最優(yōu)特征集。這些選擇出來(lái)的特征集被用于多關(guān)系樸素貝葉斯分類(lèi)。

3.3多關(guān)系樸素貝葉斯分類(lèi)

樸素貝葉斯是利用統(tǒng)計(jì)學(xué)中的貝葉斯定理來(lái)對(duì)樣本進(jìn)行分類(lèi)的一種簡(jiǎn)單概率的分類(lèi)方法。它的原理簡(jiǎn)單，易于理解。其思想基礎(chǔ)是對(duì)于一個(gè)待分類(lèi)的樣本，通過(guò)計(jì)算它屬于各個(gè)類(lèi)別的概率值來(lái)確定概率值最大的那個(gè)類(lèi)別就是該樣本的最終類(lèi)別。貝葉斯分類(lèi)應(yīng)用非常廣泛，可應(yīng)用到各種領(lǐng)域，如對(duì)垃圾郵件的過(guò)濾[19]、人臉識(shí)別[20]等。起初，樸素貝葉斯分類(lèi)只應(yīng)用于單表數(shù)據(jù)，后來(lái)被擴(kuò)展到直接處理多個(gè)關(guān)系表。

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

CMAP=argmaxci∈CP(ci|X)

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

(7)

3.4MNB-mRMR算法描述

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

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

算法: MNB-mRMR

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

輸出：SRi，每個(gè)關(guān)系表所選的特征集

step1: CreateRelationGraph (G)；

step 2: Propagate (Ri, Rt)；

step3:

a) 對(duì)于每個(gè)關(guān)系表Ri，根據(jù)式(4)計(jì)算每個(gè)特征與類(lèi)標(biāo)簽的互信；

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

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

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

step 4: 利用多關(guān)系樸素貝葉斯分類(lèi)算法對(duì)最終進(jìn)行特征選擇后的關(guān)系表進(jìn)行分類(lèi)驗(yàn)證。

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

4　實(shí)驗(yàn)結(jié)果與分析

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

4.1閾值設(shè)定

在本節(jié)中，主要討論實(shí)驗(yàn)室中所涉及的參數(shù)設(shè)置問(wèn)題。本節(jié)中所要討論的參數(shù)是特征的最大相關(guān)與最小冗余的信息差算子μ，因?yàn)樵贛NB-mRMR算法中，需要根據(jù)最大相關(guān)與最小冗余的信息差算子的大小與給定閾值μ的大小，刪除小于給定閾值的特征。為了選出最優(yōu)特征集以得到高的分類(lèi)精確度，本文通過(guò)手動(dòng)設(shè)定不同閾值，選擇那些信息差算子▽MID大于給定閾值的特征集。對(duì)于不同的閾值，整個(gè)算法的分類(lèi)準(zhǔn)確率和時(shí)間性能也會(huì)有不同。圖3表示了在信息差算子μ取不同的值時(shí)，該算法的分類(lèi)精確度的變化。該分類(lèi)精確度基本上處于一個(gè)先上升后下降的趨勢(shì)，并在μ=-0.01左右，分類(lèi)精確度最高。因此，在本文的實(shí)驗(yàn)中，我們選取-0.01作為信息差算子的閾值，根據(jù)各個(gè)特征的信息差算子的值選出大于-0.01的特征集。

圖3　不同μ值下的分類(lèi)準(zhǔn)確率的比較

4.2分類(lèi)性能比較

為了驗(yàn)證MNB-mRMR算法的有效性，本文將該算法與TILDE算法、Graph-NB算法進(jìn)行了比較，實(shí)驗(yàn)結(jié)果如表1所示。在表1中，可以看出MNB-mRMR算法相較于TILDE算法、Graph-NB算法以及FARS算法，分類(lèi)準(zhǔn)確率都要高。MNB-mRMR算法既考慮到特征與類(lèi)標(biāo)簽的相關(guān)度，又考慮到特征與特征之間的冗余度，將這兩者結(jié)合起來(lái)能更充分、更準(zhǔn)確地評(píng)估特征。因此，MNB-mRMR算法在分類(lèi)準(zhǔn)確度上會(huì)高于另外三種分類(lèi)算法。

表1　PKDD CUP 99的準(zhǔn)確率

5　結(jié)　語(yǔ)

本文提出了基于mRMR的多關(guān)系樸素貝葉斯分類(lèi)算法。特征選擇一直是提高分類(lèi)效果的有效方法，本文中將基于互信息的最大相關(guān)最小冗余的特征選擇方法應(yīng)用到多關(guān)系分類(lèi)中，剔除了與類(lèi)標(biāo)簽不相關(guān)且冗余度高的特征，選出了最優(yōu)特征集。在選擇最優(yōu)特征集的過(guò)程中，根據(jù)特征的最大相關(guān)最小冗余的信息差算子的大小進(jìn)行選擇，該信息差算子綜合了特征的最大相關(guān)度與最小冗余度，能夠有效地表示該特征對(duì)分類(lèi)效果的影響力。根據(jù)給定的信息差算子的閾值，反復(fù)實(shí)驗(yàn)訓(xùn)練，訓(xùn)練出分類(lèi)效果最好的特征集。最后用多關(guān)系樸素貝葉斯分類(lèi)算法進(jìn)行了驗(yàn)證。該方法主要解決了不相關(guān)特征與冗余的特征對(duì)分類(lèi)任務(wù)產(chǎn)生不好影響的問(wèn)題。實(shí)驗(yàn)結(jié)果表明了該算法提高了分類(lèi)精確度且加強(qiáng)了分類(lèi)模型的可理解性。

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

[2] 劉海燕. 基于信息論的特征選擇算法研究[D]. 上海:復(fù)旦大學(xué)，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]. 北京: 科學(xué)出版社, 2005:18-31.

[19] 惠孛, 吳躍. 基于全局的即時(shí)垃圾郵件過(guò)濾模型的研究[J]. 電子測(cè)量與儀器學(xué)報(bào),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。國(guó)家自然科學(xué)基金項(xiàng)目(61273292，6130 5063)。張晶，副教授，主研領(lǐng)域：數(shù)據(jù)挖掘，人工智能。畢佳佳，碩士生。劉爐，碩士生。

TP311

A

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