algorithm - google - calcular el algoritmo de arranque usando Map/Reduce

mapreduce example

Question

Esta pregunta fue originalmente una tarea que tenía, pero mi respuesta fue incorrecta y tengo curiosidad por saber cuál es la mejor solución para este problema.

El objetivo es calcular los aspectos clave del "algoritmo de arranque del sistema recomendado" mediante 4 pasos de reducción de mapas. Mi problema es con el 3er paso, así que solo traeré sus detalles.

entrada: registros de la forma:
1. (ID de población, artículo, número de usuarios de calificación, suma de calificaciones, suma de calificaciones al cuadrado)
2. (ID de población, elemento divisor, me gusta / no me gusta, elemento, número de usuarios de calificación, suma de calificaciones, suma de calificaciones al cuadrado)

La segunda forma es muy parecida a la primera forma, pero un registro para cada (divisor, me gusta / no me gusta) - donde me gusta es booleano.

Esto significa (creo) que hay 2 ^ | elementos | registros del formulario de segundos para cada registro del primer formulario ... (muchos compañeros se equivocaron (de nuevo, creo ...) asumiendo que hay la misma cantidad de registros del primer y segundo formulario)

Descripción de la tarea:

Este paso calculará, por película divisoria, el error cuadrado (SE) inducido por cada película.

• Salida: registros del formulario (ID de población, elemento divisor, elemento, error cuadrado en el elemento dado una división en el divisor).

Insinuación:

asuma que existe una cadena que precede (en el orden de clasificación del sistema) cualquier ID de película divisora.

Esto debe hacerse dentro de un paso mapreduce!

fondo adicional:
Esto se aprendió en el contexto de "The Netflix Challange".

Definición SE:

EDITAR: se puede encontrar material adicional sobre el problema [se puede encontrar una descripción del problema de netflix e información matemática sobre el problema] en este enlace [diapositivas 12-24 especialmente]

EDIT2: tenga en cuenta que ya que estamos usando map / reduce, no podemos asumir que los registros de ORDEN serán procesados ​​[tanto en map como en reducir].

Answer 1

No estoy seguro de entender su pregunta.

Lo que finalmente quieres es SE (U). Después de algunos detalles matemáticos en las diapositivas 23 y 24, se calcula "trivialmente" con / sum_ {i} SE (U) _i

Usted mismo ha comprendido que el 4 y el último septiembre es un mapa reducido para obtener esta suma.

El tercer paso es un mapa reducido para obtener (estilo LaTeX)

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

• La función de reducción suma sobre u en U_i
• La función de mapa divide los términos a sumar.

En Python esto podría parecer:

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]))

Edit : Mi respuesta original fue incompleta. Déjame explicarte de nuevo.

Lo que en última instancia quieres es SE (U) para cada divisor.

El paso a prepara algunos datos útiles sobre los artículos. Las entradas emitidas se definen con:

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

• La función de mapa explota las estadísticas sobre los elementos.
• Las funciones reducidas calculan las sumas.

Ahora, para cualquier película divisoria M:

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

El paso b computa explícitamente, para cada separador M, las estadísticas de las subpoblaciones pequeñas M + y M-.

NB me gusta / no me gustan los booleanos, es el identificador de subpoblación ''+'' o ''-''

Hay 2 nuevas entradas para cada elemento divisor:

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 ''-''

O si te gusta más la notación de 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 medio de la diapositiva 24

Nota: si considera que cada película puede ser un divisor, hay 2x | item | ^ 2 elementos de la segunda forma; eso es porque item -> (boolean, item, splitter) - que es mucho menos que tu 2 ^ | item | evaluación que no has explicado.

El paso c calcula, para cada divisor M, el SE estimado por cada película, es decir, SE (U_M) _i

Porque una suma se puede dividir entre sus diferentes miembros:

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

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

con SE(U_{+M}) computado explícitamente con esta función de mapa:

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))

Ahora todo lo que necesitamos es SE(U_{M?})_i que es un cálculo "trivial" dado en la diapositiva 24:

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

Por supuesto, no vamos a hacer estas grandes sumas, sino que usaremos el comentario justo arriba en la conferencia, y los datos ya calculados en el paso a (esa es la conclusión que extraigo de la diapositiva 24 de las últimas 3 ecuaciones)

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

Entonces, este no es un Mapa / Reducir, solo es un paso final:

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

Paso d Finalmente, los últimos pasos calculan la SE para U_M. Es simplemente la suma de las entradas anteriores, y un Mapa / Reducción trivual:

Para un separador 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)