Anomaly Detection with Score functions based on Nearest Neighbor Graphs
Anomaly Detection with Score functions based on Nearest Neighbor Graphs
复制标题
DOI：
--
复制
发表时间：
2009-10
影响因子：
8.6
通讯作者：
Manqi Zhao;Venkatesh Saligrama
中科院分区：
文献类型：
--
作者：
Manqi Zhao;Venkatesh Saligrama
我们针对高维数据提出了一种新颖的非参数自适应异常检测算法，该算法基于从 n 点标称数据上的最近邻图导出的得分函数。每当测试样本的分数低于 α（应该是所需的误报级别）时，就会宣布异常。由此产生的异常检测器被证明是渐近最优的，因为对于异常密度是标称密度和已知密度的混合的情况，对于指定的误报级别 α，它始终是最强大的。我们的算法计算效率高，维度呈线性，数据大小呈二次方。它不需要选择复杂的调整参数或函数逼近类，并且可以适应局部结构，例如维数的局部变化。我们在高维特征空间中的人工和真实数据集上演示了该算法。
We propose a novel non-parametric adaptive anomaly detection algorithm for high dimensional data based on score functions derived from nearest neighbor graphs on n-point nominal data. Anomalies are declared whenever the score of a test sample falls below α, which is supposed to be the desired false alarm level. The resulting anomaly detector is shown to be asymptotically optimal in that it is uniformly most powerful for the specified false alarm level, α, for the case when the anomaly density is a mixture of the nominal and a known density. Our algorithm is computationally efficient, being linear in dimension and quadratic in data size. It does not require choosing complicated tuning parameters or function approximation classes and it can adapt to local structure such as local change in dimensionality. We demonstrate the algorithm on both artificial and real data sets in high dimensional feature spaces.