Using Text Classifiers for Numerical Classification

1 Introduction

The machine learning community has spent many years developing robust classifier-learning methods, with C4.5[Quinlan, 1993] and Ripper [Cohen, 1995] two popular examples of such methods. Although for many years the focus has been on numerical and discrete-valued classification tasks, over the last decade there has also been considerable attention to textclassification problems[Sebastiani, 1999; Yang, 1999]. Typically such methods are applied by treating the presence or absence of each word as a separate Boolean feature. This is commonly performed either directly, by generating a large number of such features, one for each word, or indirectly, by the use of set-valued features [Cohen, 1996], in which each text-valued field of the examples is viewed as a single feature whose value for an example is the set of words that are present in that field for this example.

The information retrieval community has similarly spent many years developing robust retrieval methods applicable to many retrieval tasks concerning text-containing documents, with vector-space methods [Salton, 1991] being the best known examples of techniques in this area. Although for many years the focus has been primarily on retrieval tasks, here, too, the last decade has seen a significant increase in interest in the use of such methods for text-classification tasks. The most common techniques use the retrieval engine as the basis for a distance metric between examples, for either direct use with nearest-neighbor methods [Yang and Chute, 1994], or, based on the closely related Rocchio [1971] relevance feedback technique, for use after creating a summary "document" for each class and retrieving the nearest one [Schapire et al., 1998].

The irony is that although we now have much experience on placing text-clasification problems in the realm of numericalclassification methods, little attention has been brought to the question of whether numerical-classification problems can be effectively brought into the realm of text-classification methods. Since the text-retrieval methods on which they are based have many decade's maturity, if done effectively they have the potential of broadening further our base of methods for numerical classification.

More importantly for us, however, is the fact that many real-world problems involve a combination of both text- and numerical-valued features. For example, we came to ask these questions by confronting the problem of email classification, where we wanted to explore instance-representations that considered not only the text of each message, but also the length of the message or the time of day at which it is received [Macskassy et al., 1999]. Although the machinelearning-derived methods that we now know how to apply to pure text-classification problems could be directly applied to these "mixed-mode" problems, the application of information-retrieval-based classification methods was more problematic. The most straight-forward approach is to treat each number that a feature may take on as a distinct "word", and proceed with the use of a text-classification method using the combination of true words and tokens-for-numbers words. The problem is that this makes the numbers 1 and 2 as dissimilar as the numbers 1 and 1000 - all three values are unrelated tokens to the classification method. What we would like is an approach to applying text-classification methods to problems with numerical-valued features so that the distance between such numerical values is able to be discerned by the classification method.

This paper presents one way to do just this, converting numerical features into features to which information-retrievalbased text-classification methods can apply. Our approach presumes the use of text-classification methods that treat a piece of text as a "bag of words", representing a text object by an unordered set of tokens present in the text (most commonly words, but occasionally tokens of a more complex derivation).

The core of our approach is, roughly, to convert each number into a bag of tokens such that two numbers that are close together have more tokens in common in their respective bags than would two numbers that are farther apart. The high-level idea is to create a set of landmark values for each numerical feature, and assign two tokens to each such landmark. Every value of a feature for an example will be compared to each landmark for that feature. If the example's value is less than or equal to the landmark, the first of that landmark's two tokens is placed in that example's "bag". If the value is more than the landmark the second token is instead used in the bag. The result is that every feature gets converted into a bag of tokens, with each bag containing the same number of entries, each differing only to reflect on which side of each landmark a value lies. 1

The key question then becomes how to pick landmark values. Although our experiments show that even fairly naive approaches for selecting landmarks can perform quite well, we instead appeal to the body of work on feature discretization that has already been well-studied within machine learning [Catlett, 1991; Kerber, 1992; Fayyad and Irani, 1993; Dougherty et al., 1995; Kohavi and Sahami, 1996; Frank and Witten, 1999]. Learning methods such as C4.5 would normally have to consider a large number of possible tests on each numerical feature, in the worst case one between each consecutive pair of values that a feature takes on. These discretization methods instead use a variety of heuristic means to identify a more modest - and hence more tractable - subset of tests to consider during the learning process. Our approach is thus to apply such methods to identify a set of landmark values for each numerical feature and create two possible tokens for each landmark value, exactly one of which is assigned to each example for each landmark. The result is a "bag of words" representation for each example that can then be used by textclassification methods.

In the remainder of this paper we first describe our approach for converting numerical features into bag-of-words features in more detail, including the landmark-selectionmethods that we used. We then describe our experimental evaluation of our approach: the learningmethods, evaluationmethodsused, and our results - which show that the text-classification methods using our bag-of-words representation perform competitively with the well-used methods C4.5 and Ripper when applied to the original numerical data. We conclude the paper with some analysis of these results and some final remarks.

2 Converting Numbers to Bags of Tokens

The approach taken in this paper is to convert every number into a set of tokens such that if two values are close, these sets will be similar, and if the values are further apart the sets will be less similar. This is done for each feature by finding a set of "landmark values" or "split-points" within the feature's range of legitimate values by analyzing the values that the feature is observed to take on among the training examples. Given an example, its numerical value for a given feature is compared to each split-point for that feature generated by our approach, and for each such comparison a token will be added, representing either that the value is less than or equal to the particular split-point or greater than that split-point. This will result in exactly one token being added per split-point.

For example, consider a news-story classification task that includes a numerical feature representing the story's length. We can artificially invent a set of split-points to demonstrate our process, such as 500, 1500, and 4000. For each splitpoint we define two tokens, one for either side of the splitpoint a value may lie. Using the above split-points for the length of a news-story would result in the tokens "lengthunder500", "lengthover500", "lengthunder1500", "lengthover1500", "lengthunder4000", and "lengthover4000". A

1 However, as we will explain later, there may be fewer values in case of missing values.

new message of length 3000 would thereby have its length feature converted into the set of tokens "lengthover500", "lengthover1500", and "lengthunder4000". These would be added to the bag-of-words representation of the example - whether the other words in the bag were created from other numerical features, or the result of pre-existing text-valued features. More abstractly, consider the hypothetical numerical feature plotted along a number line in Figure 1. If a training example is obtained whose value for this feature falls in bin2, the set {morethansplit1, lessthansplit2, lessthansplit3, lessthansplit4} would be the bag-of-words representation created for this value. Note that more than one value can be given the same representation, as long as they all fall between the same two consecutive split-points.

The key question, of course, is how these split-points are selected. We use two methods in our main results. The first, called theMDL method, uses an existing entropy-based method for discretization to find good split-points[Fayyad and Irani, 1993]. This method is very similar to one that uses C4.5 on the training data, restricting it to ignore all but the single feature for which split-points are being selected, harvesting the decision points found within each of the internal nodes of the tree [Kohavi and Sahami, 1996]. The second method, which we call the density method, selects split-points that yield equal-density bins - where the number of values that fall between consecutive split-points stays roughly constant. The number of bins is selected using hill-climbing on error rate using a hold-out set. In the rest of this section we describe these two methods in more detail, concluding with a discussion of how we handle examples that are missing values for one or more of their features.

2.1 TheMDLMethod

The MDL method [Fayyad and Irani, 1993; Kohavi and Sahami, 1996] makes use of information-theoretic techniques to analyse the values of a numeric feature and create splitpoints that have high information gain. It does so in a recursive fashion, finding one split-point in the overall set of values, then finding another split-point in each of the two created subsets, until a stopping criteria based on Minimum Description Length priciples [Rissanen, 1987] is met. Each numerical feature is treated separately, yielding a different set of splitpoints for each feature. Due to space limitations we refer the reader to the given citations for further details about this popular discretization algorithm.

2.2 The DensityMethod

The density method (described in algorithmic form in Figure 2) begins by obtaining and sorting all values observed in the data for a feature f, yielding an ordered list Sf . Thus, for example, the result for some feature f might be Sf = 〈1, 2, 2, 2, 5, 8, 8, 8, 9〉. Given some desired number of splits k, the density method splits the feature set Sf into k+1 sets of equal size (except when rounding effects require being off by one) such that split-point sj is the (|Sf | ×⌊ j k+1 ⌋)-th point in Sf . Using this split-point, two tokens are generated; one for when a numerical value is less than or equal to the split-point, and another for when the numerical value is greater than the

Inputs: Sets of values for each numeric feature. Algorithm: currError ← 100 /* assume errors run from 0 - 100 */ lastError ← 100 numSplits ← 1 maxSplits← argmaxf∈numerical features(|Sf |) while(numSplits < maxSplits) do for each numerical feature f nf ← min(numSplits, |Sf |) /* Create nf split-points for feature f. */ Use as split-points for f the j-th element of Sf for j = |Sf | × ⌊ i nf+1 ⌋ with i running from 1 to nf end Divide data into 70% for train and 30% for test. C ← Run learner on train with current split-points. currError ← Evaluate C on test. if(currError = 0) do maxSplits ← 0 lastError ← currError else if(lastError < currError) do numSplits ← numSplits/2 maxSplits ← 0 else numSplits ← 2 × numSplits lastError ← currError end end Outputs: lastError

Figure 2: Density algorithm for finding split-points. split-point. k - the final number of split-points - is found using a global hill-climbing search with the number of splitpoints growing geometrically by a factor of two until the observed error rate on a 30% hold-out set is observed to increase or reach 0.

One final detail of the density method is that the algorithm in Figure 2 is actually run twice. The first time is based on a "volumetric" density calculation, where duplicate values are included in the analysis. After doing this the algorithm is run a second time after duplicate values have been removed, yielding a second set of split points that have an (approximately) equal number of distinct values between each split-point. Thus, for example, for the feature f this second run would now use the list Sf = 〈1, 2, 5, 8, 9〈. Whichever method yielded a lower error rate gives the final set of split points. If they have the same performance, whichever had fewer split-points is selected.

2.3 Missing Values

A common occurrence for many learning problems is when some examples are missing values for some of the features. This can be a complicating factor both during the learning phase, when assessing the importance of features in forming some learning result, and in classification, when making a decision when values of some of the attributes are unavailable. Common approaches range from simply deleting data or features to remove such occurrences, to imputing some value for the feature - such as through learning or through something as simple as using the median, mean, or mode value in the training data, to more complex methods such as are used in learning algorithms such as C4.5. Our approach for creating bag-of-word features out of numerical features contributes another interesting way to handle missing values. The idea is, quite simply, to add no tokens for a feature of an example when the value for this feature is missing. By not committing to any of the tokens that this feature might otherwise have added it neither contributes nor detracts from the classification process, allowing it to rely on the remaining features in assigning a label to the example.

3 Learning Algorithms

In this section we briefly describe the learning algorithms that we use in our experiments. Recall that our goal is to demonstrate that, using our approach, text-classification methods can perform as credibly on numerical classification problems as more traditional methods that were explicitly crafted for such problems. To show this we use a sampling of four different approaches for text classification. Our first is based on the Rocchio-based vector-space method for text retrieval mentioned earlier, which we label TFIDF [Joachims, 1997; Schapire et al., 1998; Sebastiani, 1999]. We also consider two probabilistic classification methods that have become popular for text classification, Naive Bayes[Domingos and Pazzani, 1996; Joachims, 1997; Mitchell, 1997] and Maximum Entropy [Nigam et al., 1999]. Finally, we also use the Ripper rule learning system [Cohen, 1995; 1996], using its capability of handling set-valued features so as to handle text classification problems in a fairly direct fashion. (The first three methods used the implementations available as part of the Rainbow text-classification system[McCallum, 1996].) The baselines to which we compare the text-classification methods are two popular "off the shelf" learning methods, C4.5 (release 8) [Quinlan, 1993] and Ripper. Note that Ripper has been mentioned twice, once as a text-classification method using our transformed features encoded for Ripper as set-valued features, and the other using the original numerical features in the same fashion as they are used with C4.5. Thus Ripper is in the unique position of being both a text-classification method when used with one representation, and as a numerical classification method when used with the other. Missing values were handled for the text-classification methods as discussed earlier, by simply not generating any tokens for a feature of an example when it had no given value, and for C4.5 and Ripper (when used with numerical features) by their built-in techniques for handling missing values.

The TFIDF classifier is based on the relevance feedback algorithm by Rocchio [1971] using the vector space retrieval model. This algorithm represents documents as vectors so that documents with similar content have similar vectors. Each component of such a vector corresponds to a term in the document, typically a word. The weight of each component is computed using the TFIDF weighting scheme, which tries to reward words that occur many times but in few documents. In the learning phase, a prototype vector is formed for each class from the positive and negative examples of that class. To classify a new document d, the cosines of the prototype vectors with the corresponding document vector are calculated for each class. d is assigned to the class with which its document vector has the highest cosine.

Naive Bayes is a probabilistic approach to inductive learning. It estimates the a posteriori probability that an example belongs to a class given the observed feature values of the example, assuming independence of the features. The class with the maximum a posteriori probability is assigned to the example. The naive Bayes classifier used here is specifically designed for text classification problems.

The Maximum Entropy classifier (labeled MAXENT in our results) estimates the conditional distribution of the class label given a document, which is a set of word-count features. The high-level idea of this technique is, roughly, that uniformdistributions should be prefered in the absence of external knowledge. A set of constraints for the model are derived from the labeled training data, which are expected values of the features. These constraints characterize the class-specific expectations for the model distribution and may lead to minimal non-uniform distributions. The solution to the maximum entropy formulation is found by the improved iterative scaling algorithm [Nigam et al., 1999].

Ripper is a learning method that forms sets of rules, where each rule tests a conjunction of conditions on feature values. Rules are returned as an ordered list, and the first successful rule provides the prediction for the class label of a new example. Importantly, Ripper allows attributes that take on sets as values, in addition to numeric and nominal features, and a condition can test whether a particular item is part of the value that the attribute takes on for a given example. This was designed to make Ripper particularly convenient to use on text data, where rather than listing each word as a separate feature, a single set-valued feature that contains all of an instance's words is used instead. Rules are formed in a greedy fashion, with each rule being built by adding conditions one at a time, using an information-theoretic metric that rewards tests that cause a rule to exclude additional negative data while still hopefully covering many positive examples. New rules are formed until a sufficient amount of the data has been covered. A final pruning stage adjusts the rule set in light of the resulting performance of the full set of rules on the data.

C4.5 is a widely used decision tree learning algorithm. It uses a fixed sets of attributes, and creates a decision tree to classify an instance into a fixed set of class-labels. At every step, if the remaining instances are all of the same class, it predicts that class, otherwise, it chooses the attribute with the highest information gain and creates a decision based on that attribute to split the training set into one subset per discrete value of the feature, or two subsets based on a thresholdcomparison for continuous features. It recursively does this until all nodes are final, or a certain user-specified threshold is met. Once the decision tree is built, C4.5 prunes the tree to avoid overfitting, again based on a user-specified setting.

4 EvaluationMethodology

To compare our text-like encoding of numbers when used with text-classification systems to the use of C4.5 and Ripper on the original numerical features we used 23 data sets taken from the UCI repository [Blake and Merz, 1998]. Table 1 shows the characteristics of these datasets. The first 14 represent problems where all the features are numeric. The final 9 represent problems in which the designated number of features are numeric and the rest are discrete or binary-valued.

The accuracy of a learner was done through ten-fold stratified cross-validation[Kohavi, 1995]. Each dataset was represented in one of four ways for our experiments:

• The original feature encoding - using numbers - for use with C4.5 and Ripper.
• The bag-of-words encoding generated by the density method, for use with the four text-classifications.
• The bag-of-words encoding generated by the MDL method, for use with the four text-classifications.
• The bag-of-words encoding generated using the tokens-for-numbers approach, for use with the five textclassifications. This was accomplished by converting every number into its English words - for example, "5" becomes "five" and "2.3" becomes "twopointthree".

The first of these represents our baseline, using a machine learning method designed for numerical classification. The

• 1 The MDL approach was unable to find any split-points for this data-set, so it is omitted in any comparisons on the MDL method.

Table 1: Properties of all datasets.

next two are the new approaches presented in this paper. The final one is the representation that simply treats each number as a distinct "word" without regard to its value.

5 Results

The first question we ask is the key one: To what extent does our approach yield a competitive learning method on numerical classification problems? Figure 3 shows the results of comparing the four text-learning methods using our MDLalgorithm features to the two numerical classification methods. Each point represents a single data set, where the x-axis is the accuracy of either C4.5 or Ripper and the y-axis is the accuracy of one of the four text methods. Points above the y=x line represent cases where the numerical-classification method was inferior to our use of a text-classification method, and points below the line are cases where the numerical method was superior. The qualitative flavor of this graph is that the MDL-algorithm features allows text-classification methods to perform credibly in many cases, exceeding numerical methods in some cases, although performing less successfully in many cases as well. We plot in Figure 4 a similar graph comparing the four text methods using the density-algorithm features to the two numerical methods. (The "outlier" cases at the bottom of the graphs are for the post-operative data set, which has only 90 examples and only 1 of its 8 features being numeric.)

Since the preceding graphs collapse eight different comparisons (four text methods versus two numerical methods)

into a picture Table 2 also shows for how many data sets each text method beat a numerical method. Each entry in the table is the number of wins/losses/ties for the new featurization method used with a text method compared to a numerical classification method. The columns label the text method used. The first two rows are results when the MDL method is used, the next two are for the density method, in each case the first comparison is to numerical classification with C4.5 comes in the first of the two rows, followed by Ripper. These results show that in a non-trivial number of cases the use of our approach for converting numerical features into text-based data beats out the popular learning methods, with absolutle improvements in accuracy ranging as high as 12%. While these results do not show that the approach is unconditionally superior to numerical classification, they do show that the approach does merit consideration for use as a numerical classification method.

The next question we ask is whether the use of two different featurization methods is necessary: Does either dominate the other? Figure /reffig:mdlvsdens shows the results of such a comparison, where each point represents a single data set and a text learning method, with the x-axis representing the result of using the MDL method with that learning algorithm, and the y-axis representing the result of using the density method with that learning algorithm. Here, too, the results show that neither method is clearly superior, with perhaps a bit better performance in general by the MDL method, but with some cases still going to the density method.

6 Additional Analysis

We began the paper stating that the obvious approach to converting numbers into text-based feature is convert each number into a unique token, to be added as-is to the set of words Compare density vs. Numeric methods

numeric average accuracy for a given example. One additional question we can ask is whether the complexity of our methods are necessary: Perhaps this simple tokenization approach performs as effectively? Figure 6 shows an analysis of this question. Each point is a data set, with the x-axis value representing the accuracy of the tokenization approach with a particular textclassification method, and the y-axis represents the accuracy with one of our two featurization methods using the same learning method. As is clearly evident from the figure, the tokenization approach is not as effective in general as our more sophisticated approach.

We conclude this section by noting that Kohavi and Sahami [1996] discuss a different discretization method that is very similar to the MDL method. This method simply runs C4.5 on the data, ignoring all features except the one for which splitpoints are being created. Kohavi and Sahami show that this method is slightly inferior to the MDL approach. However, just because it is inferior for discretization for decision-tree learning does not imply that it must be the case here, too. To test this we compared the four text classification methods using the MDL method to the C4.5 method. Figure 7 shows the results of this experiment. Each point represents a data set and a learning method. The x-axis represents the accuracy of the C4.5 approach, and the y-axis represents the accuracy of the MDL approach. As is clear, although there is some difference between the performance of the methods, they are somewhat similar in behavior.

7 Final Remarks

This paper has described an approach for converting numeric features into a representation enabling the application of text-classification methods to problems that have traditionally been solved solely using numerical-classification meth-

Compare Tokenization vs. Bag of Tokens.

c4.5-split average accuracy

Figure 7: Comparing the MDL and C4.5 approaches.

ods. In addition to opening up the use of text-methods to problems that involve "mixed-mode" data - both numerical- and text-valued features - it yields a new approach to numericalclassification method in its own right. Our experiments show that in a non-trivial number of cases the resulting methods outperform highly optimized numerical-classification methods. Also importantly, our experiments show that our approach yields a vast improvement over the naive method of converting a numeric into its equivalent textual token.

There are many directions in which we are now taking this work. Our original motivation for performing this work was to broaden the class of learning methods that can be applied to mixed-mode data. Now that we have done so, we can return to some of the work that motivated this, performing additional evaluations of this work on mixed-mode data. Doing so, however, requires a set of benchmark problems, something that does not presently exist. We are therefore in the process of creating such data sets so we can perform this evaluation process. We also noted that our approach yields an intriguing way to deal with data with missing values, and understanding its benefits and liabilities compared to other approaches remains a question that we hope to explore. Finally, as is usually the case when comparing any two learning methods that are successful in competing cases, it is difficult to make any definitive statements about when they each may be successful. Various conjectures include differences in the amount of missing values in the different data sets, the number of numeric versus non-numeric features, etc. For the given data sets we were unable to discern any such pattern in our results. This remains an important question that we also plan to study.

Acknowledgments

We would like to thank Foster Provost, Lyle Ungar, and members of the Rutgers Machine Learning Research Group for helpful comments and discussions.