

n数の配列で同士でそれぞれの類似度を推定するにはどのような方法が効率的でしょうか。

例えば

[code]

    array1 = ['aaa', 'bbb', 'ccc', 'ddd']
    array2 = ['bbb','ccc']
    array3 = ['aaa', 'ccc', 'ddd', 'eee']
    array4 = ['aaa', 'bbb', 'ccc', 'ddd']
    array5 = ['aaa', 'bbb', 'ccc', 'ddd', 'eee']
    
[/code]

のような配列があり、array1に対する類似度（同じ要素が多いほど近しい）をarray2〜5でそれぞれ求めたいかたちです。  
上記の例の通り、配列内の要素数は一律でないものとします。

この件で実際に使用したい言語はJavaScriptですが、言語に関係なく考え方のアプローチをご教授いただければ幸いです。  
よろしくお願いします。


CC BY-SA 4.0
2021-05-31T03:08:44.223
76215
2021-05-31T11:25:36.823
45574
question
javascript array
配列の類似度を推定する方法


簡単のため、要素が文字列で、それぞれは一致するか不一致か、だけが類似度に寄与すると考えます。(似ている文字列が2つあっても、不一致であれば、それは単に不一致として扱う)

また、要素は文字列なので、数値的な(配列をベクトルと見立てる、のような)取り扱いを求めているわけではない、という理解の下、配列に対して定義される[レーベンシュタイン距離(aka
編集距離)](https://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2)をベースにするのは、妥当そうだ、と考えます。レーベンシュタイン距離は、ある2つの配列があったときに、一方の要素を削除/挿入/置換していくと、何回その操作を行えばもう一方の配列と一致するか、の値として定義されています。これを用いる良いところは、レーベンシュタイン距離を効率的に求めるアルゴリズムが広く知られていることです。

また、類似度なので、おそらく、完全一致で1,
完全不一致で0になるように正規化したいことが考えられ、これは、比較する2つの配列の長い方の長さでもって、レーベンシュタイン距離を割って、その後その値を1から引けば計算できるかな、と思っています。

* * *

この定義の下、 arr1 に対する類似度は、

[code]

    arr2: 0.5
    arr3: 0.5
    arr4: 1
    arr5: 0.8
    
[/code]

になります。


CC BY-SA 4.0
2021-05-31T04:49:15.913
76217
2021-05-31T11:25:36.823
2021-05-31T11:25:36.823
754
754
76215
answer