A new measure of classifiability and its applications.

摘要

Characterizing the difficulty of a pattern classification problem is an open and challenging problem in machine learning. While some progress has been made in understanding the difficulty of learning a concept (as in the PAC learning frame work), the more pertinent and challenging problem of characterizing the difficulty of a problem given a specific and finite sample has not been addressed.; In this dissertation we develop a new measure of classifiability, motivated in part by the fact that a n-dimensional classification problem may be visualized in (n + 1) dimensions using the class label as the (n + 1)th dimension. In such a visualization, the class label provides a surface which is smooth in regions where classes are non-interlaced and rough in regions where classes are interlaced. The texture of the “class label surface” thus provides an intuitive measure of pattern classifiability. We establish Bayes-sense optimality of the proposed measure of classifiability and present some experimental results based on a simple algorithm to compute the proposed classifiability measure.; The new classifiability measure can be used broadly in solving classification problems since it not only considers the number of pattern instances of different classes (purity) at current situation, but also the spatial distribution of these instances to estimate the effect of further classification. In this dissertation, we develop new approaches for crisp and fuzzy decision tree induction, decision pre-pruning as well as feature subset selection based on the classifiability measure. The proposed algorithms outperform existing algorithms on several standard testing datasets as well as on a real world problem: evaluating skin condition.