次のようなデータセットがあるとします。
{A:1, B:3, C:6, D:6}
特定のセットを比較するための他のセットのリストもあります。
{A:1, B:3, C:6, D:6},
{A:2, B:3, C:6, D:6},
{A:99, B:3, C:6, D:6},
{A:5, B:1, C:6, D:9},
{A:4, B:2, C:2, D:6}
私のエントリはテーブルとして視覚化できます (4 つの列 A、B、C、D、および E)。
最も類似性の高いセットを見つけるにはどうすればよいですか? この例では、行 1 は完全一致で、行 2 は僅差の 2 番目ですが、行 3 はかなり離れています。
たとえば、単純なデルタを計算することを考えています。Abs(a1 - a2) + Abs(b1 - b2) + etcおそらく、最良のデルタを持つエントリの相関値を取得します。
これは有効な方法ですか？そして、この問題の名前は何ですか?
「距離」または「類似性」は、このタイプの問題を指す場合があります。
あなたが行ったように、絶対差の合計を計算するだけで、かなりうまくいくはずです。これはマンハッタン距離と呼ばれます。数学的には、次のようになります。∑<sub>x ∈ (a,b,c,d) Abs(x1 - x2)
最善の対策は、実際に必要な動作によって異なります。
比率は、より良いアイデアになる可能性があります。
1000000, 5, 5, 5vs999995, 5, 5, 5やのようなものを考えてみましょう1000000, 0, 5, 5。
上記の式によると、最初の要素は 2 番目と 3 番目の要素の両方と同じ類似性を持ちます。
これが望ましくない場合 ( に999995かなり近いと考えられる1000000一方0で、 からかなり離れていると考えられる5場合)、各距離を計算するときに 2 つの最大値で除算する必要があります。
∑<sub>x ∈ (a,b,c,d) [ Abs(x1 - x2) / max(x1, x2) ]
これにより、すべての数値が 0 から 1 の間に配置されます。これは、値のパーセンテージの差です。
これは、上記の例では、 と は非常に似ていると見なし (上記の合計は になるため1000000, 5, 5, 5) 、とははるかに異なると見なされることを意味します (合計が になるため)。999995, 5, 5, 5|1000000-999995|/1000000 + 0 + 0 + 0 = 0.0000051000000, 5, 5, 51000000, 0, 5, 5|0+5|/5 + 0 + 0 + 0 = 1
負の値が発生する可能性がある場合は、数式を適切に更新する必要があります。解決しようとしている問題に基づいて、それをどのように処理するかを決定する必要があります。10 to 0と多かれ少なかれ異なる（または同等である）必要があり5 to -5ますか？
A=1, B=2, C=3, D=4とのようなものを考えてみましょうA=4, B=1, C=2, D=3。
個々の要素はすべて変更されていますが、セットは引き続き構成されて1, 2, 3, 4おり、各要素は 1 位置だけシフトされています ( を除く4)。
一部の問題では、これはまったく問題にならず、上記は からA=1, B=11, C=21, D=31への移動とそれほど違いはありませんA=2, B=12, C=22, D=32。ただし、他の問題については、非常に関連性がある可能性があります。
string や array のようなシーケンスの場合、要素を挿入、削除、またはシフトするという考えは理にかなっています。もしそうなら、編集距離を見たいと思うでしょう。そのうちの一般的なものはレーベンシュタイン距離です。また、これを変更して、個々の値がどの程度異なるかを検討することを検討することもできます (ただし、これは簡単なことではありません)。
set のようなものでは、要素は交換可能ですが、実際には要素に厳密な順序はありません ({1, 2, 3}は と同じ{3, 1, 2}です)。この場合、最も簡単なのは、値を並べ替えて、編集距離を使用することです。何らかの方法で両方を同時にループすることもできます。これにより、値の違いをより簡単に考慮に入れることができます。
あなたの問題は、ハミング距離を見つけることを思い出させます。基本的に、2 つのオブジェクト間のハミング距離は、一方のオブジェクトが他方のオブジェクトと一致するように変更する必要がある要素の数です。同様の尺度もあります (ダメラウ・レーベンシュタイン距離、ユークリッド距離など)。
これを実装する方法には、いくつかの選択肢があります。たとえば、{1,3,4} と {1,7,4} の間の距離は 1 (1 つの要素が変更されたため) または 4 (変更の大きさのため) ですか? 距離を実際にどのように定義するかは、問題のコンテキストに大きく依存し、必ずしも正しい答えがあるとは限りません。