Dynamic Programming Approach for Optimization of Decision Rules

Speaker(s)

Beata Zielosko

Affiliation

Uniwersytet Warszawski

Date

Sept. 26, 2011, 2:15 p.m.

Room

room 5820

Seminar

Seminarium badawcze Zakładu Logiki: Wnioskowania aproksymacyjne w eksploracji danych

---

We are interested in the construction of short rules which cover many objects. In particular, the choice of short rules is connected with the Minimum Description Length principle. The rule coverage is important to discover major patterns in the data. Unfortunately, the problems of minimization of length and maximization of coverage of decision rules are NP-hard. We present an approach for decision rules optimization based on extensions of dynamic programming.  This approach allows us to describe the whole set of irredundant decision rules and optimize these rules sequentially relative to the length and coverage or relative to the coverage and length. We consider also results of experiments with decision tables from UCI Machine Learning Repository.We prove that by removal of some conditions from the left-hand side of each decision rule which is not irredundant, we can obtain an irredundant decision rule which length is at most the length of initial rule and coverage is at least the coverage of initial rule. It means that we work not only with optimal rules among irredundant decision rules but with optimal among all decision rules.

---