5

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

我的参考数据集是一维的，有 102 个实数值，有很多重复。我会试着把它贴在下面。

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

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

在 LOF 论文中，MinPts 参数（在其他地方称为 k）指定了最小编号。包含在 k 邻域中的点数。在 ELKI 实现中，我认为他们将 k 邻域定义为精确的 k 点，而不是 k 距离或 k 不同距离内的所有点。谁能确切地确认 ELKI 是如何构建 k 邻域的？还有一个私有变量允许点本身包含在它自己的邻居中，但看起来默认不包含它。

有谁知道带有用于验证目的的 LOF 分数的公共参考数据集？

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

参考：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.32323 5.12595 5.12595 5.12595 5.12595 5.7457 5.7457 5.7457 5.7457 5.7457 5.7457 5.97766 5.97766 6.07352 6.07352 6.12015 6.12015 6.12015 6.44797 6.44797 6.48131 6.48131 6.48131 6.48131 6.48131 6.48131 6.6333 6.6333 6.6333 6.70872 6.70872 6.70872 6.70872 6.70872 6.77579 6.77579 6.77579 6.77579 6.77579 6.77579 6.77579 6.77579 6.77579 6.77579 6.77579 6.77579 6.77579 6.77579 6.77579 7.03654 7.03654 7.03654 7.03654 7.03654 7.03654 7.03654 7.03654 7.03654 7.03654 7.03654 7.03654 7.03654 7.03654 7.03654 7.10361 7.10361 7.10361 7.10361 7.10361 7.10361 7.10361 7.10361 7.15651 7.15651 7.15651 7.15651 7.15651 7.15651 7.15651 7.15651 8.22598 8.22598 8.22598 8.22598 8.5538 8.5538 8.5538 8.5538 8.5538 8.5538 8.5538 8.5538 8.5538 8.5538 8.5538 8.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
4

2 回答 2

6

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

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

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

我不知道他们中的任何一个是否执行一些自动数据预处理，例如重新调整数据集。

ELKI 实现已针对我们用于教学的许多教科书示例进行了验证。

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

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

    从数据挖掘的角度来看，C 是正确的，而 A（如果正确实施）是一种优化，可以节省不必要的距离计算。B 是常见的数学视图，但对数据库上下文没有多大意义。如果我有两个“John Doe”，他们是同一个人吗？

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

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

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

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

    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

有关如何计算 LOF 的逐步演示，请参阅我关于异常值检测的大量教程幻灯片。据我所知，这是字面的 LOF。它并没有触及所有的极端情况，但它激发了 LOF 算法的设计，并且非常详尽。

于 2013-02-20T19:51:58.743 回答
0

If you are using the Anomaly Detection Extension for RapidMiner[1] (not the build-in LOF), you will get the correct results. The build-in LOF is broken. These are the same results as ELKI. This implementation is much faster than ELKI because its multi-threated and does use much less memory, too. It also can handle duplicates (even more that k+1), where ELKI throws exceptions. (based on k-distinct)

Best, Hans

[1] http://marketplace.rapid-i.com/UpdateServer/faces/product_details.xhtml?productId=rmx_anomalydetection

于 2013-04-26T14:27:10.830 回答