基于預測能力的貝葉斯網絡分類器學習

摘要：分析了貝葉斯分類器家族中有代表性的分類器；給出變量之間預測能力的概念及估計方法，在此基礎上建立了基于變量間預測能力的貝葉斯網絡分類器結構學習方法，并使用UCI數據進行分類實驗。實驗結果顯示，該方法能夠有效地進行貝葉斯網絡分類器學習，使得貝葉斯網絡分類器傾向于簡單化，具有較強的分類能力。

關鍵詞：貝葉斯網絡； 分類器； 預測能力

中圖分類號：TP311.13文獻標志碼：A

文章編號：1001－3695(2007)08－0050－03

0引言

基于貝葉斯方法的分類器是一種借助有向無環圖來描述的概率模型，同時也是一種圖形模型[1，2]。這種圖形表示強調了模型結構的獨立性，具有形式簡單、易于解釋，且可以很容易地從不同角度進行推廣等特點，是數據挖掘、機器學習、模式識別中分類知識獲取的重要工具之一。在貝葉斯分類家族中有樸素貝葉斯分類器、TAN分類器和貝葉斯網絡分類器等[3，4]。其中，樸素貝葉斯分類器和TAN分類器構建的方法比較簡單，但有很強的條件限制；在理論上，貝葉斯網絡分類器與聯合分類器具有相同的分類能力。由于具有概率推斷功能，根據條件獨立性能夠有效地降低維度、顯著提高效率則是最優分類器。實現貝葉斯網絡分類器的核心是貝葉斯網絡分類器的結構學習。現有的貝葉斯網絡結構學習方法[5，6]可分成兩類：a）基于打分—搜索的學習方法[7]。該方法過程簡單規范，但由于搜索空間大，一般要求節點有順序，只適用于變量少或在一定范圍內的結構學習。b）基于依賴分析的學習方法[8]。該方法過程比較復雜，在現有的依賴分析方法中，冗余邊檢驗是在確定邊方向之前進行的，無法準確地確定切割集，從而導致大量的高維條件概率計算，這樣往往不能定向所有的邊。

本文給出變量之間預測能力的概念及估計方法，證明預測能力就是預測正確率，預測能力相同是條件獨立性的充分必要條件。這樣通過引入預測能力，把變量之間弧的存在性與方向有機結合起來，得到了一種有效的貝葉斯網絡分類器學習方法。 

1貝葉斯分類器

貝葉斯分類是非規則分類，是通過對訓練集學習而歸納出分類器，利用分類器對沒有分類的數據進行分類。貝葉斯分類并不把一個對象絕對地指派給某一類，而是通過計算得出屬于某一類的概率，具有最大概率的類便是該對象所屬的類。一般情況下，在貝葉斯分類中所有的屬性都潛在地起作用，即并不是一個或幾個屬性決定分類，而是所有屬性都參與分類。貝葉斯分類對象的屬性可以是離散的、連續的，也可以是混合的，因此它是最優秀的分類器之一。其中主要包括樸素貝葉斯分類器、TAN分類器和貝葉斯網絡分類器等。

1．2貝葉斯分類器的結構模型

樸素貝葉斯分類器假設在給定類變量時，屬性變量之間條件獨立，在分類器結構中每一個屬性節點只具有一個類父節點。TAN分類器假設在給定類變量時，屬性變量之間具有線性依賴關系，在分類器結構中每一個屬性節點除類父節點外，最多只能具有一個屬性父節點。貝葉斯網絡分類器不作任何假設，是變量之間依賴關系的真實體現。三種分類器的結構如圖1所示。

(a) 樸素貝葉斯分類器結構

(b) TAN分類器結構

(c) 貝葉斯網絡分類器結構

2變量之間的預測能力

3基于預測能力的貝葉斯網絡分類器學習

利用在樣本充足的情況下變量之間存在的預測關系，在引入類變量后進行貝葉斯網絡分類器結構學習。

3．1貝葉斯網絡分類器結構學習

3)環路檢驗

刪除沒有父節點和沒有子節點的節點及與其相連接的弧；在剩下的子圖中再刪除沒有父節點和沒有子節點的節點及與其相連接的弧。如此下去，如果存在每一個節點既有父節點又有子節點的子圖，那么存在環路；否則，不存在環路。

3．2實驗

在UCI機器學習數據倉庫[9]中選擇20個分類數據集，對取連續值的特征，使用等頻離散化的方法進行離散化，利用所有的例子數據進行貝葉斯網絡分類器結構學習，分別使用樸素貝葉斯(naive Bayes)分類器、C4.5分類器和貝葉斯網絡分類器進行分類。采用10折交叉有效性(10fold crossvalidation)驗證方法進行分類器的分類準確性估計。分類準確性如表1所示。

從表1中可以看出，貝葉斯網絡分類器相對于樸素貝葉斯分類器和C4.5分類器都具有優勢。其主要原因是貝葉斯網絡分類器既具有最優性，同時又能夠去除不相關和冗余的屬性變量。這樣既提高了抗噪聲能力，又避免了對數據的過度擬合，因此具有良好的分類效果。

4結束語

基于預測能力的貝葉斯網絡分類器是最優分類器，但當例子數量較少時，由于不能可靠地進行結構學習，適宜選擇TAN分類器或樸素貝葉斯分類器。本文給出的貝葉斯網絡分類器學習方法中，充分利用在樣本充足的情況下，變量之間存在預測關系，證明了預測準確率就是預測能力。通過這種結構方法使得離散變量貝葉斯網絡分類器傾向于簡單化，同時建立的分類器有較強的分類能力。

參考文獻：

[1]PEARL J. Probabilistic reasoning in intelligent systems: networks of plausible inference[M].San Fransisco: Morgan Kaufmann Publishers Inc， 1988:117133.

[2]HECKERMAN D， GEIGER D， CHICKERING D M. Learning Baye￣sian networks: the combination of knowledge and statistical data[J]. Machine Learning， 1995，20(1－3):197－243.

[3]FRIEDMAN N， GEIGER D， GOLDSZMIDT M.Bayesian network classifiers[J]. Machine Learning，1997，29(2－3):131161.

[4]RAMONI M， SEBASTIAMI P. Robust Bayes classifiers[J]. Artificial Intelligence， 2001，125(1－2):209－226.

[5]王雙成， 苑森淼， 王輝. 基于類約束的貝葉斯網絡分類器學習[J].小型微型計算機系統，2004，25(6):968－972.

[6]王雙成， 苑森淼.具有丟失數據的貝葉斯網絡結構學習研究.軟件學報， 2004，15(7):10301041.

[7]LAM W， BACCHUS F. Learning Bayesian belief networks: an approach based on the MDL principle[J]. Computational Intelligence，1994，10(4):269－293.

[8]CHENG Jie， BELL D， LIU Weiru. Learning Bayesian networks from data: an efficient approach based on informationtheory[J]. Artificial Intelligence， 2002，137(1－2):43－90.

[9]NEWMAN D J， HETTICH S， BLAKE C L， et al. UCI repository of machine learning databases [ EB/OL]. http://www.ics.uci.edu/~mlearn/MLRepository.html.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”