数据挖掘之协同过滤

写在前面

这部分数据挖掘的学习是用的《写给程序员的数据挖掘指南》这本书。精简摘录里面的关键学习内容，同时自己动手实现一些代码。详情还是请看原版书籍。

原版书籍地址

协同过滤——爱你所爱

从淘宝的商品推荐到网易云音乐的日常推送，推荐系统无处不在。
本次讨论的推荐算法是协同过滤（collaborative filtering）。其中，“协同”是指：该方法是基于其他用户进行推荐的。实际上，部分推荐系统是通过协同合作来完成推荐。其工作流程为：假设要完成的任务是推荐一首音乐给你。系统会在数据库中搜索与你兴趣相似的其他用户。一旦找到一位或几位用户，就把他们喜欢的音乐推荐给你。

寻找相似用户

曼哈顿距离（Manhattan Distance）

假设用户A的坐标为（x1,y1）,用户B的坐标为（x2,y2）.两者的曼哈顿距离如下

$\vert x_1 - x_2\vert + \vert y_1 - y_2\vert$

欧式距离

就是勾股定理

$\sqrt{(x_1 - x_2)^2} + \sqrt{(y_1 - y_2)^2}$

明氏距离（Minkowski Distance）

是对上述两种距离的一般化，公式如下：

$d(x,y)=(\sum_{k=1}^n \vert x_k - y_k \vert^r)^\frac{1}{r}$

其中，当r=1时，上式计算的就是曼哈顿距离。
当r=2时，上式计算的就是欧氏距离。
当r趋于无穷时，上式计算的就是上确界距离。
我们可以看到，r越大，某一维度上的较大差异对最终差值的影响也越大。

Python代码实现

users = {"Angelica": {"Blues Traveler": 3.5, "Broken Bells": 2.0, "Norah Jones": 4.5, "Phoenix": 5.0, "Slightly Stoopid": 1.5, "The Strokes": 2.5, "Vampire Weekend": 2.0},
         "Bill":{"Blues Traveler": 2.0, "Broken Bells": 3.5, "Deadmau5": 4.0, "Phoenix": 2.0, "Slightly Stoopid": 3.5, "Vampire Weekend": 3.0},
         "Chan": {"Blues Traveler": 5.0, "Broken Bells": 1.0, "Deadmau5": 1.0, "Norah Jones": 3.0, "Phoenix": 5, "Slightly Stoopid": 1.0},
         "Dan": {"Blues Traveler": 3.0, "Broken Bells": 4.0, "Deadmau5": 4.5, "Phoenix": 3.0, "Slightly Stoopid": 4.5, "The Strokes": 4.0, "Vampire Weekend": 2.0},
         "Hailey": {"Broken Bells": 4.0, "Deadmau5": 1.0, "Norah Jones": 4.0, "The Strokes": 4.0, "Vampire Weekend": 1.0},
         "Jordyn":  {"Broken Bells": 4.5, "Deadmau5": 4.0, "Norah Jones": 5.0, "Phoenix": 5.0, "Slightly Stoopid": 4.5, "The Strokes": 4.0, "Vampire Weekend": 4.0},
         "Sam": {"Blues Traveler": 5.0, "Broken Bells": 2.0, "Norah Jones": 3.0, "Phoenix": 5.0, "Slightly Stoopid": 4.0, "The Strokes": 5.0},
         "Veronica": {"Blues Traveler": 3.0, "Norah Jones": 5.0, "Phoenix": 4.0, "Slightly Stoopid": 2.5, "The Strokes": 3.0}
        }


def minkowski(rating1, rating2, r):
    distance = 0
    commonRatings = False
    for key in rating1:
        if key in rating2:
            distance += pow(abs(rating1[key] - rating2[key]), r)
            commonRatings = True
    if commonRatings:
        return pow(distance, 1/r)
    else:
        return 0
    
def manhattan(rating1, rating2):
    return minkowski(rating1, rating2, 1)

def computeNearestNeighbor(username, users):
    distances = []
    for user in users:
        if user != username:
            distance = manhattan(users[user], users[username])
            distances.append((distance, user))
    distances.sort()
    return distances

def recommend(username, users):
    nearest = computeNearestNeighbor(username, users)[0][1]
    recommendations = []
    neighborRatings = users[nearest]
    userRatings = users[username]
    for artist in neighborRatings:
        if not artist in userRatings:
            recommendations.append((artist, neighborRatings[artist]))
    return sorted(recommendations, key=lambda artistTuple: artistTuple[1], reverse = True)

print(recommend('Hailey', users))

用户评级差异

在上面的Python代码中，users的不同用户对音乐评级的行为差异很大。
比如：Bill的评级分布在2-4之间；而Hailey的评级只有1和4两种。
这为推荐系统带来了很大的问题。

皮尔逊相关系数（Pearson Correlation Coefficient）

	Blues Traveler	Norah Jones	Phoenix	The Strokes	Weired AI
Clara	4.75	4.5	5	4.25	4
Robert	4	3	5	2	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}^n x_iy_i - \frac{\sum_{i=1}^n x_i \sum_{i=1}^n y_i}{n}}{\sqrt{\sum_{i=1}^n x_i^2 - \frac{(\sum_{i=1}^n x_i)^2}{n}} \sqrt{\sum_{i=1}^n y_i^2 - \frac{(\sum_{i=1}^n y_i)^2}{n}}}$

Python代码实现

def pearson(rating1, rating2):
    sum_xy = 0
    sum_x = 0
    sum_y = 0
    sum_x2 = 0
    sum_y2 = 0
    n = 0
    for key in rating1:
        if key in rating2:
            n += 1
            x = rating1[key]
            y = rating2[key]
            sum_xy += x * y
            sum_x += x
            sum_y += y
            sum_x2 += x**2
            sum_y2 += y**2
    denominator = sqrt(sum_x2 - (sum_x**2) / n) * \
                  sqrt(sum_y2 - (sum_y**2) / n)
    if denominator == 0:
        return 0
    else:
        return (sum_xy - (sum_x * sum_y) / n)/ denominator

余弦相似度

该公式不仅在文本挖掘中使用的非常普遍，而且广泛用于协同过滤。
两用户的播放歌曲的次数大部分为0，造成用户的数据是稀疏的。而我们在计算相似度时不希望使用这些公共的0.
计算公式如下：

$cos(x,y)=\frac{x \cdot y}{\|x\| \times \|y\|}$

其中

$\|x\| = \sqrt{\sum_{i=1}^n x_i^2}$

$x \cdot y = \sum_{i=1}^n x_i y_i$

Python代码实现

def cosinesimilar(rating1, rating2):
    sum_x2 = 0
    sum_y2 = 0
    sum_xy = 0
    for key in rating1:
        sum_x2 += rating1[key]**2
        if key in rating2:
            sum_xy += rating1[key] * rating2[key]
    sum_y2 = sum([v**2 for i,v in rating2.items()])
    return sum_xy / (sqrt(sum_x2) * sqrt(sum_y2))

相似度的选择

若数据受到分数贬值(grade-inflation,即不同用户使用不同的评级范围)的影响，则使用皮尔逊相关系数。
若数据稠密(几乎所有属性都没有零值)且属性值大小十分重要，那么，使用欧式距离或曼哈顿距离。
若数据稀疏，考虑使用余弦相似度。

K近邻

如果在推荐时，我们仅仅使用一位最接近用户的信息进行近似推荐，可能会出现问题。
为此，我们采用基于最接近的k位用户来进行推荐。

基于皮尔逊系数得到最接近的k位用户。
将系数归一化，得到他们各自占的比重。
基于上面的比重，得到某一维的数据投影数值