リスト内の文字列間のコサイン類似度を計算する必要があります。たとえば、1,000 万を超える文字列のリストがあり、各文字列は、リスト内の他のすべての文字列との類似性を判断する必要があります。そのようなタスクを効率的かつ迅速に行うために使用できる最適なアルゴリズムは何ですか? 分割統治アルゴリズムは適用できますか?
編集
特定の文字列に最も類似している文字列を特定し、類似性に関連付けられた測定値/スコアを取得できるようにしたいと考えています。私がやりたいことは、最初はクラスターの数がわからないクラスター化に沿っていると思います。
SimStringを試すことができます。
これは、近似文字列マッチング用の C++ ライブラリ (Python または Ruby バインディングを使用) です。
1,300 万文字列のデータベースに対して、コサイン類似度の高い文字列を 1 ミリ秒未満で見つけると主張しています。
使用されるアルゴリズムは、転置リストの枝刈りに基づいてここで説明されています。
転置行列を操作します。これは、この種のタスクを高速に実行する (または単に Mahout を使用する) ために Hadoop で Mahout が行うことです。
基本的に、素朴な方法でコサイン類似度を計算するのは良くありません。多くの 0 * 何かを計算することになるからです。代わりに、列で作業し、そこにすべての 0 を残してください。