关联分类算法研究

关联分类算法研究HebeiUniversity课题研究目的国际研究现状主要研究内容和创新点研究过程可能遇到的困难及解决方案总结参考文献HebeiUniversity分类问题是通过分析给定的一个带有类别标识的训练数据集，建立一个分类器，然后预测那些未知类别的数据对象关联分类算法数据集中属性的取值是符号型的课题研究目的就是改进、优化关联分类算法提高关联分类算法的分类精度提高关联分类算法的效率提高关联分类算法的可理解性课题研究目的HebeiUniversity国际研究现状1998年Liu等提出了基于类关联规则的分类算法CBA。1999年Dong等提出显露模式分类法CAEP。2000年Wang等结合关联规则分类和决策树分类提出关联决策树。2001年Li等提出基于多条关联规则的分类算法CMAR。2003年Yin等提出预测型关联规则的分类算法CPAR。CPAR采用贪婪方法从数据集中挖掘出较小规则集。2004年Antonie提出正负关联规则的分类算法。2005年Wang提出HARMONY，它直接挖掘覆盖样例置信度最高的规则。2006年AdrianoVeloso等提出的lazy关联分类。2006，2007年Arunasalam提出了适用与类不平衡数据上的关联分类。HebeiUniversity基本概念关联规则：A=>BIfAthenC定义1规则的支持度数据集中匹配规则前件A,并且满足类别属性取值为C的样例的个数.定义2规则的置信度规则的支持度与数据集中匹配规则前件A的样例的个数的比值.HebeiUniversity主要研究内容和创新点关联分类算法的优点分类精度高适应性强关联分类算法存在的问题算法的执行效率 更高效的挖掘方法剪枝的质量和效率 新的规则序关系分类器的可理解性 交叠现象对分类起的影响HebeiUniversity已完成的工作算法的执行效率在构造带类别标识的FP-tree时，在每个节点注册相应类别信息。扩展TD-FP-Growth算法，使它能直接挖掘满足最小支持度和最小置信度的类关联规则。优点：两次扫描数据库，不用重复建立条件FP-tree。减少了内存消耗，提高了运行效率。HebeiUniversity带类别标识FP-tree的构造HebeiUniversity剪枝的质量和效率关联分类中最敏感的问题如何评价类关联规则的质量如何从大量的关联规则中选择有效的规则构造分类器HebeiUniversity如何评价类关联规则的质量经典关联分类规则序关系的定义给定规则Ri，Rj。Ri优于Rj，当且仅当满足以下条件之一:Ri具有比Rj更高的置信度Ri和Rj具有相同的置信度，Ri具有比Rj更高的支持度Ri和Rj具有相同的置信度和支持度，Ri具有比Rj更少的规则项HebeiUniversity经典关联分类规则序关系的缺点其本质是采用置信度，支持度，规则项数目评价顺序。过分强调了置信度，这样在最后构造的分类器中，使得有些规则置信度很高而支持度不高，造成过度拟合。综合考虑置信度和支持度。HebeiUniversityR1:sup(R1)=100,conf(R1)=98%R2:sup(R2)=10,conf(R2)=100%经典序关系R1<R2R1>R2R1有较好的泛化能力，R2可能过度拟合数据。HebeiUniversity15个UCI数据库测试结果HebeiUniversity医疗图像数据库测试结果HebeiUniversity以后要完成的工作完善规则评价函数引入规则的项数考虑类别不平衡情况分类器中规则交叠对分类精度的影响HebeiUniversity分类器的可理解性关联分类构造分类器的方法挖掘满足置信度和支持度阈值要求的类关联规则将规则按定义的序关系排序，基于数据覆盖来选择规则分类器的特点数据集中每条记录都被一条评价值最高的规则覆盖分类器中的规则在训练集中存在相互交叠的现象规则的数目较多HebeiUniversity交叠现象怎样产生的1..10..20..30..40R1:20,100%R4:20,85%R2:20,95%R3:20,90%HebeiUniversity交叠问题解决方法每选择一条规则后，更新剩余规则的置信度，支持度。难度更新的计算量大采用更新，是否比以前的方法有效HebeiUniversity研究过程可能遇到的困难及解决方案规则评价函数的确定不同数据库的影响交叠现象对分类精度的影响选择规则后，更新置信度和支持度比较不同交叠情况的分类精度HebeiUniversity总结针对关联分类算法存在的问题算法的执行效率剪枝的质量和效率分类器的可理解性HebeiUniversity参考文献[1]B.Liu,W.HsuandY.Ma.IntegratingClassificationandAssociationRuleMining.InProc.of1998Int.Conf.onKnowledgeDiscoveryandDataMining(KDD'98),pp.80-86,NewYork,Aug1998.[2]J.Han,J.PeiandY.Yin.MiningFrequentPatternswithoutCandidateGeneration.InProc.oftheACM-SIGMOD2000Int.Conf.onManagementofData(SIGMOD’00),pp.1−12,Dallas,May2000.[3]W.Li,J.HanandJ.Pei.CMAR:AccurateandEfficientClassificationBasedonMultipleClass-AssociationRules.InProc.of2001IEEEInt.Conf.onDataMining(ICDM'01),pp.369-376,SanJoseCA,Nov2001.[4]J.Li,G.Dong,K.RamamohanaraoandL.Wong.DeEPs:ANewInstance-BasedLazyDiscoveryandClassificationSystem.MachineLearning.54,pp.99-124,2004.[5]AdrianoVeloso,WagnerMeiraJr,andMohammedJ.Zaki.LazyAssociationClassification.InProc.of2006IEEEInt.Conf.onDataMining(ICDM'06),pp.645-654,HongKong,Oct2006.[6]Maria-LuizaAntonie,OsmarR.Zaiane,andRobertC.Holte.LearningtoUseaLearnedModel:ATwo-StageApproachtoClassification.InProc.of2006IEEEInt.Conf.onDataMining(ICDM'06),pp.645-654,HongKong,Oct2006.[7]AbdelazizBerrado,GeorgeC.Runger.UsingMetarulestoOrganizeandGroupDiscoveredAssociationRules.DataMiningandKnowledgeDiscover.14:409-431,2007.[8]F.Thabtah,P.Cowling,andY.Peng.MCAR:Multi-classClassificationbasedonAssociationRuleApproach.InProceedingofthe3rdIEEEInternationalConference

onComputerSystemsandApplications.pp.1-7.Cairo,Egypt.HebeiUniversity[17]YanboJ.Wang,QinXinandFransCoenen.ANovelRuleOrderingApproachinClassificationAssociationRuleMining.InProc.MLDM'2007,pp339-348.2007.[18]FransCoenenandPaulLeng.AnEvaluationofApproachestoClassificationRuleSelection.InProc.of2004IEEEInt.Conf.onDataMining(ICDM'04),pp359-362,2004[19]K.Wang,S.Zhou,andY.He.Growingdecisiontreeonsupport-lessassociationrules.InProc.Of2000Int.Conf.onKnowledgeDiscoveryandDataMining(KDD'00),Boston,MA,Aug.2000.[20]FransCoenenandPaulLeng.ObtainingBestParameterValuesforAccurateClassification.InProc.of2005IEEEInt.Conf.onDataMining(ICDM'05),pp.597-600,2005[21]D.MeretakisandB.Wuthrich.ExtendingNaïveBayesClassifiersUsingLongItemsets.InProc.1999Int.Conf.onKnowledgeDiscoveryandDataMining(KDD'99),pages165-174,SanDiego,CA,Aug.1999.[22]BingLiu,YimingMa,andChingKianWong.ImprovinganAssociationRuleBasedClassifier.InProceedingsofthe4thEuropeanConferenceonPrinciplesofDataMiningandKnowledgeDiscovery,

Pages:504–509,2000[23]BavaniArunasalamandSanjayChawla.CCCS:ATop-downAssociativeClassifierforImbalancedClassDistribution.InProc.Of2006Int.Conf.onKnowledgeDiscoveryandDataMining(KDD'06),pp.517-522.2