News Categorization Using SVM

NEWS CATEGORIZATION USING SUPPORT VECTOR MACHINE (SVM)

Ivan Andhika, Herastia Maharani

Department of Informatics Engineering

Institut Teknologi Harapan Bangsa

Jalan Dipati Ukur no. 83 – 84

Bandung

www.ithb.ac.id

--------------------------------------------------------------------------------------------------------------------------------------------

Abstract - The advancement of internet technology provides information quickly but the news are random. News site provides categorized news so that the readers can easily read them. There are also News portals collecting news from many news sites. However, the news from personal sites and blogs are not always categorized. Categorization is needed to help readers receive news according to their interests. To answer this problem, this study concentrates to categorize news written in Indonesian language. The method used is One-Against-One Support Vector Machine (SVM) which is able to categorize more than two categories. SVM is also the best method for categorization. Before entering categorization process, this system must undergo a study process first. This process study starts with preprocess, which are extracting news from HTML file, tokenization, stemming using Porter Stemmer, Feature Selection, representation of vector. After all preprocess, SVM will go to the study step. The testing process also needs a preprocess step before testing using One-against-one SVM. This study achieves a median of 86.67% for the accuration of categorization from 150 documents of sports, automotive, and technology news.

Keywords: categorization, news, One-Against-One Support Vector Machine, SVM

--------------------------------------------------------------------------------------------------------------------------------------------

1. INTRODUCTION

Nowadays, the growth of internet users is increasingly rapid so that the spread of information in cyberspace is also increasing. The dissemination of information does not only come from official news sites but also unofficial news sites such as blogs and personal sites. As a reader, of course you want to get as much news information as possible and according to your wishes, therefore readers need some kind of filter to categorize incoming news according to the desired category. If categorization is done manually, of course it will be very time consuming, so research is needed where the system can learn to categorize news automatically based on learning results.

By looking at the problems above, the main focus studied in this research is on time optimization in the classification or categorization of online news on a news provider site. There is no longer a need for a manual process of determining news categories but can be done automatically by a system that has been previously trained.

Supervised classification is a method of object recognition with human assistance that teaches the system to make choices. By using the training data, supervised classification will categorize the incoming data. Currently, the most popular and considered the best supervised classification method is Support Vector Machine (SVM). Based on research by Thorsten Joachims which compared the performance of k-NN, Naive Bayes, Rocchio, C 4.5 and Support Vector Machine (SVM), it was concluded that the SVM algorithm had better accuracy compared to other algorithms [JOA99]. Based on this research, the author chose to use the SVM algorithm for the process of categorizing Indonesian language news in this final assignment.

2.TEXT CATEGORIZATION

Support Vector Machine (SVM) requires learning data to be able to carry out categorization. Learning data is in the form of vectors that represent news documents. However, to get to this learning stage, SVM requires a process that converts documents in the form of HTML files into vector form. This stage will be called the preprocessing stage.

2.1 Preprocess

Preprocessing is the stage where the HTML document will be converted into vector. The preprocessing stage consists of several stages as follows:

2.1.1 Extraction

At this stage, documents in the form of files will be entered into the system so they can be processed. After the document has been successfully saved into the system, the document will be cleaned of other attributes outside the document content, such as other attributes that are not related to the document content.

2.1.2 Tokenization

Tokenization is the stage of breaking sentences into tokens. One token does not have to be one word because it is very possible for one token to consist of two or more words (phrases). However, in this study, the author was limited not to use phrase handling. For example, if a document contains the following sentence:

Tabel 1 Sentence before the tokenization process

Hari ini, Bandung dilindungi oleh polisi

So the tokenization results of the document are:

Tabel 2 Results of the tokenization process

hari

ini

Bandung

dilindungi

oleh

polisi

2.1.3 Stemming

The stemming process uses the Indonesian Porter Stemmer algorithm developed by Fadillah Z. Tala [8]. The Stemming process is carried out according to the flowchart as follows:

2.1.4 Feature Selection using TFIDF

TF-IDF is a combination of the two Term Frequency (TF) methods with the Inverse Document Frequency (IDF) method. Term Frequency (TF) is a method of calculating weights based on the number of occurrences of a word (term) in one document. TF has the following equation [3]:

(1.1)

IDF uses the following calculation method [3]:

(1.2)

The weight of a word (term) is calculated by calculating the logarithm of the number of documents (N) divided by the number of documents containing that word (term) (df_t).

(1.3)

The TF-IDF weight is calculated by multiplying the TF weight (TF_t,d) by the IDF weight (IDF_t) (see equation 1.3) to obtain the combined weight of the TF-IDF [3].

3. SUPPORT VECTOR MACHINE

The learning process using SVM will use the following equation:

(1.4)

Where:

•   x_i  : Input vector

•   y_i: class

•   : transpose vector of the normal plane vector (n), which lies outside the hyperplane lines.

•     b: position relative to the center coordinates

Calculations and b can be done with the following equation [3]:

   (1.5)

   (1.6)

However, a value of  is needed to get . The value of  is obtained by maximizing the Lagrangian equation as below [3]:

   (1.7)

Provided that the following equation must be met:

   (1.8)

   (1.9)

After obtaining the value of , the values of and b can be calculated using the equations in 1.5 and 1.6.

The categorization process is carried out using the equation:

   (1.10)

The  value obtained is compared with 1 and -1, if  then the news document falls into the negative class category, if  then the document falls into the positive class category and if the document being tested does not fit into both categories, then the category of the document is unknown.

3.1 One-Against-One

The One-against-one method sometimes also called "pairwise coupling", "all pairs" or "round robin", has the concept of building one SVM for each pair of classes. This method will build  models of k binary categorization classes and k>1. [6]

4. SYSTEM PLANNING

In this chapter, the author will explain how the author will build a workforce recommendation system application.

4.1 Learning System Design using SVM

The testing process will start with the preprocessing stage then continue with learning using SVM. The learning process will use two sources, namely news from kompas.com and vivanews.com. In the preprocessing stage, the selection of keywords to represent the document is done using keyword meta-tags in the HTML document. The keyword selection process is carried out by taking one keyword in each document that has the highest TFIDF weight. The following is a flowchart for the learning process using SVM:

The learning process is carried out by getting vectors based on keywords and looking for alpha values, vector weight and bias. The keyword vector, alpha value, vector weight and bias will be saved to the learning database for the testing process.

4.2Categorization System Design Using One-Against-One SVM

The categorization process uses learning result data using SVM. The categorization process will use two sources, namely news from kompas.com and vivanews.com. The following is a flowchart of news categorization using SVM 1-vs-1:

This categorization process also uses a preprocessing stage first. However, different from the preprocessing stage in learning, this categorization preprocessing does not use keyword meta tags to search for keywords, but directly searches for words contained in the learning keyword vector.

5. SYSTEM TESTING AND RESULTS

This chapter will explain the testing of the categorization system application using SVM One-Against-One accompanied by an analysis of the test results obtained by the author.

5.1 Testing on 50 documents in the Automotive category

The test results on 50 documents have an accuracy rate of 90% because they contain errors in 5 files, namely data 4, 22, 24 and 27. This is because the vector process has a tendency towards documents in the sports category compared to automotive.

File Name	System Categorization Results
04	Sport
22	Sport
24	Sport
27	Sport

Table 3: Mistake in categorization of news in the automotive category

The news document with file name 04 received an error in determining the category because the document contained the word racing (can be seen in table 1 row 2 column 3) which is a keyword for documents in the sports category. This causes the document to be categorized as a sports news document.

Apart from the document named 04, there are 3 other documents that have an error in determining the category. Similar to news 04, news documents 22, 24, and 27 also have the same causal factor, namely keywords that do not refer to automotive documents. However, if you pay attention, the keyword for these three news stories is Facebook, which should be more directed towards news in the technology category. This error probably occurred because during the process of separating the two classes (technology and sports) the training data was not good so that the word Facebook with a certain weight fell into the sports category.

5.2 Testing on 50 documents in the Technology category

Testing 50 documents in the technology category produced 44 documents in the technology news category and 6 unknown documents so that the test results for 50 documents in the technology category had an accuracy rate of 88%.

File Name	System Categorization Results
Broadcast.Promosi.SMS.Premium.Dihentikan	Unknown
Toko.Aplikasi.Microsoft.Siap.Sambut.Aplikasi.Open.Source.	Unknown
Yahoo.Kembali.Tolak.Microsoft	Unknown
Yahoo.Lebih.Tertarik.Google.Ketimbang.Microsoft.	Unknown
Yahoo.Putuskan.Tolak.Microsoft	Unknown
Yahoo.Resmi.Tolak.Microsoft	Unknown

Table 4: Mistakes in categorization of news in the technology category

It can be seen in table 2 that this error was caused because the 6 news documents did not have keywords that matched any category, so they were not categorized.

5.3 Testing on 50 documents in the Sports category

Test results on 50 documents in the sports category had a lower level of accuracy, namely 82% because 5 news items were incorrectly categorized, and 4 news documents were unknown.

File Name	System Categorization Results
2014.Yamaha.Target.Bawa.Pebalap.Indonesia.ke.Moto2	Automotive
Abaikan.Rossi.Lorenzo.Lihat.Ancaman.baru	Technology
Allegri.Milan.Kian.Solid	Unknown
Alonso.Tampil.Fantastis.dan.Tercepat	Technology
Rossi.Akan.Bergaya.Timnas.Italia	Technology
The.Doctor.Masih.Eksis	Automotive
Turnamen.Tenis.AHM.Cup.Digelar.di.Kemayoran	Technology
Van.Basten.Messi.Akan.Raih.FIFA.Ballon.d.Or	Unknown
Veron.Belum.Mau.Pergi	Unknown

Table 5: Mistakes in categorization of news in the sports category

Categorization errors in this test are caused by two factors, namely news documents that have keywords for categories that they should not have and news documents that do not have the right keywords for the three types of categories.

The news document entitled “2014. Yamaha. Target. Bring. Racer. Indonesia. to. Moto2" has the keyword "Yamaha, which is a keyword intended for documents in the automotive category, so this document is considered to be in the automotive category.

The news document entitled "Veron.Belum.Want.Go" does not have any keywords that fit into the three categories, so the document category is Unknown.

5.4 Analysis of Test Results

The testing process went well with an average level of accuracy of 86.67%. This is influenced by several determining factors that determine success in the categorization process, namely determining the hyperplane, learning data and selecting keywords for a document.

6. CONCLUSIONS AND SUGGESTIONS

The conclusions obtained are as follows:

1.   The average categorization accuracy was 86.67% obtained from testing 50 documents from the technology, sports and automotive categories. The 13.33% category error was caused by several factors, namely errors in determining keywords for news documents and errors in learning data and news documents that did not have keywords for any category.

2.   The preprocessing stage is important to develop in order to reduce the number of dimensions and obtain keywords that better represent the content of the document.

3.   Document representation is not very good if it only uses one keyword because usually one document has more than one keyword that represents the document.

4.   The process of extracting keywords from the keyword meta tag is considered quite good if the keyword meta tag is indeed the document's keyword. However, in news sourced from vivanews, the keyword meta tag is filled not only with keywords but also with the news title and other sentences reviewed by the author which do not represent the document so that the learning outcomes are also less good.

The suggestions obtained are as follows:

1.   Maximizing the keyword selection process in preprocessing so that keywords become more representative. For example, if the keyword for a technology document entitled "Finally service provider X uses 4G technology" is the word "service", then the word service is a word that is considered influential for the technology category. Even though the word "service" is still too general to represent technology. This can cause errors in the categorization process. If there is a document in the automotive category entitled "After sales service for brand Y vehicles is very satisfactory", then it is very possible for the document to be included in the technology category if the document has a frequency of the word "service" that is in line with the technology category boundaries.

2.   Using other methods such as one-against-all or DAGSVM which are expected to increase the level of categorization accuracy also reduces the level of the categorization process.

3.   Find a way to use practice documents without limitations. In this study, the number of training documents was limited to 64 training documents because the data type used was "long", which could only handle data lengths of .

4.   Using news content as a search for learning keywords, no longer using meta keyword tags

5.   Finding a way to reduce the dimensionality of SVMs without having to reduce categorization accuracy. For example, by finding a way to get a representation of one document from various keywords but still producing only one dimension of the document so that.

7. REFERENCE

[1]Agusta, Ledy. “Perbandingan Algoritma Stemming Porter dengan Algoritma Nazief & Adriani Untuk Stemming Dokumen Teks Bahasa Indonesia”. Universitas Kristen Satya Wacana. [2009]

[2]Mahinovs,Aigarsdan Tiwari , Ashutosh (2007). “Text Classification Method Review”. Cranfield University. [2007]

[3]Manning , Christopher D. ; Raghavan, Prabhakar ; Schütze, Hinrich. “An Introduction to Information Retrieval”. Cambridge University. [2009]

[4]Mihalcea, Rada and Radev, Dragomir. http://clair.si.umich.edu/~radev/tut06/tut.pdf [2006]

[5]Sebastiani , Fabrizio (2002). “Text Categorization”. University of Padova

[6]Sembiring, Krisantus (September 2007), “Penerapan Teknik Support Vector Machine untuk Pendeteksian Intrusi pada Jaringan ”. Sekolah Teknik Elektro dan Informatika, ITB .

[7]Joachims, Thorsten (1999). “Text Categorization with Support Vector Machines: Learning with Many Relevant Features”. University Dortmund.

[8]Tala, Fadillah Z. (2003). “A Study of Stemming Effects on Information Retrieval in Bahasa Indonesia”. Institute for Logic, Language and Computation Universeit Van Amsterdam.