机器学习算法之朴素贝叶斯

概率分类法

基本问题：

假设有两类 $\omega_1$ 和 $\omega_2$
假设某样本 $x$ ，要么 $x \in \omega_1$ ，要么 $x \in \omega_2$

求解：
$P(\omega_1 \mid x)$ 与 $P(\omega_2 \mid x)$ ，且 $P(\omega_1 \mid x) + P(\omega_2 \mid x) = 1$

分类准则为：
$\begin {cases} if \quad P(\omega_1 \mid x) > P(\omega_2 \mid x),then \quad x \in \omega_1 \\ if \quad P(\omega_1 \mid x) < P(\omega_2 \mid x),then \quad x \in \omega_2 \end {cases}$

由贝叶斯公式可知：
$P(\omega_1 \mid x) = \frac {P(x,\omega_1)}{p(x)} = \frac {P(x \mid \omega_1)P(\omega_1)}{p(x)} \\ P(\omega_2 \mid x) = \frac {P(x,\omega_2)}{p(x)} = \frac {P(x \mid \omega_2)P(\omega_2)}{p(x)}$

分类准则变成：
$\begin {cases} if \quad P(x \mid \omega_1)P(\omega_1) > P(x \mid \omega_2)P(\omega_2),then \quad x \in \omega_1 \\ if \quad P(x \mid \omega_1)P(\omega_1) < P(x \mid \omega_2)P(\omega_2),then \quad x \in \omega_2 \end {cases}$
其中， $P(\omega_1)$ 和 $P(\omega_2)$ 叫做 $\omega$ 的先验概率； $P(x \mid \omega_1)$ 和 $P(x \mid \omega_2)$ 叫做 $x$ 在 $\omega$ 上的条件概率； $P(\omega_1 \mid x)$ 和 $P(\omega_2 \mid x)$ 叫做 $x$ 在 $\omega$ 上的后验概率。

注：应当更加关注先验概率。具体表现在：训练样本类别和真实场景中的样本类别比重（即类别不平衡度）应当大致相同。例如，训练人脸识别算法时，训练样本多是西方面孔，要想保证对于亚洲面孔的识别度，必须设法增加亚洲面孔所占比重。

此外，若先验概率未知，则假定所有先验概率相同。在此前提之下，分类准则为：
$\begin {cases} if \quad P(x \mid \omega_1) > P(x \mid \omega_2),then \quad x \in \omega_1 \\ if \quad P(x \mid \omega_1) < P(x \mid \omega_2),then \quad x \in \omega_2 \end {cases}$

于是，分类问题转变为概率密度估计问题，如何估计 $P(x \mid \omega)$ ，即给定一组 $\{ x_i \}_{i=1, \cdots, N} \in \omega$ ，如何求 $P(x \mid \omega)$ 。

朴素贝叶斯 (Naive Bayesian Classifier)

朴素贝叶斯法是基于贝叶斯定理和特征条件独立假设得分类方法。对于给定得训练数据集，首先基于特征条件独立假设学习输入/输出得联合概率分布；然后基于此模型，对给定得输入 $x$ ，利用贝叶斯定理求出后验概率最大得输出 $y$ 。朴素贝叶斯法实现简单，学习与预测得效率都很高，是一个常用得方法。

基本方法

设输入空间 $\chi \subseteq R^n$ 为 $n$ 维向量的集合，输出空间为类标记集合 $\gamma = \{ c_1, c_2, \cdots, c_K \}$ 。输入为特征向量 $x \in \chi$ ，输出为类标记(class label) $y \in \gamma$ 。 $X$ 是定义在输入空间 $\chi$ 的随机向量， $Y$ 是定义在输出空间 $\gamma$ 上的随机变量。 $P(X,Y)$ 是 $X$ 和 $Y$ 的联合概率分布。训练样本集
$T = \{ (x_1,y_1), (x_2,y_2), \cdots, (x_N,y_N) \}$
由 $P(X,Y)$ 独立同分布产生。具体学习先验概率分布和条件概率分布。

先验概率分布：
$P(Y = c_k), k = 1, 2, \cdots, K$
条件概率分布：
$P(X=x \mid Y=c_k) = P(X^{(1)}=x^{(1)}, \cdots, X^{(n)}=x^{(n)} \mid Y=c_k), k = 1, 2, \cdots, K$
朴素贝叶斯法对条件概率做了条件独立性的假设。这是一个较强的假设，朴素贝叶斯法也由此得名。具体假设如下：
$P(X=x \mid Y=c_k) = P(X^{(1)}=x^{(1)}, \cdots, X^{(n)}=x^{(n)} \mid Y=c_k)$
$= \prod_{j=1}^n P(X^{(j)} = x^{(j)} \mid Y = c_k)$
朴素贝叶斯法实际上学习到生成数据的机制，属于生成模型。条件独立假设等于是说用于分类的特征在类确定的条件下都是条件独立的，这会大大降低朴素贝叶斯法的难度，但有时也会牺牲一定的分类准确率。

朴素贝叶斯法分类时，对给定的输入 $x$ ，通过学习到的模型计算后验概率分布 $P(Y=c_k \mid X=x)$ ，将后验概率最大的类作为 $x$ 的类输出。后验概率根据贝叶斯定理可得：
$P(Y=c_k \mid X=x) = \frac {P(X=x \mid Y=c_k) P(Y=c_k)} {\sum_{k} P(X=x \mid Y=c_k) P(Y = c_k)}$
将上述两个式子结合，可以得到朴素贝叶斯分类的基本公式：
$P(Y=c_k \mid X=x) = \frac {P(Y=c_k) \prod_{j} P(X_{(j)} = x_{(j)}) P(Y=c_k)} {\sum_{k} P(Y=c_k) \prod_{j} P(X_{(j)} = x_{(j)})}$
所以，朴素贝叶斯分类器可表示为：
$y = \mathop {\arg\max} \limits_{c_k} P(Y=c_k) \prod_{j} P(X_{(j)} = x_{(j)})$

极大似然估计

概率模型的训练过程就是参数估计(parameter estimation)过程。对于参数估计，频率注意学派认为参数虽然未知，但却是客观存在的固定值，因此，可通过优化似然函数等准则来确定参数值；贝叶斯学派则认为参数是未观察到的随机变量，其本身也可有分布，因此，可假定参数服从一个先验分布，然后基于观测到的数据来计算参数的后验分布。源自频率主义学派的极大似然估计(Maximum Likelihood Estimation，简称MLE)，根据数据采样来估计概率分布的经典方法。

在朴素贝叶斯法中，学习意味着估计 $P(Y=c_k)$ 和 $P(X^{(j)} = x^{(j)} \mid Y=c_k)$ ，可以应用极大似然估计法估计相应的概率。先验概率 $P(Y = c_k)$ 的极大似然估计是
$P(Y = c_k) = \frac {\sum_{i=1}^N I (y_i = c_k)} {N}, k = 1, 2, \cdots, K$
设第 $j$ 个特征 $x^{(j)}$ 可能取值的集合为 $\{ a_{j1}, a_{j2}, \cdots, a_{jS_j} \}$ ，条件概率 $P(X^{(j)} = a_{jl} \mid Y = c_k)$ 的极大似然估计是
$P(X^{(j)} = a_{jl} \mid Y = c_k) = \frac {\sum_{i=1}^N I(x_i^{(j)} = a_{jl}, y_i = c_k)} {\sum_{i=1}^N I (y_i = c_k)}$
$j = 1, 2, \cdots, n; \quad l = 1, 2, \cdots, S_j; \quad k = 1, 2, \cdots, K$
式中， $x_i^{(j)}$ 是第 $i$ 个样本的第 $j$ 个特征； $a_{jl}$ 是第 $j$ 个特征可能取得第 $l$ 个值； $I$ 为指示函数。

朴素贝叶斯算法流程：

输入：训练数据 $T = \{ (x_1,y_1), (x_2,y_2), \cdots , (x_N,y_N) \}$ ，其中： $x_i = (x_i^{(1)}, x_i^{(2)}, \cdots, x_i^{(n)})^T$ ， $x_i^{(j)}$ 是第 $i$ 个样本的第 $j$ 个特征， $x_i^{(j)} \in \{ a_{j1}, a_{j2}, \cdots, a_{jS_j} \}$ ， $a_{jl}$ 是第 $j$ 个特征可能取的第 $l$ 个值， $j = 1, 2, \cdots, n$ ， $l = 1, 2, \cdots, S_j$ ， $y_i \in \{ c_1, c_2, \cdots, c_K \} .$
$\qquad$ 实例 $x$ ；
输出：实例 $x$ 的分类

计算先验概率及条件概率
$P(Y = c_k) = \frac {\sum_{i=1}^N I(y_i = c_k)} {N}, k = 1, 2, \cdots, K$
$P(X^{(j)} = a_{jl} \mid Y = c_k) = \frac {\sum_{i=1}^N I(x_i^{(j)} = a_{jl}, y_i = c_k)}{\sum_{i=1} {N} I(y_i = c_k)}$
$j = 1, 2, \cdots, n; \quad l = 1, 2, \cdots, S_j; \quad k = 1, 2, \cdots, K$
对于给定的实例 $x = (x^{(1)}, x^{(2)}, \cdots, x^{(n)})^T$ ，计算
$P(Y = c_k) \prod_{j=1}^n P(X^{(j)} = x^{(j)} \mid Y = c_k), k = 1, 2, \cdots, K$
确定实例 $x$ 的类
$y = \mathop {\arg \max} \limits_{c_k} \prod_{j=1}^n P(X^{(j)} = x^{(j)} \mid Y = c_k)$

实际应用：垃圾邮件分类

输入：一个文件 $d$ ，其中 $d = \{ w_1, w_2, \cdots, w_p \}$ ， $w_i$ 表示组成文本的单词。

输出： $d \in C_1$ ，或者 $d \in C_2$

训练样本： $\{ (d_i,c_i) \}_{i=1, \cdots, N}$

学习目标： $P(d \mid C_1)$ 和 $P(d \mid C_2)$

$P(d \mid C) = P(\{ w_1, w_2, \cdots, w_n \} \mid C) = \prod_{i=1}^n P(w_i \mid C)$
$P(w \mid C_j) = \frac {count(w,C_j) + 1} {\sum_{w \in V} count(w,C_j) + \mid V \mid}$
其中， $\prod_{i=1}^n P(w_i \mid C)$ 由独立性假设推出。
先验概率为：
$P(C_1) = \frac {count(C_1)} {count(C_1,C_2)}$
判别准则：
$\begin {cases} d \in C_1,\quad P(C_1)P(d \mid C_1) > P(c_2)P(d \mid C_2) \\ d \in C_2,\quad P(C_1)P(d \mid C_1) < P(c_2)P(d \mid C_2) \end {cases}$

最后编辑于：2021.12.28 23:11:05

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 214,100评论 6赞 493
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 91,308评论 3赞 388
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 159,718评论 0赞 349
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,275评论 1赞 287
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,376评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,454评论 1赞 292
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,464评论 3赞 412
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,248评论 0赞 269
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,686评论 1赞 306
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,974评论 2赞 328
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,150评论 1赞 342
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,817评论 4赞 337
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,484评论 3赞 322
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,140评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,374评论 1赞 267
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,012评论 2赞 365
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,041评论 2赞 351