Feature selection methods, as a preprocessing step to machine learning, are effective in reducing dimensionality, removing irrelevant data, increasing learning accuracy, and improving result comprehensibility. However, the recent increase of dimensionality of data poses a severe challenge to many existing feature selection methods with respect to the efficiency and effectiveness. In this work, we introduce a novel concept, relevant feature selection based on information gathered from decision rule models. A new measure for a feature rank based on the feature frequency and rule quality is additionally defined. The efficiency and effectiveness of our method is demonstrated through exemplary use of five real-world datasets. Six different classification algorithms were used to measure the quality of learning models built on original features and on selected features.
In the era of the acquisition of vast amounts of data, different domain information databases, efficient analysis and retrieval of regularity have become an extremely important task. The issue of classification and object recognition is applied in many fields of human activity. Data mining is fraught with many aspects which hinder it, like a very large number of observations, too many attributes, the insignificance of the part of variables for the classification process, mutual interdependence of conditional variables, the simultaneous presence of variables with different types, the presence of undefined values of variables, the presence of erroneous values of the variables, uneven distribution of categories for the target variable. Thus, the development of efficient methods for significant feature selection is valid.
Feature selection (FS) methods are frequently used as a preprocessing step to machine learning experiments. An FS method can be defined as a process of choosing a subset of original features so that the feature space is optimally reduced according to a certain evaluation criterion. Feature selection has been a fruitful field of research and development since 1970's and it has been proven to be effective in removing irrelevant features, increasing efficiency in learning tasks, improving learning performance like predictive accuracy, and enhancing comprehensibility of the learned results [1].
The feature selection methods are typically divided into three classes based on how they combine the selection algorithm and the model building: filter, wrapper and embedded FS methods. Filter methods select features with respect to the model. They are based only on general features like the correlation with the variable to be predicted. These methods select only the most interesting variables. Then, a selected subset will be a part of the classification model. Such methods are effective in computation time and robust to overfitting [2]. However, some redundant, but relevant features can remain unrecognized. In turn, wrapper methods evaluate subsets of features which allow to detect the possible interactions between variables [1, 3]. However, the increase in overfitting risk, when the number of observations is insufficient, is possible. Additionally, the significant computation time, when the number of variables is large, highly increases. The third type, called embedded methods, is intended for reducing the classification of learning. Methods in this group try to combine the advantages of both methods mentioned previously. Thus, the learning algorithm takes advantage of its own variable selection algorithm. Therefore, it needs to know initially what a good selection is, which limits its exploitation [4].
Kohavi and John [1] observed that there are several definitions of relevance that may be contradictory and misleading. They proposed two degrees of relevance (strong and weak) that are required to encompass all notions usually associated with this term. In their approach the relevance is defined in the absolute terms, with the help of the ideal Bayes classifier. In this context, a feature X is strongly relevant when removal of X alone from the data always results in deterioration of the prediction accuracy of the ideal Bayes classifier. In turn, a feature X is weakly relevant if it is not strongly relevant and there exists a subset of features S, such that the performance of the ideal Bayes classifier on S is worse than the performance on S ∪ {X}. A feature is irrelevant if it is neither strongly nor weakly relevant.
Nilsson et al. [5] introduced the formal definition of two different feature selection problems:
1. Minimal Optimal Feature Selection (MOFS) consisting in identification of minimal set of features to obtain the optimal quality of classification.
, where the problem is to find all the variables that may, under certain conditions, improve the classification.
There are two important differences between these problems. The first one is detection of attributes with low importance (ARFS) [6], which may be completely obscured by other, more important attributes, from the point of view of the classifier (MOFS). The second difference is to find the boundary between the variables poorly, but realistically related to the decision and those for which such a relation is created as a result of random fluctuations. The formal definition of the problem of all relevant feature selection (ARFS) as a distinct problem from the classical minimal optimal feature selection (MOFS), was proposed recently in 2007 [5].
In our research, we used the contrast variable concept to distinguish between relevant and irrelevant features [6]. It is a variable that does not carry information on the decision variable by design that is added to the system in order to discern relevant and irrelevant variables. Here, it is obtained from the real variables by random permutation of values between objects. The use of contrast variables was, for the first time, proposed by Stoppiglia et al. [7] and then by Tuv et al. [8].
During experiments the following general procedure was applied: In the first step, a dataset as well as a feature for investigation were defined. Then, different ranking measures were applied to estimate importance of each feature. In order to check specificity of the feature selection, the dataset was extended by adding contrast variables. It means that each original variable was duplicated and its values were randomly permuted between all objects. Hence, a set of non-informative by design shadow variables was added to original variables. The variables that were selected as important more significantly than random, were examined further, using different tests. To define the level of feature importance, six well-known ranking measures were applied: ReliefF, Information Gain, Gain Ratio, Gini Index, SVM weight, and RandomForest. Additionally, our new measure, called RQualityFS, was introduced. It is based on the frequency of presence of different feature in a rule model generated from an original dataset and it also takes into consideration the quality of the rules in which this feature occurs. Rank quality of the i-th feature could be presented as follow:
where n is a number of rules inside the model, Q Rj defines the classification quality of the rule R j and {A i } describes the presence of the i-th attribute, usually it is equal to 1 (the feature occurred) or to 0 (the feature did not occur).
In turn, the quality of the rule is defined as follows:
where E corr depicts a number of correctly matched learning objects by the j-th rule and E incorr depicts a number of incorrectly matched learning objects by this rule.
During the second step, a test probing the importance of variables was performed by analyzing the influence of variables used for model building on the prediction quality. Six different machine learning algorithms were applied to build different predictors for the original set of features and for selected features: Classification Tree (CT), Random Forest (RF), CN2 decision rules algorithm (CN2), Naive Bayes (NB), k-Nearest Neighbors (kNN), and Support Vector Machine (SVM). During this step, a 10-fold cross validation paradigm was used. Ten known evaluation measures were uti-lized in each predictor: Classification Accuracy (CA), Sensitivity, Specificity, Area Under ROC curve (AUC), Information Score (IS), F1 score (F1), Precision, Brier measure, Matthew Coefficient Correlation (MCC) parameter, and finally Informadness (Inform.) ratio [9].
Our initial investigations focus on applying the developed algorithm on several re-alworld datasets. Five datasets have been used during experiments. Four of them are gathered from the UCI ML repository, while the fifth set has been developed earlier by the authors [10]. A summary of datasets is presented in Table 1. These datasets have diverse numbers of objects, features and their types as well as classes.
To illustrate the proposed methodology, only results for Breast cancer datasets will be presented in details. The first step of the experiment revealed six features, that were recommended as important by all or almost all ranking measures. In Table 2, we can observe that deg-malig, node-caps, irradiat, inv-nodes, breast, and menopause features create a stable and core set of features which have the highest values of seven measures of importance, particularly using RQualityFS measure, introduced in our investigation.
In the same table, comparison with importance of contrast values (italic rows and contrast index) is also presented. The most important contrast feature is tumor-size (contrast) for which RQualityFS measure, defined earlier, is equal to 2.34. In this way, we also treated a threshold that separates the core, relevant set of attributes from other less informative attributes. Most of the measures (except SVM weight) used in this approach show that the selected set of features has higher values of these parameters than the gathered threshold value (underlined values). These values are denoted in bold style in Table 2. Hereby, we can observe that different measures give different thresholds. -0.01 0.00 0.00 0.00 0.00 -0.16 0.86 (contrast) breast-quad 0.07 0.00 0.00 0.00 0.03 -0.05 0.00 (contrast) inv-nodes -0.02 0.02 0.02 0.01 0.14 0.07 0.00 (contrast) node-caps -0.04 0.00 0.00 0.00 0.02 -0.03 0.00 (contrast) breast-quad -0.05 0.01 0.01 0.00 0.16 0.13 0.00
The second step of the experiment was devoted to evaluation of prediction of the quality of utilized machine learning algorithms described in Section 2. During this step, six different algorithms were applied using the 10-fold cross validation method. The average results for the Breast cancer dataset are shown in Figure 1. This procedure was utilized for two specified sets: