2

行の各要素が (キー、値) のペアであるデータ行の大きなコレクションがあるとします。

1)    [(bird, "eagle"), (fish, "cod"),      ... , (soda, "coke")]
2)    [(bird, "lark"),  (fish, "bass"),     ...,  (soda, "pepsi")]
n)    ....
n+1)  [(bird, "robin"), (fish, "flounder"), ...,  (soda, "fanta")]

新しい行を特定できる計算を実行したいのですが、この行に「最も似ている」行はどれですか?

特定の行に対して「最も類似した」行を見つける最も直接的な方法は、その行を他のすべての行と直接比較することです。これは明らかに計算上非常に高価です。

次の形式の解決策を探しています。

  • 行を取り、その行の微分整数を生成できる関数。この返された整数は、行の一種の「署名」になります。この署名の重要な特性は、2 つの行が非常に「似ている」場合は非常に近い整数を生成し、行が非常に「異なる」場合は離れた整数を生成することです。明らかに、それらが同一の行である場合、同じ署名が生成されます。

  • 次に、これらの生成された署名を、それらが指す行のインデックスと共に取得し、それらを署名ごとに並べ替えることができます。このデータ構造を保持して、高速な検索を実行できるようにします。これをデータベース B と呼びます。

  • 新しい行がある場合、データベース B の既存のどの行が最も類似しているかを知りたい場合は、次のようにします。

    1. 新しい行の署名を生成します
    2. データベース B の (signature,index) のソートされたリストをバイナリ検索して、最も近い一致を探します。
    3. データベース B で最も一致する (完全に一致する可能性がある) 行を返します。

私は彼らがこの質問で多くの手を振っていることを知っています. 私の問題は、この署名を生成する関数が何であるかを実際に知らないことです。レーベンシュタイン距離が表示されますが、それらは変換コストを表しており、署名ではありません。非可逆圧縮を試すことができることがわかりました.2つのものが同じものに圧縮されるため、「バケッタブル」である可能性があります。これを行う方法について他のアイデアを探しています。

ありがとうございました。

4

2 に答える 2

1

大量のデータがあり、これを本格的に実行したい場合は、PLSAやPSVMなどの統計的手法をお勧めします。これにより、テキストから識別トピックを抽出し、同様のトピック確率を持つドキュメントを識別できます。

より簡単ですが、精度は劣りますが、Soundexを使用する方法があります。これは、多くの言語で利用できます。あなたはsoundex（私が恐​​れている整数ではなく、短い文字列になるでしょう）を保存し、同様の行を指しているはずのsoundexと完全に一致するものを探すことができます。

関数が一連の文字列を整数に変換し、互いに近い整数が同様の文字列にマップされることを期待するのは非現実的だと思います。最も近いのは、個々のタプルごとにチェックサムを実行し、新しい行のチェックサムを既存の行のチェックサムと比較することですが、インデックスを作成できる単一の数値を見つけようとしていると思います。

于 2011-01-23T02:10:26.053 に答える
1

編集：これは私の最初の答えです。これをケース1と呼びます。キーに優先順位はありません

それは1次元であり、データは多次元であるため、ソートされた整数として行うことはできません。そういう意味での「近さ」は線上では成立しません。

あなたの例は、3行すべての鳥、魚、ソーダを示しています。キーは固定され、既知ですか? そうでない場合、最初のステップは、行のキーをハッシュして、同じキーを持つ行を確立することです。

値については、これを貧乏人のサタデー ナイトの類似性トリックと考えてください。値をハッシュします。そのハッシュで一致する 2 つの行は完全に一致し、同じ「スポット」、ゼロ距離を表します。

N がキーと値のペアの数の場合:

最も近い非正確な「近さ」は、N 個の値のうち N-1 個が一致することを意味します。したがって、さらに N 個のハッシュを生成し、それぞれが値の 1 つを削除します。これらのハッシュに一致する 2 つの行には、N 個の値のうち N-1 個が共通しています。

次に近い不正確な「近さ」は、N 個の値のうち N-2 個が一致することを意味します。したがって、さらに N 個を超えるハッシュを生成します (この時点でバイナリを把握することはできません)。今回は、各ハッシュが 2 つの値の組み合わせを除外します。これらのハッシュで一致する 2 つの行には、共通の N 個の値のうち N-2 個があります。

だから、これがどこに向かっているのかを見ることができます。論理的に極端な場合、2^N ハッシュになり、あまり美味しくありませんが、検討する価値があると見なされる一致する値が「遠い」と見なされる点が少なすぎるため、そこまで行かないと思います。

編集:次元を逃れることができないことを確認するために、値が 1 ～ 9 の 2 つのキーだけを考えてみましょう。可能なすべての値をグラフにプロットします。{1,1} が {2,2} に近いだけでなく、{5,6} が {6,7} に近いこともわかります。そこで、ブレインストーミングを行います。ピタゴラスの定理を使用して、原点から各ポイントの距離を計算します! これにより、{1,1} と {2,2} の両方を簡単に検出できます。しかし、2 つの点 {1,10} と {10,1} は、グラフ上で可能な限り離れていても、同じ数になります。そこで、それぞれの角度を追加する必要があります。同じ距離にある 2 点は角度によって区別され、同じ角度にある 2 点は距離によって区別されます。しかしもちろん、今はそれらを 2 次元でプロットしました。

編集: ケース 2 は、キーに優先順位がある場合、キー 1 がキー 2 より重要な場合、キー 3 より重要な場合などです。この場合、許可された値が AZ の場合、値を文字列化します。並べ替え可能な値を取得するための数字であるかのように組み合わせます。ABC は ABD に非常に近いですが、BBD からは非常に遠いです。

于 2011-01-23T02:34:45.693 に答える