一种基于密度近邻的增量式孤立点发现算法

A Density-Neighbors-Based Incremental Outlier Detection Algorithm

为了解决数据集更新时孤立点增量发现问题,提出一种基于密度近邻的增量式孤立点发现算法.当数据集更新时,该算法在确定出受影响的对象后,根据对象和其近邻间k-密度变化,建立对象的密度近邻序列.然后依据对象的密度近邻序列代价和其k-距离邻域的平均密度近邻序列代价,计算出受影响对象的增量异常因子(IOF)来表征对象的孤立程度,从而提高增量孤立点发现的效果.此外,由于只需重新计算这些受影响对象的IOF值,该算法还提高孤立点发现的速度.实验表明,该算法不仅在孤立点增量发现的效果上高于以往算法且减少算法的运行时间.

Aiming at the problem of incremental outlier detection with the dataset being updated, a density-neighbors-based incremental outlier detection algorithm is proposed. When the dataset is updated, the proposed algorithm identifies the affected objects and establishes the density neighbor sequences of the objects based on the change of the k-density of the object and those of its neighbors. According to the density neighbor sequence cost （DNSC） of the object and the average of the DNSC of k-distance neighbors of the object, the proposed algorithm calculates the incremental outlier factor（IOF） of each affected objects and the IOF value indicates the degree of the object as an outlier. Therefore, the proposed algorithm improves the effectiveness of incremental outlier detection. Moreover, it speeds up the outlier detection since the proposed algorithm recalculates the IOF values of these affected objects. The experimental results show that the proposed algorithm has a higher quality in outlier detection than the former incremental algorithms with the decrease of the running time.