algorithm - 更好地设计我当前的算法

Question

我正在设计一种算法来比较两个对象，我有一个公式，但我不知道它是否尽可能好。

本质上，我是在比较两个游戏之间的比喻来说明它们有多么相似:

$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

我不喜欢这些结果，因为我觉得这些数字应该产生更高的相似度。

我希望能在这里提供一些意见，如果我走错了地方，至少可以提供一些关于我应该去哪里的指导。

非常感谢!

Answer 1

数学翻译

让我(尝试)将您所拥有的转化为更数学的公式。从那里应该更容易。

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 .

一般来说，对于上述形式的集合，您的相似度算法最终会低估两个集合之间的相似度。这看起来有点像下图中的紫色曲线。蓝色曲线是余弦相似度给出的结果。因此，如果 50% 是常见的且大小相等，则两组的相似度为 0.5 .同样，如果它们有 90% 的共同点，那么它的相似度为 0.9 .

余弦相似度

您可能希望得到与两组之间的角度类似的东西。考虑元素的总集合，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" }

然后是完整的 distinct 集，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);
}