分类技术综述.docx

资源描述

分类技术综述.docx

《分类技术综述.docx》由会员分享，可在线阅读，更多相关《分类技术综述.docx（17页珍藏版）》请在冰点文库上搜索。

分类技术综述.docx

分类技术综述

分类算法综述

（一）

摘要：

分类是数据挖掘、机器学习和模式识别中一个重要的研究领域。

通过对当前数据挖掘中具有代表性的优秀分类算法进行分析和比较，总结出了各种算法的特性，为使用者选择

算法或研究者改进算法提供了依据。

1概述

分类是一种重要的数据挖掘技术。

分类的目的是根据数据集的特点构造一个分类函数或分类模型（也常常称作分类器），该模型能把未知类别的样本映射到给定类别中的某一个。

分类和回归都可以用于预测。

和回归方法不同的是，分类的输出是离散的类别值，而回归的输出是连续或有序值。

本文只讨论分类。

构造模型的过程一般分为训练和测试两个阶段。

在构造模型之前，要求将数据集随机地分为训练数据集和测试数据集。

在训练阶段，使用训练数据集，通过分析由属性描述的数据库元组来构造模型，假定每个元组属于一个预定义的类，由一个称作类标号属性的属性来确定。

训练数据集中的单个元组也称作训练样本，一个具体样本的形式可为：

（u1,u2,un;C;其中ui表示属性值，c表示类

别。

由于提供了每个训练样本的类标号，该阶段也称为有指导的学习，通常，模型用分类规则、判定树或数学公式的形式提供。

在测试阶段，使用测试数据集来评估模型的分类准确率，如果认为模型的准确率可以接受，就可以用该模型对其它数据元组进行分类。

一般来说，测试阶段的代价远远低于训练阶段。

为了提高分类的准确性、有效性和可伸缩性，在进行分类之前，通常要对数据进行预处理，包括：

（1）数据清理。

其目的是消除或减少数据噪声，处理空缺值。

（2）相关性分析。

由于数据集中的许多属性可能与分类任务不相关，若包含这些属性将减慢和可能误导学习过程。

相关性分析的目的就是删除这些不相关或冗余的属性。

（3）数据变换。

数据可以概化到较高层概念。

比如，连续值属性“收入”的数值可以概化为离散值：

低，中，高。

又比如，标称值属性“市”可概化到高层概念“省”。

此外，数据也可以规范化，规范化将给定属性的值按比例缩放，落入较小的区间，比如［0,1］等。

2分类算法的种类及特性

分类模型的构造方法有决策树、统计方法、机器学习方法、神经网络方法等。

按大的方向分类主要有：

决策树，关联规则，贝叶斯，神经网络，规则学习，k—临近法，遗传算法，粗糙集以及模糊逻辑技术。

分类算法综述

（二）决策树算法

2.1决策树（decisiontree分类算法

决策树是以实例为基础的归纳学习算法。

它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则。

它采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较，并根据不同的属性值从该结点向下分支，叶结点是要学习划分的类。

从

根到叶结点的一条路径就对应着一条合取规则，整个决策树就对应着一组析取表达式规则。

1986年

Quinlan提出了著名的ID3算法。

在ID3算法的基础上，1993年Quinlan又提出

了C4.5算法。

为了适应处理大规模数据集的需要，后来又提出了若干改进的算法，其中SLIQ（super

visedlearninginquest并口SPRINT（scalableparallelizableinductionofdecisiontrees）是比较有代表性的两个算法。

（1）ID3算法

ID3算法的核心是：

在决策树各级结点上选择属性时，用信息增益

（informationgain）作为属性的选择标准，以使得在每一个非叶结点进行测试时，能获得关于被测试记录最大的类别信息。

其具体方法是：

检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一类别的数据为止。

最后得到一棵决策树，它可以用来对新的样本进行分类。

某属性的信息增益按下列方法计算。

通过计算每个属性的信息增益，并比较它们的大小，就不难获得具有最大信息增益的属性。

设S是s个数据样本的集合。

假定类标号属性具有m个不同值，定义m个

不同类Ci（i=1,…,m）设si是类Ci中的样本数。

对一个给定的样本分类所需的期望信息由下式给出：

其中pi=si/s是任意样本属于Ci的概率。

注意，对数函数以2为底，其原因是信息用二进制编码。

设属性A具有v个不同值｛a1,a2,……,av｝可以用属性A将S划分为v个子集｛S1,S2,……,Sv｝,其中Sj中的样本在属性A上具有相同的值aj（j=1,2,……）设sij是子集Sj中类Ci的样本数。

由A划分成子集的熵或信息期望由下式给出：

熵值越小，子集划分的纯度越高。

对于给定的子集Sj，其信息期望为

其中pij=sij/sj是Sj中样本属于Ci的概率。

在属性A上分枝将获得的信息增益是

Gain（A）=I（s1,s2,・-£锄）

ID3算法的优点是：

算法的理论清晰，方法简单，学习能力较强。

其缺点是：

只对比较小的数据集有效，且对噪声比较敏感，当训练数据集加大时，决策树可能会随之改变。

（2）C4.5算法

C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：

1）用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；

2）在树构造过程中进行剪枝；

3）能够完成对连续属性的离散化处理；

4）能够对不完整数据进行处理。

C4.5算法与其它分类算法如统计方法、神经网络等比较起来有如下优点：

产生的分类规则易于理解，准确率较高。

其缺点是：

在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。

此外，C4.5只适合于

能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。

（3）SLIQ算法

SLIQ算法对C4.5决策树分类算法的实现方法进行了改进，在决策树的构造过程中采用了“预排序”和“广度优先策略”两种技术。

1）预排序。

对于连续属性在每个内部结点寻找其最优分裂标准时，都需要对

训练集按照该属性的取值进行排序，而排序是很浪费时间的操作。

为此，SLIQ

算法采用了预排序技术。

所谓预排序，就是针对每个属性的取值，把所有的记录按照从小到大的顺序进行排序，以消除在决策树的每个结点对数据集进行的排序。

具体实现时，需要为训练数据集的每个属性创建一个属性列表，为类别属性创建

一个类别列表。

2）广度优先策略。

在C4.5算法中，树的构造是按照深度优先策略完成的，

需要对每个属性列表在每个结点处都进行一遍扫描，费时很多，为此，SLIQ采

用广度优先策略构造决策树，即在决策树的每一层只需对每个属性列表扫描一次，就可以为当前决策树中每个叶子结点找到最优分裂标准。

SLIQ算法由于采用了上述两种技术，使得该算法能够处理比C4.5大得多的

训练集，在一定范围内具有良好的随记录个数和属性个数增长的可伸缩性。

然而它仍然存在如下缺点：

1）由于需要将类别列表存放于内存，而类别列表的元组数与训练集的元组数是相同的，这就一定程度上限制了可以处理的数据集的大小。

2）由于采用了预排序技术，而排序算法的复杂度本身并不是与记录个数成线性关系，因此，使得SLIQ算法不可能达到随记录数目增长的线性可伸缩性。

（4）SPRINT算法

为了减少驻留于内存的数据量，SPRINT算法进一步改进了决策树算法的数据结构，去掉了在SLIQ中需要驻留于内存的类别列表，将它的类别列合并到每个属性列表中。

这样，在遍历每个属性列表寻找当前结点的最优分裂标准时，不

必参照其他信息，将对结点的分裂表现在对属性列表的分裂，即将每个属性列表

分成两个，分别存放属于各个结点的记录。

SPRINT算法的优点是在寻找每个结点的最优分裂标准时变得更简单。

其缺点是对非分裂属性的属性列表进行分裂变得很困难。

解决的办法是对分裂属性进行分裂时用哈希表记录下每个记录属于哪个孩子结点，若内存能够容纳下整个哈希表，其他属性列表的分裂只需参照该哈希表即可。

由于哈希表的大小与训练集的大小成正比，当训练集很大时，哈希表可能无法在内存容纳，此时分裂只能分批执行，这使得SPRINT算法的可伸缩性仍然不是很好。

分类算法综述（三）贝叶斯（Bayes）分类算法

贝叶斯分类是统计学分类方法，它是一类利用概率统计知识进行分类的算法。

在许多场合，朴素贝叶斯（NalVeBayes,NB）分类算法可以与决策树和神经网络分类算法相媲美，该算法能运用到大型数据库中，且方法简单、分类准确率高、速度快。

由于贝叶斯定理假设一个属性值对给定类的影响独立于其它属性的值，而此假设在实际情况中经常是不成立的，因此其分类准确率可能会下降。

为此，就出现了许多降低独立性假设的贝叶斯分类算法，女口TAN（treeaugmentedBayes

network）算法。

（1）朴素贝叶斯算法

设每个数据样本用一个n维特征向量来描述n个属性的值，即：

X={x1,x2,…，xn}，假定有m个类，分别用C1,C2,…Cm表示。

给定一个未知的数据样本X（即没有类标号），若朴素贝叶斯分类法将未知的样本X分配给类Ci，则一定

是

P（Ci|X）>P（Cj|X）1

根据贝叶斯定理

由于P（X）对于所有类为常数，最大化后验概率P（Ci|X）可转化为最大化先验概率P（X|Ci）P（Ci）。

如果训练数据集有许多属性和元组，计算P（X|Ci）的开销可能非常大，为此，通常假设各属性的取值互相独立，这样

先验概率P（x1|Ci）,P（x2|Ci）,…，P（xn|Ci）可以从训练数据集求得。

根据此方法，对一个未知类别的样本X，可以先分别计算出X属于每一个类别Ci的概率P（X|Ci）P（Ci）,然后选择其中概率最大的类别作为其类别。

朴素贝叶斯算法成立的前提是各属性之间互相独立。

当数据集满足这种独立性假设时,分类的准确度较高,否则可能较低。

另外,该算法没有分类规则输出。

（2）TAN算法

TAN算法通过发现属性对之间的依赖关系来降低NB中任意属性之间独立的假设。

它是在NB网络结构的基础上增加属性对之间的关联（边）来实现的。

实现方法是：

用结点表示属性,用有向边表示属性之间的依赖关系,把类别属性作为根结点,其余所有属性都作为它的子节点。

通常,用虚线代表NB所需的边，用实线代表新增的边。

属性Ai与Aj之间的边意味着属性Ai对类别变量C的影响还取决于属性Aj的取值。

这些增加的边需满足下列条件：

类别变量没有双亲结点，每个属性有一个类别变量双亲结点和最多另外一个属性作为其双亲结点。

找到这组关联边之后，就可以计算一组随机变量的联合概率分布如下：

其中nAi代表的是Ai的双亲结点。

由于在TAN算法中考虑了n个属性中（n-1）个两两属性之间的关联性，该算法对属性之间独立性的假设有了一定程度的降低，但是属性之间可能存在更多其它的关联性仍没有考虑，因此其适用范围仍然受到限制。

2.3基于关联规则的分类算法关联规则挖掘是数据挖掘研究的一个重要的、高度活跃的领域。

近年来，数据挖掘技术己将关联规则挖掘用于分类问题，取得了很好的效果。

ARCS（AssociationRuleClusteringSystem基于聚类挖掘关联规则，然后使用规则进行分类。

将关联规则画在2-D栅格上，算法扫描栅格，搜索规则的矩形聚类。

实践发现，当数据中存在孤立点时，ARCS比C4.5稍微精确一点。

ARCS

的准确性与离散化程度有关。

从可伸缩性来说，不论数据库多大，ARCS需要的存储容量为常数。

CBA（classificationbasedonassociation是基于关联规则发现方法的分类算法。

该算法分两个步骤构造分类器。

第一步：

发现所有形如xi1Ax=>Ci的关联规则，即右部为类别属性值的类别关联规则（classificationassociationrulesCAR）。

第二步：

从已发现的CAR中选择高优先度的规则来覆盖训练集，也就是说，如果有多条关联规则的左部相同，而右部为不同的类，则选择具有最高置信度的规则作为可能规则。

文献[4]对该过程进行了较深入的研究，使得算法在此步骤不需要对训练数据集进行过多的扫描。

CBA算法的优点是其分类准确度较高，在许多数据集上比C4.5更精确。

此

外，上述两步都具有线性可伸缩性。

CBA（ClassificationBasedonAssociation）是关联分类。

此算法把分类规则挖掘和关联规则挖掘整合到一起。

与CART和C4.5只产生部分规则不同的是,CBA

产生所有的类关联规则CARs（ClassAssociationRules）然后选择最好的规则去覆盖训练集。

另外，在此算法的框架中，数据库可以驻留在磁盘中

CAEP使用项集支持度挖掘HV露模式（EmergingPattern）,而EP用于构造分类。

CAEP找出满足给定支持度和增长率阈值的EP。

己经发现，在许多数据集上,CAEP比C4.5和基于关联的分类更精确。

一种替代的、基于跳跃的HV露

模式JEP（JnmpingEmergingPattern是一种特殊类型的EP，项集的支持度由在一个数据集中的0陡峭地增长到另一个数据集中的非0。

在一此大的多维数据库中，JEP性能优于CAEP，但在一些小型数据库中，CAEP比JEP优，这二种分类法被认为是互补的。

ADT（AssociationDecisionTree）分二步实现以精确度驱动为基础的过度适合规则的剪枝。

第一步，运用置信度规则建立分类器。

主要是采用某种置信度的单调性建立基于置信度的剪枝策略。

第二步，为实现精确性，用关联规则建立一种

平衡于DT（DccisionTree）归纳的精确度驱动剪枝。

这样的结果就是ADT（AssociationBasedDecisionTree）。

它联合了大量的关联规则和DT归纳精确性驱动剪枝技术。

基于多维关联规则的分类算法CMAR（ClassificationBasedonMultipleClass-AssociationRules）是利用FP-Growth算法挖掘关联规则，建立类关联分布树FP—树。

采用CR—树（ClassificationRulcTrcc）结构有效地存储关联规则。

基于置信度、相关性和数据库覆盖来剪枝。

分类的具体执行采用加权厂来分析。

与CBA和C4.5相比，CMAR性能优异且伸缩性较好。

但CMAR优先生成的是长规则，对数据库的覆盖效果较差；利用加权x2统计量进行分类，会造成x2统计量的失真，致使分类值的准确程度降低。

CPAR（ClassificationBasedonPredictiveAssociationRules）整合了关联规则分类和传统的基于规则分类的优点。

为避免过度适合，在规则生成时采用贪心算法，这比产生所有候选项集的效率高；采用一种动态方法避免在规则生成时的重复计算；采用顶期精确性评价规则，并在预测时应用最优的规则，避免产生冗余的规则。

另外，MSR（MinimnmSetRule）针对基于关联规

则分类算法中产生的关联规则集可能太大的问题，在分类中运用最小关联规则集。

在此算法中，CARS并不是通过置信度首先排序，因为高置信度规则对噪声是很敏感的。

采用早期剪枝力方法可减少关联规则的数量，并保证在最小集中没有不