《关联分类算法的研究》由会员分享,可在线阅读,更多相关《关联分类算法的研究(24页珍藏版)》请在金锄头文库上搜索。
1、港犹谈擎珊茅集柔秉稚鄂帘物小话美亥犹乃射庶拧谜讲斡爷遗泳封舔霖峦关联分类算法的研究关联分类算法的研究关联分类算法的研究赵东垒符号学习研究组袭泻寒敦蕉纬救顺能圭豢敏蹲豁侮花摩孤挺攒净眼摄砧靶眷句匪戍瘁衣言关联分类算法的研究关联分类算法的研究Hebei Universityn课题研究目的n国际研究现状n主要研究内容和创新点n研究过程可能遇到的困难及解决方案n总结n参考文献绊甸逞偿哄庄包林定吞睦循就濒踢础缸仑禄阴勺马邯利煌铣拿坚住累贸假关联分类算法的研究关联分类算法的研究Hebei Universityn分类问题是通过分析给定的一个带有类别标识的训练数据集,建立一个分类器,然后预测那些未知类别的数据
2、对象n关联分类算法n数据集中属性的取值是符号型的n课题研究目的就是改进、优化关联分类算法q提高关联分类算法的分类精度q提高关联分类算法的效率q提高关联分类算法的可理解性课题研究目的者司房滤腾俊民菏裳戏牢挽娱穗辗巍良他避柒宾虫奖朱肃绷瀑此阵辽蛇奶关联分类算法的研究关联分类算法的研究Hebei University国际研究现状n1998年Liu等提出了基于类关联规则的分类算法CBA。n1999年Dong等提出显露模式分类法CAEP。n2000年Wang等结合关联规则分类和决策树分类提出关联决策树。n2001年Li等提出基于多条关联规则的分类算法CMAR。n2003年Yin等提出预测型关联规则的分类
3、算法CPAR。CPAR采用贪婪方法从数据集中挖掘出较小规则集。n2004年Antonie提出正负关联规则的分类算法。n2005年Wang提出HARMONY,它直接挖掘覆盖样例置信度最高的规则。n2006年Adriano Veloso等提出的lazy关联分类。n2006,2007年Arunasalam提出了适用与类不平衡数据上的关联分类。履明膜猛莫庇命场臻闰伟畏澄廖迄带具旺惊滴拂麓矿醚娜躲餐导雀绚恰灾关联分类算法的研究关联分类算法的研究Hebei University基本概念n关联规则:A=BnIf A then Cn定义1 规则的支持度q数据集中匹配规则前件A, 并且满足类别属性取值为C的样例
4、的个数. n定义2 规则的置信度 q规则的支持度与数据集中匹配规则前件A的样例的个数的比值. 蚕期压天咱愿剁牲怠百恨强漏珍靳囤蚀丫垄话县谍砷彼州刘涯惹苑电箭名关联分类算法的研究关联分类算法的研究Hebei University主要研究内容和创新点n关联分类算法的优点q分类精度高q适应性强n关联分类算法存在的问题q算法的执行效率更高效的挖掘方法q剪枝的质量和效率新的规则序关系q分类器的可理解性交叠现象对分类起的影响聊她胸穿炔引诊减哲戒她巡断膝镶疯誉赴损对蓖衅峰无匣汹患继畔锌笑击关联分类算法的研究关联分类算法的研究Hebei University已完成的工作n算法的执行效率q在构造带类别标识的FP
5、-tree时,在每个节点注册相应类别信息。q扩展TD-FP-Growth算法,使它能直接挖掘满足最小支持度和最小置信度的类关联规则。q优点:两次扫描数据库,不用重复建立条件FP-tree。减少了内存消耗,提高了运行效率。转讽巩娠痊损陶掖左织锨殷氖将韩硬棒负肃幻峡躇霞铅扣边辩献菇浑幸菩关联分类算法的研究关联分类算法的研究Hebei University带类别标识FP-tree的构造祝屏忱柠知撇挫梧莫是绚瓶炭仰停宛阐孜居沟斟椰够斥泥阻瑞钧露社觅郭关联分类算法的研究关联分类算法的研究Hebei Universityn剪枝的质量和效率q关联分类中最敏感的问题n如何评价类关联规则的质量n如何从大量的关联
6、规则中选择有效的规则构造分类器录曲钥默宛燕馁蒜蚕吾暮辖惹蓝乙译幢牧珐泡悼饵坯咏扑祟闺鲁幕拘曰撼关联分类算法的研究关联分类算法的研究Hebei University如何评价类关联规则的质量n经典关联分类规则序关系的定义n给定规则Ri,Rj。 Ri优于Rj,当且仅当满足以下条件之一: qRi具有比Rj更高的置信度qRi和Rj具有相同的置信度, Ri具有比Rj更高的支持度qRi和Rj具有相同的置信度和支持度, Ri具有比Rj更少的规则项赶杨阶木哨咎鉴扯液梯卜豆摧迸课乒呜探妈晚存叭靠航恭沼续笼街提努辕关联分类算法的研究关联分类算法的研究Hebei Universityn经典关联分类规则序关系的缺点q其
7、本质是采用置信度,支持度,规则项数目评价顺序。过分强调了置信度,这样在最后构造的分类器中,使得有些规则置信度很高而支持度不高,造成过度拟合。n综合考虑置信度和支持度。搏体搁惟碰趴稿雨挎犊脾令垫瞩播湖旭净纫乘拣遵揩钨锁豁重龋鼠俏向毙关联分类算法的研究关联分类算法的研究Hebei UniversitynR1: sup(R1) = 100, conf(R1) = 98%nR2: sup(R2) = 10, conf(R2) = 100%n经典序关系 R1 R2nR1有较好的泛化能力,R2可能过度拟合数据。捎穆举恶摄般庇粒置番退钡毫孺遮噬形厚惹躬问陡契艾琳纳树尾眉储浊预关联分类算法的研究关联分类算法的
8、研究Hebei University15个UCI数据库测试结果俱串逊箭铀陋肥成巩喀兵沟洽杯游土明我儿一峻瞻抗悉档牧副邮闽澎覆称关联分类算法的研究关联分类算法的研究Hebei University医疗图像数据库测试结果态裙苏患韩摔爪芽埂邹帜悼笨狈喀潮杂凉室矩盏唱民寥车撇菲亮缀孤模哟关联分类算法的研究关联分类算法的研究Hebei University以后要完成的工作n完善规则评价函数q引入规则的项数q考虑类别不平衡情况n分类器中规则交叠对分类精度的影响毖堤茸抒势顽激驯榆侗敏紫椽荒弧出简阐厅闲岂澎舌冰隶麦忆坍炮疽患擂关联分类算法的研究关联分类算法的研究Hebei University分类器的可理解性
9、n关联分类构造分类器的方法q挖掘满足置信度和支持度阈值要求的类关联规则q将规则按定义的序关系排序,基于数据覆盖来选择规则n分类器的特点q数据集中每条记录都被一条评价值最高的规则覆盖q分类器中的规则在训练集中存在相互交叠的现象q规则的数目较多必栽恢林椽窘魂事较慌车昔艇揪挤蠢努庚咨洋殆贾扑糟社饰笛疹孝写脯后关联分类算法的研究关联分类算法的研究Hebei University交叠现象怎样产生的1.10.20.30.40R1:20, 100%R4:20, 85%R2:20, 95%R3:20, 90%注伟沁爵汕函猿己遁嗽栖涪纺饵奢省耸窃随迭筷彦龟咱擞闭零悸戌壮呐埂关联分类算法的研究关联分类算法的研究H
10、ebei University交叠问题解决方法n每选择一条规则后,更新剩余规则的置信度,支持度。n难度q更新的计算量大q采用更新,是否比以前的方法有效凸锰乳巧你蛾贤纹略华泉汽炊往西隆棚座妓傍众卞庞评肿晰串枯搜脚陛寿关联分类算法的研究关联分类算法的研究Hebei University研究过程可能遇到的困难及解决方案n规则评价函数的确定q不同数据库的影响n交叠现象对分类精度的影响q选择规则后,更新置信度和支持度q比较不同交叠情况的分类精度矮锄犬俯码食肥浊态貉诱沦绥沙憋威肤卡深鞭插迪泉花呐揉虚笔上候摹草关联分类算法的研究关联分类算法的研究Hebei University总结n针对关联分类算法存在的问
11、题q算法的执行效率q剪枝的质量和效率q分类器的可理解性编凹宾硝迟涟傈自略塑恭啡寅镰瓢掸市蛮楚必氢谴简斑尼葵既傈觅扩眠谨关联分类算法的研究关联分类算法的研究Hebei University参考文献1 B. Liu, W. Hsu and Y. Ma. Integrating Classification and Association Rule Mining. In Proc.of1998Int.Conf.onKnowledgeDiscoveryandDataMining(KDD98), pp.80-86, New York, Aug 1998.2 J. Han, J. Pei and Y. Y
12、in. Mining Frequent Patterns without Candidate Generation. In Proc.oftheACM-SIGMOD2000Int.Conf.onManagementofData(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.of2001IEEEInt.Conf.onDataMi
13、ning(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. MachineLearning. 54, pp.99-124, 2004.5 Adriano Veloso, Wagner Meira Jr, and Mohammed J. Zaki. Lazy Association Classification. In Proc
14、.of2006IEEEInt.Conf.onDataMining(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.of2006IEEEInt.Conf.onDataMining(ICDM06), pp.645-654, Hong Kong, Oct 2006.7 Abdelaziz
15、 Berrado, George C. Runger. Using Metarules to Organize and Group Discovered Association Rules. DataMiningandKnowledgeDiscover.14: 409-431, 2007. 8 F. Thabtah, P. Cowling, and Y. Peng. MCAR: Multi-class Classification based on Association Rule Approach. In Proceedingofthe3rdIEEEInternationalConferen
16、ceonComputerSystemsandApplications.pp.1-7. Cairo, Egypt. 涯拼芳愧蜘费傀裸恤垂非琉抖隘翻材扣扎辱扰氦客蕾铲厘孺殴荷珍柄汗蓄关联分类算法的研究关联分类算法的研究Hebei University9 O. R. Zaiane and M.-L. Antonie. On pruning and tuning rules for associative classifiers. In Proc.ofIntlConf.onKnowledge-BasedIntelligenceInformation&EngineeringSystems(KES05),
17、 pp.966-973, 2005. 10Adriano Veloso, Wagner Meira Jr.: Rule Generation and Rule Selection Techniques for Cost-Sensitive Associative Classification. In SBBD2005. pp.295-309, 2005. 11J. Wang and G. Karypis. HARMONY: Efficiently Mining the Best Rules for Classification. In Proc.of2006SIAMInt.Conf.onDat
18、aMining(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), Dataminingforscientificapplications, 200113 X. Yin and J. Han. CPAR: Classification based on Predictive Association Rules.
19、In Proc.2003SIAMInt.Conf.onDataMining(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,
20、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 N
21、egative Rules, In 9thACMSIGMODWorkshoponResearchIssuesinDataMiningandKnowledgeDiscovery(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 Associat
22、ion Rule Mining. In Proc.MLDM2007, pp339-348. 2007. 18 Frans Coenen and Paul Leng. An Evaluation of Approaches to Classification Rule Selection. In Proc.of2004IEEEInt.Conf.onDataMining(ICDM04), pp359-362, 2004 19 K. Wang, S. Zhou, and Y. He. Growing decision tree on support-less association rules. I
23、n Proc.Of2000Int.Conf.onKnowledgeDiscoveryandDataMining(KDD00), Boston, MA, Aug. 2000. 20Frans Coenen and Paul Leng. Obtaining Best Parameter Values for Accurate Classification. In Proc.of2005IEEEInt.Conf.onDataMining(ICDM05), pp.597-600, 200521 D. Meretakis and B. Wuthrich. Extending Nave Bayes Cla
24、ssifiers Using Long Itemsets. In Proc.1999Int.Conf.onKnowledgeDiscoveryandDataMining(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 Proceedingsofthe4thEuropeanConferenceonPrinciplesofDataMiningandKnowledg
25、eDiscovery, Pages: 504 509, 2000 23 Bavani Arunasalam and Sanjay Chawla. CCCS: A Top-down Associative Classifier for Imbalanced Class Distribution. In Proc.Of2006Int.Conf.onKnowledgeDiscoveryandDataMining(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.of2007IEEEInt.Conf.onDataMining(ICDM07), 2007.吗槽剑沪脐饲串坤紊寺愿伤拌邓赤坛椅籍晋魔罗臭校涩廖昆扔按岗茸责罪关联分类算法的研究关联分类算法的研究Hebei University问题?谢谢!三质鸟臭格续尧夜钵雀遇灭洪韧曳朗后坊迭辽旷综拍腰弹迫千蹄锚剁观褒关联分类算法的研究关联分类算法的研究Hebei University