[Download postscript version]

ID3

ID3[Qui86] is used to build the decision tree to use as a classifier. But it is possible to use it to find the association rules. A path from the root to the leaf of the tree can be considered as a associated rules. And since in each node (say node $k$) of the decision tree, the number of positive tuples and negative tuples are stored. We can compute the support for the rule got from rule to the current node $k$. The problem with this method is that it may not find all of the association rules. We need to build a decision tree with generalized items. Building a generalized decision tree will be very interesting since we expect it will be better than the classical decision in that it may be more robust to noise. So we can avoid the overfitting problem and save the expensive prune stage.