在顺序重要的情况下计算相似度

Question

如果项目的顺序很重要，并且类似于贾卡德指数之类的东西，那么如何计算相似度(系数)就没有用了。

具体来说，我对比较配料感兴趣。举个简单的苹果派配料清单为例：

• 苹果
• 强化未漂白面粉
• 棕榈油
• 高果糖玉米糖浆
• 食盐
• 蛋
• 香料

然后将其与以下内容进行比较：

1. 完全相同的成分，但顺序相反。香料是最主要的成分，苹果是最不常用的成分。
2. 用植物油代替棕榈油，用糖代替玉米糖浆。

即使你天真地认为#2中的替代物是相似的，那么#2的集合比原来的#1更相似。有没有一种算法可以表达这一点呢？

Answer 1

对一个有趣的问题的迟答：

在项目顺序重要的情况下，如何计算相似度(系数)？

这正是基于字符的近似字符串匹配度量所做的，因为字符串是一个有序的字符列表。因此，我们的想法是将列表中的每个元素作为字符串中的一个字符，并应用该算法。主要的基于特征的措施是：

• Levenshtein编辑距离，它有许多可用的变体
• 雅罗-温克勒

我建议前者，因为它有一个更明确的解释，可能是更普遍的使用。

Answer 2

不确定这是否已经存在，但是也许您可以通过一些需求构建一个新的相似性度量(让我们称之为js)：

• 如果列表A和B完全相同，那么js(A, B) = 1.0
• 如果列表A和B完全不同(没有共同点)，那么js(A, B) = 0.0
• 如果所有元素都匹配但被洗牌，那么js(A, B) = 0.5
• 如果是|A| \neq |B|，那么相似性度量应该考虑最长列表中的项目(例如，如果A中的额外成分很少，但B是相同的，那么它仍然会受到一些惩罚)

然后，您可以构建一个基本完成以下操作的方法(例如，在python中)：

def js(A, B):
    cummulative_score = 0
    longest_list = B
    shortest_list = A
    if len(A) > len(B):
        longest_list = A
        shortest_list = B

    for index, element in enumerate(longest_list):
        if index < len(shortest_list):
            if element == shortest_list[index]:
                cummulative_score += 1
            if element != shortest_list[index]:
                if element in shortest_list:
                    cummulative_score += 0.5
    return cummulative_score / len(longest_list)

然后你就会得到这样的东西：

In [10]: print(l)
['Apples', 'Enriched Unbleached Flour', 'Palm Oil', 'High Fructose Corn Syrup', 'Salt', 'Eggs', 'Spices']

In [11]: print(l1)
['Apples', 'Enriched Unbleached Flour', 'vegetable oil', 'sugar', 'Salt', 'Eggs', 'Spices']

In [12]: print(l2)
['Spices', 'Eggs', 'Salt', 'High Fructose Corn Syrup', 'Palm Oil', 'Enriched Unbleached Flour', 'Apples']

In [13]: print(l3)
['Enriched Unbleached Flour', 'Palm Oil', 'High Fructose Corn Syrup', 'Salt', 'Eggs', 'Spices', 'Apples']

In [14]: print(l4)
['Apples', 'Enriched Unbleached Flour', 'Palm Oil', 'High Fructose Corn Syrup', 'Salt', 'Eggs', 'Spices', 'Ice Cream']

In [15]: js(l, l1)
Out[15]: 0.7142857142857143

In [16]: js(l, l2)
Out[16]: 0.5714285714285714

In [17]: js(l, l3)
Out[17]: 0.5

In [18]: js(l, l4)
Out[18]: 0.875

In [19]: js(l, ['Nutella'])
Out[19]: 0.0