更好地设计我当前的算法

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" }

然后完整的不同集合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);
}