Feature selection simultaneously preserving both class and cluster structures

We have used five publicly available datasets that are very commonly used for classification and clustering. The first four datasets are downloaded from UCI machine learning repository [46]. AR10P is downloaded from the open-source feature selection repository of Arizona State University[47]. We have also performed the experiments with three benchmark HSI datasets for land cover classification problems. We discuss them in a separate subsection (Subsec. 3.2).

The details of the number of features, number of classes, and number of instances for the five datasets are summarized in Table 1.

The datasets are used directly without any further processing. The datasets are partitioned into training and test sets as approximately $90\%$ and $10\%$ of the total number of instances. To implement our proposed feature selection scheme we use the neural network shown in Fig. 1 with the number of hidden layers, $n_{H}=1$. The input and output layers have $P$ and $C$ nodes respectively, where $P$ is the number of features and $C$ is the number of classes corresponding to the considered dataset. The number of hidden nodes in the hidden layer is $8$ ($20$ for AR10P data set). To get stable feature selection results, the network weights are initialized in a certain way. To set the initial weights of the proposed network, we undergo the following steps. First, we consider the usual MLP part of our network (i.e. without feature selection), depicted by the portion within the dotted rectangle in Fig. 1, and initialize its weights randomly. Next, we train the usual MLP with the cross-entropy loss defined in Equation (2) with the training set until convergence. The weights of the converged network are used as the initial weights of the proposed network. The gate parameter $\lambda_{j}$s are initialized with values drawn randomly from a normal distribution with mean $=2$ and spread $=\frac{1}{\sqrt{P}}$. The initial values of $\lambda_{j}$s are chosen around $2$ to effectively make the gates almost closed initially. As the learning progresses the $\lambda_{j}$s are updated in a way to allow the useful features to the network. For the proposed system, to select a subset of $Q$ features, the gate parameters $\lambda_{j}$s are sorted in ascending order, and the $Q$ features corresponding to the top $Q$, $\lambda_{j}$s are selected. The network weights as well as the gate parameters $\lambda_{j}$s are learned using the adaptive gradient algorithm, ‘train.AdagradOptimizer’ routine of the ‘TensorFlow’ framework [48]. For all experiments with the data sets in Table 1, both $\alpha_{1}$ and $\alpha_{2}$ of the error functions in Equations (6) and (8) are set as $1$. The total number of iterations for training the network is set to $20000$. The five datasets we consider here, have the number of instances $n<400$, which is not so large. Therefore, we use (8) as the overall loss function to train the MLP based architecture for selecting features that are reasonably good for clustering and classification. When $\beta=0$ in (8), effectively, the error function that governs the learning of our MLP based embedded feature selection scheme is (6). The corresponding feature selection scheme now only considers classification. Let us name this method as feature selection with MLP (FSMLP). When $\beta\neq 0$ in (8), our method takes structure preservation into account along with classification. Let us name the corresponding method as FSMLP_struct. To understand the importance of adding the structure preserving regularizer (7), we perform feature selection with FSMLP and compare with FSMLP_struct having different $\beta$ values. We explore three values of $\beta$s $0.1,1,$ and $10$. Although the exact value of the $\beta$ that is optimum for a particular dataset for a particular number of selected features $Q$ cannot be decided from these three values, we investigate the effect of three widely different $\beta$s to see the role of the weight to the structure preserving regularizer, i.e. $\beta$ on the performance of the selected features. We compare with three other methods namely, Independent Component Analysis (ICA)-based feature selection [49], F-score based filter method [16], and mutual information based filter method [18, 19]. The performance of both FSMLP and FSMLP_struct is dependent on the initial weights of the network. So, we repeat the initialization of the network weights and gate parameters $\lambda_{j}$s five times and run the schemes- FSMLP or FSMLP_struct five times with the five initializations. For the performance measure of FSMLP and FSMLP_struct, we consider the average performance over the five subsets obtained from the five runs. To check the effectiveness of the methods in selecting features that perform well in classification and clustering simultaneously, we compute the classification scores of the support vector machine (SVM) classifier as well as several structure-preserving indices: Sammon’s stress (SS) [45], normalized mutual information (NMI) [18, 20, 21, 22], adjusted rand index (ARI) [50], and Jaccard Index (JI) [51]. As the measure of classification performance, we use the overall classification accuracy (OCA) of the SVM classifier. The optimal hyper-parameters of SVM are determined through five-fold cross-validation using grid search. Note that here the test set is not only unseen to the SVM classifier but unseen to the feature selection methods also. SS, defined in Equation (7) use the original inter-point distances $d_{il}^{\mathbf{X}}$s and latent space inter-point distances $d_{il}^{\mathbf{\hat{X}}}$s. Here to compute $d_{il}^{\mathbf{\hat{X}}}$, we use the lower dimensional data formed by the selected $Q$ features. We use NMI, ARI, and JI as the structure-preserving performance metrics by supplying the cluster labels obtained from clustering the data in the original space (using all features) as the true label and the cluster labels obtained from clustering the data in the reduced space formed by the selected $Q$ features as the predicted cluster label. So, NMI, ARI, and JI measure how the cluster assignments in the original space and in the selected space agree, effectively giving a measure for the preservation of the original cluster structure in the selected space. We know that the maximum value for NMI or ARI or JI is $1$. Here, the value of each of these three measures being close to $1$ indicates that the cluster structure in the original space is preserved in the selected space. As the clustering algorithm we use, the fuzzy $C$ means (FCM) algorithm [52] with the fuzzy exponent $m=2$. We set the number of clusters for FCM algorithm as the number of classes. We use two values for the number of the selected features, $Q$. $Q=0.35\times P$ and $Q=0.5\times P$, where these values are rounded up to the nearest integers using the ceiling function.

Tables 2 and 3 summarize the performances of the proposed method and other comparing methods for training and test sets, respectively for the E. coli dataset. We tabulate the three previously mentioned structure preserving measures and one classifier score for two choices of the number of selected features (approximately $35\%$ and $50\%$ of the original dimension) i.e., $Q=3$, and $Q=4$ in Tables 2 and 3.

As we have already discussed in Sec. 2 the lesser the value of SS, the better the projected space (formed by selected features) preserves the original pairwise distances and hence the structure of the original data. We observe in Table 2, the mutual information based method shows the lowest value of SS, and the second lowest is FSMLP_struct with $\beta=10$ for both $Q=3$ and $Q=4$. Actually, the SS values for the mutual information based method and FSMLP_struct with $\beta=10$ are almost the same, equal up to two places after decimal points in both choices of $Q$. The SS values achieved by ICA, the F score based method and FSMLP are comparatively higher. So, the mutual information based method and FSMLP_struct with $\beta=10$ preserve the original pairwise distances most in the projected space. They are also expected to preserve the structures most. The values of the other three structure preserving measures i.e., NMI, ARI, and JI confirm that. We know that the higher the values of NMI, ARI, and JI are, the closer the clustering structures of the projected space are to the original clustering structures. The highest values of the NMI, ARI, and JI are obtained by the mutual information based method, followed by the FSMLP_struct with $\beta=10$. So, in cluster structure preservation, mutual information based method and FSMLP_struct with $\beta=10$ perform better than the other three methods and even than the other two models trained by FSMLP_struct with $\beta=0.1$ and $1$. $\beta$ is the weight of the regualizer $E_{sammons}$ in (7). Although SS and $E_{sammons}$ are not exactly same, under the influence of $E_{select}$, it is expected that the higher the value of $\beta$ lesser the value of SS would be. Table 2 reconfirms that. The SS values become lesser as the $\beta$ increases from $0.1$ to $10$. SS values of FSMLP (which is basically FSMLP_struct with $\beta=0$) and FSMLP_struct with $\beta=0.1$ are the same for both the choices of $Q$. Actually, FSMLP and FSMLP_struct with $\beta=0.1$ have all the ten measures the same. It proves that for the E.coli dataset $\beta=0.1$ does not give any effective weightage to the structure preservation term and chooses the same subsets as FSMLP. For the classification performance measure OCA, FSMLP_struct with $\beta=1$, achieves the highest value, followed by FSMLP_struct with $\beta=10$. The mutual information based method and FSMLP_struct with $\beta=10$ have all the structure preserving measures either almost equal or of comparable values, however for OCA, FSMLP_struct with $\beta=10$ is better than mutual information based method with a margin more than $18\%$. For E. coli data, the test set follows the observed trends in the training set with the following exceptions. First, for $Q=3$, the values of NMI, ARI, and JI have not increased as $\beta$ increases from $0.1$ to $10$. Second, for $Q=4$, FSMLP_struct with $\beta=10$ beats all the methods including mutual information based method. Analyzing the performances over train and test sets, for E. coli data FSMLP_struct with $\beta=10$ is the winner among the other six models.

Tables 4 and 5 compare the performance of the proposed method with other methods in terms of different criteria for the Glass dataset on its training and test sets, respectively.

The chosen numbers of features for the Glass data are $4$ and $5$. The expected nature of decreasing SS with increasing $\beta$ is clearly observed for $Q=5$ for both the training and test set. For $Q=4$, the Glass data also follows the characteristics of the E. coli data of having the same values for FSMLP and FSMLP_struct with $\beta=0.1$ in all the ten measures for both training and test set. For $Q=4$, from $\beta=0.1$ onwards, increasing $\beta$s produce decreasing SS values and increasing NMI, ARI, and JI values for both training and test datasets. We observe from the Tables 4 and 5, for $Q=5$, as the $\beta$ increases from $0$ (FSMLP) to $0.1$, and then to $1$, NMI, ARI, and JI values are increased for both training and test datasets, however at $\beta=10$, NMI, ARI, and JI values are decreased compared to $\beta=0.1$ and $1$. We can conclude that, for $Q=4$, FSMLP_struct with $\beta=10$ gives the best structure preserving performance among the considered models and for $Q=5$, FSMLP_struct with $\beta=1$ is best in structure preservation. In terms of the classification performance measure OCA, FSMLP_struct with $\beta=10$ and FSMLP_struct with $\beta=1$ show the highest OCA values for the training set and test set respectively, with $Q=4$. On the other hand, for $Q=5$, FSMLP_struct with $\beta=10$ show the highest OCA values for the training set and FSMLP_struct with $\beta=1$ show the highest OCA values for the test set. Inspecting all the performance measure values, we conclude that for the Glass dataset, both FSMLP_struct with $\beta=10$ and FSMLP_struct with $\beta=1$ are comparatively better in simultaneously preserving both class and cluster structures than the other methods.

The performances of the Ionosphere dataset are recorded in Tables 6 and 7 for training and test sets respectively.

For the Ionosphere data set, the number of selected features, $Q$ is set as $12$ and $17$. Here, in all the cases, whenever the $\beta$ is increasing, SS is decreasing and the other structure preserving indices NMI, ARI, and JI are increasing consistently. Unlike, E. coli and Glass data set, here when $\beta$ increases from $0$ (in FSMLP) to $0.1$, the structure preserving metrics including SS shifted in the desired direction in most of the cases and remained the same in some cases. Except for SS, in the other three structure preserving measures, ICA and F score based method have performed better than FSMLP and FSMLP_struct for all the cases. Classification performance is good for almost all methods for the Ionosphere data set. In the training set, for both $Q=12$ and $Q=17$, an accuracy of $97.46\%$ is reached by mutual info and F score based methods, however, FSMLP and FSMLP_struct models have reached more than $96\%$ accuracy in every case. For the test set, all the structure preserving indices are better for FSMLP and FSMLP_struct than ICA, F score, and mutual information based methods, although in terms of classification score OCA, the F score and mutual information based methods have performed marginally better than FSMLP and FSMLP_struct models. This may have happened because the selected features from the neural network based classifier which are expected to be discriminatory features, may not be the best for SVM. Moreover, FSMLP_struct makes a compromise between preserving cluster structure and classifier loss. For the Ionosphere dataset, our proposed models are not the winner. May be with higher $\beta$, FSMLP_struct would deliver better scores.

For the Sonar data, the summary of the performances of the training and test data sets in terms of the five measures for two choices of the number of selected features are available in Tables 8 and 9.

We set, $Q=21$ and $30$ for the Sonar data set. In the case of the Sonar data set, not only with increasing $\beta$, all the structure preserving indices improve, in case of the training set, FSMLP_struct with $\beta=10$ are significantly better than ICA, F score, and mutual information based methods, and FSMLP in all five scores for both the choices of $Q$. In test set for some cases, FSMLP_struct with $\beta=1$ is better than FSMLP_struct with $\beta=10$. For the Sonar data set, clearly, the proposed method performed extremely well in terms of classification and clustering performance.

Tables 10 and 11 summarize the performances of the proposed method and other comparing methods for training and test sets, respectively for the AR10P data set. The original number of features, $P$ for the AR10P data set is $2400$, which is comparatively higher than that of the other two data sets used in this sub-section. The two choices of the number of selected features here are $40$ and $60$ and these are not approximately $35\%$ and $50\%$ of the original dimension like in previous cases.

The study in [42], proposed a feature selection scheme for redundancy control in features. They reported an average number of selected features of $58.9$ without practicing redundancy control and an average number of selected features in the range of $22.8$ to $44.2$ when practicing redundancy control for AR10P data set. Hence, we choose the number of selected features $Q$ as $40$ and $60$. From the classification scores shown in Table 10, we note that for all the methods for both the choices of $Q$, classification scores in training set are more than $99\%$. In the training set, we observe that for FSMLP_struct as $\beta$ increases SS is decreased in almost all the cases. But for the test set, this is not true. For the other structure-preserving measures for the training set, FSMLP_struct with $\beta=50$ is best among all the methods for $Q=40$ and FSMLP_struct with $\beta=100$ is best among all the methods for $Q=60$. In the test set, all the methods have performed almost the same in terms of the structure-preserving measures. The classification performances of FSMLP_struct are very poor in the test set for AR10P data. The significant differences in training and test OCA values for FSMLP_struct indicate poor generalization of the system. This problem may be addressed by choosing the number of nodes for our MLP based model through cross-validation.

Results from the five data sets clearly establish the benefit of introducing the proposed structure preserving regularizer term, $E_{sammons}$ in the overall loss function (8) of the MLP based embedded feature selection scheme. Next we shall consider the band (channel) selection problem for hyperspectral satelite images.

Let our considered hyperspectral image $I$ be of dimension, $H\times W\times P$ where, $H$, $W$, and $P$ are the height, width, and number of spectral bands of the image respectively. We can represent the pixels of $I$ as $\mathbf{x}_{i}\in\mathbb{R}^{P}:i=1,2,\dots,H\times W$. Let, there be total $n$ pixels annotated with $C$ land cover classes. Without any loss of generality, we take the first $n$ pixels, i.e., $i=1,2,\dots n$ as the pixels having class labels. Our input data for land cover classification problem be $\mathbf{X}=\{\mathbf{x}_{i}=(x_{i1},x_{i2},\cdots,x_{iP})\in\mathbb{R}^{P}\}_{i=1}^{n}$. The collection of class labels of $\mathbf{X}$ be $\mathbf{Z}=\{z_{i}\in\{1,2,\cdots,C\}\}_{i=1}^{n}$, where, $z_{i}$ is the class label corresponding to $\mathbf{x}_{i}$. We aim to select a subset of size $Q$ from the original set of bands such that the selected subset performs reasonably well for land cover classification as well as in clustering. We have performed the experiments with three benchmark HSI datasets for land cover classification problems- Indian pines, Pavia University, and Salinas[53]. We have used the corrected version of the Indian pines and Salinas dataset having the number of bands 200 and 204 respectively. The Pavia University dataset uses 103 bands. The pre-processing of the datasets is the same as done in [54], following the code available in[55]. For any dataset, its pixel values are scaled to $[0,1]$ using the expression $(x-\min(x))/(\max(x)-\min(x))$, where, $x$ is a pixel value. The $\max$ and $\min$ are computed over the entire HSI. The data are then mean normalized across each channel by subtracting channel-wise means. The datasets are partitioned into training and test datasets. For band selection, only the training datasets are fed to the model. For measuring performances both training and test datasets are used. For splitting the datasets into training and test subsets, we drop the pixels of the unknown land-cover type. Let $\mathbf{X}$ be the set of pixels with known land-cover type. To obtain the training and test sets, let us divide $\mathbf{X}$ into two subsets $\mathbf{A}$ and $\mathbf{B}$ such that $\mathbf{A}\bigcup\mathbf{B}=\mathbf{X}$, $\mathbf{A}\bigcap\mathbf{B}=\phi$, and $\mathbf{A}$ and $\mathbf{B}$ contain, respectively, $25\%$ and $75\%$ pixels of $\mathbf{X}$. We use $\mathbf{A}$ as the test set. Note that, both the datasets suffer from the class imbalance problem. To avoid the learning difficulty raised by class imbalance, in the training set, we consider the same number of instances from each class. For this, from the subset $\mathbf{B}$, we randomly select (without replacement) $200$ pixels per class. If a class has less than $200$ instances in $\mathbf{B}$, we oversample the class by synthetic minority oversampling technique (SMOTE) [56] to gather $200$ points. For band selection also, we use the same neural network (Fig. 1) with the number of hidden layers, $n_{H}=3$. The numbers of hidden nodes in the three hidden layers are $500,350,$ and $150$ respectively. Here the number of input nodes of the MLP is equal to the number of bands ($P$). The network weights and the gate parameters $\lambda_{j}$s are initialized in the same way as done. For all experiments of the current sub-section, $\alpha_{1}$ and $\alpha_{2}$ of the error functions in Equations (6) and (10) are set as $5$ and $1$ respectively. The total number of iterations for training the network is set to $50000$. The rest of experimental settings are kept same as the previously mentioned experiment with the two data sets. The number of training instances of Indian pines and Salinas data set is $3200$ and that of Pavia university is $1800$. Both of the number of training instances, $n$ are high. Computation of the $E_{sammons}$ in (7) would involve computing $(3200)^{2}$ or $(1800)^{2}$ distances. Adding $E_{sammons}$ to the overall loss function would cause very intensive computation at each iteration. So, instead of $E_{sammons}$, its proposed approximation $E_{struct}$ defined in (9) is used. In (9), $|S_{t}|$ is taken as $100$. Varying the value of $\beta$ in (10), we analyse its effect on the OCA, SS, NMI, ARI, and JI. We compute SS, NMI, ARI, and JI as described in Subsec. 3.1. We also use the same clustering algorithm with the same settings as used in Subsec. 3.1.

Tables 12 and 13 summarize the comparative results of FSMLP_struct with FSMLP and other band selection methods, ICA, F score, and mutual information based filter methods on the training and test datasets of Indian pines respectively.

Similarly, Table 14 and 15 summarize the comparative results on the training and test datasets of Pavia university.

In this experiment, we have fixed the number of selected bands $Q$, approximately to $35\%$ of the original number of bands $P$. So, The number of selected bands is $70$ for Indian pines and it is $35$ for Pavia University. Tables 12 and 13 record the values of the structure-preserving indices and classification scores on Indian pines for different $\beta$ values in FSMLP_struct ($\beta$ values in Equation (10)). The considered $\beta$s for Indian pines, are $2,5,20,$ and $50$. Note here that, FSMLP is basically FSMLP_struct with $\beta=0$. We observe in Tables 12 and 13 that both for training and test datasets as the value of $\beta$ increases for FSMLP_struct (in the last five rows of the corresponding Tables) the value of SS becomes smaller. A similar trend is also observed for the Pavia University data set (here, $\beta$ varies as $1,1.5,2,$ and $2.5$) for training (Table 14) and test (Table 15) sets.

For the Pavia university dataset, we have set the values of $\beta$ in FSMLP_struct as $1,1.5,2,$ and $2.5$. Unlike Indian pines for Pavia university, we restrict the $\beta$s to lower values. This is due to the fact that the number of selected bands for Pavia university is $35$ and that for Indian pines is $70$. Lesser the number of bands, the lesser the importance ($\beta$) to be given to our structure preserving regularizer in Equation (9) to obtain a desired balance between classification and clustering performance. Table 12 which contains the results for the Indian pines training data, clearly shows that both FSMLP and FSMLP_struct are better than ICA, F-score based, mutual information based methods in all four structure preserving metrics as well as in terms of the OCA. In Table 12 we observe that with increasing values of $\beta$ there is a consistent improvement in the values of the four structure preserving metrics while the values of OCAs retain approximately at $91\%$. The results shown in Table 13 for the Indian pines test set also show that FSMLP and FSMLP_struct perform better in terms of all the five metrics than the other three methods. Also with an increase in $\beta$ all the structure-preserving metrics improve for FSMLP_struct, except the value of JI slightly decreases when $\beta$ goes to $50$ from $20$. The classification metric OCA is around $78\%$ with bands selected by FSMLP_struct for different choices of $\beta$s.

It is notable here that the test set is completely unseen in the process of band selection, yet the selected bands for the proposed method is providing fairly good results for structure preservation as well as for classification. As observed from Table 14 and Table 15 for Pavia university training and test sets respectively, the lowest (best) SS value among all the comparing methods is achieved by mutual information based filter method. However, for the other four metrics i.e. NMI, ARI, JI and OCA; FSMLP and FSMLP_struct show better values. In the case of the Pavia university dataset with increasing $\beta$; NMI, ARI, and JI are not consistently increasing but the results indicate that, it is possible to find a $\beta$, (here $\beta=2$) where the structures are preserved better maintaining a good classification score. Table 16 and 17 summarize the comparative results of training and test datasets of Salinas.

We note from Tables 16 and 17 that, for the Salinas dataset, FSMLP and FSMLP_struct are better than the other three methods in all the five metrics used. All four structure preserving metrics scores of FSMLP_struct are better than or comparable to FSMLP keeping the classification score OCA at approximately $96\%$ for the training dataset and $90\%$ for the test dataset. Tables 16 and 17 reveal that when $\beta$ is increased from $0$ to $2$, the value of SS is increased however, from $\beta=2$ to $\beta=50$ onward, the values of SS are decreased. The exceptions for the Salinas dataset, while increasing $\beta$ from $0$ to $2$ is possibly due to the fact that we do not use the entire training data in Equation (9) and use of $|S_{t}|=100$ in Equation (9) is not adequate to capture the structure of the data faithfully for the Salinas dataset. As discussed earlier, setting the value of $|S_{t}|$ is crucial for approximating Equation (7) with Equation (9). We have set $|S_{t}|=100$ for all three datasets empirically. However, choosing an optimum value of $|S_{t}|$ for each dataset is expected to avoid the occurred exceptions.

As we increase the value of $\beta$, there is more stress to reduce the loss function Equation (9). In most cases, increasing $\beta$ results in a drop in SS. This clearly suggests that the loss function Equation (9) that we use, is a computationally efficient substitute for the original SS defined in Equation (7).

We have included results of the thematic maps (Fig. 2) and it reveals that our proposed method is capable of selecting useful bands that can broadly capture the land cover types. Figure 2 illustrates thematic maps of the entire region captured in the Indian pines dataset. Figure 2(a) shows ground truth labels. Figures 2(b), 2(c), 2(d) are thematic maps of the Indian pines data set using the class labels obtained from the SVM classifier trained on the considered training set represented with $70$ bands selected by FSMLP_struct with $\beta=0$, i.e., by the method FSMLP, and FSMLP_struct considering $\beta=20$, and $\beta=50$, respectively.

Figure 2 ensures that even with the increasing stress on the structure-preserving regularizer $E_{struct}$, our proposed band selection method FSMLP_struct is able to select bands that maintain a good land cover classification performance.