VIEWS: 13 PAGES: 7 POSTED ON: 5/7/2013
in recent years the importance of finding a meaningful pattern from huge datasets has become more challenging. Data miners try to adopt innovative methods to face this problem by applying feature selection methods. In this paper we propose a new hybrid method in which we use a combination of resampling, filtering the sample domain and wrapper subset evaluation method with genetic search to reduce dimensions of Lung-Cancer dataset that we received from UCI Repository of Machine Learning databases. Finally, we apply some well- known classification algorithms (Na�ve Bayes, Logistic, Multilayer Perceptron, Best First Decision Tree and JRIP) to the resulting dataset and compare the results and prediction rates before and after the application of our feature selection method on that dataset. The results show a substantial rogress in the average performance of five classification algorithms simultaneously and the classification error for these classifiers decreases considerably. The experiments also show that this method outperforms other feature selection methods with a lower cost. Keywords-Feature Selection; Reliable Features; Lung-Cancer; Classification Algorithms.
World of Computer Science and Information Technology Journal (WCSIT) ISSN: 2221-0741 Vol. 3, No. 4, 70-76, 2013 Improving Performance of a Group of Classification Algorithms Using Resampling and Feature Selection Mehdi Naseriparsa Amir-masoud Bidgoli Islamic Azad University, Tehran North Branch Islamic Azad University, Tehran North Branch Department Of Computer Engineering MIEEE Manchester University Tehran, Iran Tehran, Iran Touraj Varaee Islamic Azad University, Tehran North Branch Tehran, Iran Abstract— In recent years the importance of finding a meaningful pattern from huge datasets has become more challenging. Data miners try to adopt innovative methods to face this problem by applying feature selection methods. In this paper we propose a new hybrid method in which we use a combination of resampling, filtering the sample domain and wrapper subset evaluation method with genetic search to reduce dimensions of Lung-Cancer dataset that we received from UCI Repository of Machine Learning databases. Finally, we apply some well- known classification algorithms (Naïve Bayes, Logistic, Multilayer Perceptron, Best First Decision Tree and JRIP) to the resulting dataset and compare the results and prediction rates before and after the application of our feature selection method on that dataset. The results show a substantial progress in the average performance of five classification algorithms simultaneously and the classification error for these classifiers decreases considerably. The experiments also show that this method outperforms other feature selection methods with a lower cost. Keywords-Feature Selection; Reliable Features; Lung-Cancer; Classification Algorithms. class data. The algorithm performed well on two kind of I. INTRODUCTION cancers. Fayyad tried to adopt a method to seek effective Data mining seeks to discover unrecognized associations features of dataset by applying a fitness function to the between data items in an existing database. It is the process of attributes. Bidgoli and Naseriparsa proposed a hybrid extracting valid, previously unseen or unknown, feature selection method by combination of resampling, chi- comprehensible information from large databases. The growth squared and consistency evaluation techniques. of the size of data and number of existing databases exceeds Most of the feature selection methods just focus on the ability of humans to analyze this data, which creates both a improving one specific classification algorithm performance. In need and an opportunity to extract knowledge from databases this paper, we try to improve a group of classification . algorithms performance by combining sample domain filtering, Assareh proposed a hybrid random model for resampling and feature subset evaluation methods. We test the classification that uses the subspace and domain of the samples performance of the group of classification algorithms on Lung- to increase the diversity in the classification process. Cancer dataset. Hayward showed that data preprocessing by choosing In section II, III, IV, V, and VI we focus on the definition of suitable features will develop the performance of classification feature selection, SMOTE, wrapper method, information gain algorithms. In another attempt Duangsoithong and Windeatt  presented a method for reducing dimensionality in the datasets and genetic algorithm which are used in our proposed method. which have huge amount of attributes and few samples. In section VII, we describe our hybrid method and explain the Dhiraj used clustering and K-mean algorithm to show the two phases involved in the feature selection process. In section efficiency of this method on huge amount of data. Xiang VIII, the experiments conditions and results are presented. In proposed a hybrid feature selection algorithm that takes the section IX the proposed method is tested and performance benefit of symmetrical uncertainty and genetic algorithms. evaluation parameters are calculated. Conclusions are given in Zhou presented a new approach for classification of multi section X. 70 WCSIT 3 (4), 70 -76, 2013 II. FEATURE SELECTION subset selection algorithm conducts a search for a good subset Feature selection includes conversion of the main dataset to using the induction algorithm itself as part of the evaluation a new dataset and simultaneously reducing dimensionality by function. The accuracy of the induced classifiers is estimated extracting the most suitable features. Conversion and using accuracy estimation techniques . Wrappers are dimensionality reduction will result in a better understanding of hypothesis driven. They assign some values to weight vectors, the existing patterns in the dataset and more reliable and compare the performance of a learning algorithm with classification by observing the most important data which different weight vector. In wrapper method, the weights of keeps the maximum properties of the main data. Feature features are determined by how well the specific feature selection consists of four basic steps (Figure 1): subset settings perform in classification learning. The algorithm generation, subset evaluation, stopping criterion, and result iteratively adjust feature weights based on its performance. validation . V. INFORMATION GAIN The information gain of a given attribute X with respect to the Starting Set class attribute Y is the reduction in uncertainty about the value of Y when we know the value of X. The uncertainty about the value of Y is measured by its entropy, H(Y). The uncertainty about the value of Y when we know the value of X is given by the conditional entropy of Y given X, H(Y|X). the formula is Subset shown in equation 1 : Evaluation Generation (1) IG is a symmetrical measure . The information gained about Y after observing X is equal to the information gained about X after observing Y. No Stopping Criteria VI. GENETIC ALGORITHM The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that is based on natural selection, the process that drives biological evolution . Yes The genetic algorithm uses three main types of rules at each Validation step to create the next generation from the current population: Selection rules select the individuals, called parents, Figure. 1 Feature selection structure that contribute to the population at the next generation. Crossover rules combine two parents to form children III. SMOTE: SYNTHETIC MINORITY OVER-SAMPLING for the next generation. TECHNIQUE Mutation rules apply random changes to individual Often real world datasets are predominantly composed of parents to form children. normal examples with only a small percentage of abnormal or interesting examples. It is also the case that the cost of misclassifying an abnormal example as a normal example is VII. DEFINITION OF THE PROPOSED METHOD often much higher than the cost of the reverse error. Under sampling of the majority (normal) class has been proposed as a A. First phase good means of increasing the sensitivity of a classifier to the In the first step, the SMOTE technique is applied on the minority class. By combination of over-sampling the minority original dataset to increase the samples of the minority class. (abnormal) class and under-sampling the majority (normal) This step contributes to make a more diverse and balanced class, the classifiers can achieve better performance than only dataset. In the second step, sample domain filtering method is under-sampling the majority class. SMOTE adopts an over- applied on the resulting dataset to refine the dataset and omit sampling approach in which the minority class is over-sampled the unreliable samples which are misclassified by the learning by creating synthetic examples rather than by over-sampling algorithm. The learning algorithm for filtering is Naïve Bayes. with replacement . Naïve Bayes eliminates misclassified samples which are added to the dataset during the resampling process by a low IV. WRAPPER METHOD computational cost. In the wrapper approach, the feature subset selection is Finally, the original dataset is merged with the secondary done using the induction algorithm as a black box. The feature dataset. The resulting dataset keeps all the samples of the 71 WCSIT 3 (4), 70 -76, 2013 original dataset and also has some additional samples which algorithms. The initial state of the classification algorithms is contribute to improve accuracy and performance of a group of the default state of WEKA software. In table1, GA parameters classifiers. are set as follows: Crossover Probability is the probability that two population members will exchange genetic material and is set to 0.6. Max Generations parameter show the number of generations to evaluate and is set to 20. Mutation Probability is Initial Dataset the probability of mutation occurring and is set to 0.033 and the last parameter is the number of individuals (attribute sets) in the population that is set to 20. TABLE I. INITIAL STATES OF GENETIC ALGORITHM Resampling and Parameter Value Filtering Crossover Probability 0.6 Max Generations 20 Mutation Probability 0.033 Refined Dataset Population Size 20 B. Performance Evaluation Parameters Definition In table 2, the name and index of the classification algorithms that are used in our experiment are shown. Final Dataset TABLE II.INDEX AND NAME OF THE CLASSIFICATION ALGORITHMS Index Classification Algorithm Name Figure 2 Steps of the first phase 1 Naïve Bayes B. Second Phase 2 Logistic Regression 3 Multilayer Perceptron In the second phase, we focus on the feature space to reach the best subset that results in the best accuracy and 4 BF Tree performance for the group of classification algorithms. 5 JRIP Actually, feature space analysis is carried out in two steps. In the first step, a feature space filtering method is adopted to In our experiments, we define some parameters to evaluate our reduce the feature space and prepare the conditions for the next feature selection method. The first parameter, is the number of step. Information gain is a filtering method which uses entropy misclassified samples and we call it MS. metric to rank the features and is used for the first filtering step. The next parameter, is the average number of misclassified At the end of this step the features with the ranks higher than samples of Lung-Cancer dataset on which the classification the threshold are selected for the next round. algorithms applied and we call it AMS. This parameter shows the efficiency of the feature selection method more In the second step, wrapper feature selection with genetic realistically. AMS parameter formula is shown in equation 2 search is carried out on the remaining feature subset. Naïve as: Bayes is chosen as the learning algorithm for wrapper feature selection. The initial population for genetic search is set by the (2) order of features which has been defined by Information gain in the previous step. The features are chosen at the end of this phase are considered as the reliable features. In equation 2, MSi, is the number of misclassified samples of Lung-Cancer dataset for a specific classification algorithm. VIII. EMPIRICAL STUDY N is the number of classification algorithms which are applied on Lung-Cancer dataset in the experiment. A. Experimenatl Conditions The third parameter is the relative absolute error of the To evaluate our feature selection method, we choose Lung- classification algorithms applied on Lung-Cancer dataset and Cancer dataset from UCI Repository of Machine Learning we show it by RAE. databases  and apply 5 important classification algorithms The next parameter is the average relative absolute error before and after implementation of our feature selection  of the classification on Lung-Cancer dataset and we call it method. Lung-Cancer dataset contains 56 features and 32 ARAE. This parameter shows how a feature selection method samples which is classified into three groups. The data could affect the classification algorithms not to predict wrongly described 3 types of pathological lung cancers. or at least their predictions are closer to the correct values. We use WEKA data mining tool to simulate our proposed ARAE parameter formula is shown in equation 3 as: method and evaluate the performance of classification 72 WCSIT 3 (4), 70 -76, 2013 (3) IX. PERFORMANCE EVALUATION 25 In equation 3, RAEi is the relative absolute error of a specific classification algorithm which is applied on Lung- 20 PM Cancer dataset. N is the number of classification algorithms 15 GW GC which are applied on Lung-Cancer dataset in the experiment. MS SGW 10 The next parameters are about correctly and incorrectly IG classification rates  for Lung-Cancer dataset. True positive 5 AF rate is the rate of correctly classified samples that belong to a specific class in Lung-Cancer dataset and we show it by 0 NB LOG MLP BFT JRIP TPRatei. True negative rate is the rate of correctly classified Classifier Nam e samples that do not belong to a specific class in Lung-Cancer dataset and we show it by TNRatei. False positive rate is the Figure 3 Number of misclassified samples from applying the rate of incorrectly classified samples that do not belong to a group of classification algorithms on Lung-Cancer dataset specific class in Lung-Cancer dataset and we show it by FPRatei. False negative rate is the rate of incorrectly classified As it is shown in figure 3, MS parameter is calculated for 5 samples that belong to a specific class in Lung-Cancer dataset classification algorithms (Naïve Bayes, Logistic Regression, and we show it by FNRatei. The average true positive, true Multilayer Perceptron, BF Tree, JRIP) and compared with negative, false positive and false negative are shown in figures different feature selection methods(GA-Wrapper, GA- 4-7. Classifier, Symmetrical Uncertainty-GA-Wrapper, Information Gain, All Features). The number of misclassified samples decreases for the group of classifiers when our hybrid feature (4) selection method is applied on Lung-Cancer dataset. 100 90 80 (5) 70 PM GW 60 RAE GC 50 SGW 40 IG 30 AlF (6) 20 10 0 NB LOG MLP BFT JRIP Classifier Name (7) Figure 4 Relative Absolute Error from applying the group of classification algorithms on Lung-Cancer dataset In equations 4-7, TPRatei, TNRatei, FPRatei and FNRatei are As it is shown in figure 4, RAE parameter is calculated for true positive, true negative, false positive and false negative 5 classification algorithms and compared with different feature for a specific classification algorithm which is applied on the selection methods (GA-Wrapper, GA-Classifier, Symmetrical Lung-Cancer dataset respectively. N is the number of Uncertainty-GA-Wrapper, Information Gain, All Features). Classification algorithms which are applied on Lung-Cancer The classification error decreases considerably for the group of dataset in the experiment. classifiers when our hybrid feature selection method is applied on Lung-Cancer dataset. 73 WCSIT 3 (4), 70 -76, 2013 1 1 0.9 0.9 0.8 PM 0.8 PM 0.7 GW 0.7 GW TPRate 0.6 FNRate GC 0.6 GC 0.5 0.5 0.4 SGW SGW 0.4 0.3 IG IG 0.3 0.2 AF AF 0.2 0.1 0.1 0 0 NB LOG MLP BFT JRIP NB LOG MLP BFT JRIP Classifier Name Classifier Name Figure 5 True positive rate from applying the group of Figure 8 False negative rate from applying the group of classification algorithms on Lung-Cancer dataset classification algorithms on Lung-Cancer dataset From figure 7 and 8, FPRate and FNRate parameters are calculated for 5 classification algorithms and compared with 1 different feature selection methods (GA-Wrapper, GA- 0.9 Classifier, Symmetrical Uncertainty-GA-Wrapper, Information 0.8 PM 0.7 Gain, All Features).The rate of incorrectly classified samples GW 0.6 for the group of classification algorithms is below 0.2 when our TNRate GC 0.5 SGW hybrid feature selection method is applied on Lung-Cancer 0.4 IG dataset. This shows that our proposed method has decreased 0.3 0.2 AF the error of the classification process. 0.1 0 NB LOG MLP BFT JRIP 18 Classifier Name 16 14 12 Figure 6 True negative rate from applying the group of 10 AMS classification algorithms on Lung-Cancer dataset 8 From figure 5 and 6, TPRate and TNRate parameters are 6 calculated for 5 classification algorithms and compared with 4 different feature selection methods (GA-Wrapper, GA- 2 Classifier, Symmetrical Uncertainty-GA-Wrapper, Information 0 Gain, All Features).The rate of correctly classified samples for PM GW GC SGW IG AF the group of classification algorithms is above 0.86 when our Feature Selection Method hybrid feature selection method is applied on Lung-Cancer dataset. This shows that our proposed method has increased the accuracy of the classification process. Figure 9 AMS parameter values for different methods 0.4 0.35 In figure 9, we can see that the AMS parameter for the 0.3 PM group of classification algorithms is less than other feature GW 0.25 selection methods when our proposed method is applied on FPRate GC 0.2 SGW Lung-Cancer dataset. This shows that the proposed method is 0.15 IG able to improve the accuracy of the group of classifiers 0.1 AF simultaneously on Lung-Cancer dataset. 0.05 0 NB LOG MLP BFT JRIP Classifier Name Figure 7 False positive rate from applying the group of classification algorithms on Lung-Cancer dataset 74 WCSIT 3 (4), 70 -76, 2013 90 1 80 0.9 70 0.8 60 0.7 ATNRate 0.6 ARAE 50 0.5 40 0.4 30 0.3 20 0.2 10 0.1 0 0 PM GW GC SGW IG AF PM GW GC SGW IG AF Feature Selection Method Feature Selection Method Figure 10 ARAE parameter values for different methods Figure 12 ATNRate parameter values for different methods In figure 10, we can see that the ARAE parameter for the In figures 11 and 12, the ATPRate and ATNRate of the group of classification algorithms is less than 20 percent when group of classification algorithms which are applied on Lung- our proposed method is applied on Lung-Cancer dataset. This Cancer dataset are shown. For both figures, the true prediction shows that the proposed method is able to decrease the rate is above 0.9. This shows that the proposed method has classification error of the group of classification algorithms increased the true prediction rate of the group of classification simultaneously on Lung-Cancer dataset. algorithms on Lung-Cancer dataset comparing with other methods. 1 0.9 0.3 0.8 0.7 0.25 ATPRate 0.6 0.2 AFPRate 0.5 0.4 0.15 0.3 0.2 0.1 0.1 0.05 0 PM GW GC SGW IG AF 0 Feature Selection Method PM GW GC SGW IG AF Feature Selection Method Figure 11 ATPRate parameter values for different methods Figure 13 AFPRate parameter values for different methods 75 WCSIT 3 (4), 70 -76, 2013  J. Han and M. Kamber, Data Mining: Concepts and Techniques, Morgan Kaufmann, USA, 2001. 0.6  A. Assareh, M. Moradi and L.Gwenn Volkert, “A hybrid random subspace classifier fusion approach for protein mass spectra 0.5 classification”, Springer, LNCS, vol 4973, pp. 1–11, Heidelberg, 2008. 0.4 AFNRate  J. Hayward, S. Alvarez, C. Ruiz, M. Sullivan, J. Tseng and G. Whalen, “Knowledge discovery in clinical performance of cancer 0.3 patients, IEEE International Conference on Bioinformatics and Biomedicine”, USA, pp. 51–58, 2008. 0.2  R. Duangsoithong and T. Windeatt, “Relevance and Redundancy Analysis for Ensemble Classifiers”, Springer-Verlag, Berlin, 0.1 Heidelberg, 2009.  K. Dhiraj, S. Kumar and A. Pandey, “Gene Expression Analysis 0 Using Clustering”, 3rd international Conference Bioinformatics PM GW GC SGW IG AF and Biomedical Engineering, 2009.  B. Jiang, X. Ding, L. Ma, Y. He, T. Wang and W. Xie, “A Hybrid Feature Selection Method Feature Selection Algorithm: Combination of Symmetrical Uncertainty and Genetic Algorithms”, The Second International Symposium on Optimization and Systems Biology, pp. 152–157, Figure 14 AFNRate parameter values for different methods Lijiang, China, October 31– November 3, 2008.  J. Zhou, H. Peng and C. Suen, “Data-driven decomposition for In figures 13 and 14, the AFPRate and AFNRate of the multi-class classification”, Journal of Pattern Recognition, vol 41, group of classification algorithms which are applied on Lung- pp. 67 – 76, 2008.  U. Fayyad, G. Piatetsky-Shapiro and P. Smyth, “From Data Cancer dataset are shown. For both figures, the false prediction Mining A Knowledge Discovery in Databases”, American rate is below 0.1. This shows that the proposed method had Association for Artificial Intelligence, 1996. decreased the false prediction rate of the group of classification  A. Bidgoli and M. Naseriparsa, “A Hybrid Feature Selection by algorithm on Lung-Cancer dataset comparing with other Resampling, Chi-squared and Consistency Evaluation Techniques”, World Academy of Science, Engineering and methods. Technology, issue 68, pp. 60-69, 2012.  J. Novakovic, P. Strbac, D. Bulatovic, “Toward optimal feature From the figures above, we observe that the proposed selection using ranking methods and classification algorithms”, method achieves higher classification accuracy for the group of Yugoslav Journal of Operations Research, vol. 21, pp. 119-135, classification algorithms in comparison to other methods. 2011. Moreover, the cost of our proposed method is considerably  N. V. Chawla, K. W. Bowyer, L. O. Hall, and W. P. Kegelmeyer, "SMOTE: Synthetic Minority Over-sampling Technique," Journal smaller than the GA-Wrapper and GA-Classifier methods, of Artificial Intelligence Research, vol. 16, pp. 321-357, 2002. because it achieves higher level of dimensionality reduction.  R. Kohavi, G.H. John, “Wrappers for Feature Subset Selection”, Artificial Intelligence, vol 97, pp. 273-324, 1997.  J. Novakovic, “The Impact of Feature Selection on the Accuracy of X. CONCLUSION Naïve Bayes Classifier”, 18th Telecommunications Forum A hybrid feature selection method is proposed. This method TELFOR, pp. 1113-1116, November 23-25, Serbia, Belgrade, 2010. combines resampling and sample filtering with feature space  H. Randy and S. Haupt, Practical Genetic Algorithms, John Wiley filtering and wrapper methods. The first phase analyses and Sons, 1998. sample domain and in the second phase, feature space filtering  C.J. Mertz and P.M. Murphy, UCI Repository of machine learning eliminates irrelevant features and then wrapper method select databases, http://www.ics.uci.edu/~mlearn/MLRepository.html, University of California, 2013. reliable features with a lower cost and higher accuracy.  M. Dash, H.Liu, “Consistency-based Search in Feature Selection”, Different performance evaluation parameters are defined and Artificial Intelligence, vol 151, pp. 155-176, 2003. calculated on Lung-Cancer dataset. The results show that our  T.S. Chou, K.K. Yen, J. Luo, “Network Intrusion Detection Design proposed method outperforms other feature selection methods Using Feature Selection of Soft Computing Paradigms”, International Journal of Information and Mathematical Sciences, (GA-Wrapper, GA-Classifier, Symmetrical Uncertainty-GA- vol 4, pp. 196-208, 2008. Wrapper, Information Gain, All Features) on Lung-Cancer dataset. Furthermore, the proposed method improves the accuracy and true prediction rate of the group of classification algorithms simultaneously. REFERENCES 76
Pages to are hidden for
"Improving Performance of a Group of Classification Algorithms Using Resampling and Feature Selection"Please download to view full document