Sistemas de Recomendação
– Filtragem Colaborativa
AULA 18
DATA MINING
Sandra de Amo
Técnicas: Filtragem Colaborativa


Por vizinhança (usando Clusterização)

Usuários similares são agrupados: itens apreciados por um
usuário similar a mim (cujas avaliações passadas são parecidas
com as minhas) são recomendados para mim.

Items similares são agrupados: items similares àqueles que
eu avaliei positivamente são recomendados para mim.
Modelos de Fatores Latentes
Clusterização






Clusterizar usuários ?
Clusterizar items ?
Clusterizar usuários e items ?
Como representar um usuário ?
Como representar um item ?
Que medidas de similaridade utilizar ?
Perfis de items e de usuários
HP1
A
4
B
5
HP2
5
5
C
D
HP3 TW
Perfil do filme HP1
1
Perfil do usuário A
4
4
3
SW1 SW2 SW3
2
2
3
Medidas de similaridade

MU só contém 1 e vazios: item foi comprado ou não
 Medida utilizada: distância de Jacquard
 Exemplo:
HP1
A
1
B
1
HP2
1
1
C
D
HP3 TW
SW1 SW2 SW3
1
1
1
1
Jacquard-Dist(A,B) = 4/5
Jacquard-Dist(A,C) = 1/2
1
1
1
A é mais similar a C do que a B
Medidas de similaridade

MU contém notas: distância de Jacquard não é adequada !
HP1
A
4
B
5
HP2
5
C
D
HP3 TW
SW1 SW2 SW3
5
1
2
4
4
3
Jacquard-Dist(A,B) = 4/5
Jacquard-Dist(A,C) = 1/2
2
3
A é mais similar a C do que a B ?
A e C têm opiniões antagônicas !
A e B têm opiniões coincidentes !
Medidas de similaridade

MU contém notas : distância do cosseno


Vazios são tratados como zero
Interpreta “não avaliei” como “não gostei”
HP1
A
4
B
5
HP2
5
C
D
HP3 TW
SW1 SW2 SW3
5
1
2
4
4
3
Cosseno(A,B) = 0,380
Cosseno(A,C) = 0.322
2
3
A é mais similar a B do que a C
Pré-processamento
Arredondar notas: Notas 5,4,3 = 1 e notas 1,2 = vazio
HP1
A
4
B
5
HP2
5
C
D
HP3 TW
SW1 SW2 SW3
5
1
2
4
4
3
A é mais similar a B do que a C
2
3
Jacquard-Dist(A,B) = 3/4
Jacquard-Dist(A,C) = 1
Pré-processamento
Normalizar notas: subtraindo de cada nota de um usuário X, a média
das notas de X
Cosseno(A,B) =
Cosseno(A,C) =
A é mais similar a B do que a C
Métodos de Recomendação
Método 1) Recomendar items a um usuário u olhando para os K
usuários mais próximos de u:

Recomenda-se para u items que foram avaliados pela maioria dos K
usuários mais próximos ou que obtiveram notas altas da maioria
destes usuários.
Método 2) Recomendar items a um usuário u olhando para os items
que ele avaliou positivamente

Para cada item I não avaliado:
 Encontra-se os m items mais próximos de I
 Considera-se dentre estes m items aqueles que o usuário avaliou.
 Calcula-se a média das notas destes items
 Esta será a nota prevista para I

Faz-se um ranking das notas dos items não avaliados por u e recomenda-se os
mais cotados
Não há simetria usuário/item nestas duas maneiras de recomendação
Clusterizando Usuários e Items :
como lidar com a esparsidade da MU
Esparsidade da MU  dificuldade para avaliar a distância entre items
e entre usuários.


Mesmo se dois items i1 e i2 são do mesmo gênero, poucos usuários
compraram ou avaliaram ambos.
Mesmo se dois usuários u1 e u2 gostam de um mesmo gênero de
filmes, eles podem não ter comprado nenhum item em comum.
Método
Passo 1


Usar um algoritmo de clusterização hierárquico para clusterizar items
(ou usuários)
Número de clusters deve ser grande = metade do número de items
Método de lidar com a
esparsidade
Exemplo Passo 1
HP1
A
4
B
5
HP2
5
C
D
3
HP3 TW
SW1 SW2 SW3
5
1
2
4
4
2
3
M1
Clusters de items
Vazios diminuiram
Método de lidar com a
esparsidade
Passo 2:
Clusteriza-se
os usuários na MU obtida no passo 1.
Número de clusters = metade do número de usuários
Calcula-se as entradas da nova matriz M2 (cluster usuários x cluster items)
Entrada i, j = média dos valores que aparecem na coluna j da matriz M1, para todos os usuários
do cluster I
Repete-se os passos 1 e 2 até obter um número razoável de clusters
Matriz final = Mn
Como recomendar usando a
matriz Mn ?
Seja U um usuário e I um item que o usuário não avaliou
Queremos prever a nota que U daria para I
1.Encontra-se


os clusters C e D de Mn aos quais U e I pertencem.
C = cluster de usuários (na vertical)
D = cluster de items (na horizontal)
2.Se
a posição C,D da matriz Mn não é vazia:

Valor da posição C,D de Mn = x
Esta é a nota prevista para I que seria dada por U

3.Se


a posição C,D da matriz Mn é vazia
Utiliza-se Método 2 para inferir a entrada da matriz Mn
Valor desta entrada = nota prevista
Modelo de Fatores Latentes
O quanto o usuáro 1 gosta de filmes da
Julia Roberts
A=JR
G=Com
Gênero = Comédia
Ator = Julia Roberts
O quanto o filme HP1
tem a ver com a atriz
Julia Roberts
Procura fatores “latentes” que relacionam características de preferências dos usuários
com características dos items.
Redução UV






MU = U.V
MU = matriz n x m
U = matriz n x p,
V = matriz p x m
onde p = número de fatores latentes
p = parâmetro do algoritmo
Problema de Otimização = Dada a matriz MU (esparsa)
encontrar matrizes U e V (completas) tais que MU é
muito próxima de UV
Como medir “proximidade”
entre as matrizes

RMSE (root-mean-square error)
MU
Exemplo
MU
RMSE = 1,086
U
V
UV
Como encontrar as melhores matrizes U e
V a 2 fatores latentes tais que UV
aproximam MU ?

Inicia-se com todos os elementos de U e V
iguais a 1.

Altera-se progressivamente os valores de
cada entrada de modo que o novo valor é o
que mais diminui o RMSE da matriz anterior
com o velho valor.
Exemplo: melhorando o u11
Exemplo: melhorando o u11
Contribuição da 1a linha
Soma dos erros
quadráticos
da 1a linha:
Antes: 18
Depois : 5,2
RMSE Antes : 75
Depois: 62.2
Exemplo: melhorando o v11
Exemplo: quando a entrada a otimizar
envolve espaços vazios da MU

Otimizando u31
MU
Técnica Gradient Descent

Dados um conjunto de valores (os elementos não vazios
da MU), para cada um deles encontrar a direção de
mudança que minimiza a função erro (o RMSE)

Quando a matriz é muito grande, esta técnica é bem
demorada, leva muito tempo para convergir.

Gradient Descent Estocástico: selecionar
randomicamente apenas um subconjunto dos pontos da
matriz.
Algoritmo da Decomposição
UV
Entrada: matriz MU (nxm) (com valores vazios),
p = número de fatores latentes
Saida : matrizes U (nxp), V (pxm) tais que RMSE(MU,UV) é minimal.
1.
2.
3.
4.
Pre-processamento da Matriz MU (n x m)
Inicializar U e V
Estipular um caminho x1,x2,...,xk, onde k = np+mp e xi são
elementos da matriz U ou da matriz V
Condição de parada
Etapas do algoritmo
1.
Preprocessamento de MU





Subtrair de cada elemento mij (não vazio) de MU a média
ei das notas dadas pelo usuário i
Subtrair de cada elemento resultante a média fj das notas
obtidas pelo item j
Pode-se inverter a ordem dos 2 procedimentos acima. Os
resultados não serão os mesmos mas serão próximos
Sempre que se for fazer predições sobre notas, é preciso
“desfazer a normalização” no final.
Se o valor previsto para mij for X, então o valor
recomendado deverá ser X + ei + fj
Etapas do algoritmo
2. Inicialização de U e V
Seja a = média dos valores de MU
Inicializar U e V com o valor √a/p para cada elemento de U e de V
Outra maneira:




Cada valor é inicializado de forma diferente considerando
o valor √a/p + x, onde x um número escolhido em um conjunto com
distribuição normal com média 0 e desvio padrão c para algum c.
Etapas do algoritmo
3. Estipular a ordem dos elementos de U e V em que é feita a
otimização.



Linha por linha: alternando linhas de U com linhas de V
Visitar os elementos nesta ordem, de uma maneira round-robin
Outra maneira: escolhe-se uma permutação qualquer do conjunto
{1,...,k} e visita os elementos das matrizes U e V nesta ordem.
Etapas do algoritmo
4. Condição de parada

A cada iteração todos os k pontos são otimizados e o
RMSE é calculado.

Caso RMSE < threshold dado, para-se o processo.

Outra variante: assim que o RMSE durante uma iteração
for < threshold, pára.
Problema com overfitting


Considere diversas decomposições UV
A fim de inferir o valor de uma posição vazia
mij na MU considere a média das inferências
feitas por cada decomposição para mij.
Fórmula Geral para otimizar
elemento urs


Seja P = UV
Elemento urs só afeta a linha r de P
urs
Exercicio para entregar

Deduzir fórmula análoga para obter o valor
otimizado para o elemento vrs = y