Overview

Automated classification techniques, where new, previously unseen data items are categorized to a predefined class of similar items, has been an active research area in pattern recognition, machine learning, and data mining. Manual classification can be costly due to the large number of instances to be checked, their complexity, or an insufficient amount of expert domain knowledge required to perform the classification. The benefit of automated systems in application domains where this occurs is obvious. Classification of natural language documents, such as web documents, is one such domain. Because the number of documents being produced now is more than ever before, especially when we consider the Internet with its massive amount of heterogeneous documents, manual classification and categorization can be extremely difficult.

Classification is different than the clustering procedures we previously examined for two major reasons. First, classification is a supervised learning task, meaning the classifier is first trained by exposing it to a set of labeled example data. Only after sufficient training is the classifier ready to be used for classification. Second, classification assigns a label to each data item (web document). In contrast clustering creates a series of groupings of the data. Thus the performance of clustering and classification algorithms is measured in different ways.

In this chapter we introduce a graph-based extension of the popular k-nearest neighbors ( k-NN) classification algorithm. The leave-one-out approach will be used to compare classification accuracy over our three document collections. We will select several values for the number...