不完备信息系统中一种拓展粗糙集模型

1、不完备信息系统中一种拓展粗糙集模型doi:10.3969/j.issn.1001-3695.2009.06.030Extensionof rough set model in incompleteinformationsystemSHEN Jin-biao(Schoolof Mathematics& InformationScience,GuangxiUniversity, Nanning 530004, China):This paper investigated the incomplete information system in which lost and absent u

2、nknown values were coexisting deeply.In such information systems,proposed a reflective relation which was based on the controlling of one parameterpared the rough set model based on this reflective relation with some other existing rough set models which had been used to deal with incomplete informa

3、tion system.Analyzed an illustrative example toindicate thevalidityof thenew-definedbinaryrelation.0 引言粗糙集理论 (rough set theory，RST)是由波兰科学家Pawlak1 于 20 世纪 80 年代初提出的一种处理含糊和不精确性问题的新型数学工具。近年来，为了适应实际工程应用的需求，已有许多学者提出了各种各样的粗糙集模型2 ，如可变精度粗1 / 9糙集、概率粗糙集、模糊粗糙集等。其中不完备信息系统(IIS)中各种拓展粗糙集模型的应用已成为粗糙集理论发展的一个重要方面 3,4。

4、一般来说， IIS 中的未知属性值具有两种解释：a) 所有的未知属性值仅仅是被遗漏的，但又是确实存在的； b) 所有的未知属性值是被认为是丢失的，是不允许被比较的。根据第一种解释，Kryszkiewicz5提出了 IIS 中的容差关系，进而进行了知识约简的方法研究；根据第二种解释，Stefanowski等人 6 构建了其中的相似关系并建立了近似集的概念。可以看出，无论Kryszkiewicz 还是 Stefanowski 所做的工作都认为 IIS 中的未知属性值仅仅具有一种可能的解释， 即遗漏型或丢失型。 然而现实世界中 IIS 的情况可能更为复杂，如 Grzymala-Busse7 就考虑了

5、一种广义的 IIS 。其中的未知属性值有的是属于遗漏型，而有的则属于丢失型。 为了使用 RST处理这种同时具有遗漏和丢失型未知属性 IIS ，Grzymala-Busse 提出了特征关系， 特征关系是结合了容差和相似关系的一种推广形式。随着对特征关系的深入研究， 发现由特征关系所得到的特征类存在两种不尽合理的情况： a) 可能会将两个没有任何明确相同属性值的对象误判在同一类中； b) 在信息系统中属性数目非常多时两对象仅具有极少数相同的属性值就被归为一类。 因此，笔者在深入研究现有广义的 IIS 模型的基础上提出了一种新的二元关系，较好地解决了上述问题。2 / 91 基本概念1.1不完备信息系

6、统一个 IIS 为一个四元组 :S=U,AT,V,f 。其中： U是一个被称为论域的非空有限的对象集合;AT 是非空有限的属性集合; 对于 aAT,有 a:UVa,Va 是属性 a 的值域 ( 可包丢失型、遗漏型空值，文中分别用“ ?”和“ * ”表示 ) , 全体属性值域集合V=aATVa；定义f 为信息函数 , 对于 aAT,xU，有f(x,a)Va。1.2容差关系在 Kryszkiewicz 提出的容差关系中，最主要的一个概念是赋予信息表中没有值的元素一个“ * ”值， “* ”值是一种任何值都有可能的值。 这个解释与这样的值仅仅是被遗漏但又确实存在的解释相对应。 换句话说就是由于不精确

7、的知识迫使人们去处理只有部分信息的不完备信息表。各个体对象具有潜在的完备信息，而当前只是遗漏了这些值。定义 1 在不完备信息系统 S 中, 若所有未知属性值均被认为是遗漏型 ( “* ”) , 则对于 AAT,由 A 决定的容差关系记为 T(A)且T(A)=(x,y)U2:aA,f(x,a)=f(y,a)f(x,a)=*f(y,a)=*1.3相似关系在 Stefanowski等人提出的基于相似关系对rough 集理论进3 / 9行扩充的方法中， 认为对象可能被不完全描述的原因不仅可能是由于知识不精确， 还可能是由于干脆就不可能用所有的属性来描述它们。不认为未知值是不确定的，而是当前不存在的，不

8、允许比较未知值。基于这种观点， 各对象可能有或多或少的完全描述，这取决于可能采用多少属性。 从这种观点看， 只要两个对象的已知属性值相同，就可以认为一个个体对象x 与另一个对象y 相似。定义 2 在不完备信息系统 S 中，若所有未知属性值均被认为是缺席型 ( “?”) ，则对于 aAT，由 A 决定的相似关系记为 S(A) 且S(A)=(x,y)U2:aA：f(x,a)=?f(x,a)=f(y,a)显然，相似关系是不对称的，但是传递的、自反的。相似关系是对象集合上的偏序。 实际上，非对称相似关系可以认为是包含关系的一个代表，因为只要 x 的描述包含于 y 的描述就认为 x 与 y 相似。1.4

9、特征关系很明显，对于如表1 所示的 IIS ，无论是容差关系还是相似关系均无法对论域进行分类， 因为容差关系仅考虑 IIS 中的所有未知属性值都是遗漏型的， 而相似关系则考虑 IIS 中的所有未知属性值都是丢失型的。因此，对于同时具有遗漏型和丢失型未知属性值的 IIS ，Grzymala-Busse 构建了其中的特征关系如下定义所示。定义 3 设 S 为一 IIS ，对于 AAT，则由 A 决定的特征关系表4 / 9示为 K(A) 且K(A)=(x,y)U2:aAf(x,a)?，f(x,a)=f(y,a)f(x,a)=*f(y,a)=*定义 4 设 S 为一 IIS ，有 AAT，则对于 XU

10、，X 基于特征关系K(A) 的下、上近似集分别记为AK(X)， K(X) 且AK(X)=x U:KA(x)XK(X)=x U:KA(x) X其中 :KA(x)=y U:(x,y)K(A) 。如果在 IIS 中，所有未知属性值均被认为是遗漏型的，则特征关系 R(A) 就退化为容差关系；从另一角度来看，若IIS 中所有未知属性值均被看做是丢失型的，则特征关系 (A) 就退化为非对相似关系。因此，可以将特征关系R(A) 看做是容差关系与非对称相似关系的一种混合表现形式。其中既保留了容差关系的相关性质，也保留了非对称相似关系的相关性质。特征关系既可以处理具有遗漏型,也可以处理具有缺席型未知属性值的不完

11、备信息系统。它虽然是继承了容差关系和非对称相似关系的优点， 具有更为合理的分类能力,但也存在一些问题。首先 ,特征关系将两个没有任何已知属性值的不同的对象归为一类 ,如 x=0,*,1,2,*,y=*,1,*,*,1；其次 ,在数据库中的属性数目非常多时,两对象仅仅具有很少的已知相同属性值就可以被划分在同一类中。在这两种情形下, 两对象仅仅是具有不可分辨的可能性,并且由于未知属性值的大量存在,这种可5 / 9能性非常小。例如x=0,*,1,2,1,y=*,1,*,*,1,此时在所有五个属性上 x 与 y 仅有一个相同的已知属性值,然而特征关系却把它们归为一类 , 这很牵强。笔者在深入研究现有广

12、义的IIS 模型的基础上提出了一种新的特征关系，较好地解决了上述问题。2 新的二元关系2.1一种新的二元关系设 MAT（x,y ）=a AT:f(x,a)=*f(y,a)=*表示对象x 或y 取值为 * 的属性集合，NAT(x,y)=a AT:f(x,a)=？ f(y,a)=？ 表示对象 x 或 y 取值为 ?的属性集合。令 NAT（x）=a AT:f(x,a)?,D=a AT:NAT(x)MAT(x,y) ,E=a AT:NAT(x) MAT(x,y) 。定义 5 设 S 为一 IIS ，对于 AAT，则由 A 决定的新二元关系表示为 R(A) 且R(A)=(x,y)U2:(a D,(f(x

13、,a)=f(y,a)f(x,a)=*f(y,a)=*) (|MAT(x,y)|/(|AT|- |NAT(x)|) ) (a NAT(x,y),f(x,a)=f(y,a)=?)(a E,f(x,a)=f(y,a)其中： 0 1。如果对象 x 和 y 有所给的二元关系， 则表示对象x 和 y 在属性上的取值，除有缺席(?) 数据外，要么取值全相等或取值大部分相等。6 / 9定义 6 设 S 为一 IIS ，有 AAT，则对于 XU，X 基于二元关系R(A) 的下、上近似集分别记为AR(X)、 R(X)且AR(X)=x U:RA(x)XR(X)=x U:RA(x) X其中 :RA(x)=y U:(x

14、,y)R(A) 。定理 1 设 S 为一 IIS ，对于 AAT，由 A 决定的新二元关系表示为 R(A) ，若 0 1，则 RA(x)R A(x) 。证明 由定义易证。定理 2 设 S 为一 IIS ，对于 AAT，由 A 决定的新二元关系表示为 R(A) ，特征关系为 K(A) ，则 RA(x)KA(x) 。证明 由定义易证。2.2有关性质定理 3 设 S 为一 IIS ，对于 AAT，由 A 决定的新二元关系表示为 R(A), 对于任意 XU，有AR(X)X?联?R(X)(1)AR(X)=U- R(U-X)(2)证明 式（1）对任意 xAR(X)，RA(x)X ，而 xRA(x) ，xX

15、，故AR(X)X。对任意 xX，xRA(x) ，有RA(x) X?粒 ?故 X?联?R(X)。综上有T(X)X(X) 。式（ 2）对任意 xAR(X)，RA(x)XRA(x) (U-X)=?7 / 9联?xR(U- X)xU- R(U-X) 。3 特殊情形分析3.1 “?”值不完备信息系统在定义 5 所建立新的二元关系的基础上 , 如果再将 IIS 系统特殊化 , 可以得到它的几种不同表现形式。首先 , 在一个 IIS 中 , 若所有的未知属性值均为缺席型“ ?”时 , 此时 取值定为 1,所以定义 5 中的二元关系就退化成为相似关系。3.2 “* ”值不完备信息系统另一方面 ,在一个 IIS 中,若所有的未知属性值均为丢失型“ * ”时 , 此时 的取值 1,因此分类的结果不受 的影响 ,从而定义 5 中的二元关系退化成为容差关系。若 0 5 结束语粗糙集理论由于其坚实的数学基础 , 近年来在知识获取、人工智能等众多科研领域得到了广泛的应用。 传统的粗糙集只能处理具有完备属性值的信息系统 , 然而在现实世界中由于各种原因 , 需处理的信息系统往往是不完备的。 建立 IIS 中的拓展粗糙集模型进行数据分