朴素贝叶斯算法

约 919 个字 预计阅读时间 3 分钟

问题及算法描述

给定数据集\(\{(x_i，y_i)\}\)， 其中 \(x \in \mathbb{R}^n\)，\(y_i \in \{ c_1，c_2，....c_k\}\)， 一共有 K 种类别，现在给出一个新的数据点\(x\)，求出它的类别\(y\).

算法希望学习一个联合概率分布\(P(X，Y)\)，而我们现在已经有的是先验分布\(P(Y)\)和条件概率分布\(P(X|Y)\).

但是后者的空间太大，这里我们引入独立性假设，假设 x 的每个维度都是独立的（事实上大概率并不是，这是极大简化计算量的一步，也是引入误差的一步，也是该算法的“朴素”之处）:

\[ P(X = x| Y = c_k) = P(X^{(1)} = x^{(1)}， X^{(2)} = x^{(2)} ... X^{(n)} = x^{(n)} | Y = c_k)= \prod_{i=1}^{n}P(X^{(i)} = x^{(i)}| Y = c_k) \]

上式的意思是在类别是\(c_k\)的前提下，X 这一 n 维随机变量的取值为 x 的概率，就是\(c_k\)这一类中每个维度的取值为\(x^{(i)}\)的概率的乘积。

学习到了联合概率分布之后，我们在分类的时候直接使用最大后验概率：

\[ y = \underset{c_k}{\operatorname{arg max}} P(Y = c_k) \prod_{i=1}^{n}P(X^{(i)} = x^{(i)}| Y = c_k) \]

上式的意思就是假设 x 的类别是\(c_k\)，计算每个\(c_k\)这一类中出现 x 的概率，找出概率最大的那一类作为 x 的分类。

PPT 中的一个分类实例

极大似然估计

利用极大似然估计，我们可以得到下面这两个概率的估计公式：

\[\begin{aligned} &P(Y = c_k) = \frac{\sum_{i=1}^{N}I(y_i = c_k)}{N} \\ &P(X^{(i)} = a_{jl}| Y = c_k) = \frac{\sum_{i=1}^{N}I(x_i^{(i)} = a_{jl}，y_i = c_k)}{\sum_{i=1}^{N}I(y_i = c_k)} \end{aligned}\]

指示函数的定义在前面已经有介绍，后续都默认使用这一定义。

第一式的意思是不同类别的出现概率的先验概率直接为样本中该类别出现的频率。

第二式的意思是在类别为\(c_k\)的前提下，第 i 维取值为\(a_{jl}\)的概率为样本中\(c_k\)类中该分量为\(a_{jl}\)的样本占\(c_k\)类样本总数的比重。

思想

极大似然估计在此处的结果基本上可以简单归结为：用频率估计概率

贝叶斯估计

上述的极大似然估计在一个情况下可能遇到问题，如果某个样本没有出现的话，对那个类别估计的信息完全丢失。

为解决这一问题，我们可以手动为每一类别添加默认 n 次的出现频数：

\[\begin{aligned} &P(Y = c_k) = \frac{\sum_{i=1}^{N}I(y_i = c_k) + \lambda}{N + K\lambda} \\ &P(X^{(i)} = a_{jl}| Y = c_k) = \frac{\sum_{i=1}^{N}I(x_i^{(i)} = a_{jl}，y_i = c_k) + \lambda}{\sum_{i=1}^{N}I(y_i = c_k) + S_i\lambda} \end{aligned}\]

其中\(S_i\)是第 i 维的取值个数，\(\lambda\)是一个超参数，一般取 1.

在第一式中，我们为每个类别都加入了\(\lambda\)的频率，所以分子单独某类的频数加上了\(\lambda\)，分母加上了总类别数 K 乘上\(\lambda\).

在第二式中，我们为每个类别的每个维度都加入了\(\lambda\)的频率，所以分子单独某类的频数加上了\(\lambda\)，分母加上了该维度可能的取值个数数乘上\(\lambda\)（因为有多少个取值，我们就人为的加上了多少个\(\lambda\)）.

可以认为贝叶斯估计是对极大似然估计进行了平滑。

Comments