6

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

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

オブジェクトが与えられた場合、それに類似したオブジェクトのセットをすばやく見つける機能が必要です。

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

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

正確に言うと、単純な解決策には、オブジェクトのすべてのペア間の非類似度を計算することが含まれますが、これは時間がかかります - O(n 2 ) ここで、n はオブジェクトの数です。複雑さの低い一般的なソリューションはありますか?

4

8 に答える 8

2

任意のオブジェクト o を、o と d よりも似ていないオブジェクトのセットにマップするデータ構造を作成する必要があります。

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

 

PS:これができない場合、問題は k 最近傍問題 (または、より正確には、しきい値近傍を持つ最近傍問題) に関連している可能性があります。すべての距離を計算せずに近くのメンバーを見つけるアルゴリズムを探す必要があります (三角形の不等式を使用するものなど)。ウィキペディアは、適切なアルゴリズムを調べるのに役立ちます。

于 2009-12-11T16:45:31.483 に答える
1

メトリックの詳細を知らなければ、なんとも言えません。O(n^2) の側面を排除するためのアイデアはありませんが、関連する定数の一部を減らす方法があるかもしれません。たとえば、ユークリッド メトリック d(p,q) = sqrt( (p_1-q_1)^2 + ..+ (p_n-q_n)^2) がある場合、距離 d を 2 乗して、部分的な距離と比較できます。 (p_i-q_i)^2 の合計を計算し、d^2 を超えると停止します。

これが実際に時間を節約するかどうかは、比較が加数を計算するだけでどれだけコストがかかるか、およびこれを行うことで回避できる加数計算の数に依存します (明らかに、d が小さいほど良いです)。

于 2009-12-11T16:49:37.467 に答える
1

オブジェクトの例: 画像、ドキュメント。もちろん、これらのオブジェクトの生の表現を扱うことはほとんど役に立ちません。通常、生の形式を前処理して、正規化された形式に変換します（ドキュメントの場合、各エントリが特定の単語の出現回数/パーセントを表すベクトル、画像の場合、見つかった視覚的特徴の表現である可能性があります画像で）。

d が固定されていて、^2 の事前計算が実行可能な場合は、たとえば、各オブジェクトのリンク リストを使用してグラフ表現を使用できます。近似最近傍アルゴリズムを使用すると、精度を犠牲にしてより効率的な解を得ることができます。

于 2010-04-08T22:50:15.717 に答える
1

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

  1. 同じオブジェクトの類似オブジェクトを何度も検索する必要がありますか?それとも一度だけ検索する必要がありますか? 回数が多い場合は、ペアごとに 1 回差を計算し、オブジェクトを類似のオブジェクトに接続するデータ構造を作成して、再計算せずにリストをすばやく取得できるようにすると、パフォーマンスが非常に向上する可能性があります。

  2. 計算の性質は何ですか？極端な例として、違いの性質が、たとえば 2 人の身長の違いである場合、身長で並べ替えられたリストを維持すると、類似したオブジェクトを非常に迅速に見つけることができます。実際の問題はそれよりも複雑だと思いますが、その論理に従って、差がいくつかの線形量の合計である場合、多次元配列を作成し、それらと同様のオブジェクトのセットを概念的に想像することができます参照オブジェクトを中心とする n 次元の球 (つまり、円、球、超球など) 内で、再びそれらを直接見つけます。実際、半径の計算が複雑すぎたり、実行時間が長すぎたりする場合は、n 次元の立方体 (つまり、正方形、立方体、tesseract、

たとえば、「差」が 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. 再び計算の性質について: 違いを構成する要素の 1 つ、または一部の小さなサブセットが他の要素よりも重要である傾向がある場合は、範囲内でこれをすばやく比較できるデータ構造を作成します。範囲内にある場合は、完全な比較を行います。そうでなければ、あなたはそれを見さえしません。
于 2009-12-11T17:35:04.697 に答える
1

類似度が推移的である場合、オブジェクト a、b、c の場合、オブジェクトのすべてのペアの類似度を計算する必要はありません。

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

はop乗算や加算などの二項演算子です。

于 2009-12-11T16:11:25.750 に答える
1

k d-treeを使用することはできませんか?

(可能であれば) 寸法を正規化する必要がある場合があります。その後、ツリーにデータを入力し、「最も近い N 近傍」検索を使用して、ある範囲内のオブジェクトを見つけようとするだけです。

于 2009-12-11T19:37:38.053 に答える
0

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

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

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

于 2009-12-11T16:14:35.060 に答える