Text Classification Algorithms: A Survey

In plain words

Text classification means sorting documents into labels, such as spam or not spam, or a topic. This paper is a guided tour of the whole job. A computer cannot read raw text directly, so the text is first cleaned and turned into numbers. Those numbers can be large, so they are sometimes compressed. Then a classifier learns from labelled examples. Finally the result is scored with measures that say how good it is.

The authors go through each stage and list the common options, with the strengths and weak points of each. Classic methods such as naive Bayes, support vector machines and decision trees are covered next to neural networks. The paper does not test anything new. Its value is the map: which choice fits which situation, and which measure can mislead you.

TL;DR

A survey, not a method. It splits text classification into four stages: features, dimensionality reduction, classifiers and evaluation. For each stage it gives the common techniques and qualitative pros and cons, and it names the evaluation measures to use. It runs no experiments of its own, so there are no new benchmark numbers. The authors' companion repository holds Python example scripts for several of the classifiers.

Problem

Text data is unstructured and high-dimensional, so a classifier cannot use it directly. Common pre-processing is cheap, but some cheap classifiers then underperform, and expensive ones cost time and memory §1. Choosing a representation, a dimension reduction, a classifier and a metric all depend on the data set and the goal. The paper's stated aim is to make these choices comparable §1 §5.

The paper frames classification at four scopes: document, paragraph, sentence and sub-sentence §1.

Method

The paper's organising structure is a pipeline with four phases. The first phase converts text to a structured feature space. The second, optional phase reduces its dimension. The third phase trains a classifier. The fourth phase evaluates it §1 fig. 1. The survey covers each phase in turn, and the sections below follow the paper's order.

1. Text cleaning and feature extraction §2. Cleaning removes characters and words that carry no information §2.1. Features are either weighted-word representations, which count words, or word-embedding representations, which learn vectors from word context §2.2 §2.3 §2.4.

• Bag of words represents a document by word counts over a fixed vocabulary. It ignores order and grammar §2.3.
• TF-IDF multiplies the term frequency by the log of the inverse document frequency. Term weight is W(d, t) = TF(d, t) · log(N / df(t)), with N the corpus size and df(t) the count of documents containing t §2.3 eq. 1.
• Word embeddings listed in the paper are Word2Vec, GloVe and FastText, plus contextual representations §2.4 tab. 1.

2. Dimensionality reduction §3. Options listed are PCA, LDA, NMF, random projection, autoencoders and t-SNE §3.1–§3.6. The paper's comparison is that PCA is costly to compute, LDA needs labels and a set number of components, random projection is much faster but weak on small data sets, and autoencoders need a lot of data §6.

3. Classifiers §4. The survey covers the following, each with its own subsection:

• Rocchio, with a relevance-feedback view §4.1.
• Boosting and bagging, which combine weak learners §4.2 alg. 1 alg. 2.
• Logistic regression §4.3, naive Bayes §4.4, k-nearest neighbours §4.5.
• Support vector machines, including a string-subsequence kernel §4.6.
• Decision trees §4.7 and random forests §4.8.
• Conditional random fields §4.9.
• Deep models: DNN, RNN (GRU and LSTM), CNN, attention networks, deep belief networks, and the authors' HDLTex and RMDL §4.10. Semi-supervised learning is covered briefly §4.11.

4. Evaluation §5. The paper defines accuracy, sensitivity, specificity, precision, recall and F1 from the confusion matrix §5. It then covers macro and micro averaging, F-beta §5, the Matthews correlation coefficient §5, ROC and TPR/FPR §5, and AUC, including a multi-class average §5. It warns that accuracy is misleading on imbalanced data §1 §6.

Pseudocode, pipeline §1 fig. 1. A sketch of the four phases, written for implementation. The paper does not give this as an algorithm, so the step names are our own.

# Text classification pipeline  [§1] [fig. 1]
# Input:  documents with labels, one label per document
# Output: predicted labels for the test documents

def classify_documents(train_docs, train_labels, test_docs):
    # 1. Clean the raw text  [§2.1]
    train_clean = clean(train_docs)
    test_clean = clean(test_docs)
    # 2. Turn each document into a numeric vector  [§2.2] [§2.3] [§2.4]
    train_features = vectorize(train_clean)
    test_features = vectorize(test_clean)
    # 3. Optionally reduce the number of features  [§3]
    train_features = reduce_dimension(train_features)
    test_features = reduce_dimension(test_features)
    # 4. Fit a classifier on the training data  [§4]
    model = fit_classifier(train_features, train_labels)
    # 5. Predict the test labels; score them with the metrics in [§5]
    return model.predict(test_features)

TF-IDF weight §2.3 eq. 1. A direct transcription of the paper's formula. Words that appear in many documents get a low weight.

# TF-IDF weight of term t in document d  [§2.3] [eq. 1]
# term_count: occurrences of t in d
# document_frequency: documents that contain t
# num_documents: N, the size of the corpus
def tfidf_weight(term_count, document_frequency, num_documents):
    # W(d, t) = TF(d, t) * log(N / df(t))  [eq. 1]
    return term_count * log(num_documents / document_frequency)

AdaBoost as the paper writes it alg. 1 §4.2. The paper's algorithm has a mix of conventions. The pitfalls section lists them. Implement from the source papers, not from this sketch.

# AdaBoost, as the paper writes it  [alg. 1]
# Input:  training set S of size m, inducer tau, number of rounds N
# Output: combined classifier C*

def adaboost(training_set, inducer, num_rounds):
    # Start with uniform instance weights  [alg. 1] [§4.2]
    weights = uniform_weights(training_set)
    for i in 1 to num_rounds:
        # Train a base classifier on the weighted sample  [alg. 1]
        base_classifier = inducer(weighted_sample(training_set, weights))
        # Weighted error of this round, normalised by 1/m  [alg. 1]
        epsilon = misclassified_weight_sum(base_classifier) / m
        # Error above 1/2: redraw the sample and restart the round  [alg. 1]
        if epsilon > 1 / 2:
            weights = reset_weights_to_one(training_set)
            continue
        # Shrink the weight of correctly classified instances  [alg. 1]
        beta = epsilon / (1 - epsilon)
        weights = multiply_correct_by(weights, beta)
        weights = normalise(weights)
    # Final vote, each classifier weighted by log(1 / beta_i)  [alg. 1]
    return weighted_vote(base_classifiers, betas)

Hyperparameters

The paper states hyperparameters only for the HDLTex deep models §4.10. For the other methods it gives none. The rows from the repository are example scripts, not paper settings; they are marked as such.

Results

No experiments are reported in this paper. Numbers are not stated for any method. The comparison tables list, for each cited method, the corpus, the validation measure and the limitation, without scores tab. 4 tab. 5.

• Validation measures named in the tables are F1-macro, F1-micro, accuracy, error rate and relative error tab. 4 tab. 5.
• Corpora named in the tables include Reuters-21578, 20 Newsgroups, RCV1-v2, Wikipedia, Yelp, IMDB, Amazon reviews and Web of Science tab. 4 tab. 5.

For headline numbers, read the original papers that these tables cite.

Paper vs code

The repository (kk7nc/Text_Classification, MIT) is linked by the paper itself. Its owner, kk7nc, matches first author Kamran Kowsari's initials, and the paper's author-contribution note says the authors wrote its sample code README.rst. Its scripts show the workflow in the paper, but they are not a reproduction of the survey's results and not an implementation of the HDLTex model.

• DNN size. The paper gives 8 hidden layers × 1024 units for the HDLTex DNN §4.10. The example DNN script has 4 hidden layers × 512 units DNN.py. The script is not HDLTex.
• HDLTex code is absent. The code/HDLTex folder contains only a README README.rst. The HDLTex numbers in §4.10 cannot be checked against code in the repository.
• RNN size. The paper gives 100 cells for the HDLTex RNN §4.10. The example RNN script uses 256 units RNN.py.
• Feature weighting. The paper's TF-IDF formula §2.3 eq. 1 has no smoothing or normalisation term. The example scripts call scikit-learn's TfidfVectorizer with default arguments DNN.py. These are not the same formula unless the library defaults are checked. We did not check them.
• The DNN example never trains. The script builds the model, prints its summary and calls exit(1) before fit DNN.py. As written, it does not train.
• Boosting. The repository has code/Boost.py. We did not compare its steps with alg. 1.

No discrepancies were checked for the survey's own tables, because those tables have no code.

Pitfalls

• MCC range. The text says MCC "ranges from −1 to 0", with −1 meaning always wrong and 0 meaning always right §5. The formula the paper gives §5 yields a value of 1 when there are no false positives or false negatives, so the stated range is inconsistent with the formula. Do not rely on the range sentence. Check the formula itself.
• Micro-average equation. The micro-averaged equation is labelled B_macro §5. This looks like a typo for B_micro; the summed-counts definition is the micro-average.
• Two AdaBoost conventions in one place. The weight update in §4.2 uses exponentials of ±α with α = ½ ln((1−ε)/ε). The algorithm alg. 1 instead scales correct weights by β = ε/(1−ε), and normalises ε by 1/m while the weights themselves are normalised to sum to one. These do not produce the same updates. The paper does not say which one to implement; the source papers do.
• Bootstrap restart in AdaBoost. alg. 1 redraws a bootstrap sample when ε > 1/2 and sets all weights to 1. The paper does not say how many times a round may restart, or how the reset interacts with the weighted vote.
• Unsupported claim about TF-IDF. The paper says the first TF-IDF term improves recall and the second improves precision, citing a source §2.3. We found no supporting result in the paper itself.
• Accuracy. The paper says accuracy is unsuitable for imbalanced data and that precision and recall are the common choice §1 §5. It does not give a threshold or a worked case.
• No experiments. Nothing here shows which method wins on which data. A claim such as "SVM is the most efficient" §6 is a summary of cited work, not a result of this paper.
• Word-embedding limits. The paper notes that pre-trained GloVe is trained on Wikipedia and can underperform TF-IDF on short messages §1 §6. This is qualitative and not measured here.

Lineage

• Builds on: nothing specific is stated; the survey cites the classical work for each technique it covers §2–§5.
• Compared against: the survey's own comparison tables list the methods of Rocchio, boosting, bagging, logistic regression, naive Bayes, KNN, SVM, decision trees, random forests, CRF, HAN, DBN, character-level CNN, RMDL and HDLTex tab. 2–tab. 5.
• Superseded by: not stated.