朴素贝叶斯改进及其应用

1、贝叶斯定理

设是类标号未知的数据样本，为某种假设，数据样本 属于某特定的类 C ，对于该分类问题，期望确定，即给定观测数据样本，假定成立的概率，称为后验概率，或称条件下的后验概率。分类就是要确定。

例如，假定数据样本集由顾客组成，用他们的年龄和收入情况进行分类。假定表示顾客的年龄在31岁到40之间并且中等收入，表示顾客将购买电脑，则反映的是观察到顾客的年龄在31岁到40之间并且中等收入时，将购买电脑的确定程度。为先验概率，在无论顾客的年龄和收入情况而购买电脑的概率。后验概率比先验概率基于更多的背景知识，而是独立于的。与之类似，是在条件下，的后验概率，即已知顾客购买电脑，其年龄在31岁到40岁之间并且中等收入的概率。由于通常情况下难以直接计算，我们可以利用贝叶斯定理，通过相对容易计算的，来求解。

贝叶斯定理提供了一种由，和计算的方法，具体是：

2、朴素的贝叶斯分类器

朴素贝叶斯分类就是假定一个属性值对给定类的影响独立于其他属性的值，该假定称作类条件独立，做此假定是为了简化计算，在此意义下称为“朴素的”。朴素贝叶斯分类的工作过程如下：

（1）    每个数据样本用一个n维特征向量表示，分别描述n个属性样本的n个度量。 

（2）    假定m个类。给定一个未知的数据样本，朴素贝叶斯分类将未知的样本分配给类，当且仅当

根据贝叶斯定理，最大化即可进行分类，其中令最大的类称为最大后验假设。

（3）    其中代表属性集取值为时的联合概率，为常数，所以最大化时只需使最大即可。类的先验概率可以用计算，其中是类中训练样本数，是训练样本总数。

（4）    给定具有许多属性的数据集 ，计算 即的开销可能非常大。为降低计算的开销，可以做类条件独立的朴素假定。在此情况下有：

概率可以由训练样本估值，其中：

（a）    如果是 离散 属 性，,其中是样本集中属于类型的样本个数。是样本集中于类型 且属性取值为的样本个数。

（b）    若是连续值属性， 常用的处理方法有两种： 一是对其离散化， 然后按照离散值处理； 另一种是假定这一属性服从某一分布。

对未知样本分类的时候，对每个类，计算。样本被指派到类当且仅当时，被指派到其最大的类。 

二、 实验过程

1、实验流程

本次实验采用RSS数据源采集网站数据，用到了下面两个数据源爬数据：

ny = feedparser.parse('http://newyork.craigslist.org/stp/index.rss')
sf = feedparser.parse('http://sfbay.craigslist.org/stp/index.rss')

得到每个网站的文章之后建立列表doclist，并且建立每篇文章相对应的类标签classlist，再生成一个所有单词出现的列表vocablist。接下来统计每个单词出现的次数，次数出现较多的单词一般是类似于and、the、for之类的并不能给分类带来帮助的无用单词，我们把这些高频词去掉。我们在doclist中随机取20个作为测试集，剩余的作为训练集，先计算某个类占的先验概率pAbusive，再计算每个类每个单词占总的这个单词出现的概率p0Vect,p1Vect，测试的时候把待测试的样本向量分别乘以p0Vect,p1Vect再每个元素加起来分别加先验概率取log。算出来哪个概率大就属于哪个类。

2、改进算法

我主要做了互信息特征选择，也就是用互信息选择所有出现单词中的一些做特征。互信息衡量的是某个特征词和类别之间的统计独立关系。某个特征词t 和某个类别ci 传统的互信息定义度量两个对象之间的相互性，在不良信息过滤问题中用于度量特征对于主题的区分度。 则特征词 t 和类别 ci 的互信息公式定义为:

其中: P( t， ci) 表示训练集中既包含特征 t 又属于类别 ci 的文档概率，P( t) 表示在整个文本训练集中包含特征 t 的文档概率，P( ci) 表示在训练集中属于类别 ci 的文档概率，P( t | ci)表示在类别 ci 中包含特征 t 的文档概率。在某个类别 ci 中出现的概率高， 而在其他类别中出现的概率低的特征 t 将获得较高的互信息， 也就有可能被选择为类别 ci 的特征。 在 m 个类别的文本训练集上特征项 t 的互信息定义为：

互信息根据特征与类别共同出现的概率， 度量特征和类别的相关性。 对于某一类别 ci 来讲，特征词 t 的互信息越大，说明该词与该类的共现概率越大。 下面利用一个简单的例子对传统互信息算法进行分析， 设存在两类文本 c1 ，c2 ， 每类中包含 5 篇文档，特征词集合中有 t1 ，t2 ，t3 三个词，并且在类别 c1 ，c2 的分布情况如表 1 所示。

利用式( 2) 计算可得：

我用这样的计算方法到的每个单词的互信息，具体python实现如下：

def chooseN(trainMatrix,trainCategory):
    numTrainDocs = len(trainMatrix)
    numWords = len(trainMatrix[0])
    pAbusive = sum(trainCategory)/float(numTrainDocs)
    MI=zeros(numWords)
    pCondition1=ones(numWords)
    pCondition0=ones(numWords)
    deleteN=[]
    for i in range(numWords):
        for j in range(numTrainDocs):
            if trainCategory[j]==1:
                pCondition1[i]=pCondition1[i]+trainMatrix[j][i]
            else:
                pCondition0[i]=pCondition0[i]+trainMatrix[j][i]
        MI[i]=pAbusive*log(pCondition1[i]/(pCondition1[i]+pCondition0[i]))+\
              (1-pAbusive)*log(pCondition0[i]/(pCondition1[i]+pCondition0[i]))
        if MI[i]>-0.8:
            deleteN.append(i)
    return deleteN

下图是在一次计算中得到的MI：

另外去高频词的时候发现去掉10个高频词的时候效果比较好。下面是实验数据：

方法（错误率）	1	2	3	4	5	6	7	8	9	10	平均错误率
互信息去10	0	0.15	0	0.05	0	0.05	0.1	0.1	0.1	0.05	0.06
互信息	0.1	0.15	0	0.1	0	0.15	0.05	0	0.05	0.15	0.075
去10	0.25	0.35	0.35	0.4	0.4	0.35	0.3	0.35	0.25	0.35	0.335
去30	0.35	0.4	0.45	0.4	0.5	0.3	0.35	0.45	0.3	0.45	0.395

三、 实验小结

这次实验相对前两次比较难，首先要理解原来朴素贝叶斯的每个步骤的代码，对于改进还要看文献，改进的互信息又很难具体下手写代码，最后找见一篇中文的“文本分类中互信息特征选择方法的研究与算法改进”的论文按照论文当中的方法才用代码实现，不过很奇怪的是计算到互信息之后用互信息小的做特征词反而得到了很好的效果，这和传统的方法是相反的，而且对于实验的两个RSS源数据每天测试的结果不太一样，有可能是网站新闻有变动之类的