资源描述：
《基于区分链表的属性约简改进算法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、从本学科出发，应着重选对国民经济具有一定实用价值和理论意义的课题。课题具有先进性，便于研究生提出新见解，特别是博士生必须有创新性的成果基于区分链表的属性约简改进算法摘要属性约简是粗糙集理论中核心内容之一，本文首先分析了区分矩阵的特性，给出经典的区分矩阵算法。然后，鉴于区分矩阵存在的空间复杂度高的缺点，提出一种，将对象数为n的区分矩阵大小由n(n-1)/2至少压缩到
2、U/R
3、*/2，降低了算法的空间复杂度，更适用于大数据量的情况。关键词粗糙集；区分矩阵；属性约简；区分线性表粗糙集(RoughSet,RS)理论是提出的一种处理不一致、不完整数据和不精确知
4、识表达等各种不完备信息的数学理论[1]。其中属性约简是粗糙集理论中核心内容之一，现已证明是典型的NP难题[2，3]。所谓属性约简是指在保证信息系统分类能力或决策能力不变的条件下，删除属性集中的冗余属性。属性约简在分类学习及分类数据挖掘中具有重要的作用，目前国内外学术界在属性约简方面已经做了大量研究，并得到了许多有效的算法[4~6]。文献[4]深入分析了算法低效性的根源,给出了高效的约简算法；文献[5]给出了基于信息论的方法；文献[6]利用正区域的启发式信息给出了两种属性相对约简算法；其中应用较多的是基于华沙大学数学家Skowron提出差别矩阵[7]以
5、及在此基础上的一些改进[9~11]，由于这种基于区分矩阵方法易于解释和计算课题份量和难易程度要恰当，博士生能在二年内作出结果，硕士生能在一年内作出结果，特别是对实验条件等要有恰当的估计。从本学科出发，应着重选对国民经济具有一定实用价值和理论意义的课题。课题具有先进性，便于研究生提出新见解，特别是博士生必须有创新性的成果核属性,同时也便于约简，该方法为属性约简算法提供了一种很好的思路。然而，基于区分矩阵的属性约简算法对对象数为n的区分矩阵大小为n(n-1)/2，不适用于大数据量的情况，所以本文给出了一种改进算法，将空间复杂度至少压缩到
6、U/R
7、*/2，
8、该算法大大降低了算法的空间复杂度，适用于大数据量的情况。定义1[2]：设U为一个有限的非空论域，R为U上的等价关系。等价关系R把集合U划分为多个互不相交的子集，每一个子集称为一个等价类，用[x]R表示，[x]R={y∈U
9、xRy}，其中x∈U，x∈y称为关于R的等价关系，论域U上的所有等价类的集合用U/R来表示。定义2[2]：令R为一族等价关系，rR,如果IND(R)=IND(R-{r}),则称r为R中不必要的；否则r为R中必要的[2]，若R中任意一个等价关系r都是必要的，则称R是独立的，否则称R是依赖的。定义3[8]：设，若Q是独立的，且IND(Q
10、)=IND(P)，则Q是等价关系族P的一个约简。定义4[8]：设P和Q是论域U上的等价关系，Q的P正域记作POSP(Q)，定义为：Q的P正域是U中所有根据U/P的信息准确分类到关系Q的等价关系中去的对象构成的集合。定义5[8]：设P和Q是论域U上的等价关系，R∈P，若POSP(Q)=POS(P-{R})(Q)则称R为P中Q不必要的，否则称R为P中Q必要的。若P中任意一关系R都是Q必要的，则称P是Q独立的(相对于Q独立的)。定义6[2]：设SP，S为P的Q约简，当且仅当S是P的Q是独立的子集，且POSS(Q)=POSP(Q).P的Q约简称为相对约简。课
11、题份量和难易程度要恰当，博士生能在二年内作出结果，硕士生能在一年内作出结果，特别是对实验条件等要有恰当的估计。从本学科出发，应着重选对国民经济具有一定实用价值和理论意义的课题。课题具有先进性，便于研究生提出新见解，特别是博士生必须有创新性的成果定义7：区分矩阵是华沙大学数学家Skowron[7]提出的，对于系统S=(U,A),其中A=C∪D,a(x)是x在属性a上的值,区分矩阵M为：同时分辨矩阵中的核就是组合数为1的属性。区分矩阵的空间复杂度为n(n-1)/2,保存着论域中两两对象的可区分属性.在论域关于属性集划分中，同一个等价类的对象两两在区分矩阵
12、中的元素为空，而且与其他等价类的对象所构成的区分矩阵中的元素完全相同，因此从每一个等价类中只取一个对象构造的新的论域，其约简与原来的相同,而空间复杂度最多为
13、U/R
14、*/2.区分矩阵Matrix的某元素Matrix[i][j]，是区分对象U[i]与U[j]的条件属性集，由于在合取吸取运算中，参数i、j并没有实际价值，因此改用区分链表List来取代区分矩阵。在构造区分链表前，先定义存储核属性的变量core，可区分两对象的条件属性集若只有一个属性Ri，则属性Ri是核属性，那么Ri存储到变量core，在接下来的区分链表的构造过程中，若区分属性集包括已经提取
15、出来的核属性，直接约去，不插入到区分链表中；否则，插入到区分链表的表尾。为减少区分链表的大小，可以在每产生一
