Вычислить алгоритм начальной загрузки, используя Map/Reduce

Ответ 1

Я не уверен, что понимаю ваш вопрос.

В конечном итоге вы хотите SE (U). После некоторых математических данных на слайдах 23 и 24 он "тривиально" вычисляется с помощью \sum_ {i} SE (U) _i

Вы сами поняли, что 4-й и последний сеанс - это карта, чтобы получить эту сумму.

Третий шаг - это сокращение карты, чтобы получить (стиль LaTeX)

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

• Сумма функции убывания по u в U_i
• Функция карты разбивает слагаемые, которые следует суммировать

В 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

• Функция карты взрывает статистику по элементам.
• Функции сокращения вычисляют суммы.

Теперь для любого данного фильма сплиттера M:

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

Шаг b явно вычисляет для каждого сплиттера M статистику для малых подгрупп M + и M-.

NB likers/dislikers не являются логическими per se, это идентификатор подгруппы "+" или "-"

Для каждого элемента разделителя есть две новые записи:

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

cf Середина слайда 24

NB Если вы считаете, что каждый фильм может быть сплиттером, то есть 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 Наконец, последние шаги вычисляют SE для U_M. Это просто сумма предыдущих записей и триальна 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)