高速な類似性検出

https://stackoverflow.com/questions/1889065

19-09-2019
|

質問

オブジェクトの膨大なコレクションがあり、それらの間の類似点を把握する必要があります。

正確に言うと:2 つのオブジェクトが与えられた場合、それらの相違度を数値として計算できます。メトリック - 値が大きいほど類似性が低いことを意味し、0 はオブジェクトの内容が同一であることを意味します。この数値を計算するコストは、小さいオブジェクトのサイズに比例します (各オブジェクトには所定のサイズがあります)。

与えられたオブジェクトから、それに類似したオブジェクトのセットを素早く見つける能力が必要です。

正確に言うと:何らかの相違値 d に対して、任意のオブジェクト o を、d よりも o と類似しないオブジェクトのセットにマップするデータ構造を作成する必要があります。これにより、セット内のオブジェクトのリストを配列する場合よりも時間がかからなくなります。またはリンクされたリスト (おそらく実際にそうなのでしょう)。通常、セットはオブジェクトの総数よりもはるかに小さいため、この計算を実行する価値は非常にあります。データ構造が固定の d を想定している場合は十分ですが、任意の d に対して機能する場合はさらに優れています。

この問題、またはそれに似た問題を以前に見たことがありますか?良い解決策とは何でしょうか?

正確に言うと:単純な解決策には、オブジェクトのすべてのペア間の相違点を計算することが含まれますが、これには時間がかかります - O(n²) ここで、n はオブジェクトの数です。より複雑性の低い一般的な解決策はありますか?

解決

メトリックの詳細を知らなくても、それは言うのは難しいのです。私はO（N ^ 2）側面を排除するための任意のアイデアを持っていないが、関係する定数の一部を削減する方法があるかもしれません。あなたが持っていた場合たとえば、ユークリッドメトリックD（P、Q）がSQRT（（P_1-Q_1）^ 2 + ... +（P_N-q_n）^ 2）、あなたは距離dを二乗し、部分的にそれを比較することができ= （P_I-Q_I）^ 2、あなたはD ^ 2を超えたときに停止の合計。

これは実際にあなたの時間を節約するかどうかは、ただの加数を計算し、どのように多くの被加数あなたがこれを行うことによって避けることが期待できる計算（明らかに、より小さなdが良く、ある）にどれだけ高価なインクルードは比較に依存します。

他のヒント

私は、データ構造を生成する必要がありますそれはのセットにoを任意のオブジェクトをマップしますよりOへのこれ以上の異なるオブジェクト D、いくつかの非類似度値dに対してます。

これは、小計がdより大きくなったときにちょうど類似度計算を放棄する最速のかもしれません。お使いの類似点は、コサインやハウスドルフ距離に基づいている場合たとえば、これは簡単に行うことができます。

PS：これを行うことができない場合は、の、あなたの問題はk最近傍の問題（あるいはより正確なしきい値周辺で最近傍問題）に関連している可能性があります。あなたはすべての距離（多分何か使って三角不等式）を計算することなくクローズすることによりメンバー見つけるアルゴリズムを探してください。ウィキペディアには、適切なアルゴリズムを探索するお手伝いをする必要があります。の

お使いの類似性尺度が推移がある場合は、

は、あなたがオブジェクトのすべてのペアのための類似性を計算する必要はありませんので、オブジェクトのために、A、B、C：

similarity(a,c) = similarity(a,b) op similarity(b,c)

opは、例えば、バイナリ演算子であります乗算または追加。

解決策は問題の性質の詳細に依存すると思います。

同じオブジェクトの類似オブジェクトを何度も検索する必要がありますか、それとも 1 回だけ検索する必要がありますか?回数が多い場合は、ペアごとに差を 1 回計算し、オブジェクトを類似オブジェクトに接続するデータ構造を作成して、再計算せずにリストをすばやく取得できるようにすると、非常に有益なパフォーマンス向上が得られる可能性があります。
計算の性質は何ですか?極端な場合、違いの性質が、たとえば 2 人の人の身長の違いである場合、身長でソートされたリストを維持すると、類似したオブジェクトを非常に迅速に見つけることができます。実際の問題はそれよりも複雑だと思いますが、そのロジックに従うと、差がいくつかの線形量の合計である場合、多次元配列を作成し、それらと類似したオブジェクトのセットを概念的に想像できます。 n 次元の球内 (すなわち、参照オブジェクトを中心とする円、球、超球など) を直接検索します。実際、半径の計算が複雑すぎる場合、または実行時間がかかりすぎる場合は、n 次元の立方体 (つまり、参照オブジェクトの周りの正方形、立方体、テッセラクトなど)、その立方体内にあるすべてのオブジェクトを「候補」として取得し、候補に対して実際の計算を実行するだけです。

たとえば、「差」が 3 つの属性 (a1、a2、a3) の差の絶対値の合計であるとします。3 次元配列を作成し、配列の各ノードの値を、それらの値を持つオブジェクト (存在する場合) に設定できます。次に、オブジェクト o との差が d 未満であるすべてのオブジェクトを検索したい場合は、次のように記述できます。

for (x1=o.a1-d;x1<o.a1+d;++x1)
{
  for (x2=o.a2-d;x1<o.a2+d;++x2)
  {
    for (x3=o.a3-d;x1<o.a3+d;++x3)
    {
      if (array[x1][x2][x3]!=null
        && (abs(x1-o.a1)+abs(x2-o.a2)+abs(x3-o.a3)<=d)
        {
          ... found a match ...
        }
    }
  }
}

差分ルールはそれよりも複雑だと思いますが、問題はありません。ルールの複雑さに合わせてアルゴリズムに洗練さを加えるだけです。重要なのは、配列を使用して、調査する必要があるオブジェクトのセットを制限することです。

計算の性質についてもう一度説明します。違いを構成する要素の 1 つ、または小さなサブセットが他の要素よりも重要である傾向がある場合は、範囲内でこれをすばやく比較できるデータ構造を作成します。範囲内にある場合は、完全な比較を実行します。そうでなければ、見向きもしないでしょう。

は、のK のD-ツリーを使用することはできませんか？

これは、大きさを正規化する（可能な場合）が必要であってもよいです。その後、あなただけのツリーを移入し、「最も近いNの隣人」検索を使用して、いくつかの範囲内の任意のオブジェクトを見つけようとする必要があります。

オブジェクトの例：画像、ドキュメント。もちろん、これらのオブジェクトの生の表現を扱うことはほとんど役に立ちません。通常、1つは、生の形式を事前処理し、（いくつかの正規化された形式に変換します文書に対して、それが見つかった視覚的特徴の表現とすることができる画像に対して、各エントリは、特定の単語が出現回数/パーセントを表すためのベクターを言います画像内）。

dは一定であり、n ^ 2事前計算が可能である場合は、単に、例えば、各オブジェクトのリンクされたリストを使用してグラフ表現を使用することができます。あなたはおおよその最近傍アルゴリズムを使用して、精度を犠牲に、より効率的なソリューションを持つことができます。

類似性は推移的であると仮定できますか。 diff(a,c) == diff(a,b) + diff(b,c)?その場合は、次のことを試してみてください。

オブジェクトのコレクションを並べ替えます。オブジェクトの類似性メトリックに適切な絶対値がない場合は、任意に 1 つのオブジェクトを「ゼロ」として選択し、他のすべてのオブジェクトをそのオブジェクトとの類似性によって並べ替えることができます。
類似性のあるオブジェクトを見つけるには s に o, 、探す o ソートされたリスト内で、差分が大きくなるまで左と右に検索します。 s.

この利点は、ソートが 1 回で済み、その後のセットの構築がセットに含まれるメンバーの数に比例することです。

BK-ツリーのような音。ここでは小さいです例に。あなたは基本的にツリーを作成し、類似したオブジェクトの検索やないために使用されるべき枝チェックし、あなたが

O(n2)を防ぎます

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow