# Unsupervised Feature Selection for Outlier Detection on Streaming Data to Enhance Network Security
## 4 Unsupervised Feature Selection for Streaming Outlier Detection
### Model for Scoring and Clustering Features
Apart from the complexity of \(\text{Loda}_{\text{Cont}}\) in time with \(\mathcal{O}(hd^{-\frac{1}{2}})\) and space \(\mathcal{O}(h(d^{-\frac{1}{2}}+b))\), referring to the naive implementation of continuously updated histograms where \(h\) is the number of histograms and \(b\) the number of histogram bins, the identification of relevant features does not increase the complexity. This is because the statistical test performed is linear with respect to the number of projections \(h\) and number of features \(d\) and only increases the complexity in big \(\mathcal{O}\) notation by a negligible constant [52]. We have integrated the functionality of relevant feature identification of \(\text{Lodacont. }\) in UFSSOD as a fundamental part and are able to produce feature scores \(s_{fi(t)}\) for the \(i\)th feature \(f_{i}\) at each time step \(t\) for one sample \(\mathbf{x}_{t}\), resulting in a one-dimensional array \(\mathbf{s}_{f}=\{s_{f1},s_{f2},...,s_{fd}\}\) of \(d\) feature scores per sample. Similarly to the continuous updating of the histograms, we propose to continuously update the feature scores for each sample by incremental averaging. There are various approaches discussed in [13], e.g., Exponentially Weighted Moving Average, that are better able to cope with occurring concept drifts in the feature scores while incrementally averaging them. As of now, however, we apply the incremental average as given per Equation (6) with a continuous counter value \(n_{t}\) for each new data instance, in order to obtain the averaged array of feature scores \(\mathbf{\bar{s}}_{f}\) but reserve the right to use more advanced moving methods in future work. While only preserving \(d\) values for the current average scores, one value for the continuous counter \(n_{t}\) and performing \(d\) updates of the scores, both the space and time complexity for each feature score averaging is \(\mathcal{O}(d)\) when applying [PERSON]'s algorithm. This does not significantly increase the overall complexity of UFSSOD since \(d\) is fixed. A summary of the scoring functionality of UFSSOD for both the outlier score and the feature scores, inclusive of their processing, is shown in Algorithm 2. \[\mathbf{\bar{s}}_{fi(t)}=\frac{1}{n_{t}}(\mathbf{\bar{s}}_{fi(t-1)}n_{t-1}+s_{fi(t)}) \tag{6}\]  
Since the features within the subset are not only influencing the efficiency of the OD task but also the cardinality of the set significantly, the number \(\gamma\) referring to the top-features is crucial. However, this is an optimization problem where the intention is to optimize the solution in such a way that the highest accuracy can be reached together with the lowest execution time achieved, e.g., by a smaller number of features. According to [8] it is still a challenging and known problem to determine the optimum number of features to select. Since this mostly applies for the supervised and offline case, we are stating that finding an optimal solution and therefore a point of equilibrium between the best classification with the lowest computational performance is impossible in the online setting. When the Unsupervised Online OD module demands a new subset of the top-\(\gamma\)-features, UFSSOD clusters \(\mathbf{\bar{s}}_{f}\) to obtain the cluster(s) with the top scoring features. Even if clustering in one-dimensional space is not as trivial as it sounds, some algorithms are capable of solving this task, e.g., by applying Kernel Density Estimation (KDE), having a strong statistical background and seeking for local minima in density to split the data into clusters. However, we are proposing the k-mean adaption for one-dimensional clustering \(\text{\sc{Kmeans.1d.dp}}\)[57; 58]. It achieves \(\mathcal{O}(kd)\) by the optimization proposed in [58] for both time and space complexity, where \(k\) refers to the number of clusters built. Three improvements have been made for \(\text{\sc{Kmeans.1d.dp}}\) for the application within UFSSOD.