Fuzzy Rank Based Parallel Online Feature Selection Method using Multiple Sliding Windows

1 Introduction

In today's world the size of the datasets increase very rapidly, which leads to the presence of noisy, irrelevant, and redundant features that degrade the performance of the learning algorithm. So, Feature Selection (FS) is applied to overcome these problems by discarding irrelevant and redundant features from the original feature set. Feature selection is the process of selecting a subset of features from the original feature set which are relevant to the target class. A variety of feature selection algorithms have been developed in the literature [4, 10, 19, 20], and it has been shown that FS improves the performance of the learning algorithm by increasing the prediction accuracy and thus reducing the burden for the learning algorithms. However, most of the existing feature selection algorithms are batch processing only, which means all the features of the datasets are available before the feature selection process is computed.

These traditional feature selection methods are not suitable when the features are arriving dynamically. Similarly in case of real-world applications [6, 25], all the features are not available before the feature selection process starts. Some of the examples are remote sensing images [18], email spam filtering [13, 29], texture-based image segmentation [23], network intrusion detection [32], and behavioral changes of hot topics in Weibo. In such cases, the features are generated dynamically, one after the other or as a group. It is also not feasible to wait until all the features have arrived before the learning process starts, and for the failure to implement traditional selection algorithms. So, online feature selection was introduced to cope with streaming features. In streaming data the features are arriving in two ways: 1) The number of features is fixed and the instances arrive dynamically, where patterns keep changing, and 2) different features may arrive dynamically at a given point in time. Some of the online feature selection methods available are Grafting [15], Alpha-Investing [34], Online Streaming Feature Selection (OSFS) [26], Online Group Feature Selection (OGFS) [24], Scalable and Accurate On Line Approach (SAOLA) [31], and Online Streaming Feature selection Using Sliding Window (OSFSW) [27]. There are some drawbacks to the above-mentioned online feature selection methods. Grafting [15] is good at discarding most of the redundant features and irrelevant features, but it requires the number of features in advance for calculating the regularization parameter (λ). Alpha-Investing [34] is good at handling large datasets, but it fails to remove the redundant features among the selected features. As a result, the error rate for this method is rather high. OSFSW uses a sliding window method for selecting the features from the online streaming data and it needs two stages for selecting the features. To overcome the drawbacks mentioned above, we proposed Online Streaming Multi Window Feature Selection method (OSMWFS) processes in parallel for selecting the features using the fast-mRMR feature selection method [17].

The proposed OSMWFS method uses the concept of multiple sliding windows being processed in parallel. In this method, instead of crisp values, we use fuzzy data for feature selection. The fuzzy features collected from the multiple sliding windows are passed to fuzzy fast-mRMR analysis for selecting the candidate features and rank the features. The fast-mRMR feature selection is used to reduce runtime by processing the redundancy of the candidate features only for the already selected relevant features, instead of the entire dataset. The process is continuous until some stopping criteria are met. OSMWFS method uses a fuzzy rank aggregation method for assigning the final ranks for the features present in the candidate feature sets. Then we select the top ‘n’ (Here ‘n’ is set to 3 in our proposed method) ranked features from the aggregate ranked features sets. Rank aggregation helps in discarding the redundant features present in other candidate feature sets. It also reduces the time needed to select the optimal features. To compare the performance of the proposed method, four state-of-the-art online streaming feature selection algorithms, namely Alpha-Investing, OSFS, SAOLA, and OSFSW are used over publicly available benchmark datasets. We use performance measures like classification Accuracy, Precision, Recall, F1-Score, time taken, and the number of features selected to validate the performance of the proposed OSMWFS method over the available state-of-the-art online streaming feature selection methods. The highlights of the proposed OSMWFS method are as follows:

1. No chance of eliminating potential candidate points of time since we are using ranking aggregation,

2. Parallel processing reduces the time required for FS, and

3. Fast mRMR + fuzzy Ranking on multiple windows enhances performance.

The remainder of the paper is organized as follows. Section 2 explains the related work. Section 3 explains the proposed work, section 4 presents the dataset description and experimental setup, Section 5 contains result analysis, and finally, section 6 offers the conclusion and future work.

2 Related Work

For the past two decades, feature selection, has been used as an efficient method to handle large dimensionality and used for finding an optimal subset of features. In general, feature selection methods are divided into four methods, namely: filter, wrapper, embedded, and hybrid methods. These feature selection methods are suitable and perform well when all the candidate features are available before a learning process starts. However, they are not applicable for real-world applications where the features are arriving one after the other at a regular interval of time. In the following paragraphs, we are going to discuss the available online feature selection methods, their merits, and demerits from different researchers.

Perkins and Theiler 2003 proposed a streaming feature selection namely Grafting algorithm [15]. It uses a stage wise gradient descent approach. The proposed method can eliminate all the available redundant features. For determining the value of the tuning parameter (λ), it requires all the candidate features in advance.

Zhou et al. 2005 proposed Alpha-Investing for streaming feature selection [34]. It overcomes the overfitting problem by dynamically adjusting the threshold for adding the feature to the model and also suitable for handling huge feature sets. The drawback of this method is that it evaluates the features only one time and discards to find the redundant features between the selected features. Therefore, the accuracy of this method is low.

Wu et al. 2010 proposed Online Streaming Feature Selection (OSFS) and Fast-OSFS for streaming feature selection based on feature relevance [26]. OSFS uses the Fisher Z-test and G² test for removing the redundant and irrelevant features from the streaming features. OSFS attains high accuracy with lesser features than Alpha-Investing and Grafting. It is suitable for high redundant features but, its runtime increases with the increase of non-redundant features.

In [11] proposed GFSSF (Group Feature Selection with Streaming Features) based on group feature selection. It works at two levels, the group level, and the individual feature level. It uses the concept of mutual information and entropy for selecting the features. GFSSF simultaneously completes the feature selection both at the individual feature level and group level. When a new feature arrives first, it invokes a feature selection level for processing in the present group. The group-level feature selection is invoked when all the features of a group have arrived. GFSSF performs stream feature selection at the group level, individual level, or both.

In [23] proposed OGFS (Online Group Feature Selection) for streaming features based on the knowledge of group information. It consists of two stages inter-group and intra-group feature selection. In intra-group selection, features are selected based on spectral graph theory. In inter-group selection, the optimal feature subset is selected based on global group information by using the Lasso linear regression model. The disadvantage of OGFS is during intra-group selection; it requires a positive parameter number in advance and needs to select an optimal value.

In [22] uses sparsity regularization and truncation techniques for the online feature selection method. Jialei Wang et al. use two different types of inputs for learning; 1) learning with full input, and 2) learning with partial inputs. The proposed methods are not able to address the problem with online multiclass classification and regression problems.

In [7] proposed a new online streaming feature selection algorithm class OS-NRRSAR-SA using rough sets. Any feature selection require prior knowledge about the feature space but in case of rough set-based data mining any domain knowledge is required other than the available data. For controlling the unknown feature space in OSFS, the OS-NRRSAR-SA method uses classical significance analysis concept available in rough set theory and fails to discard redundant features.

In [31] proposed SAOLA (Scalable and Accurate On Line Approach) for online streaming feature selection. It uses a novel pairwise correlation among the features when features are arriving one by one. Yu et al. extend the SAOLA to group-SAOLA that deals with group features. It selects the feature groups that are sparse at the feature level and group level. For increasing the accuracy of the learning algorithm, it obtains a solution that is sparse at both intra and inter-groups simultaneously. It eliminates the redundant features from both the groups and are sparse at feature and group levels. The drawback of these methods is that it is complicated to obtain optimal value for the relevance threshold.

In [33] proposed online streaming feature selection using the sampling technique and the correlation between features (STCF). It improves the performance of OSFS for high-dimensional data by using sampling techniques. Sampling techniques are used for handling imbalanced data and increasing the accuracy of the model.

In [12] proposed two streaming feature selection namely multilabel feature selection with label correlation (MUCO) and multilabel streaming feature selection (MSFS), respectively based on fuzzy Mutual Information for Multilabel learning [12]. There are two steps in MSFS namely online redundancy analysis and online relevance analysis for finding optimal feature subsets. In addition to this, the correlation between the label set are also used in this approach.

In [35] proposed online feature selection for high dimensional class imbalanced data. For real world applications like fraud detection and medical diagnosis, available data is mostly class imbalanced and has high dimensions. Existing online feature selection algorithms are discarding the small class data which has significant role in these applications. So to overcome these problem Zhou et al. proposed a new online feature selection algorithm called K-OFSD based on Dependency in K-nearest neighbors. For selecting relevant features, the algorithm uses information of nearest neighbors.

In [16] proposed filter based online feature selection method called Online Streaming Feature Selection based on Mutual Information (OSFSMI) and Online Stream Feature Selection Based on Mutual Information with fixed number of features (OSFSMI-k) using mutual information [16]. The proposed method uses MI in a streaming manner for finding correlation between features. Using this algorithm the author is able to find relevant features and can also discard redundant features.

In [27] proposed online streaming feature selection, namely OSFSW, for high redundant data using sliding window technique. In OSFSW, the features are added into the window that is highly relevant with the class label, then later, it uses this window to find the redundancy between the selected relevant features and already available candidate features. OSFSW uses a fixed-size sliding window size. In [28] proposed an extension to OSFSW, namely OSFASW that uses a self-adaption technique for selecting the size of the window.

In [36] proposed online streaming feature selection for high dimensional data using adapted neighborhood rough set. Adapted neighbours are detected using rough set neighborhood relation. Using this approach Zhou et al. is able to select maximal-relevant and maximal significant features.

In [3] proposed Dynamic Correlation-based Feature Selection (DCFS) for improving the performance of feature drifting in data streams. Proposed Correlation based Feature Selection (CFS) uses heuristic evaluation for scoring feature subsets. Relevant feature subsets are updated dynamically using CFS and also uses adaptive strategy for drift monitor.

In [7] proposed an extension to OS-NRRSAR-SA algorithm for eliminating redundant features [9]. The author uses online redundancy analysis for discarding redundant features and non-significant features are eliminated using online significance analysis.

3 Proposed Work

Consider a dataset F with n features F = {f₁, f₂, . . ., f_n}, the main objective of any feature selection method is to find an optimal feature subset say (F′) with d feature (where d << n). The objectives of the optimal feature subset (F′) are; i) F′ is an optimal solution, ii) fi'∈ F' are the most relevant features for target class (c), and iii) The error rate for F′ is very low than that of other feature subsets. So, to obtain an optimal feature set, the proposed OSMWFS method uses fuzzy fast-minimum Redundancy and Maximum Relevance feature selection method. It uses a greedy approach during the feature selection process for reducing more number of MI computations. Also to increase the computational speed of the feature selection process, we use parallel processing. To achieve parallel processing the proposed method uses CUDA programming model.

The primary goal of any feature selection is to select the features, which has high relevance with the target class c. So, to find the maximum relevant features the proposed fast-mRMR method uses Eqn. (1) to find the Max-Relevance features with the target class c [14].

where I(f_i; c) is the mutual information between the feature and the target class.

The proposed method uses fuzzy features for feature selections. The fuzzy mutual information [8] between the fuzzy features are calculated by using the Eqn. 2.

where X and Y are two fuzzy variables, H(X), H(Y) are fuzzy entropy values for X and Y, respectively, and H(X, Y) fuzzy joint entropy for X and Y. The fuzzy entropy and fuzzy joint entropy on F can be calculated by using Eqns. (3), (4) and (5), respectively.

From the literature, it is a known fact that features selected according to maximum relevance may have more redundant features, which means the dependency among the selected features may be large. The class discriminate power will not be affected much when one of the two highly dependent features are removed. Therefore, Maximum-relevance is combined with minimum-Redundancy [5]. And the minimum redundancy between the selected features are calculated by using Eqn. (6).

The mRMR score for the feature set F is obtained by using the Eqn. (7)

The fuzzy ranks (Rank_f) are assigned by using Eqn. (8), i.e., the ratio between R and mR

3.4 Framework of OSMWFS Method

Figure 1 explains the OSMWFS method framework for online streaming features using multiple sliding windows that are processed in parallel. In Figure 1 W_1, W_2, W_3, ... , W_N represents ‘N’ Sliding windows and CF_1, CF_2, CF_3, ..., CF_N represents the candidate features obtained by using fast-mRMR feature selection. In this proposed method, the features are arriving one by one at regular intervals of time. Features are added to the sliding windows in parallel one after another upon arriving until the windows are full. When the windows are full, it stops adding the feature to the current sliding windows, and it starts adding the features into other windows. Now the features that are present in the full windows are processed in parallel into fuzzy features using the Gaussian membership function. These fuzzy features are taken as input for fast-mRMR analysis and final candidate features are selected and are assigned with fuzzy rankings by using Eqn. (8) based upon the minimum redundancy and maximum relevance values of the features. By using fast-mRMR feature selection method we are able to remove the redundant and irrelevant features from the available features. Finally, the selected ranked features from the fast-mRMR feature selection method are added to the candidate feature sets (CF).

Figure 1

Framework of proposed OSMWFS Method.

The relevant features that are selected into one candidate feature set may go to irrelevant with the features that are selected in another candidate feature set in due course and vice versa. So to overcome this, the ranked features presented in each candidate feature set are aggregated with previously selected feature sets (SF) using fuzzy Gaussian rank aggregation method [2, 21]. Top ‘n’ ranked features are selected from the aggregate ranked features. These top features are then assigned to the selected feature set. The process continues as new features are streaming, and the candidate feature sets continue to change. The process is not stopped until some stopping criteria are met. Finally, at the end the features that are available in the selected feature set are considered as the optimal feature subset.

3.4.1 Algorithm

Algorithm 1 explains how the OSMWFS method is works. Line no 5–8 the reading of streaming features into the sliding windows (Buffer_i). Line no 9–13 represents the parallel execution of each sliding window for the selection of optimal features using fast-mRMR analysis. Algorithm 2 represents the fast_mRMR analysis and returns candidate features as output. The ranked candidate features from each sliding window of fast-mRMR analysis are assigned with final ranking by aggregating the feature ranks present in the candidate feature sets and the ranked features that are selected from the previous step. Fuzzy rank aggregation is done by using Eqn. (10). Here fuzzy rank aggregation is used for selecting the top ‘n’ features. In algorithm 1, line 13 represents the rank aggregation process. The optimal features are selected from line 13 of algorithm 1.

(10) μfi(x)=12πσfi2exp(-12[(x-x¯fi)2σfi2])

where x¯fi mean and σ¯fi2 variance position of features f_i.

Algorithm 1

OSMWFS Method Algorithm

Algorithm 2

fast_mRMR (Buffer_i)

4 Dataset Description

5 Result Analysis

The proposed OSMWFS method is compared with four state-of-the-art streaming feature selection methods, namely Alpha-Investing, OSFS, SAOLA, and OSFSW, over eight publicly available benchmark datasets. We use classification measures for comparing the performance of the proposed method with four state-of-the-art streaming feature selection methods. The measures are namely Accuracy, time taken, and number of features selected. First, we analyze the time taken for different window sizes (sws) to find the optimal number of features. Table 2 describes in detail the time taken and the number of features selected by the proposed algorithm for different sliding window sizes.

From Table 2, we observe that the time taken and the number of features selected is comparatively less and consistent for sws size 20. So, from this observation, the sliding window size is set to 20 in further experimental setups. When the window size increases, the running time and number of selected features also increases.

Table 3 represents the classification accuracy obtained by the state-of-the-art streaming feature selection methods like Alpha-Investing, OSFS, SAOLA, OSFSW, and proposed OSMWFS method using a k-NN classifier. Here the k value is taken as 5 in our experiments. The bolded values indicate the highest accuracy obtained by the OSMWFS method over other streaming feature selection methods. The italic values represent the second-highest accuracy obtained by the OSMWFS method. It is inferred from Table 3 that, for lymphoma and leukemia datasets proposed OSMWFS method gives nearly equivalent accuracy to that of the SAOLA method. We can observe that the prediction accuracy of the Madelon dataset is very low nearly 60 % for all the methods because it is a synthetic dataset so it includes more noisy and redundant features.

Table 4 represents the classification accuracy obtained by the state-of-the-art streaming feature selection methods like Alpha-Investing, OSFS, SAOLA, OSFSW, and proposed OSMWFS method using an SVM classifier. The bolded values indicate the highest accuracy obtained by the proposed method over other streaming feature selection methods. The italic values represent the second-highest accuracy obtained by the proposed method. However, for lymphoma and leukemia datasets proposed method gives nearly equivalent accuracy to that of the SAOLA method. We can observe that the prediction accuracy of the Madelon dataset is very low nearly 60 % for all the methods because it is a synthetic dataset so it includes more noisy and redundant features.

Table 5 represents the classification accuracy obtained by the state-of-the-art streaming features selection methods like Alpha-Investing, OSFS, SAOLA, OSFSW, and proposed OSMWFS method using Decision Tree classifier. The bolded values indicate the highest accuracy obtained by the OSMWFS method over other streaming feature selection methods. The italic values represent the second-highest accuracy obtained by the OSMWFS method. We can observe that the prediction accuracy of the Madelon dataset is very low nearly 60 % for all the methods because it is a synthetic dataset, so it includes more noisy and redundant features.

We further analyze the performance of the proposed OSMWFS method over other online streaming feature selection methods. Table 6 shows the run time and number of features selected by the state-of-the-art streaming feature selection methods and the proposed OSMWFS method. The run time for the datasets like the ionosphere, Made-lon, is less for Alpha-Investing than the other methods and proposed method. This is because Alpha – Investing only considers the newly added features and the discarded features are never considered again. However, the number of features selected for the OSMWFS method is very low when compared with the Alpha-Investing method. Moreover, the prediction accuracy is low for Alpha-Investing when compared with OSMWFS method (as observed from Tables 3–5). From Table 6, we inferred that the OSMWFS method outperforms for most of the datasets over the other streaming feature selection methods.

Table 7 represents the precision, recall, and F1-Score for ‘k-NN,’ SVM, and Decision Tree classifier for eight benchmark datasets over four state-of-the-art online feature selection (OFS) methods and proposed OSFSWFS method. Precision measures the probability of data predicted as positive to be positive. It is the measure of the ratio of True Positive by true positive plus false positive (i.e., TP/(TP+FP)).

A recall is referred to as True Positive Rate or sensitivity, and it is the measure of the ratio of True Positive by True Positive plus False Negative (i.e., TP/(TP+FN)). The columns represent measures like Precision, Recall and F1-Score over the three classifiers, whereas the rows represent the datasets and online feature selection methods. From Table 7, we infer that the performance of the proposed method is good when compared to the other OFS methods.

Receiver Operating Characteristic Curve (ROC Curve) is used to show how good a given learning model. It uses sensitivity and Specificity values for the representation. The Area Under The ROC Curve (AUC) is used to measure how best a given model varies between the classes. If the area is high, then the model is best and vice versa.

Figures 2 – 9 represent the Receiver Operating Characteristic (ROC) curve given by SVM classification over the proposed method and other state-of-the-art online feature selection methods for eight benchmark datasets. On X-axis False Positive Rate and Y-axis True Positive Rate values are represented.

Figure 2

ROC Curve for Ionosphere Dataset

Figure 3

ROC Curve for Madelon Dataset

Figure 4

ROC Curve for Lymphoma Dataset

Figure 5

ROC Curve for Gisette Dataset

Figure 6

ROC Curve for Leukemia Dataset

Figure 7

ROC Curve for Prostate Dataset

Figure 8

ROC Curve for rcv1 Dataset

Figure 9

ROC Curve for real-sim Dataset

From Figures 2 – 9, it is observed that the area under the ROC curve is low for most of the online feature selection method over the proposed OSMWFS method. From Figures 2 – 9, we observe that the AUC is more for datasets like Ionosphere, Madelon, leukemia, rc1and real-sim data. However, for other datasets, the AUC is not high for the proposed OSMWFS method but is nearby the top online feature selection method.

6 Conclusion and Future Scope

In this paper, we proposed the OSMWFS method using multiple sliding-windows that are processed in parallel, and the fuzzy fast-mRMR feature selection method is used for selecting features with minimum redundant and maximum relevant. The use of fuzzy fast-mRMR feature selection is to reduce the number of MI computations between the features and the class labels. The use of multiple sliding windows is to speedup the process of retrieving the streaming features. In this digital era, data keeps on changing rapidly and dynamically to cope up with this we need parallel processing. And finally the fuzzy rank aggregation is used to eliminated the redundant features between the previously selected feature and present selected feature set during the feature selection process. The selected features have minimum redundancy and maximum relevance with the class variable. The proposed method has a low number of features and high classification accuracy. The experimental results show that the OSMWFS method outperforms other online streaming feature selection methods. Our empirical study demonstrated that; 1) OSMWFS method is best suitable for high dimensional streaming data, 2) Parallel processing reduces the time required for FS, and 3) OSMWFS enhances the performance of the model.

Even though the OSMWFS method outperforms other online streaming features selection methods, the selection of sliding window size is static. In future, we will extend this work to fix the window size dynamically based on the data flow.