我有一組2D座標集（在每組中有100K-500K點的比例），我正在尋找測量1組相似度的最有效方法到另一個。我知道常用的東西：餘弦，Jaccard/Tanimoto等。但是我希望對任何快速/有效的測量相似性的建議，尤其是那些可以通過相似性進行聚類的測量。適用於多組2D座標的適當相似性度量
編輯1：圖像顯示我需要做什麼。我需要它們的形狀/ orientatoin到羣集中的所有紅色，藍色和綠色等
alt text http://img402.imageshack.us/img402/8121/curves.png
似乎任何解決方案的第一步都是找到每個形狀的質心或其他參考點，以便它們可以進行比較而不管絕對位置如何。
想到的一種算法是從最接近質心的點開始，然後步行到最近的鄰居。比較所比較的集合之間的那些鄰居（來自質心）的偏移量。繼續步行到質心的下一個最近的鄰居，或者先前比較過的最近未被比較的鄰居，並跟蹤這兩個形狀之間的總體差異（可能是RMS？）。此外，在這個過程的每一步計算旋轉偏移，這將使兩個形狀最接近對齊[以及鏡像是否也影響它？]。當你完成後，你將有三組值，包括它們的直接相似度，它們的相對旋轉偏移量（大多隻在旋轉後接近匹配時纔有用），以及它們在旋轉後的相似性。
不是我正在尋找的東西，但是你的回答讓我開始了一個好的方向。 – Mikos 2010-02-24 03:14:41
嘗試K-means算法。它動態計算每個簇的質心並計算與所有指針的距離並將它們與最近的簇相關聯。
非常感謝，不幸的是k-means似乎並不適合，因爲n不是先驗知道的。 – Mikos 2010-01-23 20:52:25
由於您的聚類基於形狀接近度量標準，因此您可能需要某種形式的連接組件標籤。 UNION-FIND可以給你一個快速的基本設置原語。
工會只，啓動一組不同的每一個點，併合並他們，如果他們滿足親近的一些標準，由當地共線性的影響，因爲這似乎對你很重要。然後繼續合併，直到您通過一些超過閾值的條件，以確定您的合併有多困難。如果你把它看作線條生長（只在它們的末端加入東西），那麼一些數據結構變得更簡單。你所有的羣集都是開放的線條和曲線嗎？沒有閉合的曲線，像圈子？
交叉線很難找到正確的，你要麼找到某種方式合併然後拆分，或者你設置合併標準非常有利於共線性，你在交叉線上運氣。
你可以進一步定義相似性嗎？根據我的理解，你有n組m個點（其中m的數量級爲100k）。你會用什麼標準來說任何2組相似？是否它們共享相同點的大部分子集（即，相同的x，y座標）或者兩組中的座標集緊密疊加（即描述幾何相似的2-d對象的不同座標）。 – awesomo 2010-01-20 18:30:35
謝謝，我更關注後者，即他們描述了類似的2D對象。讓我解釋一下我的用例，我有多個快速變化的散點圖，並希望通過相似性對它們進行聚類。 HTH和TIA – Mikos 2010-01-23 20:51:31
互相關會有幫助嗎？不過，我很困惑如何使其尺寸不變。我可以通過座標數量來標準化嗎？ 任何想法的人？ – Mikos 2010-01-26 17:01:07