第5章
CHAPTER 5


朴素贝叶斯分类器





朴素贝叶斯分类器是一种有监督的统计学过滤器，在垃圾邮件过滤、信息检索等领域十分常用。通过本章的介绍，读者将会看到朴素贝叶斯分类器因何得名、其与贝叶斯公式的联系，以及其与极大似然估计的关系。
5.1极大似然估计
对于工厂生产的某一批灯泡，质检部门希望检测其合格率。设m表示产品总数，随机变量Xi∈{0,1}表示编号为i的产品是否合格。由于这些产品都是同一批生产的，不妨假设

X1,X2,…,Xm~i．i．d．Bern(p)（51）

其中，p表示产品合格的概率，也就是质检部门希望得到的数据。根据经典概率模型有

p≈1m∑mi=1Xi（52）

但是式（52）为什么成立？这就需要使用极大似然估计来证明了。
极大似然估计的思想是： 找到这样一个参数p，它使所有随机变量的联合概率最大。例中，联合概率表示为

P(X1=x1,X2=x2,…,Xm=xm)=∏mi=1P(Xi=xi)=∏mi=1pxi(1-p)1-xi（53）

最大化联合概率等价于求

p*=arg maxp log∏mi=1pxi(1-p)1-xi

=arg maxp∑mi=1xilogp+(1-xi)log(1-p)

=arg maxp mlog(1-p)+logp1-p∑mi=1xi（54）

根据微积分知识容易证明式（52）



p*=1m∑mi=1Xi（55）


形式化地说，已知整体的概率分布模型f(x;θ)，但是模型的参数θ未知时，可以使用极大似然估计来估计θ的值。这里的概率分布模型既可以是连续的(概率密度函数)也可以是离散的(概率质量函数)。假设在一次随机实验中，我们独立同分布地抽到了m个样本x1,x2,…,xm组成的样本集合。似然函数，也就是联合概率分布

L(θ)=fm(x1,x2,…,xm;θ)=∏mi=1f(xi;θ)（56）





表示当前样本集合出现的可能性。令似然函数L(θ)对参数θ的导数为0，可以得到θ的最优解。但是运算中涉及乘法运算及乘法的求导等，往往计算上存在不便性。而对似然函数取对数并不影响似然函数的单调性，即

L(θ1)>L(θ2)logL(θ1)>logL(θ2)（57）

所以最大化对数似然函数

l(θ)=logL(θ)=log∏mi=1p(xi;θ)=∑mi=1logp(xi;θ)（58）

可以在保证最优解与似然函数相同的条件下，大大减少计算量。
极大似然估计通过求解参数θ使得fN(x1,x2,…,xN;θ)最大，这是一种很朴素的思想： 既然从总体中随机抽样得到了当前样本集合，那么当前样本集合出现的可能性极大。
5.2朴素贝叶斯分类
在概率论中，贝叶斯公式的描述如下

P(Yi|X)=P(X,Yi)P(X)=P(Yi)P(X|Yi)∑Kj=1P(Yj)P(X|Yj)（59）

其中Y1,Y2,…,YK为一个完备事件组，P(Yi)称为先验概率，P(Yi|X)称为后验概率。设X=(X1,X2,…,Xn)表示n维(离散)样本特征，Y∈{c1,c2,…,cK}表示样本类别。由于一个样本只能属于这K个类别中的一个，所以Y1,Y2,…,YK一定是完备的。
给定样本集合D={(x1,y1),(x2,y2),…,(xm,ym)}，我们希望估计PY|X。根据贝叶斯公式，对于任意样本x=(x1,x2,…,xn)，其标签为ck的概率为

P(Y=ck|X=x)=P(Y=ck)P(X=x|Y=ck)P(X=x)（510）

假设随机变量X1,X2,…,Xn相互独立，则有

P(X=x|Y=ck)=P(X1=x1,X2=x2,…,Xn=xn|Y=ck)

=∏ni=1P(Xi=xi|Y=ck)（511）

带入式（510）

得

P(Y=ck|X=x)=P(Y=ck)∏ni=1P(Xi=xi|Y=ck)P(X=x)（512）

在实际进行分类任务时，不需要计算出PY|X的精确值，只需要求出k*即可

k*=arg maxkP(Y=ck|X=x)（513）

不难看出，式（512）

右侧的分母部分与k无关。因此

k*=arg maxkP(Y=ck)∏ni=1P(Xi=xi|Y=ck)（514）

式中所有项都可以用频率代替概率在样本集合上进行估计

P(Y=ck)≈Nkm

P(Xi=xi|Y=ck)≈∑mj=1I{xij=xi,yj=ck}Nk（515）

其中，Nk表示D中标签为ck的样本数量。
5.3拉普拉斯平滑
当样本集合不够大时，可能无法覆盖特征的所有可能取值。也就是说，可能存在某个ck和xi使

P(Xi=xi|Y=ck)=0（516）

此时，无论其他特征分量的取值为何，都一定有

P(Y=ck)∏ni=1P(Xi=xi|Y=ck)=0（517）

为了避免这样的问题，实际应用中常采用平滑处理。典型的平滑处理就是拉普拉斯平滑

P(Y=ck)≈Nk+1m+K

P(Xi=xi|Y=ck)≈∑mj=1I{xij=xi,yj=ck}+1Nk+Ai（518）

其中，Ai表示Xi的所有可能取值的个数。
基于上述讨论，完整的朴素贝叶斯分类器的算法描述见算法51

。
算法5

1朴素贝叶斯分类器

输入： 样本集合D={(x1,y1),(x2,y2),…,(xm,ym)}； 待预测样本x； 样本标记的所有可能取值{c1,c2,…,cK}； 样本输入变量X的每个属性变量Xi的所有可能取值{ai1,ai2,…,aiAi}
输出： 待预测样本x所属的类别


1． 计算标记为ck的样本出现的概率:

P(Y=ck)=Nk+1m+K,k=1,2,…,K





2． 计算标记为ck的样本，其Xi分量的属性值为aip的概率

P(Xi=aip|Y=ck)=∑Nkj=1I(xij=aip,yj=ck)+1Nk+Ai

3． 根据上面的估计值计算x属于所有yk的概率值，并选择概率最大的作为输出

Return y=arg maxk=1,2,…,KP(Y=ck|X=x)

=arg maxk=1,2,…,KP(Y=ck)∏ni=1P(Xi=xi|Y=ck)


5.4朴素贝叶斯分类器的极大似然估计解释
朴素贝叶斯思想的本质是极大似然估计，P(Y=ck)和P(Xi=xi|Y=ck)是我们要估计的概率值。以P(Y=ck)为例，令θk=P(Y=ck)，则似然函数为

L(θ)=∏mi=1P(Y=yi)=∏Kk=1θNkk（519）

根据极大似然估计，求θ等价于求解下面的优化问题：

maxθl(θ)=∑Kk=1Nklnθk

s．t．∑Kk=1θk=1（520）

使用拉格朗日乘子法求解。首先构造拉格朗日乘数为

Lag(θ)=∑Kk=1Nklnθk+λ(∑Kk=1θk-1)（521）

令拉格朗日函数对θk的偏导为0，有

Lagθk=Nkθk+λ=0Nk=-λθk（522）

于是

∑Kk=1Nk=-λ∑Kk=1θk=-λ（523）

解得

λ=-m

θk=Nkλ=Nkm（524）

这样便得到了P(Y=ck)的极大似然估计。对P(Xi=xi|Y=ck)的极大似然估计求解过程类似，留给读者自行推导。
5.5实例： 基于朴素贝叶斯实现垃圾短信分类
本节以一个例子来阐述朴素贝叶斯分类器在垃圾短信分类中的应用。SMS Spam Collection Data Set是一个垃圾短信分类数据集，包含了5574条短信，其中有747条垃圾短信。数据集以纯文本的形式存储，其中每行对应于一条短信。每行的第一个单词是spam或ham，表示该行的短信是不是垃圾短信。随后记录了短信的内容，内容和标签之间以制表符分隔。
该数据集没有收录进sklearn．datasets，所以我们需要自行加载，如代码清单51

所示。

代码清单5

1加载SMS垃圾短信数据集


with open('．/SMSSpamCollection．txt', 'r', encoding='utf8') as f:

sms= ［line．split('＼t') for line in f］

y, x = zip(*sms)


加载完成后，x和y分别是长为5574的字符串列表。其中y的每个元素只可能是spam或ham，分别表示垃圾短信和正常短信。x的每个元素表示对应短信的内容。在训练贝叶斯分类器以前，需要首先将x和y转换成适于训练的数值表示形式，这个过程称为特征提取，如代码清单52

所示。

代码清单5

2SMS垃圾短信数据集特征提取


from sklearn．feature_extraction．text import CountVectorizer as CV

from sklearn．model_selection import train_test_split

y= ［label == 'spam' for label in y］

x_train, x_test, y_train, y_test = train_test_split(x, y)

counter= CV(token_pattern='［a-zA-Z］{2,}')

x_train= counter．fit_transform(x_train)

x_test= counter．transform(x_test)


特征提取的结果存储在(x_train, y_train)以及(x_test, y_test)中。其中x_train和x_test分别是4180×6595和1394×6595的稀疏矩阵。不难看出，两个矩阵的行数之和等于5574，也就是完整数据集的大小。因此两个矩阵的每行应该代表一个样例，那么每列代表什么呢？查看counter的vocabulary_属性就会发现，其大小恰好是6595，也就是所有短信中出现过的不同单词的个数。例如短信“Go until jurong point, go”中一共有5个单词，但是由于go出现了两次，所以不同单词的个数只有4个。x_train和x_test中的第i,j个元素就表示第j个单词在第i条短信中出现的次数。

代码清单5

3朴素贝叶斯分类器的构造与训练


from sklearn．naive_bayes import MultinomialNB as NB

model= NB()




model．fit(x_train, y_train)

train_score= model．score(x_train, y_train)

test_score= model．score(x_test, y_test)

print("train score:", train_score)

print("test score:", test_score)


最后就是朴素贝叶斯分类器的构造与训练，如代码清单53

所示。我们首先基于训练集训练朴素贝叶斯分类器，然后分别在训练集和测试集上进行测试。测试结果显示，模型在训练集上的分类准确率达到0．993，在测试集上的分类准确率为0．986。可见朴素贝叶斯分类器达到了良好的分类效果。
朴素贝叶斯分类器假设样本特征之间相互独立。这一假设非常强，以至于几乎不可能满足。但是在实际应用中，朴素贝叶斯分类器往往表现良好，特别是在垃圾邮件过滤、信息检索等场景下往往表现优异。






第6章
CHAPTER 6


支持向量机





支持向量机［5］

是一种功能强大的机器学习算法。典型的支持向量机是一种二分类算法，其基本思想是： 对于空间中的样本点集合，可用一个超平面将样本点分成两部分，一部分属于正类，一部分属于负类。支持向量机的优化目标就是找到这样一个超平面，使得空间中距离超平面最近的点到超平面的几何间隔尽可能大，这些点称为支持向量。
6.1最大间隔及超平面
给定样本集合D={(x1,y1),(x2,y2),…,(xm,ym)}，设yi∈{-1,+1}。设输入空间中的一个超平面表示为

ωTx+b=0（61）

其中，ω称为法向量，决定超平面的方向； b为偏置，决定超平面的位置。根据点到直线距离公式的扩展，空间中一点xi到超平面ωTx+b=0的欧氏距离为

ri=|ωTxi+b|‖ω‖（62）


如果超平面能将正确所有样本点分类，则点到直线的距离可以写成分段函数的形式为

ri=ωTxi+b‖ω‖,yi=+1

-ωTxi+b‖ω‖,yi=-1（63）

式（63）

也可用一个方程来表示

ri=ωTxi+b‖ω‖yi（64）

6.2线性可分支持向量机
线性可分支持向量机的目标是，通过求解ω和b找到一个超平面ωTx+b=0。在保证超平面能够正确将样本进行分类的同时，使得距离超平面最近的点到超平面的距离尽可能大。这是一个典型的带有约束条件的优化问题，约束条件是超平面能将样本集合中的点正确分类。将距离超平面最近的点与超平面之间的距离记为

r=mini=1,2,…,mri（65）





最优化问题可写做

maxω,br

s．t．ri=ωTxi+b‖ω‖yi≥r,i=1,2,…,m（66）


对于超平面ωTx+b=0，可以为等式两边同时乘以相同的不为0的实数，超平面不发生变化。所以对任一支持向量x*可以通过对超平面公式进行缩放使得(ωTx*+b)y*=1，x*到超平面的距离可表示为1‖ω‖，则优化问题可写作

maxω,b1‖ω‖

s．t．ri=ωTxi+b‖ω‖yi≥1‖ω‖,i=1,2,…,m（67）

最大化1‖ω‖也即最小化12‖ω‖2，使用12‖ω‖2作为优化目标是为了计算方便。

minω,b12‖ω‖2

s．t．ri=(ωTxi+b)yi-1≥0,i=1,2,…,m（68）



图61线性可分支持向量机一(见彩插)

可以证明，支持向量机的超平面存在唯一性，本书略。支持向量机中的支持向量至少为两个，由超平面分割成的正负两个区域至少各存在一个支持向量，且超平面的位置仅由这些支持向量决定，与支持向量外的其他样本点无关。在这两个区域，过支持向量，可以分别做一个与支持向量机分割超平面平行的平面H1和H2，两个超平面之间的距离为2‖ω‖，如图61

所示。
在感知机模型中，优化的目标是： 在满足模型能够正确分类的约束条件下，使得样本集合中的所有点到分割超平面的距离最小，这样的超平面可能存在无数个。一个简单的例子，假如二维空间中样本集合中正负样本个数点均为一个，那么垂直于两者所连直线，且位于两者之间的所有直线都将是符合条件的解。由于优化目标不同，造成解的个数不同，这是支持向量机与感知机模型很大的区别。
式（68）

中的最优化问题，可使用拉格朗日乘子法进行求解。拉格朗日函数为

Lag(ω,b,α)=12‖ω‖2+∑mi=1αi1-ωTxi+byi（69）

其中，α=(α1,α2,…,αm),αi≥0表示拉格朗日乘子。令Lag对ω和b的偏导为0


Lag(ω,b,α)ω=ω-∑mi=1αiyixi=0

Lag(ω,b,α)b=-∑mi=1αiyi=0（610）

解得

ω=∑mi=1αiyixi

0=∑mi=1αiyi（611）

将式（611）

带入式（69）

中，得到

minω,bLag(ω,b,α)=∑mi=1αi-12∑mi=1∑mj=1αiαjyiyjxTixj（612）

求minω,bLag(ω,b,α)对α的极大，等价于求-minω,bLag(ω,b,α)对α的极小。因此式（68）

的对偶问题为

minα12∑mi=1∑mj=1αiαjyiyjxTixj-∑mi=1αi

s．t．∑mi=1αiyi=0

αi≥0,i=1,2,…,m（613）

求解优化问题（613）

，即可得到α*=(α*1,α*2,…,α*m)。根据KKT(KarushKuhnTucker)条件，(ω*,b*)是原始问题（68）

的最优解，且α*是对偶问题（613）

的最优解的充要条件是： (ω*,b*),α*满足KKT条件，即

α*i≥0,i=1,2,…,m

ω*Txi+b*yi-1≥0,i=1,2,…,m

α*iω*Txi+b*yi-1=0,i=1,2,…,m（614）

由式（611）

有

ω*=∑mi=1α*iyixi（615）

考察KKT条件的第三条，可以发现要么α*i=0，要么ω*Txi+b*yi-1=0。假设αj>0，则必有ω*Txj+b*yj-1=0，于是

b*=yj-∑mi=1α*iyixTixj（616）

由此得到分割超平面

ω*x+b*=0（617）

当α*i=0时，即式（615）

、式（616）

与样本xi,yi无关。也就是说，只有当α*i>0时，样本xi,yi才对最终的结果产生影响，此时样本的输入即为支持向量。求得支持向量机的参数后，即可根据式（618）

判断任意样本的类别

f(x)=sgnω*Tx+b*（618）


6.3线性支持向量机
线性可分支持向量机假设样本空间中的样本能够通过一个超平面分隔开来。但是生产环境中，我们获取到的数据往往存在噪声(正类中混入少量的负类样本，负类中混入少量的正类样本)，从而使得数据变得线性不可分。这种情况就需要使用线性支持向量机求解了。
另一方面，即使样本集合线性可分，线性可分支持向量机给出的H1和H2之间的距离可能非常小。这种情况一般意味着模型的泛化能力降低，也就是产生了过拟合。因此我们希望H1和H2之间的距离尽可能大，这时同样可以使用线性支持向量机来允许部分样本点越过H1和H2。
线性支持向量机在线性可分向量机的基础上引入了松弛变量ξi≥0。对于样本点xi,yi，线性支持向量机允许部分样本落入越过超平面H1或H2

ωTixi+byi≥1-ξi（619）

线性可分支持向量机中，要求所有样本都满足ωTixi+byi≥1，此时H1和H2之间的距离2‖ω‖称为“硬间隔”。线性支持向量机中，ωTxi+byi≥1-ξi允许部分样本越过超平面H1或H2，此时H1和H2之间的距离2‖ω‖称为“软间隔”。需要注意的是，此时的支持向量不再仅仅包含位于H1和H2超平面上的点，还可能包含其他点。
对线性支持向量机进行优化时，我们希望“软间隔”尽量大，同时希望越过超平面H1和H2的样本尽可能不要远离这两个超平面，则优化的目标函数可写为

12‖ω‖2+C∑mi=1ξi（620）

其中，C为惩罚系数。12‖ω‖2控制最小间隔尽可能大，而∑mi=1ξi则控制越过超平面H1或H2的样本点离超平面尽量近，C是对两者关系的权衡。线性支持向量机的优化问题可写为

minω,b,ξ12‖ω‖2+C∑mi=1ξi

s．t．ωTxi+byi≥1-ξi,i=1,2,…,m

ξi≥0,i=1,2,…,m（621）

类似于线性可分支持向量机中的求解过程，式（621）

的拉格朗日函数可写作

Lag(ω,b,ξ,α,μ)

=12‖ω‖2+C∑mi=1ξi+∑mi=1αi1-ξi-ωTxi+byi-∑mi=1μiξi（622）

其中

α=(α1,α2,…,αm),αi≥0


μ=(μ1,μ2,…,μm),μi≥0（623）