数据挖掘中分类方法综述.

68*本文系国家自然科学基金资助项目“用于数据挖掘的神经网络模型及其融合技术研究”(项目编号:60275020课题研究成果之一。收稿日期:2006-03-25修回日期:2006-07-23本文起止页码:68-71,108钱晓东天津大学电气与自动化工程学院天津300072〔摘要〕对数据挖掘中的核心技术分类算法的内容及其研究现状进行综述。认为分类算法大体可分为传统分类算法和基于软计算的分类法两类,主要包括相似函数、关联规则分类算法、K近邻分类算法、决策树分类算法、贝叶斯分类算法和基于模糊逻辑、遗传算法、粗糙集和神经网络的分类算法。通过论述以上算法优缺点和应用范围,研究者对已有算法的改进有所了解,以便在应用中选择相应的分类算法。〔关键词〕数据挖掘分类软计算〔分类号〕TP183AReviewonClassificationAlgorithmsinDataMiningQianXiaodongSchoolofElectricalEngineeringandAutomation,TianjinUniversity,Tianjin300072〔Abstract〕Asoneofthekerneltechniquesinthedatamining,itisnecessarytosummarizetheresearchstatusofclassificationalgorithm.Classificationalgorithmscanbedividedintoclassicalalgorithmsandalgorithmsbasedonsoftcomputing,primarilyincludingsimilarfunction,classificationalgorithmsbasedonassociationrule,K-nearestNeighbor,decisiontree,Bayesnetworkandclassificationalgorithmsbasedonfuzzylogic,geneticalgorithm,neuralnetworkandroughsets.Bypresentingtheadvantagesanddisadvantagesandtheapplicationrangeofthealgorithmsmentionedabove,itwillbehelpfulforpeopletoimproveandselectalgorithmsforapplications,andeventodevelopnewones.〔Keywords〕dataminingclassificationsoftcomputing数据挖掘中分类方法综述*1前言数据挖掘源于20世纪90年代中期,是一个既年轻又活跃的研究领域,涉及机器学习、模式识别、统计学、数据库、知识获取与表达、专家系统、神经网络、模糊数学、遗传算法等多个领域。分类技术是数据挖掘中最有应用价值的技术之一,其应用遍及社会各个领域。基于人工智能和信息系统,抽象层次上的分类是推理、学习、决策的关键,是一种基础知识。因而数据分类技术可视为数据挖掘中的基础和核心技术。其实,该技术在很多数据挖掘中被广泛使用,比如关联规则挖掘和时间序列挖掘等。因此,在数据挖掘技术的研究中,分类技术的研究应当处在首要和优先的地位。目前,数据分类技术主要分为基于传统技术和基于软计算技术两种。2传统的数据挖掘分类方法2.1数据分类中相似函数的研究数据分类首先涉及到样本间的相似度判定函数,向量相似性判定函数可根据向量特征可比性以及是否能满足距离三角不等式加以区分,而不满足距离三角不等式的向量相似性判定函数可根据互近邻距离等来判定。当向量特征是非同质的,简单地使用上述相似性判定函数是不合适的;而对于不同质的特征,使用不同的相似性判定函数也是困难的,因为:①不同判定函数之间的综合判定很困难;②某些向量特征取决于质;③即使取决于特征量,用于相似性判定函数的离散值或区间值也需进一步研究。对于离散的向量特征,人们提出了简单匹配系数、Jaccard系数、Rao系数等相似性判定函数,但在实际使用中却存在很多限制,且这只适用于离散值数量较少的情况。目前,非同质、离散、半连续半离散以及同质的相似性判定函数的研究成果还比较少。但以上讨论仅限于在两个向量之间,在实际分类过程中,也会涉及两个类别之间相似程度(距离的计算,因为这无论在分类过程中还是评价分类质量时都是必不可少的。在实际应用中,类别间相似程度的计算函数主要包括最近距离函数、质心距离函数、平均距离函数等。2.2传统数据分类方法分类技术针对数据集构造分类器,从而对未知类别样本赋予类别标签。在其学习过程中和无监督的聚类相比,一般而言,分类技术假定存在具备环境知识和输入输出样本集知识的老师,但环境及其特性、模型参数等却是未知的。2.2.1基于关联规则(CBA:ClassificationBasedonAssocia-tionRule的分类算法该算法[1]的构造分类器可分为两步:第一步要发现所有形如xi1∧xi2=Ci的关联规则,即右侧均为类别属性值的关联规则;第二步要选择高优先度的规则来覆盖训练集,即若有多条关联规则的左侧均相同,而右侧为不同的类时,则选择具有最高置信度的规则作为可能规则。CBA算法主要是通过发现样本集中的关联规则来构造分类器。关联规则的发现采用经典算法Apriori[1],通过迭代检索出数据集中所有的频繁项集,即支持度不低于用户设定阈值的项集。此算法的优点是发现的规则相对较全面且分类准确度较高,其缺点是:①当潜在频繁2项集规模较大时,算法会受到硬件内存的制约,导致系统I/O负荷过重;②由于对数据的多次扫描和JOIN运算所产生潜在频繁项集,Apriori算法的时间代价高昂。针对Apriori算法的缺陷,LIG(largeitemsgeneration算法在求解频繁1项集的同时计算相应项的相关区间,以此得到缩小了的项集的潜在频繁2项集。频繁模式增长(FP算法放弃利用潜在频繁项集求解频繁项集的做法,进而提出频率增长算法。该算法通过扫描数据集得到频繁项的集合以及各项支持度,并按支持度大小降序排列频繁项目列表,然后通过构造一个FP-树来进行关联规则挖掘。其优点是:在完备性上,它不会打破任何模式且包含挖掘所需的全部信息;而在紧密性方面,它能剔除不相关信息,并不包含非频繁项,故支持度高的项在FP-树中共享机会也高。该算法比Apriori快一倍,但当数据集过大时,所构建的FP-树仍受内存制约。2.2.2K近邻(KNN分类算法KNN方法基于类比学习,是一种非参数的分类技术,它在基于统计的模式识别中非常有效,并对未知和非正态分布可取得较高的分类准确率,具有鲁棒性、概念清晰等优点。其基本原理为:KNN分类算法搜索样本空间,计算未知类别向量与样本集中每个向量的相似度值,在样本集中找出K个最相似的文本向量,分类结果为相似样本中最多的一类。但在大样本集和高维样本分类中(如文本分类,KNN方法的缺陷也得以凸显。首先,KNN是懒散的分类算法,对于分类所需的计算均推迟至分类进行,故在其分类器中存储有大量的样本向量。在未知类别样本需要分类时,在计算所有存储样本和未知类别样本的距离时,高维样本或大样本集所需要的时间和空间的复杂度均较高。其次,KNN算法是建立在VSM模型上的,其样本距离测度使用欧式距离。若各维权值相同,即认定各维对于分类的贡献度相同,显然这不符合实际情况。基于上述缺点,人们也采用了一些改进算法:当样本数量较大时,为减小计算,可对样本集进行编辑处理,即从原始样本集中选择最优的参考子集进行KNN计算,以减少样本的存储量和提高计算效率。截止目前,其中最主要的方法有[2]:①近邻规则浓缩法。其编辑处理的结果是产生一个样本集的子集,然后在子集上进行KNN算法的计算。②产生或者修改原型法。这种方法包括建立一个原型和在原始训练样本集中调整几个有限的数据,其中多数情况下采用神经网络技术。③多重分类器的结合法。即由几个神经网络组成一个分类器,其每个神经网络都担当一个1-最近邻分类器的作用,对其中一个子集进行1-最近邻计算,而这个子集基于Hart’s方法产生。各维权重对于相等BP神经网络可用于计算各维权值,此方法虽然利用了神经网络的分类和泛化能力,但存在以下缺点:①BP神经网络学习算法本身存在一些不足(见下文;②在其测算属性权值时,需逐个删除输入节点,但每次删除均可能需要重新强化BP神经网络训练,故对于高维或大量的样本,计算量过大。也有人使用最佳变化梯度来求证每个属性的权重,但对于非线形的KNN算法,尤其当最佳函数存在多个局部最小值时,线形的梯度调整很难保证方法的收敛性。2.2.3决策树分类算法决策树是以实例为基础的归纳学习算法。它是一种从一组无次序、无规则的事例中推理出决策树形式的分类规则。它采用自顶向下的递归方式,对决策树内部的节点进行属性值比较,并根据不同属性值来判断该节点向下的分支。但在建立决策树的过程中需要设置停止增长条件,以使决策树能在适当的时候停止生长。同时,还要考虑把决策树修剪到合适的尺寸,并尽量保持决策树的准确度。在基于决策树的分类算法中,ID3(C4.5是较早的决策树分类算法,其后又出现多种改进算法,其中SLIQ(supervisedlearninginquest和SPRINT(scalableparallelizableinductionofdecisiontree算法最具代表性。2.2.3.1ID3(C4.5分类算法Quinlan提出的ID3学习算法通过选择窗口来形成决策树,它利用的是信息论中的互信息或信息增益理论来寻找具有最大信息量属性而建立决策树节点的方法,并在每个分支子集重复这个过程。该方法的优点是描述简单、分类速度快、产生的分类规则易于理解。但此算法抗噪性差,训练正例和反例较难控制。C4.5分类算法后来虽得到改进,但仍存在算法低效问题,故不能进行增量学习。2.3.3.2SLIQ分类算法[3]针对C4.5改进算法而产生的样本集反复扫描和排序低效问题,SLIQ分类算法运用了预排序和广度优先两项技术。预排序技术消除了结点数据集排序,广度优先策略为决策树中每个叶子结点找到了最优分裂标准。SLIQ算法由于采用了上述两项技术使其能处理比C4.5大得多69的样本集;但由于所需内存较多,这在一定程度上限制了可以处理的数据集的大小;预排序技术也使算法性能不能随记录数目进行线性扩展。2.2.3.3SPRINT分类算法[4]为了减少驻留于内存的数据量,SPRINT算法进一步改进了决策树算法的数据结构,去掉在SLIQ中需要驻留于内存的类别列表,将类别合并到每个属性列表中。这样,在遍历每个属性列表中寻找当前结点的最优分裂标准时,不必参照其他信息,使寻找每个结点的最优分裂标准变得相对简单,但缺点是对非分裂属性的属性列表进行分裂变得却非常困难,因此,此算法的可扩展性较差。此外,基于决策树的主要改进算法还包括EC4.5、CART(classificationandregressiontree、PUBLIC(pruningandbuildingintegreatedinclassification等。2.2.4贝叶斯分类算法贝叶斯分类是统计学分类方法,它是一类利用概率统计进行分类的算法,此算法利用Bayes定理来预测一个未知类别的样本的可能属性,可选择其可能性最大的类别作为该样本的类别。在许多场合,朴素贝叶斯(NaiveBayes分类算法可以与决策树和神经网络分类算法相媲美。但贝叶斯定理假设一个属性对给定类的影响独立于其他属性,但此假设在实际情况中经常不成立,因此影响了其分类的准确率。为此,也出现了许多降低独立性假设的贝叶斯改进分类算法,如TAN(treeaugmentedbayesnetwork算法[5]。TAN算法通过发现属性对之间的依赖关系来降低朴素贝叶斯算法中任意属性之间独立的假设。它是在朴素贝叶斯网络的基础上增加属性对之间的关联来实现的。其方法是:用结点表示属性,用有向边表示属性之间