贝叶斯算法之⽂本分类
第1章贝叶斯原理
1.1 贝叶斯公式
设A、B是两个事件，且P(A)>0，称
乘法公式 P(XYZ)=P(Z|XY)P(Y|X)P(X)
全概率公式 P(X)=P(X|Y1)+ P(X|Y2)+…+ P(X|Y n)
贝叶斯公式
以上公式，请读者参考的1.4节“条件概率”（这⾥将原书中的A换成了X，B换成了Y），获得更深的理解。
1.2贝叶斯定理在分类中的应⽤
在分类（classification）问题中，常常需要把⼀个事物分到某个类别。⼀个事物具有很多属性，把它的众多属性看做⼀个向量，即x=
(x1,x2,x3,…,x n)，⽤x这个向量来代表这个事物。类别也是有很多种，⽤集合Y={y1,y2,…y m}表⽰。如果x属于y1类别，就可以给x打上y1标签，意思是说x属于y1类别。这就是所谓的分类(Classification)。
x的集合记为X，称为属性集。⼀般X和Y的关系是不确定的，你只能在某种程度上说x有多⼤可能性属于类y1，⽐如说x有80%的可能性属于类y1，这时可以把X和Y看做是随机变量，P(Y|X)称为Y的后验概率（posterior probability），与之相对的，P(Y)称为Y的先验概率（prior probability）[2]。 在训练阶段，我们要根据从训练数据中收集的信息，对X和Y的每⼀种组合学习后验概率P(Y|X)。分类时，来了⼀个实例x，在刚才训练得到的⼀堆后验概率中出所有的P(Y|x)， 其中最⼤的那个y，即为x所属分类。根据贝叶斯公式，后验概率为
在⽐较不同Y值的后验概率时，分母P(X)总是常数，因此可以忽略。先验概率P(Y)可以通过计算训练集中属于每⼀个类的训练样本所占的⽐例容易地估计。 我们来举个简单的例⼦，让读者对上述思路有个形象的认识[3]。
考虑⼀个医疗诊断问题，有两种可能的假设：（1）病⼈有癌症。（2）病⼈⽆癌症。样本数据来⾃某化验测试，它也有两种可能的结果：阳性和阴性。假设我们已经有先验知识：在所有⼈⼝中只有0.008的⼈患病。此外，化验测试对有病的患者有98%的可能返回阳性结果，对⽆病患者有97%的可能返回阴性结果。
上⾯的数据可以⽤以下概率式⼦表⽰：
P(cancer)=0.008,P(⽆cancer)=0.992
P(阳性|cancer)=0.98,P(阴性|cancer)=0.02密码文具盒
P(阳性|⽆cancer)=0.03，P(阴性|⽆cancer)=0.97化尸池
假设现在有⼀个新病⼈，化验测试返回阳性，是否将病⼈断定为有癌症呢？
在这⾥，Y={cancer，⽆cancer}，共两个类别，这个新病⼈是⼀个样本，他有⼀个属性阳性，可以令x=(阳性)。
我们可以来计算各个类别的后验概率：
P(cancer | 阳性) = P(阳性 | cancer)p(cancer)=0.98*0.008 = 0.0078
P(⽆cancer | 阳性) =P(阳性 | ⽆cancer)*p(⽆cancer)=0.03*0.992 = 0.0298
因此，应该判断为⽆癌症。
在这个例⼦中，类条件概率，P(cancer|阳性)和P(⽆cancer|阳性)直接告诉了我们。
⼀般地，对类条件概率P(X|Y)的估计，有朴素贝叶斯分类器和贝叶斯信念⽹络两种⽅法，这⾥介绍朴素贝叶斯分类器。
1.3朴素贝叶斯分类器
1、条件独⽴性
给定类标号y，朴素贝叶斯分类器在估计类条件概率时假设属性之间条件独⽴。条件独⽴假设可以形式化的表达如下：
其中每个训练样本可⽤⼀个属性向量X=(x1,x2,x3,…,x n)表⽰，各个属性之间条件独⽴。
⽐如，对于⼀篇⽂章，
Good good study,Day day up.
可以⽤⼀个⽂本特征向量来表⽰，x=(Good, good, study, Day, day , up)。⼀般各个词语之间肯定不是相互独⽴的，有⼀定的上下⽂联系。但在朴素贝叶斯⽂本分类时，我们假设个单词之间没有联系，可以⽤⼀个⽂本特征向量来表⽰这篇⽂章，这就是“朴素”的来历。投票箱制作
2、朴素贝叶斯如何⼯作
有了条件独⽴假设，就不必计算X和Y的每⼀种组合的类条件概率，只需对给定的Y，计算每个xi的条件概率。后⼀种⽅法更实⽤，因为它不需要很⼤的训练集就能获得较好的概率估计。
3、估计分类属性的条件概率
P(x i|Y=y)怎么计算呢？它⼀般根据类别y下包含属性xi的实例的⽐例来估计。以⽂本分类为例，xi表⽰⼀个单词，P(x i|Y=y)=包含该类别下包含单词的xi的⽂章总数/ 该类别下的⽂章总数。
4、贝叶斯分类器举例
假设给定了如下训练样本数据，我们学习的⽬标是根据给定的天⽓状况判断你对PlayTennis这个请求的回答是Yes还是No。
Day Outlook Temperature Humidity Wind PlayTennis
D1Sunny Hot High Weak No
D2Sunny Hot High Strong No
D3Overcast Hot High Weak Yes
D4Rain Mild High Weak Yes
D5Rain Cool Normal Weak Yes
D6Rain Cool Normal Strong No
D7Overcast Cool Normal Strong Yes
D8Sunny Mild High Weak No
D9Sunny Cool Normal Weak Yes
D10Rain Mild Normal Weak Yes
D11Sunny Mild Normal Strong Yes
D12Overcast Mild High Strong Yes
D13Overcast Hot Normal Weak Yes
D14Rain Mild High Strong No
可以看到这⾥样本数据集提供了14个训练样本，我们将使⽤此表的数据，并结合朴素贝叶斯分类器来分类下⾯的新实例：
x = (Outlook = Sunny,Temprature = Cool,Humidity = High,Wind = Strong)
在这个例⼦中，属性向量X=(Outlook, Temperature, Humidity, Wind)，类集合Y={Yes, No}。我们需要利⽤训练数据计算后验概率
P(Yes|x)和P(No|x)，如果P(Yes|x)>P(No|x)，那么新实例分类为Yes，否则为No。
为了计算后验概率，我们需要计算先验概率P(Yes)和P(No)和类条件概率P(xi|Y)。
因为有9个样本属于Yes，5个样本属于No，所以P(Yes)=9/14, P(No)=5/14。
类条件概率计算如下：
P(Outlook = Sunny|Yes)=2/9 P(Outlook = Sunny|No)=3/5
P(Temprature = Cool |Yes) =3/9 P(Temprature = Cool |No) =1/5
P(Humidity = High |Yes) =3/9 P(Humidity = High |No) =4/5
P(Wind = Strong |Yes) =3/9 P(Wind = Strong |No) =3/5
后验概率计算如下：
P(Yes | x)= P(Outlook = Sunny|Yes)×P(Temprature = Cool |Yes)×P(Humidity = High |Yes)×P(Wind = Strong
|Yes)×P(Yes)=2/9×3/9×3/9×3/9×3/9×9/14=2/243=9/1701≈0.00529
P(No | x)= P(Outlook = Sunny|No)×P(Temprature = Cool |No)×P(Humidity = High |No)× P(Wind = Strong
|No)×P(No)=3/5×1/5×4/5×3/5×5/14=18/875≈0.02057
通过计算得出P(No | x)> P(Yes | x)，所以该样本分类为No[3]。
5、条件概率的m估计超前支架
假设有来了⼀个新样本 x1= (Outlook = Cloudy,Temprature = Cool,Humidity = High,Wind = Strong)，要求对其分类。我们来开始计算，
P(Outlook = Cloudy|Yes)=0/9=0 P(Outlook = Cloudy |No)=0/5=0
计算到这⾥，⼤家就会意识到，这⾥出现了⼀个新的属性值，在训练样本中所没有的。如果有⼀个属性的类条件概率为0，则整个类的后验概率就等于0，我们可以直接得到后验概率P(Yes | x1)= P(No | x1)=0，这时⼆者相等，⽆法分类。
半透明纸
当训练样本不能覆盖那么多的属性值时，都会出现上述的窘境。简单的使⽤样本⽐例来估计类条件概率的⽅法太脆弱了，尤其是当训练样本少⽽属性数⽬⼜很⼤时。
解决⽅法是使⽤m估计(m-estimate)⽅法来估计条件概率：
n是类y j中的样本总数，n c是类y j中取值x i的样本数，m是称为等价样本⼤⼩的参数，⽽p是⽤户指定的参数。如果没有训练集（即n=0），则P(x i|y j)=p, 因此p可以看作是在类yj的样本中观察属性值xi的先验概率。等价样本⼤⼩决定先验概率和观测概率n c/n之间的平衡[2]。
第2章朴素贝叶斯⽂本分类算法
现在开始进⼊本⽂的主旨部分：如何将贝叶斯分类器应⽤到⽂本分类上来。
2.1⽂本分类问题
在⽂本分类中，假设我们有⼀个⽂档d∈X，X是⽂档向量空间(document space)，和⼀个固定的类集合C={c1,c2,…,cj}，类别⼜称为标签。显然，⽂档向量空间是⼀个⾼维度空间。我们把⼀堆打了标签的⽂档集合<d,c>作为训练样本，<d,c>∈X×C。例如：
<d,c>={Beijing joins the World Trade Organization, China}
对于这个只有⼀句话的⽂档，我们把它归类到 China，即打上china标签。
我们期望⽤某种训练算法，训练出⼀个函数γ，能够将⽂档映射到某⼀个类别：
γ:X→C
这种类型的学习⽅法叫做有监督学习，因为事先有⼀个监督者（我们事先给出了⼀堆打好标签的⽂档）像个⽼师⼀样监督着整个学习过程。
朴素贝叶斯分类器是⼀种有监督学习，常见有两种模型，多项式模型(multinomial model)和伯努利模型(Bernoulli model)。
2.2多项式模型
在多项式模型中， 设某⽂档d=(t1,t2,…,t k)，t k是该⽂档中出现过的单词，允许重复，则
先验概率P(c)= 类c下单词总数/整个训练样本的单词总数
类条件概率P(t k|c)=(类c下单词t k在各个⽂档中出现过的次数之和+1)/(类c下单词总数+|V|)
V是训练样本的单词表（即抽取单词，单词出现多次，只算⼀个），|V|则表⽰训练样本包含多少种单词。在这⾥，m=|V|, p=1/|V|。P(t k|c)可以看作是单词t k在证明d属于类c上提供了多⼤的证据，⽽P(c)则可以认为是类别c在整体上占多⼤⽐例(有多⼤可能性)。
2、伪代码
//C，类别集合，D，⽤于训练的⽂本⽂件集合
TrainMultiNomialNB(C,D) {
// 单词出现多次，只算⼀个
V←ExtractVocabulary(D)
// 单词可重复计算
N←CountTokens(D)
for each c∈C
// 计算类别c下的单词总数
// N和Nc的计算⽅法和Introduction to Information Retrieval上的不同，个⼈认为
//该书是错误的，先验概率和类条件概率的计算⽅法应当保持⼀致
Nc←CountTokensInClass(D,c)
prior[c][/c]←Nc/N
// 将类别c下的⽂档连接成⼀个⼤字符串
text c←ConcatenateTextOfAllDocsInClass(D,c)
for each t∈V
/
/ 计算类c下单词t的出现次数
T ct←CountTokensOfTerm(text c,t)
for each t∈V
//计算P(t|c)
condprob[t][c][/c]←
return V,prior,condprob
}
ApplyMultiNomialNB(C,V,prior,condprob,d) {
// 将⽂档d中的单词抽取出来，允许重复，如果单词是全新的，在全局单词表V中都
// 没出现过，则忽略掉
W←ExtractTokensFromDoc(V,d)
设备防护箱score[c][/c]←prior[c][/c]
for each t∈W
if t∈Vd
score[c][/c] *= condprob[t][c][/c] return max(score[c][/c])
}
3、举例
给定⼀组分类好了的⽂本训练数据，如下：
docId doc 类别
In c=China?
1Chinese Beijing Chinese yes
2Chinese Chinese Shanghai yes
3Chinese Macao yes
4Tokyo Japan Chinese no
给定⼀个新样本Chinese Chinese Chinese Tokyo Japan，对其进⾏分类。
该⽂本⽤属性向量表⽰为d=(Chinese, Chinese, Chinese, Tokyo, Japan)，类别集合为Y={yes, no}。
类yes下总共有8个单词，类no下总共有3个单词，训练样本单词总数为11，因此P(yes)=8/11, P(no)=3/11。类条件概率计算如下：P(Chinese | yes)=(5+1)/(8+6)=6/14=3/7
P(Japan | yes)=P(Tokyo | yes)= (0+1)/(8+6)=1/14
P(Chinese|no)=(1+1)/(3+6)=2/9
P(Japan|no)=P(Tokyo| no) =(1+1)/(3+6)=2/9
分母中的8，是指yes类别下text c的长度，也即训练样本的单词总数，6是指训练样本有Chinese,Beijing,Shanghai, Macao, Tokyo, Japan 共6个单词，3是指no类下共有3个单词。
有了以上类条件概率，开始计算后验概率，
P(yes | d)=(3/7)3×1/14×1/14×8/11=108/184877≈0.00058417
P(no | d)= (2/9)3×2/9×2/9×3/11=32/216513≈0.00014780
因此，这个⽂档属于类别china。
2.3伯努利模型
1、基本原理
P(c)= 类c下⽂件总数/整个训练样本的⽂件总数
P(t k|c)=(类c下包含单词t k的⽂件数+1)/(类c下单词总数+2)
在这⾥，m=2, p=1/2。
后验概率的计算，也有点变化，见下⾯的伪代码。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议