【機器學習】算法原理詳細推導與實作(三):樸素貝葉斯

在上一篇算法中，邏輯回歸作為一種二分類的分類器，一般的回歸模型也是是判别模型，也就根據特征值來求結果機率。形式化表示為 $p(y|x;\theta)$，在參數 $\theta$ 确定的情況下，求解條件機率 $p(y|x)$ 。通俗的解釋為：在給定特定特征後預測結果出現的機率。邏輯回歸的 $y$ 是離散型，取值為 $\{0,1\}$ 。這裡将要介紹另一個分類算法樸素貝葉斯，用以解決 $x$ 是離散型的資料，這是判别模型，也是一個生成學習算法。

貝葉斯定理

定理推導

樸素貝葉斯是基于貝葉斯原理得到的。假設A和B為兩個不互相獨立的事件：

【機器學習】算法原理詳細推導與實作(三):樸素貝葉斯【機器學習】算法原理詳細推導與實作(三):樸素貝葉斯

由上圖可以看出，在事件B已經發生的情況下，事件A發生的機率為事件A和事件B的交集除以事件B：

p(A|B)=p(A⋂B)p(B)

同理，在事件A已經發生的情況下，事件B發生的機率為事件A和事件B的交集除以事件A：

\[ p(B|A)=\frac{p(B\bigcap A)}{p(A)} \]

結合這兩個方程式，我們可以得到：

\[ p(A|B)p(B)=p(A\bigcap B)=p(B|A)p(A) \]

轉換後貝葉斯定理的公式定義為：

\[ P(A|B) = \frac{P(B|A)P(A)}{P(B)} \]

總的來說，貝葉斯定理可以總結為：

貝葉斯定理是将先驗機率做一次更新，得到後驗機率
樸素貝葉斯是輸入先驗機率，找到後驗機率，最後找到最大後驗機率，作為最終的分類結果，以及分類機率

實際問題

假設我們有兩個裝滿了餅幹的碗，第一個碗裡有10個巧克力餅幹和30個普通餅幹，第二個碗裡兩種餅幹都有20個。我們随機挑一個碗，再在碗裡随機挑餅幹。那麼我們挑到的普通餅幹來自一号碗的機率有多少？

解決方案

我們用 x1 代表一号碗，x2 代表二号碗。在x1中取到普通餅幹的機率是 $P(y|x1)=\frac{30}{10+30}\times\frac{1}{2}$，即抽到x1的機率是 $\frac{1}{2}$ ，再在x1中抽到普通餅幹的機率是 $\frac{30}{10+30}=\frac{3}{4}$ ，同理可得 $P(y|x2)=\frac{20}{20+20}\times\frac{1}{2}$ 。而問題中挑到挑到的普通餅幹來自一号碗，已知挑到普通餅幹，那麼這個普通餅幹來自一号碗的機率為：

\[ P(x1|y) = \frac{P(y|x1)P(x1)}{P(y)} \]

根據全機率公式可知，其中拿到普通餅幹的機率為： $P(y)=P(y|x1)P(x1)+ P(y|x2)P(x2)$

計算為：

\[ \begin{split} P(x1|y)&=\frac{P(y|x1)P(x1)}{P(y)} \\ &=\frac{P(y|x1)P(x1)}{P(y|x1)P(x1)+ P(y|x2)P(x2)} \\ &= \frac{0.75\times0.5}{0.75\times0.5+0.5\times0.5} \\ &=0.6 \end{split} \]

樸素貝葉斯

例如如果想實作一個垃圾郵件分類器，用郵件作為輸入，确定郵件是否為垃圾郵件作為輸出，即 $y\in \{0,1\}$，1表示是垃圾郵件0表示不是垃圾郵件，那麼問題來了：給你一封郵件，怎麼将郵件轉化為特征向量 $\vec x$ 來表示這個郵件，以及怎樣區分這封郵件是否是垃圾郵件。

電子郵件僅僅是一段文本，就像是一個詞清單，是以利用詞來建構特征向量 $\vec x$ 。首先周遊詞典，并且得到一個詞典中詞的清單，假設詞典中此的清單如下所示：

詞
word_1
word_2
word_3
...
word_n

假設郵件中存在字典中的詞，那麼特征向量 $\vec x$ 就就記為1，不存在就記為0。例如郵件中假設存在詞 $[word_1,word_2,...,word_n]$ ，則該郵件的特征向量 $\vec x$ 表示為：

\[ x= \begin{bmatrix} 1 \\ 1 \\ 0 \\ ... \\ 1 \end{bmatrix} \]

則 $x\in {0,1}^n $ ，假設詞典的長度為50000，那麼 $x$ 就可能有 $2^{50000}$ 種向量。如果需要履歷多項式用回歸模型進行模組化分類，那麼可能需要 $2^{50000-1}$ 個參數 $\theta$，很明顯看出需要的參數太多了，如果使用梯度下降那麼收斂将會非常慢，是以利用樸素貝葉斯算法是一個很好的選擇。

算法推導

在樸素貝葉斯算法中，我們會對 $p(x|y)$ 做一個假設，假設給定 $y$ 的時候，其中$x \in \{0,1\}^{50000}$， $x_i$ 是條件獨立的，根據鍊式法則可以得到：

\[ \begin{split} p(x_1,x_2,...,x_{50000}|y)&=p(x_1|y)p(x_1|y,x_1)p(x_2|y,x_1,x_2)...p(x_50000|y,x_1,x_2,...,x_{49999}) \\ &=p(x_1|y)p(x_2|y)...p(x_{50000}|y) \\ &=\prod_{i=1}^n p(x_i|y) \end{split} \]

為了拟合出模型的參數，符号假設為，其中 $y=1$ 是垃圾郵件， $y=0$ 是正常郵件：

\[ \phi_{i|y=1}=p(x_i=1|y=1) \phi_{i|y=0}=p(x_i=1|y=0) \phi_y=p(y=1) \]

假設存在 $m$ 個樣本，那麼 $y=1$ 和 $y=0$ 的組合起來的似然估計表示為：

\[ L(\phi_y,\phi_{i|y=0},\phi_{i|y=1})=\prod_{i=1}^m p(x^{(i)}|y^{(i)}) \]

假設訓練樣本為 $m$ 封郵件，$x_j=1$表示包含關鍵詞 $j$，$x_j=0$表示不包含關鍵詞 $j$，則垃圾郵件 $y=1$ 裡面包含的單詞 $j$ 的極大似然估計為：

\[ \phi_{j|y=1}=\frac{\sum_{i=1}^ml\{x_j^{(i)}\bigcap y^{(i)}=1\}}{\sum_{i=1}^ml\{y^{(i)}=1\}} \]

上述公式中，分子的含義是從 1到 $m$ 周遊垃圾郵件内容，對于标簽$x_j=1$的郵件計算其中詞語 $j$ 出現的郵件數目之和。換句話說就是，周遊所有垃圾郵件，統計這些垃圾郵件中包含詞語 $j$ 的郵件數目。分母是對 $i$ 從1到 $m$ 求和，最後得到垃圾郵件的總數，即分母就是垃圾郵件的數目。

同理，正常郵件 $y=0$ 裡面包含的單詞 $j$ 的極大似然估計為：

\[ \phi_{j|y=0}=\frac{\sum_{i=1}^ml\{x_j^{(i)}=1\bigcap y^{(i)}=0\}}{\sum_{i=1}^ml\{y^{(i)}=0\}} \]

垃圾郵件 $y=1$ 的極大似然估計為：

\[ \phi_{j|y=1}=\frac{\sum_{i=1}^ml\{x_j^{(i)}=1\bigcap y^{(i)}=1\}}{\sum_{i=1}^ml\{y^{(i)}=1\}} \]

假設 $m$ 封郵件裡面的詞向量 $\vec x$ 和辨別 $y$ 如下所示：

\[ (x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),...,(x^{(m)},y^{(m)}) \]

是以當垃圾郵件分類器開始訓練時，假設訓練垃圾郵件中包含某些詞 $x$ 的機率 $p(y=1|x)$ ：

\[ \begin{split} p(y=1|x)&=\frac{p(x|y=1)p(y=1)}{p(x)} \\ &=\frac{(\prod_{i=1}^n p(x_i|y=1))p(y=1)}{(\prod_{i=1}^n p(x_i|y=1))p(y=1)+(\prod_{i=0}^n p(x_i|y=0))p(y=0)} \end{split} \]

上式中分母是由全機率計算出詞 $p(x)$ 的機率，即假設 $word_3$ 在垃圾郵件中沒有出現，那麼可以得到：

\[ \begin{split} p(y=1|x)&=\frac{p(x|y=1)p(y=1)}{p(x)} \\ &=\frac{(\prod_{i=1}^{50000} p(x_3|y=1))p(y=1)}{(\prod_{i=1}^{50000} p(x_3|y=1))p(y=1)+(\prod_{i=0}^n p(x_i|y=0))p(y=0)} \\ &=\frac{0}{0+0} \end{split} \]

這就意味着如果 $word_3$ 在垃圾郵件中沒有出現，那麼機率為0，這樣子很明顯是不合理的，無論在數學上會導緻無法繼續計算，還是從機率的角度來說直接排除 $word_3$ 的可能性，其實最好的是 $word_3$ 沒出現，但是還是會有機率，隻是機率很低很低。舉個例子來說，如果某個人投籃球，連續5次都是沒投中，那麼是不是投中的機率為0了，沒投中的機率是1了？

為了修正這個方法，這裡最好是在分子分母加上一個極小數，防止數學上的無效計算和實際中的絕對不可能發生。

拉普拉斯平滑(Laplace smoothing)

繼續上面投籃球的例子，假設沒投中的機率記為 $p(y=0)$ ，投中的機率記為 $p(y=1)$ ，原來的機率為：

\[ \begin{split} p(y=0)&=\frac{沒投中的次數}{投籃球的總次數} \\ &=\frac{沒投中的次數}{投中的次數+沒投中的次數} \\ &=\frac{0}{5+0} \end{split} \]

如果給每一項都平滑一個極小數1，代表投中籃球和沒投中籃球在事先都已經發生過一次了，那麼上述式子變成：

\[ \begin{split} p(y=0)&=\frac{0+1}{(5+1)+(0+1)} \\ &=\frac{1}{7} \end{split} \]

那麼同理可以知道， $m$ 封郵件中，$x_j=1$表示包含關鍵詞 $j$，$x_j=0$表示不包含關鍵詞 $j$，則垃圾郵件 $y=1$ 裡面包含的單詞 $j$ 的極大似然估計為：

\[ \phi_{j|y=1}=\frac{\sum_{i=1}^ml\{x_j^{(i)}\bigcap y^{(i)}=1\}+1}{\sum_{i=1}^ml\{y^{(i)=1}\}+2} \]

正常郵件 $y=0$ 裡面包含的單詞 $j$ 的極大似然估計為：

\[ \phi_{j|y=0}=\frac{\sum_{i=1}^ml\{x_j^{(i)}=1\bigcap y^{(i)}=0\}+1}{\sum_{i=1}^ml\{y^{(i)}=0\}+2} \]

因為 $y$ 隻有兩種可能，我們這裡也假設事先存在一封垃圾郵件和一封正常郵件，是以分子隻需要+1，分母隻需要+2。

總結

總的來說，樸素貝葉斯訓練階段為，給定一組已知的訓練樣本 $(\vec{x_1},y_1),(\vec{x_2},y_2),...,(\vec{x_n},y_n)$，可以得到垃圾郵件中，每一個單詞出現的機率：

\[ p(x|y)=(\prod_{i=1}^{n}p(x_i|y_i) \]

而在預測階段，給定一封郵件的單詞向量 $\vec x$，求這個郵件是否是垃圾郵件，那麼問題就轉化為：已知單詞$\vec x$已經發生，求解是否垃圾郵件p(y|x)：

\[ argmax_yp(y|x)=argmax_y \frac{p(x|y)p(y)}{p(x)}argmax_y p(x|y)p(y) \]

上述中，$x$ 的取值隻能是 $x \in \{0,1 \}$，$n$的長度應該等于詞典中詞的數目。

執行個體

樸素貝葉斯是一個非常優秀的文本分類器，現在大部分垃圾郵件過濾的底層也是基于貝葉斯思想。作者收集了

封垃圾郵件，

封正常郵件，取

封郵件做訓練，

封郵件做測試。

加載資料：

# 打開資料集，擷取郵件内容，
# spam為垃圾郵件，ham為正常郵件
def loadData():
    # 選取一部分郵件作為測試集
    testIndex = random.sample(range(1, 25), 5)

    dict_word_temp = []

    testList = []
    trainList = []
    testLabel = []
    trainLabel = []

    for i in range(1, 26):
        wordListSpam = textParse(open('./email/spam/%d.txt' % i, 'r').read())
        wordListHam = textParse(open('./email/ham/%d.txt' % i, 'r').read())
        dict_word_temp = dict_word_temp + wordListSpam + wordListHam

        if i in testIndex:
            testList.append(wordListSpam)
            # 用1表示垃圾郵件
            testLabel.append(1)
            testList.append(wordListHam)
            # 用0表示正常郵件
            testLabel.append(0)
        else:
            trainList.append(wordListSpam)
            # 用1表示垃圾郵件
            trainLabel.append(1)
            trainList.append(wordListHam)
            # 用0表示正常郵件
            trainLabel.append(0)

    # 去重得到詞字典
    dict_word = list(set(dict_word_temp))
    trainData = tranWordVec(dict_word, trainList)
    testData = tranWordVec(dict_word, testList)

    return trainData, trainLabel, testData, testLabel

複制

訓練函數為：

# 訓練函數
def train(trainData, trainLabel):
    trainMatrix = np.array(trainData)

    # 計算訓練的文檔數目
    trainNum = len(trainMatrix)
    # 計算每篇文檔的詞條數
    wordNum = len(trainMatrix[0])
    # 文檔屬于垃圾郵件類的機率
    ori_auc = sum(trainLabel) / float(trainNum)
    
    # 拉普拉斯平滑
    # 分子+1
    HamNum = np.ones(wordNum)
    SpamNum = np.ones(wordNum)
    # 分母+2
    HamDenom = 2.0
    SpamDenom = 2.0

    for i in range(trainNum):
        # 統計屬于垃圾郵件的條件機率所需的資料，即P(x0|y=1),P(x1|y=1),P(x2|y=1)···
        if trainLabel[i] == 1:
            SpamNum += trainMatrix[i]
            SpamDenom += sum(trainMatrix[i])
        else:
            # 統計屬于正常郵件的條件機率所需的資料，即P(x0|y=0),P(x1|y=0),P(x2|y=0)···
            HamNum += trainMatrix[i]
            HamDenom += sum(trainMatrix[i])
    # 取對數，防止下溢出
    SpamVec = np.log(SpamNum / SpamDenom)
    HamVec = np.log(HamNum / HamDenom)
    # 傳回屬于正常郵件類的條件機率數組，屬于垃圾郵件類的條件機率數組，文檔屬于垃圾郵件類的機率
    return HamVec, SpamVec, ori_auc

複制

預測函數：

# 預測函數
def predict(testDataVec, HamVec, SpamVec, ori_auc):
    predictToSpam = sum(testDataVec * SpamVec) + np.log(ori_auc)
    predictToHam = sum(testDataVec * HamVec) + np.log(1.0 - ori_auc)
    if predictToSpam > predictToHam:
        return 1
    else:
        return 0

複制

預測錯誤一個，錯誤率

10%

，正确率

90%

：

【機器學習】算法原理詳細推導與實作(三):樸素貝葉斯【機器學習】算法原理詳細推導與實作(三):樸素貝葉斯