# Online Streaming Feature Selection via Conditional Independence
## 3 Framework for Streaming Features Filtering
### Framework for Filtering Conditional Independence
#### 3.2.2 Filtering of Single-Conditional Independence  
The selected features may become redundant with time. We use the filtering of single-conditional independence to first remove parts of redundant features from a candidate feature set _CFS_.  
The filtering of single-conditional independence is divided into two stages in order: filtering of single-conditional independence 1 and filtering of single-conditional independence 2.  
**Filtering of single-conditional independence 1:** The single-conditional independence is filtered under the condition of each feature in the _CFS_. The filtering process is as follows (Figure 4):  
Step (1): Let \(CFS=\{f_{1},f_{2},f_{3},f_{4},f_{5}\}\); \(C\) is a class attribute, and \(f_{6}\) is a new feature.  
Step (2): For each \(f_{i}\in CFS\), (i = 1, 2,..., 5), if \(\exists f_{i}\), \(s.t.\)\(f_{6}\)\(\bot\)\(C\)\(|\)\(\{f_{i}\}\), then discard \(f_{6}\).  
Step (3): Else \(CFS=CFS\cup\{f_{6}\}\).  
Step (4): Return _CFS_.  
When a new feature is added, every feature in the _CFS_ element is used as a condition for feature selection. Once conditional independence is met, the new feature will be discarded, as illustrated in Figure 4.  
**Proposition 2**.: \(C\) _is a class attribute, \(f_{i}\) is a new feature at time \(t_{i}\). If \(\exists\)\(f\in CFS\) satisfies the filtering of single-conditional independence 1, i.e., \(f_{i}\bot\)\(C\)\(|\)\(\{f\}\), then \(f\
ot\in MB(C)\)._  
Figure 4: Filtering of single-conditional independence 1.  
**Proof.** When one considers filtering of single-conditional independence 1, the following holds:  
If \(\exists f\
i CFS\), \(s.t.\)\(f_{1}\bot C|[f]\), through filtering of single-conditional independence 1, \(f_{1}\
otin CFS\), and using **Definition 2**, we obtain \(f_{1}\in S/CFS\cup\{C\}\)\(s.t.\)\(f_{1}\bot C|CFS\), \(S\) is a set of the feature space, then, \(f_{1}\
otin MB(C)\). Therefore, **Proposition 2** is proven. \(\square\)  
**Filtering of single-conditional independence 2:** The single-conditional independence is filtered on the condition of a new feature. The filtering process is as follows (Figure 5):  
Step (1): Let \(CFS=\{f_{1},f_{2},f_{3},f_{4},f_{5},f_{7}\}\), \(C\) is a class attribute, and \(f_{7}\) is a new feature that is already added in the \(CFS\) through the filtering of single-conditional independence 1.  
Step (2): For each \(f_{1}\) (i = 1, 2,..., 5), if \(\exists f_{i}\), \(s.t.\)\(f_{1}\bot C\)\(|f_{7}\), then \(CFS=CFS/\{f_{1}\}\).  
Step (3): Return \(CFS\).  
When a new feature is merged into \(CFS\), it is used as a single condition to determine independence with each of the other features in the \(CFS\). Once conditional independence is met, the other features in the \(CFS\) are discarded. For example, the features \(f_{3}\) and \(f_{5}\) are discarded, as illustrated in Figure 5.  
**Proposition 3.**_C is a class attribute, \(f_{1}\) is a new feature at time \(t_{i}\), \(f_{1}\in CFS\), If \(\exists f\in CFS/f_{1}\), that satisfies the filtering of single-conditional independence 2, i.e., \(f\bot C|[f_{1}]\), then \(f\
otin MB(C)\)._  
**Proof.** When the filtering of single-conditional independence 2 is considered, the following holds:  
If \(f_{1}\) is a new feature in \(CFS\), \(\exists f\
i CFS\), \(s.t.\)\(f\bot C|[f_{1}]\), and using **Definition 2**, we obtain the following:  
\(f_{1}\in CFS\), and features in the \(CFS\) are conditionally dependent on each other, \(s.t.\)\(f\bot C|CSF/\{f\}\), and \(f\
otin MB(C)\). Therefore, **Proposition 3** is proven. \(\square\)