A Simple Feature Selection Method for Text Classification

1 Introduction

In automatic text classification most techniques use bag-ofwords to represent documents. The main problem is then to identify what words are best suited to classify the documents in predefined classes. Feature selection techniques are then needed to identify these words.

Many feature selection techniques use some metric to determine the relevancy of a term with regard to a classification criterion. One such technique uses the information gain metric assessed over the set of all words encountered in all texts, and then chooses the best k words according to that metric [Lewis and Ringuette, 1994]. Because of computational efficiency issues, it may not be possible to use the learning algorithm itself to determine which k is best suited to learn the descriptions of the classes of documents so that the accuracy rate of the algorithm is maximized. In that case, there is little guidance to determine what value k should be. Some naive techniques just predetermine a k using the learning algorithms over a small set of data sets , and then uses that value of k directly on other data sets even though these data sets may be quite different from those used to learn the value of k. To our opinion, this k becomes rather arbitrary unless data sets can be characterized in such a way to be easily associated with previously tested data sets.

The feature selection method presented in this paper is rather simple and computationally efficient. Efficiency is a major issue in text classification of large corpora (like found on the WWW) since ma ny thousand features are usually involved. Our method is a filter approach [Hall and Smith, 1999], as the learning algorithm is not involved in the selection process of features and is self-adaptable to the nature of the corpus. It combines a feature selection method known to be among the best for text classification [Yang and Pedersen, 1997], that is, thresholding on information gain, and a new algorithm that selects and add features to a bag-ofwords according to their average coocurrence in the training set with the features already in a small set composed of the best features selected so far for their high information gain, called the pool. This paper presents this feature selection method and how we have predetermined some of its parameters, called thresholds, through experimentation. It also shows how these thresholds can be used as such in other domains and still render a good performance level in terms of the relevancy of the feature set extracted for subsequent classification purposes.

2 Experimental Testbeds

2.1 Learning Algorithms

In order to assess the potential of our feature selection method, we used it with two different learning algorithms that are widely used in text classification and retrieval: knearest neighbors (KNN) algorithms (wit h weighted and non weighted features according to different weighting functions) and Rainbow, a naive Bayes classification algorithm for text classification [McCallum, 1996; Fürnkranz et al., 1998]. However, because of lack of space, this paper only presents the results obtained with the non weighted features KNN algorithm and Rainbow, since all weighted KNN algorithms performed more poorly than their nonweighted counter-part. Appendice A briefly describes the weighting functions tested to try and improve the nonweighted version of our KNN algorithm, without success.

2.2 Data Sets

For our experiments, we used data sets previously studied in other work, and our own data sets. The data sets used in our experiments are described in table 1. These data sets may be categorized in two types: those including documents written with a concise vocabulary and those more freely written. The former set includes data sets such as Reuters (brief news) and WebKB (Web pages mainly retrieved from computer science university departments) while the latter set includes noisy data sets such as Ling-Spam (consisting of emails belonging to a mailing-list, including junk emails), Prisoner (the TV show) and Beethoven (the composer) (Web pages retrieved with Altavista using a keyword search), and News (unmoderated Usenet newsgroups on history and christianism). The difficulty associated with a classification task depends highly on the type of vocabulary used [Scott and Matwin, 1999]. Words were stemmed using the Porter algorithm for our KNN algorithms, and using the --use-stemming option with Rainbow.

1 The size may be different from the original data set to ensure computationally manageable experiments. In that case, subsets of the original data sets have been selected randomly. For WWW pages research, the size is small due to the fact that there are very few relevant documents.

2 Described in [8] and is available at

www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-20/www/data/.

3 Well known data sets available at

http://www.research.att.com/~lewis/reuters21578.html.

4 The Ling-Spam anti-spam filtering corpus, available at:

http://www.iit.demokritos.gr/~ionandr/lingspam_public.tar.gz.

5 WWW pages manually classified according to their relevance to a subject, the TV show The Prisoner.

6 WWW pages manually classified according to their relevance to a subject, Beethoven biographies.

7 Usenet articles collected from soc.history and

soc.religion.christians newsgroups. Only the first message of a thread of discussion has been retrieved. See [Scott and Matwin, 1999] for explanations about this choice.

3 Feature selection

Information Gain (IG) in text classification measures the reduction in entropy (heterogeneity of a set) gained using a term presence or absence to determine class membership. It is often used in text classification in the bag-of-words approach [Joachims, 1998; Nigam et al., 1999; Sahami et al., 1998]. This measure is the same used by ID3, a decision tree learning algorithm, to select the best attribute at each step of the tree construction [Quinlan, 1986].

3.1 The k best features using the Information Gain

Under this approach, a text classification task is considered using the first k words that rank highest on that metric. That number k, however, depends highly on the kind of corpus and task involved. Under a Bayesian classification approach, many noticed that a naive Bayesian classifier works best with many features, but better if not every available feature is used. From various experiments it was noticed that the k which seemed to be an approximation of the average number of features leading to reasonable results with that algorithm varies from 2000 features [Craven et al., 1998] to 500 features [Sahami et al., 1998] depending on the nature of the corpus.

These findings show a great variation in the size of the required vocabulary. If we consider that Bayesian classifiers suffer when irrelevant features are kept as selected features, it is difficult to justify why a predefined number of features would allow to optimize the accuracy rate of the classifier. Actually, in such data sets as Reuters, there are some words that are so characteristic of some class that fewer features need to be selected than with a data set involving newsgroups or email messages. It seems obvious that the number of required features highly depends on the nature of the corpus and of the learning algorithm. Therefore, how could we characterize the nature of the corpus in terms of the available features so that guidelines on how to select a proper k are easily inferred? This paper proposes one such way to determine k according to the nature of the terms composing the vocabulary with regard to their discrimination power relative to one another.

3.2 Using Information Gain with a threshold

A simple feature selection method could look at the IG of each feature (taken individually) with regard to the classification task. For instance, there are methods that select any feature with an IG greater than some threshold [Yang and Perdersen, 1997]. This is fully relevant to Bayesian classifiers. It is easy to see that features with low IG are useful to characterize only a handful of documents. Therefore, their probability distribution over the whole set of documents can not be estimated correctly. Bayesian classifiers rely on these probability estimates.

Similarly, infrequently used dimensions (attributes) in a KNN approach introduce noise more than anything else. As a matter of fact, KNN seems to produce better results when fewer features are involved, using the IG to keep the best features [Joachims, 1998]. KNN bias depends mostly on the kind of similarity function it uses, but it always uses the vector model, a weakness of this model being the fact that features are considered to be independent of each other. The function that seemed most successful (see Appendix A, a non weighted cosine similarity function), assigns to each feature the same weight. Given that, we should only consider features that are promising in terms of class characterization, as the presence of many irrelevant features diminish the influence of very good (relevant) features. Choosing a fixed number of features may lead to consider irrelevant ones (as with the Reuters data sets) if k is too high, or remove some good features (as with junk email classification) if k is too low.

However, even if we obtained good results on average using the KNN and Bayes classifiers, by looking at each data set individually we noticed that it would be possible to restrict the set of selected features even more. For instance, with the Reuters data set, we saw that in most binary classification tasks (for example, classifying documents according to their relevance to "corn" or "wheat"), only a few words (often under 10) were needed to obtain the best accuracy score. We observed that high IG features could represent classification alternatives (in which case one is useless), or could be complementary. Therefore, we could assess the cooccurrence of highly ranked features and eliminate those that represent alternatives of already selected high IG features.

We conducted extensive experiments where we had the number of features ranging from 1 to 5000 and the IG threshold ranging from 0 to 1. From all these experiments, we found that the best threshold to classify the data sets that we had was 0.1 in average. Therefore, we propose to first identify the terms whose IG is higher or equal to 0.1, and then, select only those features that are not covered by the strong features already in the set (in terms of their discrimination capability), as explained below. In what follows, we prove that this further refinement of the term set improves both the accuracy of the classifier and the interpretability of the characterization so produced since the number of selected features is sensibly reduced.

3.3 Our Feature Selection Algorithm

The algorithm of Figure 1 proposes a refinement of the set of selected features (already offering an IG higher than some threshold) by removing those features that cooccur with very high IG features. Cooccurrence is a kind of measure of dependency between features, which is a weakness of most statistical models used today to characterize a set of features. Because of computational issues, dependencies between terms are usually ignored. We propose to identify a small subset of terms that we know are relevant for the classification task at hand (according to their individual IG), and to comp ute dependencies between any new term and these preselected terms. The cooccurrence metric that we consider

A Simple Feature Selection Algorithm: µCooccurrence

Let V = set containing every word found in the corpus, sorted by Information Gain (in decreasing order) Let Pool = {} (the pool) Let D = set of documents Let igain_thres = 0.1 Let cooc_thres = 0.45 Let nbkeep = 5 Pool � nbkeep first features from V FOR each word w IN V - Pool IF IG(w,D) < igain_thres THEN V = V - {w} ELSIF µCooc(w,Pool,D) > cooc_thres THEN V = V - {w} ENDIF ENDFOR µCooc (w, Pool,D) : Let Sum = 0 FOR each pi in Pool Sum � Sum + (P(w | pi) in D) RETURN (Sum / nbkeep)

in the algorithm of Figure 1, written µCooc(w,Pool,D), is based on a partial cooccurence probability of w with each word in Pool, considering the whole training set. It is computed as the mean value of P(w|pi) for all pi in Pool, where P(w|pi) is the conditional probability to find w in any document if it already contains pi.

Let us take an example and assume that the word "corn" has an IG value of 0.95, meaning that it almost perfectly divides the training set. Then let us suppose that P(starch|corn) = 1 and IG(starch) < IG(corn). Since "starch" always occurs when "corn" does and since its IG is lower than that of "corn", "starch" is unlikely to bring new information (in terms of discrimination power) to the feature set, and could therefore be removed from it.

Needless to say that the reality is not that perfect. Removing a feature only when it is totally covered by some other feature (in terms of its discrimination capability) would remove only a few features, if any, which goes against our aggressive selection objective. Some approximation of coverage between terms is thus required to effectively reduce the vocabulary to those features that are meaningful in terms of their overall discrimination power. Our approach is to consider a mean of partial cooccurrence between any new term and the terms in P, the set of the nbkeep highest ranked features according to their IG, called the pool. Of course, nbkeep and cooc_thres (see the algorithm of Figure 1) have been empirically determined using our own data sets: Prisoner, Beethoven and News, and tests have been conducted over previously studied data sets: Reuters, Ling-Spam and WebKB, in order to prevent over fitting the parameters on these data sets. Due to a lack of space, we won't show here the results of this parameterization, but we concluded from these tests that the values used in the algorithm of Figure 1 hold for all our data sets, and seem to hold for other data sets that we are currently experiencing with.

4 Results

Table 2 shows the results obtained with the different feature selection methods that we tested over each corpus, under our two learning algorithms: a non weighted features KNN algorithm (first three columns) and Rainbow, a well-used Bayesian classifier (last five columns). For each method, we show k, the number of features selected and used thereafter by the learning algorithm, and the accuracy score (%) obtained subsequently.

The first column shows the k features selected when we set a threshold of 0.1 on the Information Gain score (IG) of each feature. Again, this threshold was assessed empirically over all possible values of IG ranging from 0 to 1. From the resulting set, our µCooccurrence refinement algorithm was applied to produce a smaller set of features, and the results are shown in the second column. One can see that the number of features is almost always reduced, and if so, significantly and without impact on the accuracy rate, meaning that we could eliminate useless features in terms of the prediction capability of the learning algorithms used. This helps produce a characterization of the learned concepts with a smaller vocabulary, and therefore facilitates the interpretation of the results and reduces the computation cost to classify new documents.

Then we wondered if this minimal number of features could have been reached through a fine tuning of the IG score that we used. We found that an IG of 0.13 would produce the same number of selected features (taken over all corpora), but that the accuracy rate would then go down, as shown in the third column. Obviously, the selected features in this case are not the same as those of the previous experiment. Furthermore, we see that the small fluctuation in the IG rate (0.03) has great impact on the individual corpora in terms of the number of selected features. Considering our detailed search for a good IG rate, it is not surprising to see such a fluctuation and its negative impact on the accuracy rate of the classifiers. This tends to show that 0.1 is a better threshold than 0.13, as validated in a previous experiment, and that our feature selection method is therefore useful to reduce that set by removing useless (or not so useful) features. It also suggests, at least on this type of corpora, that our method is sound and useful to determine a relevant k which, without such a method, would be impossible to determine.

For the Bayesian classifier, we observe the same phenomenon. The forth column gives the number of selected features for IG = 0.1 and the accuracy rate obtained after training Rainbow with these features. For comparison purposes, we also trained Rainbow with 2000 features (fifth column) as is suggested in [Craven et al., 1998]. By comparing the forth and fifth columns we can see that the 2000 feature sets performs better than what we obtain with IG = 0.1 except in cases where there are a few words with extreme discrimination capabilities like with the Reuters and Beethoven corpora. Despite this small loss in accuracy, the feature set with IG = 0.1 is nevertheless significantly smaller than 2000, which would undoubtedly help the interpretation of the learned concepts.

In the next experiment (sixth column), we applied our µCooccurrence refinement algorithm to reduce even further the size of the feature set. Again we obtain a reduced set without any impact on the accuracy rate, facilitating even more the subsequent interpretation of the learned concepts.

However, by setting IG = 0.13, we obtain the same number of features (taken over all feature sets) and a slightly smaller accuracy rate (see the seventh column).

Finally, as expected, an unbounded number of features has a negative impact on the accuracy rate of a Bayesian classifier, as shown in the last column. Though not illustrated in Table 2, this phenomenon also holds for KNN classifiers when the number of attributes is extremely high and the number of relevant attributes is much lower than the number of attributes, which is the case in text classification. Therefore, there is a need to determine a proper k for training the classifier with the relevant attributes.

5 Complexity Issues

Let N be the number of documents, let V be the size of the vocabulary, and let P be the size of the pool. By choosing to compute cooccurrence only between the elements of the vocabulary and the pool, we avoid having to compute it for all O(V 2 ) possibilities (when pairs of features are considered), producing a O(VPN) complexity factor rather than O(V 2 N) for assessing the cooccurrence of terms over all N documents. Since computing the IG for all features in V is O(VN), and since ordering them by their IG is O(V log V), for large corpora (where log2 V << N), the dominating complexity factor of our algorithm is the assessment of the cooccurrence of terms. Consequently, our method works under a complexity factor of O(VPN). Provided that we can determine P independently of V and N, as was done in our experiments, the resulting complexity figure for our method then becomes O(VN), which is the same complexity figure for initially assessing the IG of each feature in the vocabulary. Consequently, our µCooccurrence feature selection algorithm has the same asymptotic complexity as a feature selection method that solely computes the IG of each feature in its feature set, with a hidden constant that has now doubled however. Nevertheless, the method is computationally efficient.

6 Conclusion and Future Work

We have presented in this paper a very simple feature selection method for text classification that refines a set of features previously selected according to an IG criterion. This refinement is based on the cooccurrence of new features with a predetermined subset of highly ranked features, called the pool, hoping to avoid to include features whose discrimination capability with regard to the task is (partially) covered by the features of the pool. We seek to improve the classification speed of the learner without reducing accuracy and reduce the set of attributes that will be used later on to support the interpretation of the learned concepts. This paper shows that we reached this objective for the corpora that we studied. The method that we propose in this paper certainly proved to be promising for certain types of text classification tasks, as demonstrated by our experiments. At first glance, we are tempted to conclude that µCooccurrence has the capability to remove the features that brings no further information to those already selected. Of course further experiments will be conducted to assess the validity of that claim under various conditions.

Additional investigation will also be conducted in order to understand why µCooccurrence seems to have more impact on (non weighted feature) KNN algorithms than on Bayesian classifiers. Though we feel that the probabilities that ponder the involvement of attributes provides some explanation, we still can not understand why weighted features KNN approaches failed to surpass the non weighted KNN algorithm that we used, despite extensive experimentation using a wide range of distance functions. [Domingos and Pazzani, 1997] demonstrated why naive Bayes learners perform well in spite of the (so-called) word independence assumption. Therefore, we will focus our investigation towards the study of word dependence and its impact on the KNN model.

Further effort is also needed to extend the µCooccurrence algorithm so that it can handle multiple concept learning. Our experiments have been conducted only over binary classification tasks.

Another field of investigation will be to use multistrategic approaches to feature selection. For instance, we could assess the information gain of sequences of features. We could base our choice of feature sequences on the first few levels of decision trees built from our initial feature set, and increment the vocabulary accordingly.

Finally, though we set the IG and cooccurrence thresholds at 0.1 and 0.45 through extensive experimentation, more study on the impact of these parameters on the cla ssification task with regard to different types of corpora is required.

Appendix A

The learning bias of the KNN model is mainly related to its distance (similarity) function and to its neighbor weighting function to compute that distance. Distance weighted KNN adjusts the importance of each neighbor by weighting their contribution to the classification of a new instance. In this section, we consider the weights associated with the features themselves rather than with individual instances.

This section presents the weight and distance functions that have been studied in our search to determine which KNN algorithm would be used in the assessment of our feature selection method. Surprisingly, the simplest of these functions worked better that the others.

Let us define an instance x is as

where aj(x) is the weight of the jth attribute (feature) on x.

Using non-weighted features

If we consider that the weight of each feature is the same, then we have:

• document x in is word the If 1 ) ( = x a j
• otherwise 0 ) ( = x a j

Using weighted features

The goal reached using weighted features is to stretch the neighborhood space so that irrelevant features are given less importance. There are several ways to do this feature weighting. Here are a few examples that were tested:

• the weight of a feature for a document is its IG if the word is present in the document, 0 otherwise
• the weight of a feature is its frequency in the document
• the weight of a feature is its TFIDF (Term frequency/Inverse Document Frequency)

We also tried many variants of these methods, for example, squaring the IG so that features with high IG would get yet higher weights. Under these various weight assignment policies, we experimented with two distance functions :

Euclidian distance function

Cosine similarity function [Salton89]