0
這個問題涉及信息檢索中的類似文檔的分組/聚類。組相似的文檔
我有一組文檔，D1，D2，.. Dn。對於每個文件Di，我也有一組關鍵字Di_k1，Di_k2，...，Di_km。兩個文檔之間的相似性Di和Dj由涉及相關關鍵字的函數給出，即相似性（Di，Dj）= f（Di_K，Dj_K）。
現在，我希望將這些文檔中的每一個放置到一組組/集羣中，使得每個集羣都包含相似類型的文檔，以用於集羣中存在的元素之間的相似閾值。
一個簡單的方法是查看每一對可能的頁面，我明顯想避免，因爲我擁有的文檔數量相當大，以百萬計。我正在閱讀「信息檢索簡介」一書，但我沒有找到任何提及的可伸縮算法。
我的問題是什麼樣的算法可以幫助我有效地聚集文件？我特別感興趣的是算法的計算複雜度。
在此先感謝任何指針。
請澄清到底在找什麼。找到最佳子集是NP Hard，那是你在找什麼？ – amit 2011-05-29 14:12:44
是的。我知道它很難，這就是爲什麼我正在尋找一種高效的算法解決方案，它比最簡單但最慢的實現方案更好。 – user429113 2011-06-02 19:37:39
由於它是NP Hard，因此對於這個問題沒有已知的多項式解法，您將不得不迭代所有可能的解並選擇最優 - 這將是O（2^n），其中n是文檔數。有一些多項式算法可以找到近似值，但這些只是啓發式算法，可能會失敗。 – amit 2011-06-02 23:16:19