A scalability analysis of classifiers in text categorization

Real-world applications of text categorization often require a system to deal with tens of thousands of categories de-fined over a large taxonomy. This paper addresses the prob-lem with respect to a set of popular algorithms in text cat-egorization, including Support Vector Machines, k-nearest neighbor, ridge regression, linear least square fit and logistic regression. By providing a formal analysis of the compu-tational complexity of each classification method, followed by an investigation on the usage of different classifiers in a hierarchical setting of categorization, we show how the scalability of a method depends on the topology of the hi-erarchy and the category distributions. In addition, we are able to obtain tight bounds for the complexities by using the power law to approximate category distributions over a hi-erarchy. Experiments with kNN and SVM classifiers on the OHSUMED corpus are reported on, as concrete examples.