An enhancement for heuristic attribute reduction algorithm in rough set

Attribute reduction is one of the most important issues in the research of rough set theory. Numerous significance measure based heuristic attribute reduction algorithms have been presented to achieve the optimal reduct. However, how to handle the situation that multiple attributes have equally largest significances is still largely unknown. In this regard, an enhancement for heuristic attribute reduction (EHAR) in rough set is proposed. In some rounds of the process of adding attributes, those that have the same largest significance are not randomly selected, but build attribute combinations and compare their significances. Then the most significant combination rather than a randomly selected single attribute is added into the reduct. With the application of EHAR, two representative heuristic attribute reduction algorithms are improved. Several experiments are used to illustrate the proposed EHAR. The experimental results show that the enhanced algorithms with EHAR have a superior performance in achieving the optimal reduct.     

自适应和声搜索算法及在粗糙集属性约简中的应用

针对改进和声搜索算法（ＩＨＳ）存在的不足,提出了自适应和声搜索算法（ＡＨＳ）．该算法利用和声库中变量函数的最大差值来调节ＰＡＲ 和ｂｗ,从而提高了对多维问题的搜索效率．利用５个标准测试函数对ＡＨＳ算法进行测试,并应用于粗糙集的属性约简中．仿真结果表明了该算法的有效性和实用性．     

An efficient accelerator for attribute reduction from incomplete data in rough set framework

Feature selection (attribute reduction) from large-scale incomplete data is a challenging problem in areas such as pattern recognition, machine learning and data mining. In rough set theory, feature selection from incomplete data aims to retain the discriminatory power of original features. To address this issue, many feature selection algorithms have been proposed, however, these algorithms are often computationally time-consuming. To overcome this shortcoming, we introduce in this paper a theoretic framework based on rough set theory, which is called positive approximation and can be used to accelerate a heuristic process for feature selection from incomplete data. As an application of the proposed accelerator, a general feature selection algorithm is designed. By integrating the accelerator into a heuristic algorithm, we obtain several modified representative heuristic feature selection algorithms in rough set theory. Experiments show that these modified algorithms outperform their original counterparts. It is worth noting that the performance of the modified algorithms becomes more visible when dealing with larger data sets.     

Attribute reduction in decision-theoretic rough set models

Rough set theory can be applied to rule induction. There are two different types of classification rules, positive and boundary rules, leading to different decisions and consequences. They can be distinguished not only from the syntax measures such as confidence, coverage and generality, but also the semantic measures such as decision-monotocity, cost and risk. The classification rules can be evaluated locally for each individual rule, or globally for a set of rules. Both the two types of classification rules can be generated from, and interpreted by, a decision-theoretic model, which is a probabilistic extension of the Pawlak rough set model.As an important concept of rough set theory, an attribute reduct is a subset of attributes that are jointly sufficient and individually necessary for preserving a particular property of the given information table. This paper addresses attribute reduction in decision-theoretic rough set models regarding different classification properties, such as: decision-monotocity, confidence, coverage, generality and cost. It is important to note that many of these properties can be truthfully reflected by a single measure γ in the Pawlak rough set model. On the other hand, they need to be considered separately in probabilistic models. A straightforward extension of the γ measure is unable to evaluate these properties. This study provides a new insight into the problem of attribute reduction.     

A fast approach to attribute reduction in incomplete decision systems with tolerance relation-based rough sets

Efficient attribute reduction in large, incomplete decision systems is a challenging problem; existing approaches have time complexities no less than O(∣C∣²∣U∣²). This paper derives some important properties of incomplete information systems, then constructs a positive region-based algorithm to solve the attribute reduction problem with a time complexity no more than O(∣C∣²∣U∣log∣U∣). Furthermore, our approach does not change the size of the original incomplete system. Numerical experiments show that the proposed approach is indeed efficient, and therefore of practical value to many real-world problems. The proposed algorithm can be applied to both consistent and inconsistent incomplete decision systems.     

An improved attribute reduction scheme with covering based rough sets

Attribute reduction is viewed as an important preprocessing step for pattern recognition and data mining. Most of researches are focused on attribute reduction by using rough sets. Recently, Tsang et al. discussed attribute reduction with covering rough sets in the paper (Tsang et al., 2008), where an approach based on discernibility matrix was presented to compute all attribute reducts. In this paper, we provide a new method for constructing simpler discernibility matrix with covering based rough sets, and improve some characterizations of attribute reduction provided by Tsang et al. It is proved that the improved discernibility matrix is equivalent to the old one, but the computational complexity of discernibility matrix is relatively reduced. Then we further study attribute reduction in decision tables based on a different strategy of identifying objects. Finally, the proposed reduction method is compared with some existing feature selection methods by numerical experiments and the experimental results show that the proposed reduction method is efficient and effective.     

基于Rough Set的属性值约简算法研究

从逻辑的角度分析了属性值约简的本质及过程,在此基础上构造辨识矩阵,提出了一种基于Rough set的属性值约简新算法,并对此进行了证明。该算法比以往的算法更简便、直观,易于编程实现,也更易从本质上理解属性值约简的实质及过程,并且算法不破坏决策系统中的不一致规则所蕴含的信息量。实例分析表明该算法是有效可行的。     

The algebraic structures of generalized rough set theory

Rough set theory is an important technique for knowledge discovery in databases, and its algebraic structure is part of the foundation of rough set theory. In this paper, we present the structures of the lower and upper approximations based on arbitrary binary relations. Some existing results concerning the interpretation of belief functions in rough set backgrounds are also extended. Based on the concepts of definable sets in rough set theory, two important Boolean subalgebras in the generalized rough sets are investigated. An algorithm to compute atoms for these two Boolean algebras is presented.     

变精度粗糙集模型属性约简分析

分析了变精度粗糙集模型属性约简过程出现跳跃的原因,并给出消除跳跃现象的方法。探讨了基于分类质量、相对正域和决策类下近似的属性约简定义,并采用属性添加法对条件属性进行约简,约简过程反映了分类能力的变化。     

计算Web智能研究综述

计算Web智能是近年来提出的一个崭新的研究方向,它结合了计算智能和Web技术,致力于提高Interrlet和无线网络上电子商务等Web应用的智能化程度。首先分析了计算Web智能的研究背景,然后阐述了计算Web智能的概念和相关技术,概括了计算Web智能当前的主要研究内容和应用,最后展望了计算Web智能未来的研究方向及面临的挑战。     

A general approach to attribute reduction in rough set theory

The concept of a consistent approximation representation space is introduced. Many types of information systems can be treated and unified as consistent ap- proximation representation spaces. At the same time, under the framework of this space, the judgment theorem for determining consistent attribute set is established, from which we can obtain the approach to attribute reductions in information systems. Also, the characterizations of three important types of attribute sets (the core attribute set, the relative necessary attribute set and the unnecessary attribute set) are examined.     

基于粒度计算的属性约简算法研究

从粒度计算的角度对粗糙集理论的属性约简进行研究,分别基于代数方法和信息论方法定义了粒度差和粒度熵的概念,并在此基础上提出了两种新的属性约简算法.实验分析表明,这两种可靠有效的粒度计算方法都能得到信息表的最小约简,为进一步研究知识的粒度计算提供了可行的方法.     

A fuzzy record-to-record travel algorithm for solving rough set attribute reduction

Attribute reduction can be defined as the process of determining a minimal subset of attributes from an original set of attributes. This paper proposes a new attribute reduction method that is based on a record-to-record travel algorithm for solving rough set attribute reduction problems. This algorithm has a solitary parameter called the DEVIATION, which plays a pivotal role in controlling the acceptance of the worse solutions, after it becomes pre-tuned. In this paper, we focus on a fuzzy-based record-to-record travel algorithm for attribute reduction (FuzzyRRTAR). This algorithm employs an intelligent fuzzy logic controller mechanism to control the value of DEVIATION, which is dynamically changed throughout the search process. The proposed method was tested on standard benchmark data sets. The results show that FuzzyRRTAR is efficient in solving attribute reduction problems when compared with other meta-heuristic approaches.     

Topological approaches to covering rough sets

Rough sets, a tool for data mining, deal with the vagueness and granularity in information systems. This paper studies covering-based rough sets from the topological view. We explore the topological properties of this type of rough sets, study the interdependency between the lower and the upper approximation operations, and establish the conditions under which two coverings generate the same lower approximation operation and the same upper approximation operation. Lastly, axiomatic systems for the lower approximation operation and the upper approximation operation are constructed.     

一种新的粗糙集属性约简方法及其应用

对粗糙集理论中属性约简问题进行研究,借助于离散化获得的断点,提出一种指导属性约简的新方法,并提出一种改进的连续属性值离散化方法.以雷达辐射源用途识别为例.给出了识别实例和计算机仿真实验,并与工程中常用的统计模式识别方法进行比较,结果证明了该算法的正确性和有效性.     

基于粒化单调的不完备混合型数据增量式属性约简算法

增量式属性约简是一种针对动态数据集的新型属性约简方法.然而目前的增量式属性约简很少有对不完备混合型的信息系统进行研究.针对这类问题提出一种属性增加时的增量式属性约简算法.在不完备混合型信息系统下引入邻域容差关系.基于邻域容差关系的粒化单调性,提出信息系统属性增加时邻域容差条件熵的增量式更新方法,并提出了不完备混合型信息...     

基于系统熵的粗糙集属性约简新方法

在系统熵的基础上,定义了一种新的属性重要度并提出了一种基于改进系统熵的粗糙集属性约简算法,实验分析表明,该属性重要度为启发式信息进行的属性约简,取得了理想效果。     

基于可辨识矩阵的快速粗糙集属性约简算法

Karno Bozi提出的Core Searching算法在向约简中插入候选属性的时候,根据属性出现次数需要循环查找可辨识矩阵中的所有剩余项,直至矩阵为空,导致计算量较大和结果中冗余属性存在的可能.基于Core Searching算法提出通过给属性设立计数器的基于可辨识矩阵的快速属性约简算法,实例分析表明,该算法与Core Searching算法相比,在计算量减少和循环次数减少的同时能得到更简约的结果,是一种快速、高效的属性约简算法.     

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.     

基于直觉模糊粗糙集的属性约简

针对Jensen下近似定义的局限性,提出一种新的等价类形式的近似算子表示,并将其推广到直觉模糊环境.在此基础上,将相对正域、相对约简、相对核等粗糙集的知识约简概念推广到直觉模糊环境,提出一种直觉模糊信息系统的启发式属性约筒算法.实例计算表明.该方法比Jensen的属性约简方法更为合理有效.