资源描述：
《基于Roughset理论的增量式规则获取算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第26卷第1期小型微型计算机系统Vol.26No.12005年1月MINI-MICROSYSTEMSJan.2005基于Roughset理论的增量式规则获取算法1,232于洪,杨大春,吴中福1(重庆邮电学院计算机科学与技术研究所,重庆400065)2(重庆大学计算机科学与工程学院,重庆400044)3(深圳中兴通讯公司重庆研究所,重庆400060)E-mail:foxyuer@263.net摘要:从Roughset理论出发,讨论在新增数据时,新数据与已有规则集的关系、属性约简以及值约简的变化规律.并在此基础上提出一个新的基于RoughSet理论的增量式算法.从理论上和实验上对新算法
2、和传统算法在算法复杂度上做了分析与比较.关键词:增量式算法;规则获取;Roughset理论;决策表中图分类号:TP18文献标识码:A文章编号:1000-1220(2005)01-0036-06IncrementalRuleAcquisitionAlgorithmBasedonRoughSet1,2,YANGDa-chun3,WUZhong-fu1YUHong1(InstituteofComputerScience&Technology,ChongqingUniversityofPosts&Telecommunication,Chongqing400065,China)2(Insti
3、tuteofComputerScience&Engineering,ChongqingUniversity,Chongqing400044,China)3(ChongqingR&DInstituteofZTECorporation,Chongqing400060,China)Abstract:Therelationofthenewinstanceswiththeoriginallyruleset,thechangelawofattributereductionandvaluereduc-tionwerestudiedwhenanewinstancecoming.Anewincrem
4、entallearningalgorithmfordecisiontableswaspresentedwithintheframeworkofroughset.Thenewalgorithmandtheclassicalalgorithmwereanalyzedandcomparedbytheoryandexperi-ments.Keywords:incrementalalgorithm;ruleacquisition;roughsettheory;decisiontable1引言分别称为决策规则的前代和后继.当S中决策规则→为真时,我们说该决策规则是S中协调的,否则说该决策规
5、则是RoughSet理论是波兰科学家Z.Pawlak在1982年提出S中不协调的.当→为一个决策规则,且和分别为P[1]的一种处理含糊和不精确性问题的一种新型数学工具,目基本公式和Q基本公式,P,Q已知,则决策规则→称为[2]前已在人工智能、数据挖掘等领域得到广泛应用.Pawlak指PQ基本决策规则,简称为PQ规则.出机器学习中的若干问题都可以用RoughSet理论和方法来决策逻辑语言中任何有限决策规则集称为决策逻辑语言解释、分析和处理.在[2]中,提出了两个关于机器学习的新术中的决策算法,而任何有限基本决策规则称为一个基本决策语:静态学习和动态学习;前者也称非增量式学
6、习,后者也称算法.当基本决策算法中所有的决策规则都是PQ决策规则增量式学习.时,该算法称为PQ决策算法,或简称PQ算法,记作(P,Q).近几年来,RoughSet理论研究中对求解属性的最小约当且仅当S中所有决策规则是协调的,则S中PQ算法是协[3-5]调的,否则PQ算法是不协调的.简、较小约简和最简规则集进行了一些研究,但这些研究都是针对静态数据的.关于属性最小约简的增量式算法以及一个决策表的最小化的过程也就是获取知识(即规则)的增量式更新概念格的算法已经开始被研究[6-8],本文研究规则过程,包括两个步骤[10]:获取的增量式算法.Step1:属性约简算法,即从PQ算法得到RQ基
7、本规则(RQ算法)R=RED(P,Q);2有关理论介绍Step2:值约简算法,即得到RQ基本规则的所有约简,[9]首先,来看有关决策逻辑语言的一些基本概念.在逻辑并化简得到一个最小规则集.语言中,含义→称为知识表达语言中的决策规则,和例1.考虑图1所示的决策表[9].其中,U={1,2,3,4,5,收稿日期:2003-07-09基金项目:国家自然科学基金(60373111)资助;重庆市科委攻关基金(7006)资助;重庆邮电学院科研基金(A2004-46)资助.
