Dynamic Programming Approach for Construction of Association Rule Systems

Abstract

In the paper, an application of dynamic programming approach for optimization of association rules from the point of view of knowledge representation is considered. Experimental results present cardinality of the set of association rules constructed for information system and lower bound on minimum possible cardinality of rule set based on the information obtained during algorithm work.

Keywords

• association rules
• decision rules
• dynamic programming
• set cover problem
• rough sets

1 Introduction

Association rules are popular form of knowledge representation. They are used in various areas such as business field for decision making and effective marketing, sequencepattern in bioinformatics, medical diagnosis, etc. One of the most popular application of association rules is market basket analysis that finds associations between different items that customers place in their shopping baskets.

There are many approaches for mining association rules. The most popular, is Apriori algorithm based on frequent itemsets [ 1 ]. During years, many new algorithms were designed which are based on, e.g., transaction reduction [ 2 ], sampling the data [ 13 ], and others [ 7, 9 ].

The most popular measures for association rules are support and confidence, however in the literature many other measures have been proposed [ 8, 9 ]. In this paper, we are interested in the construction of rules which cover many objects. Maximization of the coverage allows us to discover major patterns in the data, and it is important from the point of view of knowledge representation. Unfortunately, the problem of construction of rules with maximum coverage is N P -hard [ 6 ]. The most part of approaches, with the exception of brute-force and Apriori algorithm, cannot guarantee the construction of rules with the maximum coverage. The proposed dynamic programming approach allows one to construct such rules.

Application of rough sets theory to the construction of rules for knowledge representation or classification tasks are usually connected with the usage of decision table [ 12 ] as a form of input data representation. In such a table, one attribute is distinguished as a decision attribute and it relates to a rule consequence. However, in the last years, associative mechanism of rule construction, where all attributes can occur as premises or consequences of particular rules, is popular. Association rules can be defined in many ways. In the paper, a special kind of association rules is studied, i.e., they relate to decision rules. Similar approach was considered in [ 10, 11 ], where a greedy algorithm for minimization of length of association rules was studied. In [ 15 ], a dynamic programming approach to optimization of association rules relative to coverage was investigated.

When association rules for information systems are studied and each attribute is sequentially considered as the decision one, inconsistent tables are often obtained, i.e., tables containing equal rows with different decisions. In the paper, two possibilities of removing inconsistency of decision tables are considered. If in some tables there are equal rows with, possibly, different decisions, then (i) each group of identical rows is replaced with a single row from the group with the most common decision for this group, (ii) each group of identical rows is replaced with a single row from the group with the set of decisions attached to rows from the considered group. In the first case, usual decision tables are obtained (decision tables with single-valued decisions) and, for a given row, we should find decision attached to this row. In the second case, decision tables with many-valued decisions are obtained and, for a given row, we should find an arbitrary decision from the set of decisions attached to this row.

For each decision table obtained from the information system, we construct a system of exact rules in the following way: during each step, we choose a rule which covers the maximum number of previously uncovered rows. We stop the construction when all rows of the table are covered. If the obtained system of rules is short enough, then it can be considered as an intelligible representation of the knowledge extracted from the decision table. Otherwise, we can consider approximate rules, and stop the construction of the rule system when the most part of the rows (for example 90% of the rows) are covered.

In [ 4 ], the presented algorithm was proposed as application for multi-stage optimization of decision rules for decision tables. We extend it to association rules. The presented algorithm can be considered as a simulation of a greedy algorithm for construction of partial covers. So we can use lower bound on the minimum cardinality for partial cover based on the information about greedy algorithm work which was obtained in [ 10 ].

The paper consists of five sections. Section 2 contains main notions. In Sect. 3, algorithm for construction of system of association rule systems is presented. Section 4 contains experimental results for decision tables from UCI Machine Learning Repository, and Section 5 – short conclusions.

Main Notions

An information system I is a rectangular table with n+1 columns labeled with attributes f1, . . . , fn+1. Rows of this table are filled by nonnegative integers which are interpreted as values of attributes.

An association rule for I is a rule of the kind

(fi1 = a1) ∧ . . . ∧ (fim = am) → fj = a, where fj ∈ {f1, . . . , fn+1}, fi1 , . . . , fim ∈ {f1, . . . , fn+1} \ {fj }, and a,a1,. . . ,am are nonnegative integers.

The notion of an association rule for I is based on the notions of a decision table and decision rule. We consider two kinds of decision tables: with many-valued decisions and with single-valued decisions.

A decision table with many-valued decisions T is a rectangular table with n columns labeled with (conditional) attributes f1, . . . ,fn. Rows of this table are pairwise different and are filled by nonnegative integers which are interpreted as values of conditional attributes. Each row r is labeled with a finite nonempty set D(r) of nonnegative integers which are interpreted as decisions (values of a decision attribute). For a given row r of T , it is necessary to find a decision from the set D(r).

A decision table with single-valued decisions T is a rectangular table with n columns labeled with (conditional) attributes f1, . . . ,fn. Rows of this table are pairwise different and are filled by nonnegative integers which are interpreted as values of conditional attributes. Each row r is labeled with a nonnegative integer d(r) which is interpreted as a decision (value of a decision attribute). For a given row r of T , it is necessary to find the decision d(r). Decision tables with single-valued decisions can be considered as a special kind of decision tables with many-valued decisions in which D(r) = {d(r)} for each row r.

For each attribute fi ∈ {f1, . . . , fn+1}, the information system I is transformed into a table Ifi . The column fi is removed from I and a table with n columns labeled with attributes f1, . . . , fi−1, fi+1, . . . , fn+1 is obtained. Values of the attribute fi are attached to the rows of the obtained table Ifi as decisions.

The table Ifi can contain equal rows. We transform this table into two decision tables – with many-valued and single-valued decisions. A decision table Im−v with fi many-valued decisions is obtained from the table Ifi by replacing each group of equal rows with a single row from the group with the set of decisions attached to all rows from the group. A decision table Is−v with single-valued decisions is obtained from fi the table Ifi by replacing each group of equal rows with a single row from the group with the most common decision for this group.

The set {Ifm1−v, . . . , Ifmn−+1v} of decision tables with many-valued decisions obtained from the information system I is denoted by Φm−v(I). We denote by Φs−v(I) the set {Ifs1−v, . . . , Ifsn−+v1 } of decision tables with single-valued decisions obtained from the information system I. Since decision tables with single-valued decisions are a special case of decision tables with many-valued decisions, we consider the notion of decision rule for tables with many-valued decisions.

Let T ∈ Φm−v(I). For simplicity, let T = Ifmn−+1v. The attribute fn+1 will be considered as a decision attribute of the table T . We denote by Row(T ) the set of rows of T . Let D(T ) = Sr∈Row(T ) D(r).

A decision table is called empty if it has no rows. The table T is called degenerate if it is empty or has a common decision, i.e., Tr∈Row(T ) D(r) 6= ∅. We denote by N (T ) the number of rows in the table T and, for any t ∈ ω, we denote by Nt(T ) the number of rows r of T such that t ∈ D(r). By mcd(T ) we denote the most common decision for T which is the minimum decision t0 from D(T ) such that Nt0 (T ) = max{Nt(T ) : t ∈ D(T )}. If T is empty then mcd(T ) = 0.

For any conditional attribute fi ∈ {f1, . . . , fn}, we denote by E(T, fi) the set of values of the attribute fi in the table T . We denote by E(T ) the set of conditional attributes for which |E(T, fi)| ≥ 2.

Let T be a nonempty decision table. A subtable of T is a table obtained from T by the removal of some rows. Let fi1 , . . . , fim ∈ {f1, . . . , fn} and a1, . . . , am ∈ ω where ω is the set of nonnegative integers. We denote by T (fi1 , a1) . . . (fim , am) the subtable of the table T containing the rows from T which at the intersection with the columns fi1 , . . . , fim have numbers a1, . . . , am, respectively.

As an uncertainty measure for nonempty decision tables we consider relative misclassification error rme(T ) = (N (T )−Nmcd(T )(T ))/N (T ) where Nmcd(T )(T ) is the number of rows r in T containing the most common decision for T in D(r).

A decision rule over T is an expression of the kind (fi1 = a1) ∧ . . . ∧ (fim = am) → fn+1 = t (1) where fi1 , . . . , fim ∈ {f1, . . . , fn}, and a1, . . . , am, t are numbers from ω. It is possible that m = 0. For the considered rule, we denote T 0 = T , and if m > 0 we denote T j = T (fi1 , a1) . . . (fij , aj ) for j = 1, . . . , m. We will say that the decision rule (1) covers the row r = (b1, . . . , bn) of T if r belongs to T m, i.e., bi1 = a1, . . . , bim = am.

A decision rule (1) over T is called a decision rule for T if t = mcd(T m), and if m > 0, then T j−1 is not degenerate for j = 1, . . . , m, and fij ∈ E(T j−1). We denote by DR(T ) the set of decision rules for T .

Let ρ be a decision rule for T which is equal to (1). The value rme(T, ρ) = rme(T m) is called the uncertainty of the rule ρ. Let α be a real number such that 0 ≤ α ≤ 1. We will say that a decision rule ρ for T is an α-decision rule for T if rme(T, ρ) ≤ α. If α = 0 (in this case, for each row r covered by ρ, the set D(r) contains the decision on the right-hand side of ρ) then we will say that ρ is an exact rule. We denote by DRα(T ) the set of α-decision rules for T . 3

Algorithm for Construction of Association Rule System

α-Decision rules for tables from Φm−v(I) can be considered as α-association rules (modification for many-valued decision model) for the information system I. αDecision rules for decision tables from Φs−v(I) can be considered as α-association rules (modification for single-valued decision model) for the information system I. In this section, we consider an algorithm for construction of an association rule system for I in the frameworks of both many-valued decision model and single-valued decision model. Since decision tables with single-valued decisions are a special kind of decision tables with many-valued decisions, we will discuss mainly many-valued decision model.

Let T = Ifmn−+1v. Let S be a nonempty finite set of α-decision rules for T (system of α-decision rules for T ), and β be a real number such that 0 ≤ β ≤ 1. We say that S is a β-system of α-decision rules for T if rules from S cover at least (1 − β)N (T ) rows of T .

We describe an algorithm α-β-Rules which, for a decision table T , and real numbers α and β, 0 ≤ α ≤ 1, and 0 ≤ β ≤ 1, constructs a β-system of α-decision rules for T . During each step, we choose (based on a dynamic programming algorithm [ 4 ]) a decision rule which covers maximum number of uncovered previously rows. We stop when the constructed rules cover at least (1 − β)N (T ) rows of T . We denote by Ruleα,β (T ) the constructed system of rules.

We denote by C(T, α, β) the minimum cardinality of a β-system of α-decision rules for T . It is clear that C(T, α, β) ≤ |Ruleα,β (T )|. Using information based on the work of algorithm α-β-Rules, we can obtain lower bound on the parameter C(T, α, β). During the construction of β-system of α-decision rules for T , let the algorithm αβ-Rules selects consequently rules ρ1, . . . , ρt. Let B1, . . . , Bt be sets of rows of T covered by rules ρ1, . . . , ρt, respectively. Set B0 = ∅, δ0 = 0 and, for i = 1, . . . , t, set δi = |Bi \ (B0 ∪ . . . ∪ Bi−1)|. The information derived from the algorithm’s work consists of the tuple (δ1, . . . , δt) and the numbers N (T ) and β.

From the results obtained in [ 10 ] regarding a greedy algorithm for the set cover problem it follows that C(T, α, β) ≥ l(T, α, β) where l(T, α, β)) = max ⌈(1 − β)N (T )⌉ − (δ0 + . . . + δi) δi+1 : i = 0, . . . , t − 1 .

Using algorithm α-β-Rules, for each decision table T ∈ Φm−v(I), we construct the set of rules Ruleα,β (T ). As a result, we obtain the system of rules (αassociation rules for the information system I – modification for many-valued decision model) Ruleαm,−βv(I) = ST ∈Φm−v(I) Ruleα,β (T ). This system contains, for each T ∈ Φm−v(I), a subsystem which is a β-system of α-decision rules for T . We denote by Cm−v(I, α, β) the minimum cardinality of such system. One can show that

Lm−v(I, α, β) ≤ Cm−v(I, α, β) ≤ U m−v(I, α, β), Lm−v(I, α, β) = PT ∈Φm−v(I) l(T, α, β) and U m−v(I, α, β) = Ruleαm,−βv(I) .

We can do the same for the set Φs−v(I) of decision tables with single-valued decisions. As a result, we obtain the system of rules (α-association rules for the information system I – modification for single-valued decision model) Rulesα−,βv(I) = ST ∈Φs−v(I) Ruleα,β (T ) which contains, for each T ∈ Φs−v(I), a subsystem which is a β-system of α-decision rules for T . Denote Cs−v(I, α, β) the minimum cardinality of such system. One can show that

Ls−v(I, α, β) ≤ Cs−v(I, α, β) ≤ U s−v(I, α, β), Ls−v(I, α, β) = PT ∈Φs−v(I) l(T, α, β) and U s−v(I, α, β) = Rulesα−,βv(I) . 4

Experimental Results

Experiments were made using data sets from UCI Machine Learning Repository [ 5 ] and software system Dagger [ 3 ]. Some decision tables contain conditional attributes that take unique value for each row. Such attributes were removed. In some tables, there were equal rows with, possibly, different decisions. In this case each group of identical rows was replaced with a single row from the group with the most common decision for this group. In some tables there were missing values. Each such value was replaced with the most common value of the corresponding attribute.

Prepared 12 data sets were considered as information systems. Table 1 contains name (column “Information system”), number of rows (column “Rows”), and number of attributes (column “Attr”) for each of the considered information systems. Table 1 presents also upper / lower bounds (see descriptions at the end of the previous section) on Cm−v(I, α, β) (column “many-val”) and on Cs−v(I, α, β) (column “single-val”) for pairs (α = 0, β = 0) and (α = 0.3, β = 0.2).

We can see that, for tables with many-valued decisions, upper and lower bounds on the number of rules are less than or equal to the bounds for decision tables with single-valued decision. We considered a threshold

30 × (number of attributes) as a reasonable upper bound on the number of rules if a system of rules is used for knowledge representation. In the case α = 0 and β = 0, the threshold is exceeded for five information systems (see numbers in bold): balance-scale, breast-cancer, cars, hayes-roth-data, and tic-tac-toe. The consideration of approximate rules and partial covers can improve the situation. In the case α = 0.3 and β = 0.2, the threshold is exceeded for three information systems (balance-scale, breast-cancer, and tic-tac-toe) if we consider decision tables with single-valued decisions and for two information systems (breast-cancer and tic-tac-toe) if we consider decision tables with many-valued decisons.

For four information systems (balance-scale, breast-cancer, cars, and hayes-rothdata), upper / lower bounds on Cm−v(I, α, β)) and on Cs−v(I, α, β)) for β ∈ {0, 0.01, 0.05, 0.1, 0.15, 0.2} and α ∈ {0, 0.1, 0.3} can be found in Tables 2, 3, 4, and 5. 5

Conclusions

In the paper, an algorithm for construction of association rule system is proposed. It simulates the work of greedy algorithm for set cover problem. Experimental results present cardinality of the set of association rules constructed for information system and lower bound on minimum possible cardinality of such set based on the information about the algorithm work. In the future, the length of constructed association rules will be studied also. We are planning to extend an approach proposed in [ 14 ] for decision rules to construction of association rule systems. This approach allows one to construct rules with coverage close to maximum and requires less time than the dynamic programming approach. Acknowledgements Research reported in this publication was supported by the King Abdullah University of Science and Technology (KAUST).

The authors wish to express their gratitude to anonymous reviewers for useful comments.

References

1. Agrawal , R. , Imielin´ski, T., Swami , A. : Mining association rules between sets of items in large databases . In: SIGMOD '93 , pp. 207 - 216 . ACM ( 1993 )

2. Agrawal , R. , Srikant , R.: Fast algorithms for mining association rules in large databases . In: Bocca, J.B. , Jarke , M. , Zaniolo , C. (eds.) VLDB, pp. 487 - 499 . Morgan Kaufmann ( 1994 )

3. 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 , pp. 29 - 39 . Blue Herons ( 2011 )

4. Alsolami , F. , Amin , T. , Chikalov , I. , Moshkov , M.: Multi-stage optimization of decision rules for knowledge discovery and representation . Knowledge and Information Systems ( 2015 ), (submitted)

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

6. Bonates , T. , Hammer , P.L. , Kogan , A. : Maximum patterns in datasets . Discrete Applied Mathematics 156 ( 6 ), 846 - 861 ( 2008 )

7. Borgelt , C. : Simple algorithms for frequent item set mining . In: Koronacki, J. , Ras´, Z.W. , Wierzchon´, S.T. , Kacprzyk , J . (eds.) Advances in Machine Learning II, Studies in Computational Intelligence , vol. 263 , pp. 351 - 369 . Springer Berlin Heidelberg ( 2010 )

8. Glass , D.H. : Confirmation measures of association rule interestingness . Knowledge-Based Systems 44(0) , 65 - 77 ( 2013 )

9. Han, J ., Kamber , M. : Data Mining: Concepts and Techniques . Morgan Kaufmann ( 2000 )

10. Moshkov , M.J. , Piliszczuk , M. , Zielosko , B. : Greedy algorithm for construction of partial association rules . Fundam. Inform . 92 ( 3 ), 259 - 277 ( 2009 )

11. Moshkov , M.J. , Piliszczuk , M. , Zielosko , B. : On construction of partial association rules . In: Wen, P. , Li , Y. , Polkowski , L. , Yao , Y. , Tsumoto , S. , Wang , G . (eds.) RSKT, LNCS, vol. 5589 , pp. 176 - 183 . Springer ( 2009 )

12. Pawlak , Z. , Skowron , A. : Rudiments of rough sets . Inf. Sci . 177 ( 1 ), 3 - 27 ( 2007 )

13. Toivonen , H.: Sampling large databases for association rules . In: Vijayaraman, T.M. , Buchmann , A.P. , Mohan , C. , Sarda , N.L . (eds.) VLDB, pp. 134 - 145 . Morgan Kaufmann ( 1996 )

14. Zielosko , B. : Optimization of approximate decision rules relative to coverage . In: Kozielski, S. , Mrózek , D. , Kasprowski , P. , Małysiak-Mrózek , B. , Kostrzewa , D . (eds.) BDAS 2014 . LNCS , vol. 8537 , pp. 170 - 179 . Springer ( 2014 )

15. Zielosko , B. : Global optimization of exact association rules relative to coverage . In: Kryszkiewicz, M. , Bandyopadhyay , S. , Rybin´ski, H., Pal , S.K. (eds.) PReMI 2015 . LNCS, vol. 9124 , pp. 428 - 437 . Springer ( 2015 )