广义相似关系下的不完备信息系统粗糙集模型

谭  旭^{1, 2}，陈英武²，王桢珍²

(1. 深圳信息职业技术学院 计算机应用系，广东 深圳，518029；

2. 国防科学技术大学 信息系统与管理学院，湖南 长沙，410073)

摘  要：为了更好地从含有杂合数据和不完备数据的信息系统中提取合理的规则知识，构建基于广义相似关系的不完备信息系统粗糙集模型。其步骤为：针对决策信息系统中存在杂合数据的情况，并对决策信息系统中所存在的不完备信息进行细致区分，给出广义相似关系的定义；通过提出上、下广义相似划分的上、下近似的概念，给出2种划分意义下的属性约简和规则知识提取策略；最后，在理论上对该扩展粗糙集模型的正确性进行相关证明，并用实际算例进一步验证该模型的有效性和优越性。

关键词：广义相似关系；不完备信息系统；上近似；下近似；粗糙集

中图分类号：TP18          文献标识码：A         文章编号：1672-7207(2009)05-1360-07

Rough set model based on general similarity relation in

 incomplete information systems

TAN Xu^{1, 2}, CHEN Ying-wu², WANG Zhen-zhen²

(1. Department of Computer Application, Shenzhen Institute of Information Technology, Shenzhen 518029, China;

2. School of Information Systems & Management, National University of Defense Technology, Changsha 410073, China)

Abstract: In order to extract reasonable rule-based knowledge from information systems with hybrid data and incomplete data, a new rough set model based on general similarity relation in incomplete information systems was proposed. The procedures were as follows: Firstly, general similarity relations were defined for the situation of hybrid data and different kinds of incomplete data in information systems. Secondly, two kinds of attribute reduction methods and rule-based knowledge extraction methods were investigated, which were built upon the concepts of upper and lower approximations with upper and lower general similarity partitions. Lastly, the extended rough set model was proved theoretically, and a numerical example reveals the validity and advantage of the proposed model.

Key words: general similarity relation; incomplete information system; upper approximation; lower approximation; rough set theory

粗糙集理论是Pawlak提出的一种处理不精确、不完备信息的软计算方法。因其不需借助任何外界信息能进行数据分析和处理，经过20多年的发展，已在模式识别、医疗、金融、水利、管理决策等领域得到应用。经典粗糙集理论是基于上、下近似和等价关系的概念来处理各种信息的，然而，对于现实生活中大量存在的不完备信息系统、混合数据信息系统以及模糊信息系统，通常难以得到满意的处理结果。于是，许多研究者提出了多种扩展的粗糙集模型，如变精度粗糙集模型^[1-2]、模糊粗糙集模型^[3-4]、覆盖粗糙集模型^[5-7]等。尤其针对不完备数据的信息系统，大量改进模型如容差模型^[8]、量化容差模型^[9]、非对称相似模  型^[10-11]、特征关系模型^[12]等得到广泛应用。然而，这些粗糙集模型在实际应用中各有利弊^[13]。这些模型对于不完备信息系统中存在混合数据^[14]，且条件属性集对决策属性划分存在不确定性以及知识规则抽取存在不合理性，为此，本文作者提出一种广义粗糙集模型。

1  不完备信息系统的广义相似关系

定义1  有序5元组T={U, C, D, V, f}称为一个信息系统。其中：U={o₁, o₂, …, o_n}，为决策表中全体数据对象的集合；C为条件属性集合，它们反映对象的特征；D为决策属性集，反映对象的类别；，为所有属性下的属性值集合；f为的信息函数，用于确定U中每一个对象在各个属性下的取值。给定，V_a可以为实数值的连续型数据，也可以为语言描述型数据。进一步，若，，使得(记号代表数据缺失，表示数据无法确定)，则称该信息系统为不完备信息系统。

显然，完备信息系统是不完备信息系统的特例。本文假定决策属性不存在数据缺失和数据无法确定的问题，同时，约定决策属性上的取值为离散型数据。

定义2  设T为定义的信息系统，U为该信息系统的有限论域，条件属性集上的等价关系IND(C)定义为，记，为U在条件属性集C上等价划分，划分结果记为{X₁, X₂, …, X_p}。其中，。同理，记U/IND(D)= ，为U在决策属性D上等价划分，划分结果记为{Y₁, Y₂, …, Y_q}。

等价关系满足自反性、对称性和传递性^[14]。

由于条件属性上的取值可以为实数值的连续型数据，可以为语言描述型数据，也可以存在缺失数据或无法确定的数据，下面给出广义相似关系以及广义相似划分的定义。

定义3  对于信息系统T，，定义对象o_i与o_j在条件属性集C下的广义相似度为：

其中：

在广义相似度定义下的关系S称为广义相似关系。

对于对象集在条件属性上取值为实数值的连续型数据，；对于对象集在条件属性上取值为语言描述型数据，设P= ，为对象集在属性a上按序排列的可能取值(如{优, 良, 中, 差})；l＞1，为语言标度数，则；当对象在条件属性上取值为缺失型和无法确定类型的数据时，综合分析几种扩展不完备粗糙集模型的利弊，并针对混合型数据的不完备信息系统的特点，给出如下定义。

定义4  在不完备信息系统T中，，，若有 ，根据不完备数据在对象o_i, o_j间所处的不同位置以及不完备数据的类型，给出如下计算：

从定义4可以看出，在不完备信息系统中，虽然是讨论对象在条件属性下取值为空的情况，但这里将数据缺失和不确定数据予以区分，分别赋予了不同的含义，也给出了相应的相似关系计算，如计算a与计算b和d的区别；对于不完备数据在2个比较对象间所处的不同位置，也分别给出了不同的定义，如计算c与计算a, b和d的区别；对于数据缺失的情形，考虑了决策属性上的取值对该缺失数据的取值影响，使之更加符合实际情况，如计算b和d。

容易看出，。当 0时，称对象o_i与o_j在条件属性a上是极相异的；当时，则称对象o_i与o_j在条件属性a上是极相似的，根据定义3和定义4，可得到如下性质。

性质1：

性质1说明信息系统中对象间的广义相似关系满足自反性，一般不满足交换性和传递性。特别地，对于完备信息系统，自反性和交换性是可以成立的。

给出了信息系统中的对象集在广义相似关系下的相似度后，可对所有对象集条件属性集进行广  义相似划分。相对于传统的“硬划分”，这是一种  “软划分”。给定相似阈值，并设定max_ij=，，分别为对象o_i与o_j间在条件属性集C下的最大和最小广义相似关系值，有如下定义。

定义5  设T为给定的广义不完备数据信息系统，0.5＜≤1，为相似阈值，则U在条件属性集C的-下广义相似划分为，；-上广义相似划分为，， 。其中：C_ij=，且定义-下广义相似划分的可信度为，-上广义相似划分的可信度为。

显然，对于-下相似划分，。需注意的是，相似阈值的合理选取非常重要，因为它与广义相似软划分的质量密切相关。

定理1  对象间的等价关系和等价划分是广义相似关系和广义相似划分的特例，而广义相似关系和广义相似划分则是等价关系和等价划分的泛化。

证明  给定信息系统T，，，若，且，则 ，否则，。那么，。广义相似划分中相似阈值0.5＜≤1，显然，此时≡1。这样， 。即在给定条件下，-下相似划分退化成等价划分。且在这种-下相似划分下，显然满足

，

以及 。即这种广义相似关系退化成等价关系，且满足自反性、对称性和传递性。

2  广义相似关系下的粗糙集模型

由于讨论的信息系统存在数据的不完备性和多样性，在广义相似关系下划分后，通常存在不协调性，即存在，。借鉴变精度粗糙集模型^[1]，下面给出不完备信息系统中广义相似关系下的粗糙集模型定义。

定义6  不完备信息系统T中，关于条件属性集C的-上、下广义相似划分的-上、下近似定义为：

其中：为集合Y的-下广义相似的-下近似；为集合的-下广义相似的-上近似；为集合Y的-上广义相似的-下近似；为集合Y的-上广义相似的-上近似；0.5＜≤1，合理的将使得在-上、下广义相似划分下均能获得最佳的上、下近似集，直接影响到后续的条件属性约简和规则的提取。

引理1  在不完备信息系统T中，，在-上、下广义相似划分下，一定有：

证明  在不完备信息系统中，，根据-下广义相似划分的定义，有。，再由定义6中的-上、下近似的定义，得，。

据定义6，，，显然，。而此时无法确定与之间的包含关系。

综上分析，a~c成立。证毕。

引理1阐释了在广义相似关系的背景下，条件属性集的变化给信息系统的知识划分带来的影响，也为广义相似关系下的属性约简进行了初步分析。

2.1  属性约简

在完备信息系统中等价关系和等价划分的定义中，条件属性的约简是保持信息系统分类能力不发生变化的条件下，剔除其中不相关或不重要的条件属性。通常的定义为^[14]：给定，若存在，且A的任何真子集均不满足该条件，则称条件属性集A为条件属性集C相对于属性D的约简。同样，对于广义相似关系下不完备信息系统，依然可以定义条件属性的约简。

定义7  给定不完备信息系统T，Y∈U/IND(D)，若a. ，使且，并且A的任何真子集均不满足以上条件，则称条件属性集A为条件属性集C相对于属性D的-下广义相似的近似约简；b. ，使且，并且B的任何真子集均不满足以上条件，则称条件属性集B为条件属性集C相对于属性D的-上广义相似的近似约简。

定义7结合了上、下近似2个方面来定义广义相似关系下的条件属性约简，更好地保证条件属性的约简结果能“保持信息系统分类能力不发生变化”。这也是引理1所推导的一种平衡状态。

定理2  不完备信息系统T中，若条件属性集A为-下广义相似的近似约简，条件属性集B为-上广义相似的近似约简，则有

证明 根据定义5，设{X₁, X₂, …, X_w}，则，即。且，，均有，。再根据

定义6，，。

依据已知条件，若条件属性集A为-下广义相似的近似约简，则有

且

条件属性集B为-上广义相似的近似约简，则

且

则可推出：

再由

定理得证。

定理2分析了-下广义相似的近似约简结果与-上广义相似的近似约简结果之间的关系，并充分说明了上广义相似的近似约简是一种更为粗放、粒度更大的约简，可以获取更全面的知识。而下广义相似的近似约简是一种粒度较小，要求更为精细的约简。虽然采用这2种约简能得到2种不同需求下的约简结果，但是，由于广义相似关系，它们之间存在着天然的联系。上广义相似及其约简是一种相对包容度更大的知识获取和表达方式。

定理3  对于信息系统T，基于等价关系的条件属性约简是基于广义相似关系条件属性约简的特例。

证明  设，为-下广义相似的近似约简属性集，，为-上广义相似的近似约简属性集，则或。依据定义7，有

且

且

当且，即相似关系逐渐强化为等价关系时，

进一步，当对象间的划分变为等价关系时，由定理2可知，，，而A为-下广义相似的近似约简属性集，B为-上广义相似的近似约简属性集，即

且

此时A=B。

可见，基于等价关系的条件属性约简是基于广义相似关系条件属性约简的特例。

2.2  规则提取

给出了广义相似关系和广义相似划分定义以及广义相似关系下的条件属性约简后，下面讨论如何从不完备信息系统中获取规则知识。

，有；，有，称(a, v)为条件属性集上的1个基本原子描述，(b, w)为决策属性上的1个基本原子描述。不同属性下的基本原子描述的组合称为1个基本

描述，并记，为条件属性集下的基本描述，，为决策属性下的基本描述。定义为中所含的属性数目。对于决策属性为单一属性的信息系统，。定义条件属性集下相似的基本描述簇为，条件属性集上相似基本描述簇为 。在决策属性下，定义基本描述簇为。记录为各描述簇内的对象集合。

性质2：

性质a表述了下相似基本描述簇内的对象集与上相似基本描述簇内的对象集之间的包含关系，即下广义相似划分包含于上广义相似划分，上广义相似划分是一种更为粗糙的划分；性质b~e分别阐释了上、下相似基本描述簇与决策属性上对应的基本描述簇之间的关系，为信息系统中规则的提取建立了关联。显然，这里的每一个基本描述簇都对应了1个(上、下相似)广义划分类，它们是划分类更详尽的一种描述。

根据-上、下广义相似划分以及-上、下近似定义，可以从不完备信息系统中抽取出相应的规则。对于-下广义相似划分，可以提取到形式的规则，表述成if … then … 形式的规则为：if

 then ；对于-上广义相似划分亦可以提取到形式的规则，表述成if … then … 形式的规则为：

if 。

由于信息系统的不完备性以及数据的多样性，最终提取得到的规则都是可能性规则，而这种“可能性”采用确定度和覆盖度来描述^[11]。

定义8  信息系统T中给定1条推理规则 (其中：g为上、下相似基本描述簇和的简写；h为决策属性基本描述簇的简写)，为定义5中上、下相似基本描述簇的可信  度。则该规则的确定度定义为 ，该规则的覆盖度定义为。

最终可以得到4类规则：-下广义相似-下近似下的规则，-下广义相似-上近似下的规则，-上广义相似-下近似下的规则，-上广义相似-上近似下的规则。为此，由信息系统中的规则知识能够得到不遗漏的全面挖掘，并通过规则的确定度和覆盖度予以本质区别。

3  实例分析

以一段实际中常见的烤烟烟叶外观等级评价决策信息系统为例，对本文所提出的广义相似关系下的粗糙集模型以及该粗糙集模型进行的属性约简和规则提取进行分析和阐述。混合型数据不完备信息数据见表1。

表1  混合型数据不完备信息系统实例

Table 1  Example of incomplete information systems with hybrid data values

由表1可见，对象集U在决策属性D上的等价划分为U/IND(D)={{o₁, o₂, o₅}, {o₃, o₄, o₆, o₇}}。连续型实数值数据的条件属性A₁为烟叶的“长度”；语言描述型数据的条件属性A₂为烟叶的“色度”，取值范围为{浓, 强, 中, 弱, 淡}；条件属性A₃描述了烟叶的“油分”，语言标度集合为{多, 有, 稍有, 少}；条件属性A₄取值为百分比数据，表达烟叶的“残伤”。对象o₂在属性A₃上取值为无法确定型数据，对象o₃和对象o₇分别在属性A₄和属性A₁上取值为缺失型数据。

依据定义3和定义4，可以分别得到对象之间在4个条件属性上的相似度。

从属性A₁上各对象间的相似度矩阵可以看到，由于，故(i=1, 2, …, 6)，(j=1, 2, 4, 5)，(j=3, 6, 7)，此时，。

据相似阈值的优化计算，得相似阈值=0.75，此时，-下相似广义划分结果为{{o₁, o₄, o₅}, {o₁, o₂, o₅}, {o₃, o₆}, {o₇}}，-上相似广义划分结果为{{o₁, o₂, o₄, o₅}, {o₃, o₄, o₆, o₇}}。显然，这是不同于等价划分的一种广义覆盖划分，不满足传递性。同时，通过计算得到Bel({o₁, o₂, o₄, o₅})=0.75，Bel({o₃, o₄, o₆, o₇})=0.50。

通过分析计算，设定上、下近似阈值 ，则={o₁, o₂, o₃, o₅, o₆, o₇}，= {o₁, o₂, o₃, o₄, o₅, o₆, o₇}，={o₁, o₂, o₃, o₄, o₅, o₆, o₇}，={o₁, o₂, o₃, o₄, o₅, o₆, o₇}。

依据定义7给出的广义相似关系下的条件属性约简定义，可以得到原条件属性集相对于属性D的-下广义相似的近似约简为A={A₁, A₃}，原条件属性集相对于属性D的-上广义相似的近似约简为B={A₂, A₄}。

约简后可以提取到的所有规则为：

if A₁∈[37.1, 40.3] and A₃∈{有} then 中部烟 Cer=0.67; Cov=0.67；

if A₁∈[37.1, 40.3] and A₃∈{有} then 下部烟 Cer=0.33; Cov=0.25；

if A₁∈[39.9, 44.8] then 中部烟 Cer=1.0; Cov=1.0；

if A₃∈{稍有} then 下部烟 Cer=1.0; Cov=0.5；

if A₃∈{少} then 下部烟 Cer=1.0; Cov=0.25；

if A₂∈{浓, 强} and A₄∈[18.9%, 21.7%] then 中部烟 Cer=0.56; Cov=1.0；

if A₂∈{浓, 强} and A₄∈[18.9%, 21.7%] then 下部烟 Cer=0.19; Cov=0.25；

if A₂∈{淡, 弱, 浓} then 下部烟 Cer=0.5; Cov=0.38；

这样，该信息系统中所蕴涵的所有“可能”规则知识全部获取，并通过给出每条规则的确定度和覆盖度，使得这些规则知识以更加合理和全面的方式予以展示，有助于对该信息系统的理解和后续推理。

4  结  论

a. 为了最大限度地从含有杂合数据的不完备信息系统中提取出有效的规则知识，首先对杂合数据和不完备数据在广义相似关系下进行特殊处理，分别给出了上、下广义相似下的属性约简和规则抽取的定义与方法，最后，得到的产生式规则也采用确定度和覆盖度来予以衡量和评价，能方便、直观和理性地从该类信息系统中获取知识。

b. 所提出的广义相似概念是基于等价划分概念的延拓，而基于广义相似概念的粗糙集模型也是经典粗糙集模型的进一步延伸。这是对Pawlak粗糙集理论进行的扩展和改进，使得粗糙集理论适用于工程实际。对于普通的信息系统，它完全可以作为本文所研究的特例予以处理，故本文所提出的扩展粗糙集模型具有普适性。

参考文献：

[1] Ziarko W. Variable precision rough set model[J]. Journal of Computer and System Science, 1993, 46(1): 39-59.

[2] Slezak D, Ziarko W. Attribute reduction in the bayesian version of variable precision rough set model[J]. Electronic Notes in Theoretical Computer Science, 2003, 82(4): 1-11.

[3] Dubois D, Prade H. Rough-fuzzy sets and fuzzy-rough sets[J]. International Journal Gen Systems, 1990, 17(2): 191-209.

[4] 何亚群, 李继军, 胡寿松. 基于模糊相容关系下的相容模糊粗糙集[J]. 系统工程学报, 2006, 21(5): 553-556.
HE Ya-qun, LI Ji-jun, HU Shou-song. Compatibility fuzzy-rough sets based on fuzzy compatibility relation[J]. Journal of Systems Engineering, 2006, 21(5): 553-556.

[5] Bonikowski Z, Bryniarski E, Wybraniec U. Extension and intentions in the rough set theory[J]. Information Science, 1998, 107(1): 149-167.

[6] Zhu Willian. Topological approaches to covering rough sets[J]. Information Sciences, 2007, 177(6): 1499-1508.

[7] Zhu Willian, Wang Feiyue. A new type of covering rough sets[C]//Proc of the 3rd IEEE International Conf on Intelligent Systems. London, 2006: 444-449.

[8] Kryszkiewicz M. Rules in incomplete information systems[J]. Information Sciences, 1999, 113: 271-292.

[9] Jerzy S. Incomplete information tables and rough classification [J]. Computational Intelligence, 2001, 17(3): 545-566.

[10] 王国胤. Rough Set理论与知识获取[M]. 西安: 西安交通大学出版社, 2001.
WANG Guo-yin. Rough set theory and knowledge acquisition[M]. Xi’an: Xi’an Jiaotong University Press, 2001.

[11] Yee L, WU Wei-zhi, ZHANG Wen-xiu. Knowledge acquisition in incomplete information systems: A rough set approach[J]. European Journal of Operational Research, 2006, 168(1): 164-180.

[12] LI Tian-rui, DA Ruan, Geert W, et al. A rough sets based characteristic relation approach for dynamic attribute generalization in data mining[J]. Knowledge-Based Systems, 2007, 20(5): 485-494.

[13] 瞿彬彬, 卢炎生. 基于限制非对称相似关系的粗糙集模型[J]. 小型微型计算机系统, 2007, 28(6): 1084-1088.
QU Bin-bin, LU Yan-sheng. Rough set model based on limited non-symmetric similarity relation[J]. Journal of Chinese Computer Systems, 2007, 28(6): 1084-1088.

[14] HU Qing-hua, LIU Jin-fu, YU Da-ren. Mixed feature selection based on granulation and approximation[J]. Knowledge-Based Systems, 2008, 21(4): 294-304.

[15] 张文修, 仇国芳. 基于粗糙集的不确定性决策[M]. 北京: 清华大学出版社, 2005.
ZHANG Wen-xiu, QIU Guo-fang. Uncertain decision making based on rough sets[M]. Beijing: Tsinghua University Press, 2005.

收稿日期：2008-09-01；修回日期：2008-12-28

基金项目：国家自然科学基金资助项目(70272002)

通信作者：谭  旭(1981-)，男，湖南株洲人，博士，讲师，从事粗糙集理论与智能决策的研究；电话：13760330247；E-mail: tanxu_nudt@yahoo.com