使用Map/Reduce计算自举算法

Question

这个问题最初是我的作业,但我的回答是错误的,我很好奇这个问题的最佳解决方案是什么.

目标是使用4个map reduce步骤计算"Recommender System bootstrapping algorithm"的关键方面.我的问题是第3步,所以我只带来它的细节.

输入:表格记录:
1.(人口ID,项目,评级用户数,评级总和,平均等级之和)
2.(人口ID,分配器项目,喜欢/不喜欢者,项目,评级用户数量,总和评级,平均等级总和)

第二种形式非常类似于第一种形式,但是每种形式的记录(分离者,喜欢者/不喜欢者) - 喜欢/不喜欢的人是布尔值.

这意味着(我认为)有2 ^ |项目| 来自第一种形式的每条记录的秒形式的记录......(许多同学做错了(再次,我认为......)假设有相同数量的第一和第二形式记录)

任务描述:

此步骤将根据分割器电影计算每部电影引起的平方误差(SE).

• 输出:表格的记录(人口ID,拆分项目,项目,在拆分器上给出拆分的项目的平方误差).

暗示:

假设存在一个字符串(在系统的排序顺序中)之前的任何分割器影片ID.

这必须在一个mapreduce步骤中完成!

其他背景:
这是在"The Netflix Challange"的背景下学到的.

SE定义:

编辑:有关问题的其他材料[有关netflix挑战的一些描述和有关问题的数学信息]可以在此链接中找到[幻灯片12-24特别]

EDIT2:请注意,由于我们使用的是map/reduce,因此我们无法假设任何有关ORDER记录的内容将被处理[在map和reduce中].

Answer 1

我不确定我是否理解你的问题。

你最终想要的是SE(U)。在幻灯片 23 和 24 的一些数学细节之后，它是用 \sum_{i} SE(U)_i “简单地”计算的

您自己已经了解，第​​四个也是最后一个九月是一个映射减少以获得这个总和。

第三步是map缩减得到（LaTeX风格）

SE(U)_i = \sum_{u in U_i} (r_{u,i} - r_i)^2

• reduce 函数对 U_i 中的 u 求和
• map 函数分割要求和的项

在 Python 中，这可能看起来像：

def map(Ui):
    ''' Ui is the list of user who have rated the film i'''
    for user in Ui:
        results.append((user,(r_{u,i} - r_i)^2))

def reduce(results):
    ''' Returns a final pair (item, SE(U)_i ) '''
    return (item, sum([value for user,value in results]))

编辑：我原来的答案不完整。让我再解释一下。

您最终想要的是每个分离器的 SE(U)。

步骤 a准备一些有关项目的有用数据。发出的条目定义为：

key = (population_id, item)
value =
    number: |U_i|,
    sum_of_ratings: \sum_{u \ in U_i} r_{u,i} 
    sum_of_squared_ratings: \sum_{u \in U_i} r_{u,i} ^2

• 地图功能爆炸了项目的统计数据。
• reduce 函数计算总和。

现在，对于任何给定的分割器电影 M：

U_M = U_{+M} + U_{-M} + U_{M?}

步骤b显式地计算每个分离器M的小子群M+和M-的统计量。

注意喜欢/不喜欢本身不是布尔值，它是子群体标识符“+”或“-”

每个拆分项有 2 个新条目：

key = (population_id, item, M, '+') 
value = 
    number: |U_i(+)|
    sum_of_ratings: \sum_{u \ in U_i(+)} r_{u,i}
    sum_of_squared_ratings: \sum_{u \in U_i(+)} r_{u,i} ^2

Same thing for '-'

或者，如果您更喜欢 dis/likers 符号

key = (population_id, item, M, dis/likers) 
value = 
    number: |U_i(dis/likers)|
    sum_of_ratings: \sum_{u \ in U_i(dis/likers)} r_{u,i}
    sum_of_squared_ratings: \sum_{u \in U_i(dis/likers)} r_{u,i} ^2

参见幻灯片 24 的中间部分

注意：如果您认为每部电影可能是一个分离器，则有 2x |item|^2 第二种形式的项目；那是因为 item -> (boolean, item, splitter) -- 这远远小于你的 2^|item| 评价你还没有解释。

步骤c为每个分割器M计算每部电影的估计SE，即SE(U_M)_i

因为总和可以分为不同的成员：

U_M = U_{+M} + U_{-M} + U_{M?}

SE(U_M)_i = SE(U_M?)_i + SE(U_+M) + SE(U_-M)

使用SE(U_{+M})此映射函数显式计算：

def map(key, value):
    '''     
    key = (population_id, item, M, dis/likers) 
    '''
    value = 
        count: 1
        dist: (r_u,i - r_i)^2

    emit key, value

def reduce(key, values):
    ''' 
    This function explicitly computes the SE for dis/likers
    key = (population_id, item, M, dis/likers)
    value= count, dist
    '''
    emit key, sum(count, sum(dist))

现在我们所需要的SE(U_{M?})_i只是幻灯片 24 中给出的“简单”计算：

SE(?)_i = \sum_{u \in U_i(?)}{r_{u,i}^2} - (\sum r)^2 / |U_i(?)|

当然，我们不会做这么大的求和，而是使用讲座上面的注释，以及步骤 a 中已经计算出的数据（这是我从幻灯片 24 的最后 3 个方程中得出的结论）

SE(?)_i = \sum_{u \in U_i}{r_{u,i}^2} - \sum_{u \in U_i('+'/'-')}{r_{u,i}^2} - (...)/ (|U_i| - |U_i('+'/'-'))

所以这甚至不是 Map/Reduce，它只是最终确定步骤：

def finalize(key, values):
    for [k in keys if k match key]:
        ''' From all entries get
        # from step a
        key = (population_id, item) value=(nb_ratings, sum_ratings, sum_ratings_squared)
        # from step b
        key = (population_id, item, M, '+') value=(nb_ratings_likers, sum_ratings_likers, sum_ratings_squared_likers)
        key = (population_id, item, M, '-') value=(nb_ratings_dislikers, sum_ratings_dislikers, sum_ratings_squared_dislikers)
        # from step c
        key = (population_id, item, M, '+') value=(se_likers)
        key = (population_id, item, M, '-') value=(se_dislikers)
        '''
        se_other = sum_rating_squared - sum_ratings_squared_likers  - sum_ratins_squared_dislikers - sum_ratings_likers / (nb_ratings -  (nb_ratings_likers)) - sum_ratins_squared_dislikers  - sum_ratings_likers / (nb_ratings -  (nb_ratings_likers))
        emit
            key: (population_id, splitter, item)
            value : se_likers + se_dislikers + se_other

步骤 d最后，最后的步骤计算 U_M 的 SE。它只是之前条目的总和，以及一个简单的 Map/Reduce：

对于分离器 M：

SE(U_M) = \sum_i SE(U_M)_i = \sum_i SE(U_M?)_i + \sum_i SE(U_+M) + \sum_i SE(U_-M)