#机器学习# 文章列表 浅入浅出:PageRank算法 使用 TextRank 算法为文本生成关键字和摘要 基于物品的协同过滤 如何使用MapReduce实现基于物品的协同过滤(1) 如何使用MapReduce实现基于物品的协同过滤(2) 浅入浅出:K近邻算法 使用mahout下的朴素贝叶斯分类器对新闻分类 使用Affinity Propagation进行聚类 K-medoids聚类 矩阵分解在推荐系统中的应用:NMF和经典SVD实战 使用特征递归消除筛选特征 如何分配权重 比较NMF、PCA和VQ 方差和协方差 基于SVD的协同过滤 逻辑斯谛回归代码实现 隐语义模型和NMF(非负矩阵分解) 使用PCA处理MNIST数据集 使用GBDT选取特征 基于贝叶斯的文本分类系统的数据库设计 在hadoop1.2.1上安装mahout 0.9 Hadoop 2.4 实现Kmeans聚类算法 在Iris数据集上对比PCA、LDA、NMF 基于贝叶斯的文本分类实战 单层决策树 Logistic regression(逻辑斯蒂回归) 基于用户的协同过滤 词袋模型与文档-词矩阵 如何实现拼音与汉字的互相转换 梯度下降法 如何判定相似度 MovieLens数据集介绍 基于KNN的文本分类实战 Jasper文本分类系列博客阅读摘录 使用 Mean Shift进行聚类 朴素贝叶斯的三个常用模型:高斯、多项式、伯努利 使用决策树处理iris数据集 浅入浅出:从Kmeans到Kmeans++ 如何持久化scikit-learn中训练好的模型 浅入浅出:DBSCAN聚类算法(1) 浅入浅出:DBSCAN聚类算法(2) 2015阿里移动推荐算法比赛第一赛季总结 爬山算法 使用朴素贝叶斯分类器划分邮件 层次聚类 基于MapReduce的频繁项集挖掘 搜狗实体关系提取比赛

使用朴素贝叶斯分类器划分邮件


#机器学习#


2014-05-20

朴素贝叶斯分类器,基于贝叶斯定理,是一个表现良好的分类方法。

1、推导

1.1、条件概率:

P(A|B) = P(A,B)/P(B)

A和B是随机事件,P(A/B)也就是在事件B发生的前提下事件A发生的概率。
为了易读性,笔者将P(AB)写成P(A,B)。

如果有大量的数据,我们可以通过统计结果计算条件概率。例如假设有1000封邮件,垃圾邮件有300封,出现单词购买的邮件为50封,而即是垃圾邮件又同时出现了购买这个单词的邮件共有20封。如果把垃圾邮件看成事件A,邮件里出现单词购买看成事件B,那么P(A)是指垃圾邮件出现的概率,因为没考虑其他的因素对A的影响,也可以将P(A)看做A的先验概率,这里:

P(A) = 300/1000 = 0.3

同理,

P(B) = 50/1000 = 0.05

P(A,B)是指AB同时发生的概率,

P(A,B) = 20/1000 = 0.02

根据条件概率的公式,能够得到

P(A|B) = 0.02 / 0.05 = 0.4

因为有B的影响,P(A|B)也叫做A的后验概率。

1.2、相互独立事件

如果事件A和B是相互独立的,代表着A发生的可能性对B发生的可能性没有影响,B也对A没有影响,在这种情况下,

P(A,B) = P(A)*P(B) 

既然A和B之间没有相互影响,那么

P(A|B) = P(A,B)/P(B) 
        = P(A)
P(B|A) = P(A,B)/P(A) 
        = P(B)

1.3、贝叶斯定理

P(A|B) = P(A,B)/P(B)

很容易推出:

P(A|B) = P(B|A)*P(A)/P(B)

这也就是贝叶斯公式了。

1.4、朴素贝叶斯分类器(naive Bayes classifier)

首先有以下定理:

如果B、C相互独立,那么P(B|C,A) = P(B|A)。

设有事件AB1B2,那么在B1、B2同时发生的前提下,A发生的概率是:

P(A|B1,B2) = P(B1,B2|A)*P(A) / P(B1,B2)

如果B1和B2相互独立,那么有

P(B1,B2|A) = P(B1|B2,A)*P(B2|A)
            = P(B1|A)*P(B2|A)

于是,

P(A|B1,B2) = P(B1,B2|A)*P(A) / P(B1,B2)
            = P(B1|A)*P(B2|A)*P(A) / P(B1,B2)

下面套用一下阮一峰博客中的内容。

阮一峰博客内容->start

假设某个体有n项特征(Feature),分别为F1、F2、...、Fn。现有m个类别(Category),分别为C1、C2、...、Cm。贝叶斯分类器就是计算出概率最大的那个分类,也就是求下面这个算式的最大值:

P(C|F1,F2,...,Fn)
  = P(F1,F2,...,Fn|C)*P(C) / P(F1,F2,...,Fn)

由于 P(F1,F2,...,Fn)对于所有的类别都是相同的,可以省略,问题就变成了求

P(F1,F2,...,Fn|C)*P(C)

的最大值。 朴素贝叶斯分类器则是更进一步,假设所有特征都彼此独立,因此

P(F1,F2,...,Fn|C)*P(C)
  = P(F1|C)*P(F2|C)* ... *P(Fn|C)*P(C)

阮一峰博客内容->end

朴素贝叶斯分类器假设所有特征都彼此独立存在一定的不合理性,不过该分类器一般能取得很好的分类效果。

2、判断邮件是否为垃圾邮件

判断邮件是否为垃圾邮件虽然是一个二元判断,不过通过朴素贝叶斯分类器得到的结果是一封邮件属于(或者不属于)垃圾邮件的可能性。

假定我们现在有1000封被标识的邮件作为训练集,训练集一般是人工标识,分为“垃圾邮件”、“正常邮件”。注意,训练集不宜人为地从大量邮件中有意挑拣,而应随机挑拣。

然后我们从邮件中选取特征,例如我们把单词“购买”是否出现在邮件中看作是该邮件的一个特征,训练时候应该记录含有单词“购买”的垃圾邮件有多少封,含有单词“购买”的正常邮件有多少封,按照这个思路,我们得到以下表格:

特征\统计 正常邮件 垃圾邮件 汇总
“购买” 10 50 60
“淘宝” 8 56 64
“开心” 60 3 63
“编程” 20 15 35
汇总 98 124 222

好了,现在有一封邮件需要分类,假设它有购买淘宝开心编程四个特征,那么其属于正常邮件的可能性是:

10/98 * 8/98 * 60/98 * 20/98 * 98/222
=  0.000459

属于垃圾邮件的可能性是:

50/124 * 56/124 * 3/124 * 15/124 * 124/222
=   0.00029768

结果是该邮件更有可能是正常邮件

如果邮件只有有开心编程两个特征,那么其属于正常邮件的可能性是:

60/98 * 20/98 * 98/222
= 0.0551571

属于垃圾邮件的可能性是:

3/124 * 15/124 * 124/222
= 0.0016346992153443768

结果是该邮件更有可能是正常邮件

3、让分类器更合理

如果我们的统计结果是这样的:

特征\统计 正常邮件 垃圾邮件 汇总(求和)
“购买” 10 50 60
“淘宝” 8 56 64
“开心” 63 0 63
“编程” 20 15 35
汇总(求和) 101 121 222

具有特征开心的垃圾邮件有0封。如果某封邮件具有购买淘宝开心这三个特征,按照上面的思路,该邮件属于正常邮件的可能性是:

10/101 * 8/101 * 63/101 * 101/222
= 0.00222553

属于垃圾邮件的可能性是:

50/121 * 56/121 * 0/121 * 121/222
= 0

这意味着,只要邮件里有“开心”,那么它就不是垃圾邮件(属于垃圾邮件的可能性为0),这显然是不合理的。

对此,我们可以对P(F1|C)(以及P(F2|C)、P(F3|C)等)做如下处理(加权平均):

P2(F1|C) = (1*0.5 + sum(F1)*P(F1|C)) / (1 + sum(F1))
          = (0.5 + sum(F1)*P(F1|C)) / (1 + sum(F1))

其中,若F1是开心,那么sum(F1) = 63+0 = 63

于是,属于正常邮件的可能性是:

((0.5 + 10/101 * 60) / 61) * ((0.5 + 8/101 * 64) / 65) * ((0.5 + 63/101 * 63) / 64) * 101/222
=0.0025593104680632236

属于垃圾邮件的可能性是:

((0.5 + 50/121 * 60) / 61) * ((0.5 + 56/121 * 64) / 65) * ((0.5 + 0/121 * 63) / 64) * 121/222
= 0.0008181611103439531

这封邮件还是倾向于正常邮件,不过计算方式更合理了。

4、如何由计算结果判断类别

如果计算出一封邮件属于正常邮件的概率是0.05,属于垃圾邮件的概率是0.006,基本可以肯定这是一封正常邮件。不过,如果一封邮件属于正常邮件的概率是0.05,属于垃圾邮件的概率是0.049,那么这封邮件是否该划分为垃圾邮件?也许在这个时候就要在训练之后再填上一个分类了——不确定分类

首先,设定一个阈值T(大于1),待标注数据D,两个分类C0和C1,如果:

P(C0|D) / P(C1|D) > T

那么,D属于类别C0。如果:

P(C1|D) / P(C0|D) > T

那么,D属于类别C1。

5、如果有多个类别

对于朴素贝叶斯分类器而言,多个分类和二分类没什么差别,就是训练的时候多加个分类而已。

6、参考资料

朴素贝叶斯分类器的应用
Programming Collective Intelligence
Naive Bayes and Logistic Regression


( 本文完 )