helpfn

Supervised and Traditional Term Weighting Methods for Automatic Text Categorization

Man Lan, Chew Lim Tan, Senior Member, IEEE, Jian Su, and Yue Lu, Member, IEEE

Abstract—In vector space model (VSM), text representation is the task of transforming the content of a textual document into a vector

in the term space so that the document could be recognized and classified by a computer or a classifier. Different terms (i.e., words,

phrases, or any other indexing units used to identify the contents of a text) have different importance in a text. The term weighting

methods assign appropriate weights to the terms to improve the performance of text categorization. In this study, we investigate

several widely used unsupervised (traditional) and supervised term weighting methods on benchmark data collections in combination

with SVM and kNN algorithms. In consideration of the distribution of relevant documents in the collection, we propose a new simple

supervised term weighting method, i.e., tf:rf, to improve the terms’ discriminating power for text categorization task. From the

controlled experimental results, these supervised term weighting methods have mixed performance. Specifically, our proposed

supervised term weighting method, tf:rf, has a consistently a better performance than other term weighting methods while most

supervised term weighting methods based on information theory or statistical metric perform the worst in all experiments. On the other

hand, the popularly used tf:idf method has not shown a uniformly good performance in terms of different data sets.

Index Terms—Text categorization, text representation, term weighting, SVM, kNN.

Ç

1 INTRODUCTION

TEXT categorization (TC) is the task of automaticallyclassifying unlabelled natural language documents into a predefined set of semantic categories. As the first and a vital step, text representation converts the content of a textual document into a compact format so that the document can be recognized and classified by a computer or a classifier. In the vector space model (VSM), the content of a document is represented as a vector in the term space, i.e., d ¼ðw1; . . . ;wkÞ, where k is the term (feature) set size. Terms can be at various levels, such as syllables, words, phrases, or any other complicated semantic and/or syntac- tic indexing units used to identify the contents of a text. Different terms have different importance in a text, thus an important indicator wi (usually between 0 and 1) represents how much the term ti contributes to the semantics of document d. The term weighting method is such an important step to improve the effectiveness of TC by assigning appropriate weights to terms. Although TC has

been intensively studied for several decades, the term weighting methods for TC are usually borrowed from the traditional information retrieval (IR) field, for example, the simplest binary representation, the most famous tf:idf, and its various variants.

Recently, the study of term weighting methods for TC has gained increasing attention. In contrast to IR, TC is a supervised learning task as it makes use of prior information on the membership of training documents in predefined categories. This known information is effective and has been widely used for the feature selection [1] and the construction of text classifier to improve the performance of the system. In this study, we group the term weighting methods into two categories according to whether the method involves this prior information, i.e., supervised term weighting method (if it uses this known membership information) and unsupervised term weighting method (if it does not use this information). For example, the traditional term weighting methods borrowed from IR, such as binary, term frequency (tf), tf:idf, and its various variants, belong to the unsupervised term weighting methods as the calculation of these weighting methods do not make use of the information on the category membership of training documents.

Generally, the supervised term weighting methods adopt this known information in several ways. One approach is to weight terms by using feature selection metrics such as �2, information gain, gain ratio, Odds Ratio, and so on (see [2] and [3]). Since these functions are effective in feature selection, they are naturally thought to be of great help to assign appropriate weights to terms in TC. Another approach is based on statistical confidence intervals [4], which rely on the prior knowledge of the statistical information in the labeled training data. Nevertheless, there is another approach that combines the term weighting method with a text classifier [5]. Similar to the idea of using feature selection scores, the scores used by the text classifier aim to distinguish the positive documents from negative documents are believed to be

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 31, NO. 4, APRIL 2009 721

. M. Lan is with the Department of Computer Science and Technology, East China Normal University, No. 500, Dongchuan Road, Shanghai 200241, China and with the the Department of Computer Science, School of Computing, National University of Singapore, Computing 1, Law Link, Singapore 117590. E-mail: [email protected].

. C.L. Tan is with the Department of Computer Science, School of Computing, National University of Singapore, Computing 1, Law Link, Singapore 117590. E-mail: [email protected].

. J. Su is with the Institute for Infocomm Research, 21 Heng Mui Keng Terrace, Singapore 119613. E-mail: [email protected].

. Y. Lu is with the Department of Computer Science and Technology, East China Normal University, No. 500, Dongchuan Road, Shanghai 200241, China. E-mail: [email protected].

Manuscript received 26 July 2007; revised 15 Jan. 2008; accepted 15 Apr. 2008; published online 22 Apr. 2008. Recommended for acceptance by J. Hu. For information on obtaining reprints of this article, please send e-mail to: [email protected], and reference IEEECS Log Number TPAMI-2007-07-0455. Digital Object Identifier no. 10.1109/TPAMI.2008.110.

0162-8828/09/$25.00 � 2009 IEEE Published by the IEEE Computer Society Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:55:12 UTC from IEEE Xplore. Restrictions apply.

effective in assigning more appropriate weights to the terms. These approaches will be further discussed in Section 2.3.

Since these supervised term weighting methods take the document distribution into consideration, they are naturally expected to be superior to the unsupervised (traditional) term weighting methods. However, not much work has been done on their comprehensive comparison with unsupervised term weighting methods. Although there are partial comparisons in [3] and [4], these supervised term weighting methods have been shown to have mixed results. On the other hand, another work [2] has drawn conclusions quite contrary to our previous findings [6]. Therefore, the first fundamental question arises here, i.e., “Are supervised term weighting methods based on known information able to lead to better performance than unsupervised ones for TC?”

At the same time, Leopold and Kindermann [7] pointed out that it is the text representation schemes that dominate the performance of TC rather than the kernel functions of SVM. That is, choosing an appropriate term weighting method is more important than choosing and tuning kernel functions of SVM for TC. Thus, a second question surfaces here: “Does the difference between supervised and un- supervised term weighting methods have any relationship with different learning algorithms?”

In addition, since the prior membership information of the training samples is quite helpful, we analyze the terms’ discriminating power based on this known information. As a result, we have also proposed a new supervised term weighting method, i.e., tf:rf, which first appeared in [6] and [8] and recently in [9]. While our previous work in [6], [8], and [9] provided experimental evidence for the effectiveness of tf:rf under particular experimental circum- stances, we will now formally address how and why this new method is proposed using analytical explanation and empirical observation. Thus, a third question emerges here: “ Why is the new supervised method, i.e., tf:rf, effective for TC?” Moreover, to further validate the effectiveness of tf:rf and compare with others published results, we also replicate the experiments in [10].

Therefore, the purpose of this study is to address the above three questions. To address the first two questions, we compare various widely used traditional and supervised term weighting methods (including our tf:rf) on two popular benchmark data corpora, i.e., Reuters-21578 and 20 Newsgroups, using SVM and kNN. Although these experi- ments provide evidence to validate the effectiveness of tf:rf in order to make the comparison of our results with the published results meaningful, we also duplicate the experi- ments under almost the same circumstances, as in [10]. Regarding the third question, to understand the new method tf:rf well, it is the first time that we give a detailed analysis to address how the new method is proposed and explained.

The rest of this paper is structured as follows: Section 2 reviews the popular traditional term weighting methods and the state-of-the-art supervised term weighting meth- ods. Section 3 analyzes the terms’ discriminating power and explains the newly proposed supervised term weighting method. Section 4 introduces the experimental methodol- ogy. Section 5 reports experimental results and discussions. Section 6 concludes this paper with future work.

2 TERM WEIGHTING METHODS: A BRIEF REVIEW

In text representation, terms are words, phrases, or any other indexing units used to identify the contents of a text. However, no matter which indexing unit is in use, each term in a document vector must be associated with a value (weight), which measures the importance of this term and denotes how much this term contributes to the categoriza- tion task of the document. In this section, we review a number of traditional term weighting methods and the- state-of-art supervised term weighting methods.

2.1 Three Factors for Term Weighting Assignment

Salton and Buckley [11] discussed three considerations of the assignment of appropriately weighted single term in IR field. First, term occurrences ðtfÞ in one document appear to closely represent the content of the document. Second, the term frequency alone may not have the discriminating power to pick up all the relevant documents from other irrelevant documents. Therefore, an idf factor has been proposed to increase the term’s discriminating power for IR purpose. In general, the two factors, tf and idf, are combined by a multiplication operation and are thought to improve both recall and precision measures. Third, to take the effect of document length into consideration, a cosine normalization factor is incorporated to equalize the length of the documents.

2.1.1 Term Frequency Factor

Table 1 summarizes four commonly used term frequency factors, including a binary weight, a normal raw term frequency, a logarithm of term frequency, and an inverse term frequency. The simplest binary representation (i.e., 1 for presence and 0 for absence) ignores the occurrences of the term in the document and has been used in all learning algorithms, especially in Naive Bayes and decision tree where the real number format of term weights cannot be used.1 The most popular term frequency representation only adopts the raw term frequency ðtfÞ in the document. Moreover, different variants of term frequency have been presented, for example, logð1 þ tfÞ (see [13]), where the logarithmic operation is used to scale the effect of unfavorably high term frequency in one document. Inspired by the inverse document frequency, inverse term frequency (ITF) was presented in [7].

The term frequency alone factors could be used as term weights without other factors. In our previous study [6], we

722 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 31, NO. 4, APRIL 2009

TABLE 1 Term Frequency Factors

1. McCallum and Nigam [12] used a multinomial event model for Naive Bayes text classification that can relax the constraint that document vectors should be binary valued.

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:55:12 UTC from IEEE Xplore. Restrictions apply.

have investigated three term frequency alone methods, i.e., tf, logð1 þ tfÞ, and ITF , using linear SVM in terms of microaveraged break-even point measure on two benchmark data collections. The results showed that there is no significant difference among them. The most possible reason may be that although they are different transformations, they are derived from the same base—term occurrences, and thus, there is no fundamental difference among them. As a result, we only include the tf alone and the binary method as representatives for further research in this study.

2.1.2 Collection Frequency Factor

Table 2 describes several different collection frequency factors, namely, the multipliers of 1 (that ignores the collection frequency factor), a conventional inverse collec- tion frequency factor ðidfÞ, a probabilistic inverse collection frequency ðidf-probÞ, a �2 factor ð�2Þ, an information gain factor ðigÞ, a gain ratio factor ðgrÞ, and an Odds Ratio factor ðORÞ, respectively.

Since term frequency alone may not have the discrimi- nating power to pick up all relevant documents from other irrelevant documents, an inverse document frequency (idf) factor that takes the collection distribution into account has been proposed to help to improve the performance of IR. The idf factor varies inversely with the number of documents ni, which contain the term ti in a collection of N documents and is typically computed as logðN=niÞ.

In the classical probabilistic model for IR, the relevance properties of the documents are considered, and thus, a term relevance weight is derived as the proportion of relevant documents in which a term occurs divided by the proportion of nonrelevant documents in which the term occurs. Due to the lack of knowledge of the occurrences of the terms in the relevant and nonrelevant documents in IR, this term relevance can be reduced to an idf factor of the form logððN �niÞ=niÞ [14] under an approximate circumstance. We will call this variant factor as idf prob (i.e., probabilistic idf) because it was derived from the probabilistic model and has an idf form [14]. However, in TC, the term relevance factor can be estimated based on the available training data set in advance and actually it is a well-known statistical measure, i.e., Odds Ratio.

In our previous study [6], we have also investigated the term weighting methods related to idf factor, i.e., tf:idf, logð1 þ tfÞ:idf, tf:idf prob, and idf alone. The experimental results indicated that when compared with the term frequency factor alone, the idf factor gives no or even decreases the discriminating power of the terms when

combined with the term frequency, and there is no significant difference among them. Consequently, we adopt the most popular tf:idf method as a baseline in this study.

In addition, some researchers have explored the term weighting methods by replacing the idf factor with the metrics that have been used in feature selection, such as information gain, gain ratio, �2, and Odds Ratio [2], [3]. In contrast to the standard idf factor, these factors are supervised factors because they require known information on the category membership of the training documents before the weights can be accurately estimated.

2.1.3 Normalization Factor

To eliminate the length effect, we use the cosine normal-

ization to limit the term weight range within (0, 1). Specifically, the binary feature representation does not use

any normalization since the original value is 0 or 1. Assuming that wij represents the weight of term ti in

document dj, the final term weight wij may then be defined

as wijffiffiffiffiffiffiffiffiffiffiffiffiffiffiP i ðw2

ij Þ

p . 2.2 Traditional Term Weighting Methods

As we mentioned before, the traditional term weighting

methods for TC are usually borrowed from IR and belong to the unsupervised term weighting methods. The simplest

one is binary representation. The most popular one is tf:idf

proposed by Jones (first appearing in [15] and reprinted in [16]). Note that the tf here also has various variants such as

raw term frequency, logðtfÞ, logðtf þ 1Þ, or logðtfÞþ 1. Besides, the idf factor (usually computed as logðN=niÞ) also has a number of variants such as logðN=ni þ 1Þ, logðN=niÞþ 1, and logðN=ni � 1Þ (i.e., idf prob), etc.

Interestingly, tf:idf has a variant known as BM25 (see [17]) that appears in IR literature. To understand BM25, let us first take a look at Robertson and Sparck Jones (RSJ). RSJ (see [18]) is also known as the relevance weighting from the classical probabilistic model for IR. However, due to the unavailability of relevance information in advance (other- wise, it makes a nonsense of the search process), the final term weight of term ti is further simplified based on some reasonable assumptions (for details see [17]) leading to

RSJ weight wi ¼ log N

ni : ð1Þ

It is now apparent that we can regard idf as a simple version of the RSJ weight, applicable when we have no relevance information.

The BM25 weighting function is based on an analysis of the behavior of the full eliteness model under different values of the parameters. With respect to term ti, its BM25 weight formula can be expressed as

BM25 weight wi ¼ fðtfiÞ �w�i ; ð2Þ

where w�i is the usual RSJ weight, fðtfiÞ¼ ðk1þ1Þtfi Kþtfi (K and

k1 are global parameters that are generally unknown but may be tuned on the basis of evaluation data; tfi is the

frequency of term ti in a document). It is clear that (2) expresses BM25 as a tf � idf weighting scheme. The first component is a tf component, and the second component

LAN ET AL.: SUPERVISED AND TRADITIONAL TERM WEIGHTING METHODS FOR AUTOMATIC TEXT CATEGORIZATION 723

TABLE 2 Collection Frequency Factors

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:55:12 UTC from IEEE Xplore. Restrictions apply.

is the RSJ weight, which reduces to an idf measure as

discussed earlier (see [17]). In this study, we use the typical format of tf:idf as a

multiplication of raw term frequency ðtfÞ and logðN=niÞ. There may be other variants that we do not cover in this study because they share the same idea of tf:idf, and their formats are basically similar to each other.

2.3 Supervised Term Weighting Methods

TC is a supervised learning task because the category labels of training documents are available in advance. Generally, this known information has been used in the supervised term weighting methods in the following ways.

2.3.1 Combined with Information Theory Functions or

Statistic Metrics

One approach is to weight terms by adopting feature selection metrics such as �2, information gain, gain ratio, Odds Ratio, etc. The main purpose of feature selection is to reduce the high dimensionality of the term space by selecting the most relevant and discriminating features for the classifica- tion task. The terms with higher feature selection scores are deemed to have contributed more to the TC than those with lower scores.

For example, in [2], Deng et al. replaced the idf factor with �2 factor to weight term and asserted that tf:�2 is more effective than tf:idf in their experiments with an SVM- based TC. Similarly, Debole and Sebastiani [3] assigned weights to terms by replacing the idf factor with the metrics that have been used for feature selection process, namely, information gain, �2, and gain ratio and also called them “supervised term weighting.” The difference between the two studies is that [2] used different metrics for feature selection and term weighting, while [3] adopted the same metric for feature selection and term weighting. In [3], these super- vised term weighting methods have not been shown to have a consistent superiority over the standard tf:idf-based term weighting. In most cases, the tf:idf method is better than these complicated supervised term weighting approaches. Specifically, the observation in [3] that tf:idf always outperforms tf:�2 contradicts the conclusion in [2].

Besides the TC task, the idea of using feature selection metrics as term weighting methods has been adopted in other text mining tasks. For example, in document summarization, Mori adopted gain ratio as a term weighting method to compare with a tf-based summarization system, and the result showed that this gr-based term weighting method is very effective in summarization [19].

2.3.2 Based on Statistical Confidence Intervals

In [4], the authors introduced a new term weighting method called ConfWeight based on statistical confidence inter- vals. They estimate the proportion of documents containing term tk to be a Wilson proportion estimate ~p. For a given category, we can get ~pþ and ~p� by applying ~p to the positive and negative category in the training data set, respectively. Then, they label MinPos and MaxNeg for the lower and higher limits of the 95 percent confidence interval of ~pþ and ~p�, respectively. Now, the strength of term ti for category ck

is defined as

strti;ck ¼ log2 2 � MinPosMinPosþMaxNeg

� � ; if MinPos > MaxNeg;

0; otherwise:

(

ð3Þ

Then, by using a global policy technique, the final ConfWeight of term ti in document dj is defined as

ConfWeightti;dj ¼ logðtf þ 1Þ� max c2ck

str2ti;c

� � : ð4Þ

The first component in (4) is actually a logarithmic operation of term frequency. The second component of ConfWeight determines the weight of a particular term. Thus, though the authors assigned weight to terms based on statistical confidence, to calculate the ConfWeight value for each term with respect to each category ci, the prior knowledge of the labeled training data set is required. The experimental results showed that ConfWeight generally outperformed tf:idf and gain ratio on three benchmark data collections. Furthermore, these experiments failed to show that supervised weighting methods are generally higher than unsupervised ones.

2.3.3 Interaction with Text Classifier

This approach is to weight terms in the interaction with a text classifier. Similar to the idea of using feature selection scores, since the text classifier selects the positive test documents from negative test documents by assigning different scores to the test samples, these scores are believed to be effective in assigning more appropriate weights to the terms.

For example, in [5], terms are weighted using an iterative approach involving the kNN text classifier at each step. For each iteration, the weights are slightly modified, and the categorization accuracy is measured using an evaluation set (a split from the training set). Convergence of weights should provide an optimal set of weights. However, this method is generally much too slow to be used, particularly for large problems (involving a huge vocabulary).

3 A NEW SUPERVISED TERM WEIGHTING METHOD

3.1 Terms’ Discriminating Power Analysis

For a multilabel classification problem, the benchmark on each corpus is simplified into multiple independent binary classification problems. That is, in each experiment, a chosen category is tagged as the positive category, and the other categories in the same corpus are combined together as the negative category. Therefore, all collection frequency factors are specified “locally” to a specific positive category ci. We adopt this local policy to assign term weights in this study.

Term frequency represents a close relationship between the term and the content of the documents, which contain this term. It is observed that if high-frequency terms are spread widely over a large number of documents, we may not retrieve the relevant documents from the whole collection. Consequently, the traditional idf factor and its variants are introduced to improve the discriminating power of terms in IR. However, in TC, it may not be the case. To illustrate the difference between them, we take Fig. 1 for example to analyze the terms’ discriminating power to TC.

Fig. 1 depicts the distributions of documents which contain six terms, t1, t2, t3, t4, t5, and t6, given one chosen

724 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 31, NO. 4, APRIL 2009

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:55:12 UTC from IEEE Xplore. Restrictions apply.

positive category on one data collection. In this figure, each column represents the document distribution in the corpus for each term. The height of one column is the number of documents in the corpus. The horizontal line divides these documents into two categories, the positive (above) and the negative (below). The heights of the columns above and below the horizontal line denote the number of documents in the positive and negative categories, respectively. The height of the shaded part is the number of documents that contain this term. We use a, b, c, and d to denote the number of different documents, as listed below:

. a is the number of documents in the positive category that contain this term.

. b is the number of documents in the positive category that do not contain this term.

. c is the number of documents in the negative category that contain this term.

. d is the number of documents in the negative category that do not contain this term.

Thus, N, the number of documents in the whole collection, is the sum of a, b, c, and d. In general, d � a, b, and c.

By using these notations, several widely-used collection frequency factors and information theory functions are represented as follows:

idf ¼ log N

aþ c ; ð5Þ

idf prob ¼ log bþd aþ c

; ð6Þ

�2 ¼ N � ða�d� b� cÞ2

ðaþ cÞðbþdÞðaþ bÞðcþdÞ ; ð7Þ

gr ¼ ig

�ðaþbÞ N � log ðaþbÞ

N �ðcþdÞ

N � log ðcþdÞ

N

; ð8Þ

or ¼ a�d b� c

; ð9Þ

ig ¼ a

N � log

a�N ðaþ cÞ � ðaþ bÞ

þ b

N � log

b�N ðbþdÞ � ðaþ bÞ

þ c

N � log

c�N ðaþ cÞ � ðcþdÞ

þ d

N � log

d�N ðbþdÞ � ðcþdÞ

:

ð10Þ

We assume that the six terms have the same term frequency ðtfÞ. The first three terms, i.e., t1, t2, and t3, have the same idf, which we will call idf1, and the last three terms, i.e., t4, t5, and t6 share the same idf, which we will call idf2. It is clear to find that idf1 > idf2 as the traditional idf factor gives more weights to the first three terms with less document frequency in the corpus than the last three terms.

The membership of a document in a category in TC is pretty much as the relevance of a document to an information need in IR [20]. In IR, the relevance information cannot be available in advance, while in TC, the labeled training data set is available. Considering the examples in Fig. 1, in IR, we cannot know where this horizontal line is. However in TC, due to the availability of the training data set, we can draw out this line. This difference between IR and TC comes from the availability of training data sets.

It is quite clearly observed that these six terms contribute differently to the classification task. Intuitively, it is considered that the more concentrated the terms are in the positive category than in the negative category, the more contribution they may make to separate the positive samples from the negative examples. Thus, in the above examples in Fig. 1, term t1 contributes more than t2 and t3 to distinguish the positive from the other negative categories. Similarly, term t4 contributes more than term t5 and t6.

However, by using idf and idf prob (listed in (6)) factors, we cannot see any difference among the first three terms. The similar observation can be found among the last three terms. Let us discuss the following cases in which the idf and idf prob factors fail to show their discriminating power in TC:

Case 1. Consider the first three terms, i.e., t1, t2, and t3. We can easily find that these three terms make different contributions to TC. Specifically, t1 contributes more power to discriminate the positive documents from the negative documents than t2 and t3. Thus, t1 should be weighted more than t2 and t3. However, by using idf or idf prob factor, the three terms will equalize their discriminating power for TC. The same observation can be found for the last three terms. Therefore, in this case, the idf and idf prob factors fail to assign appropriate weights to terms according to their different contributions to text classification tasks.

Case 2. Consider the two terms t1 and t4. Note the two have different idf values and idf2 ðt4Þ < idf1 ðt1Þ. However, it is clearly observed from this figure that t4 contributes more than t1, and thus, t4 should be weighted more than t1. Thus, in this case, the idf and idf prob factors have reverse effects on expressing the terms’ discriminating power for TC.

In the above two cases, the idf and idf prob factors do not have or even decrease the discriminating power for terms in TC. An obvious explanation for the failure of idf and idf prob in TC is that they do not take the document distribution in the positive and negative category into consideration.

Consequently, the other supervised factors listed from (7) to (10), i.e., �2, Odds Ratio, information gain, and gain ratio, should, in theory, outperform idf and idf prob as they make use of this prior information from the training data set. The basic idea of using these functions is that the best terms for category ck are the ones distributed most differently in the positive and negative examples of ck. However, these functions may have different interpreta- tions of this principle. For instance, in the experimental

LAN ET AL.: SUPERVISED AND TRADITIONAL TERM WEIGHTING METHODS FOR AUTOMATIC TEXT CATEGORIZATION 725

Fig. 1. Examples of different distributions of documents that contain six

terms in the whole collection.

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:55:12 UTC from IEEE Xplore. Restrictions apply.

sciences, �2 is used to measure how the results of an observation differ (i.e., are independent) from the results expected according to an initial hypothesis (here, the lower values means lower dependence). In TC, it is used to measure how independent term ti and category ck are. The term ti with the lowest value for �

2ðti;ckÞ are thus the most independent from ck; since we are interested in the terms which are not, the terms for which �2ðti;ckÞ is the highest are considered to contribute the most for classification task.

To discuss the difference between the above supervised factors and idf, we take the two factors �2 and OR for example in the following cases:

Case 3. Consider the first three terms in Fig. 1 again. The three are weighted differently in terms of idf, �2, and OR factors. Specifically, in the idf value, t1 ¼ t2 ¼ t3; in the �2 value, t1 ¼ t3 > t2; in the OR value, t1 > t2 > t3. This observation indicates that the three show inconsistent discriminating power with respect to each other. Moreover, even though �2 and OR both consider the document distribution in the positive and negative category, the two assign inconsistent weights for the same term. This difference arises from their different theoretical bases or rationales.

Case 4. Consider the two terms t1 and t4. Although the idf factor unreasonably results in t1 > t4, �

2 and OR correct this obvious mistake and appropriately makes t4 > t1. This case shows that �2 and OR would assign more appropriate weights to terms than idf.

Case 5. Consider the two terms t2 and t5. Let a ¼ c for each term (i.e., the same number of documents that contain this term in the positive and negative category). Clearly, t2 > t5 in idf value, while t5 > t2 in both �

2 and OR values. This is inconsistent with our intuitive consideration that t2 and t5 should contribute equally because each term occurs with the same frequency in the positive category as that in the negative, and thus, they both have the same discrimi- nating power.

Apparently, these supervised factors might assign more reasonable weights to terms than idf and idf prob as they consider the distribution of the documents in the positive and negative category from the training data set. However, we must note that in this section this is only a qualitative analysis of terms’ discriminating power. These supervised factors might show various degrees of discriminating power when weighting terms in the real world cases. To illustrate their different discriminating power from quanti- tative analysis aspect, we will take some real case examples in Section 3.3.

3.2 A New Supervised Term Weighting Scheme—tf:rf

The basic idea of our intuitive consideration is quite simple: the more concentrated a high-frequency term is in the positive category than in the negative category, the more contributions it makes in selecting the positive samples from the negative samples.

Although the above supervised term weighting factors take the document distribution into account, they are not always consistent with the above intuitive consideration. Specifically, several supervised term weighting factors discussed in the previous section are symmetric in terms of positive and negative categories. That is, given one category ck, if the distributions of term t1 in the positive and

negative categories are the same as those of term t3 in the negative and positive categories respectively, they will be weighted equally in �2, ig, and gr value. But, as we mentioned in the previous section, our intuitive consideration is that t1 contributes more than t3, and thus, t1 should be weighted more than t3. Why we would like to assign more weights to t1 rather than t3? For the multilabel multiclass TC task, when we build a text classifier for each category, we usually label this category as a positive category and group all the other categories as a negative category. Thus, the documents in the positive category concentrate on one topic or several topics close to each other while the documents in the negative category are spread over a wide range of topics since all nonpositive categories are grouped together as negative. Thus, the high-frequency terms concentrated in the positive category are good discriminators to select the positive samples from among the various negative samples. This idea of favoring positive terms can also be observed in [23], which tried to select such “positive” words via a metric (the square root of chi-square) as opposed to “negative” words indicative of negative documents. Therefore, unlike the above three supervised factors, we would like to assign more weight to term t1 than t3.

On first sight, the OR factor seems to be consistent with our consideration, but we may recall Case 5 listed in the previous section where two terms t2 and t5 have the same ratio of a and c. In our consideration, they would have the same contribution to TC no matter what value of b and d. That means, slightly increasing or decreasing the value of b and d (i.e., whether adding or deleting the documents in the positive or negative category, which do not contain this term) should not have an impact of the terms’ discriminat- ing power. However, it is not the case in the OR value. The difference between OR and our consideration is that we consider the terms’ discriminating power to be imposed by the number of relevant documents that contain this term only, i.e., a and c. Since d � a;b;c in general case, the OR value would vary drastically because it involves the d value.

Based on these intuitive considerations and the analysis in the previous section, we propose a new supervised weight factor relevance frequency (rf) to capture this basic idea. Its formula is expressed as

rf ¼ log 2 þ a

c

� � : ð11Þ

When combined with tf by a multiplication operation, the weight of term ti is defined as

tf:rf ¼ tf � log 2 þ a

c

� � : ð12Þ

We assign the constant value 2 in the rf formula because the base of this logarithmic operation is 2. Without the constant 2 þ , (11) would have the effect of giving a number of other terms zero weight. Let us consider two extreme cases in (12). In one extreme case, if a ¼ 0 and then rf ¼ 1, the final weight of a term in a document coincides with term frequency alone. In another extreme case, if c ¼ 0, to avoid zero divisor, we set the minimal denominator as 1, which is reasonable whatever the value of a is. Thus, the rf formula is replaced by

rf ¼ log 2 þ a

maxð1;cÞ

� � ; ð13Þ

726 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 31, NO. 4, APRIL 2009

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:55:12 UTC from IEEE Xplore. Restrictions apply.

and the final term weight is replaced by

tf:rf ¼ tf � log 2 þ a

maxð1;cÞ

� � : ð14Þ

Compared with the other supervised factors, the rf factor does not involve the d value. This is based on the observation that d � a, b, c, and thus, d will lessen the significance of a and c in expressing the terms’ discriminat- ing power for TC.

We name it relevance frequency (rf) because only the frequency of relevant documents (i.e., those that contain this term) are considered in this formula. That is, only the ratio of a and c exerts an influence on the formula. Clearly, rf function captures the idea that the best discriminators for ck are the ones distributed more in the positive samples of ck than in the negative ones. Therefore, by using rf, we weight t1 more than t2 and t3 in the above examples. Similarly, t4 is weighted more than t5 and t6 by using the rf factor.

3.3 Empirical Observation of Term’s Discriminating Power in Real-World Cases

The two previous sections presented an analytical explana- tion of the six widely used term weighting factors ((5) to (10)) and our newly proposed rf factor. To evaluate their discriminating power from a quantitative aspect, we apply them to real-world cases. To accomplish it, we choose four terms from the Reuters News Corpus. Tables 3 and 4 list the six different factors’ values for the selected four terms in terms of two categories, namely, 00 acq and 03 earn, respectively. Based on the literal meaning, the first two terms, i.e., acquir2 and stake, are closely related to the content of category 00 acq, while the last two terms, i.e., payout and dividend, are closely related to the content of category 03 earn. However, as the idf factor neglects the category information of the training set, each of these four terms is weighted equally by the idf factor in terms of the two categories. On the contrary, the supervised term weighting factors assign different weights to different terms for different categories.

Let us recall the two factors composing a term’s weight in a document, i.e., term frequency factor and collection frequency factor. They both are considered to be equally important in contributing to text classification. Therefore, deemphasizing or emphasizing either factor may result in inappropriate weights to terms. Usually, although the frequency of a term in a document varies according to the natural property of documents, it is quite a common case

that a term occurs in zero or several times rather than tens or even hundreds of times in a document.

Consider the �2 factor first. In Table 3, the �2 values of the first two terms are much larger than the last two terms, which seems reasonable since the first two terms are more relevant to the content of category 00 acq than the last two. However, the dynamic range of these four �2 values vary more considerably than that of tf, therefore, it results in suppressing the impact of the term frequency factor in contributing the discriminating power to this term. On the other hand, in Table 4, the �2 factor assigns unreasonable values to these four terms, for example, the term payout is expected to be weighted much more than the first two terms as it is more closely related to the content of category 03 earn. However, it is not the case. This observation indicates that �2 might not always assign appropriate weights to terms in real-world cases.

Compared with the values of the �2 factor, the absolute values of the ig and gr factors are very small. However, after the normalization operation on these values, the two similar observations can be found for the above four terms with respect to the two categories, i.e., one is the large dynamic range of the two factors’ values suppress the contributions of the term frequency factor for text classification and another is the term might not be weighted appropriately, for example, the term payout for category 03 earn.

Unlike the above three factors, the OR factor seems to assign reasonable values for these four terms with respect to the two categories. However, the dynamic range of the OR values for the four terms vary even more enormously than the above three factors and the term frequency factor, and thus, the OR factor may suppress the term frequency factor’s contribution power for text classification even more.

Finally, it is interesting to find that the rf factor has a comparable impact to term frequency factor for each of the four terms. Thus, the tf:rf method will be able to balance the impact of both the term frequency factor and collection frequency factor on expressing their discriminating power.

So far, we address the third question based on the analytical explanation and the empirical observation from several selected samples. To experimentally compare the performance of these factors and validate the effectiveness of the tf:rf method, we will conduct two series of experiments under various circumstances.

4 BENCHMARK METHODOLOGY

4.1 Combined Term Weighting Methods

Eight different supervised and unsupervised term weight- ing schemes listed in Table 5 are selected in this study. These methods are chosen due to their reported superior classification results or their typical representation in TC.

LAN ET AL.: SUPERVISED AND TRADITIONAL TERM WEIGHTING METHODS FOR AUTOMATIC TEXT CATEGORIZATION 727

TABLE 3 Comparison of the Weighting Values of

Four Features in Category 00 acq

TABLE 4 Comparison of the Weighting Values of

Four Features in Category 03 earn

2. Here, the acquir is a common root of several morphological forms of words and the original words can be acquire, acquired, acquires, acquiring, acquirement, etc.

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:55:12 UTC from IEEE Xplore. Restrictions apply.

The first three are unsupervised term weighting methods. The binary representation is the simplest method. The term frequency (tf) alone method has been shown to give satisfactory results in our previous study [6]. The most popular tf:idf serves as a standard baseline. The last five are supervised term weighting schemes. The tf:rf is our newly proposed term weighting method. The rf alone method, which is actually the product of binary (term frequency) and rf, can be used to explore the effects of rf alone on the classification task. The tf:�2 and tf:ig methods are two typical representatives that are based on informa- tion theory, and the two functions have been widely used for feature selection. We also investigate the tf:gr (gain ratio) method. Given the local policy for term weighting, the result of gain ratio is identical with that of information gain since they only differ in a constant multiplicative factor. The OR factor is derived from the probabilistic model, and it was actually the term relevance factor in IR. Its common format is shown in (9). However, since sometimes it seems to overstate relative positions, we would take the logarithm format to ameliorate this effect. Furthermore, to make the comparison between OR and rf more meaningful, we adopted logð2 þad=bcÞ in this study, which has the similar format of rf, where the base of the logarithm operation is 2 as well. The tf:logOR method has a rather better perfor- mance than tf:OR, thus we report the result of tf:logOR in this paper.

4.2 Inductive Learning Algorithms

We choose two state-of-the-art algorithms, i.e., kNN and SVM, for several reasons. First, the two achieve top-notch performance among the widely used algorithms [10], [21], [22]. Second, although other algorithms such as Decision Tree and Naive Bayes are also widely used, they are not included because the real number format of term weights could not be used except for the binary representation (see an exception in [12]). Finally, the two algorithms scale to large classification problems with thousands of features and examples.

4.2.1 Support Vector Machines

As a relatively new machine learning algorithm, SVM shows better performance than other methods due to its ability to efficiently handle relatively high-dimensional and large-scale data sets without decreasing classification accuracy (see [7], [10], [21], and [22]). Its excellent performance comes from the structural risk minimization principle on which the SVM is based. Generally, according to the different kernel functions from computational learning theory, SVMs are classified into two categories, i.e., linear and nonlinear (such as polynomial, radial-based function (RBF), etc).

Specifically, in this study, we adopt the linear SVM rather than nonlinear SVM for several reasons. First, linear SVM is simple and fast [21]. Second, our preliminary experimental results has shown that the linear SVM performs better than the nonlinear models. Even at the preliminary optimal tuning level, the accuracy achieved with the RBF kernel is lower than that of the linear kernel. This observation is also consistent with the findings in [21] and [22]. Thus, a simple linear SVM will serve our purpose as the first benchmark classifier algorithm. The SVM software we use is LIBSVM-2.8 [24].

4.2.2 k Nearest Neighbor

The kNN algorithm is very simple and effective. However, the most important drawback is its inefficiency in the case of high-dimensional and large-scale data sets. This draw- back comes from the nature of this “lazy” learning algorithm as it actually does not have a true learning phase and thus incurs a high computational cost at the classifica- tion time. Yang and Liu [22] set k as 30-45 since they found in that range, the kNN yields stable effectiveness. Similarly, Joachims [10] tried different k 2f1; 15; 30; 45; 60g. Following the above two attempts, we explored the k values, where k 2f1; 15; 30; 45g for the kNN classifier, and the results for the k with the best performance on the test samples are reported in Section 5.1.

4.3 Data Corpora

4.3.1 The Reuters News Corpus

The documents from the top 10 largest categories of the Reuters-21578 document collection are used. According to the ModApte split, 9,980 news stories have been partitioned into a training set of 7,193 documents and a test set of 2,787 documents. Stop words (292 stop words), punctua- tion, and numbers are removed. The Porter’s stemming [25] is done to reduce words to their base forms. The resulting vocabulary has 15,937 words. By using the �2 metric, the top p 2f25; 50; 75; 150; 300; 600; 900; 1;200; 1;800; 2;400g fea- tures per category are tried. Since SVMs have the capability to deal with high-dimensional features, the previous studies showed that feature selection does not improve or even slightly degrades the SVM performance in [7] and [26]. We also conduct experiments by inputting the full words (after removing stop words, stemming, and setting minimal term length as 4) without feature selection.

One issue of the Reuters corpus is the skewed category distribution problem. Among the top 10 categories which have 7,193 training documents, the most common category (earn) has a training set frequency of 2,877 (40 percent), but 80 percent of the categories have less than 7.5 percent instances.

4.3.2 The 20 Newsgroups Corpus

The 20 Newsgroups corpus3 is a collection of approximate 20,000 newsgroup documents nearly evenly divided among 20 discussion groups. Some newsgroups are very closely related to each other, for example, the category of comp.sys.ibm.pc.hardware and category of comp.sys.mac.hard- ware. However, others are highly unrelated, for example, the category of misc.forsale and the category of soc.religion. christian. After removing duplicates and headers, the

728 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 31, NO. 4, APRIL 2009

TABLE 5 Summary of Eight Term Weighting Methods

3. The 20 Newsgroups corpus can be freely downloaded from http:// people.csail.mit.edu/jrennie/20Newsgroups/.

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:55:12 UTC from IEEE Xplore. Restrictions apply.

remaining 18,846 documents are sorted and partitioned by date into 11,314 training documents (about 60 percent) and 7,532 test documents (about 40 percent). Therefore, com- pared with the skewed category distribution in the Reuters corpus, the 20 categories in the 20 Newsgroups corpus are of approximate uniform distribution.

The resulting vocabulary, after removing stop words (513 stop words) and words that occur less than 3 and 6 times in the positive and negative categories, respectively, has 50,088 words. According to the �2 statistics metric, the t o p p 2f5; 25; 50; 75; 100; 150; 200; 250; 300; 400; 500g f e a - tures are tried.

4.3.3 The Ohsumed Corpus

The Ohsumed collection is a subset of clinically oriented MEDLINE from year 1987 to year 1991, consisting of 348,566 references from 270 medical journals over a five- year period. The Ohsumed in year 1991 includes 74,337 documents, but only 50,216 have abstracts. Among these 50,216 documents, Joachims [10] used the first 10,000 documents for training and the second 10,000 docu- ments for testing. Specifically, we also use the Ohsumed corpus adopted by Joachims in [10] because this makes the comparison between our experiments and other published experiments reliable.

This corpus including medical abstracts from the MeSH categories are related to 23 cardiovascular diseases, and each disease corresponds to one category label. After selecting such category subset, the unique abstract number becomes 13,929 (6,286 for training and 7,643 for testing). The resulting vocabulary, after removing stop words (513 stop words) and words that occur less than 3 and 6 times in the positive and negative categories, respectively, has 19,501 words. According to the �2 metric, the top p 2 f10; 25; 50; 75; 100; 200; 300; 400; 600; 800; 1;000; 1;200g f e a - tures are tried.

4.4 Performance Evaluation

Precision and recall are two popular performance measures for TC. However, neither precision nor recall makes sense in isolation from each other as it is well known from the IR practice that higher levels of precision may be obtained at the price of low values of recall. To combine precision and recall, the two most widely used measures, i.e., F1 and breakeven point, have been proposed. F1 function attributes equal importance to precision ðpÞ

and recall ðrÞ, and it is computed as

F1 ¼ 2 �p� r pþ r

: ð15Þ

Usually, F1 function is estimated from two ways, i.e., microaveraged and macroaveraged. The two methods may give quite different results, i.e., the ability of a classifier to behave well also on categories with few examples will be emphasized by macroaveraged and much less so by microaveraged.

The breakeven point is the value at which precision is equal to recall. To obtain the breakeven point, a plot of precision as a function of recall is computed by repeatedly varying the decision threshold �. As we have known, new instances are classified by computing a score based on the classifier function and comparing the score with a decision threshold �, that is, new instances exceeding this decision threshold

are said to belong to the category. Therefore, different values of decision threshold � can be set to favor precision or recall depending on the application. If for no values of the threshold � precision and recall are exactly equal, the threshold � is set to the value for which precision and recall are closest. We must note that there may be no parameter setting that yields the breakeven.

4.5 Significance Tests

To verify the impact of the difference on the performance variation of these term weighting methods, we employ the McNemar’s significance tests [27]. It is a �2-based signifi- cance test for goodness of fit that compares the distribution of counts expected under the null hypothesis to the observed counts. The McNemar’s test can be summarized as follows:

Two classifiers fA and fB based on two different term weighting methods are performed on the test set. For each example in the test set, we record how it is classified and construct the contingency table as shown in Table 6. The null hypothesis for the significance test states that on the test set, two classifiers fA and fB will have the same error rate, which means that n10 ¼ n01. Then, the statistic � is defined as

� ¼ jn01 �n10j� 1ð Þ2

n01 þn10 ; ð16Þ

where n01 and n10 are defined in Table 6. Dietterich showed that under the null hypothesis, � is

approximately distributed as a �2 distribution with 1 degree of freedom, where the significance levels 0.01 and 0.001 correspond to the two thresholds �0 ¼ 6:64 and �1 ¼ 10:83, respectively. Given a � score computed based on the performance of a pair of classifiers fA and fB, we compare � with threshold values �0 and �1 to determine if fA is superior to fB at significance levels of 0.01 and 0.001, respectively. If the null hypothesis is correct, then the probability that this quantity is greater than 6.64 is less than 0.01. Otherwise, we may reject the null hypothesis in favor of the hypothesis that the two term weighting schemes have different performance when trained on the particular training set.

5 EXPERIMENTS

In this study, we conduct two series of experiments under various experimental circumstances.

The main purpose of the first series of experiments is to address the first two questions, i.e., to explore the super- iority of supervised term weighting methods and the relationship between term weighting methods and algo- rithms. To accomplish this, we compare eight unsupervised and supervised (including our tf:rf) term weighting methods on two popular benchmark data corpora, i.e.,

LAN ET AL.: SUPERVISED AND TRADITIONAL TERM WEIGHTING METHODS FOR AUTOMATIC TEXT CATEGORIZATION 729

TABLE 6 McNemar’s Test Contingency Table

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:55:12 UTC from IEEE Xplore. Restrictions apply.

Reuters-21578 and 20 Newsgroups, using SVM and kNN in terms of micro- and macroaveraged F1 measure. The experimental results and discussion on these two corpora are in Sections 5.1, 5.2, and 5.3.

To further validate the effectiveness of tf:rf, we conduct the second series of experiments. The second series of experiments is to duplicate the experiment of Joachims [10] and thus to make the comparison more reliable. To do this, we conduct experiments under almost the same circum- stances as [10], i.e., the same Ohsumed corpus, SVM algorithm and breakeven point measure. The comparative experimental results and discussion are in Section 5.4.

5.1 Results on the Reuters and 20 Newsgroups Corpora

Figs. 2, 3, 4, and 5 report the results of the first series of experiments on the Reuters corpus and the 20 Newsgroups corpus using SVM and kNN. Each curve in these figures represents a different term weighting method.

Fig. 2 depicts the microaveraged and macroaveraged F1 performance of different term weighting methods on the Reuters corpus using SVM. The performance of different term weighting methods at a small vocabulary size cannot be summarized in one sentence, but the trends are distinctive in that the microaveraged F1 points of different term weighting methods generally increase as the number of features grows. All term weighting methods reach a maximum microaveraged F1 point at the full vocabulary.

Among these, the best four microaveraged F1 points 0.9272, 0.9232, 0.9219, and 0.9191 are reached at the full vocabulary using tf:rf, tf, tf:logOR, and rf, respectively. The tf:rf method has always been shown to perform better than others. In contrast to the performance in terms of micro- averaged F1 measure, the performance of these methods in terms of macroaveraged F1 measure does not increase

significantly as the number of features grows. However, these methods show consistent performance in macroaver- aged F1, and the tf:rf method is still the best among these methods.

Fig. 3 depicts the microaveraged and macroaveraged F1 performance of different term weighting methods on the 20 Newsgroups corpus using SVM. The trends of the curves are similar to those in Fig. 2. That is, the microaveraged F1 points of different term weighting methods show a tendency to increase as the number of the features grows. However, these curves approach a plateau when the number of features exceeds 5,000. Finally, almost all the term weighting schemes reach a maximum of microaveraged F1 point at the full vocabulary. Among them, the best three

microaveraged F1 points 0.8081, 0.8038, and 0.8012 are reached at the full vocabulary using rf, tf:rf, and tf:idf, respectively. Moreover, the performance of these methods in macroaveraged F1 measure is quite similar to that in the microaveraged F1 measure on this nearly uniform category distribution corpus.

730 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 31, NO. 4, APRIL 2009

Fig. 2. (a) Microaveraged and (b) macroaveraged F1 measure of the eight unsupervised and supervised term weighting approaches on the Reuters-

21578 top 10 categories using linear SVM algorithm with different numbers of features.

Fig. 3. (a) Microaveraged and (b) macroaveraged F1 measure of the eight unsupervised and supervised term weighting approaches on

20 Newsgroups Corpus using linear SVM algorithm with different numbers of features.

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:55:12 UTC from IEEE Xplore. Restrictions apply.

Fig. 4 depicts the microaveraged and macroaveraged F1 performance of different term weighting methods on the Reuters corpus using kNN. The best k value for kNN is 30, and this is consistent with [10]. Unlike the shape of curves on the same corpus (Reuters) for the SVM algorithm, the performance of each term weighting method reaches a peak at a small feature set size around 400 in terms of microaveraged F1 performance and around 200 in terms of macroaveraged F1 performance, respectively. As the number of features grows, the performance of all methods declines except for tf:ig and tf:�2. The best two micro- averaged F1 points 0.8404 and 0.8399 are achieved by using binary and tf:rf methods at the feature set size of 405. Similarly, the best three macroaveraged F1 points 0.8259, 0.8219, and 0.8218 are achieved at the feature set size of 203 by using tf:rf, rf, and binary methods, respectively. When the number of features is more than 1,000, the computation inefficiency of kNN algorithm at the classification time is the most important drawback, which prevented us from conducting further experiments.

Fig. 5 depicts the microaveraged and macroaveraged F1 performance of different term weighting methods on the 20 Newsgroups corpus using kNN. The best k value for kNN is 15. The trends of curves are generally similar to those based on the Reuters and kNN (Fig. 4). Almost all the curves reach a peak at a small features size around 500 except for tf:rf, rf, and tf:logOR. The curves of these three methods show a

tendency to increase slowly as the number of features grows. The best two microaveraged F1 points 0.6913 and 0.6879 are achieved by using tf:rf and rf when the number of features is around 2,000, respectively. Similarly, we did not conduct experiments at a larger vocabulary size due to the built-in inefficiency problem of the kNN algorithm. Moreover, the performance of these methods in macroaveraged F1 measure is quite similar to the microaveraged F1 measure on this nearly uniform category distribution corpus.

5.2 Discussion on the Reuters and 20 Newsgroups Corpora

We stated that the performance of different term weighting methods is closely related to the learning algorithm (SVM or kNN) and the property of the data corpus (skewed or uniform category distribution). That is, the comparison of supervised and unsupervised term weighting methods should be studied in conjunction with the text classifier and the property of the data corpus.

We use the McNemar’s tests [27] to validate if there is a significant difference between two term weighting methods in terms of the microaveraged F1 performance analysis. Table 7 summarizes the statistical significance tests results on the two data sets and two learning algorithms at a certain feature set size where most of the methods reach their best performance. The term weighting methods with insignificant performance differences are grouped into one

LAN ET AL.: SUPERVISED AND TRADITIONAL TERM WEIGHTING METHODS FOR AUTOMATIC TEXT CATEGORIZATION 731

Fig. 4. (a) Microaveraged and (b) macroaveraged F1 measure of the eight unsupervised and supervised term weighting approaches on the Reuters-

21578 top 10 categories using kNN ðk ¼ 30Þ algorithm with different numbers of features.

Fig. 5. (a) Microaveraged and (b) macroaveraged F1 measure of the eight unsupervised and supervised term weighting approaches on

20 Newsgroups Corpus using kNN ðk ¼ 15Þ algorithm with different numbers of features.

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:55:12 UTC from IEEE Xplore. Restrictions apply.

set and “> ” and “� ” denote better than at significance level 0.01 and 0.001, respectively.

Although these methods achieve their best performance at different numbers of features, the results in Table 7 shows approximate ranks of these methods since most of them show consistent performance with respect to each other as the number of features grows given specific data corpus and learning algorithm. Moreover, in Figs. 2, 3, 4, and 5, several findings can be found as follows:

Generally, these supervised and unsupervised term weighting methods have not been shown a universally consistent performance on the two corpora and the two different algorithms.

Actually, these supervised term weighting methods have shown two extreme results in all experiments. On one hand, our tf:rf method consistently shows the best performance with respect to the two different algorithms and two text corpora. Moreover, the rf alone method, which ignores the term frequency also shows a comparable performance to tf:rf in most experiments except for on Reuters data set using the kNN algorithm (Fig. 4). On the other hand, the two typical supervised methods based on the information theory, i.e., tf:�2 and tf:ig, are the worst methods among these eight methods in most cases. Specifically, they are inferior to the unsupervised ones, i.e., tf, tf:idf, and binary and also inferior to the two newly presented special supervised methods, i.e., tf:rf and rf. Exceptionally, in Fig. 2, tf:ig and tf:�2

outperform binary representation. For another example, in Fig. 4, tf:ig is comparable to rf and tf:idf, and again, tf:�2 is the worst method of all. Another supervised term weighting method, tf:logOR performs rather better than tf:ig and tf:�2, and the best performance of tf:logOR is comparable to that of tf alone in most cases but still a bit worse than that of tf:rf. These findings indicate that these sophisticated methods based on information theoretic functions have no superiority over the simpler unsupervised ones. This is contrary to our original expectation that the supervised term weighting methods that consider the document distribution in the training documents should always be better than the unsupervised ones.

Moreover, the performance of the unsupervised term weighting methods, i.e., tf, tf:idf, and binary, is dependent on the special data corpus and the learning algorithm in use. That is, the three have no consistent performance with respect to each other. For example, for the SVM-based text classifier (Figs. 2 and 3), binary is the worst among these three methods. However, in Fig. 2, tf is better than tf:idf, but it is the other way round in Fig. 3. On the other hand, different behaviors are noted for the kNN-based text

classifier. For example, in Fig. 4, binary is the best, and tf:idf is the worst among the three unsupervised methods, while in Fig. 5, the performance of the three methods are comparable to each other. Therefore, several general observations can be made here. First, the popularly used tf:idf method performs well or even comparable to tf:rf on the 20 Newsgroups corpus using SVM and kNN. This could be explained by the observation that on the skewed corpus the idf factor has lost its discriminating power for terms, while on uniform corpus, it has retained such power. This indicates that the property of data corpus has a great impact on idf. Second, binary performs well or even comparable to tf:rf using kNN on both corpora. However, on SVM-based model, binary has rather bad performance. This indicates that kNN favors binary, while SVM does not. Third, one advantage of tf is its good robustness. Although tf does not have a comparable performance to tf:rf in all experiments, it outperforms many other methods consistently and significantly. This can be seen in Figs. 2, 3, 4, and 5.

5.3 Discussion on the Effects of Feature Set Size on Different Algorithms

We stated that the performance of term weighting methods is closely related to the learning algorithms and data collections. However, the size of the feature set at which each term weighting method reaches the peak is closely dependent upon the learning algorithm in use rather than the term weighting method itself and the benchmark data collection.

Specifically, for the SVM-based text classifier, almost all term weighting methods achieve their best performance when inputting the full vocabulary. The findings in Figs. 2 and 3 indicate this. Since SVM also has the capability to handle thousands or even tens of thousands of features, the traditional feature selection can be omitted. These findings are entirely consistent with those reported in previous studies (see [3] and [10]).

For the kNN-based text classifier, all term weighting methods achieve their best performance at a small feature set size. For example, in Fig. 4, most methods reach a peak at the feature set size of 400 or so, except for tf:ig and tf:�2. Similarly, in Fig. 5, most methods attain their maximum performance at the feature set size of 500 except for tf:rf, rf, and tf:logOR, which increase slowly with increasing feature set size.

The possible explanation for this difference lies in their different theoretical rationales. When the size of the input feature set increases, the number of features with noise also increases. SVM algorithm is resilient to noise because only the support vectors are effective for the classification performance [22]; if all other examples (vectors) are

732 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 31, NO. 4, APRIL 2009

TABLE 7 Statistical Significance Tests Results on the Two Data Corpora and Two Learning Algorithms at

Certain Numbers of Features in Terms of the Microaveraged F1 Measure

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:55:12 UTC from IEEE Xplore. Restrictions apply.

removed, the model learned will not change. This property

makes SVM theoretically different from other algorithms.

However, kNN is an example-based learning algorithm,

thus all the examples with noise have impact on the

classification performance.

5.4 Results and Discussion on the Ohsumed Corpus

To validate the effectiveness of tf:rf under the same

experimental circumstances as [10], we conduct the second

series of experiments on the Ohsumed corpus using SVM in

terms of microaveraged breakeven point measure. Besides

tf:rf and tf:idf, we also include other two methods with

good performance reported in the previous section, i.e.,

binary and tf. Fig. 6 depicts the results on the Ohsumed corpus in

terms of the microaveraged breakeven point value. In

addition, Table 8 summarizes the best results (as shown in

bold font) of four different methods. It is clearly observed

that tf:rf performs consistently and significantly better

than other term weighting methods and achieves the best

performance in all experiments in terms of microaveraged

breakeven point, i.e., 0.6805. On the other hand, the binary

representation performs consistently the worst among these

four methods, which is consistent with our previous

observation that SVM does not favor binary. The tf and

tf:idf perform comparable to each other and are better than

binary all along. These observations are not surprising and

are consistent with the previous findings on the Reuters and

20 Newsgroups corpora. In [10], Joachims used tf:idf to represent the text4 and

conducted experiments on the same data corpus using SVM

in terms of microaveraged breakeven point. Table 9 shows

the results reported by Joachims [10] in which SVMs learn

polynomial classifiers and radial basis function (rbf)

classifiers based on the following two kinds of kernel

functions:

Kpolyð~d1; ~d2Þ¼ ð~d1:~d2 þ 1Þd; ð17Þ

Krbfð~d1; ~d2Þ¼ exp �ð~d1 � ~d2Þ2 � �

: ð18Þ

Note that when d ¼ 1 in polynomial kernel functions, the polynomial SVM actually is actually a linear SVM.

Several observations from the comparison between these two studies are worth discussing:

. Our linear SVM results are more accurate, i.e., 68.05 percent for our linear SVM versus 60.7 percent for Joachims’ linear SVM and 66.1 percent for his rbf with � ¼ 0:8. The observation that linear SVM outperforms other nonlinear SVMs has already been supported by many researchers [21], [22] and our previous study in [6]. There is no clear explanation for Joachims’s different result.

. The performances of tf:idf in two experiments are almost identical, i.e., 65.78 percent for our linear SVM and 66.1 percent for his rbf SVM. This difference is not significant.

. Last but not least, our proposed tf:rf performs significantly the best among these methods in our experiments. Moreover, it outperforms the tf:idf in Joachims’ experiments whether using linear SVM or nonlinear SVMs.

Note that although our experiments use the same corpus and same evaluation measure as Joachims’, there are minor differences in data preparation such as the stemming or stop words lists for text preprocessing and the different feature selection measures. Joachims used information gain for feature selection, while we used �2 instead. This difference is not significant, and thus the comparison between the two experiments is reasonable.

6 CONCLUDING REMARKS AND FUTURE WORK

The following conclusions with empirical evidence address the three questions raised in Section 1.

The answer to the first question is: not always. That is, not all supervised term weighting methods are superior to unsupervised methods. Actually, these supervised term weighting methods are the two extremes in terms of performance. On one hand, the two supervised methods

LAN ET AL.: SUPERVISED AND TRADITIONAL TERM WEIGHTING METHODS FOR AUTOMATIC TEXT CATEGORIZATION 733

Fig. 6. Microaveraged break-even points results for the Ohsumed Data

Collection by using four term weighting schemes at different numbers of

features.

TABLE 8 The Best Performance of SVM with Four Term Weighting Schemes on the Ohsumed Corpus

4. After stemming and stop-word removal, the resulting training corpus has 15,561 terms, which occur in at least three documents. Moreover, the author used information gain measure to select the most discriminating features.

TABLE 9 Experimental Results Reported by Joachims [10]

on the Ohsumed Corpus

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:55:12 UTC from IEEE Xplore. Restrictions apply.

with solid theoretical bases, i.e., tf:�2 and tf:ig, have the worst performance in all experiments. On the other hand, our proposed supervised method tf:rf consistently achieves the best performance and outperforms other methods substantially and significantly.

The answer to the second question is, the performance of the term weighting methods, especially, the three unsuper- vised methods, has close relationships with the learning algorithms and data corpora. Their relationships with algorithms and data corpora can be summarized as follows:

. tf:rf performs consistently the best in all experi- ments.

. tf:�2 and tf:ig perform consistently the worst in all experiments.

. tf:logOR outperforms tf:�2 and tf:ig, and its performance is comparable to tf alone in most cases.

. tf:idf performs well or even comparable to tf:rf on the uniform category corpus (i.e., 20 Newsgroups corpus) either using SVM or kNN. This indicates that the property of data corpus has a great impact on idf.

. Binary performs well or even comparable to tf:rf on both corpora using kNN while rather bad on SVM- based classifier. This shows that kNN favors binary and SVM does not.

. tf has no clear relationship with algorithm or data corpus. Although tf does not perform as well as tf:rf, it performs consistently well in all experiments.

Regarding the third question, the best performance of tf:rf has been analyzed and explained from the qualitative aspect and confirmed by all experimental evidence. Given the cross-method comparison (various supervised and unsupervised), cross-classifier (SVM and kNN), and cross- corpus validation (the Reuters, 20 Newsgroups and Ohsumed corpora), we are convinced that the observed consistently best performance of tf:rf is general rather than corpus dependent or classifier dependent. We suggest that tf:rf should be used as the term weighting method for TC task because this superior advantage over other methods is robustness, i.e., it works consistently the best either cross- classifier or cross-corpus.

We should point out that the observations above are made in combination with linear SVM and/or kNN algorithms in terms of microaveraged F1 or breakeven measure and other controlled experimental settings. It will be interesting to see in our future work if we can observe the similar results on a more general learning algorithm, such as centroid-based method, or by using other performance measure. In addition, since the term weighting is the most basic component of text pre- processing methods, we expect that our weighting method can be integrated into various text mining tasks such as IR, text summarization, and so on.

Another interesting future work is to experiment on a new RCV1 benchmark corpus [26], which consists of about 850,000 documents assigned to 103 categories. Due to its huge size, it is a more reliable but a much challenging task for learning models even the top-notch algorithms such as SVM and kNN. They could not scale up very well to the huge text collections because of their polynomial complex- ity. For this reason, even though the recent work [4] and [28] used RCV1 as benchmark corpus, only a subset of RCV1 was used.

ACKNOWLEDGMENT

This project is supported in part by the NUS-I2R Project

Grant R252-000-323-592.

REFERENCES [1] Y. Yang and J.O. Pedersen, “A Comparative Study on Feature

Selection in Text Categorization,” Proc. Int’l Conf. Machine Learning, pp. 412-420, 1997.

[2] Z.-H. Deng, S.-W. Tang, D.-Q. Yang, M. Zhang, L.-Y. Li, and K.Q. Xie, “A Comparative Study on Feature Weight in Text Categor- ization,” Proc. Asia-Pacific Web Conf., vol. 3007, pp. 588-597, 2004.

[3] F. Debole and F. Sebastiani, “Supervised Term Weighting for Automated Text Categorization,” Proc. ACM Symp. Applied Computing, pp. 784-788, 2003.

[4] P. Soucy and G.W. Mineau, “Beyond TFIDF Weighting for Text Categorization in the Vector Space Model,” Proc. Int’l Joint Conf. Artificial Intelligence, pp. 1130-1135, 2005.

[5] E.-H. Han, G. Karypis, and V. Kumar, “Text Categorization Using Weight Adjusted K-Nearest Neighbor Classification,” Proc. Pacific- Asia Conf. Knowledge Discovery and Data Mining, pp. 53-65, 2001.

[6] M. Lan, S.Y. Sung, H.B. Low, and C.L. Tan, “A Comparative Study on Term Weighting Schemes for Text Categorization,” Proc. Int’l Joint Conf. Neural Networks, pp. 546-551, 2005.

[7] E. Leopold and J. Kindermann, “Text Categorization with Support Vector Machines. How to Represent Texts in Input Space?” Machine Learning, vol. 46, nos. 1-3, pp. 423-444, 2002.

[8] M. Lan, C.L. Tan, H.B. Low, and S.Y. Sung, “A Comprehensive Comparative Study on Term Weighting Schemes for Text Categorization with Support Vector Machines,” Special Interest Tracks and Posters of the WWW, pp. 1032-1033, 2005.

[9] M. Lan, C.L. Tan, and H.B. Low, “Proposing a New Term Weighting Scheme for Text Categorization,” Proc. Nat’l Conf. Artificial Intelligence, pp. 763-768, 2006.

[10] T. Joachims, “Text Categorization with Support Vector Machines: Learning with Many Relevant Features,” Proc. European Conf. Machine Learning, pp. 137-142, 1998.

[11] G. Salton and C. Buckley, “Term-Weighting Approaches in Automatic Text Retrieval,” Information Processing and Management, vol. 24, no. 5, pp. 513-523, 1988.

[12] A. McCallum and K. Nigam, “A Comparison of Event Models for Naive Bayes Text Classification,” Proc. AAAI Workshop Learning for Text Categorization, 1998.

[13] C. Buckley, G. Salton, J. Allan, and A. Singhal, “Automatic Query Expansion Using SMART: TREC 3,” Proc. Third Text REtrieval Conf., pp. 69-80, 1994.

[14] H. Wu and G. Salton, “A Comparison of Search Term Weighting: Term Relevance versus Inverse Document Frequency,” Proc. SIGIR ’81, pp. 30-39, 1981.

[15] K.S. Jones, “A Statistical Interpretation of Term Specificity and Its Application in Retrieval,” J. Documentation, vol. 28, no. 1, pp. 11- 21, 1972.

[16] K.S. Jones, “A Statistical Interpretation of Term Specificity and Its Application in Retrieval,” J. Documentation, vol. 60, no. 5, pp. 493- 502, 2004.

[17] S.E. Robertson, “Understanding Inverse Document Frequency: On Theoretical Arguments for IDF,” J. Documentation, vol. 60, no. 5, pp. 503-520, 2004.

[18] S.E. Robertson and K.S. Jones, “Relevance Weighting of Search Terms,” J. Am. Soc. Information Science, vol. 27, pp. 129-146, 1976.

[19] T. Mori, Information Gain Ratio as Term Weight: The Case of Summarization of IR Results, Assoc. Computational Linguistics, pp. 1-7, 2002.

[20] T. Saracevic, “Relevance: A Review of and a Framework for the Thinking on the Notion in Information Science,” J. Am. Soc. Information Science, vol. 26, pp. 321-343, 1975.

[21] S. Dumais, J. Platt, D. Heckerman, and M. Sahami, “Inductive Learning Algorithms and Representations for Text Categoriza- tion,” Proc. Conf. Information and Knowledge Management, pp. 148- 155, 1998.

[22] Y. Yang and X. Liu, “A Re-Examination of Text Categorization Methods,” Proc. SIGIR ’99, pp. 42-49, 1999.

[23] H.T. Ng, W.B. Goh, and K.L. Low, “Feature Selection, Perceptron Learning, and a Usability Case Study for Text Categorization,” Proc. SIGIR ’97, pp. 67-73, 1997.

734 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 31, NO. 4, APRIL 2009

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:55:12 UTC from IEEE Xplore. Restrictions apply.

[24] C.-C. Chang and C.-J. Lin, LIBSVM: A Library for Support Vector Machines, http://www.csie.ntu.edu.tw/ cjlin/libsvm, 2001.

[25] M. Porter, “An Algorithm for Suffix Stripping,” Program, vol. 14, no. 3, pp. 130-137, 1980.

[26] D.D. Lewis, Y. Yang, T.G. Rose, and F. Li, “RCV1: A New Benchmark Collection for Text Categorization Research,” J. Machine Learning Research, vol. 5, pp. 361-397, 2004.

[27] T.G. Dietterich, “Approximate Statistical Tests for Comparing Supervised Classification Learning Algorithms,” Neural Computa- tion, vol. 10, no. 7, pp. 1895-1923, 1998.

[28] Y.-S. Dong and K.-S. Han, “Text Classification Based on Data Partitioning and Parameter Varying Ensembles,” Proc. ACM Symp. Applied Computing, pp. 1044-1048, 2005.

Man Lan received the BSc degrees in fine chemical (Major) and computer science (Minor) from the Dalian University of Technology, China, in 1996, the MSc degree in computer science from Shanghai Jiao Tong University, China, in 2002, and the PhD degree in computer science from the National University of Singapore, in 2007. From 2006 to 2007, she was a research assistant with the Department of Computer Science, National University of Singapore. From

2007, she has been a research fellow with the Department of Computer Science, School of Computing, National University of Singapore, and a lecturer in the Department of Computer Science and Technology, East China Normal University. Her research interests include machine learning, text mining, information extraction and retrieval, natural language processing, and bioinformatics.

Chew Lim Tan received the BSc (Hons) degree in physics from the University of Singapore in 1971, the MSc degree in radiation studies from the University of Surrey, UK, in 1973, and the PhD degree in computer science from the University of Virginia in 1986. He is an associate professor in the Department of Computer Science, School of Computing, National Uni- versity of Singapore. His research interests include document image and text processing,

neural networks, and genetic programming. He has published more than 300 research publications in these areas. He is an associate editor of Pattern Recognition, an associate editor for Pattern Recognition Letters, and an editorial member of the International Journal on Document Analysis and Recognition. He was a guest editor of the special issue on Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD ’06) of the International Journal on Data Warehousing and Mining, April-June 2007. He has served in the program committees of many international conferences. He is the current president of the Pattern Recognition and Machine Intelligence Association (PREMIA), Singapore. He is a member of the governing board of the International Association of Pattern Recognition. He is also a senior member of the IEEE and the IEEE Computer Society.

Jian Su received the BSc degree in electronics from Sichuan University, China, in 1990 and the MSc and PhD degrees in electrical and electro- nic engineering from the South China University of Technology in 1993 and 1996, respectively. She was a research assistant at the City University of Hong Kong from 1994 to 1995 and an intern student at Centre de Recherche en Informatique de Nancy, France, in 1995. She joined Institute for Infocomm Research (I2R),

where she established herself on information extraction, coreference resolution, and (bio)text mining. She has published intensively in natural language processing (NLP) and bioinformatics conference proceedings and journals, including 12 papers in ACL Annual Meetings and one journal article in computational linguistics in recent years. She is active in professional services for the computational linguistics community. She has served as an editor/member of the editorial board for two international journals. She was the publication chair of ACL 2007 and IJCNLP 2005, technical program chair of LBM 2007, and PC members of numerous NLP conferences, including ACL, IJCNLP, COLING, and EMNLP. She also serves as member of the Technology Advisor Committee of the National Centre for Text Mining, UK (2007-present) and professor (adjunct), Harbin Institute of Technology, China (2005- present). She was also an associate professor (adjunct), School of Information System, Singapore, Management University (2005-2007). She also led her team to achieve top performances in various information extraction/text mining benchmarking such as BioCreAtIve. She was responsible for the effort to establish the largest coreference annotation corpus that has 2,000 bioabstracts and 24 biomedical full papers from the GENIA collection. She has been the principal investigator in multiple technology deployments, including biomedical information management, homeland security intelligence gathering, legal/standard enforcement, and business intelligence gathering.

Yue Lu received the bachelor’s and master’s degrees in telecommunications and electronic engineering from Zhejiang University, China, in 1990 and 1993, respectively, and the PhD degree in pattern recognition and intelligence system from Shanghai Jiao Tong University, China, in 2000. He is a professor and chair in the Department of Computer Science and Technol- ogy, East China Normal University. From 1993 to 2000, he was an engineer in the Shanghai

Research Institute of China Post. Because of his outstanding contribu- tions to the research and development of the automatic mail sorting systems, he won the Science and Technology Progress Awards issued by the Ministry of Posts and Telecommunications in 1995, 1997, and 1998, respectively. From 2000 to 2004, he was a research fellow with the Department of Computer Science, National University of Singapore. He became a professor in the Department of Computer Science and Technology, East China Normal University, in 2004. His research interests include document analysis and retrieval, natural language processing, image analysis, character recognition, and intelligence system. He was honored as the New Century Excellent Talent in University issued by Ministry of Education and Shanghai Shuguang Scholar issued by the Shanghai Municipal Education Commission in 2005. He is a member of the IEEE.

. For more information on this or any other computing topic, please visit our Digital Library at www.computer.org/publications/dlib.

LAN ET AL.: SUPERVISED AND TRADITIONAL TERM WEIGHTING METHODS FOR AUTOMATIC TEXT CATEGORIZATION 735

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:55:12 UTC from IEEE Xplore. Restrictions apply.