This paper introduces a hybrid method for textual data classification. The goal of this paper is to improve classification accuracy of method presented in our previous work by integrating to it k-Means method for decreasing training dataset and particle swarm optimization metaheuristic for a linear support vector machine parameter tuning. The paper reports that the introduced method is characterized by higher improvements in all effectiveness metrics than the methods presented in our previous works.
Textual data analysis became a very popular since people started using Internet, to be more concrete when e-shops, social networks, Blogs etc., where people can write their comments, appeared. This area is considered as a very challenging -although a lot of work has been done in this field, accuracy is still rather average due to comments, slang, smiles etc. A Support Vector Machine (SVM) is one of the most widely used method which has proved its efficiency in different tasks and domains. It is very flexible to parameter tuning, as well as internal modifications, which allows to improve its performance and accuracy. However, despite all advantages, typical for SVM algorithm is, that it is characterized by slow performance in the big data arrays. The higher number of features is, the longer computation time it requires. There have been a number of efforts to speed up SVM, and most of them focus on reduction of the training set [15,18,22]. One of the most widely known and promising method for that is k-Means [5,8,23], which can be used as standalone method or in combination with others. Aforementioned authors conclude, that properly selected training data can improve executing time with no losing or similar accuracy. Increasing accuracy is another common problem. Particle swarm optimization (PSO) is a very promising option [9,11,16]. One of its strengths is combination with other evolutionary methods. Its efficiency is also proved in SVM parameter selection tasks [6,10,21].
Motivated by these improvements, this paper proposes a hybrid method for textual data classification, which is suitable to work with large datasets. The proposed hybrid method is a combination of three methods: SVM, k-Means and PSO, which are integrated into SpeedUP method, earlier presented in [12]. Standalone SpeedUP method increased SVM classification speed, while slightly lost to ordinary SVM method in terms of accuracy [12]. Considering on it, were proposed two separate methods for improving classification accuracy: k-Means method in [13] -for training data reduction and PSO in [14] -for finding the best cost (penalty) parameter for SVM. Both aforementioned methods still lost to ordinary SVM, when are used separately, so it led to conclusion of possibility to combine these methods. The rest of the paper is organized as follows. Section 2 introduces the methods which were used in the experiments and proposed method is described, whereas Section 3 gives a description of datasets and experimental settings used to evaluate proposed approach, together with results obtained during experimenting. Finally, Section 4 outlines the conclusions.
This section shortly presents the methods relevant to research presented in this paper: Support Vector Machine [1,2,4], k-Means [17], Particle Swarm Optimization [3] and Term Frequency -Inverse Document Frequency (TF-IDF) [20]. The brief description of a proposed hybrid method, also presented herein.
TF-IDF Since machine learning algorithms cannot work with text data directly, it should be converted into vector of numbers. TF-IDF works by determining the relative frequency of words in a specific document compared to the inverse proportion of that word over the entire document corpus. This calculation determines how relevant a given word is in particular document. TfidfVectorizer module from scikit-learn [19] library is used to implement TF-IDF.
Support Vector Machine Herein is used linear SVM (LSVM), which is optimized for large-scale learning. LinearSVC module from scikit-learn [19] library is used to implement LSVM.
The main idea of this method is to partition the input dataset into k clusters, represented by adaptively-changing centroids. k-Means computes the squared distances between the input data points and centroids, and assigns inputs to the nearest centroid. KMeans module from scikit-learn [19] library used to implement k-Means method.
Particle Swarm Optimization It is a population-based stochastic metaheuristic algorithm for solving continuous and discrete optimization problems. Herein is used global best variant, which was manually programmed using Python language and adopted for LSVM parameter tuning for textual data classification tasks.
The proposed hybrid method (LSVM P SO km 30K SpeedUP ) is a combination of three methods: SVM, k-Means and PSO, which are integrated into SpeedUP method. The main idea of it is to reduce training dataset size regarding to subset size. Thus the testing dataset is split into equal subsets and the size of training data is calculated on the basis of the first subset size. k-Means and PSO methods are used for increasing accuracy of SpeedUP. 1. Before passing to SpeedUP method, training and testing datasets are preprocessed. Preprocessing contains two actions: text preprocessing and data cleaning. Text preprocessing includes actions like converting to lowercase, removing redundant tokens such as hashtag, symbols @, numbers, "http" for links, punctuation symbols, usernames etc. Data cleaning performs dataset checking for empty strings and removing them. 2. Depending on Subset size , function f (x) calculates training data size and number of sets for k-Means method. 3. Selected training data is converted into vector of numbers with TF-IDF and passed to k-Means method for the selection of the best training data for SpeedUP method, which is performed depending on results R(km i ). 4. The best training data selected is converted into vector of numbers with TF-IDF and passed to PSO method, which returns the best C value for LSVM.
After, the same training data is passed into LSVM. LSVM is trained with it and parameter C is set to one, which is returned from PSO method. 5. Depending on Subset size testing dataset is dividing into subsets td 1 , td 2 etc.
(function y(x)). 6. Subsets are converted into vector of numbers with TF-IDF and are passed to LSVM algorithm one by one and achieved results are stored in separate sets r 1 -for td 1 , r 2 -for td 2 etc. 7. The results are combined into one result set -Results.
In this paper are used two existing labeled datasets available: The Stanford Twitter sentiment corpus (sentiment1401 ) dataset and Amazon customer reviews dataset2 . The Stanford Twitter sentiment corpus dataset is introduced in [7] and contains 1.6 million tweets automatically labeled as positive or negative based on emotions. The dataset is split to 70% (1.12M tweets) for training and 30% (480K tweets) for testing. Amazon customer reviews dataset contains 4 million reviews and star ratings; it was also split to select 70% (2.8M reviews) entries for training and 30% (1.2M reviews) for testing.
The main goal of this research is to improve classification accuracy of method 30K SpeedUP introduced in [12] by integrating k-Means (km 30K SpeedUP ) and PSO (LSVM P SO 30K SpeedUP ) methods presented respectively in [13] and [14], also to compare the aforementioned methods with proposed method by performing comparative analysis between them. Two experiments are performed to reach the goal: one experiment with the Stanford Twitter sentiment corpus dataset (sentiment140) and second experiment with Amazon customer reviews dataset (Amazon reviews). Table 1 shows the sizes of training and testing data for LSVM input. It is assumed that the testing subset size should be 30K instances (30%), then training data calculated dependently on subset size is 70K instances (70%). All testing data is divided into subsets containing 30K instances (the last subset is the remainder and it could contain less than 30K instances). Python programming language and scikit-learn [19] library for machine learning were used to implement and evaluate the proposed method.
Computer with processor Intel(R) Core(TM) i7-4712MQ CPU 2.30 GHz and 16.00 GB installed memory (RAM) is used for experiments.
Effectiveness is measured using statistical measures: accuracy (ACC), precision (PPV -positive predictive value and NPV -negative predictive value), recall (TPR --true positive rate and TNR --true negative rate) and F 1 score (harmonic mean of PPV and TPR).
Two experiments were performed to evaluate the effectiveness of proposed method in terms of accuracy, precision, recall and F 1 score. Table 2 presents averaged results for proposed method in comparison with 30K SpeedUP, km 30K SpeedUP and LSVM P SO 30K SpeedUP. It is worth to mention, that all experiments were redone by using the same training and testing datasets for all methods, so they can be different from results in previous works. Also k-Means method from previous work was implemented without SVM tuning part, because it is a part of PSO method. The results clearly show, that LSVM P SO km 30K SpeedUP performs better compared with 30K SpeedUP method -1.02%, km 30K SpeedUP -0.80% and LSVM P SO 30K SpeedUP -0.22%, when applied on sentiment140 dataset. In the case of Amazon reviews dataset the proposed hybrid method also performs better compared with 30K SpeedUP -0.86% and km 30K SpeedUP -0.71%, while slightly lost (0.01%) to LSVM P SO 30K SpeedUP.
Other metrics in terms of -PPV, NPV, TPR, TNR, F 1 score -also show the superiority of the proposed method compared with previously introduced methods on sentiment140 dataset, while LSVM P SO 30K SpeedUP slightly outperform it in term of TNR. In the case of Amazon reviews dataset the proposed hybrid method perform better in terms of -NPV, TPR, while slightly lost to LSVM P SO 30K SpeedUP in terms of -PPV, TNR.
The main advantage of the proposed hybrid method is that training data selection is performed with k-Means method, which ensure the variety of the training data and could positively affect PSO metaheuristics choice in finding the best cost parameter C for LSVM. When training data is selected randomly, there is a risk, that training data will contain the same data or data will be not useful and this could negatively affect accuracy in different runs; therefore, multiple runs are required for more objective results, which is affecting classification speed. The proposed method increased the classification accuracy, without minor losses in classification speed to compare with previously presented methods. It is also proved that by using only 70,000 instances for training the proposed hybrid method can classify much bigger testing datasets (starting from 480K, 1.2M etc.) with minor losses in accuracy.
Acknowledgments. I would like to thank my supervisor Prof. Dr. Gintautas Garšva for support and advices.