Classification Algorithms on Text Documents

Fall 2001

YANCONG ZHOU and HYUK CHO

---

Table of Contents

• Introduction
• Classification Algorithms
• Data Description
• Parameter Settings
• Experimental Results
• References
• Source Codes

---

Introduction

Brief overview of this project

In this project, we implement three well-known classification algorithms for text data, which are Naive Bayesian(NB) algorithm, K-Nearest Neighbor(KNN) algorithm, and Centroid-based(CB) algorithm. Also, we propose several new algorithms and compare their classification performance in the point of accuracy, precision, and recall classification measure. Therefore, we focus on evaluating the feasibility and performance of traditional classification algorithms and, if possible, want to propose new classification algorithms that lead to better classification performance.

We start our project with the following questions:

What do we need/do in the preprocessing step? Do we need to do feature selection for better performance in the accuracy and computational efficiency? How many training/testing data are needed for reasonable performance? Can we make use of the hierarchical structure of data set in classification? Can we improve accuracy by combining two or three classification algorithms?

[Back to Top]

---

Classification Algorithms

Brief overview of basic classification algorithms

The goal of classification is to build a set of models that can correctly predict the class of the different objects. The input to these methods is a set of objects (i.e., training data), the classes which these objects belong to (i.e., dependent variables), and a set of variables describing different characteristics of the objects (i.e., independent variables). Once such a predictive model is built, it can be used to predict the class of the objects for which class information is not known a priori. The key advantage of supervised learning methods over unsupervised methods (for example, clustering) is that by having an explicit knowledge of the classes the different objects belong to, these algorithms can perform an effective feature selection if that leads to better prediction accuracy. The followings are brief overview on some classification algorithms that has been used in data mining and machine learning area and used as base algorithms in this project.

1. k-Nearest Neighbor(KNN) Algorithm

KNN classifier is an instance-based learning algorithm that is based on a distance function for pairs of observations, such as the Euclidean distance or Cosine. In this classification paradigm, k nearest neighbors of a training data are computed first. Then the similarities of one sample from testing data to the k nearest neighbors are aggregated according to the class of the neighbors, and the testing sample is assigned to the most similar class. One of advantages of KNN is that it is well suited for multi-modal classes as its classification decision is based on a small neighborhood of similar objects (i.e., the major class). So, even if the target class is multi-modal (i.e., consists of objects whose independent variables have different characteristics for different subsets), it can still lead to good accuracy. A major drawback of the similarity measure used in KNN is that it uses all features equally in computing similarities. This can lead to poor similarity measures and classification errors, when only a small subset of the features is useful for classification.

2. Naive Bayesian(NB) Algorithm

NB algorithm has been widely used for document classification, and shown to produce very good performance. The basic idea is to use the joint probabilities of words and categories to estimate the probabilities of categories given a document. NB algorithm computes the posterior probability that the document belongs to different classes and assigns it to the class with the highest posterior probability. The posterior probability of class is computed using Bayes rule and the testing sample is assigned to the class with the highest posterior probability. The naive part of NB algorithm is the assumption of word independence that the conditional probability of a word given a category is assumed to be independent from the conditional probabilities of other words given that category. There are two versions of NB algorithm. One is the multi-variate Bernoulli event model that only takes into account the presence or absence of a particular term, so it doesn't capture the number of occurrence of each word. The other model is the multinomial model that captures the word frequency information in documents.

3. Concept Vector-based(CB) Algorithm

In CB classification algorithm, the length of each vector is normalized so that it is of unit length. The idea behind the concept-based classification is extremely simple. For each set of documents belonging to the same class, we compute its concept vector by summing up all vectors in the class and normalize it by its 2-norm. If there are c classes in the training data set, this leads to c concept vectors, where each concept vector for each class. The class of a new sample is determined as follow. First, for a given testing document, which was already normalized by 2-norm so that it has unit length, we compute cosine similarity between this given testing document to all k concept vectors. Then, based on these similarities, we assign a class label so that it corresponds to the most similar concept vector's label. One of the advantages of the CB classification algorithm is that it summarizes the characteristics of each class, in the form of concept vector. So, the advantage of the summarization performed by the concept vectors is that it combines multiple prevalent features together, even if these features are not simultaneously present in a single document. That is, if we look at the prominent dimensions of the concept vector (i.e., highest weight terms), these will correspond to words that appear frequently in the class, but no necessarily all in the same set of documents. This is particularly important for high dimensional and sparse data sets for which the coverage of any individual feature is often quite low.

Brief overview of classification algorithms that are implemented and tried in this project.

4. Singular Value Decomposition(SVD)-based Algorithm

Here we use first Singular Vectors as we use concept vectors for concept vector based algorithm For each class i of training documents in k nearest neighbors, compute first singular vector. Compute cosine similarity between a given testing document and every singular vector. Assign (i.e., classify) the testing document a class label which has largest cosine value.

5. Variation of Naive Bayesian Algorithm

The multinomial model of Naive Bayesian classification algorithm captures the word frequency information in document. So it requires the word frequency that is not weighted and normalized. However we also tried with tfn-scaled word frequency data. So, only one difference from the original multinomial model is that tfn-scaled word frequency is used instead of word frequency(i.e., txx).

6. Variations of KNN algorithm

KNN using average cosine Select k nearest training documents, where the similarity is measured by the cosine between a given testing document and a training document. Using cosine values of k nearest neighbors and frequency of documents of each class i in k nearest neighbors, compute average cosine value for each class i, Avg_Cosine(i). Assign (i.e., classify) the testing document a class label which has largest average cosine. KNN using combination1 This combines objective functions of both classical KNN and KNN using average cosine. Select k nearest training documents, where the similarity is measured by the cosine between a given testing document and a training document. Using cosine values of k nearest neighbors and frequency of documents of each class in k nearest neighbors, compute combined objective function for each class i as follows: Obj(i) = weight * Doc_Count(i) + Avg_Cosine(i), where Obj(i) is the objective value for class i,              weight is a real number ranging from 0 to 1,              Doc_Count(i) is the frequency of documents of class i in k nearest neighbors              and Avg_Cosine(i) is the average cosine value for class i as before. Assign (i.e., classify) the testing document a class label which has the largest objective value. KNN using combination2 We implement "kNN.avg1" based on the work given in [5]. Select k nearest training documents, where the similarity is measured by the cosine between a given testing document and a training document. Using cosine values of k nearest neighbors and frequency of documents of each class in k nearest neighbors, compute combined objective function for each class i as follows: Obj(i) = Pos_Avg_Cosine(i) - Neg_Avg_Cosine(i), where Pos_Avg_Cosine(i) (or Neg_Avg_Cosine(i)) is the average cosine value for the set of the positive (or negative) instances among the k nearest neighbors. Here the positive instances mean the documents (in k nearest neighbors) whose class label is i. So when computing objective value for class i, only class label i is considered positive and others are considered negative. Assign (i.e., classify) the testing document a class label which has the largest objective value.

7. Hierarchical algorithms

The idea is to make good use of hierarchical structure of data set in top-down manner. By utilizing known (or artificial) hierarchical structure, the classification problem can be decomposed into a set of smaller problems corresponding to hierarchical splits in tree structure. We first start testing the top level of tree to distinguish classes. After then, we repeatedly consider only the child (or children) of the appropriate parent that we selected at the parent's level (i.e., previous level). For implementing hierarchical classification algorithm, we need to preprocess a given hierarchical structure and use additional data structures in order keep tract of hierarchical information. Details of additional data structures are specified in Data Description section.

Hierarchical Concept Vector-based (H_CB) algorithm With training data, compute concept vectors for categories including bottom (i.e. leaf) level and intermediate parents' levels. Do the following from top-level to bottom-level Compute cosine between a given document and concept vectors at present level Select a class label that has the largest cosine. if the class label is not one of true labels (i.e., the selected class is intermediate class), then continue else assign this class label for the testing document and exit Hierarchical Naive Bayesian (H_NB) algorithm Algorithm is the same as that of H_CB except only one that computing probability vectors.

8. Combination algorithms

The idea is to reduce the dimensionality of VSM and keep useful information. So, we first compute concept vectors for given categories (or classified classes using clustering algorithm), then, using the concept vectors as projection matrix, do projection of both training and testing data. Finally, we apply KNN algorithm on the projected VSM model that has reduced dimensionality.

Concept Vector based algorithm + K-Nearest Neighbor algorithm (CB_KNN) Compute a concept vector for each category using true label information of training documents and then construct concept vector matrix C(w-by-c), where c is the number of categories. Do projection of VSM model A(w-by-d) using concept vector matrix C(w-by-c) (i.e., C^T * A ) Apply KNN with the projected VSM model (i.e., c-by-d matrix). Clustering + CB + K-Nearest Cluster algorithm (Cluster_CB_KNC) Do clustering on each class of training data with given number of clusters. Compute a concept vector for each cluster using cluster information (from step 1) and then construct concept vector matrix C(w-by-k), where k is the total number of clusters. Apply KNN to concept vector matrix C(w-by-k) and VSM model A(w-by-d matrix). So, the testing document is classified into the class to which the major nearest neighbor cluster belongs. Clustering + CB + KNN algorithm (Cluster_CB_KNN) Do clustering on each class of training data with given number of clusters. Compute a concept vector for each cluster using cluster information (from step 1) and then construct concept vector matrix C(w-by-k), where k is the total number of clusters. Do projection of VSM model A(w-by-d) using concept vector matrix C(w-by-k) (i.e., C^T * A ) Apply KNN to the projected VSM model (k-by-d matrix).

[Back to Top]

---

Data Description

We briefly describe the following two datasets used in this project and also specify the options with which we use to preprocess them using rainbow or mc.

1. 20 Newsgroup Data Set

20 newsgroup data can be obtained from CMU World Wide Knowledge Base (Web->KB) project. This consists of 20000 (actually 19997) messages from 20 newsgroups. 1000 messages are collected from each newsgroup. However some of the newsgroups have similar subject and 1169 messages are cross-posted (i.e., duplicated) to different newsgroups. So, we use the cleaned 20-newsgroup data from Jason Rennie's homepage. It has 18828 cleaned messages and still keeps the same hierarchical structure of 20-newsgroup data from CMU. From now on, if we don't explicitly specified, we use this cleaned data. Here is README for cleaned 20-newsgroup data. In order to maintain the hierarchical structure of data, we need the following additional data structures: (These are examplary data structures for original hierarchical structure.) level , specifying node (or nodes) of each level. path , specifying intermediate node (or nodes) in a path from one leaf to its parents. child , specifying child (or children) of each node. leaf , specifying leaf (or leaves) to which each node can reach. To generate data in CCS format, we use the following options for MC: -s english-articles -t tfn -m 3 -ln 2 -u 15 -w SGML

2. 4 Universities Data Set

4 Universities Data can be obtained from CMU World Wide Knowledge Base (Web->KB) project. It contains 8282 WWW-pages collected from four universities, Cornell (867), Texas (827), Washington (1205), Wisconsin (1263) and manually classified in seven categories, student (1641), faculty (1124), staff (137), department (182), course (930), project (504), other (3764). Here is README for 4 universities data. To generate data in CCS format, we use the following options for MC: First run Rainbow using following options --skip-headers, --skip-html --prune-vocab-by-occur-count=2 --prune-vocab-by-infogain=2000 Then, run rainbow_2_ccs to convert rainbow format to CCS format. Finally, run make_truelabel to generate a truelabel file based on *_docs file.

3. Rainbow and MC

Rainbow MC How to convert Rainbow format to MC format (i.e. CCS)? Here is README for converting Rainbow format to MC's CCS format.

[Back to Top]

---

Parameter Settings

Common parameter setting for every algorithm:

We select 80 % of training data for each category and the remaining documents (i.e. 20 % of each category) are used as testing data. So if it is not specified explicitly, we use 80% of training data. Remember that we randomly select training data according to the given percentage of training data, so every time we run programs with different training and testing data set. To get learning curves, we set the range of training size from 0.1 to 0.9.

1. k-Nearest Neighbor(KNN) Algorithm

We try to find the optimal number of nearest neighbors(i.e., k). It turns out by experiments optimal k is different on different (sub-)data sets, so we just select some k for the whole experiments which shows the performance good enough to compare. For KNN using combination 1, we specify real-valued weight that ranges from 0 to 1. We set 0.05 as a default weight.

2. Naive Bayesian(NB) Algorithm

We compute each word probability and class probability for each category by using word frequency information (i.e., txx). So we just select the type of nonzero values in CCS (i.e., txx or tfn).

3. Concept Vector-based(CB) Algorithm

We compute one concept vector for each category by using true category information on training data. So we don't need to specify any parameters for CB classification algorithm.

4. Singular Value Decomposition-based Algorithm

We compute first singular vector for each category by using true category information on training data. So we don't need to specify any parameters for SVD-based classification algorithm.

5. Hierarchical Algorithm

We compute concept vectors (for hierarchical concept vector-based algorithm) or probability vectors (for hierarchical naive Bayesian algorithm) based on hierarchical structure. So we need to keep hierarchical structure in data preprocess step. Therefore there is no parameter to specify except the percentage of training data.

6. Combination Algorithm

For CB_KNN algorithm, we first compute concept vectors for each category by using true category information on training data and do projection of VSM model and directly apply KNN on this projected VSM model. So we don't need to specify any parameters. For CLUSTER_CB_KNC and CLUSTER_CB_KNN algorithms, we need to specify how many clusters do we get for each class and how many nearest neighbors do we consider.

[Back to Top]

---

Experimental Results

We select six classification algorithms and compare their performance in the point of accuracy, precision, recall, and shape of learning curves. However we show only both accuracy and learning curves for accuracy as below. So to get details of corresponding precision and recall performance, we need to keep the intermediate results when we are running each driver.

K-Nearest Neighbor (KNN) algorithm - original Naive Bayesian (NB) algorithm - tfn-scaled Concept Vector-based (CB) algorithm Concept Vector-based + (original) K-Nearest Neighbor (CB_KNN) algorithm Clustering + Concept Vector-based + (original) K-Nearest Neighbor (CLUSTER_CB_KNN) algorithm SVM-based algorithm

How to evaluate classification performance?

Accuracy = (TP + TN) / (TP + FP + FN + TN) Precision = TP / (TP + FP) Recall = TP / (TP + FN) Learning curves(LCs) shows the change of performance (accuracy, precision, or recall) according to the change of training data size. Concept Vector graphs

1. Accuracy for training/testing/both data

Accuracy for CB, NB, SVD, and KNN algorithm on old data (i.e., classic3 and old 20-newsgroup) Accuracy for CB, NB, CB-KNN, and KNN algorithm on 20-newsgroup data Accuracy for CB, NB, and CB-KNN algorithm on 4-university data Accuracy for both txx-scaled and tfn-scaled NB algorithm Accuracy for original KNN and its three variations Accuracy for CLUSTER_CB_KNC algorithm Accuracy for CLUSTER_CB-KNN algorithm Accuracy for SVM-based algorithms

2. Learning Curves(LCs) for training/testing/both data

LCs for six selected classification algorithms (CB, NB, KNN, CB_KNN, CLUSTER_CB_KNN, SVM)

3. Concept Vector graphs

Concept Vector graphs

[Back to Top]

---

References

Inderjit S. Dhillon and Dharmendra S. Modha, "Concept Decompositions for Large Sparse Text Data using Clustering,", Machine Learning, vol. 42:1, pp. 143-175, January, 2001. E. Han and G. Karypis, "Centroid-Based Document Classification: Analysis & Experimental Results," Technical Report: #00-017, University of Minnesota, Dept. of Computer Science, March 2000. A. McCallum and K. Nigam, "A Comparison of Event Models for Naive Bayes Text Classification," AAAI-98 Workshop on "Learning for Text Categorization". Y. Yang and J. O. Pedersen, "A Comparative Study on Feature Selection in Text Categorization," Proceedings of the Fourteenth International Conference on Machine Learning (ICML'97), pp412-420, 1997. Y. Yang, T. Ault, T. Pierce, and C. W. Lattimer, "Improving text categorization methods for event tracking," Proceedings of ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'00), pp65-72, 2000. Y. Yang and X. Liu, "A re-examination of text categorization methods," Proceedings of ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'99), pp 42--49), 1999. K. Toutanove, F. Chen, K. Popat, and T. Hofmann, "Text Classification in a Hierarchical Mixture Model for Small Training Sets" A. Vinokourov and M. Cirolami, "A Probabilistic Framework for the Hierarchic Organization and Classification of Document Collections," Journal of Intelligent Information Systems. M. Craven, D. Dipasquo, D. Freitag, A. McCallum, T. Mitchell, K. Nigam, and S. Slattery, "Learning to Construct Knowledge Bases from the World Wide Web," Preprint submitted to Artificial Intelligence, Jan, 2000.

[Back to Top]

---

Source Codes

• Mail to yczhou@cs.utexas.edu or hyukcho@cs.utexas.edu
[Back to TOP]

---