Relationships Between Length and Coverage of Exact Decision Rules

Abstract

The paper describes a new tool for study relationships between length and coverage of exact decision rules. This tool is based on dynamic programming approach. We also present results of experiments with decision tables from UCI Machine Learning Repository.

Keywords

• decision rules
• dynamic programming
• length
• coverage

Introduction

Decision rules are widely used in applications connected with data mining, knowledge discovery and machine learning.

There are many different approaches to the design and analysis of decision rules: brute-force approach, genetic algorithms [ 25 ], simulated annealing [ 12 ], Boolean reasoning [ 18, 20, 24 ], ant colony optimization [ 13 ], algorithms based on decision tree construction [ 14, 17, 21 ], algorithms based on a sequential covering procedure [ 5, 8, 9 ], different kinds of greedy algorithms [ 16, 18 ], and dynamic programming [ 2–4 ].We can find many programs which allow data analysis using decision rules based on the approaches mentioned above, e.g., LERS [ 10 ], RSES [ 7 ], Rosetta [ 19 ], Weka [ 11 ], TRS library [ 23 ], and others.

We propose a new tool for analyzing relationships between the length and coverage of decision rules. This tool is based on a dynamic programming approach and is part of the software system Dagger [ 1 ] created in King Abdullah University of Science and Technology.

We study the dependence between length and coverage of exact irredundant decision rules. Such rules are constructed using a dynamic programming algorithm [ 3 ]. The length of a rule is the number of descriptors (expressions “attribute=value”) on the left-hand side of the rule. The coverage of a rule, for a given decision table, is the number of rows in the table for which the rule is realizable (the left-hand side of the rule is true) and the decision from the righthand side of the rule is equal to the decision attached to the row. The choice of length as a rule parameter is connected with the Minimum Description Length principle [ 22 ]. The rule coverage is important for discovering major patterns in the data.

For a given decision table T , row r of T , and a natural number m, we would like to find the value FT,r(m) which is the maximum coverage of a decision rule that is true for T , realizable for r, and whose length is at most m.

We created an algorithm that allows us to find the value FT,r (m), for all m such that m is at least the minimum length of the considered rules and at most the number of attributes in T . This algorithm is based on ideas of dynamic programming and requires the construction of a graph which nodes are subtables of the decision table T . We also study the reverse relationship which is described by the function GT,r. The value of this function, for a given p, is equal to the minimum length among all irredundant decision rules for T and r which have a coverage of at least p. For experimentation, we used decision tables from UCI ML Repository [ 6 ].

The chapter consists of seven sections. Section 2 contains main notions and defines irredundant decision rules. In Sect. 3, we present an algorithm for constructing a directed acyclic graph whose nodes are subtables of a given decision table T . Section 4 is devoted to the consideration of an algorithm that constructs the function FT,r for a given decision table T and its row r. In Sect. 5, we describe how it is possible to find values of the function GT,r using values of the function FT,r . Section 6 contains the results of our experiments, and Sect. 7 – a short conclusion. 2

Main Notions

In this section, we present definitions of notions corresponding to decision tables and decision rules.

A decision table T is a rectangular table with n columns labeled with conditional attributes f1, . . . , fn. Rows of this table are filled with nonnegative integers which are interpreted as values of conditional attributes. Rows of T are pairwise different and each row is labeled with a nonnegative integer (decision) which is interpreted as a value of the decision attribute.

We denote by N (T ) the number of rows in the table T . The table T is called degenerate if T is empty (in this case N (T ) = 0) or all rows of T are labeled with the same decision.

A table obtained from T by the removal of some rows is called a subtable of the table T . Let T be nonempty and fi1 , . . . , fim ∈ {f1, . . . , fn} and a1, . . . , am be nonnegative integers. We denote by T (fi1 , a1) . . . (fim , am) the subtable of the table T which contains only rows that have numbers a1, . . . , am at the intersection with columns fi1 , . . . , fim . Such nonempty subtables (including the table T ) are called separable subtables of T .

We denote by E(T ) the set of attributes from {f1, . . . , fn} which are not constant on T . For any fi ∈ E(T ), we denote by E(T , fi) the set of values of the attribute fi in T . (1) (2) The expression

fi1 = a1 ∧ . . . ∧ fim = am → d is called a decision rule over T if fi1 , . . . , fim ∈ {f1, . . . , fn}, and a1, . . . am, d are nonnegative integers. It is possible that m = 0. In this case (1) is equal to the rule

→ d.

Let r = (b1, . . . , bn) be a row of T . We will say that the rule (1) is realizable for r if a1 = bi1 , . . . , am = bim . If m = 0 then the rule (2) is realizable for any row from T .

We will say that the rule (1) is true for T if each row of T for which the rule (1) is realizable has the decision d attached to it. Note that (1) is true for T if and only if the table T 0 = T (fi1 , a1) . . . (fim , am) is degenerate and each row of T 0 is labeled with the decision d. If m = 0 then the rule (2) is true for T if and only if T is degenerate and each row of T is labeled with the decision d.

If a rule is true for T and realizable for r, we will say that this is a decision rule for T and r. 2.1

Irredundant Decision Rules We will say that the rule (1) with m > 0 is an irredundant decision rule for T and r if (1) is a decision rule for T and r and the following conditions hold: (i) fi1 ∈ E(T ), and if m > 1 then fij ∈ E(T (fi1 , a1) . . . (fij−1 , aj−1)) for j = 2, . . . , m; (ii) if m = 1 then the table T is nondegenerate, and if m > 1 then the table T (fi1 , a1) . . . (fim−1 , am−1) is nondegenerate.

If m = 0 then the rule (2) is an irredundant decision rule for T and r if (2) is a decision rule for T and r, i.e., if T is degenerate and each row of T is labeled with the decision d.

Lemma 1. [ 3 ] Let T be a nondegenerate decision table, fi1 ∈ E(T ), a1 ∈ E(T , fi1 ), and r be a row of the table T 0 = T (fi1 , a1). Then the rule (1) with m ≥ 1 is an irredundant decision rule for T and r if and only if the rule fi2 = a2 ∧ . . . ∧ fim = am → d (3) is an irredundant decision rule for T 0 and r (if m = 1 then (3) is equal to → d).

Let τ be a decision rule over T and τ be equal to (1).

The number m of descriptors (pairs “attribute=value”) on the left-hand side of τ is called the length of the rule and is denoted by l(τ ). The length of decision rule (2) is equal to 0.

The coverage of τ is the number of rows in T for which τ is realizable and which are labeled with the decision d. We denote it by c(τ ). The coverage of decision rule (2) is equal to the number of rows in T which are labeled with the decision d. If τ is true for T (we consider now this case) then c(τ ) = N (T (fi1 , a1) . . . (fim , am)). Proposition 1. [ 3 ] Let T be a nonempty decision table, r be a row of T and τ be a decision rule for T and r which is not an irredundant decision rule for T and r. Then by removal of some descriptors from the left-hand side of τ we can obtain an irredundant decision rule irr(τ ) for T and r such that l(irr(τ )) ≤ l(τ ) and c(irr(τ )) ≥ c(τ ).

From Proposition 1 it follows that instead of arbitrary decision rules for T and r we can consider only irredundant decision rules for T and r.

We will say that an irredundant decision rule for T and r is totally optimal relative to the length and coverage if it has the minimum length and the maximum coverage among all irredundant decision rules for T and r. 3

Directed Acyclic Graph Δ(T ) Now, we consider an algorithm that constructs a directed acyclic graph Δ(T ). Based on this graph we can describe the set of irredundant decision rules for T and for each row r of T . We can also study relationships between the length and coverage of such rules. Nodes of the graph are separable subtables of the table T . During each step, the algorithm processes one node and marks it with the symbol *. At the first step, the algorithm constructs a graph containing a single node T which is not marked with *.

Let us assume that the algorithm has already performed p steps. We now describe the step (p+1). If all nodes are marked with the symbol * as processed, the algorithm finishes its work and presents the resulting graph as Δ(T ). Otherwise, choose a node (table) Θ, which has not been processed yet. If Θ is degenerate, then mark Θ with the symbol * and go to the step (p + 2). Otherwise, for each fi ∈ E(Θ), draw a bundle of edges from the node Θ. Let E(Θ, fi) = {b1, . . . , bt}. Then draw t edges from Θ and label these edges with pairs (fi, b1), . . . , (fi, bt) respectively. These edges enter to nodes Θ(fi, b1), . . . , Θ(fi, bt). If some of nodes Θ(fi, b1), . . . , Θ(fi, bt) are absent in the graph then add these nodes to the graph. Mark the node Θ with the symbol * and proceed to the step (p + 2).

The graph Δ(T ) is a directed acyclic graph. A node of this graph will be called terminal if there are no edges leaving this node. Note that a node Θ of Δ(T ) is terminal if and only if Θ is degenerate.

Now, for each node Θ of Δ(T ) and for each row r of Θ we describe a set of decision rules Rul(Θ, r). Let Θ be a terminal node of Δ(T ), i.e., Θ is a degenerate table in which each row is labeled with the same decision d. Then

Rul(Θ, r) = {→ d}.

Let Θ now be a nonterminal node of Δ(T ) such that for each child Θ0 of Θ and for each row r0 of Θ0 the set of rules Rul(Θ0, r0) has already been defined. Let r = (b1, . . . , bn) be a row of Θ labeled with a decision d. For any fi ∈ E(Θ), we define the set of rules Rul(Θ, r, fi) as follows:

Rul(Θ, r, fi) = {fi = bi ∧ α → d : α → d ∈ Rul(Θ(fi, bi), r)}.

Then

A detailed example for the construction of the directed acyclic graph and the description of the set of all irredundant decision rules for each row of a given decision table T can be found in [ 3 ].

It is possible to show (see analysis of similar algorithms in [ 17 ], page 64) that the time complexities of algorithms which construct the graph Δ(T ) and make optimization of decision rules relative to length or coverage are bounded above by polynomials on the number of separable subtables of T , and the number of attributes in T . In [ 15 ] it was shown that the number of separable subtables for decision tables with attributes from a restricted infinite information systems is bounded from above by a polynomial on the number of attributes in the table. Examples of restricted infinite information system were considered, in particular, in [ 17 ]. 4

Relationship Between Coverage and Length

Let T be a decision table with n columns labeled with attributes f1, . . . , fn, and r = (b1, . . . , bn) be a row of T . Let Θ be a node of the graph Δ(T ) containing the row r.

From Theorem 1 it follows that the set Rul(Θ, r) is equal to the set of all irredundant decision rules for Θ and r. We denote by lmin(Θ, r) the minimum length of a decision rule from Rul(Θ, r). We denote

BΘ,r = {lmin(Θ, r), lmin(Θ, r) + 1, . . . , n}.

Now we define a function FΘ,r : BΘ,r → N, where N is the set of natural numbers. For any m ∈ BΘ,r, we have

FΘ,r (m) = max{c(τ ) : τ ∈ Rul(Θ, r), l(τ ) ≤ m}.

This function describes the relationship between coverage and length of decision rules: FΘ,r(m) is equal to the maximum coverage among all irredundant decision rules for Θ and r whose length is at most m.

The function FΘ,r can be represented by the tuple (FΘ,r (t), FΘ,r(t+1), . . . , n), where t = lmin(Θ, r).

We now describe a procedure that allows us to find (describe) function FΘ,r for each node Θ of the graph Δ(T ) that contains the row r.

Let Θ be a degenerate table that contains the row r. All rows of Θ are labeled with the same decision d. We know that there is exactly one irredundant decision rule → d for Θ and r. Therefore, lmin(Θ, r) = 0 and FΘ,r (m) = N (Θ) for any m ∈ BΘ,r. Now, let Θ be a nondegenerate table (node) from Δ(T ) containing the row r. We know that and, for any m ∈ BΘ,r,

FΘ,r(m) = max{FΘ(fi,bi),r(m − 1) : fi ∈ E(Θ), m − 1 ≥ lmin(Θ(fi, bi), r)}. We use here the fact that the length of the rule fi = bi ∧ α → d is equal to the length of rule α → d plus 1, and the coverage of rule fi = bi ∧ α → d for the table Θ is equal to the coverage of rule α → d for the table Θ(fi, bi).

Let us consider an example with a decision table T0 on the top of Fig. 1. We study the relationship between coverage and length of irredundant decision rules for the row r2 of the table T0. For clarity, the example contains only a part of the directed acyclic graph Δ(T0) constructed for the decision table T0; we omitted separable subtables which do not contain the second row of T0. We attached to each subtable Θ of this graph a two-row table that describes the function FΘ,r2 : the first row contains values lmin(Θ, r2), . . . , 3, and the second row contains values FΘ,r2 (lmin(Θ, r2)), . . . , FΘ,r2 (3) respectively. The relationship between coverage and length of irredundant decision rules for the row r2 is described by the functions FΘ2,r2 , FΘ9,r2 , FΘ4,r2 , FΘ6,r2 and FT0,r2 (see corresponding tables in Fig. 1). 5

Relationships Between Length and Coverage

In this section, we study a reversed relationship, i.e., the dependency between length and coverage of irredundant decision rules.

Let T be a decision table with n columns labeled with attributes f1, . . . , fn and r = (b1, . . . , bn) be a row of T . We know (see Theorem 1) that Rul(T , r) is the set of all irredundant decision rules for T and r. We denote by cmax(T , r) the maximum coverage of a decision rule from Rul(T , r). We denote

CT,r = {0, 1, . . . , cmax(T , r)}.

We now define a function GT,r : CT,r → Z+, where Z+ is the set of nonnegative integers. For any p ∈ CT,r, we have

GT,r(p) = min{l(τ ) : τ ∈ Rul(T , r), c(τ ) ≥ p}.

The value GT,r(p) is equal to the minimum length among all irredundant decision rules for T and r for which the coverage is at least p. To find this value we can use values of the function FT,r . Let us show that

GT,r(p) = min{m : m ∈ {lmin(T , r), . . . , n}, FT,r(m) ≥ p}. (4)

We denote

m0 = min{m : m ∈ {lmin(T , r), . . . , n}, FT,r(m) ≥ p}.

It is clear that there exists a rule τ ∈ Rul(T , r) such that l(τ ) ≤ m0 and c(τ ) ≥ p, and there is no rule ρ ∈ Rul(T , r) such that l(ρ) < m0 and c(ρ) ≥ p. From here it follows that GT,r(p) = m0.

We should add that cmax(T , r) = FT,r(n). It is clear that FT,r is a nondecreasing function. So, to find the value of m0 we can use binary search which requires O(log n) comparisons. 6

Experimental Results

In this section, we present experimental results for decision tables from UCI Machine Learning Repository [ 6 ] and we show plots depicting relationships between length and coverage of irredundant decision rules.

On the left-hand side of Fig. 2 we can see the function Fcars,row488 (relationship between coverage and length), and on the right-hand side – the function Gcars,row488 (relationship between length and coverage). Both functions are constant, which means that for row 488 of decision table “cars” there exists a totally optimal rule relative to the length and coverage, i.e., rule with minimum (among

F cars, row488

G cars, row488 all irredundant rules) length equal to 1 and maximum (among all irredundant rules) coverage equal to 576.

Functions presented in Fig. 3, Fbreast−cancer,row57 and Gbreast−cancer,row57 are increasing, which means that for row 57 of decision table “breast-cancer” there are no totally optimal rules relative to the length and coverage.

Table 1 presents, for a given decision table T , the number of rows r such that there exists a totally optimal irredundant decision rule for T and r.

We denote by Row(T ) the set of rows from T . We have |Row(T )| = N (T ). Let S be a system of irredundant decision rules for T where, for each row r ∈ Row(T ), we have a decision rule rule which is realizable for r and true for T . The number of rules is equal to the number of rows in T . By P (T ) we denote the set of such systems.

By lmax(S) we denote the maximum length of rules from S. By cavg(S) we denote the average coverage of rules from S, cavg(S) =

Prule∈S c(rule) .

|Row(T )|

The value of FTavg can be calculated in the following way

FTavg(m) =

Pr∈Row(T ) FT,r(m) |Row(T )| .

So, FTavg(m) is equal to the maximum value of the average coverage of rules among all systems S ∈ P (T ), where the length of each rule is at most m.

By cmin(S) we denote the minimum coverage of rules from S. By lavg(S) we denote the average length of rules from S, lavg(S) =

Prule∈S l(rule) |Row(T )| .

Let CT = {0, 1, . . . , cmax(T )}, where

Our aim is to find for each p ∈ CT the value

cmax(T ) = min{cmax(T , r) : r ∈ Row(T )}.

Gavg(p) = min{lavg(S) : S ∈ P (T ), cmin(S) ≥ p}.

T avg can be calculated in the following way The value of GT

Gavg(p) =

T

Pr∈Row(T ) GT,r(p) . avg F cars avg G cars So, GaTvg(p) is equal to the minimum value of the average length of rules among systems S ∈ P (T ), where the coverage of each rule is at least p.

Functions F avg and Gavg for the decision table “cars” are presented in Fig. 4,

T T and for the decision table “breast-cancer” – in Fig. 5.

The study of relationships between length and coverage of irredundant decision rules can be considered as a tool that supports designing of classifiers. To predict the value of a decision attribute for a new object, we can have a classifier use only totally optimal rules, rules with the maximum coverage, or with the minimum length. We can study the accuracy of classifiers, and based on a tool for relationships, we can try to find associations between length and coverage of rules which give the best result of classification. Besides, short rules which cover many objects can be useful in knowledge representation. In this case, rules with smaller number of descriptors are more understandable.

Conclusions

In this paper, we considered relationships between length and coverage of irredundant decision rules. Such a study can be useful from the point of view of knowledge representation. It can also give useful information for the construction of rule based classifiers.

References

1. Alkhalid , A. , Amin , T. , Chikalov , I. , Hussain , S. , Moshkov , M. , Zielosko , B. : Dagger: A tool for analysis and optimization of decision trees and rules . In: Computational Informatics, Social Factors and New Information Technologies: Hypermedia Perspectives and Avant-Garde Experiences in the Era of Communicability Expansion . Blue Herons ( 2011 ) 29 - 39

2. Amin , T. , Chikalov , I. , Moshkov , M. , Zielosko , B. : Dynamic programming algorithm for optimization of β-decision rules . In Szczuka, M. , Czaja , L. , Skowron , A. , Kacprzak , M., eds.: 20th International Workshop Concurrency, Specification and Programming CS & P 2011 , September 28-30, Pultusk, Poland, Bialystok University of Technology ( 2011 ) 10 - 16

3. Amin , T. , Chikalov , I. , Moshkov , M. , Zielosko , B. : Dynamic programming approach for exact decision rule optimization . In Skowron, A. , Suraj , Z ., eds.: Rough Sets and Intelligent Systems. Professor Zdzislaw Pawlak in Memoriam . Springer ( 2012 ) to appear.

4. Amin , T. , Chikalov , I. , Moshkov , M. , Zielosko , B. : Dynamic programming approach for partial decision rule optimization . Fundam. Inform . ( 2012 ) to appear.

5. An , A. , Cercone , N.: ELEM2: a learning system for more accurate classifications . In: Proceedings of the 12th Biennial Conference of the Canadian Society for Computational Studies of Intelligence on Advances in Artificial Intelligence , London, UK, Springer-Verlag ( 1998 ) 426 - 441

6. Asuncion , A. , Newman , D.J.: UCI Machine Learning Repository (http://www . ics.uci.edu/~mlearn/, 2007 )

7. Bazan , J.G. , Szczuka , M.S. , Wojna , A. , Wojnarski , M. : On the evolution of rough set exploration system . In Tsumoto, S., Slowinski , R. , Komorowski , H.J. , Grzymala-Busse , J.W., eds. : RSCTC 2004. Volume 3066 of LNCS . Springer ( 2004 ) 592 - 601

8. Blaszczyn´ski, J., Slowin´ski, R., Szela¸g, M.: Sequential covering rule induction algorithm for variable consistency rough set approaches . Inf. Sci . 181 ( 5 ) ( 2011 ) 987 - 1002

9. Clark , P. , Niblett , T. : The CN2 induction algorithm . Mach. Learn . 3 ( 4 ) ( 1989 ) 261 - 283

10. Grzymala-Busse , J.W.: LERS - a system for learning from examples based on rough sets . In Slowin´ski, R., ed.: Intelligent Decision Support. Handbook of Applications and Advances of the Rough Sets Theory . Kluwer Academic Publishers ( 1992 ) 3 - 18

11. Hall , M. , Frank , E. , Holmes , G. , Pfahringer , B. , Reutemann , P. , Witten , I.H. : The WEKA data mining software: an update . SIGKDD Explorations 11 ( 1 ) ( 2009 ) 10 - 18

12. Jensen , R. , Shen , Q. : Semantics-preserving dimensionality reduction: rough and fuzzy-rough-based approaches . IEEE Trans. Knowl. Data Eng . 16 ( 12 ) ( 2004 ) 1457 - 1471

13. Liu , B. , Abbass , H.A. , McKay , B. : Classification rule discovery with ant colony optimization . In: IAT 2003 . IEEE Computer Society ( 2003 ) 83 - 88

14. Michalski, S., Pietrzykowski , J.: iAQ: A program that discovers rules . AAAI-07 AI Video Competition (http://videolectures .net/aaai07_michalski_iaq/, 2007 )

15. Moshkov , M. , Chikalov , I. : On algorithm for constructing of decision trees with minimal depth . Fundam. Inform . 41 ( 3 ) ( 2000 ) 295 - 299

16. Moshkov , M. , Piliszczuk , M. , Zielosko , B. : Partial Covers, Reducts and Decision Rules in Rough Sets - Theory and Applications . Volume 145 of Studies in Computational Intelligence. Springer, Heidelberg ( 2008 )

17. Moshkov , M. , Zielosko , B.: Combinatorial Machine Learning - A Rough Set Approach . Volume 360 of Studies in Computational Intelligence. Springer, Heidelberg ( 2011 )

18. Nguyen , H.S.: Approximate boolean reasoning: foundations and applications in data mining . In Peters, J.F. , Skowron , A., eds.: T. Rough Sets. Volume 4100 of LNCS . Springer ( 2006 ) 334 - 506

19. Øhrn , A. , Komorowski , J. , Skowron , A. , Synak , P. : The design and implementation of a knowledge discovery toolkit based on rough sets: The ROSETTA system . In: Rough Sets in Knowledge Discovery 1: Methodology and Applications . Volume 18 of Studies in Fuzziness and Soft Computing . Physica-Verlag ( 1998 ) 376 - 399

20. Pawlak , Z. , Skowron , A. : Rough sets and boolean reasoning . Inf. Sci . 177 ( 1 ) ( 2007 ) 41 - 73

21. Quinlan , J.R. : C4 . 5: Programs for Machine Learning . Morgan Kaufmann Publishers Inc. ( 1993 )

22. Rissanen , J.: Modeling by shortest data description . Automatica 14 ( 5 ) ( 1978 ) 465 - 471

23. Sikora , M. : Decision rule-based data models using TRS and NetTRS - methods and algorithms . T. Rough Sets 11 ( 2010 ) 130 - 160

24. Skowron , A. , Rauszer , C. : The discernibility matrices and functions in information systems . In Slowinski, R., ed.: Intelligent Decision Support. Handbook of Applications and Advances of the Rough Set Theory . Kluwer Academic Publishers, Dordrecht ( 1992 ) 331 - 362

25. S´l¸ezak, D. , Wr´oblewski, J.: Order based genetic algorithms for the search of approximate entropy reducts . In Wang, G., Liu , Q. , Yao , Y. , Skowron , A., eds.: RSFDGrC 2003. Volume 2639 of LNCS . Springer ( 2003 ) 308 - 311