基于差别矩阵的属性核快速更新算法.pdf

《基于差别矩阵的属性核快速更新算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第卷第期控制与决策年月文章编号基于差别矩阵的属性核快速更新算法杨明!杨萍南京师范大学数学与计算机科学学院南京摘要!核求解是粗糙集理论的重要内容之一"尽管在核求解问题上已有大量的研究成果"但有关核更新算法的报道却不多有人提出一种在对象增加情况下核的增量式更新算法"但未讨论对象动态删除的情况对此"提出一种基于差别矩阵的属性核快速更新算法###该算法在更新差别矩阵时仅需删除某一行及某一列"或插入某一行"因而可有效提高核的更新效率理论分析表明"该算法是有效可行的关键词!粗糙集$差别矩阵$核$更新$属性约简中图分类号文献标识码＠引言信息观求

2、解属性核的一致性和差异性有效补充和于世纪年代初提出的完善了文献但算法的效率仍需改进在文献粗糙集是一种新的处理不精确不完全与的基础上文献对差别矩阵作了进一步的改进不相容知识的数学理论近年来该理论在机器学习然而信息系统中的对象是动态变化的已得到的核数据挖掘及模式识别等多个领域得到了广泛的应将可能不再有效这就需要对核进行动态修改文献用核和属性约简是粗糙集理论中的两个重要提出一种基于改进差别矩阵的核增量式更新算研究内容法主要考虑对象动态增加情况下核的更新但未讨在现有的求解核方法中提出的基于差论对象动态删除的情况因此针对该情况本文提别矩阵的

3、求解核方法是经典的核求解方法之一该出一种基于差别矩阵的属性核快速更新算法方法可有效提高求解核的效率但在某些情况下不该算法在更新差别矩阵时仅需删除某一行能得到正确的核于是叶东毅教授提出了改进的及某一列或插入某一行因而可提高核的更新效率理论分析表明本文算法是有效可行的差别矩阵但计算量大为此王国胤教授对属性核求解问题进行了深入的探讨分析了代数观和粗糙集概念收稿日期修回日期基金项目国家自然科学基金项目江苏省自然科学基金项目江苏省高校自然科学基金项目作者简介杨明男安徽宁国人教授博士从事数据挖掘机器学习等研究杨萍女安徽宁国人副教授从事管理决策

4、粗糙集理论与应用等研究控制与决策第卷为节省篇幅仅介绍和属性约简及核有关的一表数据表些概念粗糙集的其他一些概念可见文献属性元素信息系统是一个元组其中是一组对象的非空有限集合含个对象可表示为是属性集合U为e属性的值域集是一的映射属性集合通常分为条件属性集与决策属性集为便于别矩阵定义并给出求核方法但计算量大为改进文叙述设条件属性集合中有个属性献的不足文献提出了改进的差别矩阵定其值域为有限离散集合并用表示集合的义以及求解核方法详细内容可参见文献基同时假设仅有一个决策属性其取值范围是然而上述方法均为静态求核方法于是文献由导出的等价类构成的一

5、个划分提出了基于差别矩阵的核增量式更新算法但其中e该方法未考虑对象删除情况为此本文以文献为基础引入下面的定义和定理定义增加了若两个不同的对象和具有相同的条件属性对不一致对象的计数其目的是在某个不一致对象和不同的分类则称和为不一致的否则称和删除后可快速判断其相应的不一致对象是否变为一为一致的致定义设二为论域的一个子集二定义对给定的信息系统定义差别矩阵关于的下近似为e二其中Ve为e羊’定义设二对划分的羊ee近似精度为】＜e羊定义设二若且不存在＝ee使得则称为的一个相对于决策属L。其他性的属性约简所有的属性约简的交称为的其中U核简称核记

6、为函数描述如下已有的差别矩阵定义及其求核方法为有效求核等学者提出一种简洁的利用。改进差别矩阵来确定核的方法但得出的结论在某任意e些情况下是错误的如该方法不能得到例的核却不存在e使得Ve可得到例的核详见文献且羊例表为二值数据表其中共有个元素和U个属性为条件属性集为决策表示与对象属性不一致的对象个数例在例中删除第个对象即第条记录即得到表表数据表查找中与不一致的对象属性元素性质对U若羊。则＜针对方法的缺陷文献提出了新的差定理对于信息系统若记第期杨明等!基于差别矩阵的属性核快速更新算法e且为单个属性则有e即当且仅当某个为单个属性在中找到与

7、不一致的对象时该属性属于核羊证明类似于文献的定理回＞对例依据定义建立的差别矩阵为。。U其中在中增加对应的行核的快速更新算法对U由定义得到差别矩阵为若删除对在中查找与不一致的某个对象且象为则只要得到的差别矩阵简记为羊便可由定理求得核因此在对象删除情＞况下核的快速更新本质上就是差别矩阵的更新问题的更新分以下两种情况进行若e则删除中对象对应的行和用替代在和中的位置列若e且为中与不一致的对象则分以下两种情况讨论①当羊时如果＞则U且保持不变否则U且在中增加在中增加对应的行并替换相应列中的对应的行位置②当时在中查找任意一个与不一致的对象羊如果

8、＞则用替代在和中的位置否则由定理得到核U且在中增加对应的行并替换相应列中的位置定理设U依据上述分析核的快速更新算法描述如下由定义得到的差别矩阵为若删除对象为则由算法可得正确的核输入U证明对若设由定义建立的差别矩阵为则由上述算法可知当且仅差别矩阵为e