關(guān)系學(xué)習(xí)中貝葉斯分類算法的比較研究

王 晶，張春英

（河北理工大學(xué) 理學(xué)院，河北 唐山063009）

0 引言

數(shù)據(jù)挖掘算法是在數(shù)據(jù)中尋找一種模式?，F(xiàn)存的大多數(shù)數(shù)據(jù)挖掘方法都是在單一的表中尋找模式。而一個關(guān)系數(shù)據(jù)庫一般由幾個表組成，而不是一個表。近幾年，數(shù)據(jù)挖掘的算法和模式已經(jīng)擴展到多關(guān)系方面，而多關(guān)系學(xué)習(xí)（MRDM，MRL）方法也稱為關(guān)系學(xué)習(xí)，是從關(guān)系數(shù)據(jù)庫中尋找涉及多表（多關(guān)系）的模式。

分類是數(shù)據(jù)挖掘的一種主要的應(yīng)用形式，其應(yīng)用遍歷機器學(xué)習(xí)、模式識別、統(tǒng)計學(xué)、神經(jīng)網(wǎng)絡(luò)、遺傳算法、數(shù)據(jù)庫、專家系統(tǒng)等多個領(lǐng)域。分類算法的核心部分是構(gòu)造分類器。貝葉斯分類算法是數(shù)據(jù)挖掘領(lǐng)域的一種常用的分類方法，它是統(tǒng)計學(xué)分類方法，利用概率進行分類。

目前，在關(guān)系學(xué)習(xí)中，貝葉斯分類算法有很多種，對這些算法進行總結(jié)、比較，指出其優(yōu)點與不足，對提高分類效率有很大幫助。故本文對已有的關(guān)系學(xué)習(xí)中貝葉斯分類算法作了詳細(xì)的比較，并進行歸納總結(jié)。本文第三部分是對單關(guān)系學(xué)習(xí)中貝葉斯分類算法的比較；第四部分是對多關(guān)系學(xué)習(xí)中貝葉斯分類算法的比較；最后是對本文工作的總結(jié)與展望。

1 貝葉斯分類算法基本思想

給定一個具有K個屬性的數(shù)據(jù)集，假設(shè)這K個屬性值均為離散值，分類任務(wù)是預(yù)測測試集中每一個例子的類別。給定一個具體的例子，其屬性值從ai到ak，該例子屬于某一個類ci的概率是P(C=ci| A1=a1…

Ak=ak)。顯然如果該例子屬于某一個類的概率值具有最大值，那么該例子就屬于這個類。根據(jù)貝葉斯定理

其中，P(C=ci)被稱為先驗概率，可以從訓(xùn)練數(shù)據(jù)集中計算得到。P(A1=a1,…, L,…, Ak=ak)與任何的 Ci都無關(guān)，也容易計算。求P(A1=a1…, L,…, Ak=ak| C=ci)。

如果屬性值是獨立的，則

將（2）式帶入（1）式中，可得到樸素貝葉斯分類器所使用的方法[1]，即

其中，VNB表示樸素貝葉斯分類器輸出的目標(biāo)值。理論上講，樸素貝葉斯分類與其他所有分類算法相比，具有最小的誤分類率[2]。

2 單關(guān)系學(xué)習(xí)中貝葉斯分類算法比較

樸素貝葉斯方法就是以概率密度函數(shù)為基礎(chǔ)，描述分類系統(tǒng)中條件屬性和分類屬性之間的映射關(guān)系，從理論上講，與其它所有分類算法相比，具有出錯率最小的特點，因而具有廣泛的應(yīng)用前景。但是貝葉斯方法有其自身的限制：一是先驗概率定義困難；二是實際問題中條件屬性的獨立假設(shè)一般不成立，針對貝葉斯分類方法在實際應(yīng)用中的約束和限制，許多研究者提出結(jié)合粗糙集與貝葉斯方法進行分類知識挖掘的解決方案和實際方法[3-7]。

2.1 基于粗集屬性約簡的樸素貝葉斯分類算法

鄭建軍等人于 2003年提出一種基于粗糙集的貝葉斯分類器算法，該算法在基于粗集屬性約簡方法的基礎(chǔ)上，綜合考慮條件屬性和決策屬性間的依賴性以及條件屬性間的依賴性對約簡的影響。通過基于依賴性的屬性約簡，改善屬性變量間的獨立性限制，發(fā)揮貝葉斯分類器的魯棒性，優(yōu)化貝葉斯分類器的性能。此方法解決了威脅度估計等C3I系統(tǒng)匯總的問題，效果良好。但是，此方法僅適用于完備數(shù)據(jù)的情況下。

在現(xiàn)實生活中，往往數(shù)據(jù)是不完備的。2006年，胡學(xué)剛等人也是利用屬性的依賴性，提出了不完備信息系統(tǒng)中基于粗集的貝葉斯分類算法。該文給出了粗集的相似關(guān)系，利用基于粗糙集理論的不完備數(shù)據(jù)分析方法，調(diào)用ROUSTIDA算法，對空置屬性做出處理，然后再通過屬性約簡，改善屬性間的依賴關(guān)系，找到一組最近似獨立的屬性約簡結(jié)果，最后利用貝葉斯方法對約簡后的數(shù)據(jù)集進行訓(xùn)練得到分類器，達(dá)到理想的分類效果，提高了分類的正確率。

在單關(guān)系學(xué)習(xí)中，大多數(shù)學(xué)者通過引入粗集中屬性依賴性這一特殊性質(zhì)，改善了貝葉斯方法中屬性獨立的限制，擴大了貝葉斯分類器的應(yīng)用范圍。

2.2 加權(quán)樸素貝葉斯分類算法

樸素貝葉斯算法是一種簡單而有效的分類算法，但是它的屬性獨立性假設(shè)一般在現(xiàn)實問題中不能成立，這在某種程度上影響了它的分類能力。一般并不是所有的屬性對分類都是有用的，有的影響大，有的影響小一些?；诖?，又有很多學(xué)者提出將各種特征加權(quán)算法與樸素貝葉斯算法相結(jié)合，給不同的屬性賦不同的權(quán)值，使樸素貝葉斯得以擴展。下面給出幾種典型的加權(quán)樸素貝葉斯分類算法的模型、權(quán)值確定方法、優(yōu)缺點以及進一步的工作方向進行了詳細(xì)的比較。其中，基于屬性頻率的加權(quán)樸素貝葉斯分類算法是本文提出的一種算法。

表1 幾種不同的加權(quán)樸素貝葉斯算法的比較

3 多關(guān)系學(xué)習(xí)中貝葉斯分類算法比較

在現(xiàn)實生活中，海量數(shù)據(jù)越來越多，在單表框架下進行分類已不能滿足人們的需求。多關(guān)系分類已成為數(shù)據(jù)挖掘領(lǐng)域中的研究和應(yīng)用熱點。多關(guān)系數(shù)據(jù)挖掘要從多個表中直接挖掘信息和發(fā)現(xiàn)知識，而不是將數(shù)據(jù)庫中的多個表合并成一個表再進行挖掘。

基于此種情況，文[12]中就提出一種高效準(zhǔn)確的多關(guān)系樸素貝葉斯分類算法—Graph-NB（語義關(guān)系圖）。它通過引入語義關(guān)系圖，對表進行裁剪（cutting off），達(dá)到優(yōu)化語義關(guān)系圖，從而一定程度上消除無關(guān)表對分類影響的目的，以提高分類準(zhǔn)確率。但是，這種方法也有其自身的不足。對于樸素貝葉斯而言，參與分類的基本單位是屬性而不是表，因此，直接刪除語義關(guān)系較弱的表顯然是不合適的。這樣做，很容易導(dǎo)致信息的丟失。

徐光美等人在2008年4月擴展了語義關(guān)系圖的定義[13]，針對現(xiàn)有多關(guān)系樸素貝葉斯分類器中存在的統(tǒng)計偏斜問題，給出了一種新的統(tǒng)計計數(shù)方法，為高效進行關(guān)系表連接，采用元組 ID號傳播方法對關(guān)系表進行虛擬連接，為進一步提高分類準(zhǔn)確率，使用擴展的互信息標(biāo)準(zhǔn)進行屬性剪枝。實驗顯示此種分類器具有良好的分類能力。但是，在多關(guān)系情況下，每個關(guān)系同目標(biāo)關(guān)系間的相關(guān)程度是不同的。此后，作者在文[14]中，基于上述問題，為每張表制定了一個權(quán)值w，它表示此表與目標(biāo)表間的相關(guān)程度，一般由領(lǐng)域?qū)＜抑付ǎ瑆取值范圍為[0，1]。

相對而言，對多關(guān)系樸素貝葉斯分類算法的研究，廣度和深度都不是很大，很多是基于語義關(guān)系圖、互信息或是通過空間分類創(chuàng)建決策樹[15]的。因此，這方面需要進一步的工作。

4 結(jié)論與展望

本文是圍繞貝葉斯分類方法展開，最主要的工作是對單關(guān)系和多關(guān)系情況下，幾種改進的貝葉斯分類算法的簡單綜述，表明貝葉斯分類方法在數(shù)據(jù)分類方面的重要性。在單關(guān)系下，將粗集和貝葉斯分類算法相結(jié)合得到的新的貝葉斯分類算法已相當(dāng)成熟和有效。但在多關(guān)系下，基于粗糙集理論的多關(guān)系樸素貝葉斯分類器的研究還不是很多。對多關(guān)系樸素貝葉斯分類器進行擴展，融合粗糙集理論，用以進行數(shù)據(jù)的預(yù)處理，屬性約簡，屬性重要性度量，表關(guān)系權(quán)重計算等，構(gòu)建一種基于粗糙集理論的多關(guān)系樸素貝葉斯分類算法，仍是今后工作的方向。

[1] Han Jianwei. Data m ining concepts and techniques [M]. 北京：機械工業(yè)出版社.2001

[2] 秦鋒，任詩流，程澤凱，羅慧. 基于屬性加權(quán)的樸素貝葉斯分類算法[J].計算機工程與應(yīng)用.2008

[3] 閆德勤. 對Bayesian粗糙集模型的討論[J].計算機科學(xué).2006.

[4] 楊帆，張彩麗.基于粗集的樸素貝葉斯分類算法及其應(yīng)用[J].計算機工程與應(yīng)用.2007.

[5] 胡學(xué)剛，郭亞光. 一種基于粗糙集的樸素貝葉斯分類算法[J].合肥工業(yè)大學(xué)學(xué)報.2006.

[6] 鄭建軍，劉煒，劉玉樹，王蕾. 基于粗集的貝葉斯分類器算法[J].北京理工大學(xué)學(xué)報. 2003.

[7] 李勃，王艷兵，姚青. 基于粗糙集分類算法研究與實現(xiàn)[J].計算機工程與應(yīng)用.2008.

[8] 孫成敏，劉大有，孫舒楊. 粗集和多關(guān)系學(xué)習(xí)綜述[J].吉林：計算機科學(xué).2007.

[9] 錢曉東. 數(shù)據(jù)挖掘中分類方法綜述[J]. 圖書情報工作2007,51(3).

[10] 王國胤. Rough集理論與知識獲取 [M].西安：西安交通大學(xué)出版社.2003

[11] 劉清. Rough集及Rough推理 [M].北京：科學(xué)出版社.2001

[12] 劉紅巖，陳海亮. Graph-NB:一種高效準(zhǔn)確的多關(guān)系樸素貝葉斯分類算法[J].信息系統(tǒng)學(xué)報.2008.

[13] 徐光美，楊炳儒，秦奕青. 一種新的多關(guān)系樸素貝葉斯分類器[J].系統(tǒng)工程與電子技術(shù).2008.4

[14] 徐光美，楊炳儒，秦奕青，張偉. 基于互信息的多關(guān)系樸素貝葉斯分類器[J].北京科技大學(xué)學(xué)報.2008.8

[15] 劉偉輝，王麗珍. 基于多關(guān)系的空間分類算法研究[J].云南大學(xué)學(xué)報.2006，28（S1）:158-163

[16] 安利平. 粗糙集理論的方法與應(yīng)用研究[J]天津大學(xué)學(xué)報.2001

[17] 鄧維斌，王國胤，王燕. 基于Rough Set 的加權(quán)樸素貝葉斯分類算法[J].計算機科學(xué).2007

[18] 程克非，張聰. 基于特征加權(quán)的樸素貝葉斯分類器[J].計算機仿真.2006.10

[19] 張明衛(wèi)等. 基于相關(guān)系數(shù)的加權(quán)樸素貝葉斯分類算法[J].東北大學(xué)學(xué)報.2008

[20] Paw lak Z.Rough Sets. Journal of Computer Science, 1982, 11(5):341-356

[21] Paw lak Z.Rough Sets [M].London: Kluwer academ ic publishers, 1991.10