分类问题综述

在分类(classification)问题中,常常需要把一个事物分到某个类别。一个事物具有很多属性,把它的众多属性看做一个向量,即X=(x1,x2,x3,…,xn),用x这个向量来代表这个事物。类别也是有很多种,用集合 Y={y1,y2,…ym} 表示。如果x属于y1类别,就可以给x打上y1标签,意思是说x属于y1类别。这就是所谓的分类(Classification)。

生活中很多场合需要用到分类,比如新闻分类、病人分类等等。

从数学角度来说,分类问题可做如下定义:
已知集合:,确定映射规则,使得任意有且仅有一个使得成立(不考虑模糊数学里的模糊集情况)。

其中 C 叫做类别集合,其中每一个元素是一个类别,而 I 叫做项集合,其中每一个元素是一个待分类项,f 叫做分类器,分类算法的任务就是构造分类器f。

需要强调的是,分类问题往往采用经验性方法构造映射规则,即一般情况下的分类问题缺少足够的信息来构造100%正确的映射规则,而是通过对经验数据的学习从而实现一定概率意义上正确的分类,因此所训练出的分类器并不是一定能将每个待分类项准确映射到其分类,分类器的质量与分类器构造方法、待分类数据的特性以及训练样本数量等诸多因素有关。

例如,医生对病人进行诊断就是一个典型的分类过程,任何一个医生都无法直接看到病人的病情,只能观察病人表现出的症状和各种化验检测数据来推断病情,这时医生就好比一个分类器,而这个医生诊断的准确率,与他当初受到的教育程度(构造方法)、病人的症状是否突出(待分类数据的特性)以及医生的经验多少(训练样本数量)都有密切关系。

本文介绍朴素贝叶斯分类器(Naive Bayes classifier),它是一种简单有效的常用分类算法。

贝叶斯定理

贝叶斯分类算法基于托马斯贝叶斯发明的贝叶斯定理,他提出的贝叶斯定理对于现代概率论和数理统计的发展有着重要的影响。

贝叶斯定理是关于随机事件A和B的条件概率(或边缘概率)的一则定理(公式如下),其中P(A|B)是在B发生的情况下A发生的可能性:

在贝叶斯定理中,需要了解先验概率,后验概率等概念:

P(A)是A的先验概率或边缘概率。之所以称为”先验”是因为它不考虑任何B方面的因素
P(A|B)是已知B发生后A的条件概率,也由于得自B的取值而被称作A的后验概率
P(B|A)是已知A发生后B的条件概率,也由于得自A的取值而被称作B的后验概率
P(B)是B的先验概率或边缘概率,也作标准化常量(normalizing constant)

朴素贝叶斯分类

朴素贝叶斯分类是贝叶斯分类器的一种,贝叶斯分类算法是统计学的一种分类方法,利用概率统计知识进行分类,其分类原理就是利用贝叶斯公式根据某对象的先验概率计算出其后验概率(即该对象属于某一类的概率),然后选择具有最大后验概率的类作为该对象所属的类。在许多场合,朴素贝叶斯可以与决策树,SVM相媲美。总的来说:当样本特征个数较多或者特征之间相关性较大时,朴素贝叶斯分类效率比不上决策树模型;当各特征相关性较小时,朴素贝叶斯分类性能最为良好。另外朴素贝叶斯的计算过程类条件概率等计算彼此是独立的,因此特别适于分布式计算。但它基于属性之间的独立,在实际情况中经常是不成立的,因此分类准确率可能会下降。

朴素贝叶斯分类器是一种有监督学习,常见有两种模型,多项式模型(multinomial model)和伯努利模型(Bernoulli model)。其实所谓的“多项式”或“伯努利”,只不过是在求先验概率和条件概率时统计方法不一样,基本原理没变。

用概率论来表达朴素贝叶斯分类的过程就是:
1、 是一个待分类的项,ai为x的特征属性(地位相同、相互独立),共m个
2、有类别集合
3、计算
4、如果 ,则
显然,问题的关键在于第三步-求出各分类项的后验概率,用到的就是贝叶斯公式。
根据贝叶斯定理有如下推导:

分母对于所有类别来说都是为常数,因此只需计算分子即可。又因为各个特征具有相同的地位且各自出现的概率相互独立,所以有:

上式中,P(aj|yi)是关键,其含义就是样本各个特征在各个分类下的条件概率,计算各个划分的条件概率是朴素贝叶斯分类的关键性步骤,也就是数据训练阶段的任务所在。至于样本每个特征的概率分布则可能是离散的,也可能是连续的。

特征属性划分的条件概率及Laplace校准

由上文看出,计算各个划分的条件概率P(a|y)是朴素贝叶斯分类的关键性步骤,下面说明特征属性为离散分布或者连续分布的计算处理方法。

  1. 离散分布:当特征属性为离散值时,只要统计训练样本中各个划分在每个类别中出现的频率即可用来估计P(a|y)

    由于贝叶斯分类需要计算多个特征值概率以获得事物项属于某一类的概率,若某一特征值的概率为0则会使整个概率乘积变为0(称为数据稀疏),这破坏了各特征值地位相同的假设条件,使分类准确率大大降低。因此为了降低破坏率,离散分布必须进行校准,常见的如Laplace校准:每个类别下所有特征划分的计数都加1,由于训练样本集数量足够大,因此并不会对结果产生影响,但却解决了上述概率为0的尴尬局面;另外从运算效率上,加法也比乘法提高了一个量级。

    数据稀疏是机器学习中很大的问题,比拉普拉斯平滑更好的解决数据稀疏的方法是:通过聚类将未出现的词找出系统相关词,根据相关词的概率求一个平均值。如果:系统有“苹果”,“葡萄”等词,但是没有“榴莲”,我们可以根据“苹果”,“葡萄”等平均值作为“榴莲”的概率,这样更合理。

  2. 连续分布:当特征属性为连续值时,通常假定其值服从高斯分布(正态分布)。即:
    ,而
    对于连续分布的样本特征的训练就是计算其均值和方差。

算法的改进

实际项目中,概率值P往往是很小的小数,连续的微小小数相乘容易造成下溢出使乘积为0或者得不到正确答案。一种解决办法就是对乘积取自然对数,将连乘变为连加,ln(AB)=lnA+lnB。采用自然对数处理不会带来任何损失,可以避免下溢出或者浮点数舍入导致的错误。下图给出了f(x)和ln(f(x))函数的曲线,对比可以发现:相同区域内两者同增或者同减、在相同点取得极值,因此采用自然对数不会影响最终比较结果。

应用

拼写检查

经常在网上搜索东西的朋友知道,当你不小心输入一个不存在的单词时,搜索引擎会提示你是不是要输入某一个正确的单词,比如当你在Google中输入“Julw”时,系统会猜测你的意图:是不是要搜索“July”,如下图所示:

这叫做拼写检查。根据谷歌一员工写的文章显示,Google的拼写检查基于贝叶斯方法。下面我们就来看看,怎么利用贝叶斯方法,实现”拼写检查”的功能。
用户输入一个单词时,可能拼写正确,也可能拼写错误。如果把拼写正确的情况记做c(代表correct),拼写错误的情况记做w(代表wrong),那么“拼写检查”要做的事情就是:在发生w的情况下,试图推断出c。换言之:已知w,然后在若干个备选方案中,找出可能性最大的那个c,也就是求 的最大值。
而根据贝叶斯定理,有:

由于对于所有备选的c来说,对应的都是同一个w,所以它们的P(w)是相同的,因此我们只要最大化 即可。其中:

  • P(c)表示某个正确的词的出现“概率”,它可以用“频率”代替。如果我们有一个足够大的文本库,那么这个文本库中每个单词的出现频率,就相当于它的发生概率。某个词的出现频率越高,P(c)就越大。比如在你输入一个错误的词“Julw”时,系统更倾向于去猜测你可能想输入的词是“July”,而不是“Jult”,因为“July”更常见。
  • P(w|c)表示在试图拼写c的情况下,出现拼写错误w的概率。为了简化问题,假定两个单词在字形上越接近,就有越可能拼错,P(w|c)就越大。举例来说,相差一个字母的拼法,就比相差两个字母的拼法,发生概率更高。你想拼写单词July,那么错误拼成Julw(相差一个字母)的可能性,就比拼成Jullw高(相差两个字母)。值得一提的是,一般把这种问题称为“编辑距离”,参见博客中的这篇文章。

所以,我们比较所有拼写相近的词在文本库中的出现频率,再从中挑出出现频率最高的一个,即是用户最想输入的那个词。具体的计算过程及此方法的缺陷请参见这里

基于朴素贝叶斯的文本分类算法

所谓文本分类,是指对所给出的文本,给出预定义的一个或多个类别标号,对文本进行准确、高效的分类。它是许多数据管理任务的重要组成部分。新闻类别(财经、体育、教育等)划分、垃圾邮件检测等都属于文本分类。

常用的文本分类方法有支持向量机、K-近邻算法和朴素贝叶斯。其中朴素贝叶斯具有容易实现,运行速度快的特点,被广泛使用。本文前面已详细介绍了朴素贝叶斯的基本原理,接下来将讨论了分类的一下概念以及两种常见模型:多项式模型(MM)和伯努利模型(BM),后续会会进行代码的实现,并选取一些数据进行测试。

文本分类的基础是切词,切词是一个很重要的研究方向,英文切词相对自然比较容易–几乎是切成一个个单词即可,中文切词则比较麻烦,预处理阶段需要特殊的处理,去掉停止词,停止词(StopWord)是指那些无意义的字或词,如“的”、“在”等。去掉文档中的停止词也是必须的一项工作。

在文本分类中,假设我们有一个文档d∈X,X是文档向量空间(document space),和一个固定的类集合C={c1,c2,…,cj},类别又称为标签。显然,文档向量空间是一个高维度空间。我们把一堆打了标签的文档集合作为训练样本,∈X×C。例如:

={Beijing joins the World Trade Organization, China}

对于这个只有一句话的文档,我们把它归类到 China,即打上china标签。我们期望用某种训练算法,训练出一个函数γ,能够将文档映射到某一个类别:γ:X→C

这种类型的学习方法叫做有监督学习,因为事先有一个监督者(我们事先给出了一堆打好标签的文档)像个老师一样监督着整个学习过程。

朴素贝叶斯分类器是一种有监督学习,常见有两种模型,多项式模型(multinomial model)和伯努利模型(Bernoulli model)。

多项式模型

多项式模型概率计算是以“词”为基础单位,根据分类中某词出现的次数计算概率。设某文本d=(t1,t2,…,tk),tk是该文档中出现过的单词,允许重复,则在多项式模型中类先验概率和各个单词类条件概率的计算方法为:

先验概率P(c)= 类c下单词总数/整个训练样本的单词总数

类条件概率P(tk|c) = (类c下单词tk在各个文档中出现过的次数之和+1)/(类c下单词总数+|V|)

V是训练样本的单词表(即抽取单词,单词出现多次,只算一个),|V|则表示训练样本包含多少种单词。

P(tk|c)可以看作是单词tk在证明d属于类c上提供了多大的证据,而P(c)则可以认为是类别c在整体上占多大比例(有多大可能性)。

多项式模型中各单词类条件概率计算考虑了词出现的次数,相当于考虑了词的权重,这更符合自然语言的特点。另外,根据斯坦福的《Introduction to Information Retrieval》课件上所说,多项式模型计算准确率更高。待分类项类别判断时仅根据其中出现的单词进行后验概率计算,即:P(t1|c)P(t2|c),…,P(tk|c)*p(c)

多项式朴素贝叶斯算法伪代码如下:

伯努利模型

贝努利模型不考虑词在文档中出现的次数,只考虑出不出现,因此在这个意义上相当于假设词是等权重的。

先看贝努利模型的定义–对随机实验中某事件是否发生,试验的可能结果只有两个,这种只有两个可能结果的实验称为贝努利试验。贝努利模型中甭管哪一类,每个单词只有出现或者不出现两种,因此可以这么理解二分类的贝叶斯伯努利模型–文本中某些词的出现与否决定了该文本的分类,这实际上包含了两部分:一些词出现了,另外一些词没有出现。因此伯努利模型中各个单词类条件概率的计算是:在文本中出现的单词作为“正方”参与计算,没有在文本中出现但在该类全局单词表中出现的单词作为“反方”参与计算。

伯努利模型概率计算的是以“文本”为基础单位,设某文本d=(t1,t2,…,tk),tk是该文档中出现过的单词,不允许重复,伯努利模型类先验概率和各个单词类条件概率的计算方法为:

P(c) = 类c下文件总数/整个训练样本的文件总数

P(tk|c) = (类c下包含某单词tk的文件数+1)/(类c下文件总数+2)

其中计算P(tk|c)时,分子+1是引入Laplace校准,分母加2是因为词只有出现与否两种情况,估计也是为了数据校准(TBD)。对待分类项进行类别判断计算后验概率时,“正方”的概率就是P(tk|c),“反方”的概率是(1-P(word|c))(word是虽然不在d中,但出现在该类全局单词表上的词。因为Laplace校准的存在,实际上相当于全部的单词都参与计算),即:

P(t1|c)P(t2|c),…,P(tk|c)(1-P(word0|c),…, (1-P(wordm|c)p(c)

伯努利朴素贝叶斯算法伪代码如下:


下一篇文章将用Java语言实现基于朴素贝叶斯的文本分类算法,包括多项式和伯努利两种模型的实现。

本文参考链接:
http://www.cnblogs.com/leoo2sk/archive/2010/09/17/naive-bayesian-classifier.html
http://blog.csdn.net/suipingsp/article/details/41897901
http://yuanmuqiuyu2000.blog.sohu.com/198789412.html