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（集羣）算法

回答

相關問題