[数学建模小论文]
1 引言
粗糙集(Rough Set ,RS) 理论是 Z.Pawlak 提出的一种处理不一致、不完整数据和不精确知识表达等各种不完备信息的数学理论[1] 。其中属性约简是粗糙集理论中核心内容之一，现已证明是典型的NP难题[2，3]。所谓属性约简是指在保证信息系统分类能力或决策能力不变的条件下，删除属性集中的冗余属性。属性约简在分类学习及分类数据挖掘中具有重要的作用，目前国内外学术界在属性约简方面已经做了大量研究，并得到了许多有效的算法[4~6]。文献[4] 深入分析了算法低效性的根源,给出了高效的约简算法；文献[5]给出了基于信息论的方法；文献[6]利用正区域的启发式信息给出了两种属性相对约简算法；其中应用较多的是基于华沙大学数学家Skowron提出差别矩阵[7]以及在此基础上的一些改进[9~11]，由于这种基于区分矩阵方法易于解释和计算核属性,同时也便于约简，该方法为属性约简算法提供了一种很好的思路。然而，基于区分矩阵的属性约简算法对对象数为n的区分矩阵大小为n(n-1)/2，不适用于大数据量的情况，所以本文给出了一种改进算法，将空间复杂度至少压缩到|U/R|*（|U/R|-1）/2，该算法大大降低了算法的空间复杂度，适用于大数据量的情况。
2 基本概念
定义1[2]：设U为一个有限的非空论域，R为U上的等价关系。等价关系R 把集合U 划分为多个互不相交的子集，每一个子集称为一个等价类，用[x]R表示， [x]R={y∈U| xRy}，其中x∈U，x∈y称为关于R 的等价关系，论域U上的所有等价类的集合用U/ R来表示。
定义2[2]：令R为一族等价关系，r R,如果 IND(R)= IND(R-{r}),则称r为R中不必要的；否则r为R中必要的[2]<……
<<<<<全文未完，本文约1934个中文字，未计算英文字母、数字>>>>>
|
|
