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.     

Rough set theory: a novel approach for extraction of robust decision rules based on incremental attributes

Rough set theory is a new data mining approach to manage vagueness. It is capable to discover important facts hidden in the data. Literature indicate the current rough set based approaches can’t guarantee that classification of a decision table is credible and it is not able to generate robust decision rules when new attributes are incrementally added in. In this study, an incremental attribute oriented rule-extraction algorithm is proposed to solve this deficiency commonly observed in the literature related to decision rule induction. The proposed approach considers incremental attributes based on the alternative rule extraction algorithm (AREA), which was presented for discovering preference-based rules according to the reducts with the maximum of strength index (SI), specifically the case that the desired reducts are not necessarily unique since several reducts could include the same value of SI. Using the AREA, an alternative rule can be defined as the rule which holds identical preference to the original decision rule and may be more attractive to a decision-maker than the original one. Through implementing the proposed approach, it can be effectively operating with new attributes to be added in the database/information systems. It is not required to re-compute the updated data set similar to the first step at the initial stage. The proposed algorithm also excludes these repetitive rules during the solution search stage since most of the rule induction approaches generate the repetitive rules. The proposed approach is capable to efficiently and effectively generate the complete, robust and non-repetitive decision rules. The rules derived from the data set provide an indication of how to effectively study this problem in further investigations.     

Attribute reduction based on generalized fuzzy evidence theory in fuzzy decision systems

Attribute reduction is viewed as an important issue in data mining and knowledge representation. This paper studies attribute reduction in fuzzy decision systems based on generalized fuzzy evidence theory. The definitions of several kinds of attribute reducts are introduced. The relationships among these reducts are then investigated. In a fuzzy decision system, it is proved that the concepts of fuzzy positive region reduct, lower approximation reduct and generalized fuzzy belief reduct are all equivalent, the concepts of fuzzy upper approximation reduct and generalized fuzzy plausibility reduct are equivalent, and a generalized fuzzy plausibility consistent set must be a generalized fuzzy belief consistent set. In a consistent fuzzy decision system, an attribute set is a generalized fuzzy belief reduct if and only if it is a generalized fuzzy plausibility reduct. But in an inconsistent fuzzy decision system, a generalized fuzzy belief reduct is not a generalized fuzzy plausibility reduct in general.     

Evidence-theory-based numerical algorithms of attribute reduction with neighborhood-covering rough sets

Covering rough sets generalize traditional rough sets by considering coverings of the universe instead of partitions, and neighborhood-covering rough sets have been demonstrated to be a reasonable selection for attribute reduction with covering rough sets. In this paper, numerical algorithms of attribute reduction with neighborhood-covering rough sets are developed by using evidence theory. We firstly employ belief and plausibility functions to measure lower and upper approximations in neighborhood-covering rough sets, and then, the attribute reductions of covering information systems and decision systems are characterized by these respective functions. The concepts of the significance and the relative significance of coverings are also developed to design algorithms for finding reducts. Based on these discussions, connections between neighborhood-covering rough sets and evidence theory are set up to establish a basic framework of numerical characterizations of attribute reduction with these sets.     

A fast heuristic attribute reduction approach to ordered decision systems

Rough set theory has shown success in being a filter-based feature selection approach for analyzing information systems. One of its main aims is to search for a feature subset called a reduct, which preserves the classification ability of the original system. In this paper, we consider ordered decision systems, where the preference order, a fundamental concept in dominance-based rough set approach, plays a critical role. In recent literature, based on the greedy hill climbing method, many heuristic attribute reduction algorithms are proposed by utilizing significance measures of attributes, and they are extended to deal with ordered decision systems. Unfortunately, they are often time-consuming, especially when applied to deal with large scale data sets with high dimensions. To reduce the complexity, a novel accelerator is introduced in heuristic algorithms from the perspectives of objects and criteria. Based on the new accelerator, the number of objects and the dimension of criteria are lessened thus making the accelerated algorithms faster than their original counterparts while maintaining the same reducts. Experimental analysis shows the validity and efficiency of the proposed methods.     

Dependence-space-based attribute reductions in inconsistent decision information systems

In rough set theory, attribute reduction is an important mechanism for knowledge discovery. This paper mainly deals with attribute reductions of an inconsistent decision information system based on a dependence space. Through the concept of inclusion degree, a generalized decision distribution function is first constructed. A decision distribution relation is then defined. On the basis of this decision distribution relation, a dependence space is proposed, and an equivalence congruence based on the indiscernibility attribute sets is also obtained. Applying the congruences on a dependence space, new approaches to find a distribution consistent set are formulated. The judgement theorems for judging distribution consistent sets are also established by using these congruences and the decision distribution relation.     

Multi-confidence rule acquisition and confidence-preserved attribute reduction in interval-valued decision systems

Rule acquisition is one of the most important objectives in the analysis of decision systems. Because of the interference of errors, a real-world decision system is generally inconsistent, which can lead to the consequence that some rules extracted from the system are not certain but possible rules. In practice, however, the possible rules with high confidence are also useful in making decision. With this consideration, we study how to extract from an interval-valued decision system the compact decision rules whose confidences are not less than a pre-specified threshold. Specifically, by properly defining a binary relation on an interval-valued information system, the concept of interval-valued granular rules is presented for the interval-valued decision system. Then, an index is introduced to measure the confidence of an interval-valued granular rule and an implication relationship is defined between the interval-valued granular rules whose confidences are not less than the threshold. Based on the implication relationship, a confidence-preserved attribute reduction approach is proposed to extract compact decision rules and a combinatorial optimization-based algorithm is developed to compute all the reducts of an interval-valued decision system. Finally, some numerical experiments are conducted to evaluate the performance of the reduction approach and the gain of using the possible rules in making decision.     

基于粗糙集的突发事件属性约简方法

针对突发事件不完备信息系统中的原始数据存在大量属性冗余的问题,提出一种基于粗糙集的不完备信息系统属性约简方法,以剔除冗余属性,提高知识清晰度。首先对缺失、冗余、噪声以及连续型数据进行预处理;然后进行属性分类,将属性分为条件属性与决策属性,进而建立决策表;最后根据决策表的特征,结合有序加权平均算子的思想,提出一种基于属性重要度的启发式属性约简算法。文末,通过实例验证了方法的正确性与有效性,并利用该方法实现了火灾数据的属性约简。     

A relational perspective of attribute reduction in rough set-based data analysis

Attribute reduction is very important in rough set-based data analysis (RSDA) because it can be used to simplify the induced decision rules without reducing the classification accuracy. The notion of reduct plays a key role in rough set-based attribute reduction. In rough set theory, a reduct is generally defined as a minimal subset of attributes that can classify the same domain of objects as unambiguously as the original set of attributes. Nevertheless, from a relational perspective, RSDA relies on a kind of dependency principle. That is, the relationship between the class labels of a pair of objects depends on component-wise comparison of their condition attributes. The larger the number of condition attributes compared, the greater the probability that the dependency will hold. Thus, elimination of condition attributes may cause more object pairs to violate the dependency principle. Based on this observation, a reduct can be defined alternatively as a minimal subset of attributes that does not increase the number of objects violating the dependency principle. While the alternative definition coincides with the original one in ordinary RSDA, it is more easily generalized to cases of fuzzy RSDA and relational data analysis.     

Hybrid approaches to attribute reduction based on indiscernibility and discernibility relation

Attribute reduction is one of the key issues in rough set theory. Many heuristic attribute reduction algorithms such as positive-region reduction, information entropy reduction and discernibility matrix reduction have been proposed. However, these methods are usually computationally time-consuming for large data. Moreover, a single attribute significance measure is not good for more attributes with the same greatest value. To overcome these shortcomings, we first introduce a counting sort algorithm with time complexity O(∣C∣ ∣U∣) for dealing with redundant and inconsistent data in a decision table and computing positive regions and core attributes (∣C∣ and ∣U∣ denote the cardinalities of condition attributes and objects set, respectively). Then, hybrid attribute measures are constructed which reflect the significance of an attribute in positive regions and boundary regions. Finally, hybrid approaches to attribute reduction based on indiscernibility and discernibility relation are proposed with time complexity no more than max(O(∣C∣²∣U/C∣), O(∣C∣∣U∣)), in which ∣U/C∣ denotes the cardinality of the equivalence classes set U/C. The experimental results show that these proposed hybrid algorithms are effective and feasible for large data.     

Interactive weight assessment in multiple attribute decision making

A weight assessing method is given for solving a multiple attribute decision problem involving one decision maker. The method provides significant freedom to the decision maker who is asked only to specify certain groups of attributes and the corresponding joint weights. The method then provides a sophisticated interaction between various levels of the attributes involved. Furthermore, if the decision maker wishes to give additional information of the above-mentioned kind, he establishes an interaction on the level of the solution process. This can compensate for the inherent limitations of any method based on scalar utility functions by allowing a certain intransitivity and incomparability of preferences, which are natural in multiple attribute situations.     

Robust optimization analysis for multiple attribute decision making problems with imprecise information

This paper considers ranking decision alternatives under multiple attributes with imprecise information on both attribute weights and alternative ratings. It is demonstrated that regret results from the decision maker??s inadequate knowledge about the true scenario to occur. Potential optimality analysis is a traditional method to evaluate alternatives with imprecise information. The essence of this approach is to identify any alternative that outperforms the others in its best-case scenario. Our analysis shows that potential optimality analysis is optimistic in nature and may lead to a significant loss if an unfavorable scenario occurs. We suggest a robust optimization analysis approach that ranks alternatives in terms of their worst-case absolute or relative regret. A robust optimal alternative performs reasonably well in all scenarios and is shown to be desirable for a risk-concerned decision maker. Linear programming models are developed to check robust optimality.     

Value reducts and bireducts: A comparative study

In Rough Set Theory, the notion of bireduct allows to simultaneously reduce the sets of objects and attributes contained in a dataset. In addition, value reducts are used to remove some unnecessary values of certain attributes for a specific object. Therefore, the combination of both notions provides a higher reduction of unnecessary data. This paper is focused on the study of bireducts and value reducts of information and decision tables. We present theoretical results capturing different aspects about the relationship between bireducts and reducts, offering new insights at a conceptual level. We also analyze the relationship between bireducts and value reducts. The studied connections among these notions provide important profits for the efficient information analysis, as well as for the detection of unnecessary or redundant information.     

A new multiple attribute group decision making method in intuitionistic fuzzy setting

The multiple attribute group decision making (MAGDM) problem with intuitionistic fuzzy information investigated in this paper is very useful for solving complicated decision problems under uncertain circumstances. Since experts have their own characteristics, they are familiar with some of the attributes, but not others, the weights of the decision makers to different attributes should be different. We derive the weights of the decision makers by aggregating the individual intuitionistic fuzzy decision matrices into a collective intuitionistic fuzzy decision matrix. The expert has a big weight if his evaluation value is close to the mean value and has a small weight if his evaluation value is far from the mean value. For the incomplete attribute weight information, we establish some optimization models to determine the attribute weights. Furthermore, we develop several algorithms for ranking alternatives under different situations, and then extend the developed models and algorithms to the MAGDM problem with interval-valued intuitionistic fuzzy information. Numerical results finally illustrate the practicality and efficiency of our new algorithms.     

An evidential reasoning based consensus model for multiple attribute group decision analysis problems with interval-valued group consensus requirements

With the aim of modeling multiple attribute group decision analysis problems with group consensus (GC) requirements, a GC based evidential reasoning approach and further an attribute weight based feedback model are sequentially developed based on an evidential reasoning (ER) approach. In real situations, however, giving precise (crisp) assessments for alternatives is often too restrictive and difficult for experts, due to incompleteness or lack of information. Experts may also find it difficult to give appropriate assessments on specific attributes, due to limitation or lack of knowledge, experience and provided data about the problem domain. In this paper, an ER based consensus model (ERCM) is proposed to deal with these situations, in which experts’ assessments are interval-valued rather than precise. Correspondingly, predefined interval-valued GC (IGC) requirements need to be reached after group analysis and discussion within specified times. Also, the process of reaching IGC is accelerated by a feedback mechanism including identification rules at three levels, consisting of the attribute, alternative and global levels, and a suggestion rule. Particularly, recommendations on assessments in the suggestion rule are constructed based on recommendations on their lower and upper bounds detected by the identification rule at a specific level. A preferentially developed industry selection problem is solved by the ERCM to demonstrate its detailed implementation process, validity, and applicability.     

An efficient rough feature selection algorithm with a multi-granulation view

Feature selection is a challenging problem in many areas such as pattern recognition, machine learning and data mining. Rough set theory, as a valid soft computing tool to analyze various types of data, has been widely applied to select helpful features (also called attribute reduction). In rough set theory, many feature selection algorithms have been developed in the literatures, however, they are very time-consuming when data sets are in a large scale. To overcome this limitation, we propose in this paper an efficient rough feature selection algorithm for large-scale data sets, which is stimulated from multi-granulation. A sub-table of a data set can be considered as a small granularity. Given a large-scale data set, the algorithm first selects different small granularities and then estimate on each small granularity the reduct of the original data set. Fusing all of the estimates on small granularities together, the algorithm can get an approximate reduct. Because of that the total time spent on computing reducts for sub-tables is much less than that for the original large-scale one, the algorithm yields in a much less amount of time a feature subset (the approximate reduct). According to several decision performance measures, experimental results show that the proposed algorithm is feasible and efficient for large-scale data sets.     

Rough sets based matrix approaches with dynamic attribute variation in set-valued information systems

Set-valued information systems are generalized models of single-valued information systems. The attribute set in the set-valued information system may evolve over time when new information arrives. Approximations of a concept by rough set theory need updating for knowledge discovery or other related tasks. Based on a matrix representation of rough set approximations, a basic vector H(X) is induced from the relation matrix. Four cut matrices of H(X), denoted by H^[μ,ν](X), H^(μ,ν](X), H^[μ,ν)(X) and H^(μ,ν)(X), are derived for the approximations, positive, boundary and negative regions intuitively. The variation of the relation matrix is discussed while the system varies over time. The incremental approaches for updating the relation matrix are proposed to update rough set approximations. The algorithms corresponding to the incremental approaches are presented. Extensive experiments on different data sets from UCI and user-defined data sets show that the proposed incremental approaches effectively reduce the computational time in comparison with the non-incremental approach.     

考虑可信度和属性优先级的犹豫模糊决策方法

研究了考虑可信度的犹豫模糊混合集成因子以及考虑属性优先级的犹豫模糊多属性决策方法。首先给出了用于衡量数据差异程度的加权变异率公式,并证明了其具有类似于基尼系数的优良度量性质,之后在此基础上提出了可信度诱导犹豫模糊混合平均(CIHFHA)算子。针对属性权重信息未知的犹豫模糊决策问题,构建了一种新的考虑属性优先级的熵值修正G1的组合赋权方法,该方法可有效地利用属性客观评价数据以及通过考虑属性优先级体现专家意见,解决了主客观权重分配问题,得出的属性权重更加客观、合理。之后给出了一种基于CIHFHA算子和组合赋权方法的多属性决策方法,算例说明该方法的有效性和实用性。