关联分类算法的研究

1、Hebei University关联分类算法的研究赵东垒符号学习研究组Hebei Universityn课题研究目的n国际研究现状n主要研究内容和创新点n研究过程可能遇到的困难及解决方案n总结n参考文献Hebei Universityn分类问题是通过分析给定的一个带有类别标识的训练数据集，建立一个分类器，然后预测那些未知类别的数据对象n关联分类算法n数据集中属性的取值是符号型的n课题研究目的就是改进、优化关联分类算法q提高关联分类算法的分类精度q提高关联分类算法的效率q提高关联分类算法的可理解性课题研究目的Hebei University国际研究现状n1998年Liu等提出了基于类关联规则的分

2、类算法CBA。n1999年Dong等提出显露模式分类法CAEP。n2000年Wang等结合关联规则分类和决策树分类提出关联决策树。n2001年Li等提出基于多条关联规则的分类算法CMAR。n2003年Yin等提出预测型关联规则的分类算法CPAR。CPAR采用贪婪方法从数据集中挖掘出较小规则集。n2004年Antonie提出正负关联规则的分类算法。n2005年Wang提出HARMONY，它直接挖掘覆盖样例置信度最高的规则。n2006年Adriano Veloso等提出的lazy关联分类。n2006，2007年Arunasalam提出了适用与类不平衡数据上的关联分类。Hebei Universit

3、y基本概念n关联规则：A=BnIf A then Cn定义1 规则的支持度q数据集中匹配规则前件A, 并且满足类别属性取值为C的样例的个数. n定义2 规则的置信度 q规则的支持度与数据集中匹配规则前件A的样例的个数的比值. &ACAHebei University主要研究内容和创新点n关联分类算法的优点q分类精度高q适应性强n关联分类算法存在的问题q算法的执行效率更高效的挖掘方法q剪枝的质量和效率新的规则序关系q分类器的可理解性交叠现象对分类起的影响Hebei University已完成的工作n算法的执行效率q在构造带类别标识的FP-tree时，在每个节点注册相应类别信息。q扩展TD

4、-FP-Growth算法，使它能直接挖掘满足最小支持度和最小置信度的类关联规则。q优点：两次扫描数据库，不用重复建立条件FP-tree。减少了内存消耗，提高了运行效率。Hebei University带类别标识FP-tree的构造Hebei Universityn剪枝的质量和效率q关联分类中最敏感的问题n如何评价类关联规则的质量n如何从大量的关联规则中选择有效的规则构造分类器Hebei University如何评价类关联规则的质量n经典关联分类规则序关系的定义n给定规则Ri，Rj。 Ri优于Rj，当且仅当满足以下条件之一: qRi具有比Rj更高的置信度qRi和Rj具有相同的置信度， Ri具有比

5、Rj更高的支持度qRi和Rj具有相同的置信度和支持度， Ri具有比Rj更少的规则项Hebei Universityn经典关联分类规则序关系的缺点q其本质是采用置信度，支持度，规则项数目评价顺序。过分强调了置信度，这样在最后构造的分类器中，使得有些规则置信度很高而支持度不高，造成过度拟合。n综合考虑置信度和支持度。&( )ACPredAcc RAHebei UniversitynR1: sup(R1) = 100, conf(R1) = 98%nR2: sup(R2) = 10, conf(R2) = 100%n经典序关系 R1 R2nR1有较好的泛化能力，R2可能过度拟合数据。Hebe

6、i University15个UCI数据库测试结果Hebei University医疗图像数据库测试结果Hebei University以后要完成的工作n完善规则评价函数q引入规则的项数q考虑类别不平衡情况n分类器中规则交叠对分类精度的影响Hebei University分类器的可理解性n关联分类构造分类器的方法q挖掘满足置信度和支持度阈值要求的类关联规则q将规则按定义的序关系排序，基于数据覆盖来选择规则n分类器的特点q数据集中每条记录都被一条评价值最高的规则覆盖q分类器中的规则在训练集中存在相互交叠的现象q规则的数目较多Hebei University交叠现象怎样产生的1.10.20.30.

7、40R1:20, 100%R4:20, 85%R2:20, 95%R3:20, 90%Hebei University交叠问题解决方法n每选择一条规则后，更新剩余规则的置信度，支持度。n难度q更新的计算量大q采用更新，是否比以前的方法有效Hebei University研究过程可能遇到的困难及解决方案n规则评价函数的确定q不同数据库的影响n交叠现象对分类精度的影响q选择规则后，更新置信度和支持度q比较不同交叠情况的分类精度Hebei University总结n针对关联分类算法存在的问题q算法的执行效率q剪枝的质量和效率q分类器的可理解性Hebei University参考文献1 B. Liu,

8、 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.

9、 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. Ramamo

10、hanarao 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,

11、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

12、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 Conference on Computer Systems and Applications. pp.1

13、-7. Cairo, Egypt. Hebei University9 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

14、 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

15、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 Fra

16、nsisco, 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 Classific

17、ation 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

18、 Issues in Data Mining and Knowledge Discovery (DMKD-04), pp 64-69, Paris, France, June 2004 Hebei University17 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 Eva

19、luation 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), Bosto

20、n, 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