离群点检测：cell-based挖掘DB(r,p)离群点

Background

循环嵌套发现离群点在离群点数目较少时，表现出线性的性能，因为循环经常提前退出，尽管它的算法复杂度为。当数据集很大时，开销主要来源是不能将数据集放入主存，而对检查每个对象都需要潜在地遍历整个数据集

Content

将数据空间划分为维网络，网络单元格对角线长度为,边长为;

对于单元格，其余单元可以分为两类：

• 层：直接与连接的单元；
• 层：任意方向远离1格/2格的单元；

有两条几何上的先验性质(凸包)：

• ,必有;
• ,必有

那么有两条相应的启发式剪枝规则：

• ,说明内对象均不离群的；
• ,说明内对象均离群的；

大部分点经过两个规则的判断都可以确定是否是离群点了；

算法如何降低空间开销？

答案是三次数据集的扫描；

• 第一次扫描：忽略掉空间内没有对象的单元格；
• 第二次扫描：排除掉已经可以剪枝确认是否离群的点；
• 第三次扫描：检查剩下的单元，找到所有离群点，