Probabilistic approaches to rough sets

Abstract: Probabilistic approaches to rough sets in granulation, approximation and rule induction are reviewed. The Shannon entropy function is used to quantitatively characterize partitions of a universe. Both algebraic and probabilistic rough set approximations are studied. The probabilistic approximations are defined in a decision‐theoretic framework. The problem of rule induction, a major application of rough set theory, is studied in probabilistic and information‐theoretic terms. Two types of rules are analyzed: the local, low order rules, and the global, high order rules.     

覆盖Value集

覆盖粗糙集和Vague集都是处理不确定性问题的数学工具,它们分别是粗糙集和模糊集的扩展。已有的覆盖粗糙集模型在求上、下近似时,可能将一些实际上并非肯定属于给定集合的元素纳入到下近似中,而一些可能属于给定集合的元素却没有纳入到上近似中,这就会改变一些元素与给定集合的关系。通过深入分析论域中的元素与其相关覆盖元之间的关系,建立了覆盖Vague集。该覆盖Vague集能够从一种新的角度反映出论域中各元素与给定集合之间的从属程度。进一步研究了覆盖Vague集与覆盖粗糙集中一些重要概念之间的关系。最后讨论了当覆盖退化为划分时覆盖Vague集的特性。     

MGRS: A multi-granulation rough set

The original rough set model was developed by Pawlak, which is mainly concerned with the approximation of sets described by a single binary relation on the universe. In the view of granular computing, the classical rough set theory is established through a single granulation. This paper extends Pawlak’s rough set model to a multi-granulation rough set model (MGRS), where the set approximations are defined by using multi equivalence relations on the universe. A number of important properties of MGRS are obtained. It is shown that some of the properties of Pawlak’s rough set theory are special instances of those of MGRS.Moreover, several important measures, such as accuracy measureα, quality of approximationγ and precision of approximationπ, are presented, which are re-interpreted in terms of a classic measure based on sets, the Marczewski-Steinhaus metric and the inclusion degree measure. A concept of approximation reduct is introduced to describe the smallest attribute subset that preserves the lower approximation and upper approximation of all decision classes in MGRS as well. Finally, we discuss how to extract decision rules using MGRS. Unlike the decision rules (“AND” rules) from Pawlak’s rough set model, the form of decision rules in MGRS is “OR”. Several pivotal algorithms are also designed, which are helpful for applying this theory to practical issues. The multi-granulation rough set model provides an effective approach for problem solving in the context of multi granulations.     

Knowledge acquisition in incomplete fuzzy information systems via the rough set approach

Abstract: Machine learning can extract desired knowledge from training examples and ease the development bottleneck in building expert systems. Most learning approaches derive rules from complete and incomplete data sets. If attribute values are known as possibility distributions on the domain of the attributes, the system is called an incomplete fuzzy information system. Learning from incomplete fuzzy data sets is usually more difficult than learning from complete data sets and incomplete data sets. In this paper, we deal with the problem of producing a set of certain and possible rules from incomplete fuzzy data sets based on rough sets. The notions of lower and upper generalized fuzzy rough approximations are introduced. By using the fuzzy rough upper approximation operator, we transform each fuzzy subset of the domain of every attribute in an incomplete fuzzy information system into a fuzzy subset of the universe, from which fuzzy similarity neighbourhoods of objects in the system are derived. The fuzzy lower and upper approximations for any subset of the universe are then calculated and the knowledge hidden in the information system is unravelled and expressed in the form of decision rules.     

Complexity of dimension three and some related edge-covering characteristics of graphs

We study systems of inference rules for multivalued dependencies in database relations. For such systems we define a new notion of completeness in which the underlying universe of attributes is left undetermined, whereas the earlier studied concept of completeness refers to a fixed finite universe. We introduce a new inference rule, the subset rule, and using this rule we prove that a certain system is complete. Furthermore we clarify the role of the so-called complementation rule.     

Positive approximation and converse approximation in interval-valued fuzzy rough sets

Methods of fuzzy rule extraction based on rough set theory are rarely reported in incomplete interval-valued fuzzy information systems. Thus, this paper deals with such systems. Instead of obtaining rules by attribute reduction, which may have a negative effect on inducting good rules, the objective of this paper is to extract rules without computing attribute reducts. The data completeness of missing attribute values is first presented. Positive and converse approximations in interval-valued fuzzy rough sets are then defined, and their important properties are discussed. Two algorithms based on positive and converse approximations, namely, mine rules based on the positive approximation (MRBPA) and mine rules based on the converse approximation (MRBCA), are proposed for rule extraction. The two algorithms are evaluated by several data sets from the UC Irvine Machine Learning Repository. The experimental results show that MRBPA and MRBCA achieve better classification performances than the method based on attribute reduction.     

Fuzzy rough set on probabilistic approximation space over two universes and its application to emergency decision‐making

Probabilistic approaches to rough sets are still an important issue in rough set theory. Although many studies have been written on this topic, they focus on approximating a crisp concept in the universe of discourse, with less effort on approximating a fuzzy concept in the universe of discourse. This article investigates the rough approximation of a fuzzy concept on a probabilistic approximation space over two universes. We first present the definition of a lower and upper approximation of a fuzzy set with respect to a probabilistic approximation space over two universes by defining the conditional probability of a fuzzy event. That is, we define the rough fuzzy set on a probabilistic approximation space over two universes. We then define the fuzzy probabilistic approximation over two universes by introducing a probability measure to the approximation space over two universes. Then, we establish the fuzzy rough set model on the probabilistic approximation space over two universes. Meanwhile, we study some properties of both rough fuzzy sets and fuzzy rough sets on the probabilistic approximation space over two universes. Also, we compare the proposed model with the existing models to show the superiority of the model given in this paper. Furthermore, we apply the fuzzy rough set on the probabilistic approximation over two universes to emergency decision‐making in unconventional emergency management. We establish an approach to online emergency decision‐making by using the fuzzy rough set model on the probabilistic approximation over two universes. Finally, we apply our approach to a numerical example of emergency decision‐making in order to illustrate the validity of the proposed method.     

基于模糊集截集的模糊粗糙集模型

基于L.A.Zadeh模糊集的截集的概念给出了论域U上任意模糊子集的上、下近似的刻画,得到了基于模糊集的截集的粗糙集模型,亦即模糊粗糙集,实现了用论域U中的模糊集近似论域上的任意模糊集,进一步推广了Z.Pawlak粗糙集模型,扩展了粗糙集的应用范围。最后,研究了其基本性质以及其与其他粗糙集模型的关系。     

Soft sets combined with fuzzy sets and rough sets: a tentative approach

Theories of fuzzy sets and rough sets are powerful mathematical tools for modelling various types of uncertainty. Dubois and Prade investigated the problem of combining fuzzy sets with rough sets. Soft set theory was proposed by Molodtsov as a general framework for reasoning about vague concepts. The present paper is devoted to a possible fusion of these distinct but closely related soft computing approaches. Based on a Pawlak approximation space, the approximation of a soft set is proposed to obtain a hybrid model called rough soft sets. Alternatively, a soft set instead of an equivalence relation can be used to granulate the universe. This leads to a deviation of Pawlak approximation space called a soft approximation space, in which soft rough approximations and soft rough sets can be introduced accordingly. Furthermore, we also consider approximation of a fuzzy set in a soft approximation space, and initiate a concept called soft–rough fuzzy sets, which extends Dubois and Prade’s rough fuzzy sets. Further research will be needed to establish whether the notions put forth in this paper may lead to a fruitful theory.     

Non-redundant sequential rules—Theory and algorithm

A sequential rule expresses a relationship between two series of events happening one after another. Sequential rules are potentially useful for analyzing data in sequential format, ranging from purchase histories, network logs and program execution traces.In this work, we investigate and propose a syntactic characterization of a non-redundant set of sequential rules built upon past work on compact set of representative patterns. A rule is redundant if it can be inferred from another rule having the same support and confidence. When using the set of mined rules as a composite filter, replacing a full set of rules with a non-redundant subset of the rules does not impact the accuracy of the filter.We consider several rule sets based on composition of various types of pattern sets—generators, projected-database generators, closed patterns and projected-database closed patterns. We investigate the completeness and tightness of these rule sets. We characterize a tight and complete set of non-redundant rules by defining it based on the composition of two pattern sets. Furthermore, we propose a compressed set of non-redundant rules in a spirit similar to how closed patterns serve as a compressed representation of a full set of patterns. Lastly, we propose an algorithm to mine this compressed set of non-redundant rules. A performance study shows that the proposed algorithm significantly improves both the runtime and compactness of mined rules over mining a full set of sequential rules.     

覆盖粗糙近似的一致性研究

经典粗糙集理论知识的表现形式为论域上的划分,覆盖是比划分更一般的知识表现形式。为了扩展粗糙集理论的应用领域,有必要将粗糙集理论扩展到覆盖近似空间。覆盖近似空间下的概念近似是基于覆盖近似空间知识获取的关键。针对精确概念和模糊概念,研究者定义了不同的近似方法。通过对当前的近似算子进行研究,发现了它们的不一致,并从两个角度对近似算子的定义进行了修正,从而使得它们分别与原有的算子保持一致。所得结论为覆盖近似空间下的概念近似提供了新的研究途径。     

The relationship among soft sets,soft rough sets and topologies

Molodtsov’s soft set theory is a newly emerging tool to deal with uncertain problems. Based on the novel granulation structures called soft approximation spaces, Feng et al. initiated soft rough approximations and soft rough sets. Feng’s soft rough sets can be seen as a generalized rough set model based on soft sets, which could provide better approximations than Pawlak’s rough sets in some cases. This paper is devoted to establishing the relationship among soft sets, soft rough sets and topologies. We introduce the concept of topological soft sets by combining soft sets with topologies and give their properties. New types of soft sets such as keeping intersection soft sets and keeping union soft sets are defined and supported by some illustrative examples. We describe the relationship between rough sets and soft rough sets. We obtain the structure of soft rough sets and the topological structure of soft sets, and reveal that every topological space on the initial universe is a soft approximating space.     

Rule extraction based on granulation order in interval-valued fuzzy information system

Methods of fuzzy rule extraction based on rough set theory are rarely reported in incomplete interval-valued fuzzy information systems. This paper deals with such systems. Instead of obtaining rules by attribute reduction, which may have a negative effect on inducting good rules, the objective of this paper is to extract rules without computing attribute reducts. The data completeness of missing attribute values is first presented. Two different approximation methods are then defined. Two algorithms based on the two approximation methods, called MRBFA and MRBBA are proposed for rule extraction. The two algorithms are evaluated by a housing database from UCI. The experimental results show that MRBFA and MRBBA achieve better classification performances than the method based on attribute reduction.     

不一致决策表规则提取的粗糙集方法

针对不一致决策系统中的规则提取问题,提出一种协调规则提取算法。在粗糙集背景下粒计算描述的基础上,由对象所在的条件信息粒与目标概念的包含度定义对象关于目标概念的隶属度,扩展传统的粗糙近似。给出不一致获取协调规则的算法描述及其时间复杂度。对比分析及说明性算例验证了该算法的有效性和可行性。     

两个论域上的粗集结构

粗集理论是处理不精确和不确定的数据的工具,自Pawlak 提出了粗集理论后,粗集模型得到拓广,人们提出了许多新的粗集模型,在用特征函数的方法表示上下近似的基础上研究两个论域上的粗集结构。统一了粗集的各种推广模型,使得特征函数的方法与通常的集合论的方法形成互补,对粗集结构的简化及推理有帮助,可以加深对粗集结构的认识。     

The further investigation of covering-based rough sets: Uncertainty characterization, similarity measure and generalized models

The notion of rough sets was originally proposed by Pawlak. In Pawlak’s rough set theory, the equivalence relation or partition plays an important role. However, the equivalence relation or partition is restrictive for many applications because it can only deal with complete information systems. This limits the theory’s application to a certain extent. Therefore covering-based rough sets are derived by replacing the partitions of a universe with its coverings. This paper focuses on the further investigation of covering-based rough sets. Firstly, we discuss the uncertainty of covering in the covering approximation space, and show that it can be characterized by rough entropy and the granulation of covering. Secondly, since it is necessary to measure the similarity between covering rough sets in practical applications such as pattern recognition, image processing and fuzzy reasoning, we present an approach which measures these similarities using a triangular norm. We show that in a covering approximation space, a triangular norm can induce an inclusion degree, and that the similarity measure between covering rough sets can be given according to this triangular norm and inclusion degree. Thirdly, two generalized covering-based rough set models are proposed, and we employ practical examples to illustrate their applications. Finally, relationships between the proposed covering-based rough set models and the existing rough set models are also made.     

模糊近似空间上的粗糙模糊集的公理系统

粗糙集理论是近年来发展起来的一种有效的处理不精确、不确定、含糊信息的理论，在机器学习及数据挖掘等领域获得了成功的应用．粗糙集的公理系统是粗糙集理论与应用的基础．粗糙模糊集是粗糙集理论的自然的有意义的推广．作者研究了模糊近似空间上的粗糙模糊集的公理系统，用三条简洁的相互独立的公理完全刻划了模糊近似空间上的粗糙模糊集，同时还把作者给出的公理系统与粗糙集的公理系统做了对比，指出了两者的区别．     

含序信息的粗集方法研究

经典粗集理论给出了不可识别、上近似、下近似、简式和核等概念,其核心思想是运用条件属性集导致的知识粒子来近似决策属性集导致的知识粒子,进而推导出规则。这些知识粒子的实质是根据存在于属性值问的等价关系得到的,而事实上可能存在某些属性,其属性值内部存在序关系,与其它某属性间存在语义关系,这样的属性称为标准。本文所研究的粗集方法,考虑标准所携带的这些信息,推导出含有序信息的规则,并探讨使推导的规则更加完全和一致。本文给出了含序粗集方法（CORS）的定义、数据分析以及规则生成方法,并提出了一种更加合理的质量近似公式以及生成规则的四条原则。     

Rough set theory for the interval-valued fuzzy information systems

The notion of a rough set was originally proposed by Pawlak [Z. Pawlak, Rough sets, International Journal of Computer and Information Sciences 11 (5) (1982) 341-356]. Later on, Dubois and Prade [D. Dubois, H. Prade, Rough fuzzy sets and fuzzy rough sets, International Journal of General System 17 (2-3) (1990) 191-209] introduced rough fuzzy sets and fuzzy rough sets as a generalization of rough sets. This paper deals with an interval-valued fuzzy information system by means of integrating the classical Pawlak rough set theory with the interval-valued fuzzy set theory and discusses the basic rough set theory for the interval-valued fuzzy information systems. In this paper we firstly define the rough approximation of an interval-valued fuzzy set on the universe U in the classical Pawlak approximation space and the generalized approximation space respectively, i.e., the space on which the interval-valued rough fuzzy set model is built. Secondly several interesting properties of the approximation operators are examined, and the interrelationships of the interval-valued rough fuzzy set models in the classical Pawlak approximation space and the generalized approximation space are investigated. Thirdly we discuss the attribute reduction of the interval-valued fuzzy information systems. Finally, the methods of the knowledge discovery for the interval-valued fuzzy information systems are presented with an example.     

一种基于粗糙集理论的最简规则挖掘方法

提出了一种基于粗糙集理论的最简规则挖掘方法，它是一个采用基于分类正确度的粗糙集模型进行多概念分类规则挖掘的新方法，能有效处理决策表的不一致性，采用启发式算法，挖掘出满足给定精确度的最简产生式规则知识。用多个UCI数据集对算法进行了测试，并且与著名的Rosetta软件进行实验对比，结果说明此方法大大提高了总的数据约简量，可以有效地简化最终得到的规则知识。