关联分类算法的研究.ppt

Hebei University,关联分类算法的研究,赵东垒,符号学习研究组,Hebei University,课题研究目的国际研究现状主要研究内容和创新点研究过程可能遇到的困难及解决方案总结参考文献,Hebei University,分类问题是通过分析给定的一个带有类别标识的训练数据集，建立一个分类器，然后预测那些未知类别的数据对象关联分类算法数据集中属性的取值是符号型的课题研究目的就是改进、优化关联分类算法提高关联分类算法的分类精度提高关联分类算法的效率提高关联分类算法的可理解性,课题研究目的,Hebei University,国际研究现状,1998年Liu等提出了基于类关联规则的分类算法CBA。1999年Dong等提出显露模式分类法CAEP。2000年Wang等结合关联规则分类和决策树分类提出关联决策树。2001年Li等提出基于多条关联规则的分类算法CMAR。2003年Yin等提出预测型关联规则的分类算法CPAR。CPAR采用贪婪方法从数据集中挖掘出较小规则集。2004年Antonie提出正负关联规则的分类算法。2005年Wang提出HARMONY，它直接挖掘覆盖样例置信度最高的规则。2006年Adriano Veloso等提出的lazy关联分类。2006，2007年Arunasalam提出了适用与类不平衡数据上的关联分类。,Hebei University,基本概念,关联规则：A=BIf A then C定义1 规则的支持度数据集中匹配规则前件A,并且满足类别属性取值为C的样例的个数.定义2 规则的置信度 规则的支持度与数据集中匹配规则前件A的样例的个数的比值.,Hebei University,主要研究内容和创新点,关联分类算法的优点分类精度高适应性强关联分类算法存在的问题算法的执行效率更高效的挖掘方法剪枝的质量和效率新的规则序关系分类器的可理解性交叠现象对分类起的影响,Hebei University,已完成的工作,算法的执行效率在构造带类别标识的FP-tree时，在每个节点注册相应类别信息。扩展TD-FP-Growth算法，使它能直接挖掘满足最小支持度和最小置信度的类关联规则。优点：两次扫描数据库，不用重复建立条件FP-tree。减少了内存消耗，提高了运行效率。,Hebei University,带类别标识FP-tree的构造,Hebei University,剪枝的质量和效率关联分类中最敏感的问题如何评价类关联规则的质量如何从大量的关联规则中选择有效的规则构造分类器,Hebei University,如何评价类关联规则的质量,经典关联分类规则序关系的定义给定规则Ri，Rj。Ri优于Rj，当且仅当满足以下条件之一:Ri具有比Rj更高的置信度Ri和Rj具有相同的置信度，Ri具有比Rj更高的支持度Ri和Rj具有相同的置信度和支持度，Ri具有比Rj更少的规则项,Hebei University,经典关联分类规则序关系的缺点其本质是采用置信度，支持度，规则项数目评价顺序。过分强调了置信度，这样在最后构造的分类器中，使得有些规则置信度很高而支持度不高，造成过度拟合。综合考虑置信度和支持度。,Hebei University,R1:sup(R1)=100,conf(R1)=98%R2:sup(R2)=10,conf(R2)=100%经典序关系 R1 R2R1有较好的泛化能力，R2可能过度拟合数据。,Hebei University,15个UCI数据库测试结果,Hebei University,医疗图像数据库测试结果,Hebei University,以后要完成的工作,完善规则评价函数引入规则的项数考虑类别不平衡情况分类器中规则交叠对分类精度的影响,Hebei University,分类器的可理解性,关联分类构造分类器的方法挖掘满足置信度和支持度阈值要求的类关联规则将规则按定义的序关系排序，基于数据覆盖来选择规则分类器的特点数据集中每条记录都被一条评价值最高的规则覆盖分类器中的规则在训练集中存在相互交叠的现象规则的数目较多,Hebei University,交叠现象怎样产生的,R1:20,100%,R4:20,85%,R2:20,95%,R3:20,90%,Hebei University,交叠问题解决方法,每选择一条规则后，更新剩余规则的置信度，支持度。难度更新的计算量大采用更新，是否比以前的方法有效,Hebei University,研究过程可能遇到的困难及解决方案,规则评价函数的确定不同数据库的影响交叠现象对分类精度的影响选择规则后，更新置信度和支持度比较不同交叠情况的分类精度,Hebei University,总结,针对关联分类算法存在的问题算法的执行效率剪枝的质量和效率分类器的可理解性,Hebei University,参考文献,1 B.Liu,W.Hsu and Y.Ma.Integrating Classification and Association Rule Mining.In Proc.of 1998 Int.Conf.on Knowledge Discovery and Data Mining(KDD98),pp.80-86,New York,Aug 1998.2 J.Han,J.Pei and Y.Yin.Mining Frequent Patterns without Candidate Generation.In Proc.of the ACM-SIGMOD 2000 Int.Conf.on Management of Data(SIGMOD00),pp.112,Dallas,May 2000.3 W.Li,J.Han and J.Pei.CMAR:Accurate and Efficient Classification Based on Multiple Class-Association Rules.In Proc.of 2001 IEEE Int.Conf.on Data Mining(ICDM01),pp.369-376,San Jose CA,Nov 2001.4 J.Li,G.Dong,K.Ramamohanarao and L.Wong.DeEPs:A New Instance-Based Lazy Discovery and Classification System.Machine Learning.54,pp.99-124,2004.5 Adriano Veloso,Wagner Meira Jr,and Mohammed J.Zaki.Lazy Association Classification.In Proc.of 2006 IEEE Int.Conf.on Data Mining(ICDM06),pp.645-654,Hong Kong,Oct 2006.6 Maria-Luiza Antonie,Osmar R.Zaiane,and Robert C.Holte.Learning to Use a Learned Model:A Two-Stage Approach to Classification.In Proc.of 2006 IEEE Int.Conf.on Data Mining(ICDM06),pp.645-654,Hong Kong,Oct 2006.7 Abdelaziz Berrado,George C.Runger.Using Metarules to Organize and Group Discovered Association Rules.Data Mining and Knowledge Discover.14:409-431,2007.8 F.Thabtah,P.Cowling,and Y.Peng.MCAR:Multi-class Classification based on Association Rule Approach.In Proceeding of the 3rd IEEE International Conferenceon Computer Systems and Applications.pp.1-7.Cairo,Egypt.,Hebei University,9 O.R.Zaiane and M.-L.Antonie.On pruning and tuning rules for associative classifiers.In Proc.of Intl Conf.on Knowledge-Based Intelligence Information&Engineering Systems(KES05),pp.966-973,2005.10Adriano Veloso,Wagner Meira Jr.:Rule Generation and Rule Selection Techniques for Cost-Sensitive Associative Classification.In SBBD 2005.pp.295-309,2005.11J.Wang and G.Karypis.HARMONY:Efficiently Mining the Best Rules for Classification.In Proc.of 2006 SIAM Int.Conf.on Data Mining(SDM05),California,USA,April 2005.12Bing Liu,Yiming Ma,C-K Wong,Classification Using Association Rules:Weaknesses and Enhancements.In Vipin Kumar,et al,(eds),Data mining for scientific applications,200113 X.Yin and J.Han.CPAR:Classification based on Predictive Association Rules.In Proc.2003 SIAM Int.Conf.on Data Mining(SDM03),San Fransisco,CA,May 2003.14 Frans Coenen and Paul Leng.The Effect of Threshold Values on Association Rule Based Classification Accuracy.Journal of Data and Knowledge Engineering,Vol.60,Num.2,pp345-360,February 2007 15 Frans Coenen,Paul Leng,and Lu Zhang.Threshold Tuning for Improved Classification Association Rule Mining.In Proc.of 6th Pacific Area Conference on Knowledge Discovery and Data Mining(PAKDD05),pp.334-340,Taipei,May 3-8 2002 16 Maria-Luiza Antonie and Osmar R.Zaiane,An Associative Classifier based on Positive and Negative Rules,In 9th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery(DMKD-04),pp 64-69,Paris,France,June 2004,Hebei University,17 Yanbo J.Wang,Qin Xin and Frans Coenen.A Novel Rule Ordering Approach in Classification Association Rule Mining.In Proc.MLDM2007,pp339-348.2007.18 Frans Coenen and Paul Leng.An Evaluation of Approaches to Classification Rule Selection.In Proc.of 2004 IEEE Int.Conf.on Data Mining(ICDM04),pp359-362,2004 19 K.Wang,S.Zhou,and Y.He.Growing decision tree on support-less association rules.In Proc.Of 2000 Int.Conf.on Knowledge Discovery and Data Mining(KDD00),Boston,MA,Aug.2000.20Frans Coenen and Paul Leng.Obtaining Best Parameter Values for Accurate Classification.In Proc.of 2005 IEEE Int.Conf.on Data Mining(ICDM05),pp.597-600,200521 D.Meretakis and B.Wuthrich.Extending Nave Bayes Classifiers Using Long Itemsets.In Proc.1999 Int.Conf.on Knowledge Discovery and Data Mining(KDD99),pages 165-174,San Diego,CA,Aug.1999.22 Bing Liu,Yiming Ma,and Ching Kian Wong.Improving an Association Rule Based Classifier.In Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery,Pages:504 509,2000 23 Bavani Arunasalam and Sanjay Chawla.CCCS:A Top-down Associative Classifier for Imbalanced Class Distribution.In Proc.Of 2006 Int.Conf.on Knowledge Discovery and Data Mining(KDD06),pp.517-522.200624 Florian Verhein and Sanjay Chawla.Using Significant,Positively Associated and Relatively Class Correlated Rules for Associative Classification of Imbalanced Datasets,In Proc.of 2007 IEEE Int.Conf.on Data Mining(ICDM07),2007.,Hebei University,问题？谢谢！,