◆魏茂胜



数据挖掘中的分类算法综述

◆魏茂胜

(中国矿业大学(北京)机电与信息工程学院 北京 100083)

随着网络数据爆炸式增长，数据库规模日益扩大，越来越多的人开始研究数据挖掘，作为数据挖掘中关键技术的分类算法也同样受到了广泛关注。对数据挖掘中典型分类算法的总结和比较，有利于开发者高效地选择算法，也有利于研究者对算法改进提高。

数据挖掘；分类算法；综述

0 概述

基于数据库的知识发现是伴随着人工智能和数据库的快速发展而被提出的计算机技术，它通过某种算法从大量的数据中搜索其中隐藏的有用信息，机器学习、模式识别、统计学、知识获取、智能数据库、专家系统和高性能计算等众多领域都与该技术息息相关[1]。数据挖掘(Data Mining)是基于数据库的知识发现中的关键步骤，通常将其中的知识学习阶段称为数据挖掘。

分类(Classification)算法是数据挖掘的关键技术，它通过对数据训练集的分析研究，发现分类规则，从而具备预测新数据类型的能力。分类算法主要包括两个阶段:构建模型阶段:通过分析学习已知的训练数据集，训练并构建一个准确率可以接受的模型，该模型用于描述特定的数据类集;使用模型阶段:使用训练后的模型对未知的数据对象进行分类。目前许多分类算法已被各领域研究者提出，不同的分类算法适用于不同的情况，这使得开发者对分类算法的选择存在诸多困惑。本文介绍了几种经典的数据分类算法，并分析了各自的特性，以便于开发者和研究者对分类算法的选择和研究。

1 分类算法

分类算法有很多，本文将重点介绍决策树、贝叶斯、遗传、人工神经网络、基于关联规则分类算法。

1.1决策树分类算法

决策树(Decision Tree)是由一系列节点和分支组成的树状图，其中分支由节点和子节点组成。节点表示学习或决策过程中需要考虑的属性，不同的分支则由不同的属性构成。利用某事例的属性值，从决策树的树根节点往下搜索，直至叶子节点，便可对该事例进行学习，做出决策。学习或决策的最终结果由叶子节点表示。

决策树通过对实例集的分析归纳进行学习，具备多概念学习的能力，使用简便快捷，应用领域广泛。对用无结构的属性-值对表示的大规模实例数据进行分类学习时，决策树算法是较优的选择。目前使用较多的决策树学习算法有ID3、C4.5[2]、SLIQ[3]和SPRINT[4]。

ID3作为一种决策树学习算法，可以便捷地描述概念属性-值的信息结构，算法简单容易实现且分类速度快。目前许多的被人熟知的决策树算法都是由该核心算法演变而来，例如C4.5算法。该算法通过由上而下的贪心算法构造决策树进行学习。构造过程由选择确定在根节点测试的属性开始，依据最大的信息增益和最小熵的标准来选择决策树上每个节点的被测试属性，对象集则由测试结果划分。多次进行该过程直至某一子树的叶子节点与分类标准为同一类为止。

1.2贝叶斯分类算法

贝叶斯(Bayes)分类算法在贝叶斯公式的基础上提出，是一种利用概率统计知识进行分类的算法。该分类算法在先验概率与类条件概率已知的情况下，通过贝叶斯定理计算一个类别未知的给定样本属于各个类别的概率，并且选择其中概率最大的类别作为该样本的确定类别。

朴素贝叶斯分类算法是应用最为广泛的一种基础贝叶斯算法，方法简单，运算速度快。但因为贝叶斯定理的成立依赖于严格的属性值独立性假设前提，而此假设前提在实际应用中常常是错误的，因此这种分类算法的准确率会降低。其他降低独立性假设要求的贝叶斯算法相继被研究者提出，例如TAN算法[5]。

1.3遗传算法

遗传算法是由生物进化理论演变而来的高效搜索和随机优化算法，是自然科学和计算机算法相结合的一个重要突破。该算法借助自然进化原理，把求解问题的过程转变成根据染色体上的基因寻找适应度高的染色体的过程。该算法综合了定向搜素与随机搜索的优点从而具有良好的全局搜索能力，避免了大多数优化方法容易陷入局部最优的缺点。

与自然界相似，遗传算法求解问题时并不需要对该问题有所了解，它的任务只是对算法过程中产生的所有染色体进行评价，然后根据适应度值的大小筛选染色体，其中适应度值高的染色体繁殖下一代的机会更大。染色体是遗传算法中由随机方式产生的若干个数字编码，这些染色体组成了初始种群；适应度函数的作用是用数值大小来评价每个个体，适应度低的个体会被淘汰，适应度高的个体参加遗传操作，通过交叉、变异等遗传操作后的染色体组成下一代新的种群。再对这个新种群进行下一轮进化直到得出最优解或达到最大的迭代次数。

1.4人工神经网络算法

神经网络是一种由许多神经元节点按照某些特定规则连接构成的信息处理网络。该算法可以模拟人脑的功能对训练样本进行学习分类，它从输出节点反向传播由误差引起的权值调整，其中网络的信息分布式存储于网络各个单元之间的连接权系数中。目前主要的神经网络有自组织网络、前向神经网络和后向神经网络，分类算法主要采用前向神经网络。BP网络由于其良好的非线性逼近能力与分类能力而被广泛地应用。

BP神经网络属于多层前向网络，该网络从输入节点经过各个隐含层向输出层正向传递信号，如果输出结果未达到期望值，则由输出节点反向传播误差，进行权值修正直至得到期望输出。其中每层节点的输出由上层节点决定，同层节点间没有耦合。只要有足够多的隐含层单元就能保证以任意的精度逼近任意的函数。

1.5基于关联规则的分类算法

基于关联规则(Classification based on association rule，CBA)的分类算法的提出弥补了贝叶斯分类算法需要大量样本的不足。CBA算法根据实例集中的关联规则来构造分类器，该过程通常需要两个步骤:首先，发现所有的右部为类别属性值的类别关联规则，这种规则称为CAR;接着，在所有已找到的CAR中选择置信度最高的关联规则来覆盖训练集。该分类算法发现规则较为全面，所以其分类结果也较准确，是一种潜力很大的分类算法，Aprior是基于关联规则的经典算法。

Apriori算法是一种通过迭代方法寻找所需频繁项集的基础算法。该算法可分为三步实现：首先，找到出现的频繁性大于等于预定义的最小支持度的所有项集来组成频繁项集；接着，通过频繁项集，以最小支持度和最小可信度为标准生成强关联规则;最后，使用之前得到的频集生成右部只有一项的规则，生成的这些规则只能包含集合项。通过这些产生的规则就可以留下可信度大于给定的最小可信度的规则。

2 结语

数据挖掘技术的实用性和重要性程度日益提高，许多分类算法也相继被提出，除了本文所介绍的几种之外，常用的分类算法还有基于数据库的分类算法、粗糙集分类算法、基于支持向量机的分类算法以及K-最近邻分类算法等等。每种算法都有各自的特性，没有一种算法可以适用于所有情况，了解每种算法的优缺点有助于我们更好地使用和研究。

[1]程建华.数据挖掘分类算法研究综述[J].中国高新技术企业，2008.

[2]Quinlan J R.C4.5:programs for machine learning[M]. DBLP,1993.

[3]Chandra B,Varghese P P.Fuzzy SLIQ decision tree algorithm[J].IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics A Publication of the IEEE Systems Man & Cybernetics Society,2008.

[4]Shafer J C.Agrawal R.Mehta M. SPRINT: A Scalable Parallel Classifier for Data Mining[C]// Proceedings of the 22th International Conference on Very Large Data Bases. Morgan Kaufmann Publishers Inc,2000.

[5]Liao Y,Zeng X,Song T,et al.Stock Price Forecast Using Tree Augmented Naïve (TAN) Bayes[M]// Proceedings of The Eighth International Conference on Bio-Inspired Computing:Theories and Applications (BIC-TA),2013.