二维空间中的无监督异常值检测

机器算法验证 聚类 异常值 爪哇
2022-04-16 11:24:07

问题

我正在使用Java进行一个学校项目,我的目标是从包含地理点的数据集中检测和删除异常值。

最终结果应该是单个集群,具有任何形状,包含真实区域内的所有点(例如体育场)。这是我的意思的一个简单示例:

在此处输入图像描述

手绘的蓝线代表预期的集群,而所有外部点都应被视为异常值(这只是我的情况可以接受的可能集群之一,不检测顶部也可以)。

我试过的

虽然DBSCAN看起来是最好的选择,但我需要它是无监督的,所以我不能手动设置epsminPts(该算法应该在多个数据集上运行)。可行的是一个函数,它根据数据集的大小和区域的大小(可能以米为单位,使用基于地理的距离函数)同时定义epsminPts ,但定义这样的函数对于一个小的项目。

为了避免处理eps,我决定尝试OPTICS,但它仍然需要minPts,并且在我使用 ELKI 的测试中,它返回一个包含所有点的单个集群。

最后,由于 ELKI 有很多内置算法,我也尝试了 LibSVMOneClassOutlierDetection因为它应该是二进制分类的最佳选择(这基本上是我的任务,类可以被视为集群的“内部”和“外部”),但它检测到几乎任何点都是异常值(即使它们有分数,并且所有需要的点的分数 < 0.1,所以我可能稍后会做一些后处理步骤)。

问题

所以,这里有几个问题:

  1. 是否有无监督(可能是无参数)算法可用于解决此任务?
  2. 如果是,是否有任何实施准备就绪?
  3. 奖励 - 你能推荐一个已经内置在 ELKI(甚至是 Weka)中的算法吗?如果它在 ELKI 中,如果自动评估器不够好,您能否建议评估器的评估功能?

编辑:根据我尝试过 OPTICSXi 的建议minPts = 50,结果如下。

在此处输入图像描述

如您所见,有两个问题:

  1. 红色集群是正确的候选者,它包含远离中心的点,但我想我可以稍后处理它们
  2. 红色的内部还有其他集群,虽然它们应该是其中的一部分

编辑 2:使用带有自动 eps 估计的 DBSCAN 进行了一些其他测试,我比 OPTICS 更喜欢结果,但现在的问题是:如何提取紫色簇并删除所有其他簇?我似乎找不到任何方法来评估基于密度的 DBSCAN 集群。

在此处输入图像描述

2个回答

您的任务似乎是一个聚类而不是异常值检测任务。

在下文中,我使用了这个流行的用户位置数据集 (Joensuu)

使用参数运行 OPTICS

-dbc.in /tmp/MopsiLocations2012-Joensuu.txt
-algorithm clustering.optics.OPTICSXi -opticsxi.xi 0.05
-algorithm.distancefunction geo.LngLatDistanceFunction
-optics.epsilon 5000.0 -optics.minpts 50

产生以下(分层)聚类。您可以看到有三个较大的集群(对应于JoensuuLieska和 Savijärvi;请注意,图中的纬度和经度是“错误的方式”),以及一些在 5 公里距离内无法达到密度的噪声(此处为紫色),并且50 分。这些是你的异常值。

你可以看出这两个城市都有一些子集群。例如与 Prisma Joensuu 购物中心相对应的一个。要查看更多细节,进一步减少 epsilon 很有帮助,可能只有 500 米。

在此处输入图像描述

要回答这个老问题的编辑 2——一种方法是计算每个点到集群中心的马氏距离,然后删除高于某个截止距离的那些。