基于区分对象对的不完备决策表求核

曾艳燕，徐章艳，曾玲珍，张姣，宋腊香

1.广西师范大学计算机科学与信息工程学院，广西桂林 541004

2.江西蓝天学院商学院，南昌 330029

3.鄂州市高级中学，湖北鄂州 436000

基于区分对象对的不完备决策表求核

曾艳燕1，徐章艳1，曾玲珍2，张姣1，宋腊香3

1.广西师范大学计算机科学与信息工程学院，广西桂林 541004

2.江西蓝天学院商学院，南昌 330029

3.鄂州市高级中学，湖北鄂州 436000

1 引言

属性约简是粗糙集理论的核心内容之一，而决策表中属性核的计算对解决属性约简这一核心问题具有极其重要的意义，他能有效缩小属性约简算法在属性空间的搜索范围，降低属性约简算法的复杂度，因此如何高效地求不完备决策表的核非常重要。近年来，许多学者对完备决策表的求核进行了研究，并取得了大量的成果[1-7]。然而这些经典的粗糙集求核方法在处理不完备决策表时仍存在一定的不足。对不完备决策表，Kryszkiewicz[8]提出容差关系，Stefanowski[9]等人提出非对称相似关系，王国胤[10]提出限制容差关系，文献[11-12]从知识粒度的角度对不完备决策表进行分析，他们都是在以上模型上对不完备决策表进行属性约简，然后在属性约简基础上对不完备决策表进行求核，时间复杂度为O(|C|2|U|2)，并不理想。直接对不完备决策表进行求核的算法很少，文献[13]从正区域的角度提出了求不完备决策表核的算法，文献[14]从二进制差别矩阵的角度提出了另一种对不完备决策表求核的算法。文献[6-7]中对完备决策表提出区分对象对集的定义，并在区分对象对的基础上对不完备决策表进行求核。然而，对不完备决策表，目前还没有人给出区分对象对的相应定义。于是本文对不完备决策表提出了基于差别矩阵的区分对象对集定义，并将求不完备决策表的核转化到求不完备决策表的区分对象对集上，相比于先求决策表的差别矩阵，再根据差别矩阵去求决策表的核的算法，本文算法所求出的区分对象对的个数通常远远小于差别矩阵的元素个数，大大减少了计算量，有效地降低算法的时间及空间复杂度。

2 粗糙集概念

3 相关定理

综上所述，命题成立。

综合定理2和定理3，说明了在不完备决策表中，求核可以转化到求基于差别矩阵的区分对象对集上。

4 计算正区域的方法

求正区域的计算时间主要花在计算容差类TC(x)(x∈U)上。一般来说，求容差类TC(x)的算法是：对对象集U中的对象进行两两比较，比较它们在C中的每个属性是否满足容差类的定义，若满足，则属于同一个容差类；或者对对象集U中的每个对象，根据其C的取值判断是否属于现有的容差类。在最坏的情况下，以上两种方法在每个条件属性下都需要O(|U|)2次比较，故最坏的时间复杂度为O(|C||U|2)[8]。文献[15]计算容差类TC(x)的算法时间复杂度降为又因为TC(xi)⊆U，所以O(K)≤O(|U|)。显然，该时间复杂度比一般的算法的时间复杂度O(|C||U|2)要低。

5 基于区分对象对集的求核算法

根据上述定义、定理和计算正区域的方法，下面给出基于区分对象对集的不完备决策表的求核算法。

算法求核算法

6 实例分析

为了更好地说明本文算法的有效性，以下面不完备决策表为例进行分析说明（如表1）。

表1 决策表

结合上述算法对该不完备决策表1进行求核：

7 结束语

本文首先引入了基于不完备决策表差别矩阵及其核的定义，然后给出基于差别矩阵的区分对象对定义。在此基础上，利用区分对象对的概念设计了一种对不完备决策表进行求核的算法。通过实例验证表明，该算法能有效地求得不完备决策表的核，为不完备决策表的属性约简提供了一种新方法。

[1]王国胤.Rough Set理论与知识获取[M].西安：西安交通大学出版社，2001：20-39.

[2]叶东毅，陈昭炯.一个新的二进制可辨识矩阵及其核的计算[J].小型微型计算机系统，2004，25（6）：965-967.

[3]徐章艳，杨炳儒，宋威.基于简化的二进制差别矩阵的快速求核算法[J].小型微型计算机系统，2006，27（9）：1711-1714.

[4]葛浩，李龙澍，杨传健.一种核属性快速求解算法[J].控制与决策，2009，24（5）：738-742.

[5]徐章艳，舒文豪，钱文彬，等.基于序关系的快速计算正区域核的算法[J].计算机科学，2010，37（7）：208-211.

[6]徐章艳，杨炳儒，宋威，等.基于区分对象对集的快速求核算法[J].系统工程与电子技术，2008，30（4）：731-734.

[7]徐章艳，杨炳儒，宋威.基于区分对象对集的高效属性约简算法[J].模式识别与人工智能，2006，19（5）：572-577.

[8]Kryszkiewicz M.Rough set approach to incomplete information systems[J].Information Sciences，1998，112（1）：39-49.

[9]Stefanowski J，Tsoukias A.Incomplete information tables and rough classification[J].Computational Intelligence，2001，7（3）：545-566.

[10]王国胤.Rough集理论在不完备信息系统中的扩充[J].计算机研究与发展，2002，39（10）：1238-1243.

[11]李秀红，史开泉.一种基于知识粒度的不完备信息系统的属性约简算法[J].计算机科学，2006，33（10）：169-170.

[12]徐久成，史进玲，孙林.一种基于相对粒度的决策表约简算法[J].计算机科学，2009，36（3）：205-207.

[13]李晓瑜，徐章艳，王炜，等.不完备信息系统中一种新的求核算法[J].计算机工程，2011，37（11）：56-58.

[14]曾艳燕，徐章艳，舒文豪，等.一种基于不完备决策表的求核算法[J].计算机工程与应用，2012，48（1）：135-137.

[15]Shu Wenhao，Xu Zhangyan，Ruan Shen.A quick attribution reduction algorithm dased on incomplete decision table[J]. Advanced Materials Research，2011，171/172：154-158.

ZENG Yanyan1,XU Zhangyan1，ZENG Lingzhen2,ZHANG Jiao1,SONG Laxiang3

1.School of Computer Science and Information Engineering,Guangxi Normal University,Guilin,Guangxi 541004,China
2.School of Business,Jiangxi Blue Sky College,Nanchang 330029,China
3.Ezhou Senior Middle School,Ezhou,Hubei 436000,China

The definition of discernibility object pair set of incomplete decision table,based on discernibility matrix,is defined. And it is proved that computing the core of incomplete decision table is equal to computing the discernibility object pair set of incomplete decision table.Then an algorithm for computing core based on discernibility object pair set of incomplete decision table is proposed.And the time complexity of the new algorithm ismax{O(K|C||U|)，O(|C||U||Upos|)},which is better than the time complexity of the same kind of algorithms.At last,an example is used to illustrate the efficiency of the new algorithm.

rough set;incomplete decision table;discernibility matrix;discernibility object pair set;compute core

在差别矩阵的基础上，针对不完备决策表提出了基于差别矩阵的区分对象对集定义，并证明求不完备决策表的核可以转化到求基于差别矩阵的区分对象对集上。在此基础上，提出了一种基于区分对象对的不完备决策表求核算法，该算法的时间复杂度为：max{O(|C||U||Upos|)，O(K|C||U|)}，优于同类算法的时间复杂度；用实例说明了新算法的有效性。

粗糙集；不完备决策表；差别矩阵；区分对象对集；求核

A

TP311

10.3778/j.issn.1002-8331.1201-0188

ZENG Yanyan,XU Zhangyan，ZENG Lingzhen,et al.Computing core based on discernibility object pair set in incomplete decision table.Computer Engineering and Applications,2013,49（19）：104-107.

国家自然科学基金（No.60963008）；广西自然科学基金（No.2011GXNSFA018163）。

曾艳燕（1987—），女，硕士研究生，主要研究方向：粗糙集理论及应用与数据挖掘；徐章艳（1972—），男，博士，教授，主要研究方向：粗糙集，模糊集，数据挖掘；曾玲珍（1974—），女，助教；张姣（1986—），女，硕士研究生，主要研究方向：形式概念分析，粗糙集，描述逻辑；宋腊香，主要研究方向：粗糙集理论及应用与数据挖掘。E-mail：zengyanyan0925@163.com

2012-01-13

2012-04-23

1002-8331（2013）19-0104-04

CNKI出版日期：2012-06-01http://www.cnki.net/kcms/detail/11.2127.TP.20120601.1457.029.html