A re-examination of text categorization methods

Yiming YangXin Liu

article1999SIGIR3,120 citations

Evaluates five prominent text categorization algorithms on the Reuters-21578 benchmark using statistical significance tests, showing that SVM, kNN, and LLSF substantially outperform Naive Bayes and neural networks on rare classes in skewed data distributions.

Listen

This paper presents a controlled comparison of five established text categorization methods on a standard benchmark collection, addressing longstanding difficulties in evaluating their relative strengths when category frequencies are highly uneven. The work was motivated by inconsistent prior results across different data sets, varying performance measures, and limited analysis of how methods handle rare versus common categories, all of which made it hard to determine which approaches are reliably superior in realistic conditions.

The authors evaluated Support Vector Machines, k-nearest neighbor, Linear Least-squares Fit, neural networks, and Naive Bayes on the Reuters-21578 corpus after standard preprocessing, using both micro-averaged and macro-averaged F1 scores together with multiple statistical significance tests applied at the level of individual decisions and per-category performance. They examined performance explicitly as a function of the number of positive training examples per category and reported results across the full set of 90 categories rather than selected subsets.

The clearest findings are that SVM, kNN, and LLSF form a statistically stronger group than neural networks or Naive Bayes when categories have fewer than about ten training examples, that all five methods become statistically comparable once categories exceed roughly three hundred training examples, and that micro-level tests (dominated by frequent categories) rank SVM and kNN highest while macro-level tests confirm the three stronger methods outperform the other two on rare categories. Naive Bayes consistently ranked lowest across measures, and simplified thresholding strategies for kNN produced noticeably weaker results than category-specific threshold optimization.

These outcomes indicate that method selection has the greatest practical impact on the many low-frequency categories typical of real document collections, and that joint use of micro- and macro-level significance tests yields more trustworthy comparisons than any single aggregate score. Organizations building or maintaining large-scale categorization systems should therefore prefer SVM, kNN, or LLSF when training data for some topics will remain sparse, while continuing to monitor performance separately on rare and common categories.

The study is limited to one English-language news corpus and to particular implementations of each method; results could shift with different feature-selection regimes or non-linear SVM kernels. Readers should treat the reported rankings as reliable for similar newswire tasks but would benefit from repeating the significance tests on their own collections before final deployment decisions.

Cover for A re-examination of text categorization methods

Abstract

This paper reports a controlled study with statistical significance tests on five text categorization methods: the Support Vector Machines (SVM), a k-Nearest Neighbor (kNN) classifier, a neural network (NNet) approach, the Linear Least-squares Fit (LLSF) mapping and a Naive Bayes (NB) classifier. We focus on the robustness of these methods in dealing with a skewed category distribution, and their performance as function of the training-set category frequency. Our results show that SVM, kNN and LLSF significantly outperform NNet and NB when the number of positive training instances per category are small (less than ten), and that all the methods perform comparably when the categories are sufficiently common (over 300 instances).

Table of Contents

  • A re-examination of text categorization methods
  • 1 Introduction
  • 2 Task, Corpus and Performance Measures
  • 3 Classifiers
  • 3.1 SVM
  • 3.2 kNN
  • 3.3 LLSF
  • 3.4 NNet
  • 3.5 NB
  • 4 Significance Tests
  • 4.1 Micro sign test (s-test)
  • 4.2 Macro sign test (S-test)
  • 4.3 Macro t-test (T-test)
  • 4.4 Macro t-test after rank transformation
  • 4.5 Comparing proportions (p-test)
  • 5 Evaluation
  • 5.1 Experiments set up
  • 5.2 Results
  • 5.3 Cross-classifier Comparison
  • 6 Conclusions

Knowls

  1. Knowl 1 — Global Performance Benchmark of Five Text Categorizers on Reuters-21578

    data/table

    A controlled comparison of five text categorization algorithms—Support Vector Machines (SVM), kk-Nearest Neighbor (kNNk\text{NN}), Linear Least-squares Fit (LLSF), Neural Networks (NNet), and Naive Bayes (NB)—was evaluated on the ApteMod split of the Reuters-21578 corpus. The dataset consists of 90 categories (each with at least one training and one test example), 7,769 training documents, 3,019 test documents, and 24,240 unique terms after stemming and stop-word removal.

    Performance is evaluated using micro-averaged recall (miR\text{miR}), micro-averaged precision (miP\text{miP}), micro-averaged F1F_1 (miF1\text{miF}_1), macro-averaged F1F_1 (maF1\text{maF}_1), and error rate (error\text{error}):

    Method miR miP miF1 maF1 error
    SVM .8120 .9137 .8599 .5251 .00365
    kNN .8339 .8807 .8567 .5242 .00385
    LLSF .8507 .8489 .8498 .5008 .00414
    NNet .7842 .8785 .8287 .3765 .00447
    NB .7688 .8245 .7956 .3886 .00544

    SVM, kNNk\text{NN}, and LLSF form a high-performing top tier, achieving miF10.8498\text{miF}_1 \ge 0.8498 and maF10.5008\text{maF}_1 \ge 0.5008, while NNet and NB achieve lower scores, with their performance dropping significantly on macro-averaged F1F_1 due to poor performance on rare categories.

  2. Knowl 2 — Statistical Significance Framework for Text Categorization Systems

    model/method

    To evaluate whether differences between text categorization systems AA and BB are statistically significant across both global decisions and per-category performance, a battery of five significance tests is used:

    1. Micro sign test (ss-test): Evaluates pooled binary decisions over all N=ntest×mN = n_{\text{test}} \times m document-category pairs. Let ai,bi{0,1}a_i, b_i \in \{0, 1\} denote the success of systems AA and BB on the ii-th decision. Let nn be the number of discordant decisions (aibia_i \ne b_i) and kk be the number of times ai>bia_i > b_i. Under the null hypothesis H0:kBin(n,0.5)H_0: k \sim \text{Bin}(n, 0.5), the one-sided PP-value for n>12n > 12 is computed via the standard normal approximation: Z=k0.5n0.5nZ = \frac{k - 0.5n}{0.5\sqrt{n}}

    2. Macro sign test (SS-test): A sign test applied to paired category-level F1F_1 scores aj,bj[0,1]a_j, b_j \in [0, 1] across MM unique categories, using the same binomial test formulation as the ss-test based on the number of categories where aj>bja_j > b_j versus aj<bja_j < b_j.

    3. Macro paired tt-test (TT-test): Applied to the paired category differences dj=ajbjd_j = a_j - b_j for category F1F_1 scores. The test statistic is: T=dˉs.e.(dˉ)T = \frac{\bar{d}}{\text{s.e.}(\bar{d})} where dˉ\bar{d} is the sample mean of djd_j and s.e.(dˉ)\text{s.e.}(\bar{d}) is its standard error, evaluated with n1n-1 degrees of freedom when n40n \le 40, or the standard normal distribution otherwise.

    4. Macro rank-transformed tt-test (TT'-test): Category F1F_1 scores from both systems are pooled, sorted, and replaced by ranks aja_j' and bjb_j'. The paired difference test is then applied to dj=ajbjd_j' = a_j' - b_j': T=dˉs.e.(dˉ)T' = \frac{\bar{d}'}{\text{s.e.}(\bar{d}')} This test provides robustness against extreme F1F_1 outliers in rare categories while remaining sensitive to score ordering.

    5. Micro proportion test (pp-test): Compares performance proportions pap_a and pbp_b (such as micro-averaged recall, precision, or error) based on sample sizes nan_a and nbn_b (e.g., number of true positive instances for recall, number of positive assignments for precision, or N=ntest×mN = n_{\text{test}} \times m for error): Z=papbp^(1p^)(1/na+1/nb),p^=napa+nbpbna+nbZ = \frac{p_a - p_b}{\sqrt{\hat{p}(1-\hat{p})(1/n_a + 1/n_b)}}, \quad \hat{p} = \frac{n_a p_a + n_b p_b}{n_a + n_b}

  3. Knowl 3 — Cross-Classifier Statistical Significance Orderings and Metric Divergence

    data/table

    Statistical significance tests on the Reuters-21578 corpus show that classifier rankings depend on whether the evaluation is performed at the micro level (dominated by frequent categories) or the macro level (giving equal weight to rare categories).

    System A System B ss-test SS-test TT-test TT'-test
    SVM kNN >> \sim \sim \sim
    SVM LLSF \gg \sim \sim \sim
    kNN LLSF \gg \sim \sim \sim
    SVM NNet \gg \gg \gg \gg
    kNN NNet \gg \gg \gg \gg
    LLSF NNet \sim \gg \gg \gg
    NB kNN \ll \ll \ll \ll
    NB LLSF \ll \ll \ll \ll
    NB SVM \ll \ll \ll \ll
    NB NNet \ll \sim \sim \sim

    *Note: \gg or \ll indicates P0.01P \le 0.01; >> or << indicates 0.01<P0.050.01 < P \le 0.05; \sim indicates P>0.05P > 0.05.

    System A System B miR (pp-test) miP (pp-test) error (pp-test)
    SVM kNN \ll \gg >>
    SVM LLSF \ll \gg \gg
    kNN LLSF << \gg <<
    SVM NNet \gg \gg \gg
    kNN NNet \gg \sim \gg
    LLSF NNet \gg \ll <<
    NB kNN \ll \ll \ll
    NB LLSF \ll \ll \ll
    NB SVM \ll \ll \ll
    NB NNet \sim \ll \ll

    The resulting system orderings are:

    • Micro sign test (ss-test): SVM>kNN{LLSF,NNet}NB\text{SVM} > k\text{NN} \gg \{\text{LLSF}, \text{NNet}\} \gg \text{NB}
    • Error-based proportion test (pp-test): {SVM,kNN}>LLSF>NNetNB\{\text{SVM}, k\text{NN}\} > \text{LLSF} > \text{NNet} \gg \text{NB}
    • Macro F1F_1 tests (SS-test, TT-test, TT'-test): {SVM,kNN,LLSF}{NNet,NB}\{\text{SVM}, k\text{NN}, \text{LLSF}\} \gg \{\text{NNet}, \text{NB}\}

    LLSF and NNet perform similarly on pooled decisions, but LLSF significantly outperforms NNet when rare categories are evaluated individually via macro tests.

  4. Knowl 4 — Impact of Training-Set Category Frequency on Classifier Robustness

    empirical result

    When evaluating text categorization methods across category training frequencies on Reuters-21578, classifier performance depends strongly on category rarity:

    • Rare Categories (11 to 6060 training instances, representing 67%67\% of categories; and 10\le 10 instances, representing 33%33\% of categories): SVM, kNNk\text{NN}, and LLSF achieve high macro-F1F_1 scores (0.500.50 to 0.530.53), maintaining stable performance even with fewer than 10 training instances. In contrast, NNet and NB experience severe performance degradation, achieving macro-F1F_1 scores of only 0.37650.3765 and 0.38860.3886, respectively.
    • Common Categories (>300> 300 training instances): All five classifiers converge to comparable performance levels (macro-F1F_1 values between 0.800.80 and 0.900.90).

    The overall performance gap separating SVM, kNNk\text{NN}, and LLSF from NNet and NB is driven almost entirely by the inability of NNet and NB to generalize effectively on rare categories in skewed distributions.

  5. Knowl 5 — Category-Specific Validation Thresholding in k-Nearest Neighbor Categorization

    model/method

    The kk-Nearest Neighbor (kNNk\text{NN}) classification model computes the likelihood score of category cjc_j for an input test document x\vec{x} as: y(x,cj)=dikNN(x)sim(x,di)y(di,cj)bjy(\vec{x}, c_j) = \sum_{\vec{d}_i \in k\text{NN}(\vec{x})} \text{sim}(\vec{x}, \vec{d}_i) y(\vec{d}_i, c_j) - b_j where kNN(x)k\text{NN}(\vec{x}) is the set of the kk most similar training documents to x\vec{x} using cosine similarity sim(x,di)=xdixdi\text{sim}(\vec{x}, \vec{d}_i) = \frac{\vec{x} \cdot \vec{d}_i}{\|\vec{x}\| \|\vec{d}_i\|}, y(di,cj){0,1}y(\vec{d}_i, c_j) \in \{0, 1\} indicates whether training document di\vec{d}_i belongs to category cjc_j, and bjb_j is a category-specific decision threshold. Category cjc_j is assigned to document x\vec{x} if y(x,cj)0y(\vec{x}, c_j) \ge 0.

    The optimal threshold bjb_j is learned automatically for each category using a validation subset of the training set to maximize the category's F1F_1 score. This per-category thresholding mechanism allows multiple categories to be assigned to a single document. Under this scheme with k=45k=45, kNNk\text{NN} achieves a micro-F1F_1 of 0.85670.8567 on Reuters-21578, compared to only 0.81400.8140 when using a simplified single-label heuristic that assigns only the highest-scoring category per document.

  6. Knowl 6 — Linear Least Squares Fit (LLSF) Mapping for Text Categorization

    model/method

    The Linear Least Squares Fit (LLSF) method formulates multi-label text categorization as a multivariate linear regression problem. Let ARV×NtrainA \in \mathbb{R}^{V \times N_{\text{train}}} represent the training document-term matrix (where VV is vocabulary size and NtrainN_{\text{train}} is the number of training documents) and let B{0,1}M×NtrainB \in \{0, 1\}^{M \times N_{\text{train}}} represent the binary category assignment matrix across MM categories.

    The word-category regression coefficient matrix FLSRM×VF_{LS} \in \mathbb{R}^{M \times V} is computed by solving the linear least-squares problem: FLS=argminFFAB2F_{LS} = \arg\min_F \|FA - B\|^2

    The optimization is solved using Singular Value Decomposition (SVD), retaining 500 singular values. To classify a new document vector x\vec{x}, the system computes the category weight vector y=FLSx\vec{y} = F_{LS} \vec{x}, producing a score yjy_j for each category cjc_j. Category cjc_j is assigned if yjbjy_j \ge b_j, where the threshold bjb_j is tuned on a validation subset of the training set to maximize the category-specific F1F_1 score.

  7. Knowl 7 — Single Multi-Class Neural Network Architecture for Multi-Label Text Categorization

    model/method

    To address the computational cost of training 90 separate binary neural networks for text categorization on Reuters-21578, a single three-layer feedforward neural network is trained simultaneously across all 90 categories.

    The input layer receives sparse document feature vectors over 1,000 statistical features selected by χ2\chi^2 or information gain. The intermediate hidden layer contains 64 units (selected empirically over candidate layer sizes of 16, 64, and 160 on a validation set), and the output layer contains 90 units corresponding to category assignments. While this architecture achieves a micro-F1F_1 of 0.82870.8287, its macro-F1F_1 drops to 0.37650.3765, performing poorly on rare categories compared to instance-based and linear mapping methods.

  8. Knowl 8 — Performance and Metric Clarification for Naive Bayes Text Classifiers

    empirical result

    Evaluating Naive Bayes (NB) on the full 90 categories of Reuters-21578 reveals two key findings:

    1. Multinomial vs. Multivariate Bernoulli Model: The multinomial mixture model of Naive Bayes achieves a micro-F1F_1 of 0.79560.7956, outperforming the multivariate Bernoulli model (which achieved a micro-F1F_1 of 0.7200.720). However, even the multinomial model remains statistically significantly inferior (P0.01P \le 0.01) to SVM (0.85990.8599), kNNk\text{NN} (0.85670.8567), and LLSF (0.84980.8498).

    2. Evaluation Metric Inconsistency: Previous evaluations reporting high "accuracy" for Naive Bayes used a non-standard metric defined as the proportion of correct assignments when restricting each document to exactly one category ({1n}\{1\dots n\} assignments across nn test documents). This metric is equivalent to precision under a single-label assumption, but it fails on multi-label datasets where documents have multiple categories (average 1.31.3 categories per document in Reuters-21578). Under standard multi-label TC accuracy and F1F_1 metrics, Naive Bayes ranks lowest among all evaluated methods.

Coverage note — Standard background formulations of Support Vector Machines (Vapnik's soft-margin optimization), standard definitions of information gain and chi-square feature selection formulas, and raw dataset preparation tokenization steps were omitted as they represent standard foundational literature rather than the paper's original contributions.

References

  1. 1.C. Apte, F. Damerau, and S. Weiss. Towards language independent automated learning of text categorization models. In Proceedings of the 17th Annual ACM/SIGIR conference, 1994.
  2. 2.C. Apte, F. Damerau, and S. Weiss. Text mining with decision rules and decision trees. In Proceedings of the Conference on Automated Learning and Discovery, Workshop 6: Learning from Text and the Web, 1998.
  3. 3.L. Douglas Baker and Andrew K. Mccallum. Distributional clustering of words for text categorization. In Proceedings of the 21th Ann Int ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'98), pages 96-103, 1998.
  4. 4.D. Berry and B.W. Lindgren. Statistics: Theory and Methods. Brooks/Cole, Pacific Grove, California, 1990.
  5. 5.William W. Cohen. Text categorization and relational learning. In The Twelfth International Conference on Machine Learning (ICML'95). Morgan Kaufmann, 1995.
  6. 6.William W. Cohen and Yoram Singer. Context-sensitive learning methods for text categorization. In SIGIR '96: Proceedings of the 19th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 1996. 307-315.
  7. 7.C. Cortes and V. Vapnik. Support vector networks. Machine Learning, 20:273-297, 1995.
  8. 8.Belur V. Dasarathy. Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques. McGraw-Hill Computer Science Series. IEEE Computer Society Press, Las Alamitos, California, 1991.
  9. 9.N. Fuhr, S. Hartmanna, G. Lustig, M. Schwantner, and K. Tzeras. Air/x - a rule-based multistage indexing systems for large subject fields. In 606-623, editor, Proceedings of RIAO'91, 1991.
  10. 10.P.J. Hayes and S. P. Weinstein. Construe/tis: a system for content-based indexing of a database of news stories. In Second Annual Conference on Innovative Applications of Artificial Intelligence, 1990.
  11. 11.Makato Iwayama and Takenobu Tokunaga. Cluster-based text categorization: a comparison of category search strategies. In Proceedings of the 18th Ann Int ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'95), pages 273-281, 1995.
  12. 12.Thorsten Joachims. Text Categorization with Support Vector Machines: Learning with Many Relevant Features. In European Conference on Machine Learning (ECML), 1998.
  13. 13.D. Koller and M. Sahami. Hierarchically classifying documents using very few words. In The Fourteenth International Conference on Machine Learning (ICML'97), pages 170-178, 1997.
  14. 14.W. Lam and C.Y. Ho. Using a generalized instance set for automatic text categorization. In Proceedings of the 21th Ann Int ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'98), pages 81-89, 1998.
  15. 15.David D. Lewis, Robert E. Schapire, James P. Callan, and Ron Papka. Training algorithms for linear text classifiers. In SIGIR '96: Proceedings of the 19th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 1996. 298-306.
  16. 16.D.D. Lewis and M. Ringuette. Comparison of two learning algorithms for text categorization. In Proceedings of the Third Annual Symposium on Document Analysis and Information Retrieval (SDAIR'94), 1994.
  17. 17.B. Masand, G. Linoff, and D. Waltz. Classifying news stories using memory based reasoning. In 15th Ann Int ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'92), pages 59-64, 1992.
  18. 18.A. McCallum and K. Nigam. A comparison of event models for naive bayes text classification. In AAAI-98 Workshop on Learning for Text Categorization, 1998.
  19. 19.Tom Mitchell. Machine Learning. McGraw Hill, 1996.
  20. 20.I. Moulinier. Is learning bias an issue on the text categorization problem? In Technical report, LAFORIA-LIP6, Universite Paris VI, 1997.
  21. 21.I. Moulinier, G. Raskinis, and J. Ganascia. Text categorization: a symbolic approach. In Proceedings of the Fifth Annual Symposium on Document Analysis and Information Retrieval, 1996.
  22. 22.H.T. Ng, W.B. Goh, and K.L. Low. Feature selection, perceptron learning, and a usability case study for text categorization. In 20th Ann Int ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'97), pages 67-73, 1997.
  23. 23.Osuna, R. Freund, and F. Girosi. Support vector machines: Training and applications. In A.I. Memo. MIT A.I. Lab, 1996.
  24. 24.J. Platt. Sequential minimal optimization: A fast algorithm for training support vector machines. In Technical Report MST-TR-98-14. Microsoft Research, 1998.
  25. 25.K. Tzeras and S. Hartman. Automatic indexing based on bayesian inference networks. In Proc 16th Ann Int ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'93), pages 22-34, 1993.
  26. 26.C.J. van Rijsbergen. Information Retrieval. Butterworths, London, 1979.
  27. 27.V. Vapnik. The Nature of Statistical Learning Theory. Springer, New York, 1995.
  28. 28.E. Wiener, J.O. Pedersen, and A.S. Weigend. A neural network approach to topic spotting. In Proceedings of the Fourth Annual Symposium on Document Analysis and Information Retrieval (SDAIR'95), 1995.
  29. 29.Y. Yang. Expert network: Effective and efficient learning from human decisions in text categorization and retrieval. In 17th Ann Int ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'94), pages 13-22, 1994.
  30. 30.Y. Yang. Sampling strategies and learning efficiency in text categorization. In AAAI Spring Symposium on Machine Learning in Information Access, pages 88-95, 1996.
  31. 31.Y. Yang. An evaluation of statistical approaches to text categorization. Journal of Information Retrieval (to appear), 1999.
  32. 32.Y. Yang and C.G. Chute. An example-based mapping method for text categorization and retrieval. ACM Transaction on Information Systems (TOIS), 12(3):252-277, 1994.
  33. 33.Y. Yang and J.P. Pedersen. Feature selection in statistical learning of text categorization. In The Fourteenth International Conference on Machine Learning, pages 412-420, 1997.

Citation

MLA
Yang, Y., and X. Liu. “A Re-examination of Text Categorization Methods”. Proceedings of the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 1999, pp. 42–49, https://doi.org/10.1145/312624.312647.
APA
Yang, Y., & Liu, X. (1999). A re-examination of text categorization methods. Proceedings of the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 42–49. https://doi.org/10.1145/312624.312647
Chicago
Yang, Y., and X. Liu. 1999. “A Re-examination of Text Categorization Methods”. Proceedings of the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 42–49. https://doi.org/10.1145/312624.312647.
Harvard
Yang, Y. and Liu, X. (1999) “A re-examination of text categorization methods”, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval. ACM, pp. 42–49. Available at: https://doi.org/10.1145/312624.312647.
Vancouver
1. Yang Y, Liu X (1999) A re-examination of text categorization methods. In: Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval. ACM, pp 42–49

BibTeX

@inproceedings{Yang_1999, series={SIGIR99}, title={A re-examination of text categorization methods}, url={http://dx.doi.org/10.1145/312624.312647}, DOI={10.1145/312624.312647}, booktitle={Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval}, publisher={ACM}, author={Yang, Yiming and Liu, Xin}, year={1999}, month=Aug, pages={42–49}, collection={SIGIR99} }
Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF