Synthetic Data for Feature Selection

The proposed dataset is based on a two-layer circuit as shown in Figure 1. The first layer consists of an OR gate, while the second layer consists of an AND gate.

The ORAND dataset contains three relevant features $X_{1},X_{2}$, and $X_{3}$. The target variable $Y$ is calculated via the following formula:

In addition to the three relevant variables, we add three redundant (correlated) variables - one for each of $X_{1},X_{2}$, and $X_{3}$. We also add 2 features that randomly match the target variable in 70% of the instances. In the end, we include $N_{I}=92$ irrelevant features which are randomly generated according to the Bernoulli process. We obtain a synthetic dataset consisting of 3 relevant, 3 redundant, 2 correlated, and 92 irrelevant features. There are a total $2^{100}$ possible feature value combinations of which we select $n=50$ samples. As it is often the case with high dimensional data, the number of features is high relative to the number of observations. While the default number of samples is 50, it can be changed as necessary. In fact, both the number of observations and the number of irrelevant features can be varied to analyze the performance of a feature selection algorithm under different conditions. However, it is strongly advised to employ the proposed datasets under the default settings, at least once, to obtain a benchmark reference result.

The proposed dataset is based on a two-layer circuit as shown in Figure 2. The first layer consists of two AND gates, while the second layer consists of a single OR gate.

The ANDOR dataset contains four relevant features $X_{1},X_{2},X_{3}$, and $X_{4}$. The target variable $Y$ is calculated via the following formula:

The expression in Equation 2 can be viewed as the sum of products. In addition to the four relevant variables, we add four redundant (correlated) variables - one for each of $X_{1},X_{2},X_{3}$, and $X_{4}$. We also add 2 features that randomly match with the target variable 70% of the time. Finally, we include $N_{I}=90$ irrelevant features which are randomly generated according to the Bernoulli process. We use the features to randomly generate $n=50$ samples. We obtain a synthetic dataset consisting of 4 relevant, 4 redundant, 2 correlated, and 90 irrelevant features and 50 samples. As with the ORAND dataset, the number of irrelevant features $N_{I}$ and the number of samples $n$ can be changed to evaluate a feature selection algorithm under different scenarios.

The ANDOR dataset can be expanded by increasing the number of relevant variables up to $m$ in the following manner:

Additional redundant and irrelevant features can be included in similar fashion as above.

The ADDER dataset is based on the eponymous adder circuit. It is a multi-class target dataset. The full adder takes three inputs $X_{1},X_{2}$, and $X_{3}$ and produces two outputs $Y_{1}$ and $Y_{2}$. The outputs are calculated according to the following formulae:

By combining the values of $Y_{1}$ and $Y_{2}$ into a single target variable $Y=(Y_{1},Y_{2})$, we obtain a 4-class target variable: $Y=\{(0,0),(0,1),(1,0),(1,1)\}$. As usual, we add redundant features - one for each of $X_{1},X_{2}$, and $X_{3}$ - 2 correlated features, and $N_{I}=92$ irrelevant features. We randomly generate $n=50$ samples based on the full set of features. The final dataset consists of 3 relevant, 3 redundant, 2 correlated, and 92 irrelevant features and 50 observations. As mentioned above, unlike ORAND and ANDOR, ADDER is a multi-class dataset with a 4-class target variable.

The LED-16 dataset is based on the 16-segment display configuration shown in Figure 3. The 16-segment configuration allows to display all 26 letters of the English alphabet as well as all the digits 0-9. Each segment represents a binary feature: on/off. The target variable is the alpha-numeric value displayed by the segments. Thus, the target variable can take 36 different values. We add 16 redundant features - one for each relevant feature (segment). We also include 2 correlated and 66 irrelevant features with randomly generated binary values.

The dataset contains 180 observations - 5 samples for each target value. In particular, for each target value, the values of the relevant and redundant features are determined by the display configuration, while the values of remaining features are randomly generated. In summary, the LED-16 dataset consists of 16 relevant, 16 redundant, 2 correlated, and 66 irrelevant features and 180 observations. It is a multi-class dataset with a 36-class target variable.

As shown in Figure 4, some LED segments are used more frequently than others. For example, the segment F is utilized in the majority of configurations, while the segment H is used in only a few times. While both segments are relevant, they have different levels of significance. The LED-16 dataset allows to evaluate feature selection algorithms on the basis of their sensitivity to different level of feature relevance. A robust selection algorithm should identify both strongly and weakly relevant features.

The proposed dataset is based on the parallel resistor circuit. Given a set of resistors $\{R_{1},R_{2},...,R_{N}\}$ that are connected in parallel, the total resistance $R_{T}$ is given by the following equation:

For the proposed PRC dataset, we use 5 parallel connected resistors (relevant features). The relevant features $\{X_{i}\}_{i=1}^{5}$ are generated according to the Gaussian distribution with mean $\mu_{i}=10$ and standard deviation $\sigma_{i}=i,i=1,2,...,5$. The target variable $Y=R_{T}$ is calculated according to Equation 5. Since the parallel resistors as well as the total resistance are continuous valued variables, the PRC dataset implies a regression task.

We generate 5 redundant, 2 correlated, and 88 irrelevant features to include in the dataset. The redundant variables are created as linear transformations of the relevant variables. The correlated variables are created by adding a small amount of noise perturbation to the target variable. Half of the irrelevant variables are generated according to the same Gaussian distribution as the relevant variables. In particular, for each $i=1,2,...,5$, we generated nine random features according to the Gaussian distribution $\mathcal{N}(\mu_{i}=10,\sigma_{i}=i)$. The remaining half of the irrelevant features are randomly generated according to the uniform distribution $\mathcal{U}(0,1)$.

Since the target variable $Y$ is continuous valued, we generate more observations for the PCR dataset than for the classification data described in the previous sections. In particular, we generate 500 samples using the full feature set, where the target variable is calculated via Equation 5 based on the features $\{X_{i}\}_{i=1}^{5}$.

A comparator circuit compares two inputs - usually voltages or currents - and outputs either 1 or 0 depending on which input is greater. It is often used to check if a single input is above a certain threshold. In this manner, a comparator can employed to convert an analog (continuous) signal into a digital (binary) output.

Since a comparator converts a continuous signal into binary, it can be employed in conjunction with the digital circuits described in previous sections including ORAND, ANDOR, and ADDER. For instance, one or more input variables in the ORAND circuit can be continuous-valued by using a comparator as a preprocessing gate. Thus, datasets with binary features can be extended to include continuous features, which increases the number of available synthetic datasets for feature selection.

We use the ANDOR dataset described in Section 3.2 to evaluate the feature selection algorithms. The dataset consists of 4 relevant, 4 redundant, 2 correlated, and 90 irrelevant features and a binary target class. The redundant variables are the negations of the relevant variables. The correlated variables are correlated with the target variable at 70%. To observe the effect of the sample size we consider the datasets with 50 and 20 samples.

To account for random variations, we generate the ANDOR dataset using 10 different random seeds. The feature selection algorithms are applied to each of the 10 datasets. The results are averaged and presented for analysis.

We consider univariate algorithms, recursive feature elimination (RFE), and model-based algorithms for feature selection. In the univariate approach, we employ $\chi^{2}$ to measure the relationship between a feature and the target variable. In the RFE approach, we use the support vector classifier (SVC) with linear kernel. The SVC model is iteratively fit to the data and at each stage the variable with the lowest coefficient is discarded. In the model-based approach, we use SVC with the $L_{1}$-penalty (lasso) and the extra-trees classifier. The lasso model automatically discards the irrelevant features as part of the fitting process. The extra-trees classifier is used to calculate the reduction in impurity of each feature during the fitting process.

Four feature selection algorithms - univariate ($\chi^{2}$), RFE, lasso, and extreme trees - are tested based on the ANDOR dataset. The results show that the feature selection methods perform relatively well in distinguishing between the relevant and the irrelevant features. However, the selection algorithms struggle to separate the relevant features from the redundant and correlated features. Furthermore, a decrease in the sample size leads to a lower distinction between the relevant and irrelevant features.

The results of the univariate approach for feature selection are presented in Figure 5. The average $\chi^{2}$-scores between the features and the target variable over 10 runs are provided. Since the correlated and irrelevant features are randomly generated, there exists variation in the results between the runs. To show the variations between the runs the standard deviation of $\chi^{2}$-scores are represented by the red line segments.

As shown in Figure 5(a), in case when the sample size is $n=50$, the algorithm assigns significantly higher $\chi^{2}$-scores to the relevant features than the irrelevant features. On the other hand, it also assigns high scores to the redundant and correlated features. Thus, while the algorithm is able to distinguish the relevant features from the irrelevant features, it fails to distinguish the relevant features from the redundant and correlated features. As shown in Figure 5(b), in case when the sample size is $n=20$, the difference in scores between the relevant and irrelevant features is considerably lower than in the case $n=50$. Given the large variation of the irrelevant features, it is highly likely that at least some of the irrelevant features may obtain a higher $\chi^{2}$-score than the relevant features. The features $X_{2}$ and $X_{3}$ are particularly susceptible to being overlooked.

The results of the RFE approach are presented in Table 2. The tables present RFE feature rankings for the relevant ($X_{1}$ to $X_{4}$) and redundant ($X_{5}$ to $X_{8}$) features. The left and right tables correspond to the data of size $n=50$ and $n=20$, respectively. The rows in the tables correspond to the datasets generated using different random seeds. The last row $\bm{\tilde{r}}$ provides the median rankings of the features across 10 runs. The results show that the RFE approach is less effective than the univariate approach. There is a significant variation in the rankings between different versions of the dataset which suggests that RFE is not a stable method. To summarize the results we consider the median rankings. In case $n=50$, 6 features achieved median ranking in the top 10, but only one feature $X_{8}$ is in top 4. Thus, if we were to select the top 4 features - since that is the number of relevant variables - only one feature would be correctly selected. In case the $n=20$, the algorithm performs poorly with only one feature in top 10 and none in the top 4. It is unsurprising that the algorithm is less effective when using a small sample size.

The results of the lasso-based approach in case the $n=50$ are presented in Figure 7(a). The $y$-axis represents the number of times a feature was selected in the lasso model. As shown in the figure, the lasso approach performed well in this case. The relevant features achieve significantly higher scores than the irrelevant features. However, the redundant and correlated features also achieve high scores. Thus, while the lasso approach is effective at distinguishing between the relevant and irrelevant features, it fails to differentiate the relevant features from the redundant and correlated features. The results in the case $n=20$ are expectedly less robust. As shown in Figure 7(b), the scores for the relevant features are significantly lower than those for the correlated features. In addition, several irrelevant features have higher scores than the relevant features. On the other hand, three of the redundant features have high scores which can be an acceptable substitute for the relevant features.

The results of the approach based on extra-trees are presented in Figure 8. The $y$-axis indicates the average decrease in impurity corresponding to a feature. As shown in Figure 8(a), in the case of $n=50$, the algorithm performs better than the previous approaches by assigning higher level of importance to relevant features than the irrelevant and correlated features. We also note that the irrelevant features have low variance. So they are less likely to be selected by chance. However, the algorithm does not distinguish well between the relevant and redundant variables. As expected, the algorithm performs worse in the case $n=20$. While the importance of the relevant variables $X_{1}$ and $X_{4}$ remains significantly above the irrelevant variables, the gap between the relevant variables $X_{2}$ and $X_{3}$ and the rest of the features decreased considerably. In addition, the variance of the irrelevant variables increased which increases the likelihood of an irrelevant variable achieving a high level importance purely by chance.