java - ELKI 和 RapidMiner 中 LOF 实现的不同结果

Question

我已经编写了自己的 LOF 实现，我正在尝试将结果与 ELKI 和 RapidMiner 中的实现进行比较，但所有 3 个都给出不同的结果!我正在尝试找出原因。

我的引用数据集是一维的，有 102 个真实值，有很多重复值。我会尝试在下面发布它。

首先，RapidMiner 的实现。 LOF 分数与 ELKI 和我的结果大不相同；许多人带着无穷大的 LOF 回来。此实现是否已被验证为正确？

我的结果与 ELKI 相似，但我没有得到完全相同的 LOF 值。快速浏览 ELKI 源代码中的注释，我认为这可能是因为计算 k 邻域的方式不同。

在 LOF 论文中，MinPts 参数(别处称为 k)指定最小值。要包含在 k 邻域中的点数。在 ELKI 实现中，我认为他们将 k 邻域定义为恰好 k 个点，而不是 k 距离或 k 不同距离内的所有点。任何人都可以确切地确认 ELKI 是如何构建 k 邻域的吗？还有一个私有(private)变量允许将点本身包含在它自己的邻域中，但看起来默认情况下不包含它。

有谁知道附有用于验证目的的 LOF 分数的公共(public)引用数据集？

---更多细节如下---

引用:ELKI源码在这里:

http://elki.dbs.ifi.lmu.de/browser/elki/trunk/src/de/lmu/ifi/dbs/elki/algorithm/outlier/lof/LOF.java

RapidMiner 源代码在这里:

http://code.google.com/p/rapidminer-anomalydetection/source/browse/trunk/src/de/dfki/madm/anomalydetection/evaluator/nearest_neighbor_based/LOFEvaluator.java

这是我的测试数据集:

4.323235.12595 5.12595 5.12595 5.12595 5.7457 5.7457 5.74575.7457 5.7457 5.7457 5.97766 5.977666.07352 6.07352 6.12015 6.12015 6.12015 6.44797 6.447976.48131 6.48131 6.48131 6.48131 6.48131 6.48131 6.63336.6333 6.6333 6.70872 6.70872 6.70872 6.70872 6.708726.77579 6.77579 6.77579 6.77579 6.77579 6.77579 6.775796.77579 6.77579 6.77579 6.77579 6.77579 6.77579 6.775796.775797.03654 7.03654 7.03654 7.03654 7.03654 7.03654 7.036547.03654 7.03654 7.03654 7.03654 7.03654 7.03654 7.036547.03654 7.10361 7.10361 7.10361 7.10361 7.10361 7.103617.10361 7.10361 7.15651 7.15651 7.15651 7.15651 7.156517.15651 7.15651 7.156518.22598 8.22598 8.22598 8.22598 8.5538 8.5538 8.55388.5538 8.5538 8.5538 8.5538 8.5538 8.5538 8.5538 8.55388.5538 8.5538 8.5538 8.5538 8.5538 8.5538 8.5538

例如，我得到以下第一个数字 (4.32323) 的 LOF 分数:

• RapidMiner:无穷大(MinPts 下限/上限设置为 10,100)
• ELKI:2.6774(k = 10 且 distfunction/reachdistfunction 设置为默认值)
• 我的实现:1.9531

关于我的实现正在做什么的更多细节:

1. MinPts 是 10，所以我要找到该点的 10 个不同的邻居。所以 4.32323 的邻域实际上是 48 个点，从 5.12595 到 6.77579。
2. 这给了我 2.45256 的 k-distinct 距离
3. 我正在计算第一个邻居的可达距离为 1.58277
4. 我将样本的 LRD 计算为 1/(99.9103/48)
5. 所有 48 个邻居的 lrd(o)/lrd(p) 之和为 93.748939
6. 除以 48 得到 1.9531 的 LOF

Answer 1

其实我并不惊讶他们的不同。您还可以添加 Weka 的 LOF 实现，您可能会得到另一个答案。

这是您要添加到方程式中的另一个区别:据我所知，rapidminer 实现合并具有相同坐标的点。但也许，他们在计算最近邻时忘记考虑这些权重!

在经典数据库上下文中，您不会将重复的坐标合并到单个观测值中。它们仍然是有效的数据库记录，应算作完整记录。

我不知道他们中是否有人执行一些自动数据预处理，例如重新缩放数据集。

ELKI 实现已根据我们用于教学的大量教科书示例进行了验证。

但是，算法中存在并非 100% 固定的极端情况，因此即使在算法的“文字”实现中也存在差异空间。您已经遇到了其中三个:

1. 如何处理重复点:A)聚合，B)丢弃，C)考虑不同

   从数据挖掘的角度来看，C 是正确的，而 A(如果实现正确)是一种优化，可以为您节省不必要的距离计算。 B 是常见的数学 View ，但对于数据库上下文没有多大意义。如果我有两个“李四”，他们是同一个人吗？

2. k 最近邻和 k 距离的定义。

   k距离的通常定义是:最小距离，使得至少包含k个观测值。当排除查询点时，这会产生从起点到 5.7457 的间隔:在 5.7457 - 4.32323 的半径范围内还有 10 个其他观测值。

   k个最近邻通常定义为这个距离内的任意一个点，这个距离可能大于k。但是所有其他对象必须具有与第 k 个对象相同的距离!rapidminer 似乎使用了 exactly k，这与 LOF 出版物不一致(参见 LOF 出版物中的定义 4!)

   它实际上是 k 个最近的邻居(包括关系，但除此之外不超过 k 个对象)，不是第 k 个最小的distinct 距离。你从哪里得到“不同的”？

   LOF 出版物中的定义 3 和 4 非常清楚地说明了 LOF 使用的 kNN 集。

   因此，您的 48 个对象的邻域是不正确的。

3. 如果有超过 minPts 个重复点该怎么办(文字实现将产生除以零，但出于显而易见的原因，应该为该点赋予 1.0 的 LOF)

   这可能就是 Rapidminer 正在发生的事情。

然后是可达距离:这个真的很棘手，因为它不是数学距离。它是不对称的。

第一个观察的可达性 来自 第二个恰好是第二个的 k 距离，从快速看(没有仔细检查)reach-dist(x[ 0], x[1]) = max(5.97766 - 5.12595, 5.12595 - 4.32323) = 0.80272

参见 my extensive tutorial slides on outlier detection有关如何计算 LOF 的分步演示。据我所知，这是字面上的 LOF。它没有触及所有极端情况，但它激发了 LOF 算法的设计并且非常详尽。