算法幫助需要

Question

我有一組序列（例如10000個序列），並生成一個矩陣（10000×10000），表示每兩個序列之間的成對相似性。

現在的目標是從大集合中檢索一個子集（例如1000個序列），並確保該子集中每兩個序列之間的成對相似性在一個範圍內（例如50％〜85％）。

有沒有什麼快速的算法來做到這一點？

Answer 1

可以改造這個到圖論問題：

1. 每個序列是一個節點
2. 如果兩個節點的相似性是在給定的範圍相比，還有他們之間的邊緣
3. 你的目標是找到大號connected component（如果您的相似關係是過渡性的......）或大號clique（...如果不是）。

Answer 2

您可以生成兩兩相似的排序列表（回頭指向您的矩陣），獲取該排序列表的子集，然後確保該子列表與您的子集之間的交集與您的子集大小相同，從而驗證子集中的所有元素都在指定範圍內。

雖然需要大量的設置來生成矩陣和大量的空間來創建有序列表。至少，你的矩陣設置是O（n^2）。

Answer 3

這聽起來像是「集團發現」給我;集團決策問題是NP完全的。

根據序列相似性背後的統計數據，您可能會滿意最大團問題的近似算法。一個隨機算法對你來說甚至可能足夠好。但總的來說，這是一個非常棘手的問題，即使N = 100，也不太可能做到這一點。

Answer 4

許多相似之處與n維中的點積相當或相關空間，即使當相似性沒有被明確計算時。在這些情況下，可能還有其他情況，a.b和b.c的高值可能意味着a.c的高值，但這種情況的好處並不是很好 - 不如我想象的那麼好。

僅涉及三個向量 - a，b和c我認爲，無論底層空間的維度如何，您都可以繪製三維圖表，並且我認爲最糟糕的情況是所有三個向量都處於飛機上面b和c下面b。在那種情況下，例如所有單位矢量都是單位矢量，a.b = b.c = 0.9，a比b大約25度，c比它低大約25度，a.c = 0.62。事實上，在這種情況下，對於ac = bc = x，ac = 2x^2 - 1.

在這些情況下，如果我絕對需要解決這個問題，我會嘗試回溯搜索來枚舉幾組非常接近到特定節點。例如，您可以從兩個最相似的節點開始，然後運行一個搜索，在每個級別上添加尚未嘗試過的最接近原始種子節點的節點。或者你可以建立一個單一的鏈接聚類，並檢查出所需大小的所有子樹。