基于证据理论的覆盖决策信息系统的属性约简

覆盖决策信息系统的属性约简是粗糙集理论中的重要研究内容之一.文中讨论决策为覆盖的覆盖决策信息系统的属性约简,针对覆盖决策信息系统的一类约简,利用证据理论中的信任函数和似然函数给出约简的等价刻画.根据决策类的似然函数值定义覆盖的重要度和相对重要度,给出求解约简的算法,并以实例说明算法的有效性.     

一种新的启发式知识约简算法

知识约简是Rough Set理论研究的重要内容.通过分辨矩阵定义了简化分辨函数,然后针对此分辨函数构造了两种操作以及定义了覆盖、最小覆盖等概念,并基于这种操作、概念和相关原理将决策系统的约简问题转化为寻求简化分辨函数最小覆盖的问题;面向最小属性约简定义了基于简化分辨函数的属性重要度,并以此为启发信息,结合已导出的有关最小覆盖的定理构造了一种新的知识约简算法--算法SDFAR.文中,在理论上详细证明了提出算法的完备性并给出了算法的复杂性分析,说明其高效性,对寻找最小约简是相对有效的,这在最后的实验中也得到了验证.     

基于信息系统属性同态的数据压缩

数据压缩是数据处理的一个重要主题,同态是实现数据压缩的一种有效工具。根据信息系统属性集及其上的依赖关系,定义了信息系统属性同构和信息系统属性同态的概念。研究了信息系统属性同态的性质,利用属性等价关系诱导出了信息系统属性理想同态,应用信息系统属性理想同态实现了信息系统属性集的无损压缩。最后通过比较原信息系统与同态像信息系统的距离,给出了度量任意属性同态理想程度的方法。     

基于冲突对象集的决策系统分配约简算法

目前对不一致不完备决策系统的粗糙集属性分配约简研究较少,研究不一致不完备决策系统的分配约简更具有实际应用价值。基于此,提出一种基于冲突对象集的不一致不完备决策系统分配约简方法。通过定义冲突对象集的概念,给出计算核属性集和属性重要性的方法;在此基础上,给出求解不一致不完备决策系统分配约简的算法。理论分析和实例结果表明,该方法显著降低了分配约简求解的空间复杂度,更加适合大规模数据库。     

多尺度覆盖决策信息系统的布尔矩阵方法

在多尺度决策信息系统中,一个条件属性对应某个尺度构成论域的一个划分.文中把相应的划分推广为覆盖,并建立多尺度覆盖决策信息系统模型(MSCDS).为了简化系统复杂信息的表达,采用矩阵方法.首先,利用布尔矩阵描述覆盖决策信息系统,包括上下近似、协调性和广义决策函数等.再使用布尔矩阵建立多尺度覆盖决策信息系统的定义,研究该系统的粒描述、上下近似、协调性和广义决策不变性.最后,针对协调与不协调的情况,利用布尔矩阵定义尺度组合的重要度,给出多尺度覆盖决策信息系统最优尺度选择的矩阵方法,并给出相应的选择算法和具体算例.     

不协调覆盖决策系统下属性约简的新的注记

讨论了不协调覆盖决策系统下属性约简的几点注记。给出不协调覆盖决策系统和条件限制熵的有关定义,提出了基于正域和基于限制条件信息熵的不协调覆盖决策系统的相关性质和定理,利用一个分辨矩阵设计了一种算法,它可以计算所有的不协调覆盖决策系统,并用实例验证此方法的有效性。     

一种新的决策粗糙集启发式属性约简算法

属性约简是粗糙集理论中最重要的研究内容之一。在决策粗糙集中,学者提出了多种属性约简的定义,其中包括保持所有对象正决策不变的约简定义。针对该约简定义,为了高效地获取约简集,设计了一种启发式函数 ——决策重要度,这种启发式函数根据每个属性正决策对象集合的大小来定义其重要性,正决策对象集合越大表示重要性越高,由此构造了基于决策重要度的启发式属性约简算法。该算法的优点是通过对属性决策重要度的排序,确定了一个搜索方向,避免了属性的组合计算,减少了计算量,能够找出一个较小的约简集。实验结果表明,该算法是有效的,能够得到较好的约简效果。     

邻域信息系统基于同态的数据压缩

用同态的概念作为处理部域信息系统中数据压缩的工具。给出了部域信息系统和诱导的部域信息系统概 念,并在此基础上定义了一种新的协调函数,研究了在同态映射下部域信息系统的一些重要性质,证明了原部域信息 系统与同态象部域信息系统约简的等价性,从而得到一种通过计算数据量较少的象信息系统的约简来对原系统进行 数据压缩的方法.     

基于测试代价敏感的不完备决策系统属性约简算法

提出不完备决策系统测试代价敏感属性约简问题,给出不一致对象集定义以及求解不一致对象集的算法。根据不一致对象的性质改进属性重要性定义,考虑测试代价因素以及不一致对象个数的改变量给出一个新的属性重要性的定义和属性重要性中权重的设置方法,并给出属性重要性的计算算法。在此基础上,给出一个时间复杂度为O(k|C|2|U|)和空间复杂度为O(|U|)的启发式属性约简算法,并通过理论分析、实例分析和实验分析说明该算法准确性和可行性。     

从不一致例子中挖掘规则的粗集方法MIE-RS

该文研究不一致例子中的多概念学习.所谓不一致的例子是指具有相同的条件属性值却属于不同概念的矛盾例子.该文提出了一个基于粗集扩展模型的数据挖掘算法MIE－RS,能有效处理例子集的不一致性,并且通过确定每个概念的覆盖,即最小相关属性集,为每一概念产生最简的满足给定可信度的产生式规则知识.     

Communicating between information systems

Communication between information systems is a basic problem in granular computing. The concept of homomorphism is a useful mathematical tool to study the communication between two information systems. In this paper, some properties of information systems under homomorphisms are investigated. The concepts of consistent functions are first introduced and their properties are investigated. The concepts of relation mappings between two universes are then proposed in order to construct a binary relation on one universe according to the given binary relation on the other universe. The main properties of the mappings are studied. Finally, the notions of homomorphisms of information systems based on arbitrary binary relations are proposed, and it is proved that attribute reductions in the original system and image system are equivalent to each other under the condition of homomorphism.     

A new approach to attribute reduction of consistent and inconsistent covering decision systems with covering rough sets

Traditional rough set theory is mainly used to extract rules from and reduce attributes in databases in which attributes are characterized by partitions, while the covering rough set theory, a generalization of traditional rough set theory, does the same yet characterizes attributes by covers. In this paper, we propose a way to reduce the attributes of covering decision systems, which are databases characterized by covers. First, we define consistent and inconsistent covering decision systems and their attribute reductions. Then, we state the sufficient and the necessary conditions for reduction. Finally, we use a discernibility matrix to design algorithms that compute all the reducts of consistent and inconsistent covering decision systems. Numerical tests on four public data sets show that the proposed attribute reductions of covering decision systems accomplish better classification performance than those of traditional rough sets.     

基于优势关系下的协调近似空间

在基于优势关系下的信息系统中引入了协调近似空间的概念,并证明了在优势关系下不协调目标信息系统也可以转化为一个协调近似空间,这进一步方便了基于优势关系下不协调目标信息系统的研究,丰富了粗糙集理论.     

Homomorphisms-based attribute reduction of dynamic fuzzy covering information systems

Information system homomorphisms have made a substantial contribution to attribute reduction of covering information systems. However, the efforts made on homomorphisms are far from sufficient. This paper further studies homomorphisms for attribute reduction of dynamic fuzzy covering information systems. First, the concepts of neighbourhood and induced fuzzy covering are proposed and their properties are discussed in detail. Then, we introduce the concepts of consistent functions and fuzzy covering mappings providing a basic theoretical foundation for compressing fuzzy covering information systems. Afterwards, the notion of homomorphisms is presented to reveal the relationship between fuzzy covering information systems. We show how large-scale fuzzy covering information systems and dynamic fuzzy covering information systems can be compressed into smaller ones by means of homomorphisms. Finally, illustrative examples are employed to show that attribute reduction can be simplified significantly by our proposed approach.     

On Characteristics of Information System Homomorphisms

The notion of information system homomorphism as a powerful tool to study the relation between two information systems was introduced by J.W. Grzymala-Busse. In this work, we will present some characteristics of information system homomorphism, which reveal the interdependence of the three mappings, namely, object mapping, attribute mapping and value domain mapping. Besides, given a partition on universe, we can derive a new information system homomorphism defining a partition on universe identical with the partition given. In the mean time, some invariant characteristics of upper approximation and lower approximation under information system homomorphism are investigated. At last, we establish a surjection between rough sets of information systems under an information system homomorphism.     

Approaches to knowledge reduction of covering decision systems based on information theory

In this paper, we propose some new approaches for attribute reduction in covering decision systems from the viewpoint of information theory. Firstly, we introduce information entropy and conditional entropy of the covering and define attribute reduction by means of conditional entropy in consistent covering decision systems. Secondly, in inconsistent covering decision systems, the limitary conditional entropy of the covering is proposed and attribute reductions are defined. And finally, by the significance of the covering, some algorithms are designed to compute all the reducts of consistent and inconsistent covering decision systems. We prove that their computational complexity are polynomial. Numerical tests show that the proposed attribute reductions accomplish better classification performance than those of traditional rough sets. In addition, in traditional rough set theory, MIBARK-algorithm [G.Y. Wang, H. Hu, D. Yang, Decision table reduction based on conditional information entropy, Chinese J. Comput., 25 (2002) 1-8] cannot ensure the reduct is the minimal attribute subset which keeps the decision rule invariant in inconsistent decision systems. Here, we solve this problem in inconsistent covering decision systems.     

决策形式背景上区间集概念格的属性约简

将区间集思想引入决策形式背景,研究决策形式背景上的区间集概念格及其属性约简方法.首先在决策形式背景上建立条件区间集概念格和决策区间集概念格,引入这两个区间集概念格之间的加细,给出协调决策形式背景上的区间集协调集及约简的定义,讨论区间集协调集的判定方法.通过在决策形式背景上定义可辨识区间集属性矩阵,给出寻找决策形式背景上区间集约简的方法.     

A representation of disjoint sets with fast initialization

A unified formal treatment of simulation and reduction concepts for parallel computation systems is given. A computation homomorphism, a notion introduced by Kasai and Miller (1979), is used to study the correctness properties of parallel computation systems. The concept of reduction induced by a surjective computation of homomorphism is introduced and its relationship with the similar concept of simulation is studied. The use of reduction is combined to verification techniques based on temporal logic. The results of Berthelot et al. (1979), Kasai and Miller (1979) and Kwong (1977) are unified and generalized.     

信息系统同态的性质及上下近似的不变性

作为研究信息系统之间关系的一种有力工具,信息系统同态的概念首先由J.W.Grzyrnala-Busse引入。本文研究了信息系统同态的一些性质,揭示了构成信息系统同态的对象映射、属性映射与值域映射之间的相互依赖性。由给定的论域上的划分,导出了一个新的信息系统同态,该同态对论域的划分与给定划分相同。同时,讨论了信息系统在同态的意义下,上近似与下近似的不变性,为粗糙集理论的进一步研究奠定了理论基础。