属性约简（共8篇）
属性约简 篇1
0 引言
粗糙集理论是由波兰数学家Z.Pawlak在1982年提出的,该理论是一种刻画不完整性和不确定性的数学工具,能有效地分析和处理不精确、不一致、不完整等各种不完备信息,并从中发现隐含的知识,揭示潜在的规律[1]。其主要思想是在保持分类能力不变的前提下,通过知识约简,导出问题的决策或分类规则。近年来,它已经被广泛应用到人工智能、模式识别、数据挖掘和故障诊断等方面[2,3,4,5,6]。
属性约简是粗糙集知识发现的核心内容之一,它描述了信息系统属性集中的每个属性是否都是必要的以及如何删除不必要的知识。经过多年的研究,已经知道求粗糙集的最小属性约简是一个NP-hard问题[7]。现在研究出的属性约简算法主要有:基于信息熵、基于区分矩阵、基于可辨识矩阵等算法[8],各自在某些问题上取得了相当的成效。很多学者提出利用核和属性重要性的约简算法,该类算法使用核作为计算约简的出发点,属性的重要性作为启发规则,计算最小的约简。
本文研究了可辨识矩阵的约简,从属性依赖度角度给出了两种属性重要性度算法公式,在此基础上提出了一种属性约简的启发式算法。此算法以属性频率作为启发式信息[9],同时解决了当属性频率相同的情况下的属性选择问题。即提出了属性频率相同时的属性重要性判断标准。解决了基于可辨识矩阵中以属性频率作为属性重要性度量时[9]产生重要度相同的情况。
1 粗糙集基本概念
定义1一个信息系统S,表示为S=(U,A,V,f),其中U={X1,X2,…,Xn}是论域;A是属性集合;V=∪va,∀a∈A,va表示属性的值域;f=U×A→V是一个信息函数,对x∈U,a∈A,有f(x,a)∈va。若A可分为条件属性集C和决策属性集D,即A=C∪D,C∩D=φ,则该信息系统称为决策表。
定义2在信息系统S中,对于每个属性子集B⊆A可以定义一个不可分辨的关系ID(B):
称为由B构造的不可分辨关系。
定义3在信息系统S中,对于属性集X⊆U,R为等价关系,定义2个子集:
分别称它们为X的R下近似和R上近似集。
定义4在信息系统S中,若P,Q⊆A,则Q的P正域POSP(Q)定义为:
其中P-X为X的P下近似。Q的P正域是U中所有根据分类U/P的信息可以准确地划分到关系Q的等价类中去的对象集合。
定义5 P和Q为U上的等价关系,当POSp(Q)=POSp-r(Q),称r∈P为P中Q可省略的,反之,r为P中Q不可省略的。
定义6当P中任意r都为Q不可省略时,称P为Q独立的。当S为P上的Q独立子族,并且满足POSS(Q)=POSP(Q),称S为P的Q简化。
定义7 P中所有Q不可省略原始关系族记为redQ(P),称为P的Q核,记作Coreα(P):
定义8据定义1中的决策表,从核R=Core(C)出发,根据属性重要性的大小来选择重要性最大的属性a加入到R中,R=R∪{a},直到POSR(D)=POSC(D),R为约简的属性。
2 改进的基于属性重要度的启发式算法
2.1 改进的属性重要度量方法
设S=(U,A,V,f)是一个决策表,且R⊂C,则对于任意的属性a∈C-R的属性重要性定义为:
文献[9]提出的基于可辨识矩阵的属性频率约简算法,以可辨识矩阵中属性a的出现次数作为判断属性重要性的标准:
由式(1)定义的属性重要度作为属性相对于决策的相对重要度的启发式信息,文献[9]中已经给出了详细的解释,这里不再赘述。通过上述方法可以依据属性对分类的影响即属性重要性来选择属性,但是经常会遇到属性重要性相等的情况,这时就无法选择属性。
基于文献[9]的算法中用属性频率作为属性度量方法时会出现相同属性重要性时存在的一些问题,本文提出了一种在属性度相同情况下如何选择属性的方法[10]。通过另一个属性重要度表示方法M来作为选择属性的标准,若求属性a的M值,下面给出M的定义:
对于一个决策类Yj,如果某个条件属性集决定的等价类当中有一个是Yj的子集,虽然可能没有一个是决策类的子集,可这个条件属性集对Yj来说也是很重要的,SGF2就是在这个思想的基础上提出的,SGF2表示论域U对于属性a的分类中包含于决策属性分类Yj的最大对象数在分类Yj上的比例,方便起见可以用M来表示,可以通过求相同重要度属性的M值,选择M值最大的属性加入到属性约简集中。
2.2 改进的算法
输入:决策表S=(U,C∪D);
输出:S的属性约简集。
(1)首先计算出决策表的可辨识矩阵,然后将可辨识矩阵中的核属性(即属性组合数为1的条件属性)赋给属性约简后得到的属性集,即red=Core;
(2)将可辨识矩阵中含有核属性的属性组合项去掉;
(3)根据定义1计算可辨识矩阵中所有剩余属性项中各条件属性出现的频率,选出出现频率最高的属性,该属性记为a;red=red∪{a},如果出现频率相同的属性,求出属性的M值,选择M值最大的属性加入到red中去,将可辨识矩阵中包含有条件属性a的属性组合项删除掉;
(4)计算POSred(D),当POSred(D)≠POSC(D)时,转(3),当POSred(D)=POSC(D)时,red就是最后得到的约简。
3 算法分析
下面通过一个例子来说明一下2.2改进算法的有效性,表1为某决策表。
表1决策表对应的可辨识矩阵如下:
从可辨识矩阵可知,其中c为核属性,在去掉属性c以及含有c的组合项后得到新的可辨识矩阵如下:
从可辨识矩阵中知道,属性a,b,d的出现频率是相同的,即p(a)=p(b)=p(d)=6,也就是说根据定义1的公式不能确定加入到核中的属性,因为三个属性出现的频率都是相同的,这时我们可以根据公式2来求这三个属性的M值,过程如下:
由以上公式可得:
可知a的M值最大,将a加入到red中去:
因此Red={a,c}为最后这个决策表的约简集。
4复杂度分析
算法第一步求出可辨识矩阵的核属性的时间复杂度为O(|U||A|2|A|log|U|),根据文献[11]的计算正区域的方法,算法第四步计算正区域的最大的时间复杂度为O((|C|+1)|U|log|U|),所以算法总的时间复杂度为O(|U||A|2|A|log|U|),并没有增加原先基于可辨识矩阵属性约简算法的时间复杂度。
5结束语
本文在文献[9]中提出的可辨识矩阵属性频率约简算法基础上,提出了一个改进的属性频率约简算法,即当可辨识矩阵约简算法中出现属性频率相同的情况时,通过属性求得的另一个属性重要度值来确定要选择加入到约简集中的属性,解决了在属性频率相同的情况下的属性选择问题。此方法据分析能有效地对在可辨识矩阵中属性频率相同的属性进行约简。
参考文献
[1]Pawlak Z.Rough sets[J].Communications of ACM,1995,38(11):8995.
[2]Pawlak Z.Rough Sets-Theo ret ical A spects of Reasoning About Data[M].Dordrech t:Kluwer Academic Publishers,1991:930.
[3]Frank W,Hans T.The application of rough sets analysis inactivity based modeling:Opportunities and constraints[J].Expert Systems with Application,2004(27):585592.
[4]Amitava R,Pasankar K.Fuzzy Discretization of feature space for a rough set classifier[J].Pattern Recognition Letters,2003(24):895902.
[5]Tsumoto S.Mining diagnostic rules from clinical databases using rough sets and medical diagnostic model[J].Information Sciences,2004(162):6580.
[6]王国胤.Rough集理论与知识获取[M].西安:西安交通大学出版社,2001.
[7]Wang K M,Ziarko W.On optimal decision rules in decision tables[J].Bulletin of Polish Academy of Science,1985,33:693696.
[8]Skowron A,Crauszer.The Discernibility Matrix and Functionsin Infor-mation System,Handbook of Applications and Advances of the Rough Set Theory[M].Kluwer Academic Publishers,1992:331361.
[9]任小康,吴尚智,马如云.基于可辨识矩阵的属性频率约简算法[J].兰州大学学报:自然科学版,2007,43(1):138140.
[10]罗来鹏,刘二根.一种新的属性重要性度量及其规则获取[J].计算机工程与应用,2007,43(22):170172.
[11]刘少辉,盛秋戬,吴斌,等.Rough集高效算法研究[J].计算机学报,2003,26(5):524529.
属性约简 篇2
关键词：数据挖掘 属性约简 重要度
数据挖掘是从海量的且不断动态变化的数据中，借助有效的方法挖掘出潜在、有价值的知识过程。而粗糙集理论它是一种刻画不完整性和不确定性的数学工具，能在保持分类能力不变的前提下，通过知识约简从中发现隐含的知识，揭示潜在的规律，是由波兰科学家Pawlak在1982年提出的。而属性约简是粗糙集理论研究的核心内容之一，它能保证在分类能力不变的情况下，消除重复、冗余的属性和属性值，减少数据挖掘要处理的信息量，提高数据挖掘的效率。本文提出了通过计算单个属性的重要性，以重要性大于零的属性为核，来选取其它属性加入核中形成新的集合RED，直至剩下的所有属性的重要性为零，得到的集合REDn即为属性约简。粗糙集的基本理论[1-2]
定义1设 是一个信息系统，其中 是对象的非空有限集合，即;是属性的非空有限集合;，是属性 的值域;是一个信息函数，即每个对象在每个属性上对应的信息值。若，其中 为非空有限条件属性集合，为非空有限决策属性集合，且，则称信息系统为决策表。
定义2对决策表，，考虑单决策属性的情况，即，则的分辨矩阵是一个 矩阵，其中的元素定义如下：
定义3对分辨矩阵中每个，用布尔函数 来表示，若，则决策表的分辨函数 可定义为：。基于粗糙集的数据挖掘的属性约简算法[3-4]
2.1 算法分析
第一步：求核。通过求条件属性C中的每个属性a对在整个条件属性集C的重要性SigC(x)来确定属性核CORE(x)，重要性SigC(x)>0的属性为核属性。
第二步：通过向属性核CORE(x)中依次加入重要性大的属性来确定属性集x的最小约简，详细步骤如下：(1)把a加入到属性集R 中，计算重要性，选择重要性最大的属性;(2)如果两个属性有相同的重要性，取离散值小的属性。
2.2 算法复杂度
通过算法的分析，在对决策表进行划分的时间复杂度为O(n2)。而计算条件属性的重要性也是满足划分的线性关系，因此所求属性核的时间复杂度为O(n2)，依次添加次重要度的属性也没有增加额外的开销，因此整个时间复杂度还是O(n2)。
2.3 实例及分析
为了进一步验证算法的可行性，下面以表1中的决策表为例进行分析说明，其中对象集，条件属性集，决策属性。
以上对计算出的实验数据的重要性进行统计得出信息系统的两个约简为{c1,c4}和{c2,c4}。结语
本文针对属性约简算法中的属性重要度的计算来确定核，适合对海量数据的挖掘，不仅节省了存储空间，而且在时间复杂度开销少，通过实验分析验证了算法的可行性与有效性，为决策表的属性约简提供了一条高效的途径。
参考文献：
[1]张文修,吴伟志.粗糙集理论与方法[M].北京:科学出版社,2001:18-19
[2]周献中,黄兵，李华雄,等.不完备信息系统知识获取的粗糙集理论与方法[M].南京:南京大学出版社,2010:10-11
[3]饶泓,夏叶娟,李娒竹.基于分辨矩阵和属性重要度的规则提取算法[J].计算机工程与应用，2008,44(3):163-165
属性重要性的启发式属性约简算法 篇3
关键词：属性约简,属性重要性,二进制可辨矩阵,Rough集
0 引言
Rough集理论自80年代初由波兰学者Z.Pawlak提出以来,是一种迅速发展的既有理论又有应用的研究领域[1]。粗糙集理论[2,3]是Pawlak等人提出的一种处理不精确、不完全信息的新型数学工具。由于二进制的可实现性,很多学者将其引入属性约简算法中,文献[5,6]用二进制可辨矩阵设计了基于正域的属性约简算法,但都没有解决当二进制可辨矩阵列的属性频率出现次数相同的情况下选取加入到约简中的顺序问题。本文在文献[5,6,7]的基础上,提出了以属性频率和属性关于U/D正域之和为启发式信息的二进制可辨识矩阵列的属性约简算法,解决了当二进制可辨识矩阵列的属性频率相同的情况下的属性选取问题。
1 属性约简基本概念
定义1一个信息系统S,表示为S=(U,A,V,f),其中U={X1,X2,…,Xn}是论域;A是属性集合;V=∪va,a∈A,va表示属性的值域;f=U×A→V是一个信息函数,对x∈U,a∈A,有f(x,a)∈va。若A可分为条件属性集C和决策属性集D,即A=C∪D,C∩D=φ,则该信息系统称为决策表。
定义2设R是一个等价关系族,r∈R,如果IND(R)=IND(R-{r}),则称r在R中是可被约去的知识;如果P=R-{r}是独立的,则P是R中的一个约简。
定义3在信息系统S中,若P,Q∈A,则Q的P正域POSP(Q)定义为:
其中P X为X的P下近似。Q的P正域是U中所有根据分类U/P的信息可以准确地划分到关系Q的等价类中去的对象集合。
2 二进制可辨矩阵[8]
定义4设决策表为T=(U,C,D,V,f),其中U={u1,u2,…,un},C={c1,c2,…,cm},D={d}则决策表T相应的二进制可辨矩阵MT构造为:矩阵的每一列对应一个条件属性,共有m列,每一行对应一对论域中的对象(up,uq),有n(n-1)/2行。设矩阵中一元素m((p,q),i)所在行对应的应对象对(up,uq),所在列对应条件属ci,则
这样得到的一个矩阵,称之为相应于决策表T=(U,C,D,V,f)的二进制可辨矩阵。
命题1若二进制可辨矩阵中某一行只有一个元素为1其余元素均为0,则元素1所在列对应某个属性,所有这样的属性构成信息系统的核或决策表的相对核。若没有这样的行,则核或相对核为空。
3 属性重要性的度量方法
对于决策表T=(U,C,D,V,f):用P(ci)(ci∈C,1≤i≤|C|)表示ci在二进制可辨识矩阵中的属性频率;用MAX(P(c))表示二进制可辨识矩阵中属性c出现的最大频率;用NMAX表示二进制可辨识矩阵中属性出现的频率等于最大频率的属性总数,NMAX=|{ci|P(ci)=MAX(P(c)),1≤i≤|C|}|;条件属性ci∈C(1≤i≤|C|)的重要性可以用ci的属性频率P(ci)和U/{ci}关于U/D正域POSU/{ci}(U/D)来度量,用Gci表示,则Gci可通过公式1给出,如下所示。
4 属性重要性的启发式属性约简算法
在二进制可辨矩阵中,对于那些只有一个元素为1其余元素均为0的行,元素1所在列的属性一定属于核,而对于那些有多个元素为1的行,在这些元素为1所在的列中,那些所含1的个数最多的列对应的属性虽未必是核属性,但具有很强的分辨能力,因此这样的属性在形成约简,尤其是最小约简的过程中具有重要地位。
算法二进制可辨矩阵属性重要性的启发式属性约简。
输入:决策表T=(U,C,D,V,f)
输出:决策表T属性约简
1)根据给定的决策表T=(U,C,D,V,f)产生二进制可辨矩阵M,将M中全为1和0的行删除,得到新的Mnew。置矩阵MA←Mnew,用Reduction表示属性约简,初始值为Reduction=φ。
2)对每一行,若该行只有一个元素为1,则将该元素所对应的属性为核属性,并将该属性加入到Reduction,即Reduction←Reduction∪{ci},其中ci∈C,1≤i≤|C|。
3)从MA中删除各行只有一个元素为1的行及该行元素1所对应的列值为1的行,将得到的新矩阵MAnew再赋给MA。如果MA=φ,则转到7),否则到4)。
4)将MA的各列纵向相加,并将结果存入相应col[ci]中,其中ci∈C,1≤i≤|C|。
5)用一维数组G[|C|]表示属性的重要性,初始值为G[ci]=0,其中ci∈C,1≤i≤|C|。根据公式1计算属性重要性;在M A中将属性重要性最大的属性ci列及ci列上值为1的元素所对应的行去掉;将得到的新矩阵再赋给M A,并将Reduction←Reduction∪{ci}。
6)将MA中行全为1和0的行删除,将得到的新矩阵再赋给MA。如果MA≠φ,则转到4)。
4)输出一个约简Reduction。
5 实例分析
表1中C={a,b,c,d}为条件属性,D={e}为决策属性,A=C∪D,对表1建立二进制可辨矩阵如表2所示。
将表2中去掉(1,7)、(2,4)及(5,6)三行,并将属性c中为1的行去掉,得表3。
表3中a,b,d各列的属性频率都为6,根据公式(1)计算属性的重要性,计算过程如下:
由以上公式可得:G[a]=1+3/4=1.75,G[b]=1+0=1,G[d]=1+2/4=1.5。可知a的属性的重要性最大,即Reduction={a,c}。将表3中a列及a列值为1的行去掉,再将行都为1的行删除,得到的表为空,因此Reduction={a,c}为最后这个决策表的约简集。
6 复杂度分析
设决策表中有m个条件属性,n个对象,在最坏情况下,构造二进制可辨矩阵需要比较mn(n-1)/2次,复杂度为O(mn2);根据文献[9]的计算正域的方法,计算正域的最大的时间复杂度为O((|C|+1)|U|log|U|)=O(mnlogn),而计算MAX(P(ci))的最大的时间复杂度为O(n2),所以算法第7步的时间复杂度为MAX(O((mnlogn),O(n2))。因此本算法的时间复杂度为O(mn2)。
通过上述分析,可见本算法在文献[5,6,7]的基础上,并解决了当二进制可辨识矩阵列的属性频率相同的情况下的属性选取问题。当决策表的复杂程度较高时,它使得求解的复杂程度大大降低,是一种获得属性约简的简单而有效的方法。
参考文献
[1]刘清.Rough集及Rough推理[M].第一版.北京:科学出版社,2001.
[2]Pawlak Z.Rough sets and intelligent data analysis[J].InformationSciences:2002,147:1-12.
[3]Pawlak Z,Skowron A.Rough sets:Some extensions[J].Information Sciences:2007,177:41-73.
[4]支天云,苗夺谦.二进制可辨别矩阵的变换及高效属性约简算法的构造[J].计算机科学:2002,29(2):140-142.
[5]钱文彬,徐章艳,黄丽宇等.基于信息熵的二进制差别矩阵属性约简算法[J].计算机工程与应用:2010,46(6):120-123.
[6]任小康等.基于可辫识矩阵的属性频率约简算法[J].兰州大学学报:2003,43(1):138-140.
[7]Felix R,Ushio T.Rough Sets-based Machine Learning Usinga Binary Discernibility Matrix.IPMM99 published:1999:299-305.
连续值属性约简算法改进 篇4
连续值决策表的属性约简主要分为两部分:一,将模糊聚类引入到对象划分中,解决粗糙集在连续数值属性处理上的局限性,同时获得满足一定依赖度要求的Q型模糊聚类最佳参数λQ及对应实例序对(xi,xj)λ,本文将这部分称之为基于模糊聚类和粗糙集的连续型决策表对象离散化;二,对条件属性进行R型模糊聚类,获得期望数目的聚类,并从中选出符合依赖度要求的属性子集即为一个可接受的属性约简。
(一)连续型决策表对象离散化
通过Q型模糊聚类,我们将实型属性的模糊性转化为实例对象的模糊性,依据对象间的模糊近似程度,实现对象的离散化。Q型模糊聚类的最终结果取决于决策类对全部条件属性的依赖度,在数据充分的情况下,可认为这一依赖度的值为1。我们可以获得Q型模糊聚类的最佳参数λQ,及其对应的实例序对(xi,xj)λ。如果属性子集P是条件属性C相对于D的一个合理约简,属性子集P表达的对象模糊相似关系应最大程度地保持条件属性C表达的对象间模糊相似关系。那么序对(xi,xj)λ劬(i,j)在属性子集P的模糊相似矩阵FM P中,同样具有划分对象的作用。FM P(i,j)是模糊相似关系FM P中,使得分类满足依赖度要求的对象间相似度最低要求。算法如下:
输入:一个实型决策表S=(U,C U D,V,f)。输出:Q型模糊聚类最佳参数λQ及其序对(xi,xj)λ。Step1.决策表数据预处理:补缺、去重等;Step2.计算实例对象间的模糊相似矩阵FM C;Step3.运用直接聚类法进行对象划分,聚类参数λ,得到划分类Uλ;Step4.计算决策类对划分类的依赖度γλ(D),若γλ(D)=θ,转至Step5;否则,调整参数λ,转至Step3;Step5.得到最佳聚类参数λQ,计算其相应序对(xi,xj)λ;对序对(xi,xj)λ的数据行进行再次噪声检查,如果存在多组不受噪声干扰的序对,则从中任选一组;Step6.本部分算法结束,输出最佳聚类参数λQ和相应序对(xi,xj)λ。
(二)连续值属性约简
本文用R型模糊聚类将相似度贴近的属性聚为一类,并从每一类中选择代表性的属性构成属性子集,并以该子集的依赖度是否接近决策属性对全部条件属性的依赖度为标准判断该属性子集是否合理。定义1设实型决策表S=(U,C U D),条件属性C满足依赖度阈值的最佳聚类参数为λQ,对应序对为(xi,xj)λ,则属性子集P是C相对于D的属性约简:
在基于粗糙集的启发式属性约简算法中,往往约简的结果无法由预期控制。而在实际属性约简的工作中,人们通常对约简属性的数目有一个心理预期。同样地,在连续值决策表中也可以运用这种思路求得一个符合预期的可接受属性约简。具体分为以下三个步骤:一,以预期属性数目为主导,对条件属性进行聚类。二,对聚类结果进行属性组合。应当优先选择每一类中平均相似度最大的属性进入属性子集。可以获得一个由最具代表性的属性构成的属性子集P。三,计算属性子集依赖度。基于属性子集计算对象间模糊相似关系FMP,以FMP(i,j)(其中,(i,j)=(xi,xj)λ)为聚类的阈值,得到论域对象的划分,从而获得依赖度γp(D,FMP(i,j))。如果其依赖度满足:
其中,ρ为一接近0的正数,则说明属性子集P为C的一个可接受约简。如果>ρ,说明算法不能满足预期属性规模的属性约简,此时应当调整属性规模预期或选择其它算法。
二、实证
以数据集A(见附录A)的数据为例,说明本部分属性约简过程。在A的决策表S=(U,SU D)中,条件属性集C={c1,c2,…,c7},设定期望属性数目为z=3。Step1.计算条件属性的模糊相似矩阵FMR7×7。由于案例数据为时间序列,因此选择模糊相似关系为:
其中,m=7,1≤i,j≤20。
Step2.基于FM R,应用直接聚类法对条件属性进行划分,记为Rλ;并以|Rλ=z|为聚类终止条件。Step3.计算每一类中,属性之间的平均相似度:
Step4.构建属性子集,R0.73{1}中的最佳代表属性为c2,R0.73{2}中的最佳代表属性为c4,R0.73{3}中的最佳代表属性为c5。所以,属性子集P={c2,c4,c5}
Step5.计算决策属性对属性子集P的依赖度:γp(D,FM P((xi,xj)λ))。我们得到(xi,xj)λ=(x14,x15),γc(D,λQ)=0.35。计算基于P的实例对象间的模糊相似关系FM P20×20,ρ的设置不应太小。依赖接近度为0.1,说明约简前后的正域波动为两个对象,是可以接受的。因此,P={c2,c4,c5}是全部条件属性C相对于D的一个可接受约简。事实上,基于全部条件属性C的实例对象的聚类结果:
U_C={{1},{2},{3,4,7,8},{5,9,17},{6,18},{10},{11},{12,14,15,16,19,20},{13}}
基于属性子集P的实例对象的聚类结果:
U_P={{1},{2,3,4,6,7,8,14,15,16,18,19,20},{5,9,17},{10},{11},{12},{13}}
在两组分类中,只有{6,18}在U_P中发生了合并。这说明,属性子集P不仅较好地继承了条件属性C的划分能力,对其中相对于决策属性的分类能力,更是很好地保留。该种算法可以适用于连续型、离散型以及二者混合的数据类型。
摘要：目前存在的基于粗糙集理论的属性约简算法多数只适用于离散型数据。而在现实工作中,不仅有符号、类别等离散型数据,更有大量的连续型或实型数据,甚至二者的混合。传统的离散化过程并不能保存属性在数值上的差异,造成了一定程度的信息损失。本文提出一种将模糊聚类和粗糙集相结合的属性约简算法,从而避免了实型数据的离散化。
关键词：数据,粗糙集,属性约简算法
参考文献
[1]Chen Y,Zhu Q,Xu H.Finding rough set reducts with fish swarm algorithm[J].Knowledge-Based Systems,2015,81:22-29.
[2]唐孝,舒兰.基于粒计算的属性约简改进算法[J].计算机科学,2014(32).
基于FCM的模糊粗糙属性约简 篇5
关键词：模糊聚类,模糊粗糙集,决策表,属性离散化
在利用粗糙集理论进行属性约简之前, 必须对连续属性进行离散化, 这一过程将造成某种程度的信息损失, 这是因为离散化后的属性值没有保留属性值在实数值上存在的差异[1]。为解决粗糙集离散化过程中的信息损失问题, 法国学者D.Dubios和H.Prade将模糊集理论引入粗糙集中, 对信息系统中的对象不再进行离散化, 而讨论对象间的关系时也用对象的相似关系而非粗糙集中的等价关系[2]。正是由于模糊粗糙集理论引入了的模糊概念, 它易于保留连续属性值的信息, 因此使用该理论处理数据集更能保留原始数据集所包含的信息。相关研究表明[3,4,5,6,7], 应用模糊粗糙集得到的模糊规则或基于案例的推理系统以及原始数据集的约简比粗糙集具有更高的准确度。但目前属性模糊化方法需要人为地规定划分的类数, 几乎不考虑信息系统具体属性值的特征, 方法往往过于主观, 不够合理, 可操作性不强。
1模糊粗糙集及属性模糊化
1.1 模糊粗糙集的基本概念
定义1 一个决策表系统S=
定义2 如果R满足如下条件:
自反性 μR (u, u) =1, ∀u∈U
对称性 μR (u, v) =μR (v, u) , ∀u, v∈U
则称模糊关系R∈F (U×U) 为U上的模糊相似关系。
定义3 设X是一个非空集合, R是X上的一个相似关系, 且A∈F (X) 。一个模糊粗糙集是由X上两个模糊集组成的二元对 (R- (A) , R- (A) ) , 它满足:
对每个x∈X
undefined
1.2 模糊C均值聚类算法 (FCM)
令X={x1, x2, …, xn}⊂Rp是特征空间中一个有限数据集合;n是数据集合中的元素个数;c为样本的分类数, 2≤c≤n;Rc×n是所有实的c×n矩阵的集合;V={v1, v2, …, vc}⊂Rp为特征空间Rp上的矢量集合, 有c个聚类中心向量;μi (xj) 简记为μij, 表示第j个样本属于到第i个中心的隶属度;U=[uij]∈Rc×n是一个c×n矩阵。模糊C均值聚类分析的目标函数定义为:
undefined
(1) μij∈[0, 1], 1≤i≤c, 1≤j≤n;
undefined;
undefined。
其中:
undefined
式中:dij=‖xj-vi‖undefined, 1≤i≤c, 1≤j≤n, m∈[1, +∞]是一个加权指数;Jm是类内误差的加权平方和目标函数。FCM算法通过迭代入式 (2) , 式 (3) 以达到目标函数Jm的最小化, 此时得到X的一个最优模糊C划分:U* = [μ*ij]。
1.3 聚类有效性分析
对于给定的聚类数c和隶属度矩阵U, 聚类有效性函数定义为:
undefined
对于U∈Mfc的“最优”有限集合, 若存在 (U*, c*) 满足:
undefined
则 (U*, c*) 为“最优”的有效性聚类;c*为最好的分类数目[8]。
1.4 复合属性模糊化
模糊粗糙集中, 复合属性A对论域U的划分可表示为:
undefined
式中:U/a是属性a对论域U划分形成的等价类集合;⨂算子定义为:
undefined
若A={a1, a2, …, an}, 则式 (6) 可以写成:
undefined
用
undefined
得到对象x∈U对该等价类的隶属度为:
undefined
为简单起见, 上式用Zadeh定义的min运算表示了模糊交运算。
2模糊粗糙属性约简算法
2.1 属性模糊依赖性分析
在模糊粗糙集中, 每个等价类都是模糊的, 它的上、下近似可以定义如下:
undefined
式中:Fi是一个模糊等价类;μX (x) 是对象x属于U上的任意模糊集合X的程度。
对于Fi∈U|C的模糊正域定义为:
undefined
式中:X是决策属性D的模糊等价类。
x∈U对模糊正域的隶属度为:
undefined
根据模糊正域的定义, 可以求出模糊粗糙集条件下决策属性D对条件属性集合C的依赖度:
undefined
2.2 属性约简算法
属性约简是指在保持决策表分类或决策能力不变的前提下, 删除冗余属性。可利用下面的定义来表示。
定义4 设C和D分别是决策表的条件属性集合和决策属性集合, 对于C的子集C′, 若满足:
(1) γC (D) =γC′ (D) ;
(2) 从C′中删除任何属性a后都有:
undefined
则称C′是C的相对于决策属性D的一个约简[9]。
根据上述定义设计下面的属性约简算法。首先取一个空集R, 依次把那些使得γR (D) 的增量达到最大的属性添加到集合R中来, 直到γR (D) 达到最大。输出决策表一个最小属性约简R。
算法流程如下:
1.R←{ }, γ′best←0, γ′prev←0;
2.do;
3.T←R;
4.γ′prev←γ′best;
5.∀x∈ (C-R) ;
6.if γ ′R∪{x} (D) >γ ′T (D) ;
7.T←R∪{x};
8.γ ′best←γ ′T (D) ;
9.R←T;
10.until γ ′prev=γ ′best;
11.return R。
3实例分析
实例1 为了证明此算法的有效性, 选择如表1所示的天气信息决策表, 该决策表有四个条件属性, 即{晴朗度指数 (a1) 、温度指数 (a2) 、湿度指数 (a3) 、风况指数 (a4) }取值均在[0, 1]之间, 一个决策属性{d} (d=0表示不出去游玩, d=1表示出去游玩) 。
采用模糊C均值聚类分别求取四个属性的模糊划分矩阵U。用聚类有效性函数分析结果如表2所示, 从表中可以得出, a1, a2划分成三类最有效;a3, a4划分成两类最有效。
利用模糊粗糙集的属性约简算法计算得出γC (d) =γC-{a3} (d) =0.799 8, 即属性a3对于决策属性d是冗余的。
实例2 玻璃识别数据库[10]。该数据库包含214条信息, 每条信息有9个条件属性 (1为折射率, 2～9分别为金属在其氧化物里的重量百分比, 全部是连续数值) C={c1, c2, …, c9}={Ri, Na, Mg, Al, Si, K, Ca, Ba, Fe}和1个决策属性d={玻璃类型}组成。用本文提出的方法进行约简, 计算得出γC (d) =γC-{c1, c3, c6, c9} (d) =0.421 8, 所以属性c1, c3, c6, c9对于决策属性d是冗余的。
4结语
基于FCM的模糊粗糙属性约简算法使用模糊C均值聚类算法模糊化连续属性, 通过聚类有效性分析自动确定最佳的分类数目, 克服了目前属性模糊化方法需要人为确定划分的类数、几乎不考虑信息系统具体属性值的缺点。该方法为解决粗糙集中连续属性的约简问题提供了一个有效的途径。
参考文献
[1]曾黄麟.粗集理论及其应用[M].重庆:重庆大学出版社, 1996.
[2]Dubois D, Prade H.Putting Rough Sets and Fuzzy Sets To-gether[Z].Dordrecht, 1992:203-232.
[3]Radzikowska A M, Kerre E E.A Comparative Study ofFuzzy Rough Sets[J].Fuzzy Sets and Systems, 2002, 126:137-156.
[4]Liang Hongli, Zhang Huaguang, Liu Derong.Roughness ofFuzzy Sets Based on Two New Operators[A].IEEE Inter-national Conf.on Fuzzy Systems[C].Piscataway, 2004:583-586.
[5]聂作先, 刘建成.一种面向连续属性空间的模糊粗糙约简[J].计算机工程, 2005, 31 (6) :163-165.
[6]Daniel S Yeung, Eric C C Tsang, John W T Lee, et al.Onthe Generalization of Fuzzy Rough Sets[J].IEEE Trans.onFuzzy Systems, 2005, 13 (3) :343-361.
[7]Martine De Cock, Chris Cornelis, Etienne E Kerre.FuzzyRough Sets:The Forgotten Step[J].IEEE Trans.on FuzzySystems, 2007, 15 (1) :121-130.
[8]高新波.模糊聚类分析及其应用[M].西安:西安电子科技大学出版社, 2004.
[9]范敬德, 沈中林, 于旭亮, 等.一种改进的基于模糊——粗糙集的属性约简算法[J].航空计算技术, 2007, 37 (2) :8-10.
一种属性约简新方法——修边法 篇6
属性约简,就是通过消除冗余属性和无关属性来缩小数据集规模,并保持和原数据集的概率分布基本一致,同时使得挖掘结果更易于理解。简言之,属性约简的基本作用是:降低属性空间维度;提高挖掘效率;提高分类准确率;提高结果可读性。[3]
1 粗糙集属性约简法的优缺点总结
针对高维数据集的属性约简,目前多数有效方法都是基于粗糙集的。粗糙集[3]是适合处理不确定性、不完整性和不精确性问题的数学理论,最初由波兰数学家Zdzisław Pawlak于1982年提出。该理论建立在分类机制基础上,将知识理解为对数据集的划分。
1.1 粗糙集的优点
粗糙集利用数据本身提供的信息,无须先验知识。粗糙集引入上、下近似和边界域等概念来刻画知识的不确定性,并且边界域中不确定元素数目是可计算的。粗糙集能处理不完备信息;能在保留关键信息的前提下对数据进行化简并求得知识的最小表达;能评估数据属性之间的依赖关系,揭示简单模式;能从经验数据中获取规则知识。[3]
1.2 粗糙集的缺点
实际应用中,粗糙集对象间的等价关系条件过分严苛,加之数据集里存在噪声、残缺和歧义数据,都会造成知识的遗漏或偏差。如下例:在数据集U中,E是条件属性集C上的等价类,含有10000个对象;F是决策属性集D上的等价类。基于一般的粗糙集模式,E属于F的边界域[4],不能对F做出肯定的推断,然而E中可能仅有一个对象不属于F,这也许是由于噪声导致的。该例反映出一般的粗糙集模式对噪声非常敏感[3]。而在现实应用中,数据集中有各类异常数据不可避免,因此一般的粗糙集模式在一定程度上限制了粗糙集的应用。
2 修边法介绍
2.1 修边法概述
修边法是在粗糙集基础上建立的一套改进的属性约简方法,其基本功能是在决策表中求取更准确、更有意义的属性重要度,它可以弥补粗糙集方法的缺陷,但又不丧失粗糙集的原有优势。本节论述的理论基础,请读者参阅文献[4-6]。
定义1:修边法的粗糙集定义
通过人为假设,将粗糙集中的边界域视为完全可定义的,即假设边界域中每个对象都明确属于某个划分,从而消除边界域,将粗糙集转化为精确集;然后再将假设后的精确集信息与粗糙集实际信息进行对比,求得二者之间的误差率。该误差率可取代粗糙隶属度,用于量化表示粗糙集的“粗糙度”。
定义2:修边法在决策表中的定义
通过人为假设,将决策表中的冲突域视为完全一致的,即假设冲突域中每个对象都明确属于某个决策类别,从而消除冲突,将冲突性决策表转化为一致性决策表;然后再将假设后的决策表信息与原决策表实际信息进行对比,求得二者之间的误差率。该误差率代表所缺失的条件属性的重要度。此定义可用于计算各项条件属性重要度。
修边法与普通粗糙集方法所求得的属性重要度存在偏差,前者保留了后者遗漏的部分信息,因此前者可以求得更准确的属性重要度。二者的计算成本在同一水平上。
2.2 修边法原理和步骤
1)边界域隶属度计算
决策表L=
显然在正域[4]中的对象满足μDB(x)=1,边界域中对象满足0<μDB(x)<1。
2)修边假设和修边误差
假设将粗糙集按照清晰集的方式明确划分,即∀x∈U,满足[x]B=[x]D,这样划分之后,再与粗糙集实际划分信息比较,必然产生误差。显然误差仅存于边界域中。为了使假设与实际之间的误差最小化,可用[x]B中势最大的子集[x]B⋃D所属类别来代表[x]B中全体对象的类别。若有多个子集的势最大且相等,可以任选其中之一所属类别为代表。
由此,可累计每个条件属性集下的等价类中被修边假设取代的对象数量,定义为局部修边误差。设U B={Ei|i=1,2,...,s},U D={Fj|j=1,2,...,t},x∈Ei,该误差可记为:
令μi=1-xm∈aEix(μDB(x)),则:
由于U可表示为在B上的划分,即:
因此全局修边误差记为:
定义修边误差率为:
3)属性重要度
决策表L=
其中εD(C-{a})表示若C中缺少a后,C对于D的修边误差率。w C,D(a)表示若C中缺少a后,因修边假设而被错误分类的对象在U中所占的比例。
总结wC,D(a)性质如下:
。因为即使条件属性C完全缺失,仍然可基于D的边缘分布,将U内所有对象分配到D中势最大的类别中去,而如此分类的错误率正是这里的假设误差率上限η。
若wC,D(a)=0,a相对于D可省。因为从C中去除a后,C-{a}的决策能力未减,原来可被准确分类的对象仍然能被准确分类。
若wC,D(a)≠0,a相对于D不可省。因为从C中去除a后,某些原来可被准确分类的对象不能再被准确分类了。故a为核属性。
若wC,D(ai)=wC,D(aj)=0,表示ai和aj均相对于D可省,但这并不意味着二者同时可省,这还要看wC,D(ai+aj)=0是否成立;若成立则二者皆可省,若不成立则仅可省略其中一项。选择不同属性进行省略的过程,也就是挑选属性约简的过程。
4)容错性讨论
上述方法依据wC,D(a)值是否为0来判断条件属性a是否核属性,该方法在理想环境中简便且合理。然而在现实环境中,数据集里可能充斥着错误元组,这些元组由于某种隐含的特异性(不像数据元组之间相互冲突那样显然)可能直接误导核属性的判断。修边法的这一缺陷实际上是沿袭了普通粗糙集方法属性约简的缺陷。
比如说,数据集中某个元组的决策属性值及其一项条件属性值恰巧同时出现偏差,而导致该元组与其它多数同类元组的决策分类不同,按照现有的修边法计算该项条件属性的重要度肯定大于0,但这或许仅仅是由于一个元组元组错误造成的,若据此就判断该项条件属性为核属性,未免过于草率了。如果大量条件属性都存在这种情况,那么它们都成了核属性而不能约简,属性约简过程就失去意义了。
因此在判断核属性的过程中,有必要给属性重要度设定一个阈值,来增强核属性判断的容错性。比如,可规定必须满足wC,D(a)≥τ=0.02的属性才能算作核属性。
5)属性权重
与普通粗糙集法一样,采用修边法计算条件属性重要度时,需讨论以下问题:对于核属性而言,属性重要度都是明确值;但对于非核元素来讲,属性重要度都是0,这只能说明这些条件属性单独可省,但无助于衡量它们对于决策属性的真实作用。这种作用随着属性约简结果的不同而变化。实际上,数据分析人员可从属性约简完备集REDD(C)中选出不同的属性约简redD(C),然后分别基于它们进行属性重要度计算和排序,唯有如此才能体现出这些条件下的非核属性对于决策属性的真实重要性。规则可以归纳如下:
∀ai,aj∈redD(C)=B,q=|B|,i,j=1,2,...,q,定义ai相对于约简B的属性权重:
6)在修边法中重新定义属性约简
L=
3 算法对比
以表1为例,分别用普通粗糙集方法和修边法进行计算,求取决策表的相对属性约简和属性重要度,揭示二者差异,对比二者优劣。
3.1 算法一:普通粗糙集方法
(3)可见CORED(C)={a1,a4},a2和a3可省,但并不意味二者同时可省。因为:
因此原决策表的全部属性约简结果为:
3.2 算法二:修边法
(2)可见CORED(C)={a1,a4},a2和a3可省但不同时可省,故决策表属性约简全部结果为:
redD(1)(C)={a1,a2,a4}或redD(2)(C)={a1,a3,a4}
在约简red(1)中,wred(1),D(a1)=2 7,wred(1),D(a2)=1 7,wred(1),D(a4)=1 7。
在约简red(2)中,wred(2),D(a1)=2 7,wred(2),D(a3)=1 7,wred(2),D(a4)=1 7。
3.3 两种算法比较
算法二与算法一相比,增加了计算的步骤,计算成本并无显著提高。二者求得一致的约简结果,但属性重要度不同。例如在普通粗糙集方法中,约简red(2)中各属性重要度归一化可求得属性权重为:0.47:0.29:0.24;而在修边法中,同样将约简red(2)中各属性重要度归一化求得权重为:0.5:0.25:0.25。由此可见,理论基础决定了采用修边法可以求得比普通粗糙集方法更有意义的属性权重。
3.4 属性权重的用途和意义
充分理解修边法中的属性权重意义后,可发现它在一些场合能够发挥重要作用。
例如在聚类分析中需要计算相异度,人们通常假设在各维尺度均匀的欧式空间中计算距离,显然这是不精确但又无奈的选择。为了体现每个维度在距离分量上的重要性,更合理的处理方式是为每个维度设定权重。然而在聚类之初,人们并不知道每个维度属性所应占据的权重,因此这种想法难以实施。通过修边法求得的属性权重在此有用武之地,它比仅仅依赖专家主观裁定的经验权值客观,又比其他客观赋权法容易获取。需要注意:利用属性权重赋权需理解其适用场合,其合理性和具体算法有待进一步讨论。
4 结束语
修边法是一种简便易操作的属性约简方法,它可以充分发挥普通粗糙集属性约简算法的优势,同时避免部分缺陷。
当然,修边法也不可能解决高维属性约简时的NP难题[7]。在高维约简问题中,修边法可以作为初步处理的手段,首先明确选出属性集中所有的核属性及其相应的属性重要度,然后在非核属性集合中再采用例如基于可辨识矩阵法[8]的启发式方法进一步作约简处理,这样往往可以起到事半功倍的作用。因为对于非完备数据集或包含冲突的决策表来说,如果直接采用可辨识矩阵进行属性约简,通常会导致严重错误的结论,可辨识矩阵对于决策表中某些隐性错误或误差表现得非常敏感。
参考文献
[1]Dash D,Liu H,Yao J.Dimensionalty Reduction of Unsupervised Data.In Proc.9th IEEE Intl.Conf.on Tools with AI[C],IEEE Com puter Society,1997:532-539.
[2]Liu H,Motoda H.Feature Extraction,Construction,and Selection:A Data Mining Perspective[M].Kluwer Academic Publishers,1998.
[3]张兴会.数据仓库与数据挖掘技术[M].北京:清华大学出版社,2011.
[4]Pawlak Z.Rough sets[J].International Journal of Computer and Information Sciences,1982(11):341-356.
[5]Pawlak Z,Skowron A.Rough Membership Function.In:R.E Yeager,M.Fedrizzi and J.Kacprzyk(eds.),Advaces in the Dempster-Schafer of Evidence,Wiley,New York,1994:251-271.
[6]Pawlak Z.Rough Sets,Decision Algorithms[C].In:W.Ziarko,Y.Y.Yao.Second International Conference,Rough Sets and CurrentTrends in Computing,RSCTC 2000,Banff,Canada,October 2000:30-45.
[7]陈文伟.数据仓库与数据挖掘教程[M].2版.北京:清华大学出版社,2011.
一种改进的属性值约简算法 篇7
粗糙集理论的数据约简包括属性约简和属性值约简[1],在进行属性值约简之前必须先进行属性约简。目前,静态的属性约简算法主要有两类:一类是基于信息嫡的算法,该算法的基本思路是先计算出核,而后根据其它属性的重要程度依次在核的基础上添加属性或者根据决策属性对条件属性的依赖程度依次剔除掉那些对分类不产生影响的属性;另一类是基于可辨识矩阵和可辨识函数构造的属性约简算法[2],此算法的基本思路是利用可辨识矩阵[3]导出可辨识函数,然后求解差别函数的析取范式,该范式中的每一个析取项即为系统的一个约简。
1 值约简的已有方法
粗糙集中常见的值约简算法是建立在值核的基础之上的,约简算法主要步骤如下:
Stepl:对经过属性约简后的信息系统的每个个体删除多余的条件属性值,从而得到该个体的值核。条件属性值删除过程分两种情况处理:若删除属性值后信息表中的个体发生不一致[3],则保留该个体的被删除属性;若个体未发生不一致,则删除该属性。
Step2:由得到的值核表求出最小约简。
2 改进的值约简算法
在现有的算法中,只考虑了删除某条个体的某个属性后在剩余的信息表中有重复个体这一情况,对于没有重复的个体的情况则没有考虑。本文提出了一种改进算法。
删除个体后可能出现三种情况:①决策不一致;②出现重复个体但未发生决策不一致;③未出现重复个体且未发生决策不一致。因此改进后算法步骤如下:
Step1:对经过条伴属性约简后的信息表中各条件属性逐列进行扫描。若删除某个体的某个条件属性后出现不一致个体,则保留该属性值;若有重复个体但未产生不一致,则将该重复个体的属性值记为“T”;未出现重复个体且未发生决策不一致,则将该个体的属性值记为“F”。
Step2:删除所有值为“T”的个体。
Step3:如果出现相同决策个体且其中有一个或几个个体的某些属性值为“T”,则令一个个体对应的属性值恢复为原值;如果个体间其它属性值对应相等,则删除含“T”更少的个体。此时得到值核表。
实例
对表一进行属性值约简
先对信息系统进行属性约简,得到表二。
下面采用改进后的属性值约简算法对表二进行值约简。第一步对信息系统中的条件属性逐列进行扫描,修改属性值。以X2为例。当删除属性a时,信息系统中无重复个体也未出现不一致,则将X2的属性a的值置为“F”;当删除属性b时,X2与X4发生不一致,则将X2的属性b恢复原值;当删除属性d时,X2和X3产生重复但不不一致,则将X2的属性d置为“T”。对U={X1,X2,X3,X4,X5,X6,X7}依此扫描处理之后,可以得到表三。
对于表三执行算法Step3,首先扫描条件属性值为“F”的个体。对于X2,由于XI和X2的属性b都为0,所以将XI、X2的属性a的值还原为1;对于X4,仅凭b=l就可将其与其它个体区分开来,所以将X4的属性a、d都置为“T”;同理可处理X1、X5。而对于X6、X7,则应将“F”还原,据此可得表四。
根据算法Step4的规则,X6和X7只有一个属性值不同,且X6可由X7的规则判断出,所以删除X6,最后删除表屮所有重复个体后,最终的决策表如表五。
3 结束语
改进后的值约简算法对原方法不足之处进行了完善,从而提高了值约简的效率,但是其仍然有不足之处。此算法只适用于条件属性较少的决策表的约简。
参考文献
[1]Pawlak Z.Rough Sets-Theoretical Aspects of Reasoning About Data[M].Kluwer Academic Publishers, 1991:68-162.
[2]J W Guan,D A Bell.Rough Computaional Methods for information Systems.ArtiFicial Intelligence,105 (1998):77-103.
粗糙集属性约简的一种新算法 篇8
关键词：粗糙集,属性约简,属性重要度
粗糙集(Rough Set)理论[1]是一种处理不确定、不完整知识的数学工具,最早是由波兰数学家Z.Pawlak于1982年提出的.。现在它广泛应用于数据挖掘、智能控制、模式识别等领域[2,3]。属性约简是粗糙集理论中的核心内容之一,有许多学者致力于粗糙集属性约简算法的研究[4,5]。人们总希望得到最佳的约简结果。然而Wong.S.K.M和Ziarko.W已经证明它是一个NP-HARD问题[6]。目前,以属性重要度作为启发式信息的属性约简算法是人们研究的重点。本文首先定义了一种新的属性重要度,在此基础上,定义了粗糙集属性约简的一种新算法。另外粗糙集的属性约简结果一般不是唯一的,可能同时存在多种约简。目前,许多属性约简算法将约简结果的标准定为约简后属性数最少,或者是得到的规则最简,或约简量最大[7]。但是属性子集的各个属性之间的相关性也是很重要的。基于这些看法,本文用属性相关性[8]衡量属性集中属性间的相关性,平均相关性最小的属性集即为最终的约简结果。
1 相关概念
定义1[9]称四元组IS=(U,A,V,f)是一个信息系统,其中U={x1,x2,…,xn}为对象的非空有限集合,称为论域;A为非空有限集,其中A=C∪D,C∩D=φ,C={a:a∈C}称为条件属性集,每个aj∈C(1≤j≤m)称为C的一个简单属性,D={d:d∈D}称为决策属性集;
是信息函数f的值域,而Va表示值域;表示信息函数,fa为属性a的信息函数。
定义3[9]设给定一个信息系统,定义,为属性a对属性集B的重要度。
定义4[10]给定一个信息系统IS=(U,A,V,f),a,b∈A,a,b间的属性相关性定义为:,
r(a,b)关于属性a,b对称,r(a,b)∈[0,1],r(a,b)的值越大,则属性a,b之间的相关性越强。r(a,b)值得大小从客观上反映了关于属性a和属性b划分的等价类之间的相互逼近程度。
定义5设IS=(U,A,V,f)是一个信息系统,属性子集P哿A。则分类能力表示为C(P),定义为:。定理1设IS=(U,A,V,f)是一个信息系统,属性子集P哿Q哿A,如果,则C(P)
此定理说明,随着属性的增加,划分越来越细,分类能力越来越强。由此定理进一步得到下面的结论。
定理2设IS=(U,A,V,f)是一个信息系统,属性子集P哿Q哿A,则U/IND(P)=U/IND(Q)得充要条件是C(P)=C(Q)。
2 信息系统中属性的重要度
分类能力可以用来分析信息系统中每一个属性的重要性。在信息系统IS=(U,A,V,f)中,设a∈A是某一属性,用由A中去掉a后引起的分类能力的变化的大小来衡量属性a对A的重要度,如果去掉属性a后,分类能力变化越大,则认为a对A越重要。
定义6设IS=(U,A,V,f)是一个信息系统,P哿A,a∈P,属性a在P中的重要度表示为:sigP-{a}(a),定义为:。容易得到以下性质:
性质1。
性质2属性a∈P在P中是必要的当且仅当sigP-{a}(a)>0。
性质3。
设IS=(U,A,V,f)是一个信息系统,P哿A是属性子集,a∈A-P是任一属性,用由P中添加属性a后引起的分类能力的变化大小来衡量属性a对P的重要性,类能力变化越大,则认为a对P越重要。
定义7设IS=(U,A,V,f)是一个信息系统,P哿A是属性子集,a∈A-P是任一属性,则a对P的重要度表示为:sigP(a),定义为:
。
以上内容实际是从分类能力的角度提供了一种属性约简的判断方法,在此基础上,给出一种基于分类能力的属性约简算法。
3 一种基于分类能力的属性约简算法
本节利用分类能力的概念,讨论信息系统属性约简的问题。基本思路是:用属性重要度作为启发式信息,先根据文中定义的重要度求出属性集A的核core(A),在此基础上,逐个添加最重要的属性到core(A)中去,直到分类能力不在发生变化为止,由此便得到信息系统IS=(U,A,V,f)的最小约简。
信息系统的属性约简算法:
输入:信息系统IS=(U,A,V,f)。
输出:该系统的一个最小约简。
第1步计算核core(A)。对于每个属性a∈A,计算a在A的重要度sigA-{a}(a),所有使属性sigA-{a}(a)>0的属性子集构成核core(A)。
第2步red(A):=core(A)。
第3步判断C(red(A))=C(A)是否成立,成立,转第6步,否则执行第4步。
第4步计算a∈A-red(A)对于red(A)的重要度,使得:。若满足条件的a有多个,则选取划分个数最少的属性。
第5步red(A):=red(A)∪{a},转第3步。表1信息函数
第6步输出该信息系统的最小约简red(A),终止。
4 实例分析
给定信息系统IS=(U,A,V,f),其中U={x1,x2,x3,x4,x5},A={a1,a2,a3,a4},信息函数由表一给出。
第1步计算core(A)。由于
所以。所以core(A)={a2}。
第2步red(A):=core(A)={a2}。
第3步C(red(A))≠C(A),执行第4步.
第4步计算关于red(A)的重要度:
所以。既a3是使分类能力变化最大的属性。
第5步,且,此时C(A)=C(red(A))成立,则red(A)为该信息系统的一个约简。转第6步。
第6步输出最小约简red(A)={a2,a3},算法终止。
至此,我们求出了该信息系统的最小约简。
5 一种得到最终约简的方法
众所周知,粗糙集属性约简的结果并不是唯一的,它可能存在多种约简结果。在实际应用中,从多个约简结果中找出比较合适的一个,是一个值得研究的问题。目前,许多属性约简算法将约简结果的标准定为约简后属性数最少,或者是得到的规则最简,或约简量最大[7]。但是属性子集的各个属性之间的相关性也是很重要的。基于这些看法,本文用属性相关性[8]衡量属性集中属性间的相关性,平均相关性最小的属性集即为最终的约简结果。
例1给定一个知识库K=(U,S),其中,论域为U={x1,x2,…x8},S={R1,R2,R3},等价关系R1,R2,R3和IND(S)对应的等价类分别为:
用基于Pawlak属性重要度的属性约简算法[9]得到的最终约简结果是{R1,R2}和{R1,R3}。这两个属性约简结果哪一个比较好呢?从关系数据库的角度考虑[11],属性约简的各个属性之间应该有比较小的依赖关系,基于这个观点,文献[9]提出应对属性约简继续求得各个属性间的相关性,平均相关性最小的属性集合将作为求得的最佳属性约简,并用条件熵来求得平均相关性。本文在属性相关性定义的基础上,提出用属性相关性代替条件熵来衡量属性间的相关性。属性相关性小的即为最终约简结果。此方法不仅减少了计算量,并且更能体现出属性间的关系。上例中,由定义4可得:r(R1,R2)=1/2,r(R1,R3)=3/4,从而得最终的属性约简结果为{R1,R3}。
6 总结
首先,本文在粗糙集有关知识的基础上,定义了一种新的属性重要度,并在此基础上,提出了一种新的粗糙集属性约简算法,并用实例证明此算法是切实可行的。
其次,提出一种用属性相关性得到最终约简结果的方法,在实际应用中,此方法可以从众多的属性约简结果中找出最好的属性约简。
参考文献
[1]Pawlak Z.Rough Sets[J].Int J Computer&Science,1982,11(5):341-356.
[2]Pawlak Z.Rough Sets Theory and It's Applications to Date Analysis[J].Cybernetnetics&Systems,1998,29:661-688.
[3]Aijun Anetal.Applying Knowledge Discovery to Predict water supply Consumption[J].IEEE Expert,1997:72-78.
[4]苗夺谦,胡桂荣.知识约简的一种启发式算法[J].计算机研究与发展,1999,36(6):681-684.
[5]庄静芸,徐中伟,喻钢.一种粗糙集属性约简算法[J].计算机工程,2009(8).
[6]Wong S K M,Ziarko W.on optional decision rules in decision tables[J].Bulletin of polish Academy of Science,1985,33:693-696.
[7]常犁云,王国胤,吴渝.一种基于Rough Set理论的属性约简及规则提取方法[J].软件学报,1999,10(11):1206-1211.
[8]张静,王建民,何华灿.基于属性相关性的属性约简新方法[J].计算机工程与应用,2005(8).
[9]苗夺谦,李道国.粗糙集理论算法与应用[M].北京:清华大学出版社,2008.
[10]李侃,刘玉树,王蕾.一种属性约简算法[J].计算机工程与应用,2002(5).