[貝葉斯四]之貝葉斯分類器設計

03-02

<個人網頁blog已經上線，一大波乾貨即將來襲：https://faiculty.com/>

這一小節我們將簡單的闡述一般貝葉斯分類器設計的方法。分類器流程如下所示。

輸入：d-dim 特徵向量
計算決策函數值(針對每個類別)
選取最大的值
做出決策
輸出結果

如下圖可以清楚的表達整個分類器工作的流程。

借用《演算法雜貨鋪——分類演算法之樸素貝葉斯分類(Naive Bayesian classification)》的一張圖來表示整個設計的流程。

下面我們將以兩個小例子來貫穿貝葉斯分類器設計的整個流程。

一、MNIST手寫體識別

1.0 數據集簡介

MNIST是一個0-9的手寫數字資料庫。MNIST數據集中包含60000張手寫數字圖片，10,000 張測試圖片。每張圖片的大小為28*28，包含一個手寫數字。如下圖所示。數據集鏈接：http://yann.lecun.com/exdb/MNIST/。

數據集中包含四個文件。

1. train-images-idx3-ubyte.gz: training set images (9912422 bytes) 2. train-labels-idx1-ubyte.gz: training set labels (28881 bytes) 3. t10k-images-idx3-ubyte.gz: test set images (1648877 bytes) 4. t10k-labels-idx1-ubyte.gz: test set labels (4542 bytes)

整理一下MNIST數據集。

四個文件。train_image，train_label，test_image，test_label
圖像數據。2828的圖像尺寸的灰度圖像，所以每張圖像為2828*1
標籤。針對每個數據給出0-9中一個數字作為類別。

1.1、特徵向量準備

搞個三部曲：

數據準備
模型設計
模型訓練

貝葉斯決策論也不例外，首要的，我們需要將原始數據經過一系列清洗得到輸入的特徵向量。

咋輸入數據？

MNIST數據集四個文件是用二進位進行編寫，詳細的格式如下圖所示，展示image file 和 label file。

數據的預處理可以分為兩部分：第一部分就是讀入數據，第二部分就是提取成想要的特徵向量。（1）讀入數據。實驗中我們採用MATLAB編寫，利用文件指針逐個位元組讀取，得到一個mat，然後reshape到784N的數據形式，注意這裡得到的都是0-255像素。對於label也是同理得到N1的數據形式。（2）提取特徵向量。最後我們需要對讀入的數據進行處理得到我們想要的特徵向量。這裡實驗做法十分暴力，直接將圖像變成二值化(將0-255 resize到0、1)，然後向量長度不變。所以得到的形式是784*N的二值化的矩陣。Label不做任何處理。

這裡主要是闡述整個設計流程，所以直接用最簡單的方式提取特徵。感興趣的同學可以嘗試用PCA等特徵生成的方式將輸入的圖像做特徵提取。

1.2、決策函數設計

接下來是分類器設計的主要步驟：決策函數設計。首先我們從最頂層開始往下進行推導。貝葉斯分類的核心就是找到最大的後驗概率，也就是給出一個樣本 $x$ ，它屬於 $y_j$ 的概率最大，那麼我們就認為樣本 $x$ 是屬於第 $j$ 類的。由此我們的分類器設計的目標就是計算概率值 $p(y_j|x_i)$ .

下面我們先給出形式化的定義。

$D={x^{(i)}，y^{(i)} },i=1,2,3,4……n$ 表示我們的數據集；
$x^{(i)}$ 是784維的向量，表示第 $i$ 個樣本；
$y^{(i)}$ 是標註的第 $i$ 個樣本的類別，取值範圍是0-9；
${x_k}^{(i)}$ 表示第 $i$ 個樣本的第 $k$ 維。

決策函數定義一般情況下，貝葉斯都是採用了最小錯分準則，這裡也是如此。由此我們可以得到我們的目標決策函數。

$p(y=j|x)$

也就是說對於一個樣本 $x$ ，我們只需要計算出它們屬於每一類的後驗概率，並將樣本 $x$ 判定給後驗概率大的那一類 $j$ . 接下來我們就此解釋該如何計算出這個後驗概率，也就是模型的建立過程。

1.2.1 模型建立

根據最小錯分原則，所以我們的目標就是求解最大的後驗概率，由此得到結果類別。寫成公式如下。

$target = underset {j}{argmax} quad {p(y= j|x)}$

對於一個784維的樣本 $x$ ，它的每一維出現是相互獨立的（屬性之間相互獨立，也被稱為樸素貝葉斯）。由此我們可以將我們目標後驗概率寫成如下公式。

$p(y = j|x) = underset {k}{prod}p(y = j|{x_k})$

其中：

$x_k$ 表示樣本 $x$ 的第 $k$ 個元素

接下來轉換目標為求解每個像素點的相應後驗概率（也就是樣本每個元素的後驗概率）。根據貝葉斯公式，我們得到一個設計模型。該式子的意義為：針對一個樣本 $x$ 的第 $k$ 個元素出現，屬於第 $j$ 類樣本的概率。

$p(y=j|x_k) = frac{p(x_k|y=j)p(y=j)}{p(x_k)}$

這個模型非常好理解。我們要求的就是已知樣本第 $k$ 個元素(像素)情況下，這個樣本是屬於第j類的概率。這個概率就可以用貝葉斯得到。由此我們通過訓練樣本可以得到如下概率值(因為我們的特徵向量元素取值為0或者1)。

$p(x_k = 1) = frac {#圖片中第k個像素為1的個數}{#所有圖片的個數，n}$

$p(y=j) = frac {#屬於第j類的圖像數}{#所有圖片的個數，n}$

$egin{align} p(x_k=1|y=j) =& \ &frac {#屬於第j類的圖像而且第k個像素為1的圖像數量}{#屬於第j類圖像的個數} end{align}$

因為每個像素只可能為0或者1，所以我們直接計算的是像素為1的情況。由此我們的模型就已經建立了。Model中就是這三個根據訓練數據得到概率值，接下來我們將討論如何根據這個模型判斷某個樣本的類別。

1.2.2 模型測試

根據給出的訓練數據集，我們能計算出如上的 $p(x_k = 1)$ 、 $p(y=j)$ 和 $p(x_k=1|y=j)$ . 根據這幾個結果，我們得到了後驗概率 $p(y=j|x_k)$ .

問題是，針對測試樣本，我們該如何計算？這是該貝葉斯分類器設計中的核心，很多人覺得在這裡很繞。之前我們是根據給出的訓練數據計算出的一個模型，換句話有點像最大似然估計法：用有限的觀測數據來估計一個未知參數的模型。比如對於一個拋硬幣測試，我們想知道硬幣正反出現的概率模型，那麼我們經過大量的實驗，然後計算最大似然。由此得到一個模型參數。這裡也是一樣，我們得到的是叫做貝葉斯模型。根據這個模型，然後加上輸入的測試樣本，我們計算出最大的後驗概率。

假設這個時候來了一個樣本 $x$ ，對於這個樣本的第 $k$ 個元素顯然是服從二分布的，要不為1，要不為0。所以我們根據之前的模型計算中的後驗概率計算方法，首先計算出這個樣本低 $k$ 個元素的出現概率。

$p(x_k) = p(x_k=1)^{x}(1-p(x_k=1))^{1-x}$

$p(x_k = i)= egin{cases} frac {#圖片中第k個像素為1的個數}{#所有圖片的個數n} {qquad qquad } & ext {if $i$ is 1} \ frac {#圖片中第k個像素為0的個數}{#所有圖片的個數n} {qquad } & ext {if $i$ is 0} end{cases}$

同理，對於第 $j$ 類情況下，樣本 $x$ 的第 $k$ 個元素也是服從二分布的。由此我們可以得到如下的式子。

$egin{align} p(x_k|y=j) &= p(x_k=1|y=j)^{x_k} (1-p(x_k=1|y=j)^{(1-x_k)}) end{align}$

同理，用通俗易懂的式子描述如下。

$p(x_k=i|y=j)= egin{cases} frac {#屬於第j類的圖像而且第k個像素為1的圖像數量}{#屬於第j類圖像的個數} {qquad qquad qquad } & ext {if $i$ is 1} \ frac {#屬於第j類的圖像而且第k個像素為0的圖像數量}{#屬於第j類圖像的個數} {qquad qquad qquad } & ext {if $i$ is 0} end{cases}$

整理後，我們得到樣本 $x$ 出現的後驗概率為(這裡採用貝葉斯定理即可得到)。

$egin{align} p(y=j|x) &=underset{k}{prod}p(y=j|x_k)\ &=underset{k}{prod} frac {p(x_k|y=j)p(y=j)}{p(x_k)} ag 3 end{align}$

對於輸入的測試樣本 $x$ ，我們已知了每個元素的值 $x_k = i， i in {{0,1}}$ ，那麼我們將該值帶入到上式進行計算就好了。比如我們可以得到。

$frac {p(x_k=i|y=j)p(y=j)}{p(x_k=i)}$

由此就能計算出 $target = underset {j}{argmax} quad {p(y= j|x)}$ 。到此為止，我們決策函數的分析徹底結束。接下來就是模型的訓練。

1.3 模型訓練

這一部分主要就是工程問題，首先根據輸入的訓練數據，計算出上述的模型(也就是train文件)。然後寫一個輸入樣本得到預測結果的文件(也就是test文件)。

二、字母分類設計

接下來，趁熱打鐵，我們接著擼一個類似的例子。同學們可以根據需求，自己先推一邊。過程是一模一樣的。

數據集來自於UCI：UCI字母分類數據集鏈接

2.0 數據集分析

老套路，我們對數據集先做個簡單的分析，主要是知道數據集的數據形式，便於寫程序進行讀取和預處理。

這個數據集原始數據一共包含20000張圖像(一般取前16000張圖像作為訓練，後4000張圖像作為測試)，每張圖像經過作者處理後得到了一個16維的特徵(特徵值是一個0-15的整數)，標籤就是所代表的字母A-Z。數據形式如下：

1. lettr capital letter (26 values from A to Z) 2. x-box horizontal position of box (integer) 3. y-box vertical position of box (integer) 4. width width of box (integer) 5. high height of box (integer) 6. onpix total # on pixels (integer) 7. x-bar mean x of on pixels in box (integer) 8. y-bar mean y of on pixels in box (integer) 9. x2bar mean x variance (integer) 10. y2bar mean y variance (integer) 11. xybar mean x y correlation (integer) 12. x2ybr mean of x * x * y (integer) 13. xy2br mean of x * y * y (integer) 14. x-ege mean edge count left to right (integer) 15. xegvy correlation of x-ege with y (integer) 16. y-ege mean edge count bottom to top (integer) 17. yegvx correlation of y-ege with x (integer)

其中20000張圖像的分布如下：

1. 789 A 766 B 736 C 805 D 768 E 775 F 773 G 2. 734 H 755 I 747 J 739 K 761 L 792 M 783 N 3. 753 O 803 P 783 Q 758 R 748 S 796 T 813 U 4. 764 V 752 W 787 X 786 Y 734 Z

整理一下這個數據集。

一個文件。共20000條數據，我們將前16000條數據作為訓練數據，後4000條數據作為測試數據。
數據格式。16維的特徵向量，一個A-Z的label

2.1 特徵向量生成

由第1章問題的描述中我們可以知道，字母數據集已經幫我們做好了特徵向量提取的工作。數據形式如下所示。

由此我們只需要經過簡單的處理就能得到我們想要的數據。

Image數據。上圖所示每行16維向量，每個特徵值取值為0-15的整數。形式為16*N。
Label。上圖中每行第1列，A-Z。

Step1：數據讀入(loadData.m)

% load data from file, start --start line, end --end linefunction [labels, features] = loadData(filename,start,endl)[data1,data2,data3,data4,data5,data6,data7,data8,data9,data10,data11,data12,data13,data14,data15,data16,data17] = textread(filename, %c%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d,delimiter,,);labels = data1(start:endl,1);features = [data2,data3,data4,data5,data6,data7,data8,data9,data10,data11,data12,data13,data14,data15,data16,data17];features = features(start:endl,:);%labels = labels.;features = features. + 1;% 注意：這裡的下標是0~15end

2.2 決策函數

2.2.1 模型建立

我們需要訓練的模型跟上述數字手寫體分類一樣，目標如下。

$p(y=j|x)=underset{k}{prod}p(y=j|x_k)$

物理解釋是：針對每個輸入測試樣本，我們需要求解一個它屬於j類的後驗概率，這個後驗概率等於16維特徵屬於j類的後驗概率。 $p(y=j|x_k)$ 是代表：給出樣本 $x$ 的第 $k$ 的元素，那麼這個元素屬於第 $j$ 類中實例的概率。因為我們認為每個樣本特徵之間是相互獨立的，所以採用乘法。

由此我們的目標就變成了如何計算這個樣本第 $k$ 個元素值屬於第 $j$ 類的後驗概率問題。

$p(y=j|x_k) = frac {p(x_k|y=j)p(y=j)}{p(x_k)}$

其中：

$p(y=j)$ 表示類別 $j$ 出現的概率
$p(x_k = j)$ 表示樣本第 $k$ 個元素為 $i$ 的概率 $p(x_k=i) = frac {# 樣本中第k個元素為i的樣本數}{#樣本總數}$
$p(x_k=i|y=j)$ 表示樣本屬於第 $j$ 類情況下第 $k$ 個元素的值為 $i$ 的概率 $p(x_k=i|y=j) = frac {# 第j類樣本中第k個元素為i的樣本數}{#第j類樣本總數}$

這個就是我們需要訓練的模型。

Step2: 訓練模型(bc_train.m)

function [model] = bc_train(x, y, J)[K,N] = size(x); %K為維度，N為樣本數% p(w): 類別 i 出現的概率py = zeros(J,1);for i=1:J py(i,:) = sum(y == i)/N;end% p(x_k_i): 樣本中第k個元素為i的個數 / 樣本總數pki = zeros(16,16);for k=1:16 for i=1:16 pki(k,i) = sum(x(k,:) == i)/N; endend% p(x_k_i | j): 第j類樣本中第k個元素為i的樣本數 / 第j類樣本總數pkij = zeros(16,16,J);for j=1:J for k=1:16 xj = x(:,y==j); %屬於第j類的樣本 for i=1:16 pkij(k,i,j) = sum(xj(k,:)==i)/size(xj,2); end endendmodel.pki = pki;model.py = py;model.pkij = pkij;end

2.2.2 模型測試

假定給出一個樣本 $x$ ，我們可以根據每個特徵的值計算出屬於第 $j$ 類的後驗概率。

$p(y=j|x_k = i) = frac {p(x_k = i|y=j)p(y=j)}{p(x_k=i)}$

上式中，給出的測試樣本 $x$ 顯然是確定的，所以 $x_k=i$ 中 $i$ 值是一個確定值。根據上述得到的model，我們就能計算出屬於第j類的後驗概率了。最後將特徵值的後驗概率相乘，取最大值所在的類，就是我們計算得到的類別。

其中，runChar.m文件為主程序，代碼如下：

經測試，模型在測試集上的分類正確率為：73.43%。

Step3: 測試數據(bc_predict.m)

function [yp] = bc_predict(model,x,J)[K,N] = size(x);pki = model.pki;py = model.py;pkij = model.pkij;% p(y_j|i): 樣本第i個元素為 x(:,i) 情況下，類別為j的概率pyji = zeros(J,16,N);for j=1:J for i = 1:16 for n=1:N pyji(j,i,n) = pkij(i,x(i,n),j) * py(j) / pki(i,x(i,n)); end endendresult = prod(pyji,2);yp = zeros(N,1);for i=1:N [m,yp(i,:)] = max(result(:,:,i));end

Step4: 主程序(runChar.m)

clearclc%% Step1: read data[train_labels,train_char] = loadData(./char/letter-recognition.data.txt,1,16000);[test_labels,test_char] = loadData(./char/letter-recognition.data.txt,16001,20000);%% Step2: train modeltrain_labels = train_labels - A + 1;model = bc_train(train_char, train_labels, 26);%% Step3: predicttest_labels = test_labels - A + 1;yp = bc_predict(model,test_char,26);accuary_test = sum(yp == test_labels) / length(test_labels);

#四、參考文獻

[1] MNIST handwritten digit database, Yann LeCun, Corinna Cortes and Chris Burges.下載鏈接

[2] UCI Machine Learning Repository: Letter Recognition Data Set.下載鏈接

[3] Using the MNIST Dataset.下載鏈接

[4] 周志華. 《機器學習》[M]. 清華大學出版社, 2016.

[5] 李航. 《統計學習方法》[M].清華大學出版社,2013.

[6]機器學習之貝葉斯分類器

[7]機器學習通俗入門-樸素貝葉斯分類器

PS：如需數據和代碼請上faiculty留言