32

我正在寻找Python中OPTICS算法的体面实现。我将使用它来形成基于密度的点簇（（x，y）对）。

我正在寻找可以接收 (x,y) 对并输出集群列表的东西，其中列表中的每个集群都包含属于该集群的 (x, y) 对列表。

4

7 回答 7

10

我不知道 OPTICS 的完整和精确的 python 实现。此处发布的链接似乎只是 OPTICS 想法的粗略近似。它们也不使用索引来加速，因此它们会运行O(n^2)甚至更有可能运行O(n^3)。

除了显而易见的想法之外，OPTICS 还有许多棘手的事情。特别是，建议使用相对阈值（“xi”）而不是此处发布的绝对阈值来完成阈值处理（此时结果将近似于 DBSCAN！）。

最初的 OPTICS 论文包含将算法的输出转换为实际集群的建议方法：

http://www.dbs.informatik.uni-muenchen.de/Publikationen/Papers/OPTICS.pdf

Weka 中的 OPTICS 实现基本上没有维护，同样不完整。它实际上并不产生集群，它只计算集群顺序。为此，它复制了数据库——它不是真正的 Weka 代码。

最初发布 OPTICS 的小组似乎在 Java 中的ELKI中提供了相当广泛的实现。您可能希望针对此“官方”版本测试任何其他实现。

于 2012-02-08T17:49:49.080 回答
8

编辑：已知以下不是OPTICS 的完整实现。

我进行了快速搜索，发现以下（光学）。我不能保证它的质量，但是算法看起来很简单，所以你应该能够快速验证/调整它。

以下是如何在光学算法的输出上构建集群的快速示例：

def cluster(order, distance, points, threshold):
    ''' Given the output of the options algorithm,
    compute the clusters:

    @param order The order of the points
    @param distance The relative distances of the points
    @param points The actual points
    @param threshold The threshold value to cluster on
    @returns A list of cluster groups
    '''
    clusters = [[]]
    points   = sorted(zip(order, distance, points))
    splits   = ((v > threshold, p) for i,v,p in points)
    for iscluster, point in splits: 
        if iscluster: clusters[-1].append(point)
        elif len(clusters[-1]) > 0: clusters.append([])
    return clusters

    rd, cd, order = optics(points, 4)
    print cluster(order, rd, points, 38.0)
于 2011-04-28T17:08:01.557 回答
6

虽然从技术上讲不是 OPTICS，但在https://github.com/lmcinnes/hdbscan上提供了适用于 python 的 HDBSCAN* 实现。这等效于具有无限最大 epsilon 的 OPTICS，以及不同的聚类提取方法。由于该实现提供了对生成的集群层次结构的访问，如果您愿意，您也可以通过更传统的 OPTICS 方法从中提取集群。

请注意，尽管不限制 epsilon 参数，但此实现仍然使用基于 kd-tree 和 ball-tree 的最小生成树算法实现 O(n log(n)) 性能，并且可以处理相当大的数据集。

于 2016-04-15T16:47:18.237 回答
6

现在存在pyclustering库，其中包含 Python 和 OPTICS 的 C++ 实现等。

于 2018-06-11T08:19:37.947 回答
4

它现在在 sklearn（python 的集群和机器学习模块）的开发版本（scikit-learn v0.21.dev0）中实现

这是链接： https ://scikit-learn.org/dev/modules/generated/sklearn.cluster.OPTICS.html

于 2019-03-13T18:06:41.720 回答
1

请参阅http://www.chemometria.us.edu.pl/index.php?goto=downloads上的“基于密度的聚类方法”

于 2011-04-01T16:04:55.187 回答
1

您想查看空间填充曲线或空间索引。sfc 将 2d 复杂度降低到 1d 复杂度。你想看看尼克的希尔伯特曲线四叉树空间索引博客。您想在 phpclasses.org (hilbert-curve) 下载我的 sfc 实现。

于 2011-04-23T21:27:39.183 回答