尋找算法：通過「相似性」聚類

我有一組「向量」，我需要根據它們的「相似性」對它們進行排序。尋找算法：通過「相似性」聚類

像這樣：向量{1,0,0} {1,1,0} {0,1,0} {1,0,1}相當相似，最後應該彼此接近，但矢量{1,0,0} {8,0,0} {0,5,0} - 不是。

A和B之間的度量標準是max（abs（A [i] -B [i]）），但是什麼樣的算法可以根據相對比較來分類？

UPD：輸入：N矢量的陣列
輸出中：N矢量，其中通過索引向量最接近（ARR [I] ARR [I + 1]例如）都是 'similiar'=度量之間ARR [陣列i]和arr [i + 1]對於任何i，j來說都儘可能低。
指標 - 矢量分量的最大區別

UPD2：因爲現在看來，@jogojapan是對的 - 我需要按組

2012-04-16 ShPavel

定義「排序」是什麼意思...你有一個指標嗎？你想最小化相鄰向量之間的距離之和嗎？ – 2012-04-16 12:51:10

也許你的意思是[集羣]（http://en.wikipedia.org/wiki/Cluster_analysis）（即分組），而不是排序？ – jogojapan 2012-04-16 12:56:59

讓我改述我的評論：如果你有兩個訂單，你怎麼能決定哪一個更好？「應該接近每個」是不是一個定義... – 2012-04-16 13:06:00

這是一個集羣的載體之後，在一些線性順序打印出來，組由max norm (aka sup norm or l-infinity norm)引起的距離。如果按順序排序意味着排序，則距離不足以創建線性排序。

2012-04-16 12:53:20 Memming

沒有理由不能按距離原點排序。 – Marcin 2012-04-16 12:55:01

@Marcin可能。但我懷疑這是user286215想要的。他說'相對比較'。 – Memming 2012-04-16 12:56:37

-1

任何排序算法可以給你你想要的結果。

問題是你如何比較你的載體。你只是想比較它們的大小？或者是其他東西？

2012-04-16 12:54:13 Marcin

這就是問題所在，我無法比較矢量，但是對於任何給定的對，我可以告訴他們'相似'是他們 – ShPavel 2012-04-16 12:59:49

@ user286215所以，你沒有問題。只要您可以測試它們是否更大，更小或相等，則任何排序算法都可以工作。 – Marcin 2012-04-16 13:01:22

「只要你能測試它們是更大，更小還是相等」 - 好吧，這就是比較的定義。他只是說他無法比較......或者從另外一個角度來看：如果他比較他們，那麼他肯定不會達到他的目標。 – 2012-04-16 13:04:24

排序本質上是一個一維問題。你在這裏描述的聽起來更像一個加權圖，但目前還不清楚你的目標是什麼。如果您試圖識別與已知矢量「最接近」的矢量，您也可以從信息論中找到一些概念，例如Hamming Distance。

2012-04-16 12:56:33

那麼，顯而易見的方法是（層出不窮的）「層次聚類」，它總是合併那些距離最短的聚類。你可以在那裏插入你的指標。大多數實現都在O（n^3）中，因此對於大型數據集無用。另外，你會得到一個難以閱讀的巨大樹狀圖。

您可能想給OPTICS一個嘗試。在維基百科上查找它。它可能會滿足你的需求相當好，因爲它實際上排序的點。它將從一個集羣走到另一個集羣，實際上可以產生一個分層結構（如「嵌套」）集羣。一個好的實現應該在不帶索引結構的O（n^2）中運行，並且在帶索引加速的O（n log n）中運行。

2012-04-18 04:31:43

回答