3

我正在尝试对一些地理空间数据进行聚类，我之前尝试过WEKA库。我找到了这个基准，并决定尝试ELKI。

尽管有人建议不要将 ELKI 用作 Java 库（假设它的维护比 UI 少），但我还是将它合并到了我的应用程序中，我可以说我对结果感到非常满意。它用于存储数据的结构比 Weka 使用的结构要高效得多，而且它可以选择使用空间索引这一事实无疑是一个加分项。

但是，当我将Weka 的 DBSCAN的结果与ELKI 的 DBSCAN的结果进行比较时，我有点困惑。我会接受不同的实现可以产生稍微不同的结果，但是这些差异让我认为算法有问题（可能是我的代码）。两种算法中簇的数量及其几何形状非常不同。

作为记录，我使用的是最新版本的 ELKI (0.6.0)，我用于模拟的参数是：

minpts=50 ε=0.008

我编写了两个 DBSCAN 函数（用于 Weka 和 ELKI），其中“入口点”是带有点的 csv，它们的“输出”也是相同的：一个计算一组点的凹壳的函数（每个集群一个）。由于将 csv 文件读入 ELKI“数据库”的功能相对简单，我认为我的问题可能是：

a) 在算法的参数化中；b) 阅读结果（很可能）。

参数化 DBSCAN 不会带来任何挑战，我使用了我之前通过 UI 测试过的两个强制参数：

ListParameterization params2 = new ListParameterization();
params2.addParameter(de.lmu.ifi.dbs.elki.algorithm.clustering.DBSCAN.Parameterizer.MINPTS_ID,        minPoints);
params2.addParameter(de.lmu.ifi.dbs.elki.algorithm.clustering.DBSCAN.Parameterizer.EPSILON_ID, epsilon);

阅读结果更具挑战性，因为我不完全了解存储集群的结构的组织；我的想法是遍历每个集群，获取点列表，并将其传递给计算凹壳的函数，以生成多边形。

    ArrayList<Clustering<?>> cs = ResultUtil.filterResults(result, Clustering.class);
    for (Clustering<?> c : cs) {
        System.out.println("clusters: " + c.getAllClusters().size());
      for (de.lmu.ifi.dbs.elki.data.Cluster<?> cluster : c.getAllClusters()) {
              if (!cluster.isNoise()){
                 Coordinate[] ptList=new Coordinate[cluster.size()];
                 int ct=0;
                    for (DBIDIter iter = cluster.getIDs().iter(); iter.valid(); iter.advance()) {
                        ptList[ct]=dataMap.get(DBIDUtil.toString(iter));
                        ++ct;
                    }                   
                //there are no "empty" clusters
                assertTrue(ptList.length>0);

                GeoPolygon poly=getBoundaryFromCoordinates(ptList);
                if (poly.getCoordinates().getGeometryType()==
                        "Polygon"){

                    try {
                        out.write(poly.coordinates.toText()+"\n");
                    } catch (IOException e) {
                        // TODO Auto-generated catch block
                        e.printStackTrace();
                    }           

                }else
                    System.out.println(
                            poly.getCoordinates().getGeometryType());

              }//!noise
      }
    }

我注意到“噪音”是作为一个集群出现的，所以我忽略了这个集群（我不想画它）。我不确定这是否是阅读集群的正确方法，因为我找不到很多例子。我也有一些问题，我还没有找到答案：

  • getAllClusters() 和 getTopLevelClusters() 有什么区别？
  • DBSCAN 集群是否“嵌套”，即：我们可以同时拥有属于多个集群的点吗？为什么？
  • 我在某处读到我们不应该使用数据库 ID 来识别点，因为它们是供 ELKI 内部使用的，但是还有什么其他方法可以获取每个集群中的点列表？我读到您可以对标签使用关系，但我不确定如何实际实现它......

任何可以为我指明正确方向的评论，或任何迭代 ELKI DBSCAN 结果集的代码建议都将受到欢迎！我还在我的代码中使用了 ELKI 的 OPTICSxi，我对这些结果还有更多疑问，但我想我会将其保存到另一篇文章中。

4

2 回答 2

3

这主要是对@Anony-Mousse 的跟进，他给出了一个非常完整的答案。

  • getTopLevelClusters()并getAllClusters()为 DBSCAN 做同样的事情，因为 DBSCAN 不产生分层集群。
  • DBSCAN 集群是不相交的。将集群isNoise()==true视为单例对象可能是处理噪声的最佳方法。我们的实现返回的集群OPTICSXi也是不相交的，但您应该将所有子集群的成员视为外部集群的一部分。对于凸包，一种有效的方法是首先计算子簇的凸包；然后为父计算附加对象上的凸包 + 所有子对象的凸包点。
  • RangeDBIDs@Anony-Mousse 提到的方法对于静态数据库来说非常干净。一种也适用于动态数据库的干净方法是拥有一个标识对象的附加关系。当使用 CSV 文件作为输入时，您只需添加一个包含标签的非数字列，而不是依赖行编号来保持一致，例如object123. 从逻辑的角度来看，这是最好的方法 - 如果您希望能够识别对象，请给它们一个唯一标识符。;-)
  • 我们使用 ELKI 进行教学，我们已经非常非常仔细地验证了它的 DBSCAN 算法（您可以在这里找到一个 DBSCAN 逐步演示，ELKI 结果与此完全匹配）。Weka 中的 DBSCAN 和 OPTICS 代码是很久以前由一位学生贡献的，并且从未进行过相同程度的验证。通过快速检查，Weka在我们的课堂练习数据集上没有产生正确的结果。
  • 因为练习数据集每个维度都是10的extend，所以我们可以将epsilon参数调整1/10，然后Weka结果似乎和解相匹配；所以@Anony-Mousses 的发现似乎是正确的：Weka 的实现对数据强制执行 [0;1] 缩放。
于 2014-05-14T09:36:22.817 回答
2

DBIDs如果您注意它们的分配方式，则访问ELKI 是有效的。

对于静态数据库，getDBIDs()将返回一个RangeDBIDs对象，它可以给你一个进入数据库的偏移量。这是非常可靠的。但是如果你总是重新启动你的进程，DBIDs无论如何都会被确定性地分配（只有在使用 MiniGUI 时，如果你重新运行一个作业，它们会有所不同！）

这也将比DBIDUtil.toString.

DBSCAN 结果不是分层的，因此每个集群都应该是顶级集群。

至于 Weka，它有时会进行自动归一化。那么 epsilon 值将被扭曲。对于地理数据，无论如何我更喜欢大地距离，经纬度上的欧几里得距离没有意义。

检查这部分 Wekas 代码：“norm”函数，由 EuclideanDataObject 使用。在我看来，这看起来好像 Wekas DBSCAN 对数据集执行了规范化！尝试将您的数据缩放到 [0:1]（我很确定 ELKI 中有一个过滤器），如果之后结果相同？

从这段代码片段来看，我会责怪 Weka。上面的代码在我看来也有点低效。过滤器方法使恕我直言，比在数据对象中强制过滤更有意义。

于 2014-05-13T18:50:21.190 回答