分類算法之貝葉斯(Bayes)分類器

摘要：旁聽了清華大學王建勇老師的 資料挖掘：理論與算法 的課,講的還是挺細的,好記性不如爛筆頭,在此記錄自己的學習内容,友善以後複習。

一：貝葉斯分類器簡介

1）貝葉斯分類器是一種基于統計的分類器,它根據給定樣本屬于某一個具體類的機率來對其進行分類。

2）貝葉斯分類器的理論基礎是貝葉斯理論。

3）貝葉斯分類器的一種簡單形式是樸素貝葉斯分類器,跟随機森林、神經網絡等分類器都有可比的性能。

4）貝葉斯分類器是一種增量型的分類器。

二：貝葉斯理論

第一次接觸貝葉斯還是大學學機率論的時候,那時候也就隻知道做題目,沒想到現在還能夠在工作和學習中用到它,先複習下相關的基礎機率公式吧：

1) 乘法定理：設P（B）>0,則有P(AB) = P(A|B)P(B).

2) 全機率公式：設試驗E的樣本空間為S,A為E的事件,若事件組B1,B2,…,Bn為S的一個劃分,且P（Bi）> 0(i=1,2,…,n),則有

P(A) = P(A|B1)P(B1) + P(A|B2)P(B2) + …+ P(A|Bn)P(Bn).

    注：在很多事件問題中P(A)不容易算出來,但是可以很容易的找到S的一個劃分:B1,B2,…,Bn,并且P(Bi)和P(A|Bi)為已知或者容易算出,那麼就可以根據上式求出P(A).

3）貝葉斯公式：設試驗E的樣本空間為S,A為E的事件,B1,B2…,Bn為S的一個劃分,且P(A)>0,P(Bi)>0(i=1,2,…,n),則有

P(Bi|A) = P(ABi)/P(A) = P(A|Bi)P(Bi)/∑P(A|Bi)P(Bi),i=1,2,…n.

舉例：

X是一個待分類的資料元組,由n個屬性描述；H是一個假設,例如X屬于類C。對于分類問題,我們想計算出機率P(H|X):即已知元組X的每個元素對應的屬性值,求出X屬于C類的機率。

例如：X的屬性值為：age=25,income=$5000,H對應的假設是：X會買電腦。

P(H|X)：意思是在已知某客戶資訊age=25,income=$5000的條件下,該客戶會買電腦的機率。

P(H):意思是對于任何給定的客戶資訊，該客戶會購買電腦的機率。

P(X|H)：意思是已知客戶會買電腦，那麼該客戶的age=25,income=$5000的機率。

P(X):意思是在我們所有的客戶資訊集合中,客戶的age=25,income=$5000的機率。

是以：P(H|X) = P(X|H)P(H)/P(X)

三：樸素貝葉斯分類器

樸素貝葉斯分類器的工作流程如下：

1：設D為樣本訓練集；每一個樣本X是由n個屬性值組成的，X=(x1,x2,…xn)；對應的屬性集為A1,A2,A3…An;

2: 假設有m個類标簽:C1,C2,…Cm.對于某待分類元X,樸素分類器會把P(Ci|X)(i=1,2,…m)值最大的那個類标簽Ci認為是X的類别,即樸素貝葉斯分類器預測出X屬于類Ci,當且僅當P(Ci|X)>P(Cj|X) (1≤j≤m,j≠i).是以我們的目标就是找出P(Ci|X)中的最大值。

P(Ci|X) = P(X|Ci)P(Ci)/P(X)

對于給定的樣本集，P(X)是常數，跟某個具體的類标簽沒有關聯，是以要想找出P(Ci|X)的最大值也就是找出P(X|Ci)P(Ci)的最大值：

如果我們不知道P(Ci)的值，我們可以假設P(C1)=P(C2)=…=P(Cm),當然P(Ci)可以通過估計值來代替,P(Ci)=|Ci, D| /|D|

其中|D|為樣本總數，|Ci,D|為D中屬于類Ci的樣本數。

3：如果n的值特别大,也就是說樣本元有很多屬性,那麼對于P(X|Ci)的計算會相當複雜。是以在樸素貝葉斯中進行了一個假設：即對于樣本元中的每個屬性,它們都互相條件獨立。

是以有：

對于P(xi|Ci)我們可以從訓練集中算出來,其中xi代表在某個具體樣本中對應屬性Ai的值。

P(xi|Ci)的計算分為兩種情況：

1):如果屬性Ai的值是分類變量(離散變量),那麼P(xi|Ci)等于訓練樣本空間|D|中,屬于類Ci并且對應屬性Ai的值等于xi的數目除以樣本空間中屬于類Ci的樣本數目。

2):如果Ai的值是連續型的變量,則P(xi|Ci)的計算會根據高斯分布來計算,設其中均值為μ,标準方差為σ：

4：為了預測X所屬的類标簽,我們根據前面的步驟可以算出每一個類标簽Ci對應的P（X|Ci)P(Ci)值，當某一個類标簽Ci有：

P(X|Ci)P(Ci)>P(X|Cj)P(Cj) 對于任意j：   1≤j≤m,j≠i

則我們認為X屬于類标簽Ci.

四：具體例子分析

這裡我們還是用 分類算法之決策樹 中的樣本資料來進行舉例：

樣本空間D如下表所示：其中 |D|=14.

屬性集合為A{age,come,student,credit_rating} 對應的屬性個數n=4.

分類屬性為：buys_computer,值為{yes,no}  即C1：buys_computer = yes;C2: buys_computer = no; 分類标簽個數 m = 2;

有一待分類的資料元X={age<=30,income=medium,student=yes,credit_rating=fail}.

則根據樸素貝葉斯分類器的工作流程我們可以計算出：

P(Ci):

P(buys_computer = “yes”) = 9/14 = 0.643

P(buys_computer = “no”) = 5/14= 0.357

P(xi|Ci):

P(age = “<=30” | buys_computer = “yes”) = 2/9 = 0.222

P(age = “<= 30” | buys_computer = “no”) = 3/5 = 0.6

P(income = “medium” | buys_computer = “yes”) = 4/9 = 0.444

P(income = “medium” | buys_computer = “no”) = 2/5 = 0.4

P(student = “yes” | buys_computer = “yes) = 6/9 = 0.667

P(student = “yes” | buys_computer = “no”) = 1/5 = 0.2

P(credit_rating = “fair” | buys_computer = “yes”) = 6/9 = 0.667

P(credit_rating = “fair” | buys_computer = “no”) = 2/5 = 0.4

P(X|Ci):

P(X|buys_computer = “yes”) = 0.222 x 0.444 x 0.667 x 0.667 = 0.044

P(X|buys_computer = “no”) = 0.6 x 0.4 x 0.2 x 0.4 = 0.019

P(X|Ci)*P(Ci) :

P(X|buys_computer = “yes”) * P(buys_computer = “yes”) = 0.028

P(X|buys_computer = “no”) * P(buys_computer = “no”) = 0.007

因為0.28>0.007是以X屬于類：buys_computer = “yes”.

五：樸素貝葉斯存在的問題

1：零機率問題

在上述的例子中假設在樣本資料集中income = medium的樣本數為0,那麼P(income = “medium” | buys_computer = “yes”) 和

P(income = “medium” | buys_computer = “no”) 都将為0,那麼在計算P(X|Ci)*P(Ci)時結果也為0，這樣就不好決定X是屬于哪一個類。

對于這樣的問題的一個解決方案叫做：Laplacian correction或者Laplacian estimator,是以一位法國數學家Pierre Laplace名字命名的。

它的具體做法就是給相應的屬性的不同值數目都加1:

假設：有1000個訓練樣本,其中income=low的數目為10,income=medium的數目為0，income=high的數目為990，則為了避免零機率問題，我們給每一種income的數目加1，及最後結果為 income =medium的數目為1，low的數目為11，high的數目為991.這樣也就避免了零機率問題。

2：準确度問題

樸素貝葉斯分類器是基于樣本屬性條件獨立的假設的前提下的,但是實際情況可能并不成立，這樣也就缺失準确性了.

解決樸素貝葉斯準确性問題提出的一種方法叫做：貝葉斯網絡（Bayesian Belief Networks ）.這個方法留着下次學習。