检测二维空间异常值的快速方法

Question

我有数亿的点云，如下所示：

我想删除异常值1,2,4,5,6,7。最安全的选择是建立一个连接所有点的最小生成树并删除长度$>2\sigma$的边（2可以调整），但 MST 的实施需要四倍时间且操作复杂。我尝试删除到质心距离 $>2\sigma$ 的点，但它无法识别 2、4，并且错误地删除了 3 尖端的一些点。到所有其他点的距离总和方法有类似的问题。通过 PCA 进行正交化也没有多大帮助。在致力于 MST 之前，是否有任何既定的、快速的方法来解决此类问题，尤其是在 2D 空间中？这个问题在地理空间领域似乎很常见。我想知道是否可以使用一些内核技巧将点投影到 1D 或 3D 空间中，以便可以轻松分离异常值？

Answer 1

使用 MST 检测异常值听起来很酷，但正如您提到的，它可能会很慢，时间复杂度至少是二次方。您还可以探索其他一些替代方案：例如，隔离森林通过使用随机二叉树隔离数据点来识别异常，异常由于其稀有性和不同的模式而更容易被隔离。使用线性/对数线性实现相对较快。

DBSCAN 是另一种选择：它的工作原理是将紧密堆积在一起的点分组，并将低密度区域中的点标记为异常值。这也是一个相对更快的选择，具有对数线性时间复杂度。