挖掘算法(1)朴素贝叶斯算法

原文:http://www.blogchong.com/post/NaiveBayes.html

1 文档说明

该文档为朴素贝叶斯算法的介绍和分析文档,并且结合应用实例进行了详细的讲解。

其实朴素贝叶斯的概念以及流程都被写烂了,之所以写这些是方便做个整理,记录备忘。而实例部分进行了详细的描述,网络上该实例比较简单,没有过程。

至于最后部分,则是对朴素贝叶斯的一个扩展了,当然只是简单的描述了一下过程,其中涉及到的中文分词以及TFIDF算法,有时间再具体补上。

2 算法介绍

2.1 贝叶斯定理

(1)问题引申:已知某条件概率,如何得知两个事件交换之后的概率。也就是在已知P(A|B)的情况下如何求得P(B|A);

(2)条件概率:P(A|B)表示事件B已经发生的前提下,事件A发生的概率,叫做事件B发生下事件A发生的条件概率;

   (3)基本求解公式:P(A|B)=P(AB)/P(B) //AB同时发生的概率处于B发生的概率;

   (4)贝叶斯定理:P(B|A)=P(A|B)*P(B)/P(A);

2.2 朴素贝叶斯算法

2.2.1 朴素贝叶斯思想基础

对于给出的待分类项,求解在此项出现的条件下各个类别出现的概率,哪个最大,就认为此待分类项属于哪个类别;

所以朴素贝叶斯分类器其实根本思想就是通过分类概率以及条件概率,计算分类的后验概率,然后比较,最大则说明该项属于该类别。

2.2.2 朴素贝叶斯分类过程

(1)设x={a1,a2,…,am}为一个待分类项,而每个a为x的一个特征属性。

(2)有类别集合C={y1,y2,…,yn}。

(3)计算P(y1|x),P(y2|x),…,P(yn|x)。//这些是后验概率

(4)如果P(yk|x)=max{ P(y1|x),P(y2|x),…,P(yn|x)},则x属于yk。

关键点,计算条件概率(如上第三步)

1)找到一个已知分类的待分类项集合,这个集合叫做训练样本集。

2)统计得到在各类别下各个特征属性的条件概率估计:

P(a1|y1), P(a2|y1),…, P(am|y1); P(a1|y2), P(a2|y2),…, P(am|y2); P(a1|yn), P(a2|yn),…, P(am|yn)

//需要通过条件概率和分类概率计算后验概率

3)如果各个特征属性是条件独立的,则根据贝叶斯定理有如下推导:

P(yi|x) = P(x|yi)P(yi)/P(x)    //实际计算P(x|yi)P(yi),因为P(x)都相同

4)因为分母对于所有类别为常数,因为我们只要将分子最大化皆可。又因为各特征属性是条件独立的,所以有:

P(x|yi)P(yi) = P(a1|yi)| P(a2|yi)…P(am|yi)P(yi) = P(yi)∏P(aj|yi);     //即按条件概率求积

2.2.3 朴素贝叶斯实现流程

可以看到,整个朴素贝叶斯分类分为三个阶段:

第一阶段--准备工作阶段:

这个阶段的任务是为朴素贝叶斯分类做必要的准备,主要工作是根据具体情况确定特征属性,并对每个特征属性进行适当划分,然后由人工对一部分待分类项进行分类,形成训练样本集合。这一阶段的输入是所有待分类数据,输出是特征属性和训练样本。

这一阶段是整个朴素贝叶斯分类中唯一需要人工完成的阶段,其质量对整个过程将有重要影响,分类器的质量很大程度上由特征属性、特征属性划分及训练样本质量决定。

第二阶段--分类器训练阶段

这个阶段的任务就是生成分类器,主要工作是计算每个类别在训练样本中的出现频率及每个特征属性划分对每个类别的条件概率估计,并将结果记录。

其输入是特征属性和训练样本,输出是分类器。这一阶段是机械性阶段,根据前面讨论的公式可以由程序自动计算完成。

第三阶段--应用阶段:

这个阶段的任务是使用分类器对待分类项进行分类,其输入是分类器和待分类项,输出是待分类项与类别的映射关系。这一阶段也是机械性阶段,由程序完成。


2.3 条件概率求解补充

在计算特征属性的条件概率时,若特征属性分布非离散值而是连续值,则一般情况下会符合正态分布的特点,可以通过公式计算条件概率:

且满足

注:

(1)第一个参数为特征属性的均值:μ

(2)而第二个参数为特征属性方差:σ^2

(3)条件概率:P(ak|yi)


2.4 算法分析

朴素贝叶斯分类器是“有监督分类”中的一个重要方法。它虽然简单,但是在当前实际应用中依然占有很大的比重,它具有如下几个特点:

(1)     容易构造,模型的参数的估计不需要任何复杂的迭代求解框架,因此该方法适用规模巨大的数据集;

(2)     容易理解,因此即使是不熟悉分类技术的用户也能够此方法的运作过程;

(3)     分类效果优良,对于任何应用即使它不是最好的分类方法,但是它是最稳健的分类方案;


3 应用实例

//病人分类实例

3.1 实例描述

//拥有一批病例表,通过病症,推断患者患病类型。

病历表:症状 职业 疾病

喷嚏 护士 感冒 18人

喷嚏 教师 感冒 12人

喷嚏 农夫 感冒 7人

喷嚏 工人 感冒 3人

喷嚏 护士 过敏 1人

喷嚏 农夫 过敏 13人

喷嚏 工人 过敏 16人

喷嚏 农夫 脑震荡 3人

喷嚏 工人 脑震荡 7人

头痛 工人 感冒 10人

头痛 教师 感冒 12人

头痛 农夫 感冒 5人

头痛 护士 感冒 13人

头痛 工人 过敏 8人

头痛 护士 过敏 2人

头痛 农夫 过敏 10人

头痛 教师 脑震荡 1人

头痛 农夫 脑震荡 4人

头痛 工人 脑震荡 15人

//总人数:160人

分类要求:

假设又来了一个病人,拥有病症(喷嚏),职业(工人),求其最有可能患病类型?


3.2 朴素贝叶斯分类过程

3.2.1 准备阶段

确定特征属性:

分析如下,疾病为类别集合,患病的人为待分类集合(X),症状和职业为特征属性集合。

//保证样本特征属性不相干

获取训练样本:

病例表则为训练样本。

3.2.2 分类器训练阶段

对每个类别计算P(Yi):

类别划分:

C={C0:感冒;C1:过敏;C2:脑震荡};//C0=80;C1=50;C2=30

则有类别概率如下(先验概率):

P(C0)=1/2;P(C1)=5/16;P(C2)=3/16

对每个特征属性计算所有划分的条件概率:

特征属性:

症状A0={A00:喷嚏;A01:头痛};

职业A1={A10:护士;A11:农夫;A12:工人;A13:教师};

计算特征属性划分概率:     //计算症状划分概率

P(A00|C0)=1/2 ; P(A01|C0)=1/2 ;

P(A00|C1)=3/5 ; P(A01|C1)=2/5 ;

P(A00|C2)=1/3 ; P(A01|C2)=2/3 ;

//计算职业划分概率

P(A10|C0)=31/80 ; P(A11|C0)=12/80 ; P(A12|C0)=13/80 ; P(A13|C0)=24/80 ;

P(A10|C1)=3/50 ; P(A11|C1)=23/50 ; P(A12|C1)=24/50 ; P(A13|C1)=0 ;

P(A10|C2)=0 ; P(A11|C2)=7/30 ; P(A12|C2)=22/30 ; P(A13|C2)=1/30 ;

3.2.3 应用阶段

朴素贝叶斯分类器:

患者特征属性:

A00(喷嚏);A12(工人);

分类器鉴别(计算后验概率):

C0(感冒):P(C0)P(X|C0)=P(C0)P(A00|C0)P(A12|C0)=(1/2)*(1/2)*(13/80)=13/320=0.040625

C1(过敏):P(C1)P(X|C1)=P(C1)P(A00|C1)P(A12|C1)=(5/16)*(3/5)*(24/50)=9/100=0.09

C2(脑震):P(C2)P(X|C2)=P(C2)P(A00|C2)P(A12|C2)=(3/16)*(1/3)*(22/30)=11/240=0.04583

判断:

通过分类器进行分类,其过敏(C1)的概率最大。


3.3 实例补充

(1)原始例子只有6个样本,笔者扩充到160个,构造的过程中可能存在误差,该实例只是用来说明如何使用朴素贝叶斯分类器进行分类;

(2)通过该实例主要是要掌握朴素贝叶斯分类器的具体使用;

(3)训练样本尽量大,分类才会更准确,属性划分尽量合理;

(4)属性划分频率通过统计的方式计算;

(5)其他著名实例:账号检测,性别分类 ,垃圾邮件分类等;


4 MapReduce实现

若是单纯的以MapReduce进行朴素贝叶斯分类器进行实例分类,过程比较简单,使用一个MapReduce进行训练样本进行训练得出分类器即可。但实际情况往往是提供的样本是一个复杂样本,就连特征属性就未进行划分。

以文本分类作为例子,首先文本类样本的特征属性是单个的词,若是英文样本则直接进行拆分即可,若是中文样本,则需要进行中文分词,中文分词又是一个复杂过程。

4.1 文本分类过程

以微博样本作为实例:

//中文分词可以通过ITCLAS分词器进行分词处理;

//特征词的Wk的判断参数:计算其TFIDF值(TFIDF算法);

(1)     第一个MapReduce统计训练样本(微博)中的总文档数、训练样本中出现特征词Wk的文档数(使用中文分词器itclas进行文档分词),计算每类中每个特征词的TF值(词频);

//分别有以下几个value输出:

1)       类Cj中特征词Wk的TF值;//TF=特征词出现次数/该文档总词数

2)       类Cj中出现Wk的文档数;

3)       训练样本中出现的Wk的文档总数;

4)       训练样本文档的总数;

(2)     第二个MR根据第一个MR的输出计算TFIDF值(TFIDF=tfik*log(N/n)),具体过程为Map端进行IDF计算,Reduce端进行TF*IDF计算;

//分别有以下几个value输出:

1)       每类特征词的TFIDF值;

(3)     第三个MR输入判别文档(一条微博),提取特征词,然后根据第二个MR中计算的TFIDF值,计算出最大的后验概率,进行分类。

4.2 实现补充

(1)     在实际的处理过程中,必须控制好ITCLAS分词的粒度,准确的提取特征词(对干扰词进行排除操作);

(2)     TFIDF算法在实际应用中,可以进行适当的改进;

(3)     之所以依赖MR进行处理,是依靠Hadoop对大批量样本的处理能力,能够快速的将样本训练完毕;


5 文档小结

文档仅用于备忘,若是其他朋友能够用到那就再好不过了。有兴趣的朋友可以去了解一下itclas中文分词,还有文本分类中的TFIDF算法等。

此外笔者水平有限,欢迎指正文中的各种问题。一起探讨,一起学习!

时间: 10-22

挖掘算法(1)朴素贝叶斯算法的相关文章

初识分类算法(3)-----朴素贝叶斯算法

1. 例子引入:如上篇的play or not 例子. 未知分类的样本:D:<A=sunny, B=cool, C=high ,D=strong>,  是 or 否? 我们要判断该样本的分类,即比较该样本属于是的概率大还是否的概率大 P(是/否|A=sunny, B=cool, C=high ,D=strong) P(是|A=sunny, B=cool, C=high ,D=strong)=P(是,(A=sunny, B=cool, C=high ,D=strong))/P(A=sunny,

C#编程实现朴素贝叶斯算法下的情感分析

C#编程实现 这篇文章做了什么 朴素贝叶斯算法是机器学习中非常重要的分类算法,用途十分广泛,如垃圾邮件处理等.而情感分析(Sentiment Analysis)是自然语言处理(Natural Language Progressing)中的重要问题,用以对文本进行正负面的判断,以及情感度评分和意见挖掘.本文借助朴素贝叶斯算法,针对文本正负面进行判别,并且利用C#进行编程实现. 不先介绍点基础? 朴素贝叶斯,真的很朴素 朴素贝叶斯分类算法,是一种有监督学习算法,通过对训练集的学习,基于先验概率与贝叶

【数据挖掘】朴素贝叶斯算法计算ROC曲线的面积

题记:          近来关于数据挖掘学习过程中,学习到朴素贝叶斯运算ROC曲线.也是本节实验课题,roc曲线的计算原理以及如果统计TP.FP.TN.FN.TPR.FPR.ROC面积等等.往往运用ROC面积评估模型准确率,一般认为越接近0.5,模型准确率越低,最好状态接近1,完全正确的模型面积为1.下面进行展开介绍: ROC曲线的面积计算原理 一.朴素贝叶斯法的工作过程框架图 二.利用weka工具,找到训练的预处理数据 1.利用朴素贝叶斯算法对weather.nominal.arff文件进行

统计学习方法 -&gt; 朴素贝叶斯算法

需要知道的是在什么时候可以用朴素贝叶斯算法:需要保证特征条件独立. 主要过程是学习输入和输出的联合概率分布. 预测的时候,就可以根据输入获得对打后验概率对应的输出y. 先验概率:已知输出,求输入.后验概率相反. 简单来说朴素贝叶斯算法,就是在对样本进行学习之后,到了需要做决策的时候,给定x,给出最大概率的y.这个本质上就是一个典型的后验概率模型.不过在该模型的算法推到上,还用到了先验概率的计算.但注意:最终朴素贝叶斯就是一种后验概率模型求P(y|x). 后验概率模型有一个好处,相当于期望风险最小

朴素贝叶斯算法及实现

1.朴素贝叶斯算法介绍 一个待分类项x=(a,b,c...),判断x属于y1,y2,y3...类别中的哪一类. 贝叶斯公式: 算法定义如下: (1).设x={a1, a2, a3, ...}为一个待分类项,而a1, a2, a3...分别为x的特征 (2).有类别集合C={y1, y2,  y3,  ..} (3).计算p(y1|x), p(y2|x), p(y3|x), .... (4).如果p(y(k)|x)=max{p(y1|x), p(y2|x), p(y3|x), ....},则x属于

朴素贝叶斯算法资料整理和PHP 实现版本

朴素贝叶斯算法简洁 http://blog.csdn.net/xlinsist/article/details/51236454 引言 先前曾经看了一篇文章,一个老外程序员写了一些很牛的Shell脚本,包括晚下班自动给老婆发短信啊,自动冲Coffee啊,自动扫描一个DBA发来的邮件啊, 等等.于是我也想用自己所学来做一点有趣的事情.我的想法如下: 首先我写个scrapy脚本来抓取某个网站上的笑话 之后写个Shell脚本每天早上6点自动抓取最新的笑话 然后用朴素贝叶斯模型来判断当前的笑话是否属于成

数据挖掘|朴素贝叶斯算法

作者:张一 链接:https://zhuanlan.zhihu.com/p/21571692 来源:知乎 著作权归作者所有.商业转载请联系作者获得授权,非商业转载请注明出处. 因为后期的项目将涉及到各种各样的价格数据处理问题,所以我们现在开始学习一些简单的数据清洗与算法的知识.关于算法,以前听起来觉得好高大上,现在开始学,觉得书上的描述并不是很通俗易懂,所以用自己的语言来简要写一下这些算法~ 注:非商业转载注明作者即可,商业转载请联系作者授权并支付稿费.本人已授权"维权骑士"网站(ht

朴素贝叶斯算法原理及实现

朴素贝叶斯算法简单高效,在处理分类问题上,是应该首先考虑的方法之一. 1.准备知识 贝叶斯分类是一类分类算法的总称,这类算法均以贝叶斯定理为基础,故统称为贝叶斯分类. 这个定理解决了现实生活里经常遇到的问题:已知某条件概率,如何得到两个事件交换后的概率,也就是在已知P(A|B)的情况下如何求得P(B|A).这里先解释什么是条件概率: 表示事件B已经发生的前提下,事件A发生的概率,叫做事件B发生下事件A的条件概率.其基本求解公式为:. 下面不加证明地直接给出贝叶斯定理: 2.朴素贝叶斯分类 2.1

朴素贝叶斯算法(Naive Bayes)

朴素贝叶斯算法(Naive Bayes) 阅读目录 一.病人分类的例子 二.朴素贝叶斯分类器的公式 三.账号分类的例子 四.性别分类的例子 生活中很多场合需要用到分类,比如新闻分类.病人分类等等. 本文介绍朴素贝叶斯分类器(Naive Bayes classifier),它是一种简单有效的常用分类算法. 回到顶部 一.病人分类的例子 让我从一个例子开始讲起,你会看到贝叶斯分类器很好懂,一点都不难. 某个医院早上收了六个门诊病人,如下表. 症状 职业 疾病 打喷嚏 护士 感冒  打喷嚏 农夫 过敏