In the paper, an application of dynamic programming approach to global optimization of exact association rules relative to length is presented. It is an extension of the dynamic programming approach to optimization of decision rules to inconsistent tables. An information system I is transformed into a set of decision tables {If1 , . . . , Ifn+1 }. The algorithm constructs, for each decision table from the set {If1 , . . . , Ifn+1 }, a directed acyclic graph Δ(Ifi ), i = 1, . . . , n + 1. Based on the graph, the set of so-called irredundant (fi)association rules can be described. The union of sets of (fi)-association rules, i = 1, . . . , n + 1, is considered as a set of association rules for information system I. Then, global optimization relative to length is made and sets of association rules with minimum length, for each row of information system I, are obtained. Preliminary experimental results with data sets from UCI Machine Learning Repository are included.
Association rule mining is one of the important fields of data mining and knowledge discovery. It aims to extract interesting correlations, associations, or frequent patterns among sets of items in data set.
There are many algorithms for construcion of association rules. The most
popular algorithm for mining associaion rules is Apriori algorithm [
In the paper, an application of dynamic programming approach to optimization of
exact association rules relative to length is presented. Construcion of short rules is
connected with the Minimum Description Length principle introduced by Rissanen [
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 [
This paper is an essential extension of the paper [
Proposed approach by comparison with Apriori algorithm allows one to derive a reguired number of rules for a given row only. If we consider sequential optimization relative to coverage and length it is possible to find so-called totally-optimal rules, i.e., rules with maximum coverage and minimum length. Experimental resuls show that such rules have often good coverage and small length.
The aim of the paper is to create a research tool which is applicable to medium
sized decision tables and allows one to construct exact association rules with minimum
length. To this end, an information system I with attributes {f1, . . . , fn+1} is
transformed into a set of decision tables {If1,...,Ifn+1}. The algorithm constructs, for each
decision table from the set {If1,. . . ,Ifn+1}, a directed acyclic graph Δ(Ifi ), i = 1, . . . , n + 1.
Based on the graph Δ(Ifi ), the set of so-called irredundant (fi)-association rules,
i = 1, . . . , n + 1, can be described. The union of sets of irredundant (fi)-association
rules, i = 1, . . . , n + 1, is considered as the set of irredundant association rules for
information system I . Using global optimization relative to length it is possible to obtain
the set of irredundant association rules for information system I with minimum length.
In [
The paper consists of six sections. Section 2 contains main notions. In Section 3, an algorithm for construction of a directed acyclic graph is presented. Section 4 contains a description of optimization procedure relative to length. Section 5 contains experimental results for decision tables from UCI Machine Learning Repository, and Section 6 conclusions.
An information system I is a 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 notion of a decision table and decision rule.
A decision table T is a table with n columns labeled with (conditional) attributes f1, . . . ,fn. Rows of this table are filled by nonnegative integers which are interpreted as values of conditional attributes. Each row is labeled with a nonnegative integer (decision) which is interpreted as a value of a decision attribute. It is possible that T contains equal rows with the same or different decisions.
For each attribute fi ∈ {f1, . . . , fn+1}, the information system I is transformed into a decision 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 which will be denoted by Ifi .
f1 f2 f3 r1 1 1 2 I = r2 0 0 2 r3 1 1 1
The expression fi1 = a1 ∧ . . . ∧ fim = am → fn+1 = d (1) 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 → fn+1 = d. (2)
Let r = (b1, . . . , bn) be a row of T . Rule (1) will be called realizable for r, if a1 = bi1 , . . . , am = bim . If m = 0 then rule (2) is realizable for any row from T .
Rule (1) will be called true for T if the table T ′ = T (fi1 , a1) . . . (fim , am) is degenerate and d is the most common decision for T ′. If m = 0 then rule (2) is true for T if T is degenerate and d is the most common decision for T .
If rule (1) is true for T and realizable for r, then (1) will be called a decision rule for T and r.
Decision rules for T and r will be called (fn+1)-association rules for I and r. In general case, the notion of (fi)-association rule for I and r coincides with the notion of decision rule for Ifi and r, i = 1, . . . , n + 1. The union of sets of (fi)-association rules, i = 1, . . . , n + 1, will be considered as the set of association rules for I and r.
Let T = Ifn+1 and (1) be a decision rule over T . Rule (1) will be called an irredundant rule for T and r if (1) is a decision rule for T and r and the following conditions hold if m > 0: (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 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 d is the most common decision for T .
Let T = Ifn+1 , τ be a decision rule over T , and τ be equal to (1). The length of τ is the number m of descriptors (pairs attribute=value) on the left-hand side of τ . It is denoted by l(τ ). If m = 0 then the length of the rule τ is equal to 0. 3
In this section, an algorithm for construction of a directed acyclic graph for a given decision table T is presented. Based on this graph it is possible to describe the set of irredundant rules for T and for each row r of T . This algorithm is repeated for each decision table Ifi , i = 1, . . . , n + 1, obtained from the information system I.
Let T = Ifn+1 . The constructed graph is denoted by Δ(T ). Nodes of the graph are some 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 the algorithm have already performed p steps. Now the step (p + 1) will be described. 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 the considered node with symbol * and proceed 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. Each row r of Θ is labeled with the set of attributes EΔ(T )(Θ, r) = E(Θ). 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. A node Θ is terminal if and only if Θ is degenerate.
Later, a local optimization of the graph Δ(T ) relative to the length will be described. As a result, a graph G(T ), with the same sets of nodes and edges as in Δ(T ), is obtained. The only difference is that any row r of each nonterminal node Θ from G(T ) is labeled with a nonempty set of attributes EG(T )(Θ, r) ⊆ E(Θ), possibly different from E(Θ).
Let G ∈ {Δ(T ), G(T )}. Now, for each node Θ of G and for each row r of Θ, a set of rules RulG(Θ, r) will be described.
Let Θ be a terminal node of G. In this case Θ is a degenerate table and
RulG(Θ, r) = {→ fn+1 = d}, where d is the most common decision for Θ.
Let now Θ be a nonterminal node of G such that, for each child Θ′ of Θ and for each row r′ of Θ′, the set of rules RulG(Θ′, r′) is already defined. Let r = (b1, . . . , bn) be a row of Θ. For any fi ∈ EG(Θ, r), the set of rules RulG(Θ, r, fi) is defined as follows:
RulG(Θ, r, fi) = {fi = bi ∧ γ → fn+1 = s :
γ → fn+1 = s ∈ RulG(Θ(fi, bi), r)}.
Then RulG(Θ, r) = Sfi∈EG(Θ,r) RulG(Θ, r, fi).
One can prove the following statement.
Theorem 1. For any node Θ of Δ(T ) and for any row r of Θ, RulΔ(T )(Θ, r) is equal to the set of all irredundant rules for Θ and r.
The algorithm for the directed acyclic graph construction is repeated for each decision table Ifi , i = 1, . . . , n + 1, obtained from the information system I. In general, the obtained graph is denoted by Δ(Ifi ), i = 1, . . . , n + 1. As a result, for i = 1, . . . , n + 1, the set RulΔ(Ifi )(Ifi , r) of irredundant decision rules for Ifi and r is obtained. This set will be called the set of irredundant (fi)-association rules for I and r, i = 1, . . . , n + 1. The union of sets RulΔ(Ifi )(Ifi , r) forms the set Rul(I, r) of irredundant association rules for I and r:
Rul(I, r) =
[ i=1,...,n+1
RulΔ(Ifi )(Ifi , r).
Example 1. To illustrate the presented algorithm the information system I depicted in Fig. 1 will be considered. Set Φ = {If1 , If2 , If3 } contains three decision tables obtained from I. Figure 2 presents a directed acyclic graph for decision table If1 . Based on the graph Δ(If1 ) the sets of rules attached to rows of If1 are described.
RulΔ(If1 )(If1 , r1) = {f2 = 1 → f1 = 1, f3 = 2 ∧ f2 = 1 → f1 = 1};
Let Θ be a nonterminal node of Δ(T ) and all children of Θ have already been treated. Let r = (b1, . . . , bn) be a row of Θ. The number
OptlΔ(T )(Θ, r) = min{OptlΔ(T )(Θ(fi, bi), r) + 1 : fi ∈ E(Θ, r)} is assigned to the row r in the table Θ and EΔ(Θ, r) = {fi : fi ∈ EΔ(T )(Θ, r), OptlΔ(T )(Θ(fi, bi), r) + 1 = OptlΔ(T )(Θ, r)}. Theorem 2. For each node Θ of the graph G(T ) and for each row r of Θ, the set RulG(T )(Θ, r) is equal to the set RulΔl(T )(Θ, r) of all rules with the minimum length from the set RulΔ(T )(Θ, r).
Now, a global optimization relative to the length is presented. It is made for the information system I.
The set of irredundant association rules for I and r with the minimum length from Rul(I, r) is denoted by Rull(I, r), and the minimum length of an association rule from Rul(I, r) is denoted by Optl(I, r).
To make global optimization relative to the length, the directed acyclic graph is constructed for each decision table Ifi ∈ Φ, and local optimization relative to the length of the graph Δ(Ifi ), i = 1, . . . , n + 1, is made. As a result, the graph G(Ifi ) is obtained and each row r of Ifi , i = 1, . . . , n + 1, has assigned the set RulG(Ifi )(Ifi , r) of (fi)association rules for I and r with the minimum length from RulΔ(Ifi )(Ifi , r) and the number OptlΔ(Ifi )(Ifi , r), which is the minimum length of (fi)-association rule from RulΔ(Ifi)(Ifi , r).
Then, the value Optl(I, r) is obtained, such that,
Optl(I, r) = min{OptlΔ(Ifi )(Ifi , r) : i = 1, . . . , n + 1}, and among all numbers, i = 1, . . . , n + 1, only these are selected, where These numbers forms the set N (I). Then
OptlΔ(Ifi )(Ifi , r) = Optl(I, r).
Rull(I,r) =
[ i∈N(I)
RulG(Ifi)(Ifi, r).
As a result of the global optimization relative to the length each row r of I has assigned the set Rull(I, r) of association rules with the minimum length and the number Optl(I, r).
Below one can find the set Rull(I, r) and the value Optl(I, r) for the information system I depicted in Fig. 1 and each row r of this system.
Rull(I, r1) = {f2 = 1 → f1 = 1, f1 = 1 → f2 = 1, f1 = 1 → f3 = 1, f2 = 1 → f3 = 1}, Optl(I, r1) = 1; Rull(I, r2) = {f2 = 0 → f1 = 0, f1 = 0 → f2 = 0, f1 = 0 → f3 = 2, f2 = 0 → f3 = 2}, Optl(I, r2) = 1; Rull(I, r3) = {f2 = 1 → f1 = 1, f3 = 1 → f1 = 1, f1 = 1 → f2 = 1, f3 = 1 → f2 = 1, f1 = 1 → f3 = 1, f2 = 1 → f3 = 1}, Optl(I, r3) = 1.
The problem of rule length minimization is NP-hard [
Experiments were made using data sets from UCI Machine Learning Repository [
Each data set was considered as information system I and, for each attribute fi ∈ {f1, . . . , fn+1}, the system I was transformed into a decision table Ifi . The column fi was removed from I and a table with n columns labeled with attributes f1, . . . , fi−1, fi+1, . . . , fn+1, was obtained. Values of the attribute fi were attached to the rows of the obtained table Ifi . The set {If1 , . . . , Ifn+1 } of decision tables obtained from the information system I is denoted by Φ.
Table 1 presents preliminary results of experiments connected with the minimum length of irredundant association rules (column “Association rules”). For each row r of I, the minimum length of an irredundant association rule for I and r was obtained. After that, for rows of I the minimum length of an association rule for I and r with the minimum length (column “Min”), the maximum length of such rule (column “Max”) and the average length of association rules with the minium length - one for each row (column “Avg”) were obtained. Column “Rows” contains the number of rows in I, column “Attr” contains the number of attributes in I. This table contains also, for the purpose of comparison, minimum, average and maximum length of exact irredundant decision rules (column “Decision rules”) obtained by the dynamic programming algorithm.
Based on the results in Table 1, it is possible to see that the proposed approach allows one to obtain short association rules. The minimum value of minimum length (column “Min”) is equal to 3 only for two data sets, for the rest of data sets, this value is equal to 1. In the case of comparison of length of association and decision rules, the minimum values (columns “Min”) of minimum lenght of rules are the same. The average values (columns “Avg”) and the maximum values (columns “Max”), often are smaller in the case of association rules. Only for data sets “Monks-1-test” and “Monks3-test”, the obtained results are the same for association and decision rules.
Table 2 presents the average number of nodes (column “Nodes”) and the average number of edges (column “Edges”) related to the data set I and the graph Δ(Ifi ), i = 1, . . . , n + 1. For each data set I, the set Φ was obtained. For each decision table Ifi , i = 1, . . . , n + 1, the graph Δ(Ifi ) was constructed and the number of nodes and edges were calculated. Then, the average number of nodes and edges in the directed acyclic graphs Δ(Ifi ), i = 1, . . . , n + 1, were computed.
The proposed approach of rule induction is based on the analysis of the directed
acyclic graph constructed for a given decision table. The structure of the graph depends
on data set, i.e., number of attributes, distribution of values of attributes, number of
rows. Such graph can be huge for larger data set. Therefore, possibilities of decreasing
the size of the graph were studied by the author. In [
In the paper, an application of dynamic programming to global optimization of exact association rules relative to length was presented. It is based on the dynamic programming approach to optimization of decision rules. However, there are differences: (i) definitions are different, (ii) the information system is used, (ii) decision table can be inconsistent, and (iv) global optimization relative to length was studied. The presented approach can be considered as a research tool which allows one to construct association rules with minimum length.
Possible applications of association rules obtained using presented approach are construction of classifiers, inference process in knowledege base system, filling missing values of attributes.
Future works will be connected with future selection, construction of classifiers and possibilites of decreasing the size of the directed accyclic graph.