Combinatorial Machine Learning: A Rough Set Approach (Studies in Computational Intelligence, 360)

✍ Scribed by Mikhail Moshkov, Beata Zielosko

• Publisher: Springer
• Year: 2011
• Tongue: English
• Leaves: 186
• Category: Library

✦ Synopsis

Decision trees and decision rule systems are widely used in different applications

as algorithms for problem solving, as predictors, and as a way for

knowledge representation. Reducts play key role in the problem of attribute

(feature) selection. The aims of this book are (i) the consideration of the sets

of decision trees, rules and reducts; (ii) study of relationships among these

objects; (iii) design of algorithms for construction of trees, rules and reducts;

and (iv) obtaining bounds on their complexity. Applications for supervised

machine learning, discrete optimization, analysis of acyclic programs, fault

diagnosis, and pattern recognition are considered also. This is a mixture of

research monograph and lecture notes. It contains many unpublished results.

However, proofs are carefully selected to be understandable for students.

The results considered in this book can be useful for researchers in machine

learning, data mining and knowledge discovery, especially for those who are

working in rough set theory, test theory and logical analysis of data. The book

can be used in the creation of courses for graduate students.

✦ Table of Contents

Title Page
Preface
Contents
Introduction
Examples from Applications
Problems
Decision Tables
Examples
Three Cups and Small Ball
Diagnosis of One-Gate Circuit
Problem of Three Post-Offices
Recognition of Digits
Traveling Salesman Problem with Four Cities
Traveling Salesman Problem with n 4 Cities
Data Table with Experimental Data
Conclusions
Part I: Tools
Sets of Tests, Decision Rules and Trees
Decision Tables, Trees, Rules and Tests
Sets of Tests, Decision Rules and Trees
Monotone Boolean Functions
Set of Tests
Set of Decision Rules
Set of Decision Trees
Relationships among Decision Trees, Rules and Tests
Conclusions
Bounds on Complexity of Tests, Decision Rules and Trees
Lower Bounds
Upper Bounds
Conclusions
Algorithms for Construction of Tests, Decision Rules and Trees
Approximate Algorithms for Optimization of Tests and Decision Rules
Set Cover Problem
Tests: From Decision Table to Set Cover Problem
Decision Rules: From Decision Table to Set Cover Problem
From Set Cover Problem to Decision Table
Approximate Algorithm for Decision Tree Optimization
Exact Algorithms for Optimization of Trees, Rules and Tests
Optimization of Decision Trees
Optimization of Decision Rules
Optimization of Tests
Conclusions
Decision Tables with Many-Valued Decisions
Examples Connected with Applications
Main Notions
Relationships among Decision Trees, Rules and Tests
Lower Bounds
Upper Bounds
Approximate Algorithms for Optimization of Tests and Decision Rules
Optimization of Tests
Optimization of Decision Rules
Approximate Algorithms for Decision Tree Optimization
Exact Algorithms for Optimization of Trees, Rules and Tests
Example
Conclusions
Approximate Tests, Decision Trees and Rules
Main Notions
Relationships among -Trees, -Rules and -Tests
Lower Bounds
Upper Bounds
Approximate Algorithm for -Decision Rule Optimization
Approximate Algorithm for -Decision Tree Optimization
Algorithms for -Test Optimization
Exact Algorithms for Optimization of -Decision Trees and Rules
Conclusions
Part II Applications
Supervised Learning
Classifiers Based on Decision Trees
Classifiers Based on Decision Rules
Use of Greedy Algorithms
Use of Dynamic Programming Approach
From Test to Complete System of Decision Rules
From Decision Tree to Complete System of Decision Rules
Simplification of Rule System
System of Rules as Classifier
Pruning
Lazy Learning Algorithms
k-Nearest Neighbor Algorithm
Lazy Decision Trees and Rules
Lazy Learning Algorithm Based on Decision Rules
Lazy Learning Algorithm Based on Reducts
Conclusions
Local and Global Approaches to Study of Trees and Rules
Basic Notions
Local Approach to Study of Decision Trees and Rules
Local Shannon Functions for Arbitrary Information Systems
Restricted Binary Information Systems
Local Shannon Functions for Finite Information Systems
Global Approach to Study of Decision Trees and Rules
Infinite Information Systems
Global Shannon Function hUl for Two-Valued Finite Information Systems
Conclusions
Decision Trees and Rules over Quasilinear Information Systems
Bounds on Complexity of Decision Trees and Rules
Quasilinear Information Systems
Linear Information Systems
Optimization Problems over Quasilinear Information Systems
Some Definitions
Problems of Unconditional Optimization
Problems of Unconditional Optimization of Absolute Values
Problems of Conditional Optimization
On Depth of Acyclic Programs
Main Definitions
Relationships between Depth of Deterministic and Nondeterministic Acyclic Programs
Conclusions
Recognition of Words and Diagnosis of Faults
Regular Language Word Recognition
Problem of Recognition of Words
A-Sources
Types of Reduced A-Sources
Main Result
Examples
Diagnosis of Constant Faults in Circuits
Basic Notions
Complexity of Decision Trees for Diagnosis of Faults
Complexity of Construction of Decision Trees for Diagnosis
Diagnosis of Iteration-Free Circuits
Approach to Circuit Construction and Diagnosis
Conclusions
References
Index