分类算法摘要：分类算法是数据挖掘中的最重要的技术之一。

通过对当前提出的最新的具有代表性的分类算法进行分析和比较，总结每类算法的各方面特性，从而便于研究者对已有的算法进行改进，提出具有更好性能的新的分类算法，同时方便使用者在应用时对算法的选择和使用。

关键词：分类算法决策树基于规则贝叶斯人工神经网络支持向量机分类是挖掘数据的一个重要技术，是数据挖掘中最有应用价值的技术之一，其应用遍及社会各个领域。

分类任务就是通过学习得到一个目标函数（通常也称作分类模型，即分类器），把每个属性集映射到一个预先定义的类标号。

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

和回归方法不同的是，分类的类标号是离散属性，而预测建模的回归的目标属性是连续的。

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

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

在训练阶段,分析训练数据集的属性，为每个属性产生一个对相应数据集的属性描述或模型。

在测试阶段，利用属性描述或模型对测试数据集进行分类,测试其分类准确度。

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

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

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

(2)相关性分析。

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

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

(3)数据变换。

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

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

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

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

分类模型的构造方法有决策树类、基于规则类、最近邻类、贝叶斯类、人工神经网络类等。

1决策树分类算法1.1决策树基本概念决策树是一种由结点和有向边组成的层次结构，树中包含三种结点；根结点、内部结点和叶结点（终结点）。

它采用自顶向下的递归方式，在根结点使用属性将训练数据集区分开，在内部结点进行属性值的比较，并根据不同的属性值从该结点向下分支，树的每个叶结点都赋予一个类标号，即在叶结点得到结论。

决策树是实例的分类器。

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

可将实例分到多个分类(≥2)并以析取范式(DNF)形式重写为规则。

这种具有预测功能的系统叫决策树分类器。

1.2常用的决策树算法决策树分类算法从提出以来，出现了很多算法，比较常用的有：1986年Quinlan提出了著名的ID3算法。

ID3算法体现了决策树分类的优点：算法的理论清晰，方法简单，学习能力较强。

其缺点是:只对比较小的数据集有效，且对噪声比较敏感，当训练数据集加大时，决策树可能会随之改变，并且在测试属性选择时，它倾向于选择取值较多的属性。

在ID3算法的基础上，1993年Quinlan又自己提出了改进算法—C4. 5算法。

为了适应处理大规模数据集的需要，后来又提出了若干改进的算法，其中SLIQ(su-pervised learning in quest)和SPRINT (scalable parallelizable induction of decision trees)是比较有代表性的两个算法，PUBLIC (Pruning andBuilding Integrated in Classification)算法是一种很典型的在建树的同时进行剪枝的算法。

此外，还有很多决策树分类算法。

1.3决策树技术中的核心问题建立决策树的目标是通过训练样本集，建立目标变量关于各输入变量的分类预测模型，全面实现输入变量和目标变量不同取值下的数据分组，进而用于对新数据对象的分类和预测。

当利用所建决策树对一个新数据对象进行分析时，决策树能够依据该数据输入变量的取值，推断出相应目标变量的分类或取值。

决策树技术中有各种各样的算法，这些算法都存在各自的优势和不足。

目前，从事机器学习的专家学者们仍在潜心对现有算法的改进，或研究更有效的新算法总结起来，决策树算法主要围绕两大核心问题展开:第一，决策树的生长问题，即利用训练样本集，完成决策树的建立过程。

第二，决策树的剪枝问题，即利用检验样本集，对形成的决策树进行优化处理。

以下将主要就这两方面的问题进行论述。

1.4决策树的应用和注意事项决策树是数据挖掘应用最广的技术之一，一般用于对新数据对象的分类或预测。

在实际分析中，决策树还可以应用到其他方面，如生成推理规则，寻找最佳变量等决策树可以看成是推理规则的一种图形表示，可以在决策树的基础之上产生推理规则。

另外，由于决策树的建立过程是一个不断选择最佳输入变量的过程。

因此，在划分数据方面，高层结点上的输入变量比低层结点上的输入变量更有价值，所以可以将决策树看成一种测度变量价值大小的工具。

应用决策树技术时应注意以下几个问题：第一，一般的决策树算法中，决策树的每个分枝判断只能针对单个输入变量值进行，无法同时根据多个输入变量的取值情况进行判断，这会在一定程度上限制决策树的应用范围。

从而，需要事先对变量进行处理。

第二，决策树所处理的输入变量的类型可以是定距型，也可以是定类或定序型。

在处理不同类型数据时，决策树有各自的优点和问题：当输入变量是定距型时，决策树技术的主要优势是：当数据采用不同的计量单位或当数据中存在离群点时，不会给决策树带来显著影响，因而不会给数据的准备工作带来额外负担;缺点是：忽略了数据所中蕴涵的分布形态的信息。

当输入变量是定类或定序型时，决策树的建树效率会较高。

但主要的问题是:当输入变量的分类值很多且取值分布极为分散时，决策树会过于“茂盛”，使得树结点上的样本量随着树层数的增加而快速下降，不利于决策树的合理生长改进的方法是将样本量较少的类合并，但由于类间合并有很多可选择的方案，只有穷尽所有的类合并方案后才有可能得到较好的合并结果，但穷尽的可行性会受到实际应用的限制。

1.5决策树算法的实例决策树分类可应用在钢铁厂轧辊选择中，用于决策是否更换某一轧辊的情况，在钢铁厂中，轧辊是易磨损的，且轧辊选择中，用于决策是价格比较高，需要经常更换，使用成本比较高。

而且一旦轧辊出了问题，可能会造成很大的损失。

正确的决策是否更换某一轧辊，使得公司的效益最大化，具有重要的现实意义。

把以往的更换情况整理的数据作为训练集，然后对影响是否更换的相关特征进行数据挖掘，从而可得到对轧辊的选择的决策进行指导的有意义的知识。

在进行挖掘前，首先对数据进行清理，可采用平滑技术消除或减少噪声，用该属性最常用的值处理空缺值。

用决策树算法进行分类，要求处理连续属性和离散属性。

在选择中，轧辊受役龄、价格、是否关键部件和磨损程度等多种因素影响，通过分类算法得到决策树，用来决策正在生产线上的某一轧辊是否需要更换。

表1中的数据是从钢铁厂的轧辊更换的数据库中抽取出的部分数据，含有5个属性：役龄、价格、是否关键部件、磨损程度和是否更换。

利用这样的少量的数据来说明决策树分类在钢铁厂轧辊选择中的应用。

表1 轧辊更换情况数据库训练数据使用信息增益进行属性选择：更新的备件数为s1，不更新的备件数为s2。

I (s1, s2)=I(9, 5)=0.94E(役龄)=0.694Gain(役龄)=0.245同理，Gain(价格)=0. 21, Gain(是否关键部件)=0. 15, Gain(磨损程度)=0. 10因为Gain(磨损程度)<Gain(关键部件)<Gain(价格)<Gain(役龄)，可以看出以“役龄”，这个属性进行训练集分类的信息赢取值最大，于是“役龄”就被选为用于划分的属性，以此类推，可以得到决策树如图1所不。

图1使用ID3算法得到轧辊是否更换问题的决策树这样的通过训练集得到的决策树分类模型就可以用来对新数据进行分类了，即可以判断生产线上的轧辊是否需要更换了。

2基于规则分类算法2.1基于规则分类器概念基于规则的分类器是使用一组“if …then ”规则来分类记录的技术。

模型店规则用析取范式 R=（r 1 v r 2 v ···v r k ）表示，而每一项分类规则可以表示为如下形式：r i （条件i ）——>y i其中R 称作规则集，r i 是分类规则或析取项，给则的左边称为规则前件，右边称为规则后件。

如果规则r 的前件和记录x 的属性匹配，则称r 覆盖x 。

分类规则的质量可以用覆盖率和准确率（或置信因子）来度量。

若给定数据集D 和条件A ，则有：覆盖率=D A 准确率=AyA ⋂其中A 是满足规则前件的记录数，y ⋂A 是同时满足规则前件和后件的记录数，D 是记录总数。

2.2基于规则分类器工作原理基于规则的分类器根据测试记录所触发的规则来分类记录，所产生的规则集有两个重要的性质：第一是互斥规则，如果规则集R 中不存在两条规则被同一条记录触发；第二是穷举规则，如果对属性值的任一组合，R 中都存在一条规则加以覆盖。

两个性质可以保证每一条记录被且仅被一条规则覆盖。

而解决规则集不是互斥的所带来可能相互冲突的预测规则有两种方法：第一是有序规则，使规则集中的规则按照优先等级排序，避免由多条预测而产生的类冲突的问题；第二是无需规则，把每条规则的后件看做是对相应的一次投票，然后计票确定测试记录的类标号，可以避免由于选择不当的规则而产生的错误影响，其次模型的开销相对较小，从而不必维护规则的顺序。

2.3基于关联规则(CBA: Classification Based on Association Rule)的分类算法CBA 算法主要是通过发现样本集中的关联规则来构造分类器。

关联规则的发现采用经典算法Apriori ，通过迭代检索出数据集中所有的频繁项集，即支持度小低于用户设定阈值的项集。

此算法的优点是发现的规则相对较全面且分类准确度较高，其缺点是：①当潜在频繁2项集规模较大时，算法会受到硬件内存的制约，导致系统I/O 负荷过重；②由于对数据的多次扫描和JOIN 运算所产生潜在频繁项集，Apriori 算法的时问代价高昂。

针对Apriori 算法的缺陷，LIG(large items generation)算法在求解频繁1项集的同时计算相应项的相关区问，以此得到缩小了的项集的潜在频繁2项集。

频繁模式增长((FP)算法放弃利用潜在频繁项集求解频繁项集的做法，进而提出频率增长算法。

该算法通过扫描数据集得到频繁项的集合以及各项支持度，并按支持度大小降序排列频繁项目列表，然后通过构造一个FP —树来进行关联规则挖掘。

其优点是:在完备性上，它不会打破任何模式且包含挖掘所需的全部信息；而在紧密性方面，它能剔除不相关信息，并不包含非频繁项，故支持度高的项在FP —树中共享机会也高。