Python实现OPTICS（集群）算法

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

我正在寻找采用（x，y）对的东西，并输出一个簇列表，其中列表中的每个簇都包含属于该簇的（x，y）对列表。

来源

2011-04-01 Murat Derya Özen

你看过SciPy：http://docs.scipy.org/doc/scipy/reference/cluster.html？ – vartec 2011-04-01 15:53:36

@vartec - 是的，我做到了。实际上，我正在使用那里提供的分层聚类方法（fcluster）。但现在，我想切换到OPTICS。 – 2011-04-01 15:59:23

OPTICS是一个不熟悉/未知的算法，我的问题没有被关注？ =（ – 2011-04-24 17:09:57

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

来源

2011-04-28 17:08:01 Bashwork

感谢Bashwork，但它看起来与vartec建议的代码完全相同。问题在于，我无法弄清楚如何从该算法的输出中提取聚类结构（哪些元素属于哪个聚类）。请在我的问题最底部看看'Note'。 – 2011-04-28 22:41:11

因此，代码为您提供了您需要提取集群的输出（顺序和可达性距离）。如果您查看维基百科部分以提取集群，您只需在有序结果中使用距离阈值（较低的阈值意味着更多的集群）。（http://en.wikipedia.org/wiki/OPTICS_algorithm）。如果这没有意义，我可以给一些示例代码。 – Bashwork 2011-04-29 17:50:07

我刚刚运行了您发布的代码，得到的阈值为38的结果为[[31.0，87.0]，[73.0，9.0]] [[5.0，8.0]] [[97.0，9.0]]（ 3个群集）。我将阈值降低到10，并且只有1个簇。我使用的测试数据与您给出的链接（testX）中使用的测试数据相同。如果您能更正代码，我将不胜感激，我会奖励您的赏金。 – 2011-04-29 22:39:37

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

来源

2011-04-01 16:04:55 vartec

谢谢对于vartec的回答，但实现对我来说似乎不完整。我正在寻找采用（x，y）对的东西，并输出一个集群列表，其中列表中的每个集群都包含属于该集群的（x，y）对列表。 – 2011-04-23 21:01:00

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

来源

2011-04-23 21:27:39 Bytemain

感谢墓志铭，但这到底是如何回答我的问题？你能澄清你的答案吗？ – 2011-04-23 21:55:29

一个sfc是一个使用分形的聚类算法。希尔伯特曲线的分形维数为2.如果您有2d数据，则可以轻松地将此数据细分为更小的图块。基本上这是一个重新排序。这就像将它们存储在四叉树中一样。你也可以使用一个自适应sfc，在其中跳过emtpy区域或者具有较低的sfc粒度。 Sfc通常用于地图，如谷歌地图。 – Bytemain 2011-04-23 22:02:36

听起来不错，值得一试。谢谢。但我仍然在寻找Python中的OPTICS实现。 – 2011-04-23 23:32:36

我不知道一个完整和详细的Python实现光学的。这里发布的链接似乎只是OPTICS想法的粗略近似。他们也没有使用加速指数，因此他们将运行在O(n^2)或更可能甚至O(n^3)。

除了明显的想法之外，OPTICS还有许多棘手的事情。具体而言，阈值建议用相对于阈值（“xi”）来完成，而不是像这里所发布的绝对阈值（此时结果将近似于DBSCAN！）。

原来的光学本文包含建议的方法对算法的输出转换成实际的集群：

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

在Weka的光学系统实现基本上是无人维护，只是不完整的。它实际上并不生成集群，它只计算集群顺序。为此，它会复制数据库 - 它不是真正的Weka代码。

在首次发布OPTICS的组中，似乎在Java的ELKI中有相当广泛的实现。您可能想要针对此“官方”版本测试任何其他实施。

来源

2012-02-08 17:49:49

的确，有很多不完整的OPTICS实现和Weka版本的克隆。您应该参考ELKI版本。 – 2013-01-01 11:35:56

我认为相对阈值是指一个相对清晰的论述和方法转变为更加多云的情况，并带有更多的启发式和隐藏参数。这可能没有办法解决，但我肯定觉得中间有序的可达性值是一个很好的结果。后来发生的事情可以采用不同的方法，本文选择的方法不是那么不言自明，而是唯一值得考虑的方法。 – micans 2013-01-08 15:32:47

至少有两种方法提出了如何从图确定聚类。然而，没有这种聚类提取方法，它实际上是一种聚类算法吗？在某些时候，你确实希望从中获得集群，而不仅仅是一个情节。 – 2013-01-08 17:13:29

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

请注意，尽管不限制epsilon参数，但此实现仍使用kd-tree和基于球树的最小生成树算法（and can handle quite large datasets）实现O（n log（n））性能。

来源

2016-04-15 16:47:18

Python实现OPTICS（集群）算法

回答

相关问题