协同过滤原理与Mahout实现

问题导读：

1.协同过滤原理？
2.如何使用Mahout Taste?
3.如何在集群中实现？





协同过滤

分析用户兴趣，在用户群中找到指定用户的相似（兴趣）用户，综合这些相似用户对某一信息的评价，形成系统对该指定用户对此信息的喜好程度预测。

测试数据

user&item	item1	item2	item3	item4	item5	item6
user1	2.5	3.5	3.0	3.5	2.5	3.0
user2	3.0	3.5	1.5	5.0	3.5	3.0
user3	2.5	3.0	0.0	3.5	0.0	4.0
user4	0.0	3.5	3.0	4.0	2.5	4.5
user5	3.0	4.0	2.0	3.0	2.0	3.0
user6	3.0	4.0	0.0	5.0	3.5	3.0
user7	0.0	4.5	0.0	4.0	1.0	0.0

这里列举了七个用户对六个物品的偏好信息, 其中无偏好统一设置为0.0

critics =
    {'user1':{'item1':2.5, 'item2':3.5, 'item3':3.0, 'item4':3.5, 'item5':2.5, 'item6':3.0},
     'user2':{'item1':3.0, 'item2':3.5, 'item3':1.5, 'item4':5.0, 'item5':3.5, 'item6':3.0},
     'user3':{'item1':2.5, 'item2':3.0, 'item4':3.5, 'item6':4.0},
     'user4':{'item2':3.5, 'item3':3.0, 'item4':4.0, 'item5':2.5, 'item6':4.5},
     'user5':{'item1':3.0, 'item2':4.0, 'item3':2.0, 'item4':3.0, 'item5':2.0, 'item6':3.0},
     'user6':{'item1':3.0, 'item2':4.0, 'item4':5.0, 'item5':3.5, 'item6':3.0},
     'user7':{'item2':4.5, 'item4':4.0, 'item5':1.0}}
复制代码

定义相似度

根据抽象的距离算法获得两个用户的距离大小, 并以此作为用户相似程度的依据。

欧几里得距离

最常见的距离算法, 最简单的情形即为二维空间内两个点间的距离公式

代码实现在某个维度上两者都有偏好才进行累加

# 返回一个有关person1与person2的基于距离的相似度评价
def sim_distance(prefs, person1, person2):
    # 得到shared item的列表
    si = {}
    for item in prefs[person1]:
        if item in prefs[person2]:
            si[item] = 1
    # 如果两者没有共同之处, 则返回0
    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))
复制代码

效果验证

>>> import recommendations as recmd
>>> recmd.sim_distance(critics, 'user1', 'user2')
0.29429805508554946
>>> recmd.sim_distance(critics, 'user1', 'user6')
0.4721359549995794
复制代码

皮尔逊距离

代码实现

# 返回p1和p2的皮尔逊相关系数
def sim_pearson(prefs, p1, p2):
    # 得到双方都曾评价过的物品列表
    si = {}
    for item in prefs[p1]:
        if item in prefs[p2]:
            si[item] = 1

    # 得到列表元素的个数
    n = len(si)

    # 如果两者没有共同之处, 则返回1
    if n == 0:
        return 1

    # 对所有偏好求和
    sum1 = sum([prefs[p1][it] for it in si])
    sum2 = sum([prefs[p2][it] for it in si])

    # 求平方和
    sum1Sq = sum([pow(prefs[p1][it], 2) for it in si])
    sum2Sq = sum([pow(prefs[p2][it], 2) for it in si])

    # 求乘积之和
    pSum = sum([prefs[p1][it]*prefs[p2][it] for it 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
复制代码

效果验证

>>> recmd.sim_pearson(critics, 'user1', 'user2')
0.39605901719066977
>>> recmd.sim_pearson(critics, 'user1', 'user6')
0.40451991747794525
复制代码

打分排序

根据指定的相似度算法为指定的用户计算其他用户的分值, 排序后返回TopN

代码实现

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]
复制代码

效果验证

>>> recmd.topMatches(critics, 'user7', n=3)
[(0.9912407071619299, 'user1'), (0.9244734516419049, 'user3'), (0.8934051474415647, 'user4')]
复制代码

定义邻居


数量固定: 即只取距离上最接近的 K 个邻居
范围固定: 即只取距离在阀值范围之内的邻居

基于用户推荐

基于用户对物品的偏好找到邻居用户，然后将邻居用户喜欢的推荐给当前用户。计算上，就是将一个用户对所有物品的偏好作为一个向量来计算用户之间的相似度，找到 K 邻居后，根据邻居的相似度权重以及他们对物品的偏好，预测当前用户没有偏好的未涉及物品，计算得到一个排序的物品列表作为推荐。

对于用户 A，根据用户的历史偏好，这里只计算得到一个邻居 - 用户 C，然后将用户 C 喜欢的物品 D 推荐给用户 A。

分值修正

对于某一个item, 可能最相似的用户还没有对其评分; 也可能不相似的用户给了一个较高的评分, 因此需要对分值进行修正以得到一个合理的评分。
评分= Σ相似度*评分/N

代码实现

# 利用所有他人评价值的加权平均, 为某人提供建议
def getRecommendations(prefs, person, similarity=sim_pearson):
    totals = {}
    simSums = {}
    for other in prefs:
        # 不用和当前用户做比较
        if other == person:
            continue
        sim = similarity(prefs, person, other)

        # 忽略评价值为零或小于零的情况
        if sim <= 0:
            continue
        for item in prefs[other]:
            # 只对当前用户评分为0的物品进行评分预估
            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
复制代码

效果验证

>>> recmd.getRecommendations(critics, 'user7')
[(3.3477895267131013, 'item6'), (2.832549918264162, 'item1'), (2.5309807037655645, 'item3')]
复制代码

为物品匹配用户

做一个矩阵转置即可

def transformPrefs(prefs):
    result = {}
    for person in prefs:
        for item in prefs[person]:
            result.setdefault(item, {})

            # 将物品和人员对调
            result[item][person] = prefs[person][item]
    return result
复制代码

效果验证

>>> recmd.topMatches(newCritics, 'item4', n=3)
[(0.6579516949597695, 'item5'), (0.4879500364742689, 'item1'), (0.11180339887498941, 'item2')]
>>> recmd.getRecommendations(newCritics, 'item3')
[(4.0, 'user6'), (3.0, 'user5')]
复制代码

基于物品推荐

基于物品的 CF 的原理和基于用户的 CF 类似，只是在计算邻居时采用物品本身，而不是从用户的角度，即基于用户对物品的偏好找到相似的物品，然后根据用户的历史偏好，推荐相似的物品给他。从计算的角度看，就是将所有用户对某个物品的偏好作为一个向量来计算物品之间的相似度，得到物品的相似物品后，根据用户历史的偏好预测当前用户还没有表示偏好的物品，计算得到一个排序的物品列表作为推荐。

对于物品 A，根据所有用户的历史偏好，喜欢物品 A 的用户都喜欢物品 C，得出物品 A 和物品 C 比较相似，而用户 C 喜欢物品 A，那么可以推断出用户 C 可能也喜欢物品 C。 因为物品的变化并不频繁, 因此可以将大量计算放在线下执行, 从而可以更快的得到推荐结果。

数据预处理

def calculateSimilarItems(prefs, n=10):
    # 建立字典, 以给出与这些物品最为相近的所有其它物品
    result = {}

    # 以物品为中心对偏好矩阵实施倒置处理
    itemPrefs = transformPrefs(prefs)
    c = 0
    for item in itemPrefs:
        # 针对大数据集更新状态变量
        c += 1
        if c%100 == 0:
            print "%d / %d" % (c, len(itemPrefs))

        # 寻找最为相近的物品
        scores = topMatches(itemPrefs, item, n=n, similarity=sim_distance)
        result[item] = scores
    return result
复制代码

获得推荐

def getRecommendedItems(prefs, itemMatch, user):
    userRatings = prefs[user]
    scores = {}
    totalSim = {}

    # 循环遍历由当前用户评分的物品
    for (item, rating) in userRatings.items():
        # 循环遍历与当前物品相近的物品
        for (similarity, item2) in itemMatch[item]:
            # 如果该用户已经对当前物品做过评价, 则将其忽略
            if item2 in userRatings:
                continue
            # 评价值与相似度的加权之和
            scores.setdefault(item2, 0)
            scores[item2] += similarity * rating

            # 全部相似度之和
            totalSim.setdefault(item2, 0)
            totalSim[item2] += similarity

        # 将每个合计值除以加权和, 求出评价值
        rankings = [(score/totalSim[item], item) for item, score in scores.items()]
        # 按最高值到最低值的顺序, 返回评分结果
        rankings.sort()
        rankings.reverse()
        return rankings
复制代码

效果验证

>>> itemsim = recmd.calculateSimilarItems(critics)
>>> itemsim['item1']
[(0.4494897427831781, 'item5'), (0.38742588672279304, 'item6'), (0.3483314773547883, 'item3'), (0.3483314773547883, 'item2'), (0.2402530733520421, 'item4')]
>>> recmd.getRecommendedItems(critics, itemsim, 'user7')
[(4.5, 'item6'), (4.5, 'item3'), (4.5, 'item1')]
复制代码

测试数据集

电影评分数据
这个测试数据集的文本格式如下

# movies.dat
# 电影编号::电影名::电影类别
MovieID::Title::Genres

# users.dat
# 用户编号::性别::年龄::职业::Zip-code
UserID::Gender::Age::Occupation::Zip-code

# ratings.dat
# 用户编号::电影编号::电影评分::时间戳
UserID::MovieID::Rating::Timestamp
复制代码

加载数据

def loadMovieLens(path='ml-1m/'):
    # 获取影片标题
    movies = {}
    for line in open(path + 'movies.dat'):
        (id, title) = line.split('::')[0:2]
        movies[id] = title

    # 加载数据
    prefs = {}
    for line in open(path + 'ratings.dat'):
        (user, movieid, rating, ts) = line.split('::')
        prefs.setdefault(user, {})
        prefs[user][movies[movieid]] = float(rating)

    return prefs
复制代码

运行测试

# 加载数据 
>>> prefs = recmd.loadMovieLens()
>>> prefs['87']

# 基于用户的推荐
>>> recmd.getRecommendations(prefs, '87')[0:10]
[(5.0, 'Tigrero: A Film That Was Never Made (1994)'),
 (5.0, 'Smashing Time (1967)'),
 (5.0, 'Schlafes Bruder (Brother of Sleep) (1995)'),
 (5.0, 'Return with Honor (1998)'),
 (5.0, 'Lured (1947)'),
 (5.0, 'Identification of a Woman (Identificazione di una donna) (1982)'),
 (5.0, 'I Am Cuba (Soy Cuba/Ya Kuba) (1964)'),
 (5.0, 'Hour of the Pig, The (1993)'),
 (5.0, 'Gay Deceivers, The (1969)'),
 (5.0, 'Gate of Heavenly Peace, The (1995)')]

# 基于物品的推荐
>>> itemsim = recmd.calculateSimilarItems(prefs, n=50)
100 / 3706
200 / 3706
300 / 3706
......
>>> recmd.getRecommendedItems(prefs, itemsim, '87')[0:10]
[(1.0, 'Zeus and Roxanne (1997)'),
 (1.0, 'Zachariah (1971)'),
 (1.0, 'Young Doctors in Love (1982)'),
 (1.0, 'Year of the Horse (1997)'),
 (1.0, 'Yankee Zulu (1994)'),
 (1.0, 'Wrongfully Accused (1998)'),
 (1.0, 'Wooden Man's Bride, The (Wu Kui) (1994)'),
 (1.0, 'Woo (1998)'), (1.0, 'Wolf Man, The (1941)'),
 (1.0, 'With Byrd at the South Pole (1930)')]
复制代码

使用Mahout Taste

Taste是Apache Mahout提供的一个协同过滤算法的高效实现，它是一个基于Java实现的可扩展的，高效的推荐引擎。Taste既实现了最基本的基于用户的和基于内容的推荐算法，同时也提供了扩展接口，使用户可以方便的定义和实现自己的推荐算法。同时，Taste不仅仅只适用于Java应用程序，它可以作为内部服务器的一个组件以HTTP和Web Service的形式向外界提供推荐的逻辑。Taste的设计使它能满足企业对推荐引擎在性能、灵活性和可扩展性等方面的要求。

• DataModel
  

DataModel 是用户喜好信息的抽象接口，它的具体实现支持从任意类型的数据源抽取用户喜好信息。Taste 默认提供 JDBCDataModel 和 FileDataModel，分别支持从数据库和文件中读取用户的喜好信息。

• UserSimilarity 和ItemSimilarity
  

UserSimilarity 用于定义两个用户间的相似度，它是基于协同过滤的推荐引擎的核心部分，可以用来计算用户的“邻居”，这里我们将与当前用户口味相似的用户称为他的邻居。ItemSimilarity 类似的，计算内容之间的相似度。

• UserNeighborhood
  

用于基于用户相似度的推荐方法中，推荐的内容是基于找到与当前用户喜好相似的邻居用户的方式产生的。UserNeighborhood 定义了确定邻居用户的方法，具体实现一般是基于 UserSimilarity计算得到的。

• Recommender
  

Recommender 是推荐引擎的抽象接口，Taste 中的核心组件。程序中，为它提供一个 DataModel，它可以计算出对不同用户的推荐内容。实际应用中，主要使用它的实现类 GenericUserBasedRecommender 或者 GenericItemBasedRecommender，分别实现基于用户相似度的推荐引擎或者基于内容的推荐引擎。

基于用户的推荐

public static void tasteUserCF() throws IOException, TasteException {
    // 1. 选择数据源
    // 数据源格式为UserID,MovieID,Ratings
    // 使用文件型数据接口
    String path = "data/ratings.data";
    DataModel model = new FileDataModel(new File(path));

    // 2. 实现相似度算法
    // PearsonCorrelationSimilarity: 是基于皮尔逊相关系数计算相似度
    // EuclideanDistanceSimilarity：基于欧几里德距离计算相似度
    // TanimotoCoefficientSimilarity：基于 Tanimoto 系数计算相似度
    // UncerteredCosineSimilarity：计算 Cosine 相似度
    UserSimilarity similarity = new EuclideanDistanceSimilarity(model);
    // 可选项
    // 为用户相似度设置相似度推理方法
    similarity.setPreferenceInferrer(new AveragingPreferenceInferrer(model));

    // 3. 选择邻居用户
    // 使用NearestNUserNeighborhood实现UserNeighborhood接口
    // 选择邻居用户可以基于
    // 1. '对每个用户取固定数量N个最近邻居'
    // 2. '对每个用户基于一定的限制,取落在相似度限制以内的所有用户为邻居'
    // 其中NearestNUserNeighborhood即基于固定数量求最近邻居的实现类
    // 基于相似度限制的实现是ThresholdUserNeighborhood
    UserNeighborhood neighborhood = new NearestNUserNeighborhood(50, similarity, model);
    //neighborhood.getUserNeighborhood(87);

    // 4. 实现推荐引擎
    // 使用GenericUserBasedRecommender实现Recommender接口
    // 基于用户相似度进行推荐
    Recommender recommender = new GenericUserBasedRecommender(model, neighborhood, similarity);
    Recommender cachingRecommender = new CachingRecommender(recommender);
    List<RecommendedItem> recommendations = cachingRecommender.recommend(87, 10);
    //List<RecommendedItem> recommendations = recommender.recommend(87, 10);

    // 输出推荐结果
    for (RecommendedItem item : recommendations) {
        System.out.println(item.getItemID() + "\t" + item.getValue() + "\t" + movies.get(String.valueOf(item.getItemID())));
    }
}
复制代码

运行结果

935     5.0         Band Wagon, The (1953)  Comedy|Musical
3022    4.5452147   General, The (1927) Comedy
3739    4.511283    Trouble in Paradise (1932)  Comedy|Romance
3188    4.501877    Life and Times of Hank Greenberg, The (1998)    Documentary
3306    4.496834    Circus, The (1928)  Comedy
858     4.4519324   Godfather, The (1972)   Action|Crime|Drama
2019    4.3922834   Seven Samurai (The Magnificent Seven) (Shichinin no samurai) (1954) Action|Drama
3134    4.3842034   Grand Illusion (Grande illusion, La) (1937) Drama|War
1178    4.358055    Paths of Glory (1957)   Drama|War
923     4.3343897   Citizen Kane (1941) Drama
复制代码

基于物品的推荐

public static void tasteItemCF() throws IOException, TasteException {
    // 1. 选择数据源
    // 数据源格式为UserID,MovieID,Ratings
    // 使用文件型数据接口
    String path = "data/ratings.data";
    DataModel model = new FileDataModel(new File(path));

    ItemSimilarity similarity = new EuclideanDistanceSimilarity(model);
    Recommender recommender = new GenericItemBasedRecommender(model, similarity);
    List<RecommendedItem> recommendations = recommender.recommend(87, 10);
    // 输出推荐结果
    for (RecommendedItem item : recommendations) {
        System.out.println(item.getItemID() + "\t" + item.getValue() + "\t" + movies.get(String.valueOf(item.getItemID())));
    }
}
复制代码

运行结果

642     5.0         Roula (1995)    Drama
3779    5.0         Project Moon Base (1953)    Sci-Fi
3647    5.0         Running Free (2000) Drama
1843    5.0         Slappy and the Stinkers (1998)  Children's|Comedy
658     4.652174    Billy's Holiday (1995)  Drama
3172    4.478261    Ulysses (Ulisse) (1954) Adventure
3607    4.4094486   One Little Indian (1973)    Comedy|Drama|Western
1360    4.3977237   Identification of a Woman (Identificazione di una donna) (1982) Drama
139     4.2647057   Target (1995)   Action|Drama
2591    4.261204    Jeanne and the Perfect Guy (Jeanne et le garon formidable) (1998)   Comedy|Romance
复制代码

集群方式

前提需要搭建好hadoop平台并选择与之相适应的版本

使用脚本运行

hadoop jar $MAHOUT_HOME/mahout-core-0.6-cdh4.0.1-job.jar org.apache.mahout.cf.taste.hadoop.item.RecommenderJob
# 数据目录 
--input /user/hadoop/recommend/data

# 输出目录 
--output /user/hadoop/recommend/output

# 临时目录
--tempDir /user/hadoop/tmp

# 需要用到的计算Item相似度的类名称
# SIMILARITY_COOCCURRENCE
# SIMILARITY_LOGLIKELIHOOD
# SIMILARITY_TANIMOTO_COEFFICIENT
# SIMILARITY_CITY_BLOCK
# SIMILARITY_COSINE
# SIMILARITY_PEARSON_CORRELATION
# SIMILARITY_EUCLIDEAN_DISTANCE
--similarityClassname org.apache.mahout.math.hadoop.similarity.cooccurrence.measures.EuclideanDistanceSimilarity

# 对每一个User的推荐结果的个数，RecommenderJob的默认值设为10
# --numRecommendations 10 

# 如果在输入文件中的value是无意义的或者没有value的话，这个值设为true
# –booleanData false

# User最多要有多少个偏好，大于此值将会被忽略
# --maxPrefsPerUser 

# User最少要有多少个偏好，小于此值将会被忽略
# --minPrefsPerUser

# 每一个Item最多与多少个Item计算相似度
# --maxSimilaritiesPerItem

# 在每个Item在计算相似度阶段对User的最大采样个数
# --maxPrefsPerUserInItemSimilarity

# 计算item之间的相似度的时候，去除此值之下的item pair
#--threshold (double) 
复制代码

使用JavaAPI方式

StringBuilder sb = new StringBuilder();
sb.append("--input ").append(inPath);
sb.append(" --output ").append(outPath);
sb.append(" --tempDir ").append(tmpPath);
sb.append(" --booleanData true");
sb.append(" --similarityClassname 
org.apache.mahout.math.hadoop.similarity.
cooccurrence.measures.EuclideanDistanceSimilarity");
args = sb.toString().split(" ");

JobConf jobConf = new JobConf(conf);
jobConf.setJobName("MahoutTest");

RecommenderJob job = new RecommenderJob();
job.setConf(conf);
job.run(args)
复制代码

处理流程

第 1 个 MapReduce ：将 itemID 长整型映射到整型的序号上
第 2 个 MapReduce ：统计每个用户对哪些 item 进行了评分，评分值是多少。
第 3 个 MapReduce ：统计用户的总数。
第 4 个 MapReduce ：统计每个 item 被哪些用户评分了，评分值是多少。
第 5,6,7 个 MapReduce ：计算每个 item 与所有 item 之间的相似度。
第 8 个 MapReduce ：将相同 item 之间的相似度置为 NaN 。
第 9 个 MapReduce ：确定要推荐的用户对哪些 item 进行了评分，评分值是多少。
第 10 个 MapReduce ：得到每个 item 与其他 item 之间的相似度, 这些 item 分别被哪些用户评分了，评分值是多少。
第 11 个 MapReduce ：过滤掉指定用户不需要推荐的 item 。
第 12 个 MapReduce ：得到每个用户要推荐的 item 。这些 item 对于该用户来说是评分最高的前 n 个。
复制代码

参考:

探索推荐引擎内部的秘密
集体智慧编程

引用：http://matrix-lisp.github.io/blog/2013/12/20/mahout-taste-CF/

很好的资料