[TOC]

机器学习之集体智慧编程(1):推荐物品

前言

集体智慧编程作为机器学习的经典入门书籍,很适合刚接触机器入门与数据分析的小伙伴,刚好最近正在学习集体智慧编程,所以记录一下学习过程与其中的知识点,加深自己的理解,也希望可以帮到更多的小伙伴

注意:

代码都是Python写的,如果有小伙伴对这个完全不了解又想学习的话,推荐先去看一下廖大的Python入门教程

在现代生活中,推荐系统与我们形影不离,无论是大型购物网站京东、淘宝、亚马逊还是良心音乐播放器网易云音乐等等，都常会根据人们的操作记录，给出相应的推荐。这样做的好处也显而易见，针对不用用户的喜好推荐不同的东西，更容易促进用户的消费或者增加用户的粘性。

后面我们会学习到如何根据用户的操作给他们推荐更适合他们的物品，并且附有可以练习的详细代码

黑喂狗！

搜集数据

首先，要对人做出分析，肯定需要想办法表达出此人的偏好。我们采用dict()字典作为数据的载体进行分析。

先新建一个包含了部分模拟数据的字典：

data = {
    '张三': {'乱世佳人': 3, '泰坦尼克号': 5, '功夫熊猫': 4.5, '小时代': 1, '爵迹': 0.4, '猩球崛起': 3.5},
    '李四': {'杀死比尔': 5, '超人': 4.5, '沉默的羔羊': 3, '功夫熊猫': 4, '小时代': 0.5, '爵迹': 5, '猩球崛起': 5},
    '王五': {'杀死比尔': 2, '超人': 1.5, '沉默的羔羊': 4, '功夫熊猫': 3.5, '让子弹飞': 4.5, '爵迹': 3, '猩球崛起': 4},
    '赵六': {'杀死比尔': 2, '超人': 5, '绣春刀': 2, '功夫熊猫': 3, '小时代': 0.5, '爵迹': 1, '猩球崛起': 3.5},
    '陈七': {'钢铁侠': 1, '超人': 3.5, '沉默的羔羊': 2.5, '功夫熊猫': 4.5, '小时代': 5, '爵迹': 4, '猩球崛起': 2},
}

数据中包含了五个电影观众以及其对部分影片的打分情况，我们做一个简单的列表，展示一下数据（由于篇幅限制，所以只能列举5部看得人多的电影）

ps：我没黑小四

虽然我们现在有了直观的数据，但是还是无法看出到底谁跟张三的品味比较像，为了可以。所以我们现在要找到确认两人相似性的方法，有很多种方法可以达到目的，我们选择的是欧几里得距离和皮尔逊相关度：

分析数据，寻找相近用户

欧几里得距离评价

计算近似度时一个非常简单的方法就是欧几里得距离，其实大家对欧几里得距离的内容是非常熟悉的，但是可能对这个名字比较陌生。

如果我们把欧几里得距离放在二维空间，就是大家耳熟能详的计算两点距离的公式：

所以计算n维空间中距离的公式为：
$\sqrt{(x1-x2)^2+(y1-y2)2+...+(z1-z2)^2}$
我们可以把每个电影当成一个坐标轴，把分数值当成在此维度的值，套入公式就可以得到两个人的区别度，这个值越大代表两个人差别越大，但是这样不利于我们分析人之间的相似度，所以我们把公式变形一下：
$\frac{1}{1+\sqrt{(x1-x2)^2+(y1-y2)2+...+(z1-z2)^2}}$
这样一来，我们计算出的结果就在0~1之间，并且值越大代表两个人相似性越高

在Python中，我们通过pow(x,n)来表示x的n次方，通过math函数中的sqrt来开根号，根据公式，我们可以得到如下代码：

import math
def sim_distance(pData, p1, p2):
    # 获取欧几里得距离
    #pData代表数据源，p1、p2代表两个人
    same_item = []
    for key in pData[p1]:
        # 只比较共同的项目
        if key in pData[p2]:
            same_item.append(key)

    if len(same_item) == 0:
        return 0

    sum_of_squares = sum(pow(pData[p1][item] - pData[p2][item], 2) for item in same_item)
    return 1 / (1 + math.sqrt(sum_of_squares))

现在我们可以通过此公式来计算两个人之间的相似度了：

print(sim_distance(data,'张三','李四'))
print(sim_distance(data,'张三','王五'))
print(sim_distance(data,'张三','赵六'))
print(sim_distance(data,'张三','陈七'))

运行结果:

0.16978547670707378
0.2610833580052755
0.3715878777036432
0.15182360441527204

这说明在我们的模拟数据中,赵六和张三的相似度最高

皮尔逊相关度评价

除了欧几里得距离,还有一种更复杂一点的方法来判断人之间的相似度,这就是皮尔逊相关系数,皮尔逊相关系数用于度量两个变量X和Y之间的相关（线性相关），其值介于-1与1之间,其中，1 表示变量完全正相关， 0 表示无关，-1 表示完全负相关。

公式:
$\frac{1}{n-1}\sum_{i=1}^{n}(\frac{xi-\bar x}{sx})(\frac{yi-\bar y}{sy})$
根据公式写出代码:

def sim_pearson(pData, p1, p2):
    # 求皮尔逊系数
    same_item = []
    #只计算共同项
    for key in pData[p1]:
        if key in pData[p2]:
            same_item.append(key)
    # 如果没有共同项,返回-1
    n = len(same_item)
    if n == 0:
        return -1
    # 求各自评分之和
    sum1 = sum(pData[p1][item] for item in same_item)
    sum2 = sum(pData[p2][item] for item in same_item)

    # 求各自平方和
    sum1Sq = sum(pow(pData[p1][item], 2) for item in same_item)
    sum2Sq = sum(pow(pData[p2][item], 2) for item in same_item)
    #求乘积之和
    pSum = sum(pData[p1][item] * pData[p2][item] for item in same_item)

    num = pSum - (sum1 * sum2 / n)
    den = math.sqrt(abs((sum1Sq - pow(sum1, 2) / n) * (sum2Sq - pow(sum2, 2) / n)))

    if den == 0: return 0

    return num / den

使用代码:

print(sim_pearson(data,'张三','李四'))
print(sim_pearson(data,'张三','王五'))
print(sim_pearson(data,'张三','赵六'))
print(sim_pearson(data,'张三','陈七'))

结果:

0.3118967974932389
0.7250594180737301
0.905203655171925
-0.3323774097784896

结果表明赵六和张三最相似

为评论者打分,找到最相似的

我们不可能每次都这样一个一个去比较,所以需要一个函数可以帮我们拿某个人和其他人进行比较并排序:

def top_matches(pData, p, n=5, similarity=sim_distance):
    # 获取数据源中某个key的相似数据并返回
    # 返回格式为[(相似度,key),(相似度,key2)...]
    total = [(similarity(pData, other, p), other) for other in pData if other != p]
    total.sort()
    total.reverse()
    return total[:n]

使用:

print(top_matches(data,'张三'))

结果:

[(0.3715878777036432, '赵六'), (0.2610833580052755, '王五'), (0.16978547670707378, '李四'), (0.15182360441527204, '陈七')]

我们也可以指定比较时使用sim_pearson函数:

print(top_matches(data,'张三',similarity=sim_pearson))

结果:

[(0.905203655171925, '赵六'), (0.7250594180737301, '王五'), (0.3118967974932389, '李四'), (-0.3323774097784896, '陈七')]

推荐物品

找到相似的人并不是我们的主要目的,我们的目的是看和他相似的人看过或者用过的东西里,哪些更适合推荐给他,我们当然可以找到和这个人最相近的人,然后从他没看过的影片里选一个评分最高的影片来推荐,但是这样做太随意了,有可能遇到某个比较热衷某部影片的人,我们需要更严谨的算法:

解释一下,上图中加权分数表示其他人对电影的评分乘以他与推荐人的相似度,即为加权分数,通过计算加权分数的总和以及权重的总和,然后用分数总和除以权重总和,即可得到更加科学的加权平均值,也就是预期的评分,评分越高,说明越值得看

根据上述理论,写出加权推荐物品的函数:

def getRecommendations(pData, p, n=10, similarity=sim_pearson):
    # 基于人的推荐
    # 加权平均数推荐
    totals = dict()
    simSums = dict()
    for other in pData:
        # 不跟自己比较
        if other == p: continue
        # 取得相似度
        sim = similarity(pData, p, other)
        # 忽略相似度<=0
        if sim <= 0: continue
        # 只看自己还未评价的
        for item in pData[other]:
            if item not in pData[p] or pData[p][item] == 0:
                totals.setdefault(item, 0)
                # 针对某项的加权分数
                totals[item] += sim * pData[other][item]
                # 权重之和
                simSums.setdefault(item, 0)
                simSums[item] += sim
    result = [(totals[item] / simSums[item], item) for item in totals]
    result.sort()
    result.reverse()
    return result[:n]

上面的代码遍历了其他人,查看与被比较人的相似度,如果为负,则略过此人,如果为正,只考虑他评价体系中被比较人还没看的,然后通过分数x权重,计算加权分数之和和权重之和,最后对所有条目计算加权平均值,取前n个数据展示

但是这种方法也存在弊端,对一个没有操作记录的新用户,我们是无法找到和他相近的人的,那应该怎么给他推荐物品呢?

所以我们应该获取一个以物品为中心的数据集:

def transformData(pData):
    # 转换人/物评分
    transData = dict()
    for item in pData:
        for k, v in pData[item].items():
            transData.setdefault(k, {})
            transData[k][item] = v
    return transData

通过这个方法,我们拿到了物品中人的评分,然后可以调用top_matches()来查看物品的相近物品

基于物品的过滤

上面提到过的过滤方法,都是以人对物品所打的分数为基础进行分析的,但是对于有大量商品的网站,要先计算出所有人的相似度再计算所有物品的加权分数,其速度可想而知,而且随着商品数量的增长,用户之间的相似度也会变得更低,判断难度也会增加,所以我们需要一个可以基于物品来进行过滤的算法

上述技术可以统称为基于用户的协作型过滤,接下来我们看一下基于物品的协作型过滤 ,其思路就是先计算出物品之间的相似度,然后推荐物品是找到与他相关的物品,计算加权后的分数排行,就可以了

实现每个条目和其他条目比较来此物品的相似物品:

def calculateSimItems(pData, n=10):
    # 获取所有物品最相近的n条数据评分

    simItem = dict()
    # 获取以物品为主的数据集
    itemData = transformData(pData)
    c = 0
    # 遍历每个物品,找到最相近的n个物品
    for item in itemData:
        c += 1
        simItem.setdefault(item, {})
        # 初步筛选出相似物品
        simItem[item] = top_matches(itemData, item, n)
        # 显示数据进度
        if c % 100 == 0: print('%s/%s' % (c, len(itemData)))

    return simItem

根据用户的情况进行推荐:

def getRecommendedItems(pData, simItems, user, n=10):
    # 基于物品的推荐
    # 获取用户推荐列表,pData是以用户为基础的数据源,simItems是所有物品的相似性表,user是查询用户,n是查询数据量

    scores = dict()
    total_sim = dict()
    # 获取用户打分情况
    userRating = pData[user]
    # 遍历获取用户打分过的物品
    for item in userRating:
        # 获取每个打分物品的相似物品,遍历之
        for sim_score, sim_item in simItems[item]:
            # 如果物品已经打过分,忽略
            if sim_item in userRating: continue
            # 获取打分物品的分数,求得相似物品的加权分数和
            scores.setdefault(sim_item, 0)
            scores[sim_item] += userRating[item] * sim_score
            #权重之和
            total_sim.setdefault(sim_item, 0)
            total_sim[sim_item] += sim_score
    # 取得数据集
    result = [(scores[item] / total_sim[item], item) for item in scores]
    result.sort()
    result.reverse()
    return result[:n]

为了验证我们的推荐算法,可以从网上找到真实的电影评分数据来检测,此处提供了一些真实的数据,[点我下载][http://pan.baidu.com/s/1cDD9cq] ,下载下来解压之后可以看到u.item和u.data两个文件,将其放在项目目录下,使用工具打开之后可以看到,u.item中数据格式:

电影编号     电影名
1|Toy Story (1995)|01-Jan-1995||......

前两项分别代表了电影编号和电影名

u.data数据格式:

评分人 电影编号 分数 时间
196 242 3   881250949
186 302 3   891717742
22  377 1   878887116

每一行依次是评分人,电影编号,分数,时间

有了以上数据,我们就可以测试自己的系统了!

载入数据:

def loadMovies():
    movies = dict()
    data = dict()
    with open('u.item', 'r') as f:
        for line in f:
            id, name = line.split('|')[0:2]
            movies.setdefault(id, '')
            movies[id] = name

    with open('u.data', 'r') as f:
        for line in f:
            user, movieid, rating, ts = line.split('\t')
            data.setdefault(user, {})
            if movieid in movies:
                data[user][movies[movieid]] = float(rating)
    return data

使用数据:

data=loadMovies()
itemSim = calculateSimItems(data, 20)
result = getRecommendedItems(pData=data, simItems=itemSim, user='87')
print(str(result))

运行结果:

100/1656
200/1656
...
[(5.0, "What's Eating Gilbert Grape (1993)"), (5.0, 'Vertigo (1958)'), (5.0, 'Usual Suspects, The (1995)'), (5.0, 'Toy Story (1995)'), (5.0, 'Titanic (1997)'), (5.0, 'Time to Kill, A (1996)'), (5.0, 'Temptress Moon (Feng Yue) (1996)'), (5.0, 'Substitute, The (1996)'), (5.0, 'Spice World (1997)'), (5.0, 'Rent-a-Kid (1995)')]

这样我们就拿到了最适合推荐给87号的电影名单

基于用户还是基于物品?

在针对大数据进行推荐时,明显基于物品的推荐比基于用户运算量小,速度快,但是有额外的维护数据的开销.同时,由数据'稀疏程度'不同带来的差异也会影响我们的选择,在电影的例子中,几乎每个评论者对每部电影都有评价,所以数据是'密集的',无论我们使用哪种方法,都有大量数据支持.但是如果我们要找书签/邮票等小众物品的评价,就很难基于人来分析了,因为数据集非常稀疏.

对于稀疏数据,基于物品的过滤通常更好,对于密集数据,则相差不大.而且,对于数据更替较快且数据较小的数据集,基于用户的过滤通常更好.而且有时候,告诉用户有哪些人和他很像也有一定得价值

刚开始记录,如果写的不好请见谅0.0

有问题请留言