4

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

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

$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。如果您考虑任何集合 where|A| = |B| = n和 where |Intersect(A, B)| = n * pfor ，您会得到类似的结果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" }

然后完整的不同集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 回答