朴素贝叶斯分类器

分类器陈世超什么是分类器？分类是数据挖掘的一种非常重要的方法。分类的概念是在已有数据的基础上学会一个分类函数或构造出一个分类模型（即我们通常所说的分类器(Classifier)）。该函数或模型能够把数据库中的数据纪录映射到给定类别中的某一个，从而可以应用于数据预测。总之，分类器是数据挖掘中对样本进行分类的方法的统称.分类器的构造和实施分类器的构造和实施大体会经过以下几个步骤：选定样本（包含正样本和负样本），将所有样本分成训练样本和测试样本两部分。在训练样本上执行分类器算法，生成分类模型。在测试样本上执行分类模型，生成预测结果。根据预测结果，计算必要的评估指标，评估分类模型的性能。影响分类器准确度的因素(1)、训练集的记录数量。生成器要利用训练集进行学习，因而训练集越大，分类器也就越可靠。然而，训练集越大，生成器构造分类器的时间也就越长。错误率改善情况随训练集规模的增大而降低。(2)、属性的数目。更多的属性数目对于生成器而言意味着要计算更多的组合，使得生成器难度增大，需要的时间也更长。有时随机的关系会将生成器引入歧途，结果可能构造出不够准确的分类器（这在技术上被称为过分拟合）。因此，如果我们通过常识可以确认某个属性与目标无关，则将它从训练集中移走。(3)、属性中的信息。有时生成器不能从属性中获取足够的信息来正确、低错误率地预测标签（如试图根据某人眼睛的颜色来决定他的收入）。加入其他的属性（如职业、每周工作小时数和年龄），可以降低错误率。(4)、待预测记录的分布。如果待预测记录来自不同于训练集中记录的分布，那么错误率有可能很高。比如如果你从包含家用轿车数据的训练集中构造出分类器，那么试图用它来对包含许多运动用车辆的记录进行分类可能没多大用途，因为数据属性值的分布可能是有很大差别的。对分类器的错误率进行评估的方法(1)保留方法(Holdout)：记录集中的一部分（通常是2/3）作为训练集，保留剩余的部分用作测试集。生成器使用2/3的数据来构造分类器，然后使用这个分类器来对测试集进行分类，得出的错误率就是评估错误率。(2)交叉纠错方法(Crossvalidation)：数据集被分成k个没有交叉数据的子集，所有子集的大小大致相同。生成器训练和测试共k次；每一次，生成器使用去除一个子集的剩余数据作为训练集，然后在被去除的子集上进行测试。把所有得到的错误率的平均值作为评估错误率。交叉纠错法可以被重复多次(t)，对于一个t次k分的交叉纠错法，k*t个分类器被构造并被评估，这意味着交叉纠错法的时间是分类器构造时间的k*t倍。增加重复的次数意味着运行时间的增长和错误率评估的改善。我们可以对k的值进行调整，将它减少到3或5，这样可以缩短运行时间。然而，减小训练集有可能使评估产生更大的偏差。贝叶斯分类算法定义：假设X是类的标号未知的数据样本。设H为某种假定，如数据样本X属于某特定的类C。对于分类问题，我们希望确定P(H|X),即给定观测数据样本X，假定H成立的概率。贝叶斯定理给出了如下的计算P(H|X)的简单有效的方法：P(H|X)=（P(X|H)*P(H)）/P(X)P(H)是先验概率，P(X|H)代表假设H成立的情况下，观察到X的概率。P(H|X)是后验概率。例如，假定数据样本域由水果组成，用它们的颜色和形状来描述。假定X表示红色和圆的，H表示假定X是苹果，则P（H|X）反应当我们看到X是红色并是圆的的时候，我们对X是苹果的确信程度。贝叶斯分类对两种数据具有较好的分类效果：一种是完全独立的数据，另一种是函数依赖的数据简单的说，贝叶斯定理是基于假设的先验概率、给定假设下观察到不同数据的概率，提供了一种计算后验概率的方法。在人工智能领域，贝叶斯方法是一种非常具有代表性的不确定性知识表示和推理方法。朴素贝叶斯分类算法朴素贝叶斯是贝叶斯证据独立的表达形式，属于一种特例。实际应用过程中贝叶斯表达式非常复杂，但是我们希望把它拆分成多个朴素贝叶斯来表达，这样能够快速获得后验概率。朴素贝叶斯的基本思想：对于给定的待分类项x{a1，a2.......an}，求解在此项中出现的条件下各类别ci出现的概率。哪个P(ci|x)最大，就把此待分类项归属于哪个类别。朴素贝叶斯分类算法过程1。每个数据样本用一个n维特征向量X={x1,x2,....xn}表示，分别描述对n个属性A1，A2，.....,An样本的n个度量。2。假定有m个类C1,C2,....Cm,给定一个位置的数据样本X，分类器将预测X属于具有最高后验概率的类。也就是说，朴素贝叶斯分类将未知的样本分配给类Ci(1=i=m)当且仅当P（Ci|X）P(Cj|X),对任意的j=1,2，。。。m，j不等于i。这样，最大化P(Ci|X)。其P(Ci|X)最大的类Ci称为最大后验假定。根据贝叶斯定理:3。由于P(X)对于所有类为常数，只需要P（X|Ci）*P(Ci)最大即可。如果Ci类的先验概率未知，则通常假定这些类是等概率的，即P（C1)=P（C2)=P（C3)=....=P（Cm)，因此就转换为对P（X|Ci)的最大化（P(X|Ci)常被称为给定Ci时数据X的似然度，而使P（X|Ci）最大的假设Ci称为最大似然度）。否则，需要最大化P(X|Ci)*P(Ci)。注意，类的先验概率可以用P（Ci）=si/s计算，其中si是Ci中的训练样本数，s是训练样本总数。4。给定具有许多属性的数据集，计算P（X|Ci）的开销可能非常大。为降低P（X|Ci）的开销，可以做类条件独立的朴素假定。给定样本的类标号，假定属性值相互条件独立，即在属性间，不存在依赖关系。这样只需考虑分子:其中概率P(x1|Ci),P(x2|Ci),....P(xn|Ci)可以由训练样本估值。如果Ak是离散属性，则P（xk|Ci）=sik|si,其中sik是在属性Ak上具有xk的类Ci的训练样本数，而si是Ci中的训练样本数。如果Ak是连续值属性，则通常假定该属性服从高斯分布。因而5。对未知样本X分类，也就是对每个类Ci，计算P(X|Ci)*P(Ci)。样本X被指到类Ci，当且仅当P（Ci|X）P（Cj|X），1=j=m,j不等于i，换言之，X被指派到其P（X|Ci）*P(Ci)最大的类。贝叶斯算法的处理流程：第一阶段：准备阶段该阶段为朴素贝叶斯分类做必要的准备。主要是依据具体情况确定特征属性，并且对特征属性进行适当划分。然后就说对一部分待分类项进行人工划分，以确定训练样本。这一阶段的输入是所有待分类项，输出是特征属性和训练样本。分类器的质量很大程度上依赖于特征属性及其划分以及训练样本的质量。第二阶段：分类器训练阶段主要工作是计算每个类别在训练样本中出现频率以及每个特征属性划分对每个类别的条件概率估计。输入是特征属性和训练样本，输出是分类器。第三阶段：应用阶段这个阶段的任务就是使用分类器对待分类项进行分类，其输入是分类器和待分类项，输出是待分类项与类别的映射关系。朴素贝叶斯分类举例数据样本用属性age，income，student和credit——rating描述。类标号属性buy_computer具有两个不同值。设C1对应于类buy_computer=”yes”,而C2对应类buy_computer=”no”。设我们希望分类的未知样本为：X=（age=”=30”,income=”medium”,student=”yes”,credit_rating=”fair”）。步骤1。我们需要最大化P(X|Ci)*P(Ci),i=1,2。每个类的先验概率P(Ci)可以根据训练样本计算：P(buy_computer=”yes”)=9/14=0.643,P(buy_computer=”no”)=5/14=0.357。2。为计算P(X|Ci),i=1,2,我们计算下面的条件概率：P(age=30|buy_computer=”yes”)=2/9=0.222,P(age=30|buy_computer=”no”)=3/5=0.600,P(income=”medium”|buy_computer=”yes”)=4/9=0.444,P(income=”medium”|buy_computer=”no”)=2/5=0.400,P(student=”yes”|buy_computer=”yes”)=6/9=0.677,P(credit_rating=”fair”|buy_computer=”yes”)=6/9=0.667P(student=”yes”|buy_computer=”no”)=1/5=0.200。P(credit_rating=”fair”|buy_computer=”no”)=2/5=0.4003。假设条件独立性，使用以上概率，我们得到：P(X|buy_computer=”yes”)=0.222*0.444*0.667*0.667=0.044,P(X|buy_computer=”no”)=0.600*0.400*0.200*0.400=0.019P(X|buy_computer=”yes”)*P(buy_computer=”yes”)=0.044*0.643=0.028P(X|buy_computer=”no”)*P(buy_computer=”no”)=0.019*0.357=0.007因此，对于样本X，朴素贝叶斯分类预测buy_computer=”yes”朴素贝叶斯的特点朴素贝叶斯核心：假设所有特征都彼此独立。虽然所有特征彼此独立这个假设，在现实中不太可能成立，但是它可以大大简化计算，而且有研究表明对分类结果的准确性影响不大。朴素贝叶斯算法的优点：1.算法逻辑简单，易于实现2.分类过程中时空开销小3.算法稳定，对于不同的数据特定其分类性能差别不大，健壮性比较好。一个问题如果特征属性之间是有关联的，而不是相互独立的怎么办？朴素贝叶斯算法是在假定各个特征属性相互独立的情况下提出来的，这在现实生活中是很难实现的，所以针对这个问题人们做了大量工作解决这个缺点。（1）如果特征属性之间是有联系的，并且是一个有向无环图，可以采用贝叶斯网络。（2）除了贝叶斯网络，还有半朴素贝叶斯算法。（3）还有一种具有树结构的TAN分类器，它放松了朴素贝叶斯中的独立性假设条件，允许每个属性结点最多可以依赖一个非类结点。算是一种受限制的贝叶斯网络算法。谢谢收看