什么是基于距离的异常值？
数据集S中的对象o是具有参数p和d的基于距离(DB)的异常值，即DB(p,d)，如果S中对象的最小分数p位于距哦。换句话说，它可以将基于距离的异常值视为没有足够邻居的对象，而不是依赖于统计测试。
邻居根据与给定对象的距离表示。与基于统计的方法相比，基于距离的异常值检测概括或合并了标准分布不一致性测试背后的思想。因此，基于距离的异常值也称为统一异常值或UO异常值。
基于距离的异常值检测可防止与将观察到的分布拟合到某个标准分布和选择不一致测试相关的过度计算。对于某些不一致测试，可以显示如果对象o根据给定的测试是异常值，那么对于某些正确表示的p和d，o也是DB(p,d)异常值。
例如，如果与平均值相差3个或更多标准差的对象被视为异常值，考虑到正态分布，那么这种表示可以由DB(0.9988,0.13s)-异常值“统一”。已经创建了几种用于挖掘基于距离的异常值的有效算法，如下所示-
基于索引的算法-给定一个数据集，基于索引的算法有助于多维索引结构，包括R树或kd树，以搜索每个对象o在该对象周围半径d内的邻居。令M为异常值的d邻域内的最大对象数。因此，一旦发现对象o的M+1个邻居，就可以确定o不是异常值。该算法具有最低的情况复杂度O(k*n2)，其中k是维度，n是数据集中的对象数量。
嵌套循环算法-嵌套循环算法与基于索引的算法具有相同的评估复杂性，但避免索引结构构建并尝试最小化I/O的数量。它将内存缓冲区分为两半，将数据设置为几个逻辑块。
基于单元的算法-它可以避免O(n2)计算复杂度，为内存驻留数据集开发了基于单元的算法。它的复杂度是O(ek+n)，其中c是基于单元格数量的常数，k是维数。
在这种方法中，数据空间被划分为边长类似于$\frac{d}{\sqrt[2]{k}}$的单元格。每个单元格周围有两层。
第一层是一个单元格厚，而第二层是$\sqrt[2]{k}$单元格厚，四舍五入到最接近的整数。该算法逐个单元而不是逐个对象地计算异常值。对于给定的单元格，它会累积三个计数，包括单元格中、单元格和第一层中的对象数以及单元格中和两层中的对象数。