Inhibitory Rules in Data Analysis

by Delimata, Pawel; Moshkov, Mikhail Ju; Skowron, Andrzej; Suraj, Zbigniew

• ISBN13: 9783540856375
• ISBN10: 3540856374
• Format: Hardcover
• Copyright: 2008-11-01
• Publisher: Springer Verlag

Summary

"This monograph is devoted to theoretical and experimental study of inhibitory decision and association rules. Inhibitory rules contain on the right-hand side a relation of the kind "attribut does not equal value." The use of inhibitory rules instead of deterministic (standard) ones allows us to describe more completely information encoded in decision or information systems and to design classifiers of high quality." "The most important feature of this monograph is that it includes an advanced mathematical analysis of problems on inhibitory rules. We consider algorithms for construction of inhibitory rules, bounds on minimal complexity of inhibitory rules, and algorithms for construction of the set of all minimal inhibitory rules. We also discuss results of experiments with standard and lazy classifiers based on inhibitory rules. These results show that inhibitory decision and association rules can be used in data mining and knowledge discovery both for knowledge representation and for prediction. Inhibitory rules can also be used under the analysis and design of concurrent systems." "These 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 logical analysis of data (LAD. The monograph can be used under the creation of courses for graduate students and for Ph.D. studies."--BOOK JACKET.

Table of Contents

Introduction	p. 1
Maximal Consistent Extensions of Information Systems	p. 9
Main Notions	p. 11
True Realizable Inhibitory Rules	p. 11
Separating Sets of Attributes	p. 12
Description of the Set U	p. 13
True Inhibitory Rules	p. 18
True Deterministic Rules	p. 18
Information Systems with Binary Attribute	p. 18
Structure of Ext[superscript 3](S)	p. 20
Checking Membership to Ext[superscript 3](S) and Construction of Ext[superscript 3](S)	p. 21
Description of Ext[superscript 3](S)	p. 21
True Realizable Deterministic Rules	p. 24
Information Systems with at Most One Non-binary Attribute	p. 24
Structure of Ext[superscript 4](S)	p. 26
Algorithmic Problems Related to Ext[superscript 4](S)	p. 27
Conclusions	p. 29
Minimal Inhibitory Association Rules for Almost All k-Valued Information Systems	p. 31
Main Notions	p. 32
Relationships between Rules and Inconsistent Equation Systems	p. 33
Cardinality of Irreducible Inconsistent Equation Systems	p. 34
Number of Irreducible Inconsistent Equation Systems	p. 37
Construction of All Irreducible Inconsistent Equation Systems	p. 38
Minimal Inhibitory Rules	p. 39
Length of Minimal Inhibitory Rules	p. 39
Number of Minimal Inhibitory Rules	p. 40
Construction of All Minimal Inhibitory Rules	p. 40
Conclusions	p. 41
Partial Covers and Inhibitory Decision Rules	p. 43
Partial Covers	p. 43
Main Notions	p. 44
Some Known Results	p. 44
Polynomial Approximate Algorithms	p. 46
Bounds on C[subscript min]([alpha]) Based on Information About Greedy Algorithm Work	p. 46
Upper Bound on C[subscript greedy]([alpha])	p. 48
Covers for the Most Part of Set Cover Problems	p. 49
Partial Inhibitory Decision Rules	p. 50
Main Notions	p. 51
Relationships between Partial Covers and Partial Inhibitory Decision Rules	p. 51
Precision of Greedy Algorithm	p. 53
Polynomial Approximate Algorithms	p. 54
Bounds on L[subscript min]([alpha]) Based on Information About Greedy Algorithm Work	p. 56
Upper Bound on L[subscript greedy]([alpha])	p. 59
Inhibitory Decision Rules for the Most Part of Binary Decision Tables	p. 59
Conclusions	p. 62
Partial Covers and Inhibitory Decision Rules with Weights	p. 63
Partial Covers with Weights	p. 64
Main Notions	p. 64
Some Known Results	p. 65
Polynomial Approximate Algorithms	p. 66
Comparison of Standard Greedy Algorithm and Greedy Algorithm with Two Thresholds	p. 67
Two Modifications of Greedy Algorithm	p. 68
Lower Bound on C[subscript min]([alpha])	p. 69
Upper Bounds on C[superscript gamma subscript greedy]([alpha])	p. 70
Partial Inhibitory Decision Rules with Weights	p. 71
Main Notions	p. 71
Relationships between Partial Covers and Partial Inhibitory Decision Rules	p. 73
Precision of Greedy Algorithm with Equal Thresholds	p. 75
Polynomial Approximate Algorithms	p. 75
Two Modifications of Greedy Algorithm	p. 76
Bounds on L[subscript min]([alpha]) and L[superscript gamma subscript greedy]([alpha])	p. 77
Conclusions	p. 79
Classifiers Based on Deterministic and Inhibitory Decision Rules	p. 81
Decision Tables	p. 81
Classifiers Based on Deterministic Decision Rules	p. 82
Classifiers Based on Inhibitory Decision Rules	p. 83
Results of Experiments	p. 84
Conclusions	p. 86
Lazy Classification Algorithms Based on Deterministic and Inhibitory Association Rules	p. 87
Characteristic Tables	p. 88
Information Systems	p. 88
Deterministic Characteristic Tables	p. 88
Inhibitory Characteristic Tables	p. 90
Evaluation Functions	p. 91
Algorithms of Classification	p. 91
Results of Experiments	p. 93
Conclusions	p. 96
Lazy Classification Algorithms Based on Deterministic and Inhibitory Decision Rules	p. 99
Decision Tables	p. 100
Deterministic Decision Rules	p. 100
Inhibitory Decision Rules	p. 101
Algorithms of Classification	p. 102
Results of Experiments	p. 104
Conclusions	p. 105
Final Remarks	p. 107
References	p. 109
Index	p. 115
Table of Contents provided by Ingram. All Rights Reserved.