Text categorization using weight adjusted k-nearest neighbor classification (information retrieval)

Abstract

We have seen a tremendous growth in the volume of online text documents available on the Internet, digital libraries, news sources, and company-wide intranet. These documents (with other unstructured data) will become the predominant data type stored online. Automatic text categorization, which is the task of assigning text documents to prespecified classes (topics or themes) of documents, is an important task that can help people finding information on these huge resources. Text categorization pauses unique challenges due to the large number of attributes present in the data set and multi-modal nature of the data sets. Existing classification techniques have limited applicability in the data sets of these natures. In this thesis, we present a Weight Adjusted k-Nearest Neighbor (WAKNN) classification that learns feature weights based on a greedy hill climbing technique. WAKNN allows many different optimization functions to be used and allows to have a weight learning bias to address the tradeoff between the overfitting problem and the local minima problem. Experimental results on 52 document data sets from a variety of domains confirm that WAKNN consistently outperforms other existing classification algorithms. We also present two performance optimizations of WAKNN in this thesis. The first optimization intelligently selects words used for weight adjustment. The second optimization reduces the computational cost involved with the evaluation of weight adjustments. In this optimization, the training documents in each class are clustered and the evaluation of the weight adjustments is computed with respect to these clusters. Experimental results show that these two optimization do not compromise the quality of the classification, but improve the computational performance by a few orders of magnitude. We further address the high classification cost of k-NN classification by multi-level clusters. In this approach, multiple levels of clusters with increasing cohesiveness (or tightness) are constructed. A test document is compared to the clusters from the top level to the lowest level. The test document is classified at the level in which the classification can be done with high confidence. Experimental results show that the classification using multi-level clusters can improve the computational cost substantially while maintaining the classification accuracies.