4

2つのオブジェクトを比較するアルゴリズムを設計しています。数式はありますが、それが可能な限り優れているかどうかはわかりません。

基本的に、私は2つのゲーム間の比喩を比較して、それらがどれほど類似しているかを示しています。

$divisor = ((count($similar_concepts) - $iterator) + ($total - $iterator) + ($iterator));
echo "<BR> Value: ".($iterator / $divisor);

しかし、それは読みにくいので、ここにあります：

 SimilarTropes/( (OriginalTropes - SimilarTropes) + (NewTropes - SimilarTropes) + (SimilarTropes) )

結果に完全に満足しているわけではありません。例を次に示します。

Similarities: 47
NewTropes: 107
OriginalTropes: 156
Answer: 0.21759259259259

これらの数値は類似性のパーセンテージが高くなるはずだと思うので、これらの結果は好きではありません。

私はここでいくつかの入力が欲しいです、そして私が間違った場所にいるなら、少なくとも私が代わりにどこに行くべきかについてのいくつかのガイダンス。

どうもありがとう！

4

1 に答える 1

5

数学への翻訳

私に（試みて）あなたが持っているものをもっと数学的な公式の何かに翻訳させてください。そこからはもっと簡単なはずです。

OriginalTropesあるゲームからの比喩の数です、それを呼びますA。次にNewTropes、他のゲームからの比喩です、それを呼び出しますB。次に、Similaritiesは単にとの交点AですB。その場合、式は次のようになります。

|Intersect(A, B)| / ((|A| - |Intersect(A, B)|) + (|B| - |Intersect(A, B)|) + |Intersect(A, B)|)

単純化すると、次のようになります。

|Intersect(A, B)| / (|A| + |B| - |Intersect(A, B)|)

つまり、類似性とは、共通アイテムの数をアイテムの総数から共通アイテムの数を引いたもので割った比率のことです。

それでは、いくつかの特殊なケースを取り上げましょう。取るA = B。次に、次のようになります。

|Intersect(A, B)| = |A| = |B|。その場合、式は次のようになります。

|A| / (|A| + |A| - |A|) = 1

制限事項

Aここで、セットとBサイズが等しいとしましょう。しかし、彼らは共通のアイテムの半分しか持っていません。言い換えると、

|A| = |B| = 2 |Intersect(A, B)|

その場合、類似性スコアは次のようになります。

1/2 |A| / (2|A| - 1/2|A|) = 1/3

理想的には、これはで1/2はなく、である必要があり1/3ます。|A| = |B| = nの場所と場所|Intersect(A, B)| = n * pのセットを検討すると、似たようなものが得られます0 <= p <= 1。

一般に、上記の形式のセットの場合、類似性アルゴリズムが2つのセット間の類似性を過小評価することになります。これは、下の画像の紫色の曲線のように見えます。青い曲線は、余弦の類似性が与えるものです。したがって、50％が一般的で、サイズが等しい場合、2つのセットの類似度は0.5です。同様に、それらの共通点が90％の場合、類似度は0.9です。

ここに画像の説明を入力してください

コサイン類似性

あなたが望むかもしれないのは、2つのセットの間の角度に似たものです。要素のセット全体を検討し、Intersect(A, B)を定義しますN = |Intersect(A, B)|。aとをbとのN次元表現とAします。ここBで、各要素は1、元のセットに存在する場合と存在しない場合に値を持ちます0。

次に、角度の正弦を次のように使用します。

Cos(theta) = Dot(a, b) / (||a|| * ||b||)

||a||表記は、セットのサイズではなく、ユークリッド距離を参照していることに注意してください。これは、以前使用していたものよりも優れたプロパティを持っている可能性があります。

例

これが例です。まあ言ってみれば：

 A = { "Big Swords", "Male Hero", "No Cars" }
 B = { "Male Hero", "Trains", "No Dragons" }

次に、完全に異なるセットUnion(A, B)は次のように与えられます。

Union(A, B) = { "Big Swords", "Male Hero", "No Cars", "Trains", "No Dragons" }

これは、を意味しN = |Union(A, B) = 5ます。トリッキーなパーティは、これらのそれぞれを適切にインデックス化する方法になります。実際には、辞書とカウンターを使用して要素にインデックスを付けることができます。これはあなたに任せて試してみます。今のところ、の順序を使用しますUnion(A, B)。次にa、とbは次のように与えられます。

a = { 1, 1, 1, 0, 0 }
b = { 0, 1, 0, 1, 1 ]

この時点で、それは標準的な数学になります：

Dot(a, b) = 1
|a| = sqrt(3)
|b| = sqrt(3)
Similarity = 1 / 3

サンプル実装

public double Compare(IEnumerable<String> A, IEnumerable<String> B)
{
    // Form the intersection between A and B
    var C = A.Intersect(B);

    // a and b are N (C.Length) dimensional bi-valued (0 or 1) vectors
    var a = new List<int>(C.Length);
    var b = new List<int>(C.Length);

    var map = new Dictionary<String, int>();

    // Map from the original key to an index in the intersection
    for (int i = 0; i < C.Length; i++)
    {
        var key = C[i];
        map[key] = i;
    }

    // Set the 1's in the N-dimensional representation of A
    foreach (var element in A)
    {
        var i = map[element];
        a[i] = 1;
    }

    // And do the same for B
    foreach (var element in B)
    {
        var i = map[element];
        b[i] = 1;
    }

    int dot = 0;

    // Easy part :) Standard vector dot product
    for (int i = 0; i < C.Length; i++)
        dot += a[i] * b[i];

    // It suffices to take the length because the euclidean norm
    // of a and b are, respectively, the length of A and B
    return dot / Math.Sqrt((double) A.Length * B.Length);
}
于 2012-07-03T03:44:21.473 に答える