# An Incremental Local Outlier Detection Method in the Data Stream
## 3 Results  
### Scalablity  
The proposed CLOF method was designed to detect outlier in data streams, where the varying sliding window width, k-nearest neighbor and data dimension were the main challenges for detection accuracy and efficiency. In this chapter, the efficiency, complexity, and scalability of the algorithm were analyzed based on synthetic datasets with different scales and known outliers, to obtain a much better understanding of the effect of data amounts and dimensions. Therefore, experiments were designed to verify: (i) the relation between the number of CLOF-affected data and the data scale \(N\); (ii) the dependence of the number of CLOF affected-data on parameter \(k\); and (iii) the dependence of the number of CLOF-affected data on the dimension \(d\); (iv) the efficiency of the proposed CLOF method \begin{table}
\begin{tabular}{l l} \hline \hline Input \(k\), \(X\), \(d\), \(n\), \(t\) and \(N=\left|X\right|>(2n-1)\). \\ Output: Outliersin \(X\) \\
1 & Collects \(n\) data as the first training set; \\
2 & Searches the kNN, RkNN, and SkNN for \(x_{i}\), and \(1\leq i\leq n\); \\
3 & Calculates CLOF(\(x_{i}\)), if CLOF(\(x_{i}\)) \(>1\), outlier count of \(x_{i}\) increased by 1; \\
4 & Collects a new data \(x_{n+1}\), deleting the obsolete data point \(x_{1}\); \\
5 & if the outlier count of \(x_{1}\geq t\) (\(1\leq t\leq n\)), \(x_{1}\) is an outlier; \\
6 & Searches the kNN, RkNN, and SkNN for \(x_{n+1}\), and \(2\leq i\leq n+1\); \\
7 & Updates the kNN, RkNN, SkNN, and CLOF for affected data; \\
8 & Calculates CLOF(\(x_{i}\)), if CLOF(\(x_{i}\)) \(>1\), outlier count of \(x_{i}\) increased by 1; \\
9 & Collects a new data \(x_{n+2}\), deleting the obsolete data point \(x_{2}\); \\
10 & if the outlier count of \(x_{2}\geq t\) (\(1\leq t\leq n\)), \(x_{2}\) is an outlier; \\
11 & Searches the kNN, RkNN, and SkNN for \(x_{n+2}\), and \(3\leq i\leq n+2\); \\
12 & Updates the kNN, RkNN, SkNN, and CLOF for affected data; \\
13 & Calculates CLOF(\(x_{i}\)), if CLOF(\(x_{i}\)) \(>1\), outlier count of \(x_{i}\) increased by 1; \\
14 & Continue with steps 4–13; \\
15 & Till the end of \(X\); \\
16 & Output the outliers in \(X\); \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The pseudocode of the CNN-based local outlier factor (CLOF) algorithm. compared to the kNN-based method (summarized as kLOF) and the composite nearest neighborhood (CNN)-based method without an incremental update strategy (summarized as CNN_WIUS). The kLOF method also used Equation (1) to estimate the local density of data, but only used the k-nearest neighbors to estimate the local outlier factor as follows:  
\[\text{kLOF}(x_{i})=\frac{\text{p}(x_{i})}{\frac{1}{|\text{kNN}(x_{i})|}\sum_{x _{k}\in\text{kNN}(x_{i}),i\
eq k}\text{p}(x_{k})} \tag{4}\]  
where \(|\text{kNN}(x_{i})|\) denotes the amount of objects in kNN(\(x_{i}\)). The expected value of kLOF equaled 1 when \(x_{i}\) and its kNN neighbors were sampled from the same distribution. If kLOF(\(x_{i}\)) was much larger than 1, then \(x_{i}\) would be an outlier. If kLOF(\(x_{i}\)) was equal or smaller than 1, then \(x_{i}\) would not be an outlier. By introducing the comparative analysis with the popular kNN-based method, the outlier detecting the performance of CNN based method was presented. The CNN_WIUS method used the same Equations (1) and (2) with the CLOF method to calculate the local density and local outlier factor of data. However, CNN_WIUS did not involve the incremental update strategy proposed in Section 2.3 compared to CLOF. All experiments were implemented in MatLabR2013a with a Windows 7 system running on a Core i5-4590 CPU (3.3 GHz). Similar rules as presented in [7] were used to define synthetic datasets with uniform (uniformly distributed in \([-1,1]\)) and standard Gaussian distributions (zero mean and unit covariance matrix), which were characterized as different number of data records (\(N\in\{100,\,200,\,\ldots\,,\,5000\}\)), different number of dimensions (\(D\in\{2,\,4,\,6,\,8,\,10\}\)), and different parameters \(k\) (5, 10, 15, 20).