Algorithms for Mining Distance-Based Outliers in Large Datasets-猫眼课题宝

DOI：

发表时间：

1998-08

期刊：

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Edwin M. Knorr;R. Ng

本文探讨在大型多维数据集中寻找异常值（例外情况）。异常值的识别能够在诸如电子商务、信用卡欺诈，甚至职业运动员成绩统计分析等领域发现真正意想不到的知识。我们所见到的在大型数据集中寻找异常值的现有方法只能有效地处理数据集的两个维度/属性。在此，我们研究基于距离（DB -）的异常值概念。在提供正式和实证证据表明DB -异常值的有用性的同时，我们重点关注用于计算此类异常值的算法的开发。首先，我们提出两种简单算法，复杂度均为O(kN’)，其中k为维度，N为数据集中的对象数量。这些算法很容易支持具有两个以上属性的数据集。其次，我们提出一种基于单元的优化算法，其复杂度相对于N是线性的，但相对于k是指数级的。第三，对于主要存储在磁盘上的数据集，我们提出基于单元算法的另一个版本，它保证对数据集最多进行3次遍历。我们提供……

This paper deals with finding outliers (exceptions) in large, multidimensional datasets. The identification of outliers can lead to the discovery of truly unexpected knowledge in areas such as electronic commerce, credit card fraud, and even the analysis of performance statistics of professional athletes. Existing methods that we have seen for finding outliers in large datasets can only deal efficiently with two dimensions/attributes of a dataset. Here, we study the notion of DB- (DistanceBased) outliers. While we provide formal and empirical evidence showing the usefulness of DB-outliers, we focus on the development of algorithms for computing such outliers. First, we present two simple algorithms, both having a complexity of O(k N’), k being the dimensionality and N being the number of objects in the dataset. These algorithms readily support datasets with many more than two attributes. Second, we present an optimized cell-based algorithm that has a complexity that is linear wrt N, but exponential wrt k. Third, for datasets that are mainly disk-resident, we present another version of the cell-based algorithm that guarantees at most 3 passes over a dataset. We provide

Algorithms for Mining Distance-Based Outliers in Large Datasets

文献摘要

被引文献

相似文献