What is the practical difference between association rules and decision trees in data mining?

Question

Is there a really simple description of the practical differences between these two techniques?

• Both seem to be used for supervised learning (though association rules can also handle unsupervised).

• Both can be used for prediction

The closest I've found to a 'good' description is from the Statsoft Textbook. They say Association Rules are used to:

...detect relationships or associations between specific values of categorical variables in large data sets.

Whilst Decision Tree classifiers are described as being used to:

...predict membership of cases or objects in the classes of a categorical dependent variable from their measurements on one or more predictor variables.

However, over at R Data Mining, they give an example of Association Rules being used with a target field.

So both can be used to predict group membership, is the key difference that decision trees can handle non-categorical input data whilst association rules can't? Or is there something more fundamental? One site (sqlserverdatamining.com) says that the key difference is:

The decision trees rules are based on information gain while association rules are based on popularity and/or confidence.

So (possibly answering my own question) does that mean that association rules are evaluated purely on how often they appear in the dataset (and how often they are 'true') whilst decision trees are actually trying to minimise variance?

If anyone knows of a good description they'd be willing to point me towards then that would be great.

Answer 1

Basically, Decision Trees are a pure classification techniques. These techniques aim at labelling records of unknown class making use of their features. They basically map the set of record features $\mathcal{F} = {F_1 , \dots, F_m }$ (attributes, variables) into the class attribute $C$ (target variable), the object of the classification. The relationship between $\mathcal{F}$ and $C$ is learned using a set of labelled records, defined as the training set. The ultimate purpose of classification models is to minimise the mis-classification error on unlabelled records, where the class predicted by the model differs from the real one. The features $F$ can be categorical or continuous.

Association analysis first applications were about market basket analysis, in these application you are interested in finding out association between items with no particular focus on a target one. Datasets commonly used are the transactional ones: a collection of transaction were each of those contains a set of items. For example: $$ t_1 = \{i_1,i_2 \} \\ t_2 = \{i_1, i_3, i_4, i_5 \} \\ t_3 = \{i_2, i_3, i_4, i_5 \} \\ \vdots \\ t_n = \{ i_2, i_3, i_4, i_5 \} $$ You are interested in finding out rules such as $$ \{ i_3, i_5 \} \rightarrow \{ i_4 \} $$

It turns out that you can use association analysis for some specific classification tasks, for example when all your features are categorical. You have just to see items as features, but this is not what association analysis was born for.

Answer 2

• "Association rules aim to find all rules above the given thresholds involving overlapping subsets of records, whereas decision trees find regions in space where most records belong to the same class. On the other hand, decision trees can miss many predictive rules found by association rules because they successively partition into smaller subsets. When a rule found by a decision tree is not found by association rules it is either because a constraint pruned the search space or because support or confidence were too high."

• "Association rules algorithms can be slow, despite many optimizations proposed in the literature because they work on a combinatorial space, whereas decision trees can be comparatively much faster because each split obtains successively smaller subsets of records."

• "When a decision tree is built an unbounded depth in the induction process can lead to small groups of records, decreasing rule generality and reliability . In a decision tree, internal nodes do not produce any rules (although tentative rules can be derived), which leads to increasingly longer and more complex rules until an acceptable node purity is reached. On the other hand, association rules can indeed produce rules corresponding to internal nodes corresponding to multiple trees, but they require careful interpretation since any two rules may refer to overlapping data subsets. Decision trees tend to be overfit for a particular data set, which may affect their applicability. Post-processing pruning techniques can reduce overfit, but unfortunately they also reduce rule confidence. Another issue is that decision trees can repeat the same attribute multiple times for the same rule because such attribute is a good discriminator. This is not a big issue since rules are conjunctions and therefore the rule can be simplified to one interval for the attribute, but such interval will be generally small and the rule too specific."

Excerpts from:

Ordonez, C., & Zhao, K. (2011). Evaluating association rules and decision trees to predict multiple target attributes. Intelligent Data Analysis, 15(2), 173–192.

A nice article covering this topic, definitely worth reading.

Answer 3

We may argue that both association rules and decision trees suggest a set of rules to the user and hence both are similar, but we must understand the theoretical difference between decision trees and association rules, and further how rules suggested by both are different in meaning or in use.

Firstly, decision tree is a supervised approach where the algorithm tries to predict an "outcome". A typical example of an "outcome" in real-life situations could be, e.g. churn, fraud, response to a campaign, etc. So, decision tree rules are used to predict an outcome.

Association rule learning is an unsupervised approach where the algorithm tries to find associations among items, often within large commercial databases. A typical example of a large commercial database is one containing transactions of retailers, such as customer purchase history on an e-commerce website. Items could be products purchased from stores, or movies watched on an online streaming platform. Association rule learning is all about how the purchase of one product is inducing the purchase of another product.

Secondly, decision trees are constructed based on some impurity/uncertainty metrics, e.g. information gain, Gini coefficient, or entropy, whereas association rules are derived based on support, confidence, and lift.

Thirdly, as decision tree is a "supervised" approach, its accuracy is measurable, whereas association rule learning is an "unsupervised" approach, and so its accuracy is subjective.