数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学什么是基于距离的离群点？
如果数据集 S 中的一个对象 o 满足参数 p 和 d，即 DB(p, d)，则它是一个基于距离的 (DB) 离群点，如果 S 中至少 p 比例的对象与 o 的距离大于 d。换句话说，它不依赖于统计检验，可以将基于距离的离群点视为那些没有足够邻居的对象。
邻居是根据与给定对象的距离来表示的。与基于统计的方法相比，基于距离的离群点检测概括或合并了标准分布离群值检验背后的思想。因此，基于距离的离群点也称为统一离群点或 UO-离群点。
基于距离的离群点检测避免了可能与将观察到的分布拟合到某些标准分布以及选择离群值检验相关的过度计算。对于某些离群值检验，可以证明，如果对象 o 根据给定检验是离群值，则 o 对于某些适当表示的 p 和 d 也是 DB(p, d) 离群值。
例如，如果将距均值 3 个或更多标准差的对象视为离群值（考虑正态分布），则可以通过 DB(0.9988, 0.13s) 离群值来“统一”此表示。已经创建了几种用于挖掘基于距离的离群点的有效算法，如下所示：
**基于索引的算法** - 给定一个数据集，基于索引的算法利用多维索引结构（包括 R 树或 k-d 树）来搜索对象 o 周围半径 d 内每个对象的邻居。设 M 为离群点 d 邻域内对象的最大数量。因此，一旦发现对象 o 的 M + 1 个邻居，就可以确定 o 不是离群点。该算法的最低情况复杂度为 O(k * n²)，其中 k 是维数，n 是数据集中对象的数目。
**嵌套循环算法** - 嵌套循环算法与基于索引的算法具有相同的评估复杂度，但避免了索引结构的构建，并试图最小化 I/O 次数。它将内存缓冲区划分为两半，并将数据分成多个逻辑块。
**基于单元格的算法** - 为了避免 O(n²) 的计算复杂度，开发了一种用于内存驻留数据集的基于单元格的算法。其复杂度为 O(ck + n)，其中 c 是基于单元格数量的常数，k 是维数。
在这种方法中，数据空间被划分为边长类似于 $\frac{d}{\sqrt[2]{k}}$ 的单元格。每个单元格都有两层围绕着它。
第一层厚一个单元格，第二层厚 $\sqrt[2]{k}$ 个单元格（四舍五入到最接近的整数）。该算法按单元格而非按对象逐个计算离群值。对于给定的单元格，它累积三个计数，包括单元格中的对象数量、单元格和第一层中的对象数量以及单元格和两层中的对象数量。
2K+ 次浏览
