基于区分链表的属性约简改进算法的论文

-本文为网络收集精选范文、公文、论文、和其他应用文档，如需本文，请下载-基于区分链表的属性约简改进算法的论文本文从网络收集而来，上传到平台为了帮到更多的人，如果您需要使用本文档，请点击下载按钮下载本文档（有偿下载），另外祝您生活愉快，工作顺利，万事如意！摘 要 属性约简是粗糙集理论中核心内容之一，本文首先分析了区分矩阵的特性，给出经典的区分矩阵算法。然后，鉴于区分矩阵存在的空间复杂度高的缺点，提出一种基于区分链表的属性约简改进算法，将对象数为n的区分矩阵大小由n(n-1)/2至少压缩到|u/r|*（|u/r|-1）/2，降低了算法的空间复杂度，更适用于大数据量的情况。 关键词 粗糙集；区分矩阵；属性约简；区分线性表 1 引言 粗糙集(rough set ,rs) 理论是 提出的一种处理不一致、不完整数据和不精确知识表达等各种不完备信息的数学理论1 。其中属性约简是粗糙集理论中核心内容之一，现已证明是典型的np难题2，3。所谓属性约简是指在保证信息系统分类能力或决策能力不变的条件下，删除属性集中的冗余属性。属性约简在分类学习及分类数据挖掘中具有重要的作用，目前国内外学术界在属性约简方面已经做了大量研究，并得到了许多有效的算法46。文献4 深入分析了算法低效性的根源,给出了高效的约简算法；文献5给出了基于信息论的方法；文献6利用正区域的启发式信息给出了两种属性相对约简算法；其中应用较多的是基于华沙大学数学家skowron提出差别矩阵7以及在此基础上的一些改进911，由于这种基于区分矩阵方法易于解释和计算核属性,同时也便于约简，该方法为属性约简算法提供了一种很好的思路。然而，基于区分矩阵的属性约简算法对对象数为n的区分矩阵大小为n(n-1)/2，不适用于大数据量的情况，所以本文给出了一种改进算法，将空间复杂度至少压缩到|u/r|*（|u/r|-1）/2，该算法大大降低了算法的空间复杂度，适用于大数据量的情况。2 基本概念 定义12：设u为一个有限的非空论域，r为u上的等价关系。等价关系r 把集合u 划分为多个互不相交的子集，每一个子集称为一个等价类，用xr表示， xr=yu| xry，其中xu，xy称为关于r 的等价关系，论域u上的所有等价类的集合用u/ r来表示。 定义22：令r为一族等价关系，r r,如果 ind(r)= ind(r-r),则称r为r中不必要的；否则r为r中必要的2，若r中任意一个等价关系r都是必要的，则称r是独立的，否则称r是依赖的。 定义38：设 ，若q是独立的，且ind(q)=ind(p)，则q是等价关系族p的一个约简。 定义48：设p和q是论域u上的等价关系，q的p正域记作posp(q)，定义为：q的p正域是u中所有根据u/p的信息准确分类到关系q的等价关系中去的对象构成的集合。 定义58：设p和q是论域u上的等价关系，rp，若posp(q) =pos(p-r)(q)则称r为p中q不必要的，否则称r为p中q必要的。若p中任意一关系r都是q必要的，则称p是q独立的(相对于q独立的)。 定义62：设 sp，s为p的q约简，当且仅当s是p的q是独立的子集，且poss(q) =posp(q). p的q约简称为相对约简。 定义7：区分矩阵是华沙大学数学家skowron7提出的，对于系统s=(u,a),其中a=cd, a(x)是x在属性a上的值,区分矩阵m为：同时分辨矩阵中的核就是组合数为1的属性。3 基于区分链表的属性约简改进算法 区分矩阵的空间复杂度为n(n-1)/2,保存着论域中两两对象的可区分属性.在论域关于属性集划分中，同一个等价类的对象两两在区分矩阵中的元素为空，而且与其他等价类的对象所构成的区分矩阵中的元素完全相同，因此从每一个等价类中只取一个对象构造的新的论域，其约简与原来的相同,而空间复杂度最多为|u/r|*（|u/r|-1）/2. 区分矩阵matrix的某元素matrixij，是区分对象ui与uj的条件属性集，由于在合取吸取运算中，参数i、j并没有实际价值，因此改用区分链表list来取代区分矩阵。在构造区分链表前，先定义存储核属性的变量core，可区分两对象的条件属性集若只有一个属性ri，则属性ri是核属性，那么ri存储到变量core，在接下来的区分链表的构造过程中，若区分属性集包括已经提取出来的核属性，直接约去，不插入到区分链表中；否则，插入到区分链表的表尾。为减少区分链表的大小，可以在每产生一个核属性rj，进入变量core后，化简区分链表list，若list中的元素listk包含属性rj则直接删除元素listk。对应算法如下： for(p=u;p-next !=null;p=p-next) for(q=p-next;q!=null;q=q-next) x= 对象p、q的可区分属性集； if（|x|=1） 则x进入核变量core； else if（x不包含核变量core中已有的任何一个核属性） (x); 在得到了核和区分链表后，首先，将核加入到候选约简中；然后，统计区分链表中各属性出现的次数，将出现次数最多的属性r加入到侯选约简中，删除区分链表中出现r的所有节点，依次循环，直到区分链表为空，此时侯选约简就是所求约简。对应算法如下： c_reduce=core; while(1) if(list=null) break; else 遍历list,统计各条件属性出现的次数； 选择出现次数最多的那个属性r； c_reduce=c_reduce r; 删除list中所有出现r的的节点； 4 实例分析 设如下表112给定的决策表，求所有约简及核。 u conditional attributesdecisionsabcdx12201x21200x31201x40000x51010x62011 而应用本文给出的算法,区分线性表只有b,c一个元素,计算过程如下:首先得到区分属性集a，a进入核变量，在随后生成的区分属性集中只要含有a，则直接约掉，b,c进入区分线性表，采用启发式算法，可得到约简a,b。而基于区分矩阵的属性约简算法构造的区分矩阵如下：本算法相对于传统方法，大大减少了区分矩阵所需要的存储空间。5 结论 近年来rough 集理论以其独特的优势正赢得越来越多的专家学者关注,在理论研究方面日趋成熟,并在许多领域取得了较为成功的应用，属性约简算法是粗糙集理论的核心内容之一，其中，区分矩阵作为属性约简的主要方法之一已经受到越来越多的学者关注，因此，本文深入研究分析了区分矩阵算法，基于区分线性表，提出一种改进的属性约简算法。参考文献1 pawlak z. rough sets(j). international journal of computer and information science, 1982, 11(5): 341-3562 张文修,吴伟志. 粗糙集理论介绍和研究综述j . 模糊系统与数学,2000 ,15 (4) :1-12 3 王国胤. rough 集理论与知识获取m . 西安:西安交通大学出版社,20014 刘少辉. rough集高效算法的研究. 计算机学报(j), 2003,26(5):524-5295 王国胤, 于洪, 杨大春. 基于条件信息熵的决策表约简(j) . 计算机学报 ,2002, 25( 7 ): 759-7666 张腾飞, 肖健梅, 王锡淮. 粗糙集理论中属性相对约简算法. 电子学报(j) ,2005, 33(11):2080-20837 skowron a. rauszer c. the discerni-bility matrics and functions in information system(j), intelligent decision support handbook of applications and advances of the rough sets theory dordrecht: kluwer academic publishers, 1992: 331-3628 李雄飞, 李军. 数据挖掘与知识发现m. 高等教育出版社,20039 范 敏,刘文奇.基于粗集可辨识矩阵的属性约简算法j .计算机工程与应用,2004 ,38 (13) :79 - 8010 wangjue ,wangju. reduction algorithm based on disernibility matrix: the ordered attributes method j . j . comput . sci . &technol ,2