Partial Covers, Reducts and Decision Rules in Rough Sets

by Moshkov, Mikhail Ju; Piliszczuk, Marcin; Zielosko, Beata

• ISBN13: 9783540690276
• ISBN10: 3540690271
• Format: Hardcover
• Copyright: 2009-03-06
• Publisher: Springer Verlag

Summary

This monograph is devoted to theoretical and experimental study of partial reducts and partial decision rules on the basis of the study of partial covers. The use of partial (approximate) reducts and decision rules instead of exact ones allows us to obtain more compact description of knowledge contained in decision tables, and to design more precise classifiers. Algorithms for construction of partial reducts and partial decision rules, bounds on minimal complexity of partial reducts and decision rules, and algorithms for construction of the set of all partial reducts and the set of all irreducible partial decision rules are considered. The book includes a discussion on the results of numerous experiments with randomly generated and real-life decision tables. These results show that partial reducts and decision rules can be used in data mining and knowledge discovery both for knowledge representation and for prediction.The results obtained in the monograph can be useful for researchers in such areas as machine learning, data mining and knowledge discovery, especially for those who are working in rough set theory, test theory and LAD (Logical Analysis of Data). The monograph can be used under the creation of courses for graduate students and for Ph.D. studies.

Table of Contents

Introduction	p. 1
Partial Covers, Reducts and Decision Rules	p. 7
Partial Covers	p. 8
Main Notions	p. 8
Known Results	p. 9
Polynomial Approximate Algorithms	p. 10
Bounds on Cmin (¿) Based on Information about Greedy Algorithm Work	p. 13
Upper Bound on Cgreedy(¿)	p. 17
Covers for the Most Part of Set Cover Problems	p. 18
Partial Tests and Reducts	p. 22
Main Notions	p. 22
Relationships between Partial Covers and Partial Tests	p. 23
Precision of Greedy Algorithm	p. 24
Polynomial Approximate Algorithms	p. 25
Bounds on Rmin (¿) Based on Information about Greedy Algorithm Work	p. 26
Upper Bound on Rgreedy (¿)	p. 28
Tests for the Most Part of Binary Decision Tables	p. 29
Partial Decision Rules	p. 35
Main Notions	p. 36
Relationships between Partial Covers and Partial Decision Rules	p. 37
Precision of Greedy Algorithm	p. 38
Polynomial Approximate Algorithms	p. 38
Bounds on Lmin (¿) Based on Information about Greedy Algorithm Work	p. 40
Upper Bound on Lgreedy (¿)	p. 43
Decision Rules for the Most Part of Binary Decision Tables	p. 43
Conclusions	p. 49
Partial Covers, Reducts and Decision Rules with Weights	p. 51
Partial Covers with Weights	p. 53
Main Notions	p. 53
Some Known Results	p. 54
Polynomial Approximate Algorithms	p. 55
Comparison of Usual Greedy Algorithm and Greedy Algorithm with Two Thresholds	p. 56
Two Modifications of Greedy Algorithm	p. 59
Lower Bound on Cmin (¿)	p. 61
Upper Bounds on C¿greedy(¿)	p. 64
Results of Experiments for ¿-Covers	p. 66
Partial Tests and Reducts with Weights	p. 70
Main Notions	p. 71
Relationships between Partial Covers and Partial Tests	p. 72
Precision of Greedy Algorithm with Equal Thresholds	p. 73
Polynomial Approximate Algorithms	p. 74
Two Modifications of Greedy Algorithm	p. 74
Bounds on Rmin (¿) and R¿greedy(¿)	p. 77
Results of Experiments for ¿-Tests and ¿-Reducts	p. 78
Partial Decision Rules with Weights	p. 83
Main Notions	p. 83
Relationships between Partial Covers and Partial Decision Rules	p. 84
Precision of Greedy Algorithm with Equal Thresholds	p. 86
Polynomial Approximate Algorithms	p. 86
Two Modifications of Greedy Algorithm	p. 87
Bounds on Lmin (¿) and L¿greedy (¿)	p. 89
Results of Experiments for ¿-Decision Rules	p. 91
Conclusions	p. 96
Construction of All Irreducible Partial Covers, All Partial Reducts and All Irreducible Partial Decision Rules	p. 97
Irreducible t-Covers	p. 98
Cardinality of Irreducible t-Covers	p. 98
Number of Irreducible t-Covers	p. 100
Algorithms for Construction of All Irreducible t-Covers	p. 101
Set TABD(m,n) of Decision Tables	p. 101
t-Reducts	p. 102
Cardinality of t-Reducts	p. 102
Number of t-Reducts	p. 105
Algorithms for Construction of All t-Reducts	p. 106
Results of Experiments	p. 107
Irreducible t-Decision Rules	p. 109
Length of Irreducible t-Decision Rules	p. 109
Number of Irreducible t-Decision Rules	p. 112
Algorithms for Construction of All Irreducible t-Decision Rules	p. 113
Results of Experiments	p. 114
Conclusions	p. 116
Experiments with Real-Life Decision Tables	p. 117
0.5-Hypothesis for Reducts	p. 118
0.5-Hypothesis for Decision Rules	p. 122
Classifiers Based on Partial Reducts	p. 126
Classifiers Based on Partial Decision Rules	p. 129
Conclusions	p. 133
Universal Attribute Reduction Problem	p. 135
From Data Table to Decision Table	p. 136
Problem of Attribute Reduction	p. 137
Definition of Problem	p. 137
Examples	p. 138
Maximally Discerning Reducts	p. 139
Greedy Algorithm	p. 139
Precision of Greedy Algorithm	p. 140
Polynomial Approximate Algorithms	p. 140
Lower Bound on Rmin (¿)	p. 141
Upper Bound on Rgreedy (¿)	p. 141
Conclusions	p. 142
Final Remarks	p. 143
References	p. 145
Index	p. 149
Table of Contents provided by Ingram. All Rights Reserved.