覆盖族生成拓扑的约简

本文研究了在覆盖族产生的拓扑不变的条件下覆盖族的约简问题.利用拓扑学理论讨论覆盖广义粗糙集的约简理论,给出计算约简的方法,丰富了覆盖广义粗糙集理论.     

Four matroidal structures of covering and their relationships with rough sets

Covering is a common form of data representation, and covering-based rough sets serve as an efficient technique to process this type of data. However, many important problems such as covering reduction in covering-based rough sets are NP-hard so that most algorithms to solve them are greedy. Matroids provide well-established platforms for greedy algorithm foundation and implementation. Therefore, it is necessary to integrate covering-based rough set with matroid. In this paper, we propose four matroidal structures of coverings and establish their relationships with rough sets. First, four different viewpoints are presented to construct these four matroidal structures of coverings, including 1-rank matroids, bigraphs, upper approximation numbers and transversals. The respective advantages of these four matroidal structures to rough sets are explored. Second, the connections among these four matroidal structures are studied. It is interesting to find that they coincide with each other. Third, a converse view is provided to induce a covering by a matroid. We study the relationship between this induction and the one from a covering to a matroid. Finally, some important concepts of covering-based rough sets, such as approximation operators, are equivalently formulated by these matroidal structures. These interesting results demonstrate the potential to combine covering-based rough sets with matroids.     

Reduction about approximation spaces of covering generalized rough sets

The introduction of covering generalized rough sets has made a substantial contribution to the traditional theory of rough sets. The notion of attribute reduction can be regarded as one of the strongest and most significant results in rough sets. However, the efforts made on attribute reduction of covering generalized rough sets are far from sufficient. In this work, covering reduction is examined and discussed. We initially construct a new reduction theory by redefining the approximation spaces and the reducts of covering generalized rough sets. This theory is applicable to all types of covering generalized rough sets, and generalizes some existing reduction theories. Moreover, the currently insufficient reducts of covering generalized rough sets are improved by the new reduction. We then investigate in detail the procedures to get reducts of a covering. The reduction of a covering also provides a technique for data reduction in data mining.     

Covering rough sets based on neighborhoods: An approach without using neighborhoods

Rough set theory, a mathematical tool to deal with inexact or uncertain knowledge in information systems, has originally described the indiscernibility of elements by equivalence relations. Covering rough sets are a natural extension of classical rough sets by relaxing the partitions arising from equivalence relations to coverings. Recently, some topological concepts such as neighborhood have been applied to covering rough sets. In this paper, we further investigate the covering rough sets based on neighborhoods by approximation operations. We show that the upper approximation based on neighborhoods can be defined equivalently without using neighborhoods. To analyze the coverings themselves, we introduce unary and composition operations on coverings. A notion of homomorphism is provided to relate two covering approximation spaces. We also examine the properties of approximations preserved by the operations and homomorphisms, respectively.     

基于精度的属性约简新方法

自Pawlak提出粗糙集概念以来,人们就一直对粗糙集的近似精度很感兴趣,出现了不少有关近似精度的文献.在粗糙集理论中,精度是量化由粗糙集边界引起的不精确性的一种重要数字特征.在分析传统精度和基于等价关系图的过剩熵的近似精度的基础上,提出了一种新的精度定义.比较发现,新定义的精度更具有合理性.同时把这个新定义的精度运用到了属性约简上,通过实例比较发现,本文提出的属性约简更具有可行性.     

Updating attribute reduction in incomplete decision systems with the variation of attribute set

In rough set theory, attribute reduction is a challenging problem in the applications in which data with numbers of attributes available. Moreover, due to dynamic characteristics of data collection in decision systems, attribute reduction will change dynamically as attribute set in decision systems varies over time. How to carry out updating attribute reduction by utilizing previous information is an important task that can help to improve the efficiency of knowledge discovery. In view of that attribute reduction algorithms in incomplete decision systems with the variation of attribute set have not yet been discussed so far. This paper focuses on positive region-based attribute reduction algorithm to solve the attribute reduction problem efficiently in the incomplete decision systems with dynamically varying attribute set. We first introduce an incremental manner to calculate the new positive region and tolerance classes. Consequently, based on the calculated positive region and tolerance classes, the corresponding attribute reduction algorithms on how to compute new attribute reduct are put forward respectively when an attribute set is added into and deleted from the incomplete decision systems. Finally, numerical experiments conducted on different data sets from UCI validate the effectiveness and efficiency of the proposed algorithms in incomplete decision systems with the variation of attribute set.     

A rough set approach to the characterization of transversal matroids

Rough sets are efficient for data pre-processing during data mining. However, some important problems such as attribute reduction in rough sets are NP-hard and the algorithms required to solve them are mostly greedy ones. The transversal matroid is an important part of matroid theory, which provides well-established platforms for greedy algorithms. In this study, we investigate transversal matroids using the rough set approach. First, we construct a covering induced by a family of subsets and we propose the approximation operators and upper approximation number based on this covering. We present a sufficient condition under which a subset is a partial transversal, and also a necessary condition. Furthermore, we characterize the transversal matroid with the covering-based approximation operator and construct some types of circuits. Second, we explore the relationships between closure operators in transversal matroids and upper approximation operators based on the covering induced by a family of subsets. Finally, we study two types of axiomatic characterizations of the covering approximation operators based on the set theory and matroid theory, respectively. These results provide more methods for investigating the combination of transversal matroids with rough sets.     

覆盖广义粗糙集的模糊性

在研究覆盖广义粗糙集的基础上,利用两个距离函数Hamming和Euclidean距离函数,结合模糊集的最近寻常集,引入了覆盖广义粗糙集模糊度的概念,给出了一种模糊度计算方法,并证明了该模糊度的一些重要性质。这些结果在覆盖广义粗糙集的理论研究和应用都发挥着一定作用。     

Entropy and co-entropy of a covering approximation space

The notions of entropy and co-entropy associated to partitions have been generalized to coverings when Pawlak’s rough set theory based on partitions has been extended to covering rough sets. Unfortunately, the monotonicities of entropy and co-entropy with respect to the standard partial order on partitions do not behave well in this generalization. Taking the coverings and the covering lower and upper approximation operations into account, we introduce a novel entropy and the corresponding co-entropy in this paper. The new entropy and co-entropy exhibit the expected monotonicity, provide a measure for the fineness of the pairs of the covering lower and upper approximation operations, and induce a quasi-order relation on coverings. We illustrate the theoretical development by the first, second, and third types of covering lower and upper approximation operations.     

知识库的精细关系比较

比较知识库精细关系的两种不同定义,得出等价关系与划分、二元关系与覆盖、以及二元关系与覆盖约简之间的一些有趣联系;进而探讨这两种定义在粗糙集中对提高知识确定性程度的不同作用.这些结论将对基于粗糙集的不确定性研究提供一定的帮助.     

覆盖空间及粗糙集与拓扑的统一

引入覆盖空间,定义了其邻域、内部、闭包、测度等概念,研究了它们的性质.得出了粗糙集近似空间和拓扑空间都是具体覆盖空间的重要结论,从而用覆盖空间统一了粗糙集和拓扑.利用覆盖空间,得到了粗糙集和拓扑中更深刻的性质,从算子论和集合论的角度丰富和深化了粗糙集与拓扑的内容.     

On some types of neighborhood-related covering rough sets

Covering rough sets are natural extensions of the classical rough sets by relaxing the partitions to coverings. Recently, the concept of neighborhood has been applied to define different types of covering rough sets. In this paper, by introducing a new notion of complementary neighborhood, we consider some types of neighborhood-related covering rough sets, two of which are firstly defined. We first show some basic properties of the complementary neighborhood. We then explore the relationships between the considered covering rough sets and investigate the properties of them. It is interesting that the set of all the lower and upper approximations belonging to the considered types of covering rough sets, equipped with the binary relation of inclusion ?, constructs a lattice. Finally, we also discuss the topological importance of the complementary neighborhood and investigate the topological properties of the lower and upper approximation operators.     

多粒度模糊粗糙集研究

本文研究了模糊粗糙集中属性约简问题.利用模糊粗糙集和多粒度粗糙集各自优点的结合,提出了两类多粒度模糊粗糙集模型,使得两类粗糙集中的上下近似算子关于负算子对偶.同时研究了多粒度模糊粗糙集的性质及与单粒度模糊粗糙集的关系.并通过构造区分函数的方法提出了一类多粒度模糊粗糙集模型的近似约简方法.最后用一个实例核对了该类多粒度模糊粗糙决策系统近似约简方法的有效性.     

模糊信息系统属性重要性度量

利用包含度工具将粗糙集方法应用在模糊信息系统中,给出了模糊信息系统中属性重要性度量计算方法,通过举例说明了[3]中关于属性重要性度量概念的局限性。     

广义覆盖粗集的约简

在保持一对覆盖上、下近似算子不变的条件下,探讨覆盖族的约简.利用所构造的辩识矩阵给出覆盖族的约简与核心的判别定理,并提出基于信息量的寻找最小约简的算法,从而进一步完善广义覆盖粗集的约简理论.     

The reduction and fusion of fuzzy covering systems based on the evidence theory

This paper studies reduction of a fuzzy covering and fusion of multi-fuzzy covering systems based on the evidence theory and rough set theory. A novel pair of belief and plausibility functions is defined by employing a method of non-classical probability model and the approximation operators of a fuzzy covering. Then we study the reduction of a fuzzy covering based on the functions we presented. In the case of multiple information sources, we present a method of information fusion for multi-fuzzy covering systems, by which objects can be well classified in a fuzzy covering decision system. Finally, by using the method of maximum flow, we discuss under what conditions, fuzzy covering approximation operators can be induced by a fuzzy belief structure.     

NMGRS: Neighborhood-based multigranulation rough sets

Recently, a multigranulation rough set (MGRS) has become a new direction in rough set theory, which is based on multiple binary relations on the universe. However, it is worth noticing that the original MGRS can not be used to discover knowledge from information systems with various domains of attributes. In order to extend the theory of MGRS, the objective of this study is to develop a so-called neighborhood-based multigranulation rough set (NMGRS) in the framework of multigranulation rough sets. Furthermore, by using two different approximating strategies, i.e., seeking common reserving difference and seeking common rejecting difference, we first present optimistic and pessimistic 1-type neighborhood-based multigranulation rough sets and optimistic and pessimistic 2-type neighborhood-based multigranulation rough sets, respectively. Through analyzing several important properties of neighborhood-based multigranulation rough sets, we find that the new rough sets degenerate to the original MGRS when the size of neighborhood equals zero. To obtain covering reducts under neighborhood-based multigranulation rough sets, we then propose a new definition of covering reduct to describe the smallest attribute subset that preserves the consistency of the neighborhood decision system, which can be calculated by Chen’s discernibility matrix approach. These results show that the proposed NMGRS largely extends the theory and application of classical MGRS in the context of multiple granulations.     

Rough set based maximum relevance-maximum significance criterion and Gene selection from microarray data

Among the large amount of genes presented in microarray gene expression data, only a small fraction of them is effective for performing a certain diagnostic test. In this regard, a new feature selection algorithm is presented based on rough set theory. It selects a set of genes from microarray data by maximizing the relevance and significance of the selected genes. A theoretical analysis is presented to justify the use of both relevance and significance criteria for selecting a reduced gene set with high predictive accuracy. The importance of rough set theory for computing both relevance and significance of the genes is also established. The performance of the proposed algorithm, along with a comparison with other related methods, is studied using the predictive accuracy of K-nearest neighbor rule and support vector machine on five cancer and two arthritis microarray data sets. Among seven data sets, the proposed algorithm attains 100% predictive accuracy for three cancer and two arthritis data sets, while the rough set based two existing algorithms attain this accuracy only for one cancer data set.     

基于粗集与概念格的属性简约讨论

概念格的属性简约是在形式背景下解决复杂问题的重要途径,通过对概念格、粗糙集的讨论,将两者有效结合,并借助粗糙集上(下)近似的方法,得出了一个对概念格属性简约的方法,方法将二维的概念格属性简约转化为一维的一种对象格的简约,避免了形式背景下的概念的计算和进一步的可辨识矩阵的计算,方法简便,算法简单易实现,是概念格属性简约有效的算法.     

属性粗糙集的新型近似算子

由等价类中元素属性测度的上、下确界定义的属性粗糙集,没有充分反映等价类中其它元素的作用,在信息处理中不免造成元素信息的丢失.为此提出一种新的属性粗糙集近似算子的表示方法,给出了相应的性质并实例说明了这一方法的合理性.