# An Incremental Local Outlier Detection Method in the Data Stream
## 2 Materials and Methods
### Related Work
The most popular one is the kNN, which requires a user-supplied parameter, \(k\) to find the k-th nearest neighbor and to fix the size of the neighborhood set [22]. Another one is the distance-based neighbor, which needs to supply a unified distance for each data; for example, in a two-dimensional data set, a circle centered at data p can be drawn with the radius of the user-setting distance, and all of the data within this circle will form the local neighborhood of data p [23]. Unfortunately, the distance-based neighbor approach is not applicable to process data streams, due to the common problem of non-homogeneous data within them. Recently, the composite nearest neighborhood (CNN), including kNN, the reverse k-nearest neighbors (RkNN), and shared k-nearest neighbors (SkNN), have been proposed to flexibly model different local patterns of data, e.g., improving the false positive identification of outliers in the boundary of the data set [24]. The RkNN of an object p are essentially objects that have p in their kNN, and SkNN of object p are those objects that share one or more nearest neighbors with p.  
Calculation methods for LOF have been widely studied. The LOF strategy was firstly proposed in [20], where the local reachability density calculated in the kNN of data was used to indicate outlierness. The kNN-weight method (kNNW) is used the sum of distances to an object's kNN to reduce variation in scores, and to make the score less sensitive to the change of parameter \(k\)[25]. In [24], the distance of the k-th nearest object to the data p (abbreviated as kdist(p)) was used, and \(1/\text{kdist}(\text{p})\) was used to define the density of p. Influenced outlierness (INFLO), described as the comparison between the density of p and the average density in kNN and RkNN of p, was calculated. In the Local Distance-based Outlier Factor (LDOF) method, the average distance \(\overline{\text{d}}_{\text{p}}\) between p and the data within the kNN of p was calculated as the density estimation, and the comparison of \(\overline{\text{d}}_{\text{p}}\) to the average distance between data in the kNN of p was calculated as the outlierness [26]. The local density factor (LDF) replaces the density estimate by a variable-width Gaussian kernel density estimation (KDE) [27]. Recently, a relative density-based outlier score (RDOS) method involving the multivariate Gaussian kernel function was introduced, and it measured the local outlierness of objects with reference to their CNN [28]. Although many LOF methods have been proposed, few of them can be directly used in the outlier detection of data streams for the lack of an update strategy. In literatures [7; 8], incremental LOF methods based on kNN have been proposed, which have some limitations in describing the local characteristics of data [24]. Thus, in this paper, the incremental LOF method involving CNN (CLOF) is focused upon. To the best of our knowledge, none of the state-of-the-art approaches are designed for detecting local outliers in data streams with an incremental update method based on CNN. In a fixed sliding window with user-specified width selection, the density of data p based on the average distance from p to its CNN is calculated, and the CLOF(p) is estimated by comparing p's density with the average density in its CNN area. To follow the changes of data streams, a new data point has to be inserted into the sliding window, and an obsolete data point has to be deleted from the sliding window. Therefore, the influence of these updates on algorithm complexity is discussed through theoretical and experimental analysis, which have demonstrated that the amount of affected data is limited. Experiments performed on simulated and real life data sets are also used to verify the scalability and accuracy of the proposed algorithm.