Estimating case base complexity using Fractal Dimension

This paper presents a novel measure of complexity of a case base. The concept of Fractal Dimensions, which is a generalization of the idea of dimensions, is used to estimate complexity. In terms of a classification problem, the idea of Fractal Dimension is used to estimate the ruggedness of the space spanned by instances along the decision boundary. Experiments over collections of varying complexity show that the measure exhibits strong negative correlation with classification accuracies over several classifiers. We also present empirical findings from experiments over non-textual datasets.