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