不完备信息系统中基于限制容差关系的属性约简方法
开篇：润墨网以专业的文秘视角，为您筛选了一篇不完备信息系统中基于限制容差关系的属性约简方法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要:决策表核属性的确定往往是信息约简的基础，然而以往的核属性约简方法大多是针对完备信息系统的。将完备信息系统中的属性核与属性序约简算法延伸至不完备系统，提出一种不完备信息系统中基于限制容差关系的属性约简方法。该方法通过构造限制容差关系下决策表的改进分辨矩阵来求得核属性，并将非核属性按直观影响分类质量的能力排序，能够保证得到的约简结果是相对最小约简。通过实验比较证明该方法可行、有效。
ス丶词:不完备信息系统；属性约简；限制容差关系；核属性
ブ型挤掷嗪: TP18;TP311.13 文献标志码:A
Abstract: The confirmation of core attribute of a decision table is always the basis of information reduction. However, most of the previous reduction methods in core attribute are for complete information system. Extending the reduction algorithm in core attribute and attribute order to incomplete information system, which was used in complete information system, this paper presented an attribute reduction algorithm based on limited tolerance relation in incomplete information system. This method obtained core attribute by constructing an improved discernable matrix of decision table in incomplete information system, and sorted the attributes which did not belong to core attribute by ability of affecting classification quality intuitively. Thus, the reduction result was ensured to be a relatively minimized reduction. This method is proved to be feasible and more effective through comparison.
Key words: incomplete information system；attribute reduction； limited tolerance relation；core attribute
0 引言
属性约简一直是Rough集理论研究的核心内容之一［1-2］。在完备信息系统中，属性约简技术已经取得巨大的成功，然而现实生活中，由于缺失、遗漏信息的存在，信息系统往往是不完备的，如何在不完备的环境下进行属性约简具有更强的实践意义［3-4］。近年来，基于不完备信息系统的约简方法也受到了越来越多的关注：文献［5］中分析了不完备系统中约简的判定条件，并给出了一种直接约简算法；文献［6］从信息熵的角度介绍了一种基于信息熵的不完备系统属性约简方法；文献［7］以相似关系作为不分明关系，以属性重要度为启发提出了一种基于相似关系的属性约简方法。然而以上这些文献都是以空集开始逐步添加属性求取约简的，没有能够利用核属性集，浪费了大量的计算时间。王国胤指出决策表核属性的确定往往是信息约简的基础［8］，这是因为：属性核中的所有属性在系统的任何约简结果中都是必须的，否则系统的分辨关系就得不到保证。通常的属性核计算方法只适用于完备信息系统，这是因为分辨矩阵中选取了等价关系作为不分明关系，如果要将属性核算法延伸至不完备系统中，需要对分辨矩阵做出改进。
文献［9］定义了一个不完备系统下的相似矩阵用于求取决策表属性核，以折半查找的思想给出了一种属性约简算法，该方法能够较快速地求出约简，但是并不能够保证求出的结果是相对最小约简，原因在于其选取的不分明二元关系［10］与非核属性序的确定［11］存在不足：王国胤在文献［12］中通过实验证明了限制容差关系比相似关系、容差关系更适合作为扩充Rough集模型下的不分明二元关系。
基于此，本文提出了一种不完备系统中基于限制容差关系的属性约简方法，该算法将完备系统下的属性核与属性序约简方法扩充至不完备系统中，通过构造改进的分辨矩阵，并将非核属性按直观影响分类质量的能力排序，确保能够得到相对最小约简。理论分析和实验证明了本文算法的有效性和可行性。
1 基本概念
定义1 不完备决策表［2］。Ь霾弑硎且桓鲇行虻乃脑组S=〈U,A,V, f〉，其中，U是对象的集合，A=C∪D是属性集合，C和D分别称为条件属性集和决策属性集，D≠ВV是属性集A的值域，f:U×AV是从属性到值域的映射。オ
如果对于至少存在一个属性a∈C，Va包含空值，即f(x,a)=*，则称此决策表是不完备的。具有遗漏属性值的属性子集BA，记遗漏值为*。オ
定义2 限制容差关系［2］。假定不完备信息系统S=〈U,A,V, f〉及U上定义的二元关系L(限制容差关系)，BA，令PB(x)={b|b∈B∧b(x)≠}，则歇x,y∈U×U(LB(x,y)讵歇b∈B(b(x)=b(y)=*)∨((PB(x)∩PB(y)≠)∧歇b∈B((b(x)≠*)∧(b(y)≠*)(b(x)=b(y)))))，显然限制容差关系L具有自反性、对称性，但不具有传递性。由此我们可以继续定义限制容差类ILB(x)={y|y∈U∧LB(x,y)}，相应的上、下近似集定义如下オ
DBL={x|x∈U∧ILB(x)∩D≠}オ
DLB={x|x∈U∧ILB(x)D}オ
定义3 一致性决策表［9］。不完备信息系统S中，设U/IND(D)={Q1,Q2,…，Qr}表示决策属性D对U的划分，U/IND(B)={B1,B2,…，Bm}表示条件属性集B对U的覆盖，称POSB(D)=┆∪Q∈U/DDLBQ为B关于D的正区域。在限制容差关系下，当且仅当POSB(D)=U时，不完备决策表为一致性决策表；如果POSB(D)U，则不完备决策表是不一致的。如果没有特别说明，本文所涉及到的算法对于一致决策表和不一致决策表都是适用的。オ
定义4 近似分类质量［9］。不完备信息系统S中，设U/IND(D)={Y1,Y2，…,Yk}，BC，则B相对决策属性D的分类质量定义为：γB=card(POSB(D))/card(U)，card()表示集合的基数。オ
定义5 约简与核［9］。设不完备决策表S=〈U,A,V, f〉，RC，如果γR=γC，并且不存在R′R使得γR′=γR，则称R是C的相对于决策属性D的一个属性约简。所有C相对于D的属性约简的交称为C相对于决策属性D的核，记为CORED(C)。オ
2 限制容差关系下核属性的计算方法
2.1 限制容差关系下不完备信息系统的改进分辨矩阵
首先，对于限制容差关系下的不完备决策表，可以对其定义一个改进的分辨矩阵：
MLC={mLC(xi,xj)}n×n； 1≤i,j≤n=|U|(1)お
式中：
mLC(xi,xj)=
f(a1)f(a2)…f(a|C|),d(xi)≠d(xj)
,其他 И
其中：
f(ak)=
1, ak(xi)≠ak(xj)≠唱
0, ak(xi)=ak(xj)≠唱
*, ak(xi)=*∨ak(xj)=
*∨ak(xi)=ak(xj)=* お
式中1≤k≤|C|。可以看出mLC(xi,xj)Т表的是决策属性值不相等的两个对象在条件属性上取值的差异。通过研究分析该矩阵，可以得到如下定理。
定理
在基于限制容差关系分辨矩阵中，ИmLC(xi,xj)，如果有且只有一个条件属性b,使得f(b)=1，并且使得xi与xj在其他属性值上满足限制容差关系，即LC\b(xi,xj)，则该属性b一定属于核属性。オ
证明
根据限制容差关系的特性，不妨分为下面三种情况来讨论：
1)如果xi与xj不存在一个条件属性，使得xi、xj在该属性上同时取得非空值,即f(ak)=*(1≤k≤|C|)。如果xi与xj不满足限制容差关系，那么xi与xj就是可以分辨的，我们可以认为xi与xj在某些属性上的取值是不一样的，但是不一样属性的个数是不明确的，因此在这种情况下不可能获得核属性。オ
2)如果xi与xj存在两个以上的条件属性，使得xi、xj在这些属性上同时取得相异的非空值。显然，xi与xj不满足限制容差关系，那么xi与xj就是可以分辨的，是靠两个以上的属性同时把它们区分开的，因此在这种情况下也不能够得到核属性。オ
3)当xi与xj只在一个条件属性b上取得相异的非空值，即f(b)=1时。如果xi与xj在其他条件属性上不可分辨，那么就满足LC\b(xi,xj)，所以b就是唯一能够把xi、xj分辨开来的属性。实际上，xi与xj最初在条件属性上是能够分辨的，但是去掉属性b之后使得xi、xj变得不可分辨了，这样一来决策表在除去b的条件属性上的分类质量就降低了，即γC\b(S)
2.2 限制容差关系下核属性求取算法
根据定理，就可以给出限制容差关系下运用分辨矩阵求取核属性的算法(以下简称算法1)。
输入：一个不完备的决策表S=(U,C∪D,V, f)；オ
输出：决策表SУ暮耸粜浴＊
步骤1 计算限制容差关系下决策表的分辨矩阵MLC；オ
步骤2 选出有且只有一个属性满足f(b)=1的元素mLC(xi,xj)；オ
步骤3 判断xi与xj是否满足LC\b(xi,xj)，如果满足，则属性b为核属性，否则b不是核属性。オ
2.3 算法复杂度分析
通过计算，得到分辨矩阵MLC的时间复杂度为O(|U|2)，步骤2、3的时间复杂度也都为O(|U|2)，所以算法的时间复杂度为O(|U|2)；算法初始所需要的空间为|U|×|C|，计算分辨矩阵时需要一个辅助空间|U|2×|C|，所以算法的空间复杂度O(|U|2×|C|)。オ
下面用一个实例来说明算法的有效性。从表1［2］中可以看出mLC(a4,a6)中有且只有f(c2)=1，并且有LC\c2(a4,a6)，所以c2为表1的核属性。另外，在mLC(a1,a9)中只有f(c4)=1，并且有LC\c4(a1,a9)，所以c4也是表1的核属性。表1的属性核就为COREd(C)={c2，c4}。オ
3 限制容差关系下非核属性序的度量方法
3.1 限制容差关系下核属性的进一步研究
文献［5］指出：在限制容差关系下对不完备决策表进行属性约简时，不能依照正域的不变作为约简条件，而应该以近似分类质量不降低这一要求进行约简。核属性集是一个决策表中所有约简的交集，同时是唯一能区分某些记录的属性，所以在不完备信息系统下它应该是含有最大确定性信息量的属性集。因此，Е锚COREd(C)(S)≥γC(S)。如果γCOREd(C)(S)=γC(S)，说明决策表Sг诤耸粜陨匣竦玫娜范ㄐ孕畔⒂朐谡个条件属性集上获得的确定性信息一样多，也就是说其他属性对于决策表来说是冗余的，因为它们不能够提供确定性信息使得决策表的分类质量提高，也不会影响不确定性使得决策表的分类质量降低。这时的核属性即是决策表SУ脑技蚪峁。以表1为例，我们求得了它在限制容差关系下的属性核COREd(C)={c2，c4}，并且γCOREd(C)(S)=γC(S)=25%，说明{c2，c4}就是表1在限制容差关系下的一个约简结果；而当γCOREd(C)(S)>γC(S)时，说明在求属性核的过程中间消除了一些不确定的信息，使得决策表的分类能力得到了提升，也就是说在非核属性中保留着决策表原始分类的不确定性，这部分中的某一些属性对于约简来说是必要的。
3.2 非核属性的排序方法
通过上面的分析可以了解到，如果决策表在核属性上的分类质量比初始分类质量高，说明某些非核属性对于约简来说是必须的。为了将这些属性挑选出来，需要先将非核属性排序:计算每一个非核属性所在列含有的不确定值的个数，按照含不确定值的多少从大到小将非核属性排序，如果某两个属性所含不确定值个数相等，则按照其属性序号排序，У玫脚判蚝蟮姆呛耸粜约UC={c′1c′2…c′m}(1≤m≤|c|)。Ы非核属性如此排序，实际上是为了保证决策表分类质量在直观上沿着梯度方向下降到初始分类质量，因为先选取的非核属性相对于核属性含有的不确定信息应该是最多的，将它加入约简当中能使得决策表的分类质量更快地接近初始分类质量。应该注意的是，将某个非核属性加入约简中有可能使决策表分类质量下降到初始分类质量之下，这样的属性相对核属性含有过大的不确定信息，其一定不是必要的约简属性。
4 限制容差关系下的基于属性核的约简算法
4.1 算法描述
下面给出限制容差关系下的基于属性核的约简的具体算法(以下简称算法2)描述。
程序前
输入：一个不完备的决策表S=(U,C∪D,V, f)；И
输出：Sг谙拗迫莶罟叵迪碌脑技蚪峁R。И
步骤1 首先根据算法1计算出S的属性核COREd(C)，并令R=COREd(C)；И
步骤2 计算决策表S在条件属性集上的分类质量γC(S)和在COREd(C)上的分类质量γCOREd(C)(S)，如果γCOREd(C)(S)=γC(S)则转向步骤5，否则转向步骤3；И
步骤3 将非核属性按照3.2节的方法排序，У玫UC={c′1c′2…c′m}(1≤m≤|c|)；お
步骤4
for(i=1；i
{
Ъ扑悝锚R∪ci′(S)；И
if(Е锚R∪ci′(S)>γC(S))
{if(Е锚R∪ci′(S)==γR(S))И
R=R；お
else if(Е锚R(S)>γR∪ci′(S))
R=R∪ci′;お
}
else if(Е锚R∪ci′(S)==γC(S))
{R=R∪ci′；break;}
else R=R;お
}
步骤5 结束程序，R即为所求的约简结果。
程序后
4.2 算法复杂度分析
Ъ扑愫耸粜缘氖奔涓丛佣任O(|U|2)，如果采用冒泡排序，非核属性排序的复杂度为O(|C|2)，通常情况下|U|愍|C|，所以算法的时间复杂度为O(|U|2)。 由于没有额外的空间开销，算法的空间复杂度依然是O(|U|2×|C|)。オ
5 算法实例分析
本文以文献［9］中的实例为例，通过分析该决策表在限制容差关系下的约简过程与结果，并与文献［9］中的方法比较从而证明本文算法的优越性。
表2为一个给定的不完备信息决策表S=(U,A,V, f),其中论域U={a1,a2,…,a11,a12}，A={c1,c2,…,c8,d}，条件属性C={c1,c2,…,c7,c8}，决策属性D={d}。オ
步骤1 г擞盟惴1计算出表2的属性核：通过计算限制容差关系下表2的分辨矩阵MLC，可以发现mLC(a1,a4)和mLC(a1,a5)中都只有f(c6)=1并且有LC\c6(a1,a4)和LC\c6(a1,a5)，所以条件属性c6是表2的核属性；同时，mLC(a2,a6)中只有f(c4)=1并且有LC\c4(a2,a6)，所以c4也是表2的核属性。因此，表2的属性核COREd(C)={c4，c6}，令R=COREd(C)。
步骤2 计算表2在条件属性C上的分类质量γC(S)=33.3%，在COREd(C)上的分类质量γCOREd(C)(S)=66.7%，因为γCOREd(C)(S)>γC(S)，所以转向步骤3。
步骤3 将表2中的非核属性排序，得到UC={c3,c1,c5,c7,c2,c8}。
步骤4 进行循环操作：第一次循环计算出γR∪c3(F)=7/12=58.3%，因为γC(F)
文献［9］中采用折半查找算法在约简速度上固然提高了，但是并不能保证找到的结果是最小约简。在容差关系下，我们可以算得Е锚{c3,c4,c5,c6,c8}(S)=γ{c1,c3,c4,c5,c6,c8}(S)，д馑得鳘c1б彩强梢栽技虻氖粜浴3鱿终庵窒窒笤因在于对属性的重要度度量的过程中主观性偏大，缺少对属性中含有不确定信息量的分析。而本文算法选用比容差关系更适合的限制容差关系作为不分明二元关系，通过构造改进的分辨矩阵求取属性核，将非核属性按其直观影响分类质量的能力排序，以初始分类质量为约束条件进行约简，从而避免了文献［9］中现象的发生，能够保证所求得的约简为相对最小约简。
6 结语
计算属性核的过程往往是属性约简的初始化，属性核约简算法较之其他约简算法能够节省大量的计算时间。本文通过构造一种改进的分辨矩阵，将完备信息系统下的属性核约简算法延伸至不完备信息系统，提出了一种不完备信息系统中基于限制容差关系的属性约简方法。通过实验证明该方法计算简单、快捷，能够保证求得的约简结果为相对最小约简。然而算法的复杂度相对较高，如何降低复杂度将是下一步工作的重点。
げ慰嘉南:
[1] PAWLAK Z. Rough sets［J］.International Journal of Computer and Information Sciences, 1982, 11(3):341-356.お
[2] 王国胤.Rough集理论与知识获取 ［M］. 西安：西安交通大学出版社，2001.
[3] LEUNG Y, WU WEIZHI, ZHANG WENXIU. Knowledge acquisition in incomplete information systems: a rough set approach［J］. European Journal of Operational Research, 2006, 168(2): 164-180.
[4] KRYSZKIEWICZ M. Rough set approach to incomplete information systems［J］. Information Sciences, 1998, 112(1/4):39-49.
[5] 黄海，王国胤，吴渝.一种不完备信息系统的直接约简方法［J］.小型微型计算机系统，2005, 26(10)：1761-1765.
[6] 付昂，王国胤，胡军.基于信息熵的不完备信息系统属性约简算法［J］.重庆邮电大学学报:自然科学版，2008, 20(5)：586-592.
[7] 杨霁琳，秦克云，裴峥.不完备决策表中基于相似关系的属性约简［J］.计算机工程，2010, 36(20)：10-12.
[8] 王国胤.决策表核属性的计算方法［J］.计算机学报，2003,26(5)：611-615.
[9] 鄂旭，邵良杉，周津，等.一种新的不完备信息系统属性约简算法［J］. 重庆邮电大学学报：自然科学版，2010，22(5)：648-651.
[10] STEFANOWSKI, TSOUKIAS A. On the extension of rough sets under incomplete information ［C］// Proceedings of the 7th International Workshop on New Directions in Rough, Data Mining, and Granularsoft Computer. Berlin: SpringerVerlag, 1999:73-81.
[11] HAN SUQING, WANG JUE. Reduct and attribute order［J］. Journal of Computer Science and Technology, 2004, 19(4):429-449.
[12] 王国胤.Rough集理论在不完备信息系统中的扩充 ［J］.计算机研究与发展，2002,39(10)：1240-1243.