数据挖掘
协同过滤
利用他人的喜好来进行推荐，也就是说，是大家一起产生的推荐。
工作原理：
如果要推荐一本书给你，我会在网站上查找一个和你类似的用户，然后将他喜欢的书籍推荐给你
曼哈顿距离
相当于三角形两边之和
公式
$$
d = |x_1 - x_2| + |y_1 - y_2|
$$
欧几里得距离
两点直线距离，相当于三角形第三边
利用勾股定理计算
公式
$$
d = \sqrt{(x_1 -x_2)^2 + (y_1 -y_2)^2}
$$
闵可夫斯基距离
将曼哈顿距离和欧几里得距离归纳成一个公式
公式
$$
d(x, y) = (\sum_{k=1}^n{|x_k - y_k|^r})^{\frac{1}{r}}
$$
其中
r = 1 曼哈顿距离
r = 2 欧几里得距离
$r = \infty$ 极大距离
r值越大,单个维度的差值大小会对整体距离有更大的影响
计算示例
1、二维模型
数据
点 | x | y
- | -| -
A | 5| 5
B | 2| 5
C | 1| 4
D | 4 | 2
曼哈顿距离
点 | 和D的距离计算 | 和D的距离
- | - | -
A | $|5-4| + |5-2| = 1 + 3 $ | 4
B | $|2-4| + |5-2| = 2 + 3 $ | 5
C | $|1-4| + |4-2| = 3 + 2 $ | 5
欧式距离
点 | 和D的距离计算 | 和D的距离
- | - | -
A | $\sqrt{(5-4)^2 + (5-2)^2} = \sqrt{1 + 9} = \sqrt{10}$ | 3.16
B | $\sqrt{(2-4)^2 + (5-2)^2} = \sqrt{4 + 9} = \sqrt{13}$ | 3.60
C | $\sqrt{(1-4)^2 + (4-2)^2} = \sqrt{9 + 4} = \sqrt{13}$ | 3.60
2、N维模型
我们在计算两个用户的距离时，只采用他们都评价过的项目
曼哈顿距离和欧几里得距离在数据完整的情况下效果最好
| 项目\评分 | A | B | Difference | $Difference^2$ |
|---|---|---|---|---|
| a | 3.5 | 2 | 1.5 | 2.25 |
| b | 2 | 3.5 | 1.5 | 2.25 |
| c | - | 4 | - | - |
| d | 4.5 | - | - | - |
| e | 5 | 2 | 3 | 9 |
| f | 1.5 | 3.5 | 2 | 4 |
| g | 2.5 | - | - | - |
| h | 2 | 3 | 1 | 1 |
| Manhattan Distance (曼哈顿) | 9 | |||
| sum of squares | 18.50 | |||
| Euclidean Distance (欧几里得) | 4.30 |
计算过程
$Euclidean = \sqrt{(3.5-2)^2 + (2-3.5)^2 + (5 -2)^2 + (1.5-3.5)^2 + (2-3)^2}$
$= \sqrt{1.5^2 + (-1.5)^2 + 3^2 + (-2)^2 + (-1)^2} $
$= \sqrt{2.25 + 2.25 + 9 + 4 + 1} $
$= \sqrt{18.5}$
$= 4.3$
Python代码实现
# -*- coding: utf-8 -*- # 用户数据，格式：[用户: {乐队: 评分}] users = { "Hailey": { "Broken Bells": 4, "Deadmau5": 1, "Norah Jones": 4, "The Strokes": 4, "Vampire Weekend": 1 }, "Jordyn": { "Broken Bells": 4.5, "Deadmau5": 4, "Norah Jones": 5, "Phoeni x": 5, "Slightly Stoopid": 4.5, "The Strokes": 4, "Vampire Weekend": 4 } } import math def manhattan(rating1, rating2): """ 曼哈顿距离 rating1和rating2参数中存储的数据格式均为 {'The Strokes': 3.0, 'Slightly Stoopid': 2.5} """ distance = 0 # 取key 的交集 keys = rating1.keys() & rating2.keys() for key in keys: distance += abs(rating1[key] - rating2[key]) return distance # print(manhattan(users["Hailey"], users["Jordyn"])) def euclidean(rating1, rating2): """ 欧几里得距离 rating1和rating2参数中存储的数据格式均为 {'The Strokes': 3.0, 'Slightly Stoopid': 2.5} """ distance = 0 # 取key 的交集 keys = rating1.keys() & rating2.keys() for key in keys: distance += math.pow(rating1[key] - rating2[key], 2) return math.sqrt(distance) # print(euclidean(users["Hailey"], users["Jordyn"])) def minkowski(rating1, rating2, r): """ 闵可夫斯基距离 r = 1 曼哈顿距离 r = 2 欧几里得距离 rating1和rating2参数中存储的数据格式均为 {'The Strokes': 3.0, 'Slightly Stoopid': 2.5} """ distance = 0 # 取key 的交集 keys = rating1.keys() & rating2.keys() for key in keys: distance += pow(abs(rating1[key] - rating2[key]), r) return pow(distance, 1 / r) # print(minkowski(users["Hailey"], users["Jordyn"], r=2)) def compute_near_neighbors(username, users): """计算所有用户至username用户的距离，倒序排列并返回结果列表""" distances = [] for user in users: if user != username: distance = manhattan(users[username], users[user]) distances.append((distance, user)) # 按距离排序——距离近的排在前面 distances.sort() return distances # print(compute_near_neighbors("Hailey", users)) def recommend(username, users): """返回推荐结果列表""" # 找到距离最近的用户 nearest = compute_near_neighbors(username, users)[0][1] recommendations = [] # 找出这位用户评价过、但自己未曾评价的乐队 neighborRatings = users[nearest] userRatings = users[username] for artist in neighborRatings: if artist not in userRatings: recommendations.append((artist, neighborRatings[artist])) # 按照评分进行高到低排序 return sorted(recommendations, key=lambda item: item[1], reverse=True) # print(recommend("Hailey", users))
皮尔逊相关系数
分数膨胀: 每个用户的打分标准非常不同
皮尔逊相关系数用于衡量两个变量之间的相关性
它的值在-1至1之间，1表示完全吻合，-1表示完全相悖。
皮尔逊相关系数的计算公式
$$
r = \frac{
\sum_{i=1}^n{
(x_i-\overline{x})(y_i-\overline{y})
}
}
{
\sqrt{\sum_{i=1}^n(x_i-\overline{x})^2}
\sqrt{\sum_{i=1}^n(y_i-\overline{y})^2}
}
$$
计算皮尔逊相关系数的近似值
$$
r = \frac{
\sum_{i=1}^nx_iy_i -
\frac{\sum_{i=1}^nx_i\sum_{i=1}^ny_i}{n}
}
{
\sqrt{\sum_{i=1}^nx_i^2 - \frac{(\sum_{i=1}^nx_i)^2}{n}}
\sqrt{\sum_{i=1}^ny_i^2 - \frac{(\sum_{i=1}^ny_i)^2}{n}}
}
$$
分解计算示例
@| a | b | c | d |e
-|-|-|-|-|-
A | 4.75 | 4.5 | 5 | 4.25 | 4
B | 4 | 3 | 5 | 2 | 1
第一步，计算分子
$\sum_{i=1}^nx_iy_i$
$=(4.75 \times 4) + (4.5 \times 3) + (5 \times 5) + (4.25 \times 2) + (4 \times 1)$
$= 19 + 13.5 + 25 + 8.5 + 4$
$=70$
$\frac{\sum_{i=1}^nx_i\sum_{i=1}^ny_i}{n}$
$=\frac{(4.75+4.5 +5 +4.25+4) \times ( 4 +3 +5 +2 + 1)}{5}$
$=\frac{22.50 \times 15}{5}$
$=\frac{337.5}{5}$
$=67.50$
所以，分子为
$\sum_{i=1}^nx_iy_i - \frac{\sum_{i=1}^nx_i\sum_{i=1}^ny_i}{n}$
$= 70 - 67.5$
$=2.5$
第二步，计算分母
先计算A
$\sum_{i=1}^nx_i^2$
$=4.75^2 + 4.5^2 + 5^2 + 4.25^2 + 4^2$
$=22.56 + 20.25 + 25 + 18.06 + 16$
$=101.874$
$\frac{(\sum_{i=1}^nx_i)^2}{n}$
$=\frac{(4.75 + 4.5 + 5 + 4.25 + 4)^2}{5}$
$=\frac{506.250}{5}$
$=101.250$
同样的方法计算B
$\sum_{i=1}^ny_i^2$
$= 4^2 + 3^2 + 5^2 + 2^2 + 1^2$
$=16 + 9 + 25 + 4 + 1$
$=55$
$\frac{(\sum_{i=1}^ny_i)^2}{n}$
$=\frac{(4 + 3+ 5+2+ 1)^2}{5}$
$=\frac{225}/{5}$
$=45$
所以，分母为
$\sqrt{\sum_{i=1}^nx_i^2 - \frac{(\sum_{i=1}^nx_i)^2}{n}}\sqrt{\sum_{i=1}^ny_i^2 - \frac{(\sum_{i=1}^ny_i)^2}{n}}$
$=\sqrt{101.874 - 101.250}\sqrt{55 - 45}$
$=\sqrt{0.62}\sqrt{10}$
$=0.789 \times 3.162$
$=2.494$
最后计算r
$r = \frac{2.5}{2.494}$
$= 1.002$
因此，A和B的偏好完全吻合
def pearson(rating1, rating2): """ 计算皮尔逊相关系数 """ sum_xy = 0 sum_x = 0 sum_y = 0 sum_x2 = 0 sum_y2 = 0 # 取key 的交集 keys = rating1.keys() & rating2.keys() n = len(keys) for key in keys: x = rating1[key] y = rating2[key] sum_xy += x * y sum_x += x sum_y += y sum_x2 += pow(x, 2) sum_y2 += pow(y, 2) # 计算分母 denominator = math.sqrt(sum_x2 - pow(sum_x, 2) / n) * math.sqrt(sum_y2 - pow(sum_y, 2) / n) if denominator == 0: return 0 else: # 计算分子 numerator = sum_xy - (sum_x * sum_y) / n return numerator / denominator # 计算上面示例 users = { "A": {"a": 4.75, "b": 4.5, "c": 5, "d": 4.25, "e": 4}, "B": {"a": 4, "b": 3, "c": 5, "d": 2, "e": 1} } print(pearson(users['A'], users['B'])) # 0.9999999999999998
余弦相似度
稀疏性问题
当非零值很稀少了，也就不能计算两项目之间的距离
余弦相似度的计算中会略过这些非零值
公式
$$
\cos(x, y) = \frac{x \centerdot y}{| x| \times |y|}
$$
其中，“·”号表示数量积。“||x||”表示向量x的模，计算公式是：
$$
\sqrt{\sum_{i=1}^nx_i{^2}}
$$
余弦相似度的范围从1到-1，1表示完全匹配，-1表示完全相悖
计算示例
项目 | a | b | c | d | e
-|-|-|-|-|-
A |4.75 |4.5|5 |4.25|4
B |4|3|5|2|1
两向量为
$x = (4.75, 4.5, 5, 4.25, 4)$
$y = (4, 3, 5, 2, 1)$
分子求数量积
$x \centerdot y = (4.75 \times 4) + (4.5 \times 3) + ( 5 \times 5 ) + (4.25 \times 2)+( 4 \times 1)$
$= 19 + 13.5 + 25 + 8.50 + 4$
$= 70$
分母求模：
$$| x |= \sqrt{4.75^2+4.5^2+ 5^2+ 4.25^2+ 4^2} = \sqrt{101.875} = 10.09$$
$$| y |= \sqrt{4^2+3^2+5^2+ 2^2+1^2} = \sqrt{55} = 7.416$$
余弦值
$$
\cos(x, y) = \frac{70}{10.09 \times 7.416} = \frac{70}{74.83} = 0.935
$$
如果数据存在“分数膨胀”问题，就使用皮尔逊相关系数。
如果数据比较“密集”，变量之间基本都存在公有值，且这些距离数据是非常重要的，那就使用欧几里得或曼哈顿距离。
如果数据是稀疏的，则使用余弦相似度。
解决稀疏数据问题（效果都不好）
1、人们给音乐打分是从1到5分，那些没有打分的项目就统一给0分
2、计算“平均值”——将两人共同评价过的歌曲分数除以歌曲数量
总之，曼哈顿距离和欧几里得距离在数据完整的情况下会运作得非常好，
如果数据比较稀疏，则要考虑使用余弦距离。
K最邻近算法
在协同过滤中可以使用K最邻近算法来找出K个最相似的用户
只依靠最相似的 一个 用户来做推荐，如果这个用户有些特殊的偏好，就会直接反映在推荐内容里。
解决方法之一是找寻多个相似的用户，这里就要用到K最邻近算法了。
例如：K=3
Person | 皮尔逊相关系数 | 影响值 |项目评分| 加权评分
- | -| -|-|-
A | 0.8 | 40% | 3.5 | 1.40
B | 0.7 | 35% |5 | 1.75
C | 0.5 | 25% |4.5 |1.125
汇总 | | | | 4.275
计算贡献比重
$ total = 0.8 + 0.7 + 0.5 = 2.0 $
$ influence_A = 0.8 / 2 = 40\% $
$ influence_B = 0.7 / 2 = 35\% $
$ influence_C = 0.5 / 2 = 25\% $
计算加权评分
$rating = (3.5 \times 40\%) + (5 \times 35\%)+ (4.5 \times 25\%)$
$=1.40+ 1.75 + 1.125 $
$=4.275$