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

来源：华佗养生网

ISSN100020054清华大学学报(自然科学版)2002年第42卷第6期

CN1122223󰃗N.42,No.6JTsinghuaUniv(Sci&Tech),2002,Vol5󰃗38

7272730

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

刘红岩,　陈　剑,　陈国青

(清华大学经济管理学院,北京100084)

摘　要:分类算法是数据挖掘中的最重要的技术之一。通过对当前提出的最新的具有代表性的分类算法进行分析和比较,总结每类算法的各方面特性,从而便于研究者对已有的算法进行改进,提出具有更好性能的新的分类算法,同时方便使用者在应用时对算法的选择和使用。关键词:数据挖掘;分类;关联规则中图分类号:TP311;TP391

文章编号:100020054(2002)0620727204

文献标识码:A

类算法之一,为了适应大规模数据集的处理,数据挖

[2]

掘研究兴起之后对它又进行了改进,其中SLIQ

[3]

(supervisedlearninginquest)和SPRINT(scal2ableparallelizableinductionofdecisiontrees)是比较有代表性的两个算法。1.1　C4.5算法算法简介假设T为训练集,为T构造决策树时,根据In2formationGain值选择作为结点的属性及标准,按照此标准将T分成n个子集。若第i个子集Ti含有的元组的类别一致,该结点就成为决策树的叶子结点而停止。而对于不满足此条件的T的其他子集,按照上述方法继续直至所有子集所含元组都属于一个类别为止。

算法分析

决策树分类算法与其他类分类算法如统计方法、神经网络等比较起来有如下优点:

a)产生的分类规则易于理解。决策树的每个分枝都对应一个分类规则,因此决策树分类算法最终可以输出一个容易理解的规则集;b)速度相对较快;c)准确率相对较高。

尽管如此,决策树算法仍然有如下的缺点:首先,在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。其次,C4.5只适合于能够驻留于内存的数据集使用,当训练集大得无法在内存容纳时程序无法运行。1.2　SLIQ算法

SLIQ算法对C4.5决策树分类算法的实现方

Reviewofclassificationalgorithms

fordataminingLIUHongyan,CHENJian,CHENGuoqing

(SchoolofEconomicsandManagement,TsinghuaUniversity,Beijing100084,China)

Abstract:Classificationisoneofthemostimportanttechniquesindatamining.Thispapersummarizesthemainfeaturesofeveryalgorithmbyanalyzingandcomparingavarietyoftypicalclassifierstoprovideabasisforimprovingoldalgorithmsordevelopingneweffectiveones.Thesummarycanalsobeusedtoselectthesedataminingtechniquesfornewapplications.

Keywords:datamining;classification;associationrules

　　分类是数据挖掘中应用领域极其广泛的重要技术之一,至今已经提出很多算法。分类是根据数据集的特点构造一个分类器,利用分类器对未知类别的样本赋予类别的一种技术。构造分类器的过程一般分为训练和测试两个步骤。在训练阶段,分析训练数据集的特点,为每个类别产生一个对相应数据集的准确描述或模型。在测试阶段,利用类别的描述或模型对测试进行分类,测试其分类准确度。一般来说,测试阶段的代价远远低于训练阶段。

本文主要分析训练阶段。按照各种算法的技术特点,将其分成决策树类、Bayes类、基于关联规则类以及利用数据库技术类等几类算法进行叙述。

法进行了改进,在决策树的构造过程中采用了“预排

收稿日期:2001202213

基金项目:清华大学“九八五”基础研究项目作者简介:刘红岩(19682),女(汉),山东,讲师。

E2mail:hyliu@tsinghua.edu.cn

1　决策树分类算法

C4.5

[1]

是较早提出的使用最普遍的决策树分

728

清华大学学报(自然科学版)2002,42(6)

序”和“广度优先”两种技术。

算法描述

1)预排序

对于连续属性来说,在每个内部结点寻找其最优标准的时候,都需要对训练集按照该属性的取值进行排序,而排序是个很浪费时间的操作。为此SLIQ算法采用了预排序的技术,以便能够消除在

1.3　SPRINT算法

为了减少需要驻留于内存的数据量,SPRINT

算法进一步改进了决策树算法实现时的数据结构,去掉在SLIQ中需要驻留于内存的类别列表,将它的类别列合并到每个属性列表中。这样,在遍历每个属性列表寻找当前结点的最优标准时,不必参照其他信息。而对结点的表现在对属性列表的,即将每个属性列表分成两个,分别存放属于各个结点的记录。其优点是在寻找每个结点的最优标准时变得相对简单一些,但是其缺点是对非属性的属性列表进行变得很困难。解决的办法是对属性进行时用哈希表记录下每个记录属于哪个孩子结点,若内存能够容纳下整个哈希表,其他属性列表的只需参照该哈希表即可。由于哈希表的大小与训练集的大小成正比,当训练集很大时,哈希表可能无法在内存容纳,此时只能分批执行,这使得SPRINT算法的可扩展性仍然不是很好。决策树的每个结点对数据集进行排序的需要。所谓预排序,就是针对每个属性的取值,把所有的记录按照从小到大的顺序进行排序。

具体实现时,需要为训练集数据的每个属性创建一个属性列表。为每个元组的类别创建一个类别列表。如表1所示。在属性Age的属性列表中,第一列是训练集每一行中该属性的取值,第二列则是其记录号。在类别列表中,第一列是每行记录的类别,第二列是各行所属的结点编号。算法实现时需要有足够的内存来保存类别列表。

表1　属性列表和类别列表

训练集

AgeSalaryClass

3065G2315B4075G5540B55100G4560G233040455555Age

213654Salary1540606575100246135类别列表GBGBGGN1N1N1N1N1N1取值记录号取值记录号ClassLeef2　Bayes分类算法

Bayes分类算法是一类利用概率统计知识进行分类的算法,如NB(NaiveBayes)[4]算法。这些算法

　　2)广度优先策略

在C4.5中,树的构造是按照深度优先策略完成的,需要对每个属性列表在每个结点处都进行一遍扫描,费时很多。SLIQ采用广度优先策略构造决

策树,即在决策树的每一层只需对每个属性列表扫描一次,就可以为当前决策树中每个叶子结点找到最优标准。

算法分析

SLIQ算法由于采用了上述两种技术使得该算

主要利用Bayes定理来预测一个未知类别的样本属

于各个类别的可能性,选择其中可能性最大的一个类别作为该样本的最终类别。由于贝叶斯定理的成立本身需要一个很强的性假设前提,而此假设在实际情况中经常是不成立的,因而其分类准确性就会下降。为此就出现了许多降低性假设的Bayes分类算法,如TAN(treeaugmentedBayes

[4]

network)算法。2.1　NB算法

设u(a1u,a2u,…,anu)是未知类别的样本,p(ck󰃜u)是u属于类别ck∈{c1,c2,…,cm}的概率。由贝叶斯定理,假设各属性的取值互相,可以推导出:

法能够处理比C4.5所能处理的大得多的训练集,因此在一定程度上具有良好的随记录个数和属性个数增长的可扩展性。然而它仍然存在如下缺点:

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

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

p(ck󰃜u)∞p(ck)

∏p(a

i=1

󰃜ck)=

∏p(a

i=1iu

∧ck)

n-p(ck)

.　　根据此公式,对一个未知类别的样本u,可以计

算出u属于每一个类别的概率,选择其中概率最大的类别作为其类别即可。

NB算法成立的前提是各属性之间互相,即对于任何可能的属性A,B和类别属性C的取值,pr(A󰃜B,C)=pr(A󰃜C)都成立,则认为给定类别C、属性A和B是互相的。当数据集满足这

展性。

刘红岩,等:　数据挖掘中的数据分类算法综述729

种性假设时,分类的准确度较高,否则,则较低。这是该算法的主要特点。另外,该算法没有分类规则输出。2.2　TAN算法

TAN算法通过发现属性对之间的关联来降低

3.2　算法分析

CBA算法主要是通过发现训练集中的关联规

则来构造分类器。关联规则的发现采用经典算法Apriori,该算法对于发现隐藏于大量交易记录之中

它是在NB网络结NB中任意属性之间的假设。

构的基础上增加属性对之间的关联(边)来实现的,如图1[4]所示。

的关联规则来说是比较有效的。但当利用它发现分类规则时,为了防止漏掉某些规则,最小支持度经常被设为0,此时该算法就发挥不了它的优化作用,结果是产生的频繁集有时多得在内存无法容纳,从而使得程序无法继续运行。

CBA算法的优点是其分类准确度较高,因为它发现的规则相对较全面。

4　基于数据库技术的分类算法

虽然数据挖掘研究的兴起是由数据库领域的研究人员掀起的,然而至今为止提出的大多数算法则没有利用数据库的相关技术,数据挖掘应用也很难与数据库系统集成,此问题已成为该领域研究的关键问题之一。在分类算法中,致力于解决此问题的算[6][7]

法目前有MIND和GAC2RDB两个。4.1　MIND算法

MIND(miningindatabase)算法是采用数据库中用户定义的函数(user2definedfunction,简称UDF)实现发现分类规则的算法。

图1　从训练集pima中学习到的TAN模型

图中顶点代表一个随机变量,边代表变量之间的关联。虚线代表的是NB所需的边,实线代表是新增的边。属性Ai与Aj之间的边意味者属性Ai对类别变量的影响还取决于属性Aj的取值。为了节省时间,这些增加的边需满足的条件包括:类别变量没有双亲结点,每个属性有一个类别变量双亲结点和最多另外一个属性作为其双亲结点。找到这组关联边之后,就可以计算一组随机变量的联合概率分布如下:

pr(A1,A2,…,An,C)=pr(C)

∏p

i=1

(Ai󰃜0Ai)

其中0Ai代表的是Ai的双亲结点。从该算法可以看出,与NB算法相比,由于在TAN算法中考虑了n个属性中(n-1)个两两属性之间的关联性,该算法对属性之间性的假设有了一定程度的降低,但是属性之间可能存在的更多的其他的关联性仍没有考虑,因此其适用范围仍然受到。

算法描述MIND采用典型的决策树构造方法构建分类器。具体步骤同SLI其主要区别在于它采用Q类似。

数据库提供的UDF方法和SQL语句实现树的构造。简要的说就是在树的每一层,为每一个属性建立一个维表,存放各属性的每个取值属于各个类别的个数以及所属的结点编号。根据这些信息可以为当前结点计算每种标准的GiniIndex值,选出最优的标准,然后据此对结点进行,修改维表中结点编号列的值。上述过程中,对维表的创建和修改需要进行多次,若用SQL实现,耗时很多,因此采用UDF实现。而分类标准的寻找过程则通过创建若干表和视图,利用连接查询实现[8]。

算法分析在决策树的构建过程中,最费时的操作是对属于每个非终端结点的数据集进行类别分布信息的统计计算以及利用标准对数据集进行。这两种操作在MIND中都是通过UDF实现的。该算法的优点是通过采用UDF实现决策树的构造过程使得分类算法易于与数据库系统集成。

该算法的缺点是,算法采用UDF完成主要的

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

3.1　CBA算法描述

[5]

CBA(classificationbasedonassociation)是

基于关联规则发现方法的分类算法。该算法分两个步骤构造分类器:第一步:发现所有的右部为类别的类别关联规则(classificationassociationrules,简称CAR)。第二步:从已发现的CAR中选择高优先度的规则来覆盖训练集。论文对该过程进行较多的研究,使得算法在此步骤不需要对训练集进行过多的扫描。

730

清华大学学报(自然科学版)2002,42(6)

计算任务,而UDF一般是由用户利用高级语言实现的,无法使用数据库系统提供的查询处理机制,无法利用查询优化方法,且UDF的编写和维护相当复杂。另外MIND中用SQL语句实现的那部分功能本身就是比较简单的操作,而采用SQL实现的方法却显得相当复杂。4.2　GAC-RDB算法

GAC2RDB算法是一种利用SQL语句实现的

类算法。在算法的训练阶段,利用挖掘关联规则的

Apriori算法找出训练集中所有的频繁且有意义的的项集,存放于集合F中。对于一个未知类别的样本A,可以从F中找出包含在A中的最长的项集来计算A属于各个类别的概率,并且选择其中概率最大的类别为其分类。

LB算法的分类准确度比现有的其他分类算法的准确度好。但是该算法仍具有与贝叶斯类算法和CBA算法相同的缺点。

分类算法[7]。

算法描述

GAC2RDB算法采用一种基于分组记数的方法

6　总　结

分类是一种重要的数据挖掘技术.本文对各类

算法进行了分析、比较和总结。另外文[8]对这些分类算法的准确度和部分算法的执行速度进行了比较,结果表明,这些算法的准确度差别不大。实际上,在当今数据量不断膨胀的时代,算法的执行速度、可扩展性以及输出结果的可理解性等特性更为重要。因此尽管各个算法各有其优点,但一个各方面特性都很好的分类算法仍值得我们进一步研究。

参考文献　(References)

[1]QuinlanJR.C4.5:ProgramsforMachineLearning[M].

SanMateo,California:MorganKaufmann,1993.[2]MehtaM,AgrawalR,RissanenJ.SLIQ:Afastscalable

classifierfordatamining[A].LectureNotesincomputerSciProcofthe5thIntConfonExtendingDatabaseTech[C].Avignon,France,1996:1833.

[3]ShaferJC,AgrawalR,MehtaM.SPRINT:Ascalable

parallelclassifierfordatamining[A].Procofthe22ndIntConfonVeryLargeDatabases[C].Mumbai(Bombay),India,1996.

[4]FriedmanN,GeigerD,GoldszmidtM,Bayesiannetwork

classifier[J].MachineLearning,1997,29(1):131163.[5]LiuB,HsuW,MaY.Integratingclassificationand

associationrulemining[A].AgrawalR.Procofthe4thIntConfonKnowledgeDiscoveryandDataMining[C].NY,USA:AAAIPress,1998:8086.

[6]WANGM,IyerB,VitterJS.Scalableminingfor

classificationrulesinrelationaldatabases[A].EaglestoneB,DesaiBC,SHAOJianhua.Procofthe1998IntDatabaseEngandApplSymp[C].Cardiff,Wales,UK:IEEEComputerSociety,1998.5867.[7]LUHongjun,LIUHongyan.Decisiontables:scalable

calssificationexploringRDBMScapabilities[A].Proc26thIntConfonVeryLargeDatabases[C].Cairo,Egypt,2000:373384.

[8]刘红岩.可扩展的快速分类算法的研究与实现[D].北京:

清华大学,2000.LIUHongyan.ResearchandImplementationofaFastandScalableClassificationSystem[D].Beijing:TsinghuaUniversity,2000.(inChinese)[9]MeretakisD,WüthrichB.ExtendingNaiveBayesclassifiers

usinglongitemsets[A].ChaudhuriS.Proceedingsof5thInternationalConferenceonKnowledgeDiscoveryandDataMining[C].USA:AAAIPress,1999:295301.

统计训练集中各种属性取值组合的类别分布信息,通过最小置信度和最小支持度两个阈值找出有意义的分类规则。该算法使用关系数据库系统提供的聚集运算功能,利用SQL语句完成主要的计算任务。在该算法中,首先利用SQL语句计算利用每个属性进行类别判定的信息含量,从而选择一个最好的属性,并且按照信息含量的大小对属性进行排序。接着循环地进行属性的选择、候选分类表的生成、剪裁以及分类误差的计算,直到满足结束条件为止,如最小误差阈值和误差没有改善为止。

算法分析GAC2RDB算法具有的优点如下:

1)该算法将传统的一次一个记录(元组)的处理方式改变为面向集合的关系处理模式。使得算法具有与现有的其他分类器相同的分类准确度,执行速度有较大提高,而且关于训练集元组个数和属性个数的可扩展性良好。

2)算法使用标准的分组聚集统计语句,可以充分利用数据库系统的查询处理功能,使得应用程序不仅易于与数据库系统集成,而且用户需要编写的程序变得非常简单。

3)该算法在某种程度上与一些基于关联规则的分类算法如CBA和LB有些相似,但它避免使用基于Apriori算法,从而避免对数据集重复地进行扫描,也不需要对训练集转换成交易型数据库格式。

当然该算法仍然存在一些尚需改进的地方,例如,如何自动地确定参数的取值,改进属性选择的方法等。

5　其他分类算法

除了上述描述的各种分类算法之外,还有一些其他算法,例如LB(LargeBayes)[9]算法。

LB算法是一种基于概率统计和关联规则的分

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

全部频道

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