关联分类算法的研究

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,关联分类算法的研究,符号学习研究组,课题研究目的,国际研究现状,主要研究内容和创新点,研究过程可能遇到的困难及解决方案,总结,参考文献,2,分类问题是通过分析给定的一个带有类别标识的训练数据集，建立一个分类器，然后预测那些未知类别的数据对象,关联分类算法,数据集中属性的取值是符号型的,课题研究目的就是改进、优化关联分类算法,提高关联分类算法的分类精度,提高关联分类算法的效率,提高关联分类算法的可理解性,课题研究目的,3,国际研究现状,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,提出了适用与类不平衡数据上的关联分类。,4,基本概念,关联规则：,A=B,If A then C,定义,1,规则的支持度,数据集中匹配规则前件,A,并且满足类别属性取值为,C,的样例的个数,.,定义,2,规则的置信度,规则的支持度与数据集中匹配规则前件,A,的样例的个数的比值,.,5,主要研究内容和创新点,关联分类算法的优点,分类精度高,适应性强,关联分类算法存在的问题,算法的执行效率,更高效的挖掘方法,剪枝的质量和效率,新的规则序关系,分类器的可理解性,交叠现象对分类起的影响,6,已完成的工作,算法的执行效率,在构造带类别标识的,FP-tree,时，在每个节点注册相应类别信息。,扩展,TD-FP-Growth,算法，使它能直接挖掘满足最小支持度和最小置信度的类关联规则。,优点：两次扫描数据库，不用重复建立条件,FP-tree,。减少了内存消耗，提高了运行效率。,7,带类别标识,FP-tree,的,构造,8,剪枝的质量和效率,关联分类中最敏感的问题,如何评价类关联规则的质量,如何从大量的关联规则中选择有效的规则构造分类器,9,如何评价类关联规则的质量,经典关联分类规则序关系的定义,给定规则,Ri,，,Rj,。,Ri,优于,Rj,，,当且仅当满足以下条件之一,:,Ri,具有比,Rj,更高的置信度,Ri,和,Rj,具有相同的置信度，,Ri,具有比,Rj,更高的支持度,Ri,和,Rj,具有相同的置信度和支持度，,Ri,具有比,Rj,更少的规则项,10,经典关联分类规则序关系的缺点,其本质是采用置信度，支持度，规则项数目评价顺序。过分强调了置信度，这样在最后构造的分类器中，使得有些规则置信度很高而支持度不高，造成过度拟合。,综合考虑置信度和支持度。,11,R1: sup(R1) = 100, conf(R1) = 98%,R2: sup(R2) = 10, conf(R2) = 100%,经典序关系,R1 R2,R1,有较好的泛化能力，,R2,可能过度拟合数据。,12,15个UCI数据库测试结果,13,医疗图像数据库测试结果,14,以后要完成的工作,完善规则评价函数,引入规则的项数,考虑类别不平衡情况,分类器中规则交叠对分类精度的影响,15,分类器的可理解性,关联分类构造分类器的方法,挖掘满足置信度和支持度阈值要求的类关联规则,将规则按定义的序关系排序，基于数据覆盖来选择规则,分类器的特点,数据集中每条记录都被一条评价值最高的规则覆盖,分类器中的规则在训练集中存在相互交叠的现象,规则的数目较多,16,交叠现象怎样产生的,1,.,10,.,20,.,30,.,40,R1:20, 100%,R4:20, 85%,R2:20, 95%,R3:20, 90%,17,交叠问题解决方法,每选择一条规则后，更新剩余规则的置信度，支持度。,难度,更新的计算量大,采用更新，是否比以前的方法有效,18,研究过程可能遇到的困难及解决方案,规则评价函数的确定,不同数据库的影响,交叠现象对分类精度的影响,选择规则后，更新置信度和支持度,比较不同交叠情况的分类精度,19,总结,针对关联分类算法存在的问题,算法的执行效率,剪枝的质量和效率,分类器的可理解性,20,参考文献,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.,Co,wling, 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.,21,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, 2001,13 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,22,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, 2005,21 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. 2006,24,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.,23,问题？谢谢！,24,