面向高维流数据的离群值检测算法

Outlier detection algorithm for high dimensional data stream

累计局部离群因子(cumulative local outlier factor,C_LOF)算法能有效解决数据流中的概念漂移问题和克服离群点检测中的伪装问题,但在处理高维数据时,时间复杂度较高。为有效解决时间复杂度高的问题,提出一种基于投影索引近邻的累计局部离群因子(cumulative local outlier factor based projection indexed nearest neighbor,PINN_C_LOF)算法。使用滑动窗口维护活跃数据点,在新数据到达和旧数据过期时,引入投影索引近邻(projection indexed nearest neighbor,PINN)方法,增量更新窗口中受影响数据点的近邻。实验结果表明,PINN_C_LOF算法在检测高维流数据离群值时,在保持检测精确度的前提下,其时间复杂度较C_LOF算法明显降低。

Cumulative local outlier factor(C_LOF)algorithm can effectively solve the concept drift problem in data stream and overcome the camouflage problem in outlier detection,but it has high time complexity in processing high-dimensional data.To effectively solve the problem of high time complexity,a cumulative local outlier factor based projection indexed nearest neighbor(PINN_C_LOF)algorithm was proposed.A sliding window was used to maintain active data points,and a projection indexed nearest neighbor(PINN)method was introduced to incrementally update the neighbors of affected data points in the window when new data point arrived and old data point expired.Experimental results show that the time complexity of PINN_C_LOF algorithm is significantly lower than that of C_LOF algorithm on the premise of maintaining the detection accuracy.