一种基于粗集的格值信息系统的知识约简方法

开篇：润墨网以专业的文秘视角，为您筛选了一篇一种基于粗集的格值信息系统的知识约简方法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：粗糙集理论是一种建立在分类的基础上处理模糊和不确定知识的数学工具，正越来越被人们所关注。首先介绍了格值信息系统的相关知识，并以偏序关系为基础得到了一种新的关系：优势关系，给出了约简和核心，简化了概念的分类特征，也给出了上近似、下近似及约简的判定定理和辨识矩阵的概念，最后通过具体的例子说明这种约简方法是有效的。

关键词：粗糙集；格；格值信息系统；知识约简；协调集

中图分类号：TP311文献标识码：A 文章编号：1009-3044(2008)18-20000-00

A Knowledge Reduction Method Based on Rough Sets and Lattice-valued Information Systems

HUANG Jia-zeng,CAI Xiang-yun

(School of Science，Kunming University of Science and Technology,Kunming 650093,China)

Abstract: Rough set theory is an established on the basis of the classification deal with the ambiguity and uncertainty of knowledge mathematical tool, more and more people are concerned. First introduced the lattice-value information systems knowledge, and to partial order for the basis has been A new relationship: advantage, given the reduction and the core, the concept of simplifying the classification of features, it is also given on the approximation, and the approximate reduction of matrix determined theorem and the concept of identification, the final adoption of specific Reduction of examples to illustrate this method is effective.

Key words: rough sets; lattice; lattice-valued information system; knowledge reduction; consistent set

1 引言

知识发现是人工智能的核心问题之一，它是从信息系统中识别正确、新颖、有潜在应用价值并最终可为人们所理解的模式方法。粗糙集理论提供了知识发现的一种数学方法。而知识约简是知识发现的重要课题，所以也是粗糙集理论的核心问题之一，其中约简与核心成为用粗糙集研究的两个相互联系的中心课题。

本文通过格引入格值信息系统，在格值信息系统上定义了优势关系。定义了这种关系下上下近似，建立了基于格值信息系统的知识约简方法，特别是给出了它的约简、核心以及辨识矩阵并对其分析研究，这为其它类型系统的知识约简提供了理论依据与算法。

2 格值信息系统上的粗糙集理论

格值信息系统为研究各种信息系统提供了最一般的框架和模型。先给出有关概念和术语。

定义2.1设（L，≤）是偏序集，若在L上有二元运算∧，∨：L2L满足：

作者简介：黄加增(1974～),男，福建莆田人，硕士研究生，研究方向：粗糙集与概念格；导师简介：蔡翔云，教授，硕士生导师。研究方向：数据库及应用。

（1）交换律：x∧y=y∧x,x∨y=y∨x;

（2）结合律：(x∧y)∧z=x∧(y∧z),( x∨y)∨z=x∨( y∨z);

（3）吸收律：x∧y=y??y≤x,x∨y=y??x≤y.

则称（L，∧，∨）为格，简称L为格.

定义2.2称（U,A,F）为格值信息系统，若U={x1,x2, …,xn}为对象集，每个xi(i≤n)称为一个对象，A={a1,a2, …,am}为属性集，每个aj(j≤m)称为一个属性，F={fa:a∈A}为对象属性值映射，也称信息函数，其中

Fa:UVa或L(a∈A)

Va是属性a的值域，是有限格（为了叙述方便我们不妨假设所有属性值域为同一个格）。(同时为了方便起见我们用一个符号“≥”表示Va上的序关系).

对于任意B？？A，记 RB＝{(x,y) ∈U×U：fa(x)=fa(y)},??a∈B.

则RB是U上的等价关系，称为由B决定的不可区分关系。它产生U上的一个分划记为：

U/RB={[x]B:x∈U}

其中 [x]B={y:(x,y) ∈RB}}={y∈U:fa(x)=fa(y)} ??a∈B,x∈U.

是x关于B的等价类.??X??U，记

，

则?? RB(X)与??RB(X)分别称为x关于B的下近似和上近似.X的下近似是按着知识B肯定属于X的对象全体，而X的上近似是按着知识B可能属于X的对象全体.通过这种等价关系处理知识约简有许多学者研究过就不再阐述。这里介绍一种非等价关系处理知识约简。

定义2.3 设（U,A,F）为格值信息系统，？？B？A，定义如下二元关系

, 为劣势关系,与优势关系是一对相似的关系。在这边不再详细讨论.

容易证明以下性质成立：

（1）？？R≥B是自反和传递的，未必是对称的，因此一般情况下不是等价关系；

（2）当hzj05.tif；

（3）当hzj06.tif；

（4）hzj07.tif是U的一个覆盖；

（5）当y∈？？[x]≥B时，有[y]≥B????[x]≥B.

定义2.4设（U,A,F）为格值信息系统.对任意X??U,B??A，记

则？？R≥B（X）和？？R≥B（X）分别称为X在关系？？R≥B下关于属性B的下近似和上近似。

设（U,A,F）为格值信息系统,若B？A，则对于任意X？U，可以验证以下性质成立：

3格值信息系统的优势关系下的属性约简

定义3.1设（U,A,F）为格值信息系统且B？A。若RB≥=???RA≥,则称B是格值信息系统（U,A,F）在关系??RA≥下的协调集.若进一步对任意b∈B, RB-(b)≥=???RA≥,则称 是格值信息系统（U,A,F）在关系??RA≥下的约简。若B是协调集，而B的任何真子集均不是协调集，则称B为约简集。记

D≥(x,y)={a∈A│(x,y)?R≥a}={a∈A│fa(x)???fa(y)},称D≥(x,y)为格值信息系统（U,A,F）在关系??RA≥下的辨识属性集, D≥={ D≥(x,y)│x,y∈U}为格值信息系统

（U,A,F）在关系??RA≥下的辨识矩阵。记D0≥={ D≥(x,y) ≠φ│x,y∈U}。

定理3.1 设D≥(x,y)为格值信息系统（U,A,F）在关系??RA≥下的辨识属性集，B??A.则以下命题等价：

（1）B是协调集；

（2）?D≥(x,y) ≠φ，有B∩D≥(x,y) ≠φ；

（3）?B’?A，若B’∩B=φ，则B’??D0≥.

证明（1）??（2）：

B是协调集??RB≥?? RA≥??(x,y)? RA≥时，有?? ?D≥(x,y) ≠φ时，有(x,y)? RB≥，即?a∈B，使a∈D≥(x,y) ?? ?D≥(x,y) ≠φ时，B∩D≥(x,y) ≠φ。

（3）由（1）、（2）即得。

设B≥={Bk≥│k≤l}为格值信息系统（U,A,F）在关系BA≥下的约简集全体。记C＝∩k≤lBk≥，K=∪k≤l Bk≥-C， I=U-(K∪C)，称C为（U,A,F）的核心属性集，K为（U,A,F）的相对必要属性集，I为（U,A,F）的不必要属性集.

定理3.2设（U,A,F）是格值信息系统，则以下命题等价：

（1）a是核心属性；

（2）存在x,y∈U，使D≥(x,y)={a}；

（3）RA-{a}≥??? RA≥。

证明（1）？？（2） 若(2)不成立，即a∈D≥(x,y)，│ D≥(x,y) │ ≥2。记 B=∪{(D≥(x,y)-{a})│[x]A≥∩[y]A≥=?}，则对任意[x]A≥∩[y]A≥=?，有

B∩D≥(x,y) ≠φ。由定理3.1知，B是协调集。从而存在约简C？B，且a?C，这与 是核心属性矛盾。

（2）？（3） 由(2)知，存在x,y，fa(x)?fa(y)，且，fa(x)>fa(y)（b≠a），所以(x,y)RA-{a}≥，(x,y)?RA≥。从而RA-{a}≥?RA≥。

（3）？（1） 若a不是核心属性，则存在属性约简B，使a?B，于是B? A-{ a }，从而RA-{a}≥??RB≥??RA≥，与（3）矛盾，则证。

定理3.3设（U,A,F）是格值信息系统，则a是不必要属性当且仅当R(a) ≥? 当R(a) ≥?? 当Ra ≥，其中R(a) ≥＝∪{Rb-{a}≥│RB≥?RA≥,B??A}。

证明 若 是必要属性，则 不存在于任何约简之中。于是??RB≥?RA≥（B??A），有Rb-{a}≥？？RA≥。否则，若Rb-{a}≥？？RA≥，？？B’?B-{a}，有??RB≥??RA≥，从而B是约简，且a∈B，与a是不必要属性矛盾。

若R(a) ≥?? Ra≥，则??B??A，??RB??RA，有

即a不存在于任何约简之中，所以a是不必要属性。

例1表1描述了一个格值信息系统。

表2给出了表1所示的格值信息系统基于 的辨识矩阵，其中P，S，G，F分别表示Price，Size，Surroundings，Floors-High：

表2例1所示格值信息系统基于RA≥的辨识矩阵

显然，B＝{Price，Size，Surroundings，Floors-High}是表1所示格值信息系统基于RA≥的约简。

4 结束语

知识约简能够简化信息系统，又不损失有用的信息，因此它是知识获取的重要内容。关于信息系统的知识约简的研究已有很多成果且大多是在Pawlak粗糙集模型中进行的。本文研究在格的基础上的知识约简。通过不等价刻画得到了上、下近似与约简的判定定理和相应的辨识属性矩阵。由此提供了这种知识约简的具体操作方法。这在理论上与应用上都是有意义的。对于其它格的类型的知识约简的讨论有待进一步研究。

参考文献：

[1] 张文修，吴伟志，等.粗糙集理论与方法[M].北京：科学出版社，2001.

[2] 张文修，姚一豫，梁怡.粗糙集与概念格[M].西安：西安交通大学出版社，2006.

[3] 仇国芳，陈劲.概念格的规则约简与属性特征[J].浙江大学学报，2007，2：158-163.

[4] X.B Yang ,J.Y Yang, C.Wu, et al. Dominance-based rough set approach and knowledge reductions in incomplete ordered information system[J]. Information Sciences,2008,178:1219C1234.

[5] Ling Wei, Hong-Ru Li, Wen-Xiu Zhang. Knowledge reduction based on the equivalence relations defined on attribute set and its power set[J]. Information Sciences,2007,177:3178C3185.

[6] Xia Wang, Wenxiu Zhang. Relations of attribute reduction between object and property oriented concept lattices[J]. Knowledge-Based Systems，2008，17：1699-1675.

收稿日期：2008-04-17

作者简介：黄加增（1974-），男，福建莆田人，硕士研究生，研究方向：粗糙集与概念格；导师简介：蔡翔云，教授，硕士生导师，研究方向：数据库及应用。

注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”