6
$\begingroup$

In Ross Quinlan's seminal paper Induction of Decision Trees, Quinlan summarizes the current state of machine learning in 1985 and loudly introduces the ID3 decision algorithm in the context of its peers in the field. However, he also states this halfway into the paper:

An alternative method based on the chi-square test for stochastic independence has been found to be more useful.

And further in:

Hart notes, however, that the chi-square test is valid only when the expected values of $p' i$ and $n'i$ are uniformly larger than four. This condition could be violated by a set C of objects either when C is small or when few objects in C have a particular value of some attribute, and it is not clear how such sets would be handled. No empirical results with this approach are yet available.

The name for this modification of the algorithm is not given, though. Is there an accepted name for this modification of ID3 (which is usually dependent on Shannon entropy to perform branching)? It seems like something that should be obvious (eg, ID3.1.x), but I cannot find a formal source.

I've also taken the liberty of perusing and studying the meta links within the FAQ of this fine site, and this didn't seem to fall into any of the bins for obviousness or non-research level, nor did it appear to be a good fit for other StackExchange sites. It is, however, a simple question that I could not find the answer to in any of the common sources.

This is directly pertinent to my research: I'm compiling another optimization that bridges the gap between generalized Shannon mutual information and Pearson's chi-squared test for independence in the context of TDIDT, then applying it to multivariate characteristics in cancer data as an alternative to random forests. As such, working definitions for my terms are greatly useful, insofar as they might lead to further papers I am not familiar with.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Have you tried stats.stackexchange.com $\endgroup$
    – Suresh Venkat
    Nov 12, 2011 at 5:03
  • 2
    $\begingroup$ I'd considered it! However, the lack of discussion of ID3 there discouraged me. I have sent an email to J.R. Quinlan directly, though. If anyone knows, he should. $\endgroup$
    – MrGomez
    Nov 12, 2011 at 8:34

1 Answer 1

Reset to default
1
$\begingroup$

Unfortunately, I'm not able to get into detail of the ID3 paper you cited.

I read the Quinlan's book about C4.5 and I don't remember any quote about Chi-square splitting procedure. However, it exists a decision trees induction process that uses Chi-squares as splitting procedure, it is CHAID: http://en.wikipedia.org/wiki/CHAID.

By the way, do you really need a Chi-square splitting procedure? Good permances of C4.5 are well known, and it uses Information Gain as splitting criterion. Moreover, classical Data Mining books (such as Introduction to Data Mining by Tan et al.) state that better performances can be achieved with different pruning techniques rather than different splitting criteria.

If you really want a Chi-square splitting procedure I would suggest to use CHAID or modify the Java implementation of C4.5 in WEKA.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ To offer some additional detail: I am attempting to show convergence between a specific form of naive ensemble classifier with pruning and an algorithm analogous to CHAID, insofar as my observations have shown that the former simplifies to the latter. The procedure to do so is obvious to me, but it helps to better define my terms. To that end, thank you for your answer. -- I've also gotten in touch with Ross Quinlan directly. His reply indicates he has no special name for this modification of ID3; it had simply been a measure to prevent overfitting until he devised a suitable pruning stage. $\endgroup$
    – MrGomez
    Nov 14, 2011 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.