تخمین گفتگو و استخراج قانون از جداول تصمیم گیری در نظریه مجموعه راف
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی|
|29501||2008||12 صفحه PDF||21 صفحه WORD|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Computers & Mathematics with Applications, Volume 55, Issue 8, April 2008, Pages 1754–1765
استخراج قانون مبتنی بر تخمین گفتگو
جدول 1. جدول تصمیم گیری متناقض
جدول 2. قوانین تصمیم گیری استخراج شده از جدول تصمیم گیری S1
جدول 3. جدول تصمیم گیری متناقض
جدول 4. قوانین تصمیم گیری استخراج شده از جدول تصمیم گیری S2
In this paper, the concept of a granulation order is proposed in an information system. The converse approximation of a target concept under a granulation order is defined and some of its important properties are obtained, which can be used to characterize the structure of a set approximation. For a subset of the universe in an information system, its converge degree is monotonously increasing under a granulation order. This means that a proper family of granulations can be chosen for a target concept approximation according to user requirements. As an application of the converse approximation, an algorithm based on the converse approximation called REBCA is designed for decision-rule extraction from a decision table, which has a time complexity of View the MathML sourceO(m2|C|2|U|log2|U|), and its practical applications are illustrated by two examples.
Recently, rough set theory developed by Pawlak in  has become a popular mathematical framework for the analysis of vague descriptions of objects. The focus of rough set theory is on the ambiguity caused by limited discernibility of objects in the domain of discourse. Its key concepts are those of object indiscernibility and set approximation, and its main perspectives are information view and algebra view . The primary use of rough set theory has so far mainly been in generating logical rules for classification and prediction using information granules; thereby making it a prospective tool for pattern recognition, image processing, feature selection, data mining and knowledge discovery process from large data sets ,  and . As a recently renewed research topic, granular computing (GrC) is an umbrella term to cover any theories, methodologies, techniques, and tools that make use of granules in problem solving ,  and . Basic ideas of GrC have appeared in related fields, such as interval analysis, rough set theory, cluster analysis, machine learning, databases, and many other. As follows, for our further development, we briefly review research on GrC. L.A. Zadeh identified three basic concepts that underlie the process of human cognition, namely, granulation, organization, and causation. “Granulation involves decomposition of whole into parts, organization involves integration of parts into whole, and causation involves association of causes and effects”. A general framework of granular computing was presented by Zadeh  in the context of fuzzy set theory. Some authors ,  and  examined granular computing in connection with the theory of rough sets. Yao  suggested the use of hierarchical granulations for the study of stratified rough set approximations. Lin  and Yao  studied granular computing using neighborhood systems. Klir  investigated some basic issues of computing with granular computing with granular probabilities. The theory of quotient space had been extended into the theory of fuzzy quotient space based on fuzzy equivalence relation . Liang and Shi  established the relationship among knowledge granulation, information entropy, granularity measure and rough entropy in rough set theory. Liang and Qian  and  studied rough sets approximation based on dynamic granulation (positive approximation) and its application for rule extracting. In the view of granular computing, a general concept described by a set is always characterized via the so-called upper and lower approximations under static granulation in rough set theory, and a static boundary region of the concept is induced by the upper and lower approximations. However, in rough sets approximation under dynamic granulation, a general concept described by using the positive approximation is characterized via variational upper and lower approximations under dynamic granulation, which is an aspect of people’s comprehensive solving ability at some different granulations. In recent years, rough set theory has been widely applied to extracted from decision tables. Decision tables have two cases: consistent decision tables and inconsistent decision tables. Ziarko  proposed a method of rule extracting from decision tables by reducing boundary area in decision tables. There are at least three approaches to reducing boundary area. The first and simplest technique is to try to increase the decision table “resolution” by adding more attributes or by increasing the precision of existing ones. The second approach is to provide another layer of decision tables, by treating each subdomain of objects matching the description of an elementary set of the boundary area of the original decision tables as a domain (the universe) by itself. The third proposed method of boundary area reduction is based on the idea of treating the subdomain of the original domain corresponding to the whole boundary area as the new domain by itself. However, in fact, the classification accuracy (the approximation measure)  is constrained according to decision requirements or preference of decision makers in general. An obvious question is how to extract much simpler decision rules on the basis of keeping an approximation measure. Liang and Qian  and  presented the notion of positive approximation and applied it for rule extracting from consistent decision tables in rough set theory. In , a given relative knowledge reduction determines a family of decision rules for a decision table. That is to say, relative knowledge reduction must be obtained before rule extracting from decision tables. Many types of knowledge reductions have been proposed , , , , , , , , , ,  and  in the area of rough set and each of the reductions aimed at some basic requirement. However, the complexity of these attribute reductions are much worse, which is inconvenient to extract decision rules from decision tables. Our research aims to find a method for rule extracting without computing relative attribute reduction of a decision table in rough set theory. Based on these studies, the main objectives of this paper are to establish the structure of the approximation of a target concept by introducing a notion of a granulation order, investigate some of its important properties, and apply it to rule extracting from decision tables. The rest of this paper is organized as follows. In Section 2, we review some basic concepts and properties of the positive approximation. The definitions of converse approximations of a target concept and a target decision (target partition) based on dynamic granulation are presented respectively, and some of their very useful properties are educed in Section 3. In Section 4, a new rule-extracting method of decision tables based on converse approximation in rough set theory is proposed and time complexity of this algorithm is analysed. And we show how the algorithm to extract decision rules by two illustrative examples (a consistent decision table and an inconsistent decision table). Finally, Section 5 concludes the whole paper.
نتیجه گیری انگلیسی
In this paper we have extended rough set approximation under static granulation to rough set approximation under dynamic granulation, which is called the converse approximation of a target concept. The concept of converse approximation is mainly based on a granulation order from fine to coarse. For a subset of the universe, its converge degree is monotonously increasing as a granulation order becomes longer. This means that a target concept or a target classification can be approximated by the change in the converse approximation induced by a granulation order. As an application of the converse approximation, an algorithm called REBCA has been proposed for extracting decision rules from a decision table. Two illustrative examples (a consistent decision table and an inconsistent decision table) have been employed to show the validity of this algorithm. Moreover, the time complexity of algorithm REBCA is much smaller than those of existing rule-extracting approaches based on attribute reduct. These results will be helpful in efficiently extracting decision rules from practical large-scale data sets.