半樸素貝葉斯分類器

樸素貝葉斯采用了“屬性條件獨立性假設”，但這個假設的确是有些草率了。因為往往屬性之間包含着各種依賴。于是，人們嘗試對這個假設進行一定程度的放松，由此産生了“半樸素貝葉斯分類器”。半樸素貝葉斯分類器的基本想法是适當考慮一部分屬性間的互相依賴資訊。獨依賴估計是半樸素貝葉斯分類器最常用的一種政策。顧名思義，獨依賴是假設每個屬性在類别之外最多依賴一個其他屬性。

 其中，paj    為屬性 xi 所依賴的屬性，稱為    xi    的父屬性。假設父屬性    paj    已知，那麼可以使用下面的公式估計

于是，問題的關鍵變成了如何确定每個屬性的父屬性。不同的做法産生了不同的獨依賴分類器

• SPODE（Super-Parent ODE）假設所有的屬性都依賴于同一個屬性，稱為超父。
• TAN（Tree Augmented naive Bayes）則在最大帶權生成樹算法的基礎上發展的一種方法。
• AODE（Averaged ODE）是一種內建學習的方法，嘗試将每個屬性作為超父來建構SPODE，與随機森林的方法有所相似。

TAN

　　1.計算任意屬性之間的條件互資訊

　　2.以屬性為節點建構完全圖，節點間的權重設為相應的互資訊；

　　3.建構此完全圖的最大帶權生成樹，挑選根變量，将邊置為有向；

　　4.加入類别結點yy，增加從yy到每個屬性的有向邊。

容易看出，條件互資訊  I(xi,xj|y) 刻畫了屬性  xi  和  xj  在已知類别情況下的相關性。是以，通過最大生成樹算法，TAN實際上僅保留了強相關屬性之間的依賴性。

在這裡，我們通過将屬性條件獨立性假設放松為獨立依賴假設，獲得了泛化性能的提升。那麼如果更進一步，考慮屬性間的高階依賴，能否可以進一步提升泛化性能呢？

也就是說，将第一個公式中的  paj  擴充為包含kk個屬性的集合  paj  ，進而将  ODE  拓展為  kDE  。需要注意的是，随着  k  的增加，準确地估計機率  P(xj|ci,paj)  所需的訓練樣本數量将以指數級增加。

是以，若訓練資料非常充分，泛化性能有可能提升；但在有限樣本的條件下，則會陷入估計高階聯合機率的泥沼。