机器学习笔记1：欧几里得距离和皮尔逊相关度

Posted on
这段时间打算深入学习一下机器学习的常用基本算法，包括弄明白这些算法的原理等。笔记主要总结这些算法。本文内容主要关于书中第二章『提供推荐』的两个基本概念，欧几里得距离和皮尔逊相关度及实现。

概述

这段时间打算学习一下机器学习的常用基本算法，包括弄明白这些算法的原理等。笔记主要总结这些算法。本文内容主要关于书中第二章『提供推荐』的两个基本概念，欧几里得距离和皮尔逊相关度及实现。

背景

假设我们有一些用户对电影的评价数据如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
# test data
# 格式如下
# critics = {
#     '用户': {
#         '电影名': 分数值,
#         ...
#     },
#     ...
# }
critics = {
    'Lisa Rose': {
        'Lady in the Water': 2.5,
        'Snakes on a Plane': 3.5,
        'Just My Luck': 3.0,
        'Superman Returns': 3.5,
        'You, Me and Dupree': 2.5,
        'The Night Listener': 3.0
    },
    'Gene Seymour': {
        'Lady in the Water': 3.0,
        'Snakes on a Plane': 3.5,
        'Just My Luck': 1.5,
        'Superman Returns': 5.0,
        'The Night Listener': 3.0,
        'You, Me and Dupree': 3.5
    },
    'Michael Phillips': {
        'Lady in the Water': 2.5,
        'Snakes on a Plane': 3.0,
        'Superman Returns': 3.5,
        'The Night Listener': 4.0
    },
    'Claudia Puig': {
        'Snakes on a Plane': 3.5,
        'Just My Luck': 3.0,
        'The Night Listener': 4.5,
        'Superman Returns': 4.0,
        'You, Me and Dupree': 2.5
    },
    'Mick LaSalle': {
        'Lady in the Water': 3.0,
        'Snakes on a Plane': 4.0,
        'Just My Luck': 2.0,
        'Superman Returns': 3.0,
        'The Night Listener': 3.0,
        'You, Me and Dupree': 2.0
    },
    'Jack Mattews': {
        'Lady in the Water': 3.0,
        'Snakes on a Plane': 4.0,
        'The Night Listener': 3.0,
        'Superman Returns': 5.0,
        'You, Me and Dupree': 3.5
    },
    'Toby': {
        'Snakes on a Plane': 4.5,
        'You, Me and Dupree': 1.0,
        'Superman Returns': 4.0
    }
}

上述Python嵌套字典存储了我们需要的数据（保存为recommendations.py），接下来我们以这些数据来学习计算相似度评价值。

欧几里得距离

欧几里得距离评价（Euclidean Distance Score）是计算相似度评价值的一个非常简单的方法。欧氏距离是在欧氏空间中两点的距离值，欧几里得距离评价即经过适当处理后的值（欧氏距离加1后取倒数），两点之间的距离越近，其欧几里得距离评价越高，取值范围为[0,1]。其Python的实现如下所示（添加到recommendations.py中）。

1
2
3
4
5
6
7
8
9
10
11
from math import sqrt
# Euclidean Distance Score
def sim_distance(prefs, person1, person2):
    si = {}
    for item in prefs[person1]:
        if item in prefs[person2]:
            si[item] = 1
    if len(si) == 0: return 0
    sum_of_squares = sum(pow(prefs[person1][item] - prefs[person2][item], 2)
        for item in prefs[person1] if item in prefs[person2])
    return 1 / (1 + sqrt(sum_of_squares))

上面的sim_distance函数共有3个参数，分别是偏好数据（就是我们的示例数据字典），用户1，和用户2。该函数根据偏好数据来计算用户1和用户2的欧几里得距离评价。

1
2
3
from recommendations import *
sim_distance(critics, 'Lisa Rose', 'Gene Seymour')
# 输出结果为0.294298055086

注意sim_distance函数中的最后一行，我们把求到的欧氏距离加1后取倒数，这是为了能让我们队偏好相近的情况给出越大的值。所以这里给欧氏距离加1厚去倒数（加1是为了防止被零整除的错误）。

皮尔逊相关度

皮尔逊相关度（Pearson Correlation Score）相对于欧几里得距离而言稍微复杂一些，该相关系数是判断两组数据与某一直线的拟合程度的一种度量。

皮尔逊相关度对『夸大分值（grade inflation）』进行了修正。示例数据中，Jack Matthews总是比Lisa Rose给出的分值更高，但最终的直线仍然是拟合的，这是因为他们两者有着近似的偏好。如果某人总是倾向于给出比另一个人更高的分值，而二者的分值之差又始终保持一致，则他们依然可能会存在很好的相关性。欧几里得距离评价会因为一个人的评价比另一个人更严格，而得出评价始终相对偏低的结论（并不说这样是错的，根据具体的应用场景不同而不同）。

皮尔逊相关度算法的具体Python实现如下所示（添加到recommendations.py中）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Pearson Correlation Score
def sim_pearson(prefs, person1, person2):
    si = {}
    for item in prefs[person1]:
        if item in prefs[person2]:
            si[item] = 1
    n = len(si)
    if n == 0:
        return 1
    sum1 = sum([prefs[person1][item] for item in si])
    sum2 = sum([prefs[person2][item] for item in si])
    sum1Sq = sum([pow(prefs[person1][item], 2) for item in si])
    sum2Sq = sum([pow(prefs[person2][item], 2) for item in si])
    pSum = sum([prefs[person1][item] * prefs[person2][item] for item in si])
    num = pSum - (sum1 * sum2 / n)
    den = sqrt((sum1Sq - pow(sum1, 2) / n) * (sum2Sq - pow(sum2, 2) / n))
    if den == 0:
        return 0
    r = num / den
    return r

sim_pearson函数的三个参数与意义相同，但函数的值域在[-1,1]之间。值为1表示两个人对每一样物品均有完全一致的评价，值为-1表示两人对每一样物品均有截然相反的评价，值为0表示两人无相关性。

1
2
3
from recommendations import *
sim_pearson(critics, 'Lisa Rose', 'Gene Seymour')
# 输出结果为0.396059017191

为评论者打分

我们现在已经能对两个人进行比较了，为了找出对用户而言最合适的评论者，我们可以编写函数然后排序来找到结果，代码如下（添加到recommendations.py中）。

1
2
3
4
5
def topMatches(prefs, person, n = 5, similarity = sim_pearson):
    scores = [(similarity(prefs, person, other), other) for other in prefs if other != person]
    scores.sort()
    scores.reverse()
    return scores[0 : n]

topMatches函数一共四个参数，分别是偏好数据，目标用户，取排序的前几名，相似度算法的选取。其中默认取排序的前5名，相似度算法默认用皮尔逊相关度。

1
2
3
4
5
6
from recommendations import *
topMatches(critics, 'Toby', n = 3, similarity = sim_pearson)
# 输出结果如下
[(0.9912407071619299, 'Lisa Rose'),
(0.9244734516419049, 'Mick LaSalle'),
(0.8934051474415647, 'Claudia Puig')]

根据结果可知，Toby应该阅读Lisa Rose撰写的影评，因为她的评委与Toby很相近。

推荐物品

很多时候我们需要的不是去看别人的影评，而是希望得到一份电影的推荐列表。问题是，如果Toby只看Lisa Rose撰写的影评，可能会有一些特殊情况，比如Lisa偏好有些古怪，她特别喜欢某部电影，而该电影在其他影评人那里口碑都很差；又或者Lisa有些电影没看到，而这些电影恰恰就是Toby喜欢看的电影。

为了解决这个问题，我们需要对影片的评分加权值，将权值乘以评分后，再除以权值的和。简单地说就是类似于取评分的数学期望，注意这里的评分是不均匀的。下表给出了具体的执行过程。

评论者 相似度 Night S.xNight Lady S.xLady Luck S.xLuck
Rose 0.99 3.0 2.97 2.5 2.48 3.0 2.97
Seymour 0.38 3.0 1.14 3.0 1.14 1.5 0.57
Puig 0.89 4.5 4.02 3.0 2.68
LaSalle 0.92 3.0 2.77 3.0 2.77 2.0 1.85
Matthews 0.66 3.0 1.99 3.0 1.99
总计 12.89 8.38 8.07
Sim.Sum 3.84 2.95 3.18
总计/Sim.Sum 3.35 2.83 2.53

算法的具体Python实现如下所示（添加到recommendations.py中）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Recommendations
def getRecommendations(prefs, person, similarity = sim_pearson):
    totals = {}
    simSums = {}
    for other in prefs:
        if person == other:
            continue
        sim = similarity(prefs, person, other)
        if sim <= 0 :
            continue
        for item in prefs[other]:
            if item not in prefs[person] or prefs[person][item] == 0:
                totals.setdefault(item, 0)
                totals[item] += prefs[other][item] * sim
                simSums.setdefault(item, 0)
                simSums[item] += sim
    rankings = [(total / simSums[item], item) for item, total in totals.items()]
    rankings.sort()
    rankings.reverse()
    return rankings

使用欧几里得距离评价测试如下。

1
2
3
4
5
6
7
8
from recommendations import *
rankings = getRecommendations(critics, 'Toby', similarity = sim_distance)
for ranking in rankings:
    print(ranking)
# 输出结果如下
# (3.4571286944914226, 'The Night Listener')
# (2.7785840038149234, 'Lady in the Water')
# (2.422482042361917, 'Just My Luck')

使用皮尔逊相关系数评价测试如下。

1
2
3
4
5
6
7
8
from recommendations import *
rankings = getRecommendations(critics, 'Toby', similarity = sim_pearson)
for ranking in rankings:
    print(ranking)
# 输出结果如下
# (3.3477895267131013, 'The Night Listener')
# (2.832549918264162, 'Lady in the Water')
# (2.5309807037655645, 'Just My Luck')

以上，我们根据不同的使用相似度评价值算法，得到了Toby的影片推荐列表，可以看出在本例中，二者的并没有质的区别。

最后我们还可以对数据先进行转置，然后再调用topMatches函数，我们可以得到和指定某部电影近似的其他电影，具体过程这里不再赘述。

参考

  1. 集体智慧编程 - Toby Segaran - 亚马逊中国
  2. Euclidean distance - Wikipedia
  3. Pearson product-moment correlation coefficient - Wikipedia