Decision table decomposition is a method that decomposes given decision table into an equivalent set of decision tables. Decomposition can enhance the quality of knowledge discovered from databases by simplifying the data mining task. The paper contains a description of decision table decomposition method and their evaluation for data classification. Additionally, a novel method of obtaining attributes sets for decomposition was introduced. Experimental results demonstrated that decomposition can reduce memory requirements preserving the accuracy of classification.
Increasing amount of data requires to develop new data analysis methods. A common
approach in data mining is to make a prediction based on decision tables.
Decomposition of a decision table to smaller subtables could be obtained by the divide and conquer
strategy. This idea comes from logic synthesis and functional decomposition [
The fundamentals of decision system and logic synthesis are different, but there are many similarities between them. The decision system is usually described by a decision table, and combinational logic of a digital system by a truth table. Input variables of digital systems correspond to conditional attributes. Therefore, multiple terms from logic synthesis may be extended to data mining. Functional decomposition could be used to build a hierarchical decision system.
The functional decomposition was firstly used in logic synthesis of digital systems.
In this situation, decomposition involves breaking a large logic functions, which are
difficult to implement, into several smaller ones, which can be easy to implement. A
similar problem in machine learning relies on disassembling the decision table to the
subsystems in such a way that the original decision table can be recreated through a
series of operations corresponding to the hierarchical decision making. But the most
important is that we can induce noticeably simpler decision rules and trees for the
resulting components to finally make the same decision as for the original decision table.
[
For evaluation of decomposition, the decision trees and rules classifiers based on
extensions of dynamic programming [
Information system is a pair A = (U, A), where U is a non-empty, finite set of objects called the universe, A is a non-empty, finite set of attributes, i.e. each element a ∈ A is a function from U into Va, where Va is the domain of a called value set of a. Then, the function ρ maps the product of U and A into the set of all values. The value of the attribute for a specific object is denoted by ρ(ut, ai), with ut ∈ U , ai ∈ A
One or more distinguished attributes from set A of information system may indicate a decision from rest of attributes. Such information system is called decision system. Formally, decision system is information system denoted by A = (U, A ∪ D), where A ∩ D = ∅. Attributes in set A are referred to as conditional attributes while attributes in set D are referred to as decision attributes. However, in the case when function ρ maps U × (A ∪ D) into the set of all attribute values such system is called decision table.
Let A = (U, A) be an information system. For each subset B ⊆ A we define B-indiscernibility relation IN DA(B):
IN DA(B) = (up, uq) ∈ U 2 : ∀ai ∈ B, ρ(up, ai) = ρ(uq, ai) (1) The attribute values a1, i.e. ρpi = ρ(up, a1) and ρqi = ρ(uq, a1) are compatible (ρpi ∼ ρqi) if, and only if, ρpi = ρqi or ρpi = ∗ or ρqi = ∗, where "∗" represents attributes value "do not care". In the other case ρpi and ρqi are not compatible (ρpi ≁ ρqi).
The consequence of this definition is compatibility relation COMA(B) associated with every B ⊆ A :
COMA(B) = (up, uq) ∈ U 2 : ∀ai ∈ B, ρ(up, ai) ∼ ρ(uq, ai)
(2)
COMA(B) classifies objects by grouping them into compatibility classes, i.e.
U/COMA(B), where B ⊆ A. Collection of subsets U/COM (B) is called r-partition
on U and denote as ΠA(B). R-partition on a set U may be viewed as a collection of
non-disjoint subsets of U , where the set union is equal U . All symbols and operations
of partition algebra [
To compress data and accelerate computations, hierarchical decomposition can be applied. The goal is to break down a decision table into two smaller subtables.
Let F be a functional dependency D = F(A) for a consistent decision system A = (U, A∪D), where A is a set of conditional attributes and D is a set of decision attributes. Let B1, B2 be subsets of A such that A = B1 ∪ B2 and B1 ∩ B2 = ∅. A simple hierarchical decomposition relative to B1, B2 exists for F(A) if and only if: F(A) = H(B1, G(B2)) = H(B1, δ) (4) where G and H represent the following functional dependencies: G(B2) = δ and H(B1, δ) = D, where δ is a intermediate attribute. The output of functions F(A) and H are exactly the same. In other words we try to find a function H depending on the variables of the set B1 as well on the output δ of a function G depending on the set B2.
In Theorem 1., r-partition ΠG represents component G, and the product of rpartitions Π(B1) and ΠG corresponds to H. The decision tables of the resulting components can be easily obtained from these r-partitions.
According to Theorem 1 the main problem is to find a partition ΠG. To solve that problem, a subset of original attributes B2 and an m-block partition Π (B2) = {K1, K2, ..., Km} generated by that subset is appropriate to consider. Two blocks Ki, Kj of partition Π (B2) are compatible if and only if the partition Π ′ obtained from Π (B2) by joining the blocks Ki and Kj into a single block Kij (without changing the ′ other ones) satisfies the equation (5), i.e. iff Π · ΠG ≤ Π (D). Otherwise, Ki, Kj are incompatible.
For decision table from Table 1 and sets of attributes B1 = {a0, a5}, B2 = {a1, a2, a3, a4} the following set of incompatible pairs could be found: E = {(K1, K8), (K2, K4), (K2, K8), (K3, K7)(K4, K5)}. The subset of n partition blocks, Π (B2) = {Ki1 , Ki2 , ..., Kin } where Kij ∈ Π (B2) is the compatible class of Π (B2) partition blocks iff all blocks of that subset are pairwise compatible. The compatibility class is referred to as maximal compatibility class (MCC) iff it does not belong to any other compatibility class of the partition concerned.
K7
K8 K6
K1 K5
K2 K4
K3
The decomposition process may be interpreted in terms of an incompatibility graph (Fig. 1). The edges represent the incompatible pairs of partition Π (B2) : (K1, K8), (K2, K4), (K2, K8), (K3, K7), (K4, K5). It is clearly visible that the proper coloring of the graph specifies the compatible classes: {K1, K2, K3, K5} , {K4, K6, K7, K8} and, as a consequence, the partition ΠG =
0, 1, 2, 4, 5, 7, 9; 3, 6, 8 .
Another approach to building an incompatibility graph is to create a labeled
partition matrix [
Let C and B be sets of attributes, then B depends entirely on a set of attributes C, denoted C ⇒ B, if all values of attributes from B are uniquely determined by the values of attributes from C. If B depends in degree k, 0 ≤ k ≤ 1, on C, then: (6) (7) (8) where k = γ(C, B) = |P OSC (B)|
|U | P OSC (D) =
[ X∈U/B
C∗(X) called a positive region of the partition U/B with respect to C, is the set of all elements of U that can be uniquely classified to blocks of the partition U/B, by means of C.
Proposed method allows us to measure dependency between all possible pairs of conditional attributes and decision attribute. Related dependency of one conditional attribute can be generated from a given information system: A = (U, A ∪ {d}), where A = {a0, ..., ak} is a set of conditional attributes and d is a decision attribute: r(x) =
P0k γ({x, ai} , {d}) |A| , x ∈ A
The above function of related dependency is used for comparison of attributes. This function is being calculated for each attribute, then the results are being sorted by the value of function r. The most dependent attributes are put in set B1, which corresponds to the final decision table H. Example 1. For Table 1 first step of the algorithm is to built a matrix of attribute dependency between each pair of condition attributes and decision attribute. Then the mean of partial results is calculated, which is represented by related dependency r(x) in Table 3. These results can be sorted by value and divided into two equinumerous sets. If the number of attributes is odd, then set |B1| = |B2| + 1. An example of sorting and assignment attributes is presented in Table 4. The calculation of related dependency r(x) allows formulating an accurate method for assessing sets B1 and B2, i.e. B1 = {a1, a3, a5} and B2 = {a0, a2, a4}. Therefore the decomposition is as follows: F(A) = H({a1, a3, a5} , G({a0, a2, a4})).
Hierarchical Decision Making
Due to the decomposition of decision tables, there is a need for hierarchical decision
system to evaluate this method for the purpose of classification [
B1
B2 G
Intermediate decision H
F Fdiencailsion
number of misclassifications and the depth of decision trees or the length of decision
rules. Proposed algorithm constructs a directed acyclic graph (DAG), which represents
structure of subtables of initial tables. For decision table A separable subtables of A
described by systems of equalities of the kind ai = b are considered as subproblems,
where ai is an attribute and b is its value. Classification and optimization of decision
trees and rules are discussed in details in [
In the applied approach to optimization of decision trees directed acyclic graph
(DAG) represents a set of CART-like decision trees [
The system of decision rules as a prediction model was also considered. As in case
of decision trees we used dynamic programming algorithm to create and optimize
decision rules [
To evaluate the proposed decomposition algorithm and hierarchical decision making
idea the Dagger software system created in King Abdullah University of Science and
Technology was used. Proposed algorithm has been tested on categorical datasets from
UCI ML Repository [
data set rows attributes compression (SD/S) flags 196 27 0.801 house 281 17 0.395 kr-vs-kp 3198 37 0.209 breast cancer 268 10 0.754
cars 1730 7 0.261 spect-test 169 23 0.751 dermatology 366 35 0.352
The advantage of decomposition is due to the fact that two components (i.e. tables G and H) require less memory than the original decision table. Let us express the size of the table as S = n Pi bi, where n is the number of objects, and bi = log2 |Vai | is the number of bits required to represent attribute ai. Then, after the decomposition, we may compare the size of specific components with that of the original table (prior to decomposition). Results of compression are presented in Table 5.
However, for most of measurements, accuracy keeps a significant level or is slightly
better. The biggest improvement occurring when dynamic programing rules were used.
Effective data aggregation algorithms have been sought after for a long time due to the
increasing complexity of databases used in practice. Recently, some suggestions were
put forward that decomposition algorithms, previously used mainly in logic synthesis
of digital systems, may be applied for that purpose [
The paper indicates the advantages and possibilities of decomposition algorithms for the purpose of classification. Results of experiments performed by proposed decomposition algorithm and Dagger system has been presented. New attributes selection criteria describing partitions for decomposition has been introduced and used in the experiments. Proposed method is particularly efficient in data compression. It allows to build simple classification model and save memory, simultaneously keep the accuracy. To achieved better results in accuracy data set decomposition requires further research, particularity with attributes selection criteria. Also, there is a need to extend the decomposition to deal with continuous attributes and noise in data. Acknowledgments. The authors would like to thank professor Mikhail Moshkov and his team for their support while writing this paper. This research has been supported by King Abdullah University of Science and Technology.