算法工程师面试之朴素贝叶斯

深藏阁楼爱情的钟 2022-12-16 06:58 123阅读 0赞

# 前言 #

*  文章来源： CSDN@LawsonAbs
 *  弄懂一个算法是快乐的，(＾－＾)V

--------------------

# 1.定义 #

首先给出如下几个变量的定义：

*   X X X 是定义在n维向量上的随机变量，表示特征
 *   Y Y Y 是定义在 c 1 , c 2 , . . . , c k \{c\_1,c\_2,...,c\_k\} c1,c2,...,ck 上的随机变量，表示类别
 *   x j x^j xj表示特征向量的第`j`维
 *   c k c\_k ck表示第`k`类

朴素贝叶斯算法目的是为了计算在给定特征数据 x下的分类情况，是一种分类算法。朴素贝叶斯的思想基于贝叶斯定理： P ( y ∣ x ) = p ( x , y ) p ( x ) P(y|x)= \\frac\{p(x,y)\}\{p(x)\} P(y∣x)=p(x)p(x,y)

我们想得到后验概率 p ( y ∣ x ) p(y|x) p(y∣x)，那么就只需要知道 p ( x , y ) p(x,y) p(x,y)即可，因为 p ( x ) p(x) p(x)是已知的【因为x是给出的样本数据】。那么我们就需要对 p ( x , y ) p(x,y) p(x,y)建模，那么该怎么学习 p ( x , y ) p(x,y) p(x,y)呢？我们可以学习先验概率分布 p ( Y = c k ) p(Y=c\_k) p(Y=ck)以及条件概率分布来获取 p ( X = x ∣ Y = c k ) p(X=x|Y=c\_k) p(X=x∣Y=ck)，从而获取到 p ( x , y ) p(x,y) p(x,y)。即：  
 P ( Y = c k ) , k = 1 , 2 , 3 , . . . K P ( X = x ∣ Y = c k ) = P ( X 1 = x 1 , . . . X n = x n ∣ Y = c k ) = > P ( X , Y ) = P ( X = x ∣ Y = c k ) ∗ P ( Y = c k ) \\begin\{aligned\} &P(Y=c\_k) , k = 1,2,3,... K\\\\ &P(X=x|Y=c\_k) = P(X^1=x^1,...X^n=x^n| Y=c\_k)\\\\ &=>P(X,Y) = P(X=x|Y=c\_k) \* P(Y=c\_k) \\end\{aligned\} P(Y=ck),k=1,2,3,...KP(X=x∣Y=ck)=P(X1=x1,...Xn=xn∣Y=ck)=>P(X,Y)=P(X=x∣Y=ck)∗P(Y=ck)  
这里的 X 1 = x 1 X^1 = x^1 X1=x1 的含义是:随机变量的第一维特征的取值。

# 2.表达式 #

y = a r g m a x c k P ( Y = c k ) ∏ j P ( X j = x j ∣ Y = c k ) y=argmax\_\{c\_\{k\}\} \\quad P(Y=c\_k)\\quad \\prod\_\{j\} P(X^j = x^j | Y = c^k) y=argmaxckP(Y=ck)j∏P(Xj=xj∣Y=ck)  
其中：

*   X X X 是定义在n维向量上的随机变量
 *   x j x^j xj表示特征向量的第`j`维
 *   c k c\_k ck表示第k类

# 3.为什么说它是朴素的？ #

因为该模型假设在类确定的条件下，其各个特征是相互独立的。

# 4.条件独立性假设有什么用？具体说明。 #

条件独立性假设是用于简化计算才提出的。因为每个特征都有不同个数的取值，假设 x j x^j xj的取值有 S j S\_j Sj个，因为需要遍历取值，那么对于计算 P ( X = x ∣ Y = c k ) = P ( X 1 = x 1 , . . . X n = x n ∣ Y = c k ) P(X=x|Y=c\_k) = P(X^1=x^1,...X^n=x^n| Y=c\_k) P(X=x∣Y=ck)=P(X1=x1,...Xn=xn∣Y=ck) 的复杂度就是  K ∏ j n S j K \\prod\_\{j\}^\{n\} S\_j K∏jnSj。这个复杂度是很高的。所以可以简化成  
 P ( X = x ∣ Y = c k ) = P ( X 1 = x 1 ∣ Y = c k ) . . . P ( X n = x n ∣ Y = c k ) = ∏ j = 1 n P X j = x j ∣ Y = c k \\begin\{aligned\} P(X=x|Y=c\_k) &= P(X^1=x^1| Y=c\_k) ... P(X^n=x^n| Y=c\_k) \\\\ &= \\prod\_\{j=1\}^\{n\}P\{X^j=x^j|Y=c\_k\}\\\\ \\end\{aligned\} P(X=x∣Y=ck)=P(X1=x1∣Y=ck)...P(Xn=xn∣Y=ck)=j=1∏nPXj=xj∣Y=ck  
变成一个连乘的形式。

# 5.实际应用 #

这里我们尝试使用朴素贝叶斯做一个文本分类。文本不同于图像，比如说：MNIST手写数据集中，图像是有固定大小的（28\*28=784），这样就可以得到一个784维的向量，然后这每一维都可以看作是特征，但是文本该怎么做呢？这就涉及到特征工程 这门儿手艺，即怎么从文本中获取各个特征？  
我个人思考的方法有：

*  使用 TF-IDF 获取一个文本中的常用词，这样我们可以按照其得分排列，组合成一个固定维数的向量。但这又涉及到另外一个问题，即各个变量的不同维度上的特征可能不是同性质的东西，比如： x 1 1 x^1\_1 x11 与  x 2 1 x^1\_2 x21 的这个第一维特征是同类特征吗？如果不是同类特征就不具备计算 p ( x ∣ y ) p(x|y) p(x∣y)的前提。

# 参考资料 #

*  李航《统计学习方法》