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

阅读量：5917 次

发布时间：2019-06-19

本文共 4397 字，大约阅读时间需要 14 分钟。

原文：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值，计算出最大的后验概率，进行分类。