Python实现的OPTICS(聚类)算法

Question

我正在寻找在Python 中使用OPTICS算法的一个不错的实现.我将用它来形成基于密度的点((x,y)对).

我正在寻找接收(x,y)对并输出簇列表的东西,其中列表中的每个簇包含属于该簇的(x,y)对的列表.

Answer 1

我不知道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中有相当广泛的实现.您可能希望针对此"官方"版本测试任何其他实现.

Answer 2

编辑:已知以下不是 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)

Answer 3

虽然在技术上不是OPTICS,但可以在https://github.com/lmcinnes/hdbscan上找到用于python的HDBSCAN*实现.这相当于具有无限最大epsilon的OPTICS和不同的簇提取方法.由于实现提供了对生成的集群层次结构的访问,因此如果您愿意,也可以通过更传统的OPTICS方法从中提取集群.

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

Answer 4

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