资源描述：
《基于区分链表的属性约简改进算法的论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、基于区分链表的属性约简改进算法的论文摘要属性约简是粗糙集理论中核心内容之一，本文首先分析了区分矩阵的特性，给出经典的区分矩阵算法。然后，鉴于区分矩阵存在的空间复杂度高的缺点，提出一种基于区分链表的属性约简改进算法，将对象数为n的区分矩阵大小由n(n-1)/2至少压缩到
2、u/r
3、*（
4、u/r
5、-1）/2，降低了算法的空间复杂度，更适用于大数据量的情况。关键词粗糙集；区分矩阵；属性约简；区分线性表1引言粗糙集(roughset,rs)理论是z.pa为：同时分辨矩阵中的核就是组合数为1的属性。3基于区分链表的属性
6、约简改进算法区分矩阵的空间复杂度为n(n-1)/2,保存着论域中两两对象的可区分属性.在论域关于属性集划分中，同一个等价类的对象两两在区分矩阵中的元素为空，而且与其他等价类的对象所构成的区分矩阵中的元素完全相同，因此从每一个等价类中只取一个对象构造的新的论域，其约简与原来的相同,而空间复杂度最多为
7、u/r
8、*（
9、u/r
10、-1）/2.区分矩阵matrix的某元素matrix[i][j]，是区分对象u[i]与u[j]的条件属性集，由于在合取吸取运算中，参数i、j并没有实际价值，因此改用区分链表list来取代区分
11、矩阵。在构造区分链表前，先定义存储核属性的变量core，可区分两对象的条件属性集若只有一个属性ri，则属性ri是核属性，那么ri存储到变量core，在接下来的区分链表的构造过程中，若区分属性集包括已经提取出来的核属性，直接约去，不插入到区分链表中；否则，插入到区分链表的表尾。为减少区分链表的大小，可以在每产生一个核属性rj，进入变量core后，化简区分链表list，若list中的元素list[k]包含属性rj则直接删除元素list[k]。对应算法如下：for(p=u;p->next!=null;p=p
12、->next)for(q=p->next;q!=null;q=q->next){x=对象p、q的可区分属性集；if（
13、x
14、==1）则x进入核变量core；elseif（x不包含核变量core中已有的任何一个核属性）list.add(x);}在得到了核和区分链表后，首先，将核加入到候选约简中；然后，统计区分链表中各属性出现的次数，将出现次数最多的属性r加入到侯选约简中，删除区分链表中出现r的所有节点，依次循环，直到区分链表为空，此时侯选约简就是所求约简。对应算法如下：c_reduce=cor
15、e;ationscience,1982,11(5):341-356[2]张文修,吴伟志.粗糙集理论介绍和研究综述[j].模糊系统与数学,2000,15(4):1-12[3]王国胤.rough集理论与知识获取[m].西安:西安交通大学出版社,2001[4]刘少辉.rough集高效算法的研究.计算机学报(j),2003,26(5):524-529[5]王国胤,于 洪,杨大春.基于条件信息熵的决策表约简(j).计算机学报,2002,25(7):759-766[6]张腾飞,肖健梅,王锡淮.粗糙集理论中属性相对约简算
16、法.电子学报(j),2005,33(11):2080-2083[7]skoatricsandfunctionsininformationsystem(j),intelligentdecisionsupporthandbookofapplicationsandadvancesoftheroughsetstheorydordrecht:kluicpublishers,1992:331-362[8]李雄飞,李军.数据挖掘与知识发现[m].高等教育出版社,2003[9]范敏,刘文奇.基于粗集可辨识矩阵的属性约简算法
17、[j].计算机工程与应用,2004,38(13):79-80[10]basedondisernibilitymatrix:theorderedattributesmethod[j].j.put.sci.technol,2001,16(6):489-504[11]王兵,陈善本.一种基于差别矩阵的属性约简完备算法[j].上海交通大学学报,2004,38(1):43-46
