基本介紹
- 中文名：貝葉斯分類算法
- 外文名：bayesian classifier
- 所屬學科：統計學
- 定義 ：利用機率統計知識進行分類的算法
分類,樸素貝葉斯算法,TAN算法（樹增強型樸素貝葉斯算法）,分類算法,ARCS,CBA,CBA,ADT,CMAR,CPAR,基本步驟,
分類
樸素貝葉斯算法
設每個數據樣本用一個n維特徵向量來描述n個屬性的值，即：X={x1，x2，…，xn}，假定有m個類，分別用C1, C2,…，Cm表示。給定一個未知的數據樣本X（即沒有類標號），若樸素貝葉斯分類法將未知的樣本X分配給類Ci，則一定是
P(Ci|X)>P(Cj|X) 1≤j≤m，j≠i
根據貝葉斯定理
由於P(X)對於所有類為常數，最大化後驗機率P(Ci|X)可轉化為最大化先驗機率P(X|Ci)P(Ci)。如果訓練數據集有許多屬性和元組，計算P(X|Ci)的開銷可能非常大，為此，通常假設各屬性的取值互相獨立，這樣
先驗機率P(x1|Ci)，P(x2|Ci)，…，P(xn|Ci)可以從訓練數據集求得。
根據此方法，對一個未知類別的樣本X，可以先分別計算出X屬於每一個類別Ci的機率P(X|Ci)P(Ci)，然後選擇其中機率最大的類別作為其類別。
樸素貝葉斯算法成立的前提是各屬性之間互相獨立。當數據集滿足這種獨立性假設時,分類的準確度較高，否則可能較低。另外，該算法沒有分類規則輸出。
TAN算法（樹增強型樸素貝葉斯算法）
TAN算法通過發現屬性對之間的依賴關係來降低NB中任意屬性之間獨立的假設。它是在NB網路結構的基礎上增加屬性對之間的關聯(邊)來實現的。
實現方法是：用結點表示屬性，用有向邊表示屬性之間的依賴關係，把類別屬性作為根結點，其餘所有屬性都作為它的子節點。通常，用虛線代表NB所需的邊，用實線代表新增的邊。屬性Ai與Aj之間的邊意味著屬性Ai對類別變數C的影響還取決於屬性Aj的取值。
這些增加的邊需滿足下列條件：類別變數沒有雙親結點，每個屬性有一個類別變數雙親結點和最多另外一個屬性作為其雙親結點。
找到這組關聯邊之後，就可以計算一組隨機變數的聯合機率分布如下：
其中ΠAi代表的是Ai的雙親結點。由於在TAN算法中考慮了n個屬性中(n-1)個兩兩屬性之間的關聯性，該算法對屬性之間獨立性的假設有了一定程度的降低，但是屬性之間可能存在更多其它的關聯性仍沒有考慮，因此其適用範圍仍然受到限制。
分類算法
ARCS
CBA
CBA(classification based on association)是基於關聯規則發現方法的分類算法。該算法分兩個步驟構造分類器。第一步：發現所有形如xi1∧x => Ci 的關聯規則，即右部為類別屬性值的類別關聯規則(classification association rules，CAR)。第二步：從已發現的CAR中選擇高優先度的規則來覆蓋訓練集，也就是說，如果有多條關聯規則的左部相同，而右部為不同的類，則選擇具有最高置信度的規則作為可能規則。文獻[4]對該過程進行了較深入的研究，使得算法在此步驟不需要對訓練數據集進行過多的掃描。
CBA算法的優點是其分類準確度較高，在許多數據集上比C4.5更精確。此外，上述兩步都具有線性可伸縮性。
CBA
CBA(Classification Based on Association)是關聯分類。此算法把分類規則挖掘和關聯規則挖掘整合到一起。與CART和C4.5隻產生部分規則不同的是,CBA產生所有的類關聯規則CARs(Class Association Rules)，然後選擇最好的規則去覆蓋訓練集。另外，在此算法的框架中，資料庫可以駐留在磁碟中
CAEP使用項集支持度挖掘HV露模式(Emerging Pattern), 而EP用於構造分類。CAEP找出滿足給定支持度和增長率閾值的EP。已經發現，在許多數據集上，CAEP比C4.5和基於關聯的分類更精確。一種替代的、基於跳躍的HV露模式JEP(Jnmping Emerging Pattern)是一種特殊類型的EP，項集的支持度由在一個數據集中的0陡峭地增長到另一個數據集中的非0。在一此大的多維資料庫中，JEP性能優於CAEP, 但在一些小型資料庫中，CAEP比JEP優，這二種分類法被認為是互補的。
ADT
ADT(Association Decision Trec)分二步實現以精確度驅動為基礎的過度適合規則的剪枝。第一步，運用置信度規則建立分類器。主要是採用某種置信度的單調性建立基於置信度的剪枝策略。第二步，為實現精確性，用關聯規則建立一種平衡於DT(Dccision Tree)歸納的精確度驅動剪枝。這樣的結果就是ADT(Association Based Decision Trec)。它聯合了大量的關聯規則和DT歸納精確性驅動剪枝技術。
CMAR
基於多維關聯規則的分類算法CMAR(Classification Based on Multiple Class-Association Rules)是利用FP-Growth算法挖掘關聯規則，建立類關聯分布樹FP－樹。採用CR－樹(Classification Rulc Trcc)結構有效地存儲關聯規則。基於置信度、相關性和資料庫覆蓋來剪枝。分類的具體執行採用加權廠來分析。與CBA和C 4.5相比，CMAR性能優異且伸縮性較好。但CMAR優先生成的是長規則，對資料庫的覆蓋效果較差;利用加權x統計量進行分類，會造成x統計量的失真，致使分類值的準確程度降低。
CPAR
CPAR(Classification Based on Predictive Association Rules)整合了關聯規則分類和傳統的基於規則分類的優點。為避免過度適合，在規則生成時採用貪心算法，這比產生所有候選項集的效率高;採用一種動態方法避免在規則生成時的重複計算;採用頂期精確性評價規則，並在預測時套用最優的規則，避免產生冗餘的規則。另外，MSR(Minimnm Set Rule)針對基於關聯規則分類算法中產生的關聯規則集可能太大的問題，在分類中運用最小關聯規則集。在此算法中，CARS並不是通過置信度首先排序，因為高置信度規則對噪聲是很敏感的。採用早期剪枝力方法可減少關聯規則的數量，並保證在最小集中沒有不相關的規則。實驗證實，MSR比C45和CBA的錯誤率要低得多。
基本步驟
主要有以下7個步驟：
1. 收集大量的垃圾郵件和非垃圾郵件，建立垃圾郵件集和非垃圾郵件集。
2. 提取郵件主題和郵件體中的獨立字元串，例如 ABC32，￥234等作為TOKEN串並統計提取出的TOKEN串出現的次數即字頻。按照上述的方法分別處理垃圾郵件集和非垃圾郵件集中的所有郵件。
3. 每一個郵件集對應一個哈希表，hashtable_good對應非垃圾郵件集而hashtable_bad對應垃圾郵件集。表中存儲TOKEN串到字頻的映射關係。
4. 計算每個哈希表中TOKEN串出現的機率P=（某TOKEN串的字頻）/（對應哈希表的長度）。
5. 綜合考慮hashtable_good和hashtable_bad，推斷出當新來的郵件中出現某個TOKEN串時，該新郵件為垃圾郵件的機率。數學表達式為：
A 事件 ---- 郵件為垃圾郵件；
t1,t2 …….tn 代表 TOKEN 串
則 P （ A|ti ）表示在郵件中出現 TOKEN 串 ti 時，該郵件為垃圾郵件的機率。
設
P1 （ ti ） = （ ti 在 hashtable_good 中的值）
P2 （ ti ） = （ ti 在 hashtable_ bad 中的值）
則 P （ A|ti ） =P2 （ ti ） /[ （ P1 （ ti ） +P2 （ ti ） ] ；
6. 建立新的哈希表hashtable_probability存儲TOKEN串ti到P（A|ti）的映射。
7. 至此，垃圾郵件集和非垃圾郵件集的學習過程結束。根據建立的哈希表 hashtable_probability可以估計一封新到的郵件為垃圾郵件的可能性。
當新到一封郵件時，按照步驟2，生成TOKEN串。查詢hashtable_probability得到該TOKEN 串的鍵值。
假設由該郵件共得到N個TOKEN 串，t1,t2…….tn,hashtable_probability中對應的值為 P1 ， P2 ， ……PN， P(A|t1 ,t2, t3……tn) 表示在郵件中同時出現多個TOKEN串t1,t2……tn時，該郵件為垃圾郵件的機率。
由複合機率公式可得P(A|t1 ,t2, t3……tn)=（P1*P2*……PN）/[P1*P2*……PN+（1-P1）*（1-P2）*……（1-PN）]，當 P(A|t1 ,t2, t3……tn) 超過預定閾值時，就可以判斷郵件為垃圾郵件。
