# An Incremental Local Outlier Detection Method in the Data Stream
## 2 Materials and Methods
### Distance-Based Local Density and Outlier Factor Estimation  
The distance-based method was used to estimate the local density of an object corresponding to its CNN area. Given a set of \(D\) dimensional objects \(X=\{x_{1},x_{2},\ldots,x_{n}\}\), and \(|X|=n\) (the number of data in a sampling dataset or sliding window), where \(x_{i}\in\mathbb{R}^{D}\) for \(i=1,2,\ldots,n\), the distance-based method calculates the average distance from \(x_{i}\) to its \(k\) nearest neighbors \(\text{kNN}(x_{i})\) as the local density of \(x_{i}\):  
\[\text{p}(x_{i})=\frac{1}{k}\sum_{x_{j}\in\text{kNN}(x_{i}),j\
eq i}\|x_{i}-x_ {j}\| \tag{1}\]  
where \(\|x_{i}-x_{j}\|\) denotes the Euclidean distance between \(x_{i}\) and \(x_{j}\). This data-based density estimation in Equation (1) has many good properties, such as its non-parametric property and low computational complexity [21]. After calculating the local density of all objects, the CNN-based local outlier factor (CLOF) is calculated to measure the density deviation of an object \(x_{i}\) from its composite nearest-neighbor \(\text{CNN}(x_{i})\), and is defined as follows:  
\[\text{CLOF}(x_{i})=\frac{\text{p}(x_{i})}{\frac{1}{|\text{CNN}(x_{i})|}\sum_{ x_{k}\in\text{CNN}(x_{i}),i\
eq k}\text{p}(x_{k})} \tag{2}\]  
where \(|\text{CNN}(x_{i})|\) denotes the number of objects in \(\text{CNN}(x_{i})\). The expected value of CLOF is equal to 1 when \(x_{i}\) and its CNN neighbors are sampled from the same distribution, which indicates the lower bound of CLOF for outlier detection [28]. If \(\text{CLOF}(x_{i})\) is much larger than 1, then \(x_{i}\) would be an outlier. If \(\text{CLOF}(x_{i})\) is equal to or smaller than 1, then \(x_{i}\) would not be an outlier. An outlier count for each data \(x_{i}\) in the data stream is designed in this paper. The outlier count of \(x_{i}\) will be increased by 1 if \(\text{CLOF}(x_{i})\) is greater than 1. Furthermore, \(x_{i}\) is judged asan outlier when its outlier count is greater than or equal to a pre-defined threshold. For a fixed sliding window width \(n\), each data \(x_{i}\) can be processed \(n\) times by our CLOF method. In order to take advantage of the temporal correlation of data, this outlier determination criterion is designed. In contrast, many studies use a single-judgment criterion, which only judges the outlierness of a data when it is involved in the sliding window at the first time [7; 24]. As shown in Figure 1, the two-dimensional data set \(X\) consists of an outlier \(x_{1}\), a dense region, and a sparse region, where \(k=2\), \(x_{1}\) is an outlier, and \(x_{2}\) is at the border between the dense and sparse regions. The kNN, RkNN, SkNN, and CNN of \(x_{1}\) and \(x_{2}\) are separated by different lines. If only kNN is involved in calculating LOF as in the literature [7; 8], \(x_{1}\) and \(x_{2}\) have the same outlierness, which is obviously wrong. More comprehensively, if kNN, RkNN, and SkNN are involved in estimating the local neighborhood characteristics, \(x_{2}\) is surrounded by both dense and sparse data, and conversely \(x_{1}\) is only surrounded by dense data. Thus, \(x_{1}\) has much higher outlierness than \(x_{2}\), which is more accurate. For \(\forall x_{i}\in X\), the following Theorems 1-3 are proposed to estimate the amount of objects in local neighbours of \(x_{i}\). **Theorem 1**. : _The amount of objects in kNN\((x_{i})\) is k._  
Proof. : Follows directly from the definition of k-nearest neighbor (kNN). \(\square\)  
**Theorem 2**. : _Themaximal number of reverse k-nearest neighbors of a record \(x_{i}\) is proportional to k, exponentially proportional to the data dimension \(d\), and does not depend on the total number \(n\) in dataset \(X\)._  
Proof. : According to the theoretical proof in [7]: \(|\mathrm{RkNN}(x_{i})|\leq F=\Theta\Big{(}k2^{D}\sqrt{D}\Big{)}\), \(|\mathrm{RkNN}(x_{i})|\) is proportional to \(k\), exponentially proportional to the data dimension \(d\), and does not depend on \(n\). \(\square\)  
**Theorem 3**.