Extracting salient information from discarded features via attribute selection and pruning

Extracting salient information from discarded features via attribute selection and pruning Antonio J. Tallón-Ballesteros 1* , Sung-Bae Cho 2 1 Department of Languages and Computer Systems, University of Seville, Seville, Spain 2 Department of Computer Science, Graduate School of Artificial Intelligence, Yonsei University, Seoul, Korea Abstract This paper introduces a novel two-step proposal for attribute subset selection. The first step is able to extract handy information from non-selected features after an initial feature subset selection to be added to the preliminary subset selected; for this step the feature subset selector relies on the Correlation-based Feature Selection (CFS). The second step tries to prune the solution given that in the first step some extra attributes out of initially non-selected features have been added to the relevant features; the ultimate goal of this pruning is to optimise the attribute subset prior to conduct a classification task. In accordance with the experimental results, the simplification of solutions is effective since an improvement takes place in most of the cases where the new method does determine some attributes to be removed. Some performance measures are reported within a test bed composed of a good number of binary and multi-class classification problems. Comparisons with other attribute selection procedures such as CFS, Fast Correlation-based Feature Selection and Gain Ratio revealed that the new approach is very competitive and may be taken into account by the data preparation community. Keywords Classification, feature selection, data mining, data preparation, discarded attributes, pruning 1. I NTRODUCTION Data Engineering (DE) is generally considered to be a central issue in the development of data mining applications [1]. The goal of DE is to put quality data on the hands of users [2]. Characteristics of problems play an important role in knowledge and data engineering applications since their solutions are clearly dependent. Problems can be classified according to three factors such as a) the completeness of knowledge or data in the environment, b) the accuracy of knowledge or data available in the environment and c) the knowledge about the objective and/or requirements of the problem at hand [3]. The core procedures inside Machine Learning are categorised into Supervised Learning, Unsupervised Learning and Reinforcement Learning methods. The most widespread paradigm is Supervised Machine Learning (SML) [4]. This contribution focuses on SML where the objects are featured by the values for the properties and a label value * Corresponding author. Tel: +34 954556237; fax: +34 954557139. Email address: [email protected] (A.J. Tallón-Ballesteros). is present in every sample [5]. Data Mining (DM) comprises three parts [6]: a) Data Preparation (DP), b) Data Surveying (DS) and c) Data Modelling. Figure 1 depicts the DM activities. DP also called Preparing the Data for modelling prepares data and also prepares the miner so that when using prepared data, the miner produces better models, faster; it cleans the records and also applies any kind of reduction at level of instances, features or classes; the results of this phase are training and testing sets. DS also called Surveying the data goals to look at the general structure and reports whether or not there is a useful amount of information enfolded in the data set about various areas; it tries to study the problem or even to detect some initial noise or inconsistencies on the data; it is conducted by a domain expert. Data Modelling involves a fundamental matter where the miner applies any modelling tool to produce a predictive model. Figure 1.- Data Mining steps. DP consumes approximately 60% of the total DE effort and is therefore a hot research topic [6]. It includes the tasks of data selection, data reorganisation, data exploration, data cleaning, and data transformation [7]. This paper pays special attention to Feature Selection (FS) which falls in the category of data selection. The pre-requirement to apply attribute selection is empty in the sense that having a few features in a problem is enough to carry out a data pre-processing task. In the past years, many publications with a very small input attribute space have been very useful to put on the table the necessity of feature selection such as [8], [9], [10] where some problems with three, four or eight initial properties (haberman, iris and pima data sets) are undergone attribute selection. Nowadays the number of features is on the rise due to use of many sensors and the very low cost of information storage. Another matter is how effective the solution to conduct a further learning procedure can be. As stated by very recent studies, a couple of features or even a single one may not be enough to foresee effectively on new, unseen data [11] with general purpose classifiers. Another issue is the case of single variable classifiers where the type of purpose is different and only one variable is necessary [12]. Feature selection can also be conducted to represent only important information about a particular situation in a 2D or 3D plot. In addition, other times the solution with feature selection may not be very accurate since there are many fields where real data are collected concerning scientific applications and, at the beginning, the purpose of the data gathering is not clearly in mind and some values may not be stored due to measure failures or even the quality and smartness of data not being the main goal [13]. This paper aims at optimising the attribute subset obtained with an advanced feature selection procedure [14]. The way to optimise is based on characteristics space pruning of the baseline solution. To do that, an attribute subset approach operating with a learning algorithm is run as an additional preparation phase on the solution initially reached; the important matter is that the target classifier is different from the inner learning method applied to optimise the solution. Moreover, the family of prediction models belongs to another approach to conduct a fair and unbiased study. As a result, the desirable end is to get more accurate models to predict with unknown samples. The scope of the proposed research falls into SML for classification tasks. The research question is motivated by the fact that a single Feature Subset Selector (FSS) may not be able to capture properly all the relationships among different attributes; to overcome this shortcoming Feature Subset Selection is populated with some extra attributes which are those selected applying a FSS to the discarded features in the first Feature Selection. The augmented solution contains essential and important features; although both are going to operate cooperatively, it is very likely that some attributes could be dropped without degrading the classifier performance. The contribution of this paper lies in the incorporation of a semi-wrapper FSS to optimise the baseline solution which is built with the application of an advanced Attribute Subset Selection (ASS) based on the classical Correlation-based Feature Selection proposed two decades ago. The fundamental motivation for using a semi-wrapper is its speed and acceptable performance compared to a wrapper. The rest of this manuscript is organised as follows. Section 2 reviews some concepts about attribute selection. Section 3 describes in detail the proposed method. Section 4 depicts the test bed and the experimentation framework. Section 5 shows the results for the experiments conducted to confirm the usefulness of the proposal. Section 6 states the concluding remarks and introduces future research lines. 2. A TTRIBUTE SELECTION One of the cornerstones of DP is generating a data set smaller than the original one. Attribute Selection (AS) is a way for selecting relevant data via discarding some attributes that may not be very promising in terms of predictability [15]. The benefits of the AS application are varied and probably an increase in the model simplicity and the predictive power are the two of utmost importance. There are two main perspectives to perform AS: filters and wrappers. The former only makes use of inner properties of the data to determine any relationship between the attribute values and the associated label. The latter is guided by an induction learning to help pick up the highest quality solutions. From another point of view, any AS approach may be divided into attribute ranking (AR) or attribute subset selection (ASS) depending on whether the procedure output is an ordered list or a subset [16]. Clearly, the computation time to get a score for every attribute is much more reduced than testing and assessing different combinations which includes typically as the first step getting an initial list and then picking one element and adding some of the subsequent elements of the list following a search strategy. AR is a linear complexity problem whereas ASS is a combinatorial problem that requires higher computational costs that may be an exponential time complexity for exhaustive search or a quadratic one for heuristic search. Additionally, the ASS can be integrated within a wrapper and the running time may be a critical burden. Going further, the solutions provided by wrapper are too specific and therefore their applicability narrower. In the context of ASS, there is a very wide literature covering different search methods and different metrics to assess the subsets of attributes. It should be mentioned the complete review by B. Xue et al. which was published a few years ago and included more than two hundred references and is a very up-to- date survey of the state-of-the-art for ASS with heuristic-based approaches [17]. AR only requires a measure to analyse the dispersion, correlation, mutual information (also called entropy), chi-squared statistics, symmetrical uncertainty, etc. of the data where the attributes are projected one at a time along with the class label. A novelty work combines simultaneously AS with discretization techniques conducting experiments with some AR methods [18]. In accordance with a recent survey [19], current FS techniques primarily concentrate on obtaining relevant attributes. ASS is a branch of AS with the highest number of publications within the data mining community probably due to its good performance. The most widespread method is Correlation-based feature Selection (CFS) [20] which incorporates a Best First search along with a correlation measure to assess the quality of the subsets. The usual is to discard non-selected attributes and to only include the selected attributes to train the supervised machine learning model. A new proposal introduced the application of an ASS method even to the non-selected attributes and in a subsequent step the selected attributes from the original training set and the selected ones from the non-selected initially are merged and are the input to the classification algorithm [14]. From a different perspective, FS may be tackled with static FS and streaming FS: in the former the original data do not change over the time and in the latter new features may be added to the original data [21]. 3. T HE PROPOSED METHOD This paper presents a method to optimise the solution reached by an advanced attribute subset selection procedure by means of CFS; the reason of this choice is motivated by the fact that CFS is considered a very powerful method all over the data mining community and it counts with around two thousands and eight hundreds citations according to scholar google (http://scholar.google.com) at the moment of this paper submission. CFS considers the hypothesis that good attribute subsets contain attributes with a high correlation with the label, yet uncorrelated with each other [20]. The starting point is the initial solution which is submitted to an additional CFS with a different characteristic space; both attribute sets are merged and we call it baseline scenario. The new approach carries out an additional attribute subset selection with Boruta algorithm [22]. Boruta applies Random Forest (RF) classifier to determine all-relevant feature subset from problems and is designed as a wrapper approach. There are some advantages to apply RF [23] as the engine of the wrapper such the number of parameters to be set up is very small [22] and the classification performance is very good. Boruta arises from the spirit of RF and hence adding randomness to the system several; basically, only variables whose importance is higher than that of the randomised variables are considered important. Furthermore, RF runs are performed several times computing the importance of all attributes [22]. The operation of Boruta [24] is as follows: i) it evaluates the relevance of variable in the input data by comparing the importance measured by RF for original attributes with that obtained for the random features added in an artificial fashion; to do that, it trains RF on the problem extended with random contrast attributes, obtained by shuffling randomly values of original features between instances, ii) for every feature, it is tested if its importance is higher than the maximal importance achieved by any contrast attribute; in order to obtain statistically significant results the procedure is looped several times, with contrast variables generated independently for each iteration. Technically, Boruta is a wrapper method. Nonetheless, this contribution does not consider RF as the target classifier and therefore we can state that Boruta is applied as a semi-wrapper FS method [25]. Thus, the proposed method mixes an advanced attribute selection procedure based on a sophisticated application of CFS with Boruta as a semi-wrapper and thus the new approach falls into a new type of attribute selection procedure that we may call hybrid filter and semi-wrapper attribute subset selection. Moreover, this paper considers as target classifiers some induction algorithms belonging to strategies that do not follow decision trees specially to analyse the convenience of the proposed method as a general attribute subset selection framework. The rationale to conduct Boruta only with an initial tentative good quality solution is to diminish the computational cost and at the same time to study if some attributes can be safely discarded because the initial solution is bigger than the solution with the application of CFS only once. Thus, Boruta is used as an optimiser. The advantages of using a classifier to assess the quality of a solution are the higher accuracy and also that a type of classification algorithm has been applied before carrying out the learning phase with unseen data. Figure 2 portrays the proposed method composed of two parts. The first phase called advanced attribute selection performs a feature subset selection via CFS in two sequential steps (double CFS), considering the original training data and the complementary reduced training data as inputs of the aforementioned steps, respectively. The second phase named optimisation takes the combination of the solutions achieved by each of the selections conduced in the first phase and tries to optimise the solution via Boruta algorithm which makes use of RF to assess the solution quality. With regard to the sketch, any classifier may be used for the subsequent learning process although this paper only evaluates the solution reached with learning algorithms which do not fall within the category of inductive decision trees. The performance of baseline and optimised scenarios are going to be compared and it may help to measure the behaviour of our proposal. Figure 3 presents the pseudo-code of the proposal. In the first phase, two attribute subsets via CFS are obtained and conveniently combined since there is no overlapping; the most relevant of the non-selected attributes are retained for a further processing. In the second phase an optimisation of the solution obtained in the first step takes place via Boruta algorithm. In the specialised literature there are a few attempts to address a two-stage attribute selection. A twophase approach applying an embedded method based on Support Vector Machines Recursive Feature Elimination (SVM-RFE) is proposed in [26]. More recently, S. Jadhav et al. [27] presented a method conducting a Feature Ranking followed by a wrapper approach in credit rating context. In 2020, P. K. Theodorikis and D. C. Gkikas [28] describe a model based on a wrapper approach combined with decision trees although no empirical analysis is conducted. 4. E XPERIMENTATION SETTING Table 1 gives details about the test bed to assess the proposed method which is composed of ten binary and multiple class problems. The data sets are very interesting since they represent complex real-world or challenge problems; most of them are available at the international well-known repository from the University of California at Irvine [29], MADELON has been introduced in NIPS 2003 challenge [30] and STAD that stands for STomach Adenocarcinoma is a problem from Bioinformatics [31]. There are six multiple class data sets and the remaining are binary, throwing an average of 4.4 classes. The size in terms of instances varies from 100 to 19020. The attribute space size goes from 9 to 500. Last column presents the Attribute-to-label ratio to provide a measure between the attribute space size and the number of labels which may be interpreted as a measure of how much attributes are required from every label on average; this measure is reported throughout this contribution and enables us to get a measure about the simplification and eventual optimisation that the proposal has reached with an extra quantitative value. The experimental design follows a stratified holdout procedure [32] with three and one quarters for the training and testing set, respectively. There are some particular cases where the problems were pre-arranged and we keep on this distribution; some examples are Led24 [33], SPECTF [34] and vowel [35]. Table 2 enumerates the approaches used within the proposed method in the phases 1 and 2 along with a brief characterization and also including their setting and last column represents the target classifiers. The results obtained after the double CFS are considered as the baseline ones and those raised after the application of both stages, named double CFS and Boruta, are the optimised results. Concerning the technology for developing the proposed framework we have used some visual tools [36] such as Weka (Waikato Environment for Knowledge Analysis) [37] and RStudio [38] which are written in Java and R programming languages. Figure 2.- The proposal framework: Advanced attribute selection and optimisation. Pseudo-code 1. Advanced attribute selection and optimisation Phase 1: Advanced Attribute Selection Require: training_instances Output: training_attribute_space SA  CFS (training_instances); nonSA  attributes (training_instances) minus SA; SA2  CFS (nonSA); training_attribute_space  SA ∪ SA2; // baseline scenario Phase 2: Optimisation Require: baseline_attribute_space Output: unnecessary, optimised taxonomy_of_attributes  Boruta (baseline_attribute_space); optimised  taxonomy_of_attributes.important; unnecesary  taxonomy_of_attributes.unimportant; // optimised scenario Figure 3.- Pseudo-code of the proposal Advanced attribute selection and optimisation. For CFS and Boruta, the implementations of Weka and R package Boruta [39] within RStudio have been used, respectively. The target classifiers are k-Nearest Neighbour (since in this contribution k=1, it is referred as to 1NN) [40] which is based on the nearest neighbour rule, PART which is a method to obtain rules from PARtial decision Trees [41] and Naïve Bayes (NB) [42], which is supported by the Bayes Theorem, have been run under Weka framework. We have set up the AS and learning algorithms with the default parameters that are those suggested by the own authors of the algorithms. Table 3 represents the number of attributes in the initial situation, after applying the first phase of the proposed method (baseline scenario) and after being conducted fully the new proposal. It is worth mentioning that in some cases, the proposal is not able to reduce the solution reached with the advanced attribute selection which may mean the high quality of it. Last column reports the attribute-to-label ratio of the baseline and optimised situations; concerning the numerical values, we can see that, on average, around 3 or 4 attributes for every label are required to conduct the learning process. In addition, no more than eight features per class are required for binary problems and no more than six attributes, per label too, to cope with multiple class data sets. Furthermore, the number of unnecessary features from the baseline solution ranges from 1 to 5 in the cases where is possible to optimise the solution. In general terms, the theoretical lower bound for the selected attributes is one; from an empirical point of view, the practical lower bound to get reliable results is two [10]. Table 4 illustrates a reduction analysis on data sets where the proposed method is able to optimise the solution with the baseline approach. The reduction percentage with the baseline strategy is very remarkable with values from 18.2 to 96.8 with an average of 64.1. Moreover, the optimisation can reduce even a bit more the baseline solutions with improvements that fluctuate from 0.8% to 14.3% raising an average of 5.9. The important news are the difference between 100% and the reported value on column labelled Optimised over initial which is the global optimisation measure, raising numbers from 2.0% (100.0%-98.0% for AID1608) to 81.3% (100.0%-22.7% for CTG) and an average of 29.9% (100.0%-70.1% for the whole test bed) which represents the percentage of needed features from the full data set. Consequently, only the problems that have been shown in Table 4 are going to be dealt with hereinafter. As performance measures the accuracy and Cohen’s kappa have been chosen to evaluate the models obtained by the classification models, once the classifiers are trained. Cohen’s kappa measure is of special interest for multi-class problems [43]. Accuracy is a very well-known measure to score the number of hits divided by the number of samples to be assessed. Cohen’s kappa is a convenient alternative measure since it compensates for random hits [44]. Given that all the considered attribute selection methods and classifiers are non-stochastic algorithms, the number of runs is one and the test result is reported on the forthcoming tables. Table 1. Test bed summary Data set #Instances #Attributes #Labels Attribute-to-label ratio Total Training Testing AID1608 1033 827 206 152 2 76.0 B. tissue 106 81 25 9 6 1.5 CTG 2126 1594 532 22 3 7.3 Led24 3200 200 3000 24 10 2.4 MADELON 2000 1500 500 500 2 250.0 magic 19020 14265 4755 10 2 5.0 SPECTF 267 80 187 44 2 22.0 STAD 100 75 25 14 3 4.7 Waveform 5000 3750 1250 40 3 13.3 Vowel 990 528 462 11 11 1.0 Average 3384.2 2290.0 1094.2 82.6 4.4 38.3 Range 100-19020 75-14265 25-4755 9-500 2-11 1-250 Table 2. Attribute selection methods and classifiers Name Type Parameter Value Target classifier Correlation based Feature Selection (CFS) Filter Attribute evaluation measure Correlation 1NN, PART and NB Type of search Best first Consecutive expanded nodes without improving 5 Direction of search Forward Boruta Semi-wrapper Classifier to assess optimisation Random forest 1NN, PART and NB 5. R ESULTS This section illustrates the results for the baseline and optimised scenarios with three classifiers, which are described in Section 4, and two performance measures with baseline and optimised reduced testing instances. Lastly, we present the results with other additional attribute selection methods together with a global plot of them for the two assessment metrics reported in this paper. 5.1. Results for the baseline and optimised scenarios The results obtained for the baseline (only phase 1 is done) and optimised (this proposal, where phases 1 and 2 are conducted) scenarios for different classifiers are presented. The improvement values have been highlighted in italics. Table 5 presents the results obtained with 1NN classifier. The accuracy has been enhanced in five out of six problems with an average improvement of 5.23. Cohen’s kappa is increased on average 0.0902 which means a 9%. A tie happens in CTG although the optimisation is interesting given that an attribute that has been featured unnecessary according to Boruta is also unnecessary in accordance with the results and the model at the end is simpler and faster to train. 1NN classifier takes important advantages with the proposal and may improve the typical storage problems that suffer classifiers based on nearest neighbours. MADELON has improved outstandingly and has passed from an accuracy of 71.00% to 83.60%. Table 6 reports the performance of the proposed method with PART. The progress now takes place in three out of six problems and the improvements are a bit lower than with 1NN. The ties go for AID1608, CTG and SPECTF. The number of attributes in AID1608 has been divided by two which represents an important reduction in terms of complexity and the final attribute space is able to keep the results. In SPECTF a quarter of the feature space has been discarded which is very remarkable. CTG has been mentioned with the previous classifier though now the accuracy and Cohen’s kappa are higher than with 1NN which may mean that could be an improvement margin with 1NN classifier probably with another optimiser. Table 7 exhibits the results obtained with NB classifier. The number of wins is four out of six. There is one tie and one loss. The loss is the first time that has happened with the proposal and perhaps may indicate that the semi-wrapper approach based on RF is not a very suitable option for NB or even that the SPECTF problem requires a further analysis and any noise may be present in the data. The average is improved only 1.46% in accuracy and 0.0263 in Cohen’s kappa which is lower than with PART even though now there is one extra win and one tie has been changed to loss. MADELON has resulted in a tie although it is positive since the reduction in the attribute space is around a quarter. Table 3. Selected Attributes in the baseline scenario and with the Proposed Approach along with the attribute-to-label ratio Data set #Attributes #Labels Attribute-to-label ratio Initial Baseline Optimised Unnecessary Initial Baseline Optimised AID1608 152 6 3 3 2 76.0 3.0 1.5 B. tissue 9 8 8 - 6 1.5 1.3 1.3 CTG 22 18 17 1 3 7.3 6.0 5.7 Led24 24 7 7 - 10 2.4 0.7 0.7 MADELON 500 16 12 4 2 250.0 8.0 6.0 magic 10 6 6 - 2 5.0 3.0 3.0 SPECTF 44 20 15 5 2 22.0 10.0 7.5 STAD 14 5 3 2 3 4.7 1.7 1.0 Waveform 40 18 17 1 3 13.3 6.0 5.7 Vowel 11 10 10 - 11 1.0 0.9 0.9 Average 82.6 11.4 9.8 2.7 4.4 38.3 4.1 3.3 Range 9-500 5-20 3-17 1-5 2-11 1-250 0.7-10.0 0.7-7.5 5.2. Results obtained with various attribute selection procedures A comparison applying the current proposal (advanced attribute selection and optimisation; it is also referred as to optimised -scenario-), Fast Correlation-based Feature Selection (FCBF) [45] which is an information [41] E. Frank, and I. H. Witten. "Generating accurate rule sets without global optimization." (1998). [42] P. Langley, W. Iba, and K. Thompson. "An analysis of Bayesian classifiers." Aaai. Vol. 90. 1992, pp. 223-228. [43] A. J. Tallón-Ballesteros, and J. C. Riquelme. "Data Mining Methods Applied to a Digital Forensics Task for Supervised Machine Learning." Computational Intelligence in Digital Forensics: Forensic Investigation and Applications. Springer, Cham, 2014. 413-428. [44] J. Cohen. "A coefficient of agreement for nominal scales." Educational and psychological measurement 20.1 (1960): 37-46. [45] L. Yu, and H. Liu. "Feature selection for high-dimensional data: A fast correlation-based filter solution." Proceedings of the 20th international conference on machine learning (ICML-03). 2003, pp. 856-863 [46] J. R. Quinlan, and J. Ross. "Induction of decision trees." Machine learning 1.1 (1986): 81-106. Figure 4.- Test accuracy plot with global results for our approach (Optimised) compared to three attribute selection procedures for three classifiers. Classification data set 0,00 10,00 20,00 30,00 40,00 50,00 60,00 70,00 80,00 90,00 100,00 FCBF CFS GainRatio Optimised FCBF CFS GainRatio Optimised FCBF CFS GainRatio Optimised FCBF CFS GainRatio Optimised FCBF CFS GainRatio Optimised FCBF CFS GainRatio Optimised FCBF CFS GainRatio Optimised AID1608 CTG MADELON SPECTF STAD Waveform Average 1NN PART NB Test accuracy Figure 5.- Test Cohen’s kappa plot with global results for our approach (Optimised) compared to three attribute selection procedures for three classifiers Classification data set Test Cohen's kappa -0,1000 0,0000 0,1000 0,2000 0,3000 0,4000 0,5000 0,6000 0,7000 0,8000 0,9000 1,0000 FCBF CFS GainRatio Optimised FCBF CFS GainRatio Optimised FCBF CFS GainRatio Optimised FCBF CFS GainRatio Optimised FCBF CFS GainRatio Optimised FCBF CFS GainRatio Optimised FCBF CFS GainRatio Optimised AID1608 CTG MADELON SPECTF STAD Waveform Average 1NN PART NB