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.     

Approximations and reducts with covering generalized rough sets

The covering generalized rough sets are an improvement of traditional rough set model to deal with more complex practical problems which the traditional one cannot handle. It is well known that any generalization of traditional rough set theory should first have practical applied background and two important theoretical issues must be addressed. The first one is to present reasonable definitions of set approximations, and the second one is to develop reasonable algorithms for attributes reduct. The existing covering generalized rough sets, however, mainly pay attention to constructing approximation operators. The ideas of constructing lower approximations are similar but the ideas of constructing upper approximations are different and they all seem to be unreasonable. Furthermore, less effort has been put on the discussion of the applied background and the attributes reduct of covering generalized rough sets. In this paper we concentrate our discussion on the above two issues. We first discuss the applied background of covering generalized rough sets by proposing three kinds of datasets which the traditional rough sets cannot handle and improve the definition of upper approximation for covering generalized rough sets to make it more reasonable than the existing ones. Then we study the attributes reduct with covering generalized rough sets and present an algorithm by using discernibility matrix to compute all the attributes reducts with covering generalized rough sets. With these discussions we can set up a basic foundation of the covering generalized rough set theory and broaden its applications.     

Rough Set理论中连续属性的离散化方法

Rough Set(RS)理论是一种新的处理不精确、不完全与不相容知识的数学工具.传 统的RS理论只能对数据库中的离散属性进行处理,而绝大多数现实的数据库既包含了离散 属性,又包含了连续属性.文中针对传统RS理论的这一缺陷,利用决策表相容性的反馈信 息,提出了一种领域独立的基于动态层次聚类的连续属性离散化算法.该方法为RS理论处 理离散与连续属性提供了一种统一的框架,从而极大地拓广了RS理论的应用范围.通过一 些例子将本算法与现有方法进行了比较分析,得到了令人鼓舞的结果.     

基于相对决策嫡的决策树算法及其在入侵检测中的应用

为了弥补传统决策树算法的不足,提出一种基于相对决策熵的决策树算法DTRDE。首先,将Shannon提出的信息熵引入到粗糙集理论中,定义一个相对决策熵的概念,并利用相对决策熵来度量属性的重要性;其次,在算法DTRDE中,采用基于相对决策熵的属性重要性以及粗糙集中的属性依赖性来选择分离属性,并且利用粗糙集中的属性约简技术来删除冗余的属性,旨在降低算法的计算复杂性;最后,将该算法应用于网络入侵检测。在KDD Cup99数据集上的实验表明,DTRDE算法比传统的基于信息熵的算法具有更高的检测率,而其计算开销则与传统方法接近。     

复合覆盖粗糙集模型及其应用

针对覆盖粗糙集仅适用于单一数据类型的论域覆盖的问题,提出复合覆盖粗糙集模型。在研究邻域覆盖粗糙集、集值覆盖粗糙集、区间值覆盖粗糙集的基础上,在复合数据模型下,通过建立多种覆盖关系（邻域覆盖、集值覆盖、区间值覆盖等）,提出复合覆盖粗糙集模型,并给出复合覆盖粗糙集相关概念及性质。该模型适用于多种数据类型（符号数据、区间数据、集合数据、数值数据等）的论域覆盖问题,通过实例说明了该模型在复合信息系统中的应用,进一步加深对复合覆盖粗糙集相关概念的理解。     

Fuzzy rough set based attribute reduction for information systems with fuzzy decisions

Fuzzy rough set is a generalization of crisp rough set to deal with data sets with real value attributes. A primary use of fuzzy rough set theory is to perform attribute reduction for decision systems with numerical conditional attribute values and crisp (symbolic) decision attributes. In this paper we define inconsistent fuzzy decision system and their reductions, and develop discernibility matrix-based algorithms to find reducts. Finally, two heuristic algorithms are developed and comparison study is provided with the existing algorithms of attribute reduction with fuzzy rough sets. The proposed method in this paper can deal with decision systems with numerical conditional attribute values and fuzzy decision attributes rather than crisp ones. Experimental results imply that our algorithm of attribute reduction with general fuzzy rough sets is feasible and valid.     

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

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

基于相似度的粗糙集近似算子快速求解

由于经典粗糙集只能处理精确分类问题,基于相似度的粗糙集模型被提出并用于解决不完备信息系统的相关问题.粗糙集通过近似算子对某一给定的概念进行近似表示,科学的求解这些算子对粗糙集理论的发展具有重要意义.本文提出一种新的近似算子快速求解方法,分析证明了所提快速方法比经典方法具有更高的求解效率.文章定义了元素覆盖度、集合覆盖度等概念,使用覆盖度等价关系可以将覆盖粗糙集转化为经典粗糙集,从而简化覆盖粗糙集的相关问题的解决.     

Parameter reductions in N‐soft sets and their applications in decision‐making

Parameter reduction is an important operation for improving the performance of decision‐making processes in various uncertainty theories. The theory of N‐soft sets is emerging as a powerful mathematical tool for dealing with uncertainties beyond the standard formulation of the soft set theory. In this research article, we extend the notion of parameter reduction to N‐soft set theory, and we also justify its practical calculation. To this purpose, we define related theoretical concepts (e.g. N‐soft subset, reduct N‐soft set and redundant parameter) and examine some of their fundamental properties. Then, we argue that the idea of attributes reduction from the rough set theory cannot be employed in the N‐soft set theory in order to reduce the number of parameters. Consequently, we take an original position in order to adequately define and compute parameter reductions in N‐soft sets. Finally, we develop an application of parameter reduction of N‐soft sets.     

On axiomatic characterizations of three pairs of covering based approximation operators

Rough set theory is a useful tool for dealing with inexact, uncertain or vague knowledge in information systems. The classical rough set theory is based on equivalence relations and has been extended to covering based generalized rough set theory. This paper investigates three types of covering generalized rough sets within an axiomatic approach. Concepts and basic properties of each type of covering based approximation operators are first reviewed. Axiomatic systems of the covering based approximation operators are then established. The independence of axiom set for characterizing each type of covering based approximation operators is also examined. As a result, two open problems about axiomatic characterizations of covering based approximation operators proposed by Zhu and Wang in (IEEE Transactions on Knowledge and Data Engineering 19(8) (2007) 1131-1144, Proceedings of the Third IEEE International Conference on Intelligent Systems, 2006, pp. 444-449) are solved.     

覆盖多粒度梯形模糊数决策理论粗糙集模型

作为经典Pawlak粗糙集模型的推广,基于论域上的等价关系,针对风险决策分类问题,多粒度粗糙集已有研究。其特点是在力争决策的期望损失（亦称决策的条件风险）最小的条件下,比较客观地确定对象分类区域的概率描述临界值,进而进行对象的最佳分类决策。然而,在实际应用中论域上的等价关系很难把握,况且特征状态的风险损失往往带有某种不确定性。凡此,无疑在一定程度上限制了多粒度决策理论粗糙集的应用。对此进行了研究：提出了覆盖多粒度梯形模糊数决策理论粗糙集模型,分别就平均、乐观和悲观的情形进行了讨论和刻划;得到了覆盖多粒度梯形模糊数决策理论粗糙集与已有相关模型之间的关系;结果和算例表明了模型的广泛性。     

一致覆盖决策系统的属性约简

现实生活中总存在大量复杂且庞大的数据库,运用同态函数的概念可以对一致覆盖决策系统进行数据压缩。首先介绍关于覆盖的一致函数的定义、覆盖映射的概念以及相关属性,然后提出一致覆盖决策系统中同态函数的定义,并证得一个一致覆盖决策系统可以被压缩成一个相对规模较小的决策系统。同时,在同态函数的条件下,两者的属性约简等价。     

多粒度覆盖信息系统的属性约简方法比较

为拓展覆盖粗糙集模型,用多粒度方法研究了张燕兰等提出的广义覆盖决策信息系统模型,定义了多粒度意义下的覆盖上下近似,提出了多粒度属性约简算法。用实例对多粒度覆盖粗糙集属性约简方法和胡清华等提出的单粒度方法进行了比较。     

医疗健康数据的模糊粗糙集规则挖掘方法研究

医疗健康数据通常属性较多,且存在连续型、离散型并存的混合数据,这在很大程度上限制了知识发现方法对医疗健康数据的挖掘效率。以模糊粗糙集理论为基础,研究混合数据上的分类规则挖掘方法,通过引入规则获取算法的泛化阈值,来控制获取规则集的大小和复杂程度,提高粗糙集知识发现方法在医疗健康数据上的分类效率。最后通过对比实验验证了该算法在医疗决策表上挖掘规则的有效性。     

覆盖概率粗糙集的模糊性

在经典覆盖近似空间中定义了论域上任意元素x的最小子覆盖,基于任意元素的最小子覆盖给出了覆盖粗糙集上、下近似新的描述,进而给出了已有覆盖概率粗糙集模型在最小子覆盖意义下的描述。同时,以覆盖概率粗糙集的粗糙隶属函数为基础,应用经典模糊集熵的概念讨论了覆盖概率粗糙集模糊性的度量。     

不协调目标信息系统的知识约简

在不协调目标信息系统中引入了最大分布约简的概念，讨论了最大分布约简、分配约简、分布约简和近拟约简之间的关系。最大分布 间弱于分布约简，克服了对信息系统过于苛刻的要求。同时，它又克服了分配约简可能产生与原系统不相容的命题规则的缺陷；给出了这些知识约简的判定定理和相应的可辨识属性矩阵，从而提供了不协调目标信息系统的知识约简的新方法。     

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.     

多尺度集值决策信息系统

集值信息系统中的对象的属性值多值化,可以实现对复杂信息更全面的刻画.在传统的集值信息系统中,每个属性只有一个尺度.但在具体应用中,人们往往需要在不同的尺度上处理和分析数据.为此,将多尺度信息系统的粒度转换函数引入集值信息系统中,建立多尺度集值信息系统的理论框架,并讨论该系统的不同尺度间信息粒、粗糙集的关系.在此基础上,...     

智能决策中的模糊近似

信息表通过目标集合来描述，目标通过条件属性和决策属性进行描述，在对这样的信息表分析处理过程中，粗糙集理论是一个非常有用的工具，粗糙集合理论的主要观点就是知识的上下近似，在实际中，条件属性和决策属性的概念通常是模糊的，而且可以利用模糊集合来说明，提出了基于模糊集合和粗糙集结合的一种新方法，对包含度进行了定义，给出了截近似和综合函数的概念，应用这些概念并结合具体例子讨论了条件属性和决策属性之间的关系，为决策过程中对条件属性权值的指定提供了理论基础。     

不一致决策表的k阶分配序约简

在不一致决策表中定义了k阶分配序约简，给出了k阶分配序一致集的判定定理。通过定义k阶分配序区分矩阵，给出了求k阶分配序约简的区分矩阵法。为了克服区分矩阵法时间复杂度过高的缺陷，通过定义属性的相对重要性，提出了一种求k阶分配序约简的启发式算法，分析得到该算法的时间复杂度是多项式的结论。实例验证了算法的有效性。