分类算法综述

分类算法综述1分类算法分类是数据挖掘中的一个重要课题。分类的目的是学会一个分类函数或分类模型（也常常称作分类器），该模型能把数据库中的数据项映射到给定类别中的某一个。分类可用于提取描述重要数据类的模型或预测未来的数据趋势。分类可描述如下：输入数据，或称训练集（TrainingSet），是一条条的数据库记录（Record）组成的。每一条记录包含若干个属性（Attribute），组成一个特征向量。训练集的每条记录还有一个特定的类标签（ClassLabel）与之对应。该类标签是系统的输入，通常是以往的一些经验数据。一个具体样本的形式可为样本向量：（v1,v2,…,vn;c）。在这里vi表示字段值，c表示类别。分类的目的是：分析输入数据，通过在训练集中的数据表现出来的特性,为每一个类找到一种准确的描述或者模型。这种描述常常用谓词表示。由此生成的类描述用来对未来的测试数据进行分类。尽管这些未来的测试数据的类标签是未知的，我们仍可以由此预测这些新数据所属的类。注意是预测，而不能肯定，因为分类的准确率不能达到百分之百。我们也可以由此对数据中的每一个类有更好的理解。也就是说：我们获得了对这个类的知识。2典型分类算法介绍解决分类问题的方法很多，下面介绍一些经典的分类方法，分析各自的优缺点。2.1决策树分类算法决策树（DecisionTree）是一种有向无环图（DirectedAcyclicGraphics,DAG）。决策树方法是利用信息论中的信息增益寻找数据库中具有最大信息量的属性字段，建立决策树的一个结点，在根据该属性字段的不同取值建立树的分支，在每个子分支子集中重复建立树的下层结点和分支的一个过程。构造决策树的具体过程为：首先寻找初始分裂，整个训练集作为产生决策树的集合，训练集每个记录必须是已经分好类的，以决定哪个属性域（Field）作为目前最好的分类指标。一般的做法是穷尽所有的属性域，对每个属性域分裂的好坏做出量化，计算出最好的一个分裂。量化的标准是计算每个分裂的多样性（Diversity）指标。其次，重复第一步，直至每个叶节点内的记录都属于同一类且增长到一棵完整的树。主要的决策树算法有ＩＤ３、C4.5(C5.0)、CART、PUBLIC、SLIQ和SPRINT算法等。它们在选择测试属性采用的技术、生成的决策树的结构、剪枝的方法以及时刻，能否处理大数据集等方面都有各自的不同之处。2.1.1ＩＤ３（C4.5）算法在当前决策树学习的各种算法中，影响最大的是JR.Quinlan于1986年提出的ID3算法，他提出用信息增益作为属性的选择标准，以使得在对每一个非叶结点进行测试时，能获得关于被测试记录最大的类别信息。ID3总是选则具有最高信息增益的属性作为当前结点的测试属性。具体方法是：检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一类别的数据为止，最后得到一棵决策树，它可以用来对新的样本进行分类。ＩＤ３算法通过不断的循环处理，初步求精决策树，直到找到一个完全正确的决策树。在选择重要特征时利用了信息增益的概念。该算法优点在于：（1）算法的基础理论清晰，方法简单，计算速度快；（2）搜索空间是完全的假设空间，目标函数就在搜索空间中，不存在无解的危险；（3）全盘使用训练数据，可得到一棵较为优化的决策树。在实际应用中，对于非增量式的学习任务，ＩＤ３算法通常是建立决策树的很好选择，但该算法不足之处在于：（1）不能增量地接受训练例，这就使得每增加一次实例都必须废除原有的决策树，重新计算信息增益并构造新的决策树，这造成极大的开销；（2）智能处理离散属性，在分类前需要对其进行离散化的处理；（3）在建树时，每个结点仅含一个特征，这是一种变元的算法，特征间的相关性强调不够；（4）对噪声较为敏感，数据质量差将直接导致生成的决策树过于庞大或决策树中很多分支的信息量很少。（5）在建树的过程中每当选择一个新属性时，算法只考虑了该属性带来的信息增益，未考虑到选择该属性后为后续属性带来的信息增益，即未考虑树的两层节点；（6）其信息增益存在一个内在偏置，它偏袒属性值数目较多的属性。2.1.2SLIQ分类算法针对C4.5改进算法而产生的样本集反复扫描和排序低效问题，SLIQ分类算法运用了预排序和广度优先两项技术。预排序技术消除了结点数据集排序，广度优先策略为决策树中每个叶子结点找到了最优分裂标准。SLIQ分类算法由于采用了上述两项技术使其能处理比C4.5大得多的样本集。但由于所需内存较多，这在一定程度上限制了可以处理的数据集的大小；预排序技术也使算法性能不能随记录数目进行线性扩展。2.1.3SPRINT分类算法为了减少驻留于内存的数据量，SPRINT算法进一步改进了决策树算法的数据结构，去掉在SLIQ中需要驻留于内存的类别列表，将类别合并到每个属性列表中。这样，在遍历每个属性列表中寻找当前结点的最优分裂标准时，不必参照其他信息，使寻找每个结点的最优分裂标准变得相对简单，但缺点是对非分裂属性列表进行分裂却变得非常困难。因此，该算法的扩展性能较差。此外，基于决策树的主要改进算法还包括EC4.5、CART(classificationandregressiontree)、PUBLIC(pruningandbuildingintegreatedinclassification)等。2.2三种典型贝叶斯分类器贝叶斯分类是统计学分类算法，它是一类利用概率统计知识进行分类的算法。它在先验概率与条件概率已知的情况下，预测类成员关系可能性的模式分类算法。如计算一个给定样本属于一个特性类的概率，并选定其中概率最大的一个类别作为该样本的最终判别。假设每个训练样本用一个n维特征向量X={x1,x2,…,xn}表示，分别描述n个属性A1，A2,…,An对样本的测量。将训练样本集分为m类，记为C1，C2,…,Cm。贝叶斯原理通常用下面的公式来表示：P(X|Ci)P(Ci)P(Ci|X)m其中，X表示观测数据样本，Cj为某种假设，P(Ci)是Ci的先验概率，（i,j=1,2,..,m）P(X|Ci)是条件概率，先验概率对条件概率加权平均后，得到条件X下，Ci的后验概率P(Ci|X)。上述是朴素贝叶斯的工作过程，也是贝叶斯分类算法的判别准则。在许多场合，朴素贝叶斯（NaïveBayes,NB）分类可以与决策树和神经网络分类算法相媲美，该算法能运用到大型数据库中，且方法简单、分类准确率高、速度快。由于贝叶斯定理假设一个属性值对给定类的影响独立于其它的属性值，而此假设在实际情况中经常是不成立的，因此其分类准确率可能会下降。为此，就出现了许多降低独立性假设的贝叶斯分类算法，如TAN(treeaugmentedBayesnetwork)算法、贝叶斯网络分类器（Bayesiannetworkclassifier，BNC）。2.2.1朴素贝叶斯算法朴素贝叶斯分类器以简单的结构和良好的性能受到人们的关注，它是最优秀的分类器之一。朴素贝叶斯分类器建立在一个类条件独立性假设(朴素假设)基础之上：给定类结点(变量)后，各属性结点(变量)之间相互独立。朴素贝叶斯分类器可以看作是贝叶斯网络的一种最简化的模型。根据朴素贝叶斯的类条件独立假设，则有：条件概率P(X1|Ci),P(X2|Ci),…,P(Xn|Ci)可以从训练数据集求得。根据此方法，对一个未知类别的样本X，可以先分别计算出X属于每一个类别Ci的概率P(X|Ci)P(Ci),然后选择其中概率最大的类别作为其类别。朴素贝叶斯算法成立的前提是各属性之间相互独立。当数据集满足这种独立性假设时，分类的准确度较高，否则可能较低。另外，该算法没有分类规则输出。2.2.2TAN算法TAN算法通过发现属性对之间的依赖关系来降低NB中任意属性之间独立的额假。它是在NB网络结构的基础上增加属性对之间的关联（边）来实现的。实现方法是：用结点表示属性，用有向边表示属性之间的依赖关系，把类别属性作为根结点，其余所有属性都作为它的子节点。通常，用虚线代表NB所需的边，用实线代表新增的边。属性Ai和Aj之间的边意味着属性Ai对类别变量C的影响还取决于属性Aj的值。这些增加的边满足下列条件：类别变量没有双亲结点，每个属性有一个列别变量双亲结点和最多另外一个属性作为其双亲结点。找到这组关联边之后，就可以计算一组随机变量的联合概率分布如下：其中代表的是Ai的双亲结点。由于在TAN算法中考虑了Ain个属性之间独立性的假设有了一定程度的降低，但是属性之间可能存在更多其它的关联性仍没有考虑，因此其使用范围仍然受到限制。2.2.3贝叶斯网络分类器贝叶斯网络分类器放弃了朴素贝叶斯分类器的条件独立性假设，所以最能与领域数据相吻合。在贝叶斯网络的结构中类结点地位同其他属性结点一样，也可以有父节点。本文采用基于搜索打分的方法构造贝叶斯分类器，搜索打分算法采用K2搜索算法和BIC评分函数。贝叶斯网络分类方法如下：1）输入：训练集D；变量顺序；变量父结点个数上界u；2）K2算法构造BNC:a、所有结点组成无向图b、确定变量jX的父结点个数，等于u则停止为它寻找父结点；c、如果父节点的个数大于u，则从中按顺序选择jX之前的节点，但不是jX父结点的变量iX做为jX的父结点；d、使用BIC测度对新结构打分；e、同前次打分比较，如果评分高，则添加iX为jX的父节点；如果BIC评分低，则停止为jX寻找父结点；3）使用训练数据集进行参数学习（最大似然估计法）；4）对测试集分类，得出分类准确度。下面主要从分类准确度和分类耗时这两个方面分析比较这三种分类器。（1）朴素贝叶斯分类器。从分类准确度上看，NBC虽然结构简单但是它的分类准确度并不低。从分类耗时看，NBC普遍比其它两种分类器花费的时间少，这与它不需要结构学习，计算复杂度低是密切相关的。NBC在现实中有着广泛的适应性，这主要还因为在大部分领域中属性之间的依赖关系要明显低于属性和类别之间的依赖关系，所以NBC的条件独立性假设是具有一定的现实意义的。（2）基于BIC测度的TAN分类器是所有NBC改进分类器中效果最好的一个。TAN分类器的分类准确度普遍高于NBC，TAN分类器放松了条件独立性假设这是同现实世界相符合的，当属性之间关联性越大时，TAN分类器的效果就越好。TAN分类器中需要设置根节点，根节点就是选择除去类节点以外的属性节点作为其它属性节点的根节点，根节点的设置对分类准确度并没有很大的影响。从分类时间上看，TAN分类器在这三种分类器中是花费时间最长的。（3）理论上BNC分类器应该有最好的分类效果，但是实际中，BNC的分类效果并不理想，这主要与两个因素有关：（1）数据集的规模。BNC对大样本的数据集有较好的分类效果，在小规模数据集情况下就不如NBC和TAN；（2）在使用K2算法进行结构学习的过程中有一个重要的参数，用来确定结点变量的次序，它对先验知识的依赖性很大。在不了解相关的领域或没有专家的指导的情况下，确定变量的次序就变得相当困难。从分类耗时上看，BNC分类器的分类耗时比NBC要长，同TAN比较有一定的不确定性，它普遍要比TAN分类时间短。这三种分类器并不是对每种数据集都有好的分类效果，因此在对数据集选择分类器的时候还需要具体情况具体对待，主要考查属性之间的关联性、数据的规模和时间限制等方面。数据集属性相关性小的时候选择NBC有较好的分类效果，数据集属性相关性大时候选择TAN分类器。在数据集规模较大且具有一定先验知识时选择贝叶斯网络分类器。2.3k-近邻k-近邻(kNN，k-NearestNeighbors)算法是一种基于实例的分类方法，是一种非参数的分类技术。基本原理：KNN分类算法搜索样本空间，计算未知类别向量与样本集中每个向量的相似度，在样本集中找出K个最相似的文本向量，分类结果为相似样本中最多的一类。但在大样本集和高维样本分类中（如文本分类），KNN方法的缺陷凸显。表现在以下几个方面：（1）KNN分类算法是懒散的分类算法，对于分类所需的计算均推迟至分类进行，故