Announcing the Final Examination of Mr. Mingyu Zhong for the degree of Doctor of Electrical Engineering

An Analysis of Misclassification Rates for Decision Tree Classifiers

Mr. Mingyu Zhong
Wednesday, July 11, 2007
3:00PM - HCEC 450

Abstract


The decision tree is a well-known methodology for classification and regression. In this paper, we focus on the minimization of the misclassification rate for decision tree classifiers. We derive the necessary equations that provide the optimal tree prediction, the estimated risk of the tree's prediction, and the reliability of the tree's risk estimation. We carry out an extensive analysis of the application of Lidstone's Law of Succession for the estimation of the class probabilities. In contrast to existing research, we not only compute the expected values of the risks but also calculate the corresponding reliability of the risk (measured by variances). We also provide an explicit expression of the k-norm estimation for the tree's misclassification rate that combines both the expected value and the reliability. Furthermore, our proposed and proven theorem on k-norm estimation suggests an efficient pruning algorithm that has a clear theoretical interpretation, is easily implemented, and does not require a validation set. Our experiments show that our proposed pruning algorithm produces accurate trees quickly that compares very favorably with two other prominent pruning algorithms, CCP of CART and EBP of C4.5. Finally, our work provides a deeper understanding of decision trees.

Outline of Studies

  • Major: Electrical Engineering
  • Educational Career:
    • B.A., 2002, Tsinghua University, Beijing, China
    • M.S., 2005, University of Central Florida
  • Committee in Charge:
    • Dr. Michael Georgiopoulos
    • Dr. Georgios C. Anagnostopoulos
    • Dr. Annie S. Wu
    • Dr. Ronald F. DeMara
    • Dr. Avelino J. Gonzalez