Python实现OPTICS（聚类）算法

Question

我在找一个不错的Python实现的OPTICS算法。我要用它来形成基于密度的点的聚类，也就是一组一组的(x,y)坐标。

我希望这个实现能够接收(x,y)坐标对，然后输出一个聚类的列表，每个聚类里面包含属于这个聚类的(x,y)坐标对的列表。

Answer 1

虽然严格来说这不是OPTICS，但在Python中有一个HDBSCAN*的实现，可以在这个链接找到：https://github.com/lmcinnes/hdbscan。这个实现相当于OPTICS，只不过它的最大epsilon值是无限的，而且提取聚类的方法也不同。因为这个实现可以访问生成的聚类层次结构，所以如果你愿意，也可以通过更传统的OPTICS方法从中提取聚类。

需要注意的是，尽管这个实现没有限制epsilon参数，但它仍然能以O(n log(n))的性能运行，使用的是基于kd-tree和ball-tree的最小生成树算法，并且可以处理相当大的数据集。

Answer 2

我不知道有没有一个完整且准确的Python版本的OPTICS。这里分享的链接似乎只是对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的代码。

在ELKI中，似乎有一个相当全面的Java实现，是最初发布OPTICS的团队提供的。你可能想把其他实现和这个“官方”版本进行对比测试。

Answer 3

编辑：以下内容已知并不是OPTICS算法的完整实现。

我做了个快速搜索，找到了这个链接（Optics）。我不能保证它的质量，不过这个算法看起来相对简单，所以你应该能很快验证或调整它。

下面是一个如何在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)