{'fraction_non_alphanumeric': 0.03351493582066895, 'fraction_numerical': 0.014741848971950007, 'mean_word_length': 4.633064133016627, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Feature Subset Selection Algorithm Automatic Recommendation Method

Many feature subset selection (FSS) algorithms have been proposed, but not all of them are appropriate for a given feature selection problem. At the same time, so far there is rarely a good way to choose appropriate FSS algorithms for the problem at hand. Thus, FSS algorithm automatic recommendation is very important and practically useful. In this paper, a meta learning based FSS algorithm automatic recommendation method is presented. The proposed method first identifies the data sets that are most similar to the one at hand by the k-nearest neighbor classification algorithm, and the distances among these data sets are calculated based on the commonly-used data set characteristics. Then, it ranks all the candidate FSS algorithms according to their performance on these similar data sets, and chooses the algorithms with best performance as the appropriate ones. The performance of the candidate FSS algorithms is evaluated by a multi-criteria metric that takes into account not only the classification accuracy over the selected features, but also the runtime of feature selection and the number of selected features. The proposed recommendation method is extensively tested on 115 real world data sets with 22 well-known and frequently-used different FSS algorithms for five representative classifiers. The results show the effectiveness of our proposed FSS algorithm recommendation method.

Although a large number of FSS algorithms have been proposed, there is no single algorithm which performs uniformly well on all feature selection problems. Experiments (Hall, 1999;Zhao & Liu, 2007) have confirmed that there could exist significant differences of performance (e.g., classification accuracy) among different FSS algorithms over a given data set. That means for a given data set, some FSS algorithms outperform others.
This raises a practical and very important question: which FSS algorithms should be picked up for a given data set? The common solution is to apply all candidate FSS algorithms to the given data set, and choose one with the best performance by the crossvalidation strategy. However, this solution is quite time-consuming especially for highdimensional data (Brodley, 1993).
For the purpose of addressing this problem in a more efficient way, in this paper, an FSS algorithm automatic recommendation method is proposed. The assumption underlying our proposed method is that the performance of an FSS algorithm on a data set is related to the characteristics of the data set. The rationality of this assumption can be demonstrated as follows: 1) Generally, when a new FSS algorithm is proposed, its performance needs to be extensively evaluated at least on real world data sets. However, the published FSS algorithms are rarely tested on the identical group of data sets (Hall, 1999;Zhao & Liu, 2007;Yu & Liu, 2003;Dash & Liu, 2003;Kononenko, 1994). That is, for any two algorithms, they are usually tested on the different data. This implies that the performance of an FSS algorithm biases to some data sets.
2) At the same time, the famous NFL (No Free Lunch) (Wolpert, 2001) theory tells us that, for a particular data set, different algorithms have different data-conditioned performance, and the performance differences vary with data sets.
The above evidences imply that there is a relationship between the performance of an FSS algorithm and the characteristics of data sets. In this paper, we intend to explore this relationship and utilize it to automatically recommend appropriate FSS algorithm(s) for a given data set. The recommendation process can be viewed as a specific application of meta-learning (Vilalta & Drissi, 2002;Brazdil, Carrier, Soares, & Vilalta, 2008) that has been used to recommend algorithms for classification problems (Ali & Smith, 2006;King, Feng, & Sutherland, 1995;Brazdil, Soares, & Da Costa, 2003;Kalousis, Gama, & Hilario, 2004;Smith-Miles, 2008;Song, Wang, & Wang, 2012).
To model this relationship, there are three fundamental issues to be considered: i) which features (often are referred to as meta-features) are used to characterize a data set; ii) how to evaluate the performance of an FSS algorithm and identify the applicable one(s) for a given data set; iii) how to recommend FSS algorithm(s) for a new data set.
In this paper, the meta-features, which are frequently used in meta-learning (Vilalta & Drissi, 2002;Ali & Smith, 2006;King et al., 1995;Brazdil et al., 2003;Castiello, Castellano, & Fanelli, 2005), are employed to characterize data sets. At the same time, a multi-criteria metric, which takes into account not only the classification accuracy of a classifier with an FSS algorithm but also the runtime of feature selection and the number of selected features, is used to evaluate the performance of the FSS algorithm. Meanwhile, a k -NN (k -Nearest Neighbor) based method is proposed to recommend FSS algorithm(s) for a new data set.
Our proposed FSS algorithm recommendation method has been extensively tested on 115 real world data sets with 22 well-known and frequently-used different FSS algorithms for five representative classifiers. The results show the effectiveness of our proposed recommendation method.
The rest of this paper is organized as follows. Section 2 introduces the preliminaries. Section 3 describes our proposed FSS algorithm recommendation method. Section 4 provides the experimental results. Section 5 conducts the sensitivity analysis of the number of the nearest data sets on the recommendation results. Finally, section 6 summarizes the work and draws some conclusions.

Preliminaries
In this section, we first describe the meta-features used to characterize data sets. Then, we introduce the multi-criteria evaluation metric used to measure the performance of FSS algorithms.

Meta-features of Data Sets
Our proposed FSS algorithm recommendation method is based on the relationship between the performance of FSS algorithms and the meta-features of data sets.
The recommendation can be viewed as a data mining problem, where the performance of FSS algorithms and the meta-features are the target function and the input variables, respectively. Due to the ubiquity of "Garbage In, Garbage Out" (Lee, Lu, Ling, & Ko, 1999) in the field of data mining, the selection of the meta-features is crucial for our proposed FSS recommendation method.
The meta-features are measures that are extracted from data sets and can be used to uniformly characterize different data sets, where the underlying properties are reflected. The meta-features should be not only conveniently and efficiently calculated, but also related to the performance of machine learning algorithms (Castiello et al., 2005).
There has been 15 years of research to study and improve on the meta-features proposed in the StatLog project (Michie, Spiegelhalter, & Taylor, 1994). A number of meta-features have been employed to characterize data sets (Brazdil et al., 2003;Castiello et al., 2005;Michie et al., 1994;Engels & Theusinger, 1998;Gama & Brazdil, 1995;Lindner & Studer, 1999;Sohn, 1999), and have been demonstrated working well in modeling the relationship between the characteristics of data sets and the performance (e.g., classification accuracy) of learning algorithms (Ali & Smith, 2006;King et al., 1995;Brazdil et al., 2003;Kalousis et al., 2004;Smith-Miles, 2008). As these meta-features do characterize data sets themselves, and have no connection with learning algorithms and their types, so we use them to model the relationship between data sets and FSS algorithms.
The most commonly used meta-features are established focusing on the following three aspects of a data set: i) general properties, ii) statistic-based properties, and iii) informationtheoretic based properties (Castiello et al., 2005).  In this section, first, the classical metrics evaluating the performance of FSS algorithm are introduced. Then, by analyzing the user requirements in practice application, based on these metrics, a new and user-oriented multi-criteria metric is proposed for FSS algorithm evaluation by combining these metrics together.

Classical Performance Metrics
When evaluating the performance of an FSS algorithm, the following three metrics are extensively used in feature selection literature: i) classification accuracy , ii) runtime of feature selection, and iii) number of selected features.
1) The classification accuracy (acc) of a classifier with the selected features can be used to measure how well the selected features describe a classification problem. This is because for a given data set, different feature subsets generally result in different classification accuracies. Thus, it is reasonable that the feature subset with higher classification accuracy has stronger capability of depicting the classification problem. The classification accuracy also reflects the ability of an FSS algorithm in identifying the salient features for learning.
2) The runtime (t) of feature selection measures the efficiency of an FSS algorithm for picking up the useful features. It is also viewed as a metric to measure the cost of feature selection. The longer the runtime, the higher the expenditure of feature selection.
3) The number of selected features (n) measures the simplicity of the feature selection results. If the classification accuracies with two FSS algorithms are similar, we usually favor the algorithm with fewer features.
Feature subset selection aims to improve the performance of learning algorithms which usually is measured with classification accuracy. The FSS algorithms with higher classification accuracy are in favor. However, this does not mean that the runtime and the number of selected features could be ignored. This can be explained by the following two considerations: 1) Suppose there are two different FSS algorithms A i and A j , and a given data set D. If the classification accuracy with A i on D is slightly greater than that with A j , but the runtime of A i and the number of features selected by A i are much greater than those of A j , then A j is often chosen.
2) Usually, we do not prefer to use the algorithms with higher accuracy but longer runtime, so is those with lower accuracy but shorter runtime. Therefore, we need a tradeoff between classification accuracy and the runtime of feature selection/the number of selected features. For example, in real-time systems, it is impossible to choose the algorithm with high time-consumption even if its classification accuracy is high.
Therefore, it is necessary to allow users making a user-oriented performance evaluation for different FSS algorithms. For this purpose, it is needed to address the problem of how to integrate classification accuracy with the runtime of feature selection and the number of selected features to obtain a unified metric. In this paper, we resort to the multi-criteria metric to explore this problem. The underlying reason lies that the multi-criteria metric has been successfully used to evaluate data mining algorithms by considering the positive properties (e.g. classification accuracy) and the negative ones (e.g. runtime and number of selected features) simultaneously (Nakhaeizadeh & Schnabl, 1997.
When comparing two algorithms, besides the metrics used to evaluate their performance, the ratio of the metric values can also be used. For example, suppose A 1 and A 2 are two different FSS algorithms, if A 1 is better than A 2 in terms of classification accuracy, i.e., acc 1 > acc 2 2 , then ratio acc 1 /acc 2 > 1 can be used to show A 1 is better than A 2 as well. On the contrary, for the negative metrics runtime of feature selection and number of of the selected features, the corresponding ratio < 1 means a better algorithm.
Actually, a multi-criteria metric adjusted ratio of ratios (ARR) (Brazdil et al., 2003), which combines classification accuracy and runtime together as a unified metric, has been proposed to evaluate the performance of a learning algorithm. We extend ARR by integrating it with the runtime of feature selection and the number of selected features, so a new multi-criteria metric EARR (extened ARR) is proposed. In the following discussion, we will show that the new metric EARR is more inclusive, very flexible, and easy to understand.

Multi-Criteria Metric EARR
Let DSet = {D 1 , D 2 , · · · , D N } be a set of N data sets, and ASet = {A 1 , A 2 , · · · , A M } be a set of M FSS algorithms. Suppose acc j i is the classification accuracy of a classifier with FSS algorithm A i on data set D j (1 ≤ i ≤ M , 1 ≤ j ≤ N ), and t j i and n j i denote the runtime and the number of selected features of FSS algorithm A i on data set D j , respectively. Then the EARR of A i to A j over D k is defined as where α and β are the user-predefined parameters which denote the relative importance of the runtime of feature selection and the number of selected features, respectively. The computation of the metric EARR is based on the ratios of the classical FSS algorithm performance metrics, the classification accuracy, the runtime of feature selection and 2. Where acc1 and acc2 are the corresponding classification accuracies of algorithms A1 and A2, respectively. the number of selected features. From the definition we can know that EARR evaluates an FSS algorithm by comparing it with another algorithm. This is reasonable since it is more objective to assert an algorithm is good or not by comparing it with another one instead of just focusing on its own performance. For example, suppose there is a classifier with 70% classification accuracy on a data set, we will get confused on whether the classifier is good or not. However, if we compare it with another classifier that can obtain 90% classification accuracy on the same data set, then we can definitely say that the first classifier is not good compared with the second one.
Noted that, in practice, the runtime difference between two different FSS algorithms usually can be quite great. Meanwhile, for high-dimensional data sets, the difference of the number of selected features for two different FSS algorithms can be great as well. Thus, the ratio of runtime and the ratio of the number of selected features usually have much more wide ranges than that of the classification accuracy. If the simple ratio of runtime and the simple ratio of the number of selected features are employed, they would dominate the value of EARR, and the ratio of the classification accuracy will be drowned. In order to avoid this situation, the common logarithm (i.e., the logarithm with base 10) of the ratio of runtime and the common logarithm of the ratio of the number of selected features are employed.
The parameters α and β represent the amount of classification accuracy that a user is willing to trade for a 10 times speedup/reduction on the runtime of feature selection/the number of selected features, respectively. This allows users to choose the algorithms with shorter runtime and less features but acceptable accuracy. This can be illustrated by the following example. Suppose that acc k i = (1 + α + β) · acc k j , the runtime of algorithm A i on a given data set is 10 times of that of A j (i.e., t k i = 10 · t k j ), and the number of selected features of algorithm A i is 10 times of that of A j (i.e., n k i = 10 · n k j ). Then, according to In this case, A j outperforms A i . If a user prefers fast algorithms with less features, A j will be his/her choice.
The value of EARR varies around 1. The value of EARR D k A i ,A j is greater than (or equal to, or smaller than) that of EARR D k A j ,A i indicates that A i is better than (or equal to, or worse than) A j .
Eq. (1) can be directly used to evaluate the performance of two different FSS algorithms. When comparing multiple FSS algorithms, the performance of any algorithm A i ∈ ASet on a given data set D can be evaluated by the metric EARR D A i defined as follows: This equation shows that the EARR of an FSS algorithm A i on D is the arithmetic mean of the EARR D A i ,A j of A i to other algorithm A j on D. That is, the performance of any FSS algorithm A i ∈ ASet is evaluated based on the comparisons with other algorithms in {ASet −{A i }}. The larger the value of EARR, the better the corresponding FSS algorithm on the given data set D.

FSS Algorithm Recommendation Method
In this section, we first give the framework of the FSS algorithm recommendation. Then, we introduce the nearest neighbor based recommendation method in detail.

Framework
Based on the assumption that there is a relationship between the performance of an FSS algorithm on a given data set and the data set characteristics (aka meta-features), our proposed recommendation method firstly constructs a meta-knowledge database consisting of data set meta-features and FSS algorithm performance. After that, with the help of the meta-knowledge database, a k-NN based method is used to model this relationship and recommend appropriate FSS algorithms for a new data set.
Therefore, our proposed recommendation method consists of two parts: Meta-knowledge Database Construction and FSS Algorithm Recommendation. Fig. 1   As mentioned previously, the meta-knowledge database consists of the meta-features of a set of historical data sets and the performance of a group of FSS algorithms on them. It is the foundation of our proposed recommendation method, and the effectiveness of the recommendations depends heavily on this database.
The meta-knowledge database is constructed by the following three steps. Firstly, the meta-features in Table 1 are extracted from each historical data set by the module "Metafeatures extraction". Then, each candidate FSS algorithm is applied on each historical data set. The classification accuracy, the runtime of feature selection and the number of selected features are recorded, and the corresponding value of the performance metric EARR is calculated. This is accomplished by the module "Performance metric calculation". Finally, for each data set, a tuple, which is composed of the meta-features and the values of the performance metric EARR for all the candidate FSS algorithms, is obtained and added into the knowledge database.

2) FSS Algorithm Recommendation
Based on the introduction of the first part "Meta-knowledge Database Construction" we presented above, the learning target of the meta-knowledge data is a set of EARR values instead of an appropriate FSS algorithm. In this case, it has been demonstrated that the researchers usually resort to the instance-based or k -NN (nearest neighbors) methods or their variations (Brazdil et al., 2003(Brazdil et al., , 2008 for algorithm recommendation. Thus, a k -NN based FSS algorithm recommendation procedure is proposed.
When recommending FSS algorithms for a new data set, firstly, the meta-features of this data set are extracted. Then, the distance between the new data set and each historical data set is calculated according to the meta-features. After that, its k nearest data sets are identified, and the EARR values of the candidate FSS algorithms on these k data sets are retrieved from the meta-knowledge database. Finally, all the candidate FSS algorithms are ranked according to these EARR values, where the algorithm with the highest EARR achieves the top rank, the one with the second highest EARR gets second rank, and so forth, and the top r algorithms are recommended.

Recommendation Method
To recommend appropriate FSS algorithms for a new data set D new based on its k nearest data sets, there are two foundational issues to be solved: i) how to identify its k nearest data sets, and ii) how to recommend appropriate FSS algorithms based on these k data sets.

1) k nearest data sets identification
The k nearest data sets of D new are identified by calculating the distance between D new and each historical data set based on their meta-features. The smaller the distance, the more similar the corresponding data set to D new .
In order to effectively calculate the distance between two data sets, the L 1 norm distance (Atkeson, Moore, & Schaal, 1997) is adopted since it is easy to understand and calculate, and its ability in measuring the similarity between two data sets has been demonstrated by Brazdil et al. (2003).
is the value of pth feature of F i and h is the length of the meta-features. The L 1 norm distance between data sets D i and D j can be formulated as It is worth noting that the ranges of different meta-features are quite different. For example, of the meta-features introduced in Table 1, the value of normalized class entropy varies from 0 to 1, while the number of instances can be millions. Thus, if these meta-features with different ranges are directly used to calculate the distance between two data sets, the metafeatures with large range would dominate the distance, and the meta-features with small range will be ignored. In order to avoid this problem, the 0-1 standardized method (Eq. (4)) is employed to make all the meta-features have the same range [0, 1].
is the value of the pth meta-feature of data set D i , min (f ·,p ) and max (f ·,p ) denote the minimum and maximum values of the pth meta-feature over historical data sets, respectively.

2) FSS algorithm recommendation
Once getting the k nearest data sets of D new , the performance of the candidate FSS algorithms on D new is evaluated according to those on the k nearest data sets. Then, the algorithms with the best performance are recommended.
Eq. (5) indicates that the performance of the FSS algorithm A i on D new is evaluated by its performance on the D knn of D new . For a data set D j ∈ D knn , the smaller the distance d j between itself and D new , the more similar the two data sets. This means for two data sets D p and D q , if d p < d q then the data set D p is more similar to D new , so the EARR of A i on D p is more important for evaluating the performance of A i on D new . Thus, the weighted average, which takes into account the relative importance of each data set in D knn rather than treating each data set equally, is employed. Moreover, in the domain of machine learning, the reciprocal of the distance usually is used to measure the similarity. So the According to the EARR of each candidate FSS algorithm in ASet on D new , a rank of these candidate FSS algorithms can be obtained. The greater the EARR, the higher the rank. Then, the top r (e.g., r = 3 in this paper) FSS algorithms are picked up as the appropriate ones for the new data set D new .
Procedure FSSAlgorithmRecommendation shows the pseudo-code of the recommendation. Time complexity. The recommendation procedure consists of two parts. In the first part (lines 1-3), the k nearest data sets of the given new data set D are identified. Firstly, the meta-features F of D are extracted by function MetaFeatureExtraction(). Then, the k-nearest historical data sets are identified by function NeighborRecognition() based on the distance between F and the meta-features F i of each historical data set D i . Suppose that P is the number of instances and Q is the number of features in the given data set D, the time complexity of function MetaFeatureExtraction() is O(P + Q). For function NeighborRecognition(), the time complexity is O(n) which depends on the number of the historical data sets n. Consequently, the time complexity of the first part is O(P +Q)+O(n).
In the second part (lines 4-8), the r FSS algorithms are recommended for the data set D. Since the weights and EARRs of the k nearest data sets can be obtained directly, the time complexity of these two steps is O(1). The time complexity for estimating and ranking the EARRs of the algorithms in ASet is O(k · m) + O(m · log(m)), where k is the preassigned number of the nearest data sets and m is the number of the candidate FSS algorithms.

Procedure FSSAlgorithmRecommendation
Inputs : D -a new given data set;  +O(m·log(m)). In practice, for a data set D that needs to conduct feature selection, the number of the instances P and/or the number of the features Q in D are much greater than the number of the nearest data sets k and the number of the candidate FSS algorithms m, so the major time consumption of this recommendation procedure is determined by the first part.

Experimental Results and Analysis
In this section, we experimentally evaluate the proposed feature subset selection (FSS) algorithm recommendation method by recommending algorithms over the benchmark data sets.

Benchmark Data Sets
115 extensively-used real world data sets, which come from different areas such as Computer, Image, Life, Biology, Physical and Text 4 , are employed in our experiment. The sizes of these data sets vary from 10 to 24863 instances, and the numbers of their features are between 5 and 27680.

Experimental Setup
In order to evaluate the performance of the proposed FSS algorithm recommendation method, further verify whether the proposed method is potentially useful in practice, and confirm the reproducibility of our experiments, we set the experimental study as follows.

FSS Algorithms
FSS algorithms can be grouped into two broad categories: Wrapper and Filter (Molina et al., 2002;Kohavi & John, 1997). The Wrapper method uses the error rate of the classification algorithm as the evaluation function to measure a feature subset, while the evaluation function of the Filter method is independent of the classification algorithm. The accuracy of the Wrapper method is usually high; however, the generality of the result is limited, and the computational complexity is high. In comparison, Filter method is of generality, and the computational complexity is low. Due to the fact that the Wrapper method is computationally expensive (Dash & Liu, 1997), the Filter method is usually a good choice when the number of features is very large. Thus, we focus on the Filter method in our experiment. A number of Filter based FSS algorithms have been proposed to handle feature selection problems. These algorithms can be significantly distinguished by i) the search method used to generate the feature subset being evaluated, and ii) the evaluation measures used to assess the feature subset (Liu & Yu, 2005;de Souza, 2004;Dash & Liu, 1997;Pudil, Novovičová, & Kittler, 1994).
In order to guarantee the generality of our experimental results, twelve well-known or the latest search methods and four representative evaluation measures are employed. The brief introduction of these search methods and evaluation measures is as follows. iv) Genetic search (GS): A randomized search method which performs using a simple genetic algorithm (Goldberg, 1989). The genetic algorithm finds the feature subset to maximize special output function using techniques inspired by natural evolution.
v) Linear search (LS): An extension of BestFirst search (Gutlein, Frank, Hall, & Karwath, 2009) which searches the space of feature subsets by greedy hill-climbing augmented with a backtracking facility.
vi) Rank search (RS) (Battiti, 1994): It uses a feature evaluator (such as gain ratio) to rank all the features. After a feature evaluator is specified, a forward selection search is used to generate a ranking list.
vii) Scatter search (SS) (Garci'a Lopez, Garci'a Torres, Melian Batista, Moreno Perez, & Moreno-Vega, 2006): This method performs a scatter search through the feature subset space. It starts with a population of many significant and diverse feature subsets, and stops when the assessment criteria is higher than a given threshold or does not have improvement any longer.
viii) Stepwise search (SWS) (Kohavi & John, 1997): A variation of the forward search. At each step in the search process, after a new feature is added, a test is performed to check if some features can be eliminated without significant reduction in the output function.
ix) Tabu search (TS) (Hedar, Wang, & Fukushima, 2008): It is proposed for combinatorial optimization problems. It is an adaptive memory and responsive exploration by combining a local search process with anti-cycling memory-based rules to avoid trapping in local optimal solutions.
x) Interactive search (Zhao & Liu, 2007): It traverses the feature subset space for maximizing the target function while taking consideration the interaction among features.
xi) FCBF search (Yu & Liu, 2003): It evaluates features via the relevance and redundancy analysis, and uses the analysis results as guideline to choose features.
2) Evaluation measures i) Consistency (Liu & Setiono, 1996;Zhao & Liu, 2007): This kind of measure evaluates the worth of a feature subset by the level of consistency in the target concept when the instances are projected onto the feature subset. The consistency of any feature subset can never be lower than that of the full feature set.
ii) Dependency (Hall, 1999;Yu & Liu, 2003): This kind of measure evaluates the worth of a subset of features by considering the individual predictive ability of each feature along with the degree of redundancy among these features. The FSS methods based on this kind of measure assume that good feature subsets contain features closely correlated with the target concept, but uncorrelated with each other.
iii) Distance (Kira & Rendell, 1992;Kononenko, 1994): This kind of measure is proposed based on the assumption that the distance of instances from different target concepts is greater than that from same target concepts.
iv) Probabilistic significance (Zhou & Dillon, 1988;Liu & Setiono, 1995): This measure evaluates the worth of a feature by calculating the probabilistic significance as a two-way function, i.e., the association between feature and the target concept. A good feature should have significant association with the target concept.
We should pay attention to that, besides the above four evaluation measures, there is another basic kind of measure: information-based measure (Liu & Yu, 2005;de Souza, 2004;Dash & Liu, 1997), which is not contemplated in the experiments. The reason is demonstrated as follow. The information-based measure is usually in conjunction with ranker search method. Thus, the FSS algorithms based on this kind of measure usually provide a rank list of the features instead of telling us which features are relevant to the learning target. In this case, we should preassign particular thresholds for these FSS algorithms to pick up the relevant features. However, there is not any effective method to set the thresholds or any acknowledged default threshold for these FSS algorithms. Moreover, it is unfair to conclude that these information measure based FSS algorithms with any assigned threshold are not appropriate when comparing to the other FSS algorithms. Therefore, this kind of FSS algorithm is not employed in our experiments.
Based on the search methods and the evaluation measures introduced above, 22 different FSS algorithms are obtained. Table 3 shows the brief introduction of these FSS algorithms. Where all these algorithms are available in the data mining toolkit Weka 5 (Hall,Frank,5  It is noted that some of these algorithms require particular settings of certain parameters. For the purpose of allowing other researchers to confirm our results, we introduce the parameter settings of these FSS algorithms. Such as, for FSS algorithms "INTERACT-D" and "INTERACT-C", there is a parameter, c-contribution threshold, used to identify the irrelevant features. We set this threshold as 0.0001 suggested by Zhao and Liu (2007). For FSS algorithm "FCBF", we set the relevance threshold to be the SU (Symmetric Uncertainty) value of the N/ log N th ranked feature suggested by Yu and Liu (2003). For FSS algorithm "Relief-F", we set the significance threshold to 0.01 used by Robnik-Šikonja and Kononenko (2003). For FSS algorithm "Signific", there is a threshold, statistical significance level α, used to identify the irrelevant features. We set α as the commonly-used value 0.01 in our experiment. The other FSS algorithms are conducted in the Weka environment with the default setting(s).

Classification Algorithms
Since the actual relevant features of real world data sets are usually not known in advance, it is impracticable to directly evaluate an FSS algorithm by the selected features. Classification accuracy is an extensively used metric for evaluating the performance of FSS algorithms, and also plays an important role in our proposed performance metric EARR for assessing different FSS algorithms.
However, different classification algorithms have different biases. An FSS algorithm may be more suitable for some classification algorithms than others (de Souza, 2004). This fact affects the performance evaluation of FSS algorithms.
Although Naive Bayes and Bayes Net are both bayes-based classification algorithms, they are quite different from each other since Naive Bayes is proposed based on the hypoth-6. http://www.public.asu.edu/huanliu/INTERACT/INTERACTsoftware.html esis that the features are conditional independent (John & Langley, 1995), while Bayes Net takes into account the feature interaction (Friedman et al., 1997).

Measures to Evaluate the Recommendation Method
FSS algorithm recommendation is an application of meta-learning. So far as we know, there are no unified measures to evaluate the performance of the meta-learning methods. In order to assess our proposed FSS algorithm recommendation method, two measures, recommendation hit ratio and recommendation performance ratio, are defined.
Let D be a given data set and A rec be an FSS algorithm recommended by the recommendation method for D, these two measures can be introduced as follows.

1) Recommendation hit ratio
An intuitive evaluation criterion is whether the recommended FSS algorithm A rec meets users' requirements. That is, whether A rec is the optimal FSS algorithm for D, or the performance of A rec on D has no significant difference with that of the optimal FSS algorithm.
Suppose A opt represents the optimal FSS algorithm for D, and ASet opt denotes the FSS algorithm set in which each algorithm has no significant difference with A opt (of course it includes A opt as well). Then, a measure named recommendation hit can be defined to assess whether the recommended algorithm A rec is effective on D.

Definition 1 (Recommendation hit). If an FSS algorithm A rec is recommended to a data set D, then the recommendation hit Hit(A rec , D) is defined as
Where Hit(A rec , D) = 1 means the recommendation is effective since the recommended FSS algorithm A rec is one of the algorithms in ASet opt for D, while hit(A rec , D) = 0 indicates the recommended FSS algorithm A rec is not a member of ASet opt , i.e., A rec is significantly worse than the optimal FSS algorithm A opt on D, thus the recommendation is bad.
From Definition 1 we know that the recommendation hit Hit(A rec , D) is used to evaluate the recommendation method for a single data set. Thus, it is extended as recommendation hit ratio to evaluate the recommendation for a set of data sets, and is defined as follows.

Definition 2 Recommendation hit ratio
Where G is the number of the historical data sets, e.g., G = 115 in our experiment. Definition 2 represents the percentage of data sets on which the appropriate FSS algorithms are effectively recommended by our recommendation method. The larger this value, the better the recommendation method.

2) Recommendation performance ratio
The recommendation hit ratio reveals that whether or not an appropriate FSS algorithm is recommended for a given data set, but it cannot tell us the margin of the recommended algorithm to the best one. Thus, a new measure, the recommendation performance ratio for a recommendation, is defined.

Definition 3 (Recommendation performance ratio). Let EARR rec and EARR opt be the performance of the recommended FSS algorithm A rec and the optimal FSS algorithm on D, respectively. Then, the recommendation performance ratio (RPR) for A rec is defined as
In this definition, the best performance EARR opt is employed as a benchmark. Without the benchmark, it is hard to determine the recommended algorithms are good or not. For example, suppose the EARR of A rec on D is 0.59. If EARR opt = 0.61, then the recommendation is effective since EARR of A rec is very close to EARR opt . However, the recommendation is poor if EARR opt = 0.91.
RPR is the ratio of EARR of a recommended FSS algorithm to that of the optimal one. It measures how close the recommended FSS algorithm to the optimal one, and reveals the relative performance of the recommended FSS algorithm. Its value varies from 0 to 1, and the larger the value of RPR, the closer the performance of the recommended FSS algorithm to that of the optimal one. The recommended algorithm is the optimal one if and only if RPR = 1.

Values of the Parameters α and β
In this paper, a multi-criteria metric EARR is proposed to evaluate the performance of an FSS algorithm. For the proposed metric EARR, two parameters α and β are established for users to express their requirements on algorithm performance.
In the experiment, when presenting the results, two representative value pairs of parameters α and β are used as follows: 1) α = 0 and β = 0. This setting represents the situation where the classification accuracy is most important. The higher the classification accuracy over the selected features, the better the corresponding FSS algorithms.
2) α = 0 and β = 0. This setting represents the situation where the user can tolerate an accuracy attenuation and favor the FSS algorithms with shorter runtime and fewer selected features. In the experiment, both α and β are set to 10% that is quite different from α = β = 0. This allows us can explore the impact of these two parameters on the recommendation results.
Moreover, in order to explore how parameters α and β affect the recommended FSS algorithms in terms of classification accuracy, runtime and the number of selected features, different parameters settings are provided. Specifically, the values of α and β vary from 0 to 10% with an increase of 1%.

Experimental Process
In order to make sure the soundness of our experimental conclusion and guarantee the experiments reported being reproducible, in this part, we introduce the four crucial processes used in our experiments. They are i) meta-knowledge database construction, ii) optimal FSS algorithm set identification for a given data set, iii) Recommendation method validation and iv) sensitivity analysis of the number of the nearest data sets on recommendations.

Procedure PerformanceEvaluation
Inputs : data = a given data set, i.e, one of the 115 data sets; learner = a given classification algorithm, i.e., one of {Naive Bayes, C4.5, PART, IB1 or Bayes Network}; For each data set D i (1 ≤ i ≤ 115), we i) extract its meta-features F i ; ii) calculate the EARRs for the 22 candidate FSS algorithms with the stratified 5×10-fold cross-validation strategy (Kohavi, 1995), and iii) combine the meta-features F i and the EARR of each FSS algorithm together to form a tuple, which is finally added to the meta-knowledge database.
Since the extraction of meta-features and the combination of the meta-features and the EARRs are straightforward, we just present the calculation of EARRs, procedure Perfor-manceEvaluation shows the details.

2) Optimal FSS algorithm set identification
The optimal FSS algorithm set for a given data set D i consists of the optimal FSS algorithm for this data set and those algorithms that have no significant performance difference with the optimal one on D i .
The optimal FSS algorithm set for a given data set D i is obtained via a non-parametric Friedman test (1937) followed by a Holm procedure test (1988) on the performance, which is estimated by the 5×10 cross validation strategy, of the 22 FSS algorithms. If the result of the Friedman test shows that there is no significant performance difference among the 22 FSS algorithms, these 22 FSS algorithms are added to the optimal FSS algorithm set. Otherwise, the FSS algorithm with the highest performance is viewed as the optimal one and added to the optimal FSS algorithm set. Then, the Holm procedure test is performed to identify the algorithms from the rest 21 FSS algorithms. The algorithms that have no significant performance differences with the optimal one are added into the optimal FSS algorithm set.
The reason why the non-parametric test is employed lies in that it is difficult for the performance values to follow the normal distribution and satisfy variance homogeneous condition.
Note that the optimal FSS algorithm sets for different settings of parameters α and β are different, since the values of these two parameters directly affect the required performance values.

3) Recommendation method validation
The leave-one-out strategy is used to empirically evaluate our proposed FSS algorithm recommendation method as follows: for each data set D i (1 ≤ i ≤ 115) that is viewed as the test data, i) identify its k nearest data sets from the training data = {D 1 , · · · , D i−1 , D i+1 , · · · , D 115 } excluding D i ; ii) calculate the performance of the 22 candidate FSS algorithms according to Eq. (5) based on the k nearest data sets where the value of k is determined by the standard cross-validation strategy, and recommend the top three to D i ; and iii) evaluate the recommendations by the measures introduced in section 4.2.3.

4) Sensitivity analysis of the number of the nearest data sets on recommendations
In order to explore the effect of the number of the nearest data sets on the recommendations and provide users an empirical method to choose its value, for each data set, all the possible numbers of the nearest data sets are tested. That is, when identifying the k nearest data sets for a given data set, k is set from 1 to the number of the historical data sets minus 1 (e.g., 114 in this experiment).

Results and Analysis
In this section, we present the recommendation results in terms of recommended FSS algorithms, hit ratio and performance ratio , respectively. Due to the space limit of the paper, we do not list all the recommendations, but instead present the results under two significantly different pairs of α and β, i.e., (α = 0, β = 0) and (α = 10%, β = 10%).
Afterward, we also provide the experimental results of the influence of the user-oriented parameters α and β on recommendations in terms of classification accuracy, runtime, and the number of selected features, respectively.

Recommended Algorithms and Hit Ratio
Figs. 2, 3, 4, 5 and 6 show the first recommended FSS algorithms for the 115 data sets when the classification algorithms Naive Bayes, C4.5, PART, IB1 and Bayes Network are used, respectively.
In each figure, there are two sub-figures corresponding to the recommendation results for (α = 0, β = 0) and (α = 10%, β = 10%), respectively. In each sub-figure, '•' and '×' denote the correctly and incorrectly recommended algorithms, respectively.         1) For all the five classifiers, the proposed method can effectively recommend appropriate FSS algorithms for most of the 115 data sets.
In the case of (α = 0, β = 0), the number of data sets, whose appropriate FSS algorithms are correctly recommended, is 109 out of 115 for Naive Bayes, 111 out of 115 for C4.5, 109 out of 115 for PART, 108 out of 115 for IB1, and 109 out of 115 for Bayes        (b) α = 10%, β = 10% Figure 5: FSS algorithms recommended for the 115 data sets when IB1 is used Network, respectively. This states that the recommendation method is effective when classification accuracy is most important. In the case of (α = 10%, β = 10%), the number of data sets, whose appropriate FSS algorithms are correctly recommended, is 104 out of 115 for Naive Bayes, 109 out of 115 for C4.5, 110 out of 115 for PART, 106 out of 115 for IB1, and 104 out of 115 for Bayes Network, respectively. This indicates that the recommendation method also works well when tradeoff is required among classification accuracy, runtime, and the number of selected features.
2) The distribution of the recommended FSS algorithms for the 115 data sets is different for different parameters settings. The distribution is relatively uniform for (α = 0, β = 0),     Figure 6: FSS algorithms recommended for the 115 data sets when Bayes Network is used while it is seriously biased to some algorithm (e.g., the 22th FSS algorithm) for (α = 10%, β = 10%). This phenomenon is similar for all the five classifiers. This can be explained as follows. The FSS algorithms with the best classification accuracy distribute on the 115 data sets uniformly. Thus, in the case of (α = 0, β = 0) where users favor accurate classifiers, the distribution of the recommended FSS algorithms is relatively uniform as well. However, there exist some FSS algorithms that run faster (e.g., the 22th algorithm "Signific") or select fewer features (e.g., the 8th algorithm "CFS-SWS", the 18th algorithm "Cons-SWS", and the 22th algorithm "Signific") on most of the 115 data sets. For this reason, in the case of (α = 10%, β = 10%) where users prefer the FSS algorithms with less runtime and fewer features, the distribution of the FSS algorithms with the best performance on the 115 data sets is biased to some algorithms, so is the recommended FSS algorithms.
3) The 22th FSS algorithm performs well on about 85 out of 115 data sets for all classifiers when (α = 10%, β = 10%). It seems that this FSS algorithm is a generally wellperformed FSS algorithm that can be adopted by all FSS tasks and there is no need for FSS algorithm recommendation. Unfortunately, this is not the case. The 22th FSS algorithm is still failing to perform well over about a quarter of the 115 data sets. Yet, our recommendation method can distinguish these data sets and further effectively recommend appropriate FSS algorithms for them. This indicates our recommendation method is still necessary in this case. Compared with (α = 0, β = 0), we can know that this case is due to the larger α and β values and can be explained as follows. For all the 22 FSS algorithms, although the classification accuracies of a classifier over the features selected by them are different, the differences are usually bounded. Meanwhile, from Eq. (1) we know that when α/β is set to be greater than the bound value, the value of EARR will be dominated by the runtime/the number of selected features. This means that if α or β is set to be a relatively large value, the algorithm with a lower time complexity or the algorithm that chooses smaller number of features will be recommended, and the classification accuracy over the selected features will be ignored. However, as we know, one of the most important targets of feature selection is to improve the performance of learning algorithms. So it is unreasonable to ignore the classification accuracy and just focus on the speed and the simplicity of an FSS algorithm.
Thus, in real applications, the values of α and β should be set under the limit of classification accuracies. Generally, the α/β should be bounded by (acc max − acc min )/acc min , where acc max and acc min denote the maximum and the minimum classification accuracies, respectively.   Table 4 shows the hit ratio of the recommended FSS algorithms for the five classifiers. From it we can observe that: 1) If a single FSS algorithm is recommended, the hit ratio of the first recommended algorithm Alg 1st is the highest, its value is up to 96.52% and at least is 90.43% for all the five classifiers. Thus, Alg 1st should be the first choice. 2) If the top three algorithms are recommended, the hit ratio is up to 100% and at least is 98.62%. That indicates that the confidence of the top three algorithms including an appropriate one is very high. This is the reason why only the top three algorithms are recommended. Moreover, the proposed recommendation method has reduced the number of candidate algorithms to three, users can further pick up the one that fits his/her specific requirement from them.

Recommendation Performance Ratio
Figs. 7 and 8 show the recommendation performance ratio RPR of the first recommended FSS algorithm for the five classifiers with (α = 0, β = 0) and (α = 10%, β = 10%), respectively. From these two figures we can observe that, for most data sets and the two settings of α and β, the RPRs of the recommended FSS algorithms are greater than 95% and some of them are up to 100% no matter which classifier is used. This indicates that the FSS algorithms recommended by our proposed method are very close to the optimal one. Table 5 shows the average RPRs over the 115 data sets for the five classifiers under different settings of (α, β). In this table, for each classifier, columns "Rec" and "Def" shows the RPR value corresponding to the recommended FSS algorithms and default FSS algorithms, respectively. Where the default FSS algorithm is the most frequent best one on the 115 data sets under the classifier. From it we observe that the average RPRs range from 97.32% to 98.8% for (α = 0, β = 0), and from 97.82% to 98.99% for (α = 10%, β = 10%), respectively. Moreover, the average RPR of the recommended FSS algorithms surpasses that of the default FSS algorithms for all the five different classifiers. This means our proposed recommendation method works very well and greatly fits user's performance requirement.

Recommendation Time
When recommending FSS algorithms for a feature selection problem, the recommendation time is contributed by meta-features extraction, k nearest data sets identification, and the candidate algorithm ranking according to their performance on the k data sets.
Of these three recommendation time contributors, only the candidate algorithm ranking is related with the parameters α and β of the performance metric EARR.
However, the computation of performance EARR is the same whatever the values of α and β are. This means recommendation time is independent of the specific settings of α and β. Thus, we just present the recommendation time with (α = 0, β = 0), and Table 6 shows the details.
From Table 6 we observe that for a given data set, the recommendation time differences for the five classifiers are small. The reason is that the recommendation time is mainly contributed by the extraction of meta-features, which has no relation with classifiers. This is consistent with the time complexity analysis in Section 3.2. We also observe that for most of the data sets, the recommendation time is less than 0.1 second, and its average value on the 115 data sets is around 0.65 second for each of the five classifiers. This is much faster than the conventional cross validation method.

Impact of the Parameters α and β
Figs. 9, 10, 11, 12 and 13 show the impact of the settings of α and β on the classification accuracy, the runtime of feature selection, the number of selected features, the Hit Ratio and the RPR value, respectively. From it we observe that, with the increase of either α or β, the classification accuracies of the five classifiers with the recommended FSS algorithms decrease. This is because the increase of α or β indicates that users much prefer faster FSS algorithms or the FSS algorithms that can get less features. Thus, the proportion of classification accuracy in performance is decreased. This means the ranks of the FSS algorithms that run faster and/or get less features are improved and the corresponding FSS algorithms are finally selected. 1) With the increase of α, the average runtime of the recommended FSS algorithms for each classifier decreases. Note a larger value of α means users favor faster FSS algorithms. Thus, this indicates that user's performance requirement is met since faster FSS algorithms were recommended. 2) With the increase of β, the average runtime of the recommended FSS algorithms increases as well. This is because in our proposed recommendation method, the appropriate FSS algorithms for a given data set are recommended based on its nearest data sets. Moreover, in the experiment, for more than half (i.e., 69) of the 115 data sets, there is a negative correlation between the number of selected features and the runtime of the 22 FSS algorithms. Thus, the more data sets with this kind of negative correlation, the more possible the nearest neighbors of a given data set have the negative correlation. Therefore, a larger β means longer runtime. Another possible reason is that a larger value of β means users favor the FSS algorithms that choose fewer features, and in order to get fewer features, the FSS algorithms need to consume relatively more time. 1) With the increase of α, the average number of selected features increases as well. This is because in our proposed recommendation method, the appropriate FSS algorithms for a given data set are recommended based on its nearest data sets. Moreover, in the experiment, for more than half (i.e., 69) of the 115 data sets, there is a negative correlation between the number of selected features and the runtime of the 22 FSS algorithms. Thus, the more data sets with this kind of negative correlation, the more possible the nearest neighbors of a given data set have the negative correlation. Therefore, a larger α means more features. Another possible reason is that a larger value of α means users favor faster FSS algorithms. It is possible that shorter computation time can be obtained via filter out less features so more features are remained. Note that there is an exception. That is, the average number of selected features for C4.5 decreases when the value of α is small. However, the decrement comes up in a quite small range of α (i.e., < 0.005).
2) With the increase of β, the average number of features selected by the recommended FSS algorithm decreases. Note a larger value of β means users favor the FSS algorithms that can get fewer features. Thus, this indicates that user's requirement is met since the FSS algorithms that can get fewer features were recommended.  With the change of the α and β, the hit ratio and RPR of the recommended FSS algorithms vary as well. However, the change intervals fall in a relative small interval and the lower bound stands at a fairly high level. The minimum average hit ratio is up to 91.74% and the minimum average RPR is up to 97.68%. This indicates that the proposed FSS algorithm recommendation method has general application and works well for different settings of α and β.

Sensitivity Analysis of the Number of Nearest Data Sets on Recommendation Results
In this section, we analyze how the number of the nearest data sets affects the recommendation performance. Based on the experimental results, we provide some guidelines for selecting the appropriate number of nearest data sets in practice.

Experimental Method
Generally, different numbers of the nearest data sets (i.e., k) will result in different recommendations. Thus, when recommending FSS algorithms to a feature selection problem, an appropriate k value is very important. The k value that results in higher recommendation performance is preferred. However, the recommendation performance difference under two different k values sometimes might be random and not significant. Thus, in order to identify an appropriate k value from alternatives, we should first determine whether or not the performance differences among them are statistically significant. Non-parametric statistical test, Friedman test followed by Holm procedure test as suggested by Demšar (2006), can be used for this purpose.
In the experiment, we conducted FSS algorithm recommendation with all possible k values (i.e., from 1 to 114) over the 115 data sets. When identifying the appropriate k values, the non-parametric statistical test is conducted as follows.
Firstly, the Friedman test is performed over the 114 recommendation performance at the significance level 0.05. Its null hypothesis is that the 114 k values perform equivalently well in the proposed recommendation method over the 115 data sets.
If the Friedman test rejects the null hypothesis, that is, there exists significant difference among these 114 k values, then we choose one under which the recommendation has the best performance as the reference. After that, the Holm procedure test is performed to find out the k values under which the recommendation performance has no significant difference with that of the reference. The identified k values including the reference are the appropriate numbers of the nearest data sets.

Results Analysis
Fig. 14 shows how the number of the nearest data sets (i.e., k) affects the performance of the recommendation method under different settings of α and β, where '×' denotes the k under which the recommendation performance is significantly worse than others at the significance level of 0.05. From it we observe that: 3) Comparing the cases of α = β = 0 and α = β = 10%, we found that '×' appears when k < 21 for the former and k < 29 for the latter, while it emerges again when k > 76 for the former. This means we cannot choose the k values falling into these ranges. At the same time, we also found that the peak values of RPR for α = β = 10% appear in the range of [32,54], which is also one of the peak value ranges for α = β = 0 except C4.5. This means if we set k to 28% to 47% of the number of data sets, better recommendation performance can be obtained.

Conclusion
In this paper, we have presented an FSS algorithm recommendation method with the aim to support the automatic selection of appropriate FSS algorithms for a new feature selection problem from a number of candidates. The proposed recommendation method consists of meta-knowledge database construction and algorithm recommendation. The former obtains the meta-features and the performance of all the candidate FSS algorithms, while the latter models the relationship between the meta-features and the FSS algorithm performance based on a k -NN method and recommends appropriate algorithms for a feature selection problem with the built up model.
We have thoroughly tested the recommendation method with 115 real world data sets, 22 different FSS algorithms, and five representative classification algorithms under two typical user's performance requirements. The experimental results show that our recommendation method is effective.
We have also conducted a sensitivity analysis to explore how the number of the nearest data sets (k) impacts the FSS algorithm recommendation, and suggest to set k as the 28% to 47% of the number of the historical data sets.
In this paper, we have utilized the well-known and commonly-used meta-features to characterize different data sets. "Which meta-features are informative?" and "Are there any other more informative meta-features?" are still open questions. To our knowledge, there still does not exist any effective method to answer these questions. Thus, for future work, we plan to explore further that how to measure the information of the meta-features and whether there are some more informative meta-features that can lead to further improvements for FSS algorithm recommendation.