# Online Streaming Feature Selection via Conditional Independence
## 4 Online Streaming Feature Selection Algorithms  
### The ConInd Algorithm and Analysis  
The _ConInd_ framework is used with online feature selection for filtering of streaming features. We provide the detailed proposal of the _ConInd_ algorithm, as illustrated in Figure 6. In the _ConInd_ algorithm, \(CFS\) is a candidate feature set of current time, whereas \(f_{i}\) is a new feature at time \(t_{i}\).  
**Filtering 1:**_Filtering of null-conditional independence_: In Steps 5 and 6, the filtering of null-conditional independence is executed. If \(f_{i}\) is an irrelevant feature with a class attribute \(C\), the feature \(f_{i}\) is discarded. Otherwise, the feature \(f_{i}\) is further used in the filtering of single-conditional independence.  
**Filtering 2:**_Filtering of single-conditional independence_: The filtering of single-conditional independence is orderly divided into two step categories: Steps 8-11 involve the filtering of single-condition independence 1, whereas Steps 12-15 involve the filtering of single-condition independence 2.  
* _Filtering of single-conditional independence_ 1: For each feature in the \(CFS\), we determine the conditional independence with the class attribute \(C\). If \(\exists f\in CFS\), \(s.t.\)\(f_{i}\bot C|[f]\), then discard \(f_{i}\), because it is a redundant feature. Next, jump to Step 3 and continue to determine the next new feature \(f_{i+1}\). On the contrary, if \(\exists f\in CFS\), \(s.t.\)\(f_{i}\bot C|[f]\), then feature \(f_{i}\) is non-redundant with the class attribute \(C\). The feature \(f_{i}\) is then included in the \(CFS\). It is validated through the filtering of single-conditional independence 2.
* _During the filtering of single-conditional independence_ 2: For the new feature \(f_{i}\), the conditional independence of each feature in the \(CFS\) expected for \(f_{i}\) is determined one feature at a time. If \(f\in CFS-\{f_{i}\}\) s.t. \(f\bot C|[f_{i}]\), discard \(f\) from \(CFS\) and jump to Step 3. The reason is that \(f\) and \(C\) are conditionally independent under the condition of \(f_{i}\). Therefore, the feature \(f\) is unnecessary if \(f_{i}\in CFS\). On the contrary, if \(f\in CFS-\{f_{i}\}\), \(s.t.\)\(f\bot\)\(C|[f_{i}]\), the feature \(f_{i}\) is kept in the \(CFS\). Then, we continue filtering for multi-conditional independence.  
**Filtering 3:**_Filtering of multi-conditional independence_: As indicated in Steps 16-20, for the \(CFS\), each feature \(f\) in the \(CFS\), \(y\bot C|subSet\), is determined under the condition of \(subSet\subseteq CFS-\{y\}\). If \(y\bot C|subSet\), then feature \(y\) is redundant and is discarded from \(CFS\). Through a continuous loop in Steps 16-20, all redundant features in the \(CFS\) are discarded due to the arrival of new features.  
The _ConInd_ algorithm uses the notation \(f_{i}\bot C|S\), \(S\subseteq CFS-\{f_{i}\}\), to denote conditional independence. To evaluate \(f_{i}\bot C|S\), _ConInd_ uses the \(p\)-value returned by the \(G^{2}\) test for discrete data and _[PERSON]'s z-test_ for continuous data to measure it, with a significance level of 0.05 or 0.01 often used. In the present study, we set the significance level threshold value to 0.05.  
Assuming that \(\alpha\) is a given significance level of 0.05 and \(\rho\) is the \(p\)-value returned, \(f_{i}\bot C|S\) defines the null hypothesis (\(H_{0}\)). \(f_{i}\) and \(C\) are conditionally independent given \(S\), _iff_\(\rho>\alpha\). \(f_{i}\bot C|S\) defines the alternative hypothesis (\(H_{1}\)). \(f_{i}\) and \(C\) are non-conditionally independent given \(S\), _iff_\(\rho\leq\alpha\).