[数据结构与算法]NB 算法 (包括符号型与数值型 结合 Java 程序分析)

摘要: 本贴结合例子与程序分析 NB 算法.
Naive Bayes 是一个经典的、有代表性的分类算法. Naive 的 i 上面应该是两个点, 它读作 “哪义乌”, 表示很傻瓜很天真. Bayes 是一个神职人员, 也是概率界的一个神级人物. 中国程序猿喜欢把它读作 “牛逼算法”, 其实也没吹的那么厉害.

1. 例子数据集 1: 符号型

符号型数据集, 还是用 weather 吧. 可在 https://gitee.com/fansmale/javasampledata 下载.

@relation weather.symbolic

@attribute outlook {sunny, overcast, rainy}
@attribute temperature {hot, mild, cool}
@attribute humidity {high, normal}
@attribute windy {TRUE, FALSE}
@attribute play {yes, no}

@data
sunny,hot,high,FALSE,no
sunny,hot,high,TRUE,no
overcast,hot,high,FALSE,yes
rainy,mild,high,FALSE,yes
rainy,cool,normal,FALSE,yes
rainy,cool,normal,TRUE,no
overcast,cool,normal,TRUE,yes
sunny,mild,high,FALSE,no
sunny,cool,normal,FALSE,yes
rainy,mild,normal,FALSE,yes
sunny,mild,normal,TRUE,yes
overcast,mild,high,TRUE,yes
overcast,hot,normal,FALSE,yes
rainy,mild,high,TRUE,no

2. 基础理论

2.1 条件概率

$$P(AB)=P(A)P(B|A)\text{\hspace{1em}(1)}$$
其中:

• $P(A)$ 表示事件 $A$ 发生的概率;
• $P(AB)$ 表示事件 $A$ 和 $B$ 同时发生的概率;
• $P(B|A)$ 表示在事件 $A$ 发生的情况下, 事件 $B$ 也发生的概率.

例: $A$ 表示天气是晴天, 即 outlook = sunny; $B$ 表示湿度高, 即 humidity = high.
14 天中, 有 5 天 sunny, 则 $P(A)=P(\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{k}=\mathrm{s}\mathrm{u}\mathrm{n}\mathrm{n}\mathrm{y})=5/14$.
这 5 个晴天中, 有 3 天温度高, 则 $P(B|A)=P(\mathrm{h}\mathrm{u}\mathrm{m}\mathrm{i}\mathrm{d}\mathrm{i}\mathrm{t}\mathrm{y}=\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}|\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{k}=\mathrm{s}\mathrm{u}\mathrm{n}\mathrm{n}\mathrm{y})=3/5$.
那么, 即是晴天又温度度的概率是 $P(AB)=P(\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{k}=\mathrm{s}\mathrm{u}\mathrm{n}\mathrm{n}\mathrm{y}\wedge \mathrm{h}\mathrm{u}\mathrm{m}\mathrm{i}\mathrm{d}\mathrm{i}\mathrm{t}\mathrm{y}=\mathrm{h}\mathrm{i}\mathrm{t}\mathrm{h})=3/14=P(A)P(B|A)$.

2.2 独立性假设

令 $\mathbf{x}=x_1\wedge x_2\wedge ?\wedge x_m$ 表示一个条件的组合, 如: $\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{k}=\mathrm{s}\mathrm{u}\mathrm{n}\mathrm{n}\mathrm{y}\wedge \mathrm{t}\mathrm{e}\mathrm{m}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{e}=\mathrm{h}\mathrm{o}\mathrm{t}\wedge \mathrm{h}\mathrm{u}\mathrm{m}\mathrm{i}\mathrm{d}\mathrm{i}\mathrm{t}\mathrm{y}=\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}\wedge \mathrm{w}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{y}=\mathrm{F}\mathrm{A}\mathrm{L}\mathrm{S}\mathrm{E}$, 它对应于我们数据集的第一行. 令 $D_i$ 表示一个事件, 如: play = no. 根据 (1) 式可知:
$$P(D_i|\mathbf{x})=\frac{P(\mathbf{x}{D}_i)}{P(\mathbf{x})}=\frac{P(D_i)P(\mathbf{x}|D_i)}{P(\mathbf{x})}\text{\hspace{1em}(2)}$$
现在我们做一个大胆的假设, 认为各个条件之间是独立的:
$$P(\mathbf{x}|D_i)=P(x_1|D_i)P(x_2|D_i)\dots P(x_m|D_i)=\prod _{j=1}^{m}P(x_j|D_i)\text{\hspace{1em}(3)}$$
这个大胆的假设, 就是 Naive 的来源. 在现实数据中, 它是不成立的! 我都承认自己不靠谱了, 你还想怎么样? 反正我的疗效好, 哼！
综合 (2)(3) 式可得:
$$P(D_i|\mathbf{x})=\frac{P(\mathbf{x}{D}_i)}{P(\mathbf{x})}=\frac{P(D_i){\prod }_{j=1}^{m}P(x_j|D_i)}{P(\mathbf{x})}\text{\hspace{1em}(4)}$$
如果用例子替换成 $P(\mathrm{p}\mathrm{l}\mathrm{a}\mathrm{y}=\mathrm{n}\mathrm{o}|\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{k}=\mathrm{s}\mathrm{u}\mathrm{n}\mathrm{n}\mathrm{y}\wedge \mathrm{t}\mathrm{e}\mathrm{m}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{e}=\mathrm{h}\mathrm{o}\mathrm{t}\wedge \mathrm{h}\mathrm{u}\mathrm{m}\mathrm{i}\mathrm{d}\mathrm{i}\mathrm{t}\mathrm{y}=\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}\wedge \mathrm{w}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{y}=\mathrm{F}\mathrm{A}\mathrm{L}\mathrm{S}\mathrm{E})$, 就读作: “在出太阳而且气温高而且湿度高而且没风的天气, 不打球的概率”.
这个概率是算不出来的, 因为我们计算不了分母 $P(\mathbf{x})$. 不过我们的目标是进行分类, 也就是说, 哪个类别的概率高, 我们就选谁. 而对不同的类别, 这个式子的分母是完全相同的! 所以我们的预测方案就可以描述为:
$$d(\mathbf{x})=\underset{1\le i\le k}{\mathrm{argmax}}P(D_i)P(D_i|\mathbf{x})=\underset{1\le i\le k}{\mathrm{argmax}}P(D_i)\prod _{j=1}^{m}P(x_j|D_i)=\underset{1\le i\le k}{\mathrm{argmax}}\log P(D_i)+\sum _{j=1}^m\log P(x_j|D_i)\text{\hspace{1em}(5)}$$

• $\mathrm{argmax}$ 表示哪个类别的相对概率高, 我们就预测为该类别.
• 由于 $\log$ 函数保持了单调性, 我们直接拿来用, 一方面不改变最终选择的类别, 另一方面可以把乘法搞成加法. 这是将数学应用于计算机的常用招数, 防止溢出. 真是太可恶了!
• 如何计算 $P(x_j|D_i)$? 我们在最初讲条件概率的时候已经有例子了, 这里针对决策属性值再来一个: $$P(x_j|D_i)=\frac{P(x_j{D}_i)}{P(D_i)}=\frac{P(\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{k}=\mathrm{s}\mathrm{u}\mathrm{n}\mathrm{n}\mathrm{y}\wedge \mathrm{p}\mathrm{l}\mathrm{a}\mathrm{y}=\mathrm{y}\mathrm{e}\mathrm{s})}{P(\mathrm{p}\mathrm{l}\mathrm{a}\mathrm{y}=\mathrm{y}\mathrm{e}\mathrm{s})}\text{\hspace{1em}(6)}$$

2.3 Laplacian 平滑

然鹅, (5) 式在预测时会出现问题. 例如:

• $P(\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{k}=\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{c}\mathrm{a}\mathrm{s}\mathrm{t}|\mathrm{p}\mathrm{l}\mathrm{a}\mathrm{y}=\mathrm{n}\mathrm{o})=0$, 即不打球的时候, 天气不可能是多云. 如果新的一天为阴天, 则不打球的概率为 0.
• $P(\mathrm{t}\mathrm{e}\mathrm{m}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{e}=\mathrm{h}\mathrm{o}\mathrm{t}|\mathrm{p}\mathrm{l}\mathrm{a}\mathrm{y}=\mathrm{y}\mathrm{e}\mathrm{s})=0$, 即打球的时候, 温度不可能是高 (注意这个例子与前面数据集的冲突, 大家领会精神就行). 如果新的一天温度高, 则打球的概率为 0.

那么, 如果有一天 $\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{k}=\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{c}\mathrm{a}\mathrm{s}\mathrm{t}\wedge \mathrm{t}\mathrm{e}\mathrm{m}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{e}=\mathrm{h}\mathrm{o}\mathrm{t}$, 岂不是打球和不打球的概率都为 0 了?
这里的根源在于 “一票否决权”, 即 (5) 式的连乘因子中, 只要有一个为 0, 则乘积一定为 0. 为了解决该问题, 我们要想办法让这个因子不要取 0 值.

$$P^L(x_j|D_i)=\frac{nP(x_j{D}_i)+1}{nP(D_i)+v_j}=\frac{nP(\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{k}=\mathrm{s}\mathrm{u}\mathrm{n}\mathrm{n}\mathrm{y}\wedge \mathrm{p}\mathrm{l}\mathrm{a}\mathrm{y}=\mathrm{y}\mathrm{e}\mathrm{s})+1}{nP(\mathrm{p}\mathrm{l}\mathrm{a}\mathrm{y}=\mathrm{y}\mathrm{e}\mathrm{s})+3}\text{\hspace{1em}(7)}$$
其中, $n$ 是对象的数量, $v_j$ 是第 $j$ 个属性的可能取值数, outlook 有 3 种取值. 这样可以保证

• $P^L(x_j|D_i)>0$;
• outlook 三种取值导致的条件概率之和恒为 1. 即
  $P^L(\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{k}=\mathrm{s}\mathrm{u}\mathrm{n}\mathrm{n}\mathrm{y}|\mathrm{p}\mathrm{l}\mathrm{a}\mathrm{y}=\mathrm{y}\mathrm{e}\mathrm{s})+P^L(\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{k}=\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{c}\mathrm{a}\mathrm{s}\mathrm{t}|\mathrm{p}\mathrm{l}\mathrm{a}\mathrm{y}=\mathrm{y}\mathrm{e}\mathrm{s})+P^L(\mathrm{r}\mathrm{a}\mathrm{i}\mathrm{n}=\mathrm{s}\mathrm{u}\mathrm{n}\mathrm{n}\mathrm{y}|\mathrm{p}\mathrm{l}\mathrm{a}\mathrm{y}=\mathrm{y}\mathrm{e}\mathrm{s})=1$.

第二个条件与如下条件保持一定程度的一致:

• $P(\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{k}=\mathrm{s}\mathrm{u}\mathrm{n}\mathrm{n}\mathrm{y}|\mathrm{p}\mathrm{l}\mathrm{a}\mathrm{y}=\mathrm{y}\mathrm{e}\mathrm{s})+P(\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{k}=\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{c}\mathrm{a}\mathrm{s}\mathrm{t}|\mathrm{p}\mathrm{l}\mathrm{a}\mathrm{y}=\mathrm{y}\mathrm{e}\mathrm{s})+P(\mathrm{r}\mathrm{a}\mathrm{i}\mathrm{n}=\mathrm{s}\mathrm{u}\mathrm{n}\mathrm{n}\mathrm{y}|\mathrm{p}\mathrm{l}\mathrm{a}\mathrm{y}=\mathrm{y}\mathrm{e}\mathrm{s})=1$.

对于 $P(D_i)$ 也需要进行平滑:
$$P^L(D_i)=\frac{nP(D_i)+1}{n+c}\text{\hspace{1em}(8)}$$

考虑 Laplacian 平滑的优化目标为:
$$d(\mathbf{x})=\underset{1\le i\le k}{\mathrm{argmax}}\log P^L(D_i)+\sum _{j=1}^m\log P^L(x_j|D_i)\text{\hspace{1em}(9)}$$

3. 针对符号型数据的预测算法跟踪

请各位打开 日撸 Java 三百行（51-60天，kNN 与 NB）, 对照程序来理解.
399 行是入口, 转到 357 行.
359 行的数据, 可以换成本贴中的数据.

3.1 初始化

361 行初始化一个对象, 包括

• 从文件中读入数据 (111 行);
• 将最后一列设为决策属性 (118 行);
• 条件属性数为总属性数减 1 (119 行);
• 类别数为决策属性的属性值个数 (121) 行. 这一系列语句的解释, 请参见 Weka 中的数据表基本管理.

3.2 设置数据类型

362 行设置数据类型为符号型, 这个与数值型区别.

3.3 计算决策属性的分布

363 行计算决策属性 (play) 的分布.

• 142-146 行计算个数. 如 yes, no 在这个数据集上的出现次数分别是 9 和 5, 则该向量的值为 [9, 5].
• 149 行计算基本的分布, 为 $[\frac{9}{14},\frac{5}{14}]$.
• 150 行计算 Laplacian 分布, 为 $[\frac{9+1}{14+2},\frac{5+1}{14+2}]=[\frac{10}{16},\frac{6}{16}]$.
  至此, (8) 式需要的 $P^L(D_1)=\frac{10}{16}$, $P^L(D_2)=\frac{6}{16}$ 就获得了.

3.4 计算条件概率

364 行计算条件概率.

• 166 行分配空间用于计数.
  这里涉及到了三维数组, 它们分别对应于什么?
  我们需要计算 $P(\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{k}=\mathrm{s}\mathrm{u}\mathrm{n}\mathrm{n}\mathrm{y}\wedge \mathrm{p}\mathrm{l}\mathrm{a}\mathrm{y}=\mathrm{y}\mathrm{e}\mathrm{s})$ 这样的概率, 它涉及到了
  • 第一维确定哪个决策类别. 本例中是 play = yes. 总的决策类别数为 numClasses.
  • 第二维确定哪个条件属性. 本例中是 outlook, 即第 0 个属性. 总的条件属性数为 numConditions.
  • 第三维确定该条件属性的哪个值. 本例中是 sunny. 总的属性值个数为 3. 但对于不同的属性而言, 有不同的属性值个数, 所以在这里暂时无法确定空间.
    注意这里虽然用的是 double 类型, 但计算的是整数个数. double 只是为了让后面除法不要搞成整除.
• 167 行同理.
• 170-176 行则把第三维的空间分配好.
• 178-187 行进行计数类加. 其中, 185 行有个反向的索引, 将 tempClass 当作是下标来用. 额, 只有自己对着例子慢慢计算了.
• 190-198 行计算 Laplacian 概率, 获得式 (9) 连加的各项. 它最终用于 291 行.

3.5 预测

365 行进行预测.
254-257 行进行逐个样本的测试, 注意本程序仅测试了训练集的数据, 当然, 你很容易把它改成新的测试集.
265 行的方法根据两种数据分别选择, 现在选择的是 classifyNominal().

• 284 行这个循环对应的是 (5) 式中的 argmax, 即从几个类别中取概率最大那个.
• 285 行用的是决策属性的 Laplacian 平滑. 我们前面没讲为啥决策类平滑的原因, 自悟吧.
• 287 行这个循环就是 (5) 式中的累加.
• 292 行这个减号, 是从 (6) 式的除号来的 (注意 log 后乘法变加法, 除法变减法).
  367 行计算准确性并输出.

4. 处理数值型数据需要的理论

数值型数据, 没有办法使用 $P(\mathrm{h}\mathrm{u}\mathrm{m}\mathrm{i}\mathrm{d}\mathrm{i}\mathrm{t}\mathrm{y}=87)$, 因为湿度刚刚好为 87 (而不是 87.001) 的概率为 0. 实际上, 湿度为任何值的概率都为 0. 当然, $P(86\le \mathrm{h}\mathrm{u}\mathrm{m}\mathrm{i}\mathrm{d}\mathrm{i}\mathrm{t}\mathrm{y}<87)$ 的概率不为 0.
但是, 如果我们不想把湿度做成 $[86,87)$ 这样的区间 (即进行离散化), 能不能也用 NB 算法来预测呢? 可以的!
我们需要做两件事:

• 根据数据及分布假设, 求得概率密度函数 $p(\mathrm{h}\mathrm{u}\mathrm{m}\mathrm{i}\mathrm{d}\mathrm{i}\mathrm{t}\mathrm{y}=87)$, 这里是 $p$ 而不是 $P$;
• 直接用 $p$ 代替 (5) 式中的 $P$, 对, 就是这样简单粗暴.
  正态分布在实际中最常见, 它的写法如下:
  $$p(x)=\frac{1}{\sqrt{2\pi }\sigma }exp\left(?\frac{(x?\mu {)}^2}{2{\sigma }^2}\right)$$
  这里涉及两个参数: 均值 $\mu$ 和方差 $\sigma$. 通过有限的几个数据, 就可以把它们计算出来.
  我们把 (5) 式改造一下以适应数值型数据, 注意 $\sqrt{2\pi }$ 是常数可以去掉:
  $$d(\mathbf{x})=\underset{1\le i\le k}{\mathrm{argmax}}\log P^L(D_i)+\sum _{j=1}^m?\log {\sigma }_{ij}?\frac{(x_j?{\mu }_{ij}{)}^2}{2{\sigma }_{ij}^2}\text{\hspace{1em}(10)}$$
  这里的 ${\sigma }_{ij}$ 和 ${\mu }_{i}j$ 表示方差与均值都与类别、属性相关. 仅需要对于决策属性那里进行 Laplacian 平滑.

5. 针对数值型数据的预测算法跟踪

400 行是入口, 转到 375 行.
383 行的代码甚至与符号型数据的完全相同.

5.1 计算高斯分布的参数

384 行进行参数计算.

• 209 行分配空间. 这里只有两维, 分别是对应于决策属性值和各条件属性. 每个 GaussianParamters 对象有两个成员变量 mu $\mu$ 和 sigma $\sigma$.
• 215 和 216 行的循环负责填相应的元素.
• 220 到 229 行将第 i 个类别和第 j 个属性的属性值取出来.
• 232 行计算均值.
• 234-239 行计算方差.

5.2 预测

309 行这个方法负责预测.

• 314 行这个循环负责 $\mathrm{argmax}$
• 322 行这里进行概率的累加.

6. 小结

值型数据的代码居然比符号型的还短!
用其它分布的假设, 可以获得其它结果.

附录: 在这里没有用到的式子, 如果接下来我发现它们真没用, 就删除

全概率 1:
$$P(A)=P(AD)+P(A?D)=P(D)P(A|D)+P(?D)P(A|?D)\text{\hspace{1em}(2)}$$
其中, $?D$ 表示事件不发生.
这个式子的意思是, 事件 $D$ 与 $A$ 同时发生的概率, 加上事件 $?D$ 与事件 $A$ 同时发生的概率, 等于事件 $A$ 发生的概率.
例: $A$ 表示天气是晴天, 即 outlook = sunny; $D$ 表示要打球, 即 play = yes.
14 天中, 有 5 天 sunny, 则 $P(A)=P(\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{k}=\mathrm{s}\mathrm{u}\mathrm{n}\mathrm{n}\mathrm{y})=5/14$.
14 天中, 有 2 天 sunny 且打球, 则 $P(AD)=P(\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{k}=\mathrm{s}\mathrm{u}\mathrm{n}\mathrm{n}\mathrm{y},\mathrm{p}\mathrm{l}\mathrm{a}\mathrm{y}=\mathrm{y}\mathrm{e}\mathrm{s})=2/14$.
14 天中, 有 3 天 sunny 且不打球, 则 $P(AD)=P(\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{k}=\mathrm{s}\mathrm{u}\mathrm{n}\mathrm{n}\mathrm{y},\mathrm{p}\mathrm{l}\mathrm{a}\mathrm{y}=\mathrm{n}\mathrm{o})=3/14$.
该式的后一部分是通过将式 (1) 代入获得的.

全概率 2: 有的时候决策类不只是两种情况 (例如 iris 的种类为 $k=3$), 所以需要推广一下.
假设 $D_1$, $D_2$, $\dots$, $D_k$ 构成一个完备事件组，即它们两两互不相容，其和为全集, 并且 $P(D_i)>0$. 则
$$\begin{array}{ll}P(A)& =P(A{D}_1)+P(A{D}_2)+P(A{D}_k)\\ & =P(D_1)P(A|D_1)+P(D_2)P(A|D_2)+?+P(D_k)P(A|D_k)\\ & ={\sum }_{i=1}^{k}P(D_i)P(A|D_i)\end{array}\text{\hspace{1em}(3)}$$

$$\begin{array}{ll}P(D_i|x)& =\frac{P(x{D}_i)}{P(x)}=\frac{P(D_i)P(x|D_i)}{P(x)}\\ & =\frac{{\sum }_{i=1}^{k}P(D_i)P(A|D_i)}{P(x)}\end{array}$$

同理, $P(AB)=P(B)P(A|B)$.
因此,
$$P(A)=\frac{P(B)P(A|B)}{P(B|A)}\text{\hspace{1em}(2)}$$
令

$P(X=x)={\sum }_{k}P(X=x|Y=c_k)P(Y=c_k)$

$P(a_1=sunny)$
$=P(a_1=sunny\&play=P)+P(a_1=sunny\&play=N)$
$=P(a_1=sunny|play=P)P(play=P)+P(a_1=sunny|play=N)P(play=N)$