数据挖掘中分类方法综述

1、68*本文系国家自然科学基金资助项目“用于数据挖掘的神经网络模型及其融合技术研究”(项目编号:60275020课题研究成果之一。收稿日期:2006-03-25修回日期:2006-07-23本文起止页码:68-71,108钱晓东天津大学电气与自动化工程学院天津300072摘要对数据挖掘中的核心技术分类算法的内容及其研究现状进行综述。认为分类算法大体可分为传统分类算法和基于软计算的分类法两类,主要包括相似函数、关联规则分类算法、K 近邻分类算法、决策树分类算法、贝叶斯分类算法和基于模糊逻辑、遗传算法、粗糙集和神经网络的分类算法。通过论述以上算法优缺点和应用范围,研究者对已有算法的改进有所了解,以便

2、在应用中选择相应的分类算法。关键词数据挖掘分类软计算分类号TP183AReviewonClassificationAlgorithmsinDataMining QianXiaodongSchool of Electrical Engineering and A utomation, Tianjin University, Tianjin 300072AbstractAs one of the kernel techniques in the data mining, it is necessary to summarize the research status of classificati

3、on algorithm.Classification algorithms can be divided into classical algorithms and algorithms based on soft computing, primarily including similar function,classification algorithms based on association rule, K-nearest Neighbor, decision tree, Bayes network and classification algorithms based on fu

4、zzy logic, genetic algorithm, neural network and rough sets. By presenting the advantages and disadvantages and the application range of the algorithms mentioned above, it will be helpful for people to improve and select algorithms for applications, and even to develop new ones.Keywordsdata mining c

5、lassification soft computing数据挖掘中分类方法综述*1前言数据挖掘源于20世纪90年代中期,是一个既年轻又活跃的研究领域,涉及机器学习、模式识别、统计学、数据库、知识获取与表达、专家系统、神经网络、模糊数学、遗传算法等多个领域。分类技术是数据挖掘中最有应用价值的技术之一,其应用遍及社会各个领域。基于人工智能和信息系统,抽象层次上的分类是推理、学习、决策的关键,是一种基础知识。因而数据分类技术可视为数据挖掘中的基础和核心技术。其实,该技术在很多数据挖掘中被广泛使用,比如关联规则挖掘和时间序列挖掘等。因此,在数据挖掘技术的研究中,分类技术的研究应当处在首要和优先的地位。

6、目前,数据分类技术主要分为基于传统技术和基于软计算技术两种。2传统的数据挖掘分类方法2.1数据分类中相似函数的研究数据分类首先涉及到样本间的相似度判定函数,向量相似性判定函数可根据向量特征可比性以及是否能满足距离三角不等式加以区分,而不满足距离三角不等式的向量相似性判定函数可根据互近邻距离等来判定。当向量特征是非同质的,简单地使用上述相似性判定函数是不合适的;而对于不同质的特征,使用不同的相似性判定函数也是困难的,因为:不同判定函数之间的综合判定很困难;某些向量特征取决于质;即使取决于特征量,用于相似性判定函数的离散值或区间值也需进一步研究。对于离散的向量特征,人们提出了简单匹配系数、Jacc

7、ard 系数、Rao 系数等相似性判定函数,但在实际使用中却存在很多限制,且这只适用于离散值数量较少的情况。目前,非同质、离散、半连续半离散以及同质的相似性判定函数的研究成果还比较少。但以上讨论仅限于在两个向量之间,在实际分类过程中,也会涉及两个类别之间相似程度(距离的计算,因为这无论在分类过程中还是评价分类质量时都是必不可少的。在实际应用中,类别间相似程度的计算函数主要包括最近距离函数、质心距离函数、平均距离函数等。2.2传统数据分类方法分类技术针对数据集构造分类器,从而对未知类别样本赋予类别标签。在其学习过程中和无监督的聚类相比,一般而言,分类技术假定存在具备环境知识和输入输出样本集知识的

8、老师,但环境及其特性、模型参数等却是未知的。一步要发现所有形如xi1xi2=>Ci的关联规则,即右侧均为类别属性值的关联规则;第二步要选择高优先度的规则来覆盖训练集,即若有多条关联规则的左侧均相同,而右侧为不同的类时,则选择具有最高置信度的规则作为可能规则。CBA算法主要是通过发现样本集中的关联规则来构造分类器。关联规则的发现采用经典算法Apriori1,通过迭代检索出数据集中所有的频繁项集,即支持度不低于用户设定阈值的项集。此算法的优点是发现的规则相对较全面且分类准确度较高,其缺点是:当潜在频繁2项集规模较大时,算法会受到硬件内存的制约,导致系统I/O负荷过重;由于对数据的多次扫描和J

9、OIN运算所产生潜在频繁项集,Apriori算法的时间代价高昂。针对Apriori算法的缺陷,LIG(large items generation算法在求解频繁1项集的同时计算相应项的相关区间,以此得到缩小了的项集的潜在频繁2项集。频繁模式增长(FP算法放弃利用潜在频繁项集求解频繁项集的做法,进而提出频率增长算法。该算法通过扫描数据集得到频繁项的集合以及各项支持度,并按支持度大小降序排列频繁项目列表,然后通过构造一个FP-树来进行关联规则挖掘。其优点是:在完备性上,它不会打破任何模式且包含挖掘所需的全部信息;而在紧密性方面,它能剔除不相关信息,并不包含非频繁项,故支持度高的项在FP-树中共享机

10、会也高。该算法比Apriori快一倍,但当数据集过大时,所构建的FP-树仍受内存制约。但在大样本集和高维样本分类中(如文本分类,KNN方法的缺陷也得以凸显。首先,KNN是懒散的分类算法,对于分类所需的计算均推迟至分类进行,故在其分类器中存储有大量的样本向量。在未知类别样本需要分类时,在计算所有存储样本和未知类别样本的距离时,高维样本或大样本集所需要的时间和空间的复杂度均较高。其次,KNN算法是建立在VSM模型上的,其样本距离测度使用欧式距离。若各维权值相同,即认定各维对于分类的贡献度相同,显然这不符合实际情况。基于上述缺点,人们也采用了一些改进算法:当样本数量较大时,为减小计算,可对样本集进行

11、编辑处理,即从原始样本集中选择最优的参考子集进行KNN计算,以减少样本的存储量和提高计算效率。截止目前,其中最主要的方法有2:近邻规则浓缩法。其编辑处理的结果是产生一个样本集的子集,然后在子集上进行KNN算法的计算。产生或者修改原型法。这种方法包括建立一个原型和在原始训练样本集中调整几个有限的数据,其中多数情况下采用神经网络技术。多重分类器的结合法。即由几个神经网络组成一个分类器,其每个神经网络都担当一个1-最近邻分类器的作用,对其中一个子集进行1-最近邻计算,而这个子集基于Harts方法产生。各维权重对于相等BP神经网络可用于计算各维权值,此方法虽然利用了神经网络的分类和泛化能力,但存在以下

12、缺点:BP神经网络学习算法本身存在一些不足(见下文;在其测算属性权值时,需逐个删除输入节点,但每次删除均可能需要重新强化BP神经网络训练,故对于高维或大量的样本,计算量过大。也有人使用最佳变化梯度来求证每个属性的权重,但对于非线形的KNN算法,尤其当最佳函数存在多个局部最小值时,线形的梯度调整很难保证方法的收敛性。在基于决策树的分类算法中,ID3(C4.5是较早的决策树分类算法,其后又出现多种改进算法,其中SLIQ(supervised learning in quest和SPRINT(scalable parallelizable induction of decision tree算法最具

13、代表性。ID3(C4.5分类算法Quinlan提出的ID3学习算法通过选择窗口来形成决策树,它利用的是信息论中的互信息或信息增益理论来寻找具有最大信息量属性而建立决策树节点的方法,并在每个分支子集重复这个过程。该方法的优点是描述简单、分类速度快、产生的分类规则易于理解。但此算法抗噪性差,训练正例和反例较难控制。C4.5分类算法后来虽得到改进,但仍存在算法低效问题,故不能进行增量学习。69的样本集;但由于所需内存较多,这在一定程度上限制了可以处理的数据集的大小;预排序技术也使算法性能不能随记录数目进行线性扩展。SPRINT分类算法4为了减少驻留于内存的数据量,SPRI

14、NT算法进一步改进了决策树算法的数据结构,去掉在SLIQ中需要驻留于内存的类别列表,将类别合并到每个属性列表中。这样,在遍历每个属性列表中寻找当前结点的最优分裂标准时,不必参照其他信息,使寻找每个结点的最优分裂标准变得相对简单,但缺点是对非分裂属性的属性列表进行分裂变得却非常困难,因此,此算法的可扩展性较差。此外,基于决策树的主要改进算法还包括E C4.5、CART (classification and regression tree、PUBLIC(pruning and building integreated in classification等。T AN算法通过发现属性对之间的依赖关系

15、来降低朴素贝叶斯算法中任意属性之间独立的假设。它是在朴素贝叶斯网络的基础上增加属性对之间的关联来实现的。其方法是:用结点表示属性,用有向边表示属性之间的依赖关系,把类别属性作为根结点,其余所有属性都作为它的子节点。属性Ai与Aj 之间的边意味着属性Ai对类别变量C的影响取决于属性Aj。TAN算法考虑了n个属性中两两属性间的关联性,对属性之间独立性的假设有了一定程度的降低,但没有考虑属性之间可能存在更多的其他关联性,因此,其适用范围仍然受到限制。此外,还出现了贝叶斯信念网络、半朴素贝叶斯算法、BAN算法等多种改进算法。但贝叶斯分类算法学习是很困难的,有些研究已经证明其学习属于NP-complet

16、e问题。数据挖掘的分类算法很多,而且都在不断的发展中,因此,不宜一一例举。3基于软计算的数据分类方法在数据挖掘领域,软计算的用途越来越广泛:模糊逻辑用于处理不完整、不精确的数据以及近似答案等;神经网络用于高非线形决策、泛化学习、自适应、自组织和模式识别;遗传算法用于动态环境下的高效搜索、复杂目标对象的自适应和优化;粗糙集根据“核”属性获得对象的近似描述,能有效处理不精确、不一致、不完整等各种不完备信息。当数据集表现出越来越多的无标签性、不确定性、不完整性、非均匀性和动态性特点时,传统数据挖掘算法对此往往无能为力,软计算却可为此提供一种灵活处理数据的能力,软计算内的融合和与传统数据挖掘方法的结合

17、逐渐成为数据挖掘领域的研究趋势。3.1粗糙集(rough set粗糙集理论是一种刻划不完整和不确定性数据的数学工具6,不需要先验知识,能有效地处理各种不完备信息,从中发现隐含的知识,并和各种分类技术相结合建立起能够对不完备数据进行分类的算法。粗糙集理论将分类能力和知识联系在一起,使用等价关系来形式化地表示分类,知识因而表示为等价关系集R对离散空间U的划分。粗糙集理论还包含求取数据中最小不变集和最小规则集的理论,即约简算法(即分类中属性约简和规则生成,其基本原理是通过求属性的重要性并排序,在泛化关系中找出与原始数据具有同一决策或分辨能力的相关属性的最小集合,以此实现信息约简,这也是粗糙集理论在分

18、类中的主要应用。约简主要借助于信息表这样一种有效的知识表达形式;在保持信息表中决策属性和条件属性依赖关系不变时进行的信息表约简,具体包括属性约简和值约简。属性约简在一定程度上对信息表中的非必要的冗余信息进行约简,但对每一个实例而言仍可能存在不必要的属性,因此在不引起冲突的条件下可将每一个实例的不必要属性删除,即为值约简。值约简的最终结果就是分类所需要的规则,常见的值约简算法包括归纳值约简、启发式值约简、基于决策矩阵的值约简算法等、增量式规则获取算法和其他一些改进算法。粗糙集本身限制条件较强,在实际应用中,可以模态逻辑和概率统计信息对基本粗糙集模型进行扩展,从而形成了代数粗糙集模型和概率统计粗糙

19、集模型。3.2遗传算法遗传算法在解决多峰值、非线性、全局优化等高复杂度问题时具备独特优势,它是以基于进化论原理发展起来的高效随机搜索与优化方法。它以适应值函数为依据,通过对群体、个体施加遗传操作来实现群体内个体结构的优化重组,在全局范围内逼近最优解。遗传算法综合了定向搜索与随机搜索的优点,避免了大多数经典优化方法基于目标函数的梯度或高阶导数而易陷入局部最优的缺陷,可以取得较好的区域搜索与空间扩展的平衡。在运算时随机的多样性群体和交叉运算利于扩展搜索空间;随着高适应值的获得,交叉运算利于在这些解周围探索。遗传算法由于通过保持一个潜在解的群体进行多方向的搜索而有能力跳出局部最优解。遗传算法的应用主

20、要集中在分类算法7等方面。其基本思路如下:数据分类问题可看成是在搜索问题,数据库看作是70搜索空间,分类算法看作是搜索策略。因此,应用遗传算法在数据库中进行搜索,对随机产生的一组分类规则进行进化,直到数据库能被该组分类规则覆盖,从而挖掘出隐含在数据库中的分类规则。应用遗传算法进行数据分类,首先要对实际问题进行编码;然后定义遗传算法的适应度函数,由于算法用于规则归纳,因此,适应度函数由规则覆盖的正例和反例来定义。1978年Holland实现了第一个基于遗传算法的机器学习系统CS-1(cognitive system level one,其后又提出了桶队(Bucket Brigade算法。1981

21、年Smith实现了与CS-1有重大区别的分类器LS-1,以此为基础,人们又提出了基于遗传算法的分类系统,如GCLS(genetic classifier learning system等算法。3.3模糊逻辑模糊数学是研究模糊现象的数学;模糊数学最基本概念是隶属函数,即以一个值域在0,1之间的隶属函数来描述论域中对象属于某一个类别的程度,并以此为基础确定模糊集的运算法则、性质、分解和扩展原理、算子、模糊度、模糊集的近似程度等度量概念和算法。分类操作离不开向量相似程度的计算,而模糊分类操作也需要向量模糊相似系数的计算。在模糊分类方法中,首先要建立模糊相似矩阵,表示对象的模糊相似程度其元素称为模糊相

22、似系数,其确定方法主要有:数量积法、夹角余弦法、相关系数法、最大最小法、算术平均最小法、几何平均最小法、绝对值指数法、指数相似系数法、绝对值倒数法、绝对值减数法、参数法、贴近度法等。模糊分类方法可以很好地处理客观事务类别属性的不明确性,主要包括8传递闭包法、最大树法、编网法、基于摄动的模糊方法等;但人们更多地将模糊方法和其他分类算法结合起来,既有与传统分类算法,如模糊决策树、模糊关联规则挖掘等的结合,也有与软计算在内其他方法,如模糊神经网络等的结合。3.4神经网络神经网络是分类技术中重要方法之一,其优势在于:神经网络可以任意精度逼近任意函数;神经网络方法本身属于非线形模型,能够适应各种复杂的数

23、据关系;神经网络具备很强的学习能力,使它能够比很多分类算法更好地适应数据空间的变化;神经网络借鉴人脑的物理结构和机理,能够模拟人脑的某些功能,具备“智能”的特点。基于神经网络的分类方法很多,基本是按照神经网络模型的不同而进行区分,用于数据分类常见的神经网络模型包括:BP神经网络、RBF神经网络、自组织特征映射神经网络、学习矢量化神经网络。目前神经网络分类算法研究较多集中在以BP为代表的神经网络上。4结语分类算法是数据挖掘中的核心和基础技术之一,本文对(下转第108页71108(上接第71页基于传统算法和软计算的常见数据分类算法进行了综述;从而便于研究者对已有算法进行改进和设计新的分类算法。未来

24、数据分类算法的研究则更多地集中在智能分类领域,如基于软计算的分类算法以及免疫算法、分形编码、蚁群优化等智能算法的分类研究上。参考文献:1Liu B, Hsu W. Integrating classification and association rule mining?/Agrawal R, Stdorz P, Piatetsky G. Proc of 4th Int.Conf. on Knowledge Discovery and Data Mining. Menlo Park:AAAI Press, 1998:80-86.2Kuncheva L I. Editing for the k

25、-nearest neighbors rule by a genetic. Pattern Recognition Letters, 1995,16:809-814.3Mehta M, Agraal R. SLIQ: A fast scalable classifier for data mining?/Peter M G, Apers M B, Georges G. Proc of 5th Int.Conf. on Extending Database Technology: Lecture Notes in Computer Science, Springer: Springer Pres

26、s, 1996:18-33.4Shafer J C, Agrawal R. SPRINT: A scalable parallel classifier for data mining?/Vigayaraman T M, Buchmann A P , Mohan C.Proc of 22nd Int. Conf. on very large databases. San Fransrsco:Morgan Kaufmann Publishers Inc., 1996:544-555.59Michie D, Spiegelhalter D J. Machine Learning, Neural an Stastical Classification. London: Ellis Horwood Press,