New Reduction Algorithm Based on Decision Power of Decision Table
The current reduction algorithms based on rough sets still have some disadvantages. First, we indicated their limitations for reduct generation. We modified the mean decision power, and proposed to use the algebraic definition of decision power. To select
- PDF / 338,980 Bytes
- 9 Pages / 430 x 660 pts Page_size
- 24 Downloads / 192 Views
Abstract. The current reduction algorithms based on rough sets still have some disadvantages. First, we indicated their limitations for reduct generation. We modified the mean decision power, and proposed to use the algebraic definition of decision power. To select optimal attribute reduction, the judgment criterion of decision with inequality was presented and some important conclusions were obtained. A complete algorithm for the attribute reduction was designed. Finally, through analyzing the given example, it was shown that the proposed heuristic information was better and more efficient than the others, and the presented in the paper method reduces time complexity and improves the performance. We report experimental results with several data sets from UCI repository and we compare the results with some other methods. The results prove that the proposed method is promising. Keywords: Rough set, Decision table, Reduction, Decision power.
1
Introduction
Rough set theory is a valid mathematical tool that deals with imprecise, uncertain, vague or incomplete knowledge of a decision system (see [1]). Reduction of knowledge is always one of the most important topics. Pawlak (see [1]) first proposed attribute reduction from the algebraic point of view. Wang (see [2, 3]) proposed some reduction theories based on the information point of view, and introduced two novel heuristic algorithms of knowledge reduction with the time complexity O(|C||U |2 ) + O(|U |3 ) and O(|C|2 |U |) + O(|C||U |3 ) respectively, where |C| denotes the number of conditional attributes and |U | is the number of objects in U , and the heuristic algorithm based on the mutual information (see [4]) with the time complexity O(|C||U |2 ) + O(|U |3 ). These presented reduction algorithms have still their own limitations, such as sensitivity to noises, relatively high complexities, nonequivalence in the representation of knowledge reduction and some drawbacks in dealing with inconsistent decision tables. It is known that reliability and coverage of a decision rule are all the most important standards for estimating the decision quality (see [5, 6]), but these algorithms (see [1, 2, 3, 7, 8, 9]) can’t reflect the change of decision quality objectively. To compensate for their limitations, we construct a new method for G. Wang et al. (Eds.): RSKT 2008, LNAI 5009, pp. 180–188, 2008. c Springer-Verlag Berlin Heidelberg 2008
New Reduction Algorithm Based on Decision Power of Decision Table
181
separating consistent objects from inconsistent objects, and the corresponding judgment criterion with an inequality used in searching for the minimal or optimal reducts. Then we design a new heuristic reduction algorithm with relatively lower time complexity. For the large decision tables, since usually |U | |C|, the reduction algorithm is more efficient than the algorithms discussed above. Finally, six data sets from UCI repository are used to illustrate the performance of the proposed algorithm and a comparison with the existing methods is reported.
2
Rough Set Th
Data Loading...
