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

Question

我编写了自己的LOF实现,并且我试图将结果与ELKI和RapidMiner中的实现进行比较,但所有3都给出了不同的结果!我想弄清楚为什么.

我的参考数据集是一维的,102个实数值,有许多重复.我会尝试在下面发布.

首先,RapidMiner实现.LOF分数与ELKI和我的结果大不相同; 许多人带着无穷大的LOF回来.此实施是否已经过验证是正确的？

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

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

有没有人知道一个公共参考数据集,其中附有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. 这给了我一个k-distinct距离2.45256
3. 我正在计算第一个邻居的可达性距离为1.58277
4. 我正在计算样本的LRD为1 /(99.9103/48)
5. 所有48个邻居的lrd(o)/ lrd(p)之和为93.748939
6. 除以48得到LOF为1.9531

Answer 1

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

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

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

我不知道他们中是否有人执行某些自动数据预处理,例如重新调整数据集.

ELKI实施已经过我们用于教学的一些教科书示例的验证.

然而,算法中存在不是100%固定的极端情况,因此即使在算法的"文字"实现中也存在差异的空间.你已经遇到了其中三个:

1. 如何处理重复点:A)聚合,B)下降,C)考虑不同

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

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

   k距离的通常定义是:最小距离,使得至少包含k个观测值.当排除查询点时,从起点得到的最大值为5.7457:半径为5.7457的其他10个观测值 - 4.32323.

   k个最近邻居通常被定义为该距离内的任何点,其可以大于k.但是所有其他对象必须与第k个具有相同的距离!似乎快速计时器使用的是k,它与LOF出版物不一致(参见LOF出版物中的定义4!)

   它实际上是k个最近的邻居(包括领带,但不包括不超过k个对象),而不是k个最小的不同距离.你从哪里得到"独特的"？

   LOF出版物中的定义3和4在kNN集LOF使用中非常清楚.

   因此,您的48个物体附近是不正确的.

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

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

然后有可达距离:这个非常棘手,因为它不是数学距离.它是不对称的.

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

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