自己動手寫貝葉斯分類器給圖書分類
原文出處： 電流
背景與目的
首先，這是一個機器學習初學者兼非數學科班出身的非典型工程師的自學記錄。所以本文不會特別理論，也不會太深入地講解公式，但是會非常有目的性，針對一個特別現實的問題，從頭開始分享解決方案，包括某些優化方案。
從問題開始
我們要解決的問題，是對圖書進行二元分類。分類的依據是圖書的tag。這些tag可能來自專家，或者編輯，或者用戶。例如“外國文學”，“偵探”，“計算機”，“python”都屬于tag。
出于我們的小小實驗項目的需求，簡化問題，我們現在要把圖書分為“人文”或者“非人文”兩類。所以，正如上文所說，這是一個對圖書進行的二元分類問題。
例如，《計算機科學導論》，它的標簽有“計算機”“科學”“經典”“導論”，它屬于“非人文”。《麥田里的守望者》，它的標簽有“小說”“文學”“美國”，它屬于“人文”。我們的分類器有能力根據一本書的標簽，自動地將其歸類為“人文”或者“非人文”。試試看，蠻有意思的！
為了解決這個問題，我們給出若干個前提：
- 任何一本書只可能歸類為“人文”或“非人文”中的一類
- 1本書有1個或以上的tag
- 所有書都沒有“人文”和“非人文” 的tag（什么？你不相信？看看亞馬遜京東就知道了）
- 你需要很少的概率知識，比如什么是概率？條件概率又是什么？ </ul>
- p(tag1,tag2,tag3…|cate1)的值，也就是你知道在一本書已經被分類為“人文”的情況下，tag1,tag2,tag3…一起出現的概率
- p(cate1)，也就是所有被標記為“人文”分類的書，（在訓練集中）在所有書（“人文”和“非人文”）中出現的概率
- p(tag1,tag2,tag3…)，也就是tag1,tag2,tag3…（在訓練集）所有tag中出現的概率
- 什么是樸素貝葉斯
- 為了施行樸素貝葉斯分類，應該如何準備訓練集，其中tag集是非常重要的
- 在訓練數據的基礎上，得到每個tag在“人文”和“非人文”中的出現概率
- 利用這些出現概率，為新的文章進行分類
- 巧妙利用對數和一些初始值（例如ones()）來為算法做一些優化
使用python和numpy
我們將使用python作為這個實驗項目的編程語言。
numpy是一個python的科學計算庫，需要你自行安裝。因為我們的程序涉及一些簡單的矩陣運算，用numpy可以大大簡化編程工作量。
基本原理
貝葉斯分類器的工作原理
還是需要了解一定的理論知識的，別擔心，這部分很快就過去。我會直接結合要解決的問題來講解。
基本上，用貝葉斯分類是要解決一個這樣的問題：已知一本書有這些tag：tag1,tag2,tag3……它屬于“人文”分類的概率是多少？屬于“非人文”分類的概率呢？
假設p1表示在這種情況下，它屬于“人文”的概率，p2表示這種情況下，它屬于“非人文”的概率。
如果p1>p2，那么這本書就屬于“人文”，反過來就是“非人文”。我們不考慮p1=p2的情況。
很簡單，不是么？
所以，問題就變成了，如何通過tag1,tag2,tag3…來計算p1和p2？畢竟，只要知道了這兩個值，我們的最終問題就解決了。
條件概率
其實，這是一個條件概率的問題。所謂條件概率，就是求：在已知b發生的情況下，a發生的概率。我們寫做：p(a|b)。
結合我們的實際問題，那就是在tag1,tag2,tag3…已經發生的情況下（也就是這本書的tag就是tag1,tag2,tag3…），這本書屬于“人文”和“非人文”的概率。我們寫做：
p(cate1|tag1,tag2,tag3…) 意思是在tag1,tag2,tag3…發生的情況下，這本書屬于cate1的概率（cate1＝“人文”）
p(cate2|tag1,tag2,tag3…) 意思是在tag1,tag2,tag3…發生的情況下，這本書屬于cate2的概率（cate2=“非人文”）
這里的p(cate1|tag1,tag2,tag3…)其實就是上面說的p1,我們這里用更為專業的方法來寫。
條件概率怎么求呢？這就是貝葉斯公式：
|
1
|
p(a|b) = p(b|a) * p(a) / p(b)
|
這個意思就是：想要求p(a|b)，而你又知道p(b|a)，p(a)和p(b)的值，那你就可以通過p(b|a)*p(a)/p(b)來求得p(a|b)。
換成我們要解決的實際問題，等于：
|
1
|
p(cate1|tag1,tag2,tag3...) = p(tag1,tag2,tag3...|cate1) * p(cate1) / p(tag1,tag2,tag3...)
|
翻譯為人話，那就是你想求p(cate1|tag1,tag2,tag3…)，而你現在知道：
也就是說，我們只要挨個求出上述3項，我們就可以求出p(cate1|tag1,tag2,tag3…)了。同樣，p(cate2|tag1,tag2,tag3…)也可以求出。
這里有個值得注意的技巧，上述3項中，其實第3項不需要我們計算。因為我們的目的是比較p(cate1|tag1,tag2,tag3…)與p(cate2|tag1,tag2,tag3…)的大小，不是為了得到實際的值，由于上述公式里的分母p(tag1,tag2,tag3…)是一樣的，所以，我們只需要比較分子的大小就可以了。也就是比較：
p(tag1,tag2,tag3…|cate1) * p(cate1)，
與p(tag1,tag2,tag3…|cate2) * p(cate2)的大小
這樣可以省去我們一些計算。
樸素貝葉斯
那么，如何計算p(tag1,tag2,tag3…|cate1)呢？這里要用到樸素貝葉斯的概念，就是說，我們認為，在一本書中的標簽里，每個標簽都是相互獨立的，與對方是否出現沒有關系。也就是說“計算機”和“經典”出現的概率互不相關，不會因為“計算機”出現了就導致“經典”出現的概率高。
既然是相互獨立，那么，p(tag1,tag2,tag3…|cate1)就等于：
|
1
|
p(tag1|cate1) x p(tag2|cate1) x p(tag3|cate1) x ...
|
p(tag1,tag2,tag3…|cate2)就等于：
|
1
|
p(tag1|cate2) x p(tag2|cate2) x p(tag3|cate2) x ...
|
也就是說，我們可以計算每一個tag，分別在“人文”和“非人文”書籍的所有tag中出現的概率，然后將它們乘起來，就得到我們想要的。
舉例分析
我們現在有一本書《計算機科學導論》，它的標簽是“計算機”“科學”“理論”“經典”“導論”，我們想知道在這幾個標簽出現的情況下，《計算機科學導論》分別屬于“人文”和“非人文”的概率。
那么，我們已經有了什么呢？幸運的是，我們目前手頭有10本書，已知其中6本是“人文”，4本是“非人文”。這10本書，經過排重，一共有70個不同的標簽，“計算機”，“科學”，“理論”，“導論”也在其中。
基于此，我們可以得出，p(cate1)=6/10=0.6，p(cate2)=1-0.6=0.4。也就是說“人文”書在所有書中的概率是0.6，“非人文”是0.4。
接下來就是p(tag1,tag2,tag3…|cate1)和p(tag1,tag2,tag3…|cate2)了。也就是，我們要算出，在“人文”類里的所有書中，“計算機”“科學”“理論”“經典”“導論”這幾個tag在“人文”書的所有tag里出現的概率。同樣，我們還要算出，在“非人文”類里的所有書中，上述這幾個tag在所有“非人文”書中的所有tag里出現的概率。計算的方法，就是將每個tag在“人文”和“非人文”中出現的概率，相乘，然后再分別乘以0.6和0.4。
然后比較一下大小就可以了。也就是比較p(cate1) x p(tag1,tag2,tag3…|cate1)與p(cate2) x p(tag1,tag2,tag3…|cate2)的大小。
開始動手
1.準備訓練集
幾乎所有的機器學習都需要訓練集。貝葉斯分類也一樣。事實上，我們上面所說的我們##已知##的數據，就是訓練集。上面例子中舉出的那10本書，以及這10本書所有排重后的tag，就是我們的訓練集；而0.6和0.4這兩個概率，還有p1(tag1,tag2,tag3…|cate1)和p2(tag1,tag2,tag3…|cate2)，就是我們基于訓練集的數據計算出來的，機器學習管這叫“訓練”。
基于我們的問題，我們需要準備100本書，人為地分為“人文”和“非人文”兩類，并且收集將這些書的所有tag。這些書如何獲得？你可以爬取亞馬遜或者豆瓣上的書籍資源。
2.形成tag集
將上述所說的tag，用python里的列表來保存，我們令其為dicts.dicts里的每一個元素是一個tag，例如：
|
1
|
dicts = ['科學','理論','c++']這樣的形式。
|
3.計算訓練集中“人文”和“非人文”的概率
非常簡單，如我們的例子所說，假設這訓練集中的這100本書，有60本是“人文”，那么p(cate1)=60/100=0.6。p(cate2)=1-p(cate1)=0.4。這里我們用變量:
|
1
2
|
pcate1 = 0.6
pcate2 = 0.4
|
4.計算tag集中每個tag在訓練集“人文”書籍中的tag出現的概率
首先，我們基于訓練集構造一個列表，這個列表里的每一項又是一個列表，這個列表里的每一項，不是1就是0。1表示這個詞典中這個位置的tag是這本書的一個tag。
舉例：假設我們的dicts是這樣的：
|
1
2
3
4
5
6
7
|
['計算機','小說','心理','科學','編程','行為','導論','經典','游記','美國']
我們有這樣一個列表：tag_vector_cate1
[
[0,1,0,0,0,0,0,1,1],
[0,0,1,0,0,0,0,1,0],
..............
]
|
這個列表對應的是“人文”類。
每一行代表訓練集中“人文”類的一本書。第一行對應的書是《麥田里的守望者》，它的標簽是“小說”，“經典”，“美國”。第二行對應的書是《可預測的非理性》，它的標簽是“心理”，“行為”，“美國”。注意，我們是用整個tag集dicts來表示一本書的tag。所以，第一行第1列(我們從0開始計數)的1，表示《每天里的守望者》有一個’小說’的tag(對應dicts里的第1列)；第一行第2列的0，表示《麥田里的守望者》這本書沒有’心理’這個tag(對應dicts里的第2列)。同理，我們看到第一行和第二行的第7列都是1，說明《麥田里的守望者》和《可預測的非理性》都有’美國’這個tag。
有了這樣的數據，我們就很好計算了。現在以計算p(tag1|cate1)為例。對于tag1，我們計算出在訓練集里“人文”的所有書中，tag1出現了多少次。例如：在訓練集里，“人文”有60本，其中40本書都有“經典”這個tag，那么我們就令num_of_tag1=40。按照這個方法，我們求出每個tag出現了多少次，比如：num_of_tag2=32,num_of_tage=18……
然后，我們求出在“人文”類里，所有書的tag標簽總數（注意這里是不排重的）。例如“人文”類有2本書，第一本書的標簽是“散文”“經典”“外國”，第二本是“經典”“小說”。那么，所有書的tag標簽總數就是3+2=5。現在，我們求出訓練集里所有100本的tag標簽總數。假設總數是700。我們令total_cate1=700。
于是，tag1在“人文”類里出現的概率：p(tag1|cate1) = num_of_tag1 / total_cate1 = 40/700 = 0.057。同理，我們得出p(tag2|cate1)，p(tag3|cate1)…
利用numpy，我們可以很方便地用幾句代碼來實現這個過程。
|
1
2
3
4
5
6
7
|
from numpy import *
num_tags_cate1 = ones(len(dicts)) #(1)
total_cate1 = 2.0 #(2)
for item in tag_vector_cate1:
num_tags_cate1 += item #(3)
total_cate1 += sum(item) #(4)
p_tags_cate1 = num_tags_cate1 / total_cate1 #(5)
|
這里做一下說明。
(1)代碼，表示生成一個numpy數組。ones()是numpy的函數，返回一個填充了數值1的numpy數組，參數是這個數組的長度。例如：temp=ones(3)，表示生成了一個numpy數組[1,1,1]并返回給了temp。所以，(1)代碼就是以訓練集的tag集dicts的長度為參數，生成一個和dicts等長的填充了1的numpy數組，返回給num_tags_cate1。為什么要和dicts登長？還記得吧，我們是以整個字典集來表示一本書的。我們要計算的就是這個dicts里的每一個tag的概率，并放到一個數組里。num_tags_cate1就是這個數組。至于這個數組為什么要填充1，稍后會說明。
(2)total_cate1 = 2.0。total_cate1是分母，分母不能是0，所以我們要令其初始值不為0。為什么是2.0？稍后會說明。
(3)num_tags_cate1 += item。item顯然是一個python的列表，就是我們剛才說的[0,1,0,0,0,0,0,1,1]。當你用一個numpy數組加上一個python的list時，numpy會幫你做對應項目的計算，相當于重載了＋。例如，a是一個numpy數組：[1,2,3,5,0]，b是一個python的list：[0,0,3,2,1]。a + b = [1,2,6,7,1]，結果是一個numpy數組。在這個例子里，相當于“小說”，“經典”，“美國”這3個標簽的數量分別增加了1。
(4)把每本書出現的所有tag的數量相加。sum(item)也是numpy的函數，作用是將item里的每一項相加。例如：sum([2,5,-1])，其結果2+5+(-1)=6。假如item是這樣的一個list：[0,1,0,0,0,0,0,1,1]，對應的是《麥田里的守望者》，它的標簽分別是“小說”“經典”“美國”，相當于標簽總數增加了3。
(5)很明顯，我們用num_tags_cate1去除以total_cate1，這也是numpy重載了“/”運算符，例如[2,4,6]/2，相當于每一項分別除以2，最后得到一個numpy數組，也就是[1,2,3]。在這個例子里，就相當于我們分別用tag1,tag2,tag3…出現的次數去除以標簽的總數量，并得到一個numpy數組p_tags_cate1。這個數組里的每一項是一個概率值，代表其對應的tag在cate1（“人文”）類別里出現的概率。
同樣，我們可以計算出p_tags_cate2。也就是每個tag在cate2（“非人文”）里出現的概率。
5.現在我們有什么
來到這里，我們已經有了幾乎所有的東西。回憶一下貝葉斯分類的公式：
|
1
|
p(cate1|tag1,tag2,tag3...) = p(tag1,tag2,tag3...|cate1) x p(cate1) / p(tag1,tag2,tag3...)
|
我們前面討論過，分子可以忽略，不計算，也就是不需要理會分母p(tag1,tag2,tag3…)。
進一步地，按照樸素貝葉斯理論，分子等于：
|
1
|
p(tag1,tag2,tag3...|cate1) x p(cate1) = p(tag1|cate1) x p(tag2|cate1) x p(tag3|cate1) x ... x p(cate1)
|
p(cate1)就是等于上面所說的pcate1。
p(tag1|cate1)，p(tag2|cate1)……就是我們上面得出的numpy數組p_tags_cate1里的每一項。我們只需要把它們相乘起來，就得到p(tag1|cate1) x p(tag2|cate1) x …… !
來到這里，我們要解釋一下，為什么上文的代碼用1來填充num_tags_cate1。如果我們用0來填充，當某個tag一直為0時（雖然理論上不可能出現），整個分子相乘的結果為0，這樣最后的值就變為0了，影響了結果。所以，為了避免這種情況，我們認為每個tag至少要出現1次，所以我們用ones來填充。這樣，最壞情況下，num_tags_cate1=[1,1,1,.....]。
而total_cate1=2.0，就是對應當num_tags_cate1=[1,1,1,...]時，那么我們認為每個tag出現的概率是0.5（1/2.0），這是一個可以調節的參數，但是要記住不要令total_cate1=1.0。如果這樣，那么每個tag出現的概率變成1了，大有問題。
6.利用訓練得出的數據給新書進行分類
終于完成了貝葉斯分類器，現在我們看看如何給新書分類。
所謂給新書分類，就是當已經完成了訓練集的訓練后（還記得吧？那100本手工分類的書就是訓練集），這時候，我們要對第101本書進行分類。這本書不是訓練集里的書，是新書。我們基于前面計算出來的公式里的幾個元素，來對它進行分類。
同樣的，我們抽取新書的標簽，并用python里的list來保存，記作：tagvects，它的形式如：[1,0,0,1,0,0,1....]。
接著，我們讓p_tags_cate1里的每個項乘以對應的tagvects里的項：
|
1
|
results_tags_cate1 = p_tags_cate1 * tagvects
|
再令num_tags_cate1里的每一項相乘：
|
1
2
3
4
|
temp1 = 1.0
for item in results_tags_cate1:
if item != 0:
temp1 = temp1 * item
|
同樣的方法，計算出temp2：
|
1
2
3
4
5
|
results_tags_cate2 = p_tags_cate2 * tagvects
temp2 = 1.0
for item in results_tags_cate2:
if item != 0:
temp2 = temp2 * item
|
最后，這樣：
|
1
2
3
4
5
6
|
p_cate1_tags = temp1 * pcate1
p_cate2_tags = temp2 x pcate2
if p_cate1_tags > p_cate2_tags:
print '人文'
else:
print '非人文'
|
顯然，我們通過比較p_cate1_tags與p_cate2_tags的大小，就可以為新書進行分類了，哪邊的值大，就分到哪邊。
優化trick
由于上面的公式，是多個概率相乘，當你的tag集dicts的長度非常大時（也就是你的書的標簽特別多時），這是個很可怕的做法，由于每一項都是小數，這么多小數相乘，將可能出現溢出，或者數太小導致計算結果為0。這時候，需要一個trick，來做一下優化，避免這種情況。
我們取數學上非常流行的做法，取對數ln，來改善我們的算法。在python里，取對數的函數是log()。
可以在幾個地方取對數。這里推薦這樣的做法，把要計算的式子變成：
|
1
|
ln(p(tag1|cate1) * p(tag2|cate1) *....* p(cate1)))
|
展開來，就變成：
|
1
|
ln(p(tag1|cate1)) + ln(p(tag2|cate1)) + ... + ln(pcate1)
|
回憶一下，p(tag1|cate1),p(tag2|cate1)…是我們上面算出的p_tags_cate1的每一項（p_tags_cate1是numpy數組，其中每一項表示對應的tag在“人文”分類中出現的概率）。在我們上面的計算中：
|
1
|
p_tags_cate1 = num_tags_cate1 / total_cate1
|
現在我們對其取對數，于是，改代碼改為：
|
1
|
p_tags_cate1 = log(num_tags_cate1 / total_cate1)
|
注意，這里的log，是對numpy的數組中的每一項求log，結果還是一個數組。
于是，p_tags_cate1就成為了取對數后的數組。
然后求ln(pcate1)，把pcate1變為：
|
1
|
pcate1 = log(pcate1)
|
所以，上面最后分類的代碼就改為：
|
1
2
3
4
5
|
results_tags_cate1 = p_tags_cate1 * tagvects
temp1 = 1.0
for item in results_tags_cate1:
if item != 0:
temp1 = temp1 + item
|
同樣的方法，計算出temp2：
|
1
2
3
4
5
|
results_tags_cate2 = p_tags_cate2 * tagvects
temp2 = 1.0
for item in results_tags_cate2:
if item != 0:
temp2 = temp2 + item
|
然后就可以分類了：
|
1
2
3
4
5
6
|
p_cate1_tags = temp1 + pcate1
p_cate2_tags = temp2 + pcate2
if p_cate1_tags > p_cate2_tags:
print '人文'
else:
print '非人文'
|
總結
很高興你終于來到了這里。本文力求簡潔，盡量降低學習成本。但是肯定存在第一次閱讀還覺得有些不太理解的可能，這是正常的，凡事總有個過程，尤其是機器學習這個領域，需要你反復咀嚼和思考以及實踐。攥寫本文的過程中，我也在反復加深對貝葉斯分類的理解，但是表達出來，還是有不太清晰的地方。如果你有不解或者建議，歡迎與我多討論。
通過本文，我們明白了：