离群数据规则挖掘的决策树构造方法.doc

离群数据规则挖掘的决策树构造方法 计算机工程与设计ComputerEngineeringandDesign2011,Vo1.32,No.51781 离群数据规则挖掘的决策树构造方法 王瑞伟,李志华 (江南大学信息工程学院,江苏无锡214122) 摘要:提出了一种针对离群数据规则挖掘的决策树构造方法.通过给出一个平均致密度的新定义和对离群数据产生机制 的深入分析,提出离群数据的致密度往往比正常样本数据高的新认识,指出离群数据本质上也是不平衡数据,基于此提出 了一种自动标记离群数据的新算法,并进一步在该算法和C4.5算法部分功能的基础上提出了一种基于离群数据自动标记的 模糊决策树构造方法.仿真实验结果表明,该方法具有高效的离群数据规则挖掘能力,能处理不平衡数据,优化决蓑树的结 构,挖掘出更高信任度的规则,有一定的实用价值. 关键词:离群数据;平均致密度;覆盖;决策树;规则挖掘 中图法分类号:TP301文献标识码:A文章编号:1000.7024(2011)05.1781.04 Decisiontreeconstructionmethodforoutliersrulemining WANGRui—wei,LIZhi—hua (SchoolofInformationandEngineering,JiangnanUniversity,Wuxi214122,China) Abstract:Anewdecisiontreeconstructionmethodforoutliersruleminingispresented.Bystudyingtheproducingmechanismof outliers,adefinitionofaveragedensenessfordatadistributionisgiven,thehigherdensityofoutliersthanthatofnormaldataispointed out,andtheoutliersisessentiallyimbalanceddata,too.Basedontheabove,allauto—taggingoutliersATOalgorithmisgiven.Further, anATO—basedfuzzydecisiontreegenerationmethodFDTMisproposed,whichconstructsthedecisiontreebytheformtreefunctionof C4.5finally.ExperimentalresultsdemonstratethattheFDTMoutperformstheC4.5attheaspectsoftheefficiencyofoutliersrulemining, theconfidenceoftheminingrules,thecapabilityoftacklingtheimbalanceddataandoptimizingtheconstructionofthedecisiontree. Keywords:outliers;averagedenseness;cover;decisiontree;rulemining 0引言 离群点(outliers,又称孤立点)是指数据集合中不符合数据 一 般特性或一般模型的数据对象,这些数据对象通常远离其 它数据对象,并且往往蕴含着一些特殊情况的信息n.多个 离群点的集合,或称超过一定数量规模的离群点集合称为离 群数据.离群数据产生的原因有两种:①在收集数据的过程 中由于度量或执行错误产生的异常;②数据本身的变异产生 的异常,后一种异常完全是由于潜在的不确定性机制造成的, 产生的离群数中往往蕴藏有丰富的,有价值的信息,并且具有 特殊性,有助于对数据中潜在规律的挖掘.通常,离群数据往 往偏离大部分数据,并且呈现小样本,致密性的特点,如果从 模式识别的样本分布角度而言,相对于大量的正常数据,其本 质上就是不平衡数据.如网络安全事件中的违法数据,海量 手机短信息中不文明信息,Web页面中不健康网页内容等,这 些数据大量存在,并且相对于正常网络数据而言是典型的离 群数据.当前有关离群数据的数据挖掘的研究n.已有很多, 但如果要进一步获取更加有效的模式作为证据,如对于网络 安全取证,则必然要对网络数据中大量存在的离群数据进行 规则挖掘,这是当前学术界一个比较热门的研究领域. 目前,主要从两方面来研究规则的生成:①通过应用决策 分类算法生成决策树,然后根据决策树抽取规则,其缺点是: 只能在单个结点上检验单一属性,当学习的对象数目较多时, 单变量决策的表达很复杂,决策树的复杂度比较高而分类精 度却不高;②通过粗糙集等理论,构造决策表,根据决策表生 成规则,其缺点是: