An Improved Term Weighting Scheme for Text Categorization Pham Xuan Nguyen Faculty of Information Technology University of Engineering and Technology Vietnam National University, Hanoi Supervised by Dr. Le Quang Hieu A thesis submitted in fulfillment of the requirements for the degree of Master of Science in Computer Science August 2014 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com ORIGINALITY STATEMENT ‘I hereby declare that this submission is my own work. To the best of my knowledge, it contains no materials previously published by another person, or substantial proportions of material which have been accepted for the award of any other degrees or diplomas at University of Engineering and Technology (UET/Coltech) or any other educational institutions, except where due acknowledgement is made in the thesis. Any contributions made to the researches by others are explicitly acknowledged in the thesis.
I also declare that the intellectual content of this thesis is the product of my own work, except to the extent that assistance from others in the project’s design and conception or in style, presentation and linguistic expression are acknowledged.’ Hanoi, August 24th , 2014 Signed. i LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com ABSTRACT In text categorization, term weighting is the task to assign weights to terms during the document presentation phase. Thus, it affects the classification performance. In addition to resulting in a high performance of text categorization, an effective term weighting scheme should be easy to use.
Term weighting methods can be divided into two categories, namely, supervised and unsupervised [27]. The traditional term weighting schemes such as binary, tf and tf.idf [38], belong to unsupervised term weighting methods. Other schemes (for example, tf.χ2 [12]) that make use of the prior information about the membership of training documents, belong to the supervised term weighting methods. The supervised term weighting method tf.rf [27] is one of the most effective schemes to date.
It showed better performance than many others [27].rf is not the best in some cases.rf requires many rf values for each term. In this thesis, we present an improved term weighting scheme from tf.rf, called logtf. Our new scheme uses logtf = log2 (1.0 + tf ) instead of tf. Furthermore, our scheme is simpler than tf.rf because it only uses the maximum value of rf for each term.
Our experimental results showed that our scheme is consistently better than tf.rf and others. ii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com To my family ♥ iii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com ACKNOWLEDGEMENTS First, I would like to express my gratitude to my supervisor, Dr. Le Quang Hieu. He guided me throughout the years and gave me several useful advices about study method.
He was very patient with me. His words influenced strongly on me. I also would like to give my honest appreciation to my colleagues at Hoalu University and University of Engineering and Technology (UET/Coltech) for their great support. Thank you all! iv LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Table of Contents 1 Introduction 1 1.2 Structure of this Thesis.
2 2 Overview of Text Categorization 4 2.3 Text Categorization tasks .1 Single-label and Multi-label Text Categorization .2 Flat and Hierarchical Text Categorization .4 Applications of Text Categorization .1 Automatic Document Indexing for IR Systems .3 Word Sense Disambiguation .4 Text Filtering System .5 Hierarchical Categorization of Web Pages .5 Machine learning approaches to Text Categorization .3 Support Vector Machines. 15 3 Term Weighting Schemes 18 3.2 Previous Term Weighting Schemes .1 Unsupervised Term Weighting Schemes .2 Supervised Term Weighting Schemes. 21 v LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com TABLE OF CONTENTS vi 3.3 Our New Term Weighting Scheme .1 Term Weighting Methods .2 Machine Learning Algorithm .1 Reuters News Corpus .5 Results and Discussion .1 Results on the 20 Newsgroups corpus .2 Results on the Reuters News corpus. 34 5 Conclusion 37 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com List of Figures 2.1 An example of vector space model .2 An example of transforming a multi-label problem into 3 binary clas- sification problems .3 A hiararchy with two top-level categories .4 Text Categorization using machine learning techniques .5 An example of a decision tree [source [27]] .1 Linear Support Vector Machine [source [14]] .2 The micro − F1 measure of eight term weighting schemes on the 20 Newsgroups corpus with different numbers of features .3 The macro − F1 measure of eight term weighting schemes on the 20 Newsgroups corpus with different numbers of features .4 The micro − F1 measure of eight term weighting schemes on the Reuters News corpus with different numbers of features .5 The macro − F1 measure of eight term weighting schemes on the Reuters News corpus with different numbers of features .6 The f1 measure of four methods on each category of Reuters News corpus using SVM algorithm at the full vocabulary .7 The f1 measure of four methods on each category of 20 Newsgroups corpus using SVM algorithm at the full vocabulary, category from 1 to 10 .8 The f1 measure of four methods on each category of 20 Newsgroups corpus using SVM algorithm at the full vocabulary, category from 11 to 20.
34 vii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com List of Tables 3.1 Traditional Term Weighting Schemes .2 Examples of two terms having different tf and log2 (1 + tf ) .1 Experimental Term Weighting Schemes .1 Examples of two term weights as using rf and rfmax. 38 viii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com List of Abbreviations TC Text Categorization TWS Term Weighting Scheme IR Information Retrieval ML Machine Learning F1 F-measure SVM Support Vector Machine ix LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chapter 1 Introduction 1.1 Motivation In recent decades, there is a huge growth in the number of textual information documents, especially in Word Wide Web. As a result, the needs for categorizing the documents increased rapidly and text categorization (TC) field attracted many researchers. In text representation phase, the content of documents are transformed into a compact format.
Specifically, each document is presented as a vector of terms in the vector space model. Each vector component contains a value presenting how much a term contributes to the discriminative semantics of the document. Term Weighting Scheme is the task to assign weights to terms in this phase. TWS is a well-studied field.
The traditional term weighting methods such as binary, tf and tf.idf are borrowed from information retrieval (IR) domain. These term weighting schemes do not use the previous information about the member- ship of training documents. Other schemes using this information are called the supervised term weighting schemes, for example, tf. To date, the supervised term weighting scheme tf.rf [27] is one of the best meth- ods.
It achieves better performance than many others in a series of thorough ex- 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Structure of this Thesis 2 periments using two commonly-used algorithms (SVM and kNN) as well as two benchmark data collections (Reuters News and 20 Newsgroups). However, the per- formance of tf.rf is not stable.rf shows the considerable better performance than all other schemes in the experiments on Reuters News data set, while its perfor- mance is worse than rf ’s performance (a term weighting scheme does not use the tf factor), and is slightly better than tf.idf (a common term weighting method) in the experiments on 20 Newsgroups corpus. Furthermore, for each term, tf.rf requires N (the total number of categories) rf values in a multi-label classification problem.
It raises a question whether there is a typical rf value for each term. In this thesis, we propose an improved term weighting scheme, which applies two improvements to tf. First, we replace tf by logtf = log2 (1. Moreover, we only use the maximum of rf value (rfmax ) for each term in a multi-label classification problem.
The formula for our scheme is logtf. We conducted experiments with the experimental settings described in [27], where tf.rf was proposed. We use two standard measures (micro − F1 and macro − F1 ) as well as linear SVM. We carefully select eight term weighting schemes, in- cluding two common methods, two schemes used in [27], four methods applying our improvements, in order to assess our work.
The experimental results show that logtf.rfmax consistently outperforms tf.rf as well as other schemes on two data sets.2 Structure of this Thesis The remainder of this thesis is organized as follows. Chapter 2 provides an overview of text categorization. Chapter 3 reviews the term weighting schemes for text cate- gorization, and describes our improved term weighting scheme. Chapter 4 describes our experiments, including the used algorithms, data sets, measures, results and discussion.
Chapter 5 presents the conclusion. In this study, the default studied language is English. In addition, we only apply the bag-of-words approach to represent a document, and used data sets are flat. The LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Structure of this Thesis 3 results of the study can result in a valuable term weighting method for TC. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chapter 2 Overview of Text Categorization This chapter gives an overview of TC. We begin by introducing TC, then present some applications and tasks of TC. The rest this chapter is about the approaches to TC, especially SVM, which is applied in this thesis.1 Introduction Automated text categorization (or text classification) is the supervised learning task of assigning documents into the predefined categories.
TC differs from text clustering where we can not know the set of categories in advance. TC has been studying since the early 1960s, but it only has been focused in recent decades due to the needs of categorizing a large number of the documents in Word Wide Web. Generally, TC relates to the machine learning (ML) and information retrieval (IR) field. In the 1980s, the popular approaches to TC is constructing an expert system, which is capable of taking text classification decision based on knowledge engineering techniques.
The famous example of this method is CONSTRUE system [22]. Since the early 1990s, the machine learning approaches to TC have become popular. 4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Text Representation 5 Figure 2.1: An example of vector space model 2.2 Text Representation Generally, text is stored in the readable particular types such as HTML, PDF, DOC, and so on.
However, these forms are not suitable for most machine learning algorithms. Thus, the content of a document must be transformed into a compact representation so as to be recognized and categorized by classifiers. One way to text representation is use the vector space model (VSM) based on words documents (a technique in the IR domain). In VSM, the content of a textual document is converted to a vector in the term space (each term usually associates a word).
For detail, the document d is represented as (w1 ,. , wn ), where n is the total number of terms. The value of wk represents how much the term tk contributes to classify the document d.1 illustrates the way of representing documents in VSM. Five documents are represented as five vectors in the 3-dimensional space (System, Class, Text).
LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Text Representation 6 In the process of transforming documents according to VSM, the word sequence in a document is not considered and each dimension in vector space associates with a word in the vocabulary that is built after text preprocessing phase. In this phase, the words assume to have no information content (such as stop words, numbers, and so on) in a document are removed. Then words can be stemmed.
Finally, the rest words in all of documents are sorted alphabetically, and numbered consecutively.