2

2 つのセット (順不同、重複要素なし) を想定します。

A = set(["z", "x", "c"])
B = set(["x", "z", "d", "e"])

これらのセットには、"z" と "x" の 2 つの共通要素と、セット固有の要素 c、d、e があります。

ストリング距離のように、各セットにスコアを与えるにはどうすればよいですか?

  • 要素の順序を無視し、
  • 孤立したセットごとに重複禁止の制約を課す

?

例でわかるように、各セットのサイズは異なる場合があります。

このアルゴリズムの重要でない要件は次のとおりです。

  • 挿入 > 削除 (要素が不足しているセットは、要素が多すぎるセットよりもコストが高いことを意味します) 可能であれば、または単に INS = DEL
  • スワップ: 0 (注文は距離に影響しないため、コストはかかりません)

今のところ、設定された距離スコアを計算しています。

score_A = len(common(a,b)) / len(a)    # common(...) calculates intersection
score_B = len(common(a,b)) / len(b)

quadratic_score = sqrt(score_A * score_B)

この問題にどのようにアプローチするか、ソリューションを改善することをお勧めしますか?

コストを指定できるアルゴリズムはありますか?

今、集合変更のための単純な代数を定義しようとしています:

def calculate_distance( a, b, insertion_cost=1, deletion_cost=1 ):
    """
    Virtually, a programmer-friendly set-minus.

    @return     the distance from A to B, mind that this is not
                a commutative operation.
    """
    score = 0
    for e in a:
        if e not in b: # implies deletion from A
            score += deletion_cost

    for e in b:
        if e not in a: # implies insertion into A
            score += insertion_cost

    return score

この値を何に対して正規化するにはどうすればよいですか?

4

3 に答える 3

3

より大きなセットのサイズに対するセットの交点のサイズはどうですか? そう：

float(len(A.intersection(B)))/max(len(A),len(B))

多くの場合、望ましい0.0から1.0の範囲でスケーリングされた数値が得られます。1.0 は完全な平等を表し、0.0 は共通点がないことを表します。

于 2012-07-03T18:02:41.573 に答える
2

this oneと同様の質問

OPが「距離」として何かを求めていると仮定すると、距離関数の一般的な要件に従って2つのセットが同一である場合は0にする方がよいと思います

また、対称不等式と三角不等式があるとよいでしょう。

対称は直感的で、三角形の不等式は d(A,C) ≤ d(A,B) + d(B,C) を意味します

私は次のようなものを提案します：

C = A.intersection(B)
Distance = sqrt(len(A-C)*2 + len(B-C)*2)

ただし、三角不等式の証明方法はまだわかりません。

OPの更新された関数の結果を正規化するには、次のようにしますscore = score / (len(a) + len(b))

aが交差しない場合は 1 になり、が交差する場合はb0 になります。a == b

于 2012-07-03T19:19:29.190 に答える