8

このサイトで同様の問題を探したところ、http：//math.nist.gov/javanumerics/jama/とこれが見つかりました：http： //sujitpal.blogspot.com/2008/09/ir-math-with- java-similarity-measures.html

ただし、これらはO（n ^ 2）で実行されているようです。私はいくつかのドキュメントクラスタリングを行ってきましたが、小さなドキュメントセットを処理する場合でも、このレベルの複雑さは実現不可能であることに気付きました。ドット積の場合、両方のベクトルに含まれるベクトル項のみが必要であるとすると、ベクトルをツリーに配置して、n log nの複雑さでドット積を計算できます。ここで、nはで一意の項の最小数です。 2つのドキュメントのうちの1つ。

私は何かが足りないのですか？これを行うJavaライブラリはありますか？

ありがとう

4

4 に答える 4

2

ハッシュマップは優れていますが、多くのメモリを必要とする可能性があります。

ベクトルがキーでソートされたキーと値のペアとして保存されている場合、ベクトルの乗算はO（n）で実行できます。両方のベクトルを並列に反復する必要があります（マージソートアルゴリズムなどで同じ反復が使用されます）。乗算の擬似コード：

i = 0
j = 0
result = 0
while i < length(vec1) && j < length(vec2):
  if vec1[i].key == vec2[j].key:
    result = result + vec1[i].value * vec2[j].value
  else if vec1[i].key < vec2[j].key:
    i = i + 1
  else
    j = j + 1
于 2010-07-27T19:22:05.163 に答える
2

ベクトル要素をハッシュテーブルに格納する場合、ルックアップはとにかく log n だけですよね? 小さいドキュメント内のすべてのキーをループし、それらが大きいドキュメントに存在するかどうかを確認します..?

于 2010-07-27T18:13:05.440 に答える
0

サイズが n のセット内のすべてのアイテムに限定されたアイテム (たとえば m アイテム) のみを推奨する場合、複雑さは n^2 ではなく、m*n である必要があります。m は定数なので、複雑さは線形です。

プロジェクト simbase https://github.com/guokr/simbaseで確認できます。これはベクトル類似の nosql データベースです。

Simbase は以下の概念を使用します。

  • ベクトル セット: ベクトルのセット
  • 基底: ベクトルの基底、1 つのベクトル セット内のベクトルは同じ基底を持つ
  • 推奨事項: 同じ基準を持つ 2 つのベクトル セット間の一方向のバイナリ関係
于 2014-06-12T15:14:53.420 に答える