# Online Streaming Feature Selection via Conditional Independence
## 1 Introduction  
Feature selection [1; 2; 3; 4] is the most referenced method for reducing dimensions of features. It can efficiently combat the curse of dimensionality [5] by removing irrelevant and redundant features [6]. The final goal is to extract an \"optimal subset\" of features from the original features [3], so that the classifiers can learn from it to improve prediction accuracy and achieve better time complexity during classification. As an important direction for feature selection, streaming feature selection (_SFS_) assumes that the number of training instances is fixed while the number of features increases over time [2]. For the streaming feature, features flow in one at a time, and each feature is required to be processed online upon arrival. However, all the features cannot be present in advance. Therefore, traditional batch learning that assumes that the feature selection task is conducted in an off-line learning fashion and that all features of the training instances are given a priori is not suitable [3]. Recently, onlineselection of dynamic features has received significant attention [7]. In some situations, online feature selection can be performed upon feature arrival where features arrive sequentially over time, especially for online feature selection with streaming features (_OSFSF_) that aim to provide complementary methodology for addressing high dimensional data [5]. The goal of _OSFSF_ is to process the streaming features dynamically using the incoming streaming features one at a time [8-10]. There are several real-world application scenarios, such as streaming images captured through _CCTV_[11], fleeting hashtags on _Twitter_[12], feature collection in intrusion-detection systems [13], automatic classification of music genres in music television [14], and monitoring and analysis of environments [15]. In these applications, feature dimensions keep increasing while feature spaces become enlarged over time. Therefore, it is necessary to process online feature selection in real time to reduce processing complexity. There are several representative research efforts on _OSFSF_[16], e.g., _Alpha-investing_, _OSFS_, and _SAOLA_, but their strategies suffer from limited prediction accuracy or running time if the streaming features possess characteristics of low redundancy and high relevance, such as in real time medical diagnosis [17]. For such streaming features, many selected features would be generated. Experiments indicate that the existing methods highlighted above are restricted to such types of streaming features. The _Alpha-investing_ algorithm is unstable, and its prediction accuracy is significantly low on most datasets [16]. It selects numerous features from a candidate feature set because it does not re-evaluate the selected features. Hence, its performance is limited [6; 16; 18]. Although the _OSFS_ algorithm offers high prediction accuracy in many datasets, its running time increases exponentially with an increase in the number of features with low redundancy and high relevance [6]. The _SAOLA_ algorithm offers outstanding efficiency in running time and possesses few features but has low prediction accuracy [19]. To address the limitations of the abovementioned works, we propose a novel online algorithm, named _ConInd_, to process streaming features with low redundancy and high relevance. Unlike existing _OSFSF_ studies, we select a subset of relevant features through three-layer filtering according to a conditional independence analysis to improve the prediction accuracy, reduce running time, and reduce the number of features selected. We use a \(p\)-value to measure the conditional independence between features within a class attribute to discard irrelevant and redundant features from candidate feature sets. In addition, we regard the subset as an approximate _Markov blanket_. It is well known that _Markov blankets_[20] provide minimal feature sets required for the classification of a chosen response variable with maximum predictability.