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

Background

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

Content

将数据空间划分为$l$维网络，网络单元格对角线长度为$\frac r2$,边长为$\frac{r}{2\sqrt l}$;

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

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

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

• $\forall x\in c,y\in C_1$,必有$dis(x,y)\le r$;
• $\forall x\in c, dis(x,y)\ge r$,必有$y\in C_2$

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

• $|c|+|C_1|>\left \lceil \pi N \right \rceil$,说明$c$内对象均不离群的；
• $|c|+|C_1|+|C_2|<\left \lceil \pi N \right \rceil+1$,说明$c$内对象均离群的；

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

算法如何降低空间开销？

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

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