A Characterization of Difficult Problems in Classification.
Ricardo Vilalta, Youssef Drissi · 2002
Most classification algorithms experience difficulties when the input-output distribution is irregular (i.e., neighbor examples in the input space have different values in the output space), and sparse. We characterize the difficulty of a classification problem using a limited number of examples by re-defining a measure of class variation to account for irregular distributions, and by introducing a new measure of example cohesiveness in the input space to account for (lack of) sparseness. Our empirical study indicates these measures correlate with accuracy performance.