�ݺ�ߣ

Systemy rekomendacji

Adam Kawa
Seminarium: Systemy przetwarzania informacji
09.01.2008, godz. 12:15

 Plan prezentacji
 Wprowadzenie
 Metody zbierania informacji o użytkowniku
 Techniki rekomendacji
 Problemy, trudności i wyzwania
 Przykłady aplikacji

Wprowadzenie
 Definicja
Systemy rekomendacji to programy, które
 strają się przedstawić informacje o przedmiotach (np. muzka, filmy),
którymi dany użytkownik mógłby być zainteresowany
 wykorzystują w tym celu zebrane informacje na temat preferencji i cech
użytkownika, preferencji i cech innych użytkowników oraz atrybutów
przedmiotów.

Wprowadzenie
 Definicja [1]

Wprowadzenie
 Przyczyny powstania [2]
 przyrost liczby użytkowników (większe
zróżnicowanie ich potrzeb)
 przyrost ilości danych (udostępnianych oraz
poszukiwanych)

 ten sam czas, który można poświęcić na
znalezienie interesujących informacji
 ten sam czas, który można poświęcić na
zrozumienie i wykorzystanie znalezionych
informacji

Wprowadzenie
 Możliwe korzyści [2]
 Dla użytkowników
 szybki dostęp do poszukiwanych zasobów
 możliwość otrzymania informacji zgodnej z preferencjami i oczekiwaniami

 Dla właścicieli:
 pozyskanie licznej grupy klientów
 możliwość zdefiniowania grup docelowych, do których mogą być
kierowane szczegółowe treści i oferty
 zdobycie uznania wśród użytkowników za dostosowanie portalu do ich
potrzeb
 szansa na pozyskanie lojalności
 konkurencyjność wobec serwisów, które nie stosują
takich praktyk

Wprowadzenie
 Problem rekomendacji (uproszczony) [3]
Niech
 C - zbiór wszystkich użytkowników
 I - zbiór rekomendowanych przedmiotów (np. ksiązki, filmy, usługi
finansowe)
 R - uporządkowany zbiór (np. liczb całkowitych z zakresu <1,100>)

u : C× I  R - funkcja użyteczności przedmiotu i dla użytkownika c.

Zadanie:

∀ c∈C , i c =max u c ,i
i∈I
(dla każdego użytkownika znaleźć przedmiot o największej wartości funkcji
użyteczności)

 Problem rekomendacji (uproszczony) [2]
 Ogólna idea działania
 identyfikacja użytkownika (zebranie infromacji o nim)
 analiza danych (stworzenie profilu użytkownika reprezentującego jego
preferencje)
 indywidualizacja zasobów (rekomendacja przedmiotów najbardziej
pasujących do profilu danego użytkownika)

Metody zbierania informacji
 Metody zbierania informacji o użytkowniku
 Profilowanie jawne (explicit profile)
 Profilowanie domniemane (implicit profile)

 Profilowanie jawne (explicit profile)
 uzyskiwanie informacji bezpośrednio od użytkownika poprzez wypełnianie
kwestionariuszy lub odpowiadanie na pytania, np.
 ocena przedmiotu w skali liczbowej
 uszeregowanie listy przedmiotów od najbardziej do najmniej ulubionych
 utworzenie listy przedmiotów, które użytkownik (nie) lubi.

 subiektywny obraz profilu użytkownika
 spotykane z niechęcią ze strony użytkownika
 trudności w pozyskiwaniu dużej liczy informacjii

 Profilowanie domniemane (implicit profile)
 obserowanie zachowań użytkownika, np.
 prowadzenie archiwum zakupionych przedmiotów
 utrzymywanie listy ostatnio przeglądanych przedmiotów
 analiza cech oglądanych przedmiotów
 analiza czasu poświęconego na oglądanie przedmiotu
 wyszukiwanie innych użytkowników o podobnych gustach

 rzeczywisty i aktualny obraz profilu użytkownika na podstawie jego
faktycznego zachowania
 niewidoczne dla użytkownika
 umożliwia zebranie większej ilości informacji

Techniki rekomendacji
 Techniki rekomendacji
 Niespersonalizowane
 Oparte na użytkowniku (user-based)
 Oparte na zawartości (content-based)

 Kolaboratywne filtrowanie (collaborative filtering)
 Oparte na użytkowniku (user-based)

 Hybrydowe metody (hybrid methods) - lączące powyższe techniki

 Niespersonalizowane (non-personalized) [1]
 Rekomendacja najpopularniejszych przedmiotów wszystkim użytkownikom.

 popularność: oceny użytkowników, dane sprzedaży, oglądalność itd.

 obliczenie średniej oceny popularności dla każdego przedmiotu
 rekomendacja przedmiotów z najwyższą średnią ocen
 np. prezentacja listy 10 najpopularniejszych filmów (komedii)

 Oparte na użytkowniku (user-based) [1]
 Rekomendacja tych samych przedmiotów grupom użytkowników o wspólnych
cechach osobistych.

 cechy osobiste: wiek, płeć, kraj, zawód, stan cywilny itd.

 znalezienie użytkowników o podobnych cechach
 rekomendacja przedmiotów wybieranych przez użytkowników o podobnych
cechach

 Oparte na użytkowniku (user-based) [1]
 znalezienie użytkowników o podobnych cechach
 np. algorytm K-najbliższych sąsiadów z funkcją odległości:

D(u,v) = dwiek(u,v) + dpłec(u,v) + dhobby(u,v) + ...
dwiek(u,v) = | u.wiek – v.wiek | / max_roznica_wiek

 rekomendacja przedmiotów wybieranych przez użytkowników o podobnych
cechach
 np. średnia ważona ocen sąsiadów

Pa , j=
∑ r u , j⋅w a , j , w a , j =min 
1
, max waga 
∑ wa , u D a , u

 Niespersonalizowane (non-personalized) oraz oparte na
użytkowniku (user-based) [1]
 Zalety
 możliwość obliczenia rekomendacji bez konieczności zebrania informacji
na temat cech przedmiotów oraz preferencji i gustów użytkownika

 Wady i problemy
 niski stopień personalizacji rekomendacji
 niewystarczający współczynnik trafności rekomendacji

 Oparte na zawartości (content-based) [1]
 Rekomendacja przedmiotów o podobnych cechach, jak te przedmioty, którymi
użytkownik był w przeszłości zainteresowany.

 cechy przedmiotów: np. film - rodzaj, reżyser, obsada, opis, słowa kluczowe,
nagrody itd.

 zebranie informacji na temat cech przedmiotów
 znalezienie najbardziej podobnych przedmiotów do preferowanych wcześniej
przez użytkownika
 rekomendacja przedmiotów najbardziej pasujących do profilu użytkownika

 najczęściej wykorzystywane są tekstowe opisy przedmiotów za pomocą
słów kluczowych, np.
 system rekomendacji stron internetowych Fab reprezentuje stronę
internetową za pomocą 100 najistotniejszych słów
 system rekomendacji książek LIBRA reprezentuje ksiązke za pomocą
wektora zbiorów słów kluczowych tzn.
ksiązka = [autor, tytuł, temat, opis, ...]
temat = [...], opis = [...]

 internetowe bazy danych, np. http://www.imdb.com/
 booty intenetowe

 Oparte na zawartości (content-based) [3]
 miara poziomu istotności (ważności) słowa k i w dokumencie dj
 term frequency/inverse document frequency (TF-IDF)
N - liczba rekomendowanych dokumentów
ni - ilość dokumentów, w których występuje słowo kluczowe ki
fij - ilość wystąpień słowa kluczowego ki w dokumencie dj
f i, j

TF i , j = - frekwencja słowa ki w dokumencie dj
max f z , j
f z, j ∈d j

N
IDF i =log   - odwrotna frekwencja dokumentu dla słowa ki
ni
w i , j =TF i , j ×IDF i - waga słowa ki w dokumencie dj
content  d j =[w 1, j , w2, j ,... , w m , j ] - opis dokumentu dj

 określenie profilu użytkownika na podstawie zebranych danych
 user_profile(c) = [wc1, wc2, ..., wcm], wektor wag, gdzie waga wci oznacza
poziom istotności słowa kluczowego ki dla użytkownika c.
 średnie wagi słów kluczowych w mierze TF-IDF
 prawdopodobieństwa istotności słów kluczowych obliczone przez sieć
Bayessowska

 rekomendacja przedmiotów najbardziej pasujących do profilu użytkownika
 u(c,i) = score(user_profile(c), content(i))
 cosinus kąta między wektorami
w w
 c⋅ i
u c ,i =cos c ,  i =
w w
∥ c∥ ×∥  i∥
w w

 inne metody wykorzystywane w rekomendacji opartej na zawartości
 obliczanie funkcji użyteczności z wykorzystaniem pewnego modelu
wyuczonego na podstawie danych treningowych
 naiwny klasyfikator bayessowski
 oszacowuje prawdopodbieństwo, że dany przedmiot p należy do
j
pewnej klasy Ci (np. odpowiedni, nieodpowiedni) na podstawie
danego zbioru słów kluczowych k1,j,..., kn,j opisujących przedmiot pj
P  p j ∈C i = PC i | k 1, j ∧...∧k n , j 

 przy (upraszczającym) założeniu niezależności słów kluczowych

P  p j ∈C i =P C i  ∏x P  k x , j |C i 
 wysoka trafność klasyfikacji

 Wady i problemy
 ograniczona analiza zawartości
 konieczność reprezentowania opisu przedmiotu w formie
umożliwiającej jego automatyczną analizę przez komputer (np. tekst)
lub wprowadzenia go ręcznie
 trudności w analizie zawartości niektórych przedmiotów np. obrazów,
dźwięków, strumieni video
 nie rozróznianie różnych przedmiotów reprezentowanych przez
identyczne zbiory cech (nieuwzględnianie jakości przedmiotu)

 Wady i problemy
 zbyt wysoka specjalizacja
 rekomendacja jedynie dla przedmiotów pasujących do profilu
użytkownika (zbyt jednorodne alternatywy, brak „niespodziewanych”
rekomendacji)
 wysokie prawdopodobieństwo rekomendacji niemalże identycznych
przedmiotów (np. newsy opisujące te same wydarzenie)

 problem nowego użytkownika (new user problem)
 niemożliwość udzielenia trafnych rekomendacji dla użytkownika, który
nie ocenił wystarczająco dużej liczby przedmiotów

 Kolaboratywne filtrowanie oparte na użytkowniku
(user-based collaborative filtering) [1]
 rekomendacja przedmiotów, którymi byli zainteresowani inni użytkownicy o
podobnych preferencjach i oczekiwaniach
 analogia do ustnej rekomendacji

 oceny użytkowników, dane sprzedaży, oglądalność itd.
 zebranie informacji na temat gustów użytkownika
 znalezienie użytkowników o najbardziej podobnych preferencjach i gustach
 rekomendacja na podstawie preferencji podobnych użytkowników

(user-based collaborative filtering)
 znalezienie użytkowników o najbardziej podobnych preferencjach i
oczekiwaniach
I u , v ={i ∈ I : ru ,i ≠∅ , r v , i ≠∅}
 współczynnik korelacji Pearsona
∑  r u , i −r u × r v , i −r v 
i∈I u ,v
similarity u , v =
 ∑  r u ,i −r u 2× ∑  r v , i−r v 2
i∈I u , v i∈I u , v

 cosinus kąta między wektorami
u =[ r u ,i : r u , i ∈ I u , v ] ,
w v =[r v , i : r v ,i ∈ I u , v ]
w
w w
u⋅v
similarity u , v =cosu ,  v =
w w
∥ u∥ ×∥  v∥
w w

(user-based collaborative filtering) [3]
 rekomendacja na podstawie preferencji podobnych użytkowników

1
 r u , i=
N
∑ r u ' ,i
u ' ∈U '


r u , i=k u ∑ similarity  u , u ' ×r u ' ,i
u ' ∈U '


r u , i= r u k u
 ∑ similarity u , u' × r u ' , i − r '  (uwzględnienie użycia
u
u ' ∈U '

różnych skali ocen przez różnych użytkowników)

k u =1/ ∑ ∣similarity u , u' ∣
u ' ∈U '
r u - średnia ocen użytkownika u


 Zalety
 możliwość rekomendacji produktów, bez konieczności zebrania informacji
na temat ich atrybutów, cech.
 możliwość rekomendacji produktów, których atrybuty są niedostępne lub
trudne w analizie np. obrazy, dźwięki, idee, opinie.
 możliwość rekomendacji przypadkowych, ale odpowiadających
preferencjom użytkownika przedmiotów

 Wady i problemy
 new user problem
 new item problem - brak możliwości rekomendacji nowych przedmiotów
zanim nie zostaną one ocenione przez wystarczająco dużą liczbę
użytkowników
 sparsity problem - brak ocen danego użytkownika dla zdecydowanej
więszości przedmiotów; rzadka macierz użytkownik-przedmiot
 niewystarczająco dobre rekomendacje dla użytkowników o
zróżnicowanych opiniach lub nietypowych preferencjach.

 Hybrydowe systemy rekomendacji (hybrid
recommender systems)
 Rekomendacja przedmiotów z jednoczesnym wykorzystaniem różnych technik
rekomendacji (najczęściej - opartej na zawartości i kolaboratywnego
filtrowania) w celu uniknięcia ograniczeń związanych z ich niezależnym
stosowaniem.

 Przykład: Content-Boosted Collaborative Filtering
 poprawa istniejących danych na temat użytkowników i przedmiotów
poprzez wykorzystanie cechy osobistych użytkowników oraz zawartości
przedmiotów (wygenerowanie pseudo-ocen)
 spersonalizowane rekomendacje przy użytciu kolaboratywnego filtrowania
 lepsze wyniki niż te, które dają niezależnie działające rekomendacje oparte
na zawartości, kolaboratywne filtrowanie oraz proste systemy hybrydowe

Problemy, trudności i wyzwania
 Problemy, trudności i ich typowe rozwiązania
 wielowymiarowe rekomendacje [3]
 uwzględnienie dodatkowych „kontekstowych informacji” (np. dzień
tygodnia, pora roku, miejsce)
 zdefiniowanie funkcji użyteczności nad wielowymiarową dziedziną
D 1 ×...× D n zamiast dwuwymiarowej użytkownik× przedmiot tj.

u: D1 ×...× D n  R

np. d3 - miejsce oglądania filmu (kino, mieszkanie); d4 - czas (dzień
roboczy, weekend, ranek, wieczór); d5 - osoby towarzyszące (rodzice,
dziewczyna, przyjaciele)

 redukcja do problemu dwuwymiarowej rekomendacji przez wybranie
elementów spełniających dodatkowe „kontekstowe kryteria” (tagi tekstowe)

 multikryterialne oceny [3]
 wykorzystanie ocen wielu kryteriów przy końcowej ocenie danego przedmiotu
np. rekomendacja restauracji - ocena jedzenia, dekoracji oraz serwisu

 kombinacja liniowa ocen wszystkich kryteriów
 optymalizacja oceny „naważniejszego” kryterium, traktując pozostałe jako
stałe, niech np.
 fc(r), dc(r), sc(r) – oceny użytkownika c dotyczące odpowiednio jedzenia,
dekoracji i serwisu w restarauracji r
 wybranie fc(r) jako najważniejszego kryterium oceny restauracji r
 znalezienie restauracji r o największej wartości fc(r), t.że dc(r)>d i sc(r)>s

 konieczność szacowania niektórych wartości spośród fc(r), dc(r), sc(r)

 złośliwi użytkownicy [3]
 oszukiwanie systemów rekomendacji w celu zwiększenia popularności
własnych przedmiotów
 zatrudnianie użytkowników wysoko oceniających wskazane
przedmioty
 wykorzystanie botów internetowych generujących „sztuczne
zainteresowanie” wskazanymi przedmiotami

 inwazyjność - trudności w jawnym zbieraniu informacji
 profilowanie doniemane - zbieranie i analizowanie np. danych sprzedaży,
częstości i czasu oglądania przedmiotu, sekwencji kliknięć na stronie

 zbyt wysoka specjalizacja
 unikanie rekomendacji zbyt podobnych przedmiotów do tych, którymi
użytkownik był zainteresowany w przeszłości

 cold-start oraz sparsity problem
 zbyt mało danych w początkowej fazie działania systemu (new user, new
item problem)

 wykorzystanie cech osobowych użytkownika oraz zawartości przedmiotu
● pseudo-oceny dla przedmiotów, które nie zostały ocenione przez danego
użytkownika

 The Netflix $1 Million Prize
 konkurs ogłoszony przez Netflix, internetową wypożyczalnie filmów w
październiku 2006 roku.
 zasady i idea konkursu
 poprawa współczynnika trafności systemu rekomendacji Netfixa o 10%
 udostępnienie bazy danych klientów (ponad 100 milionów ocen, 17,770
filmów, 480,189 osób) jako zbioru treningowego
 testowanie systemów na aktualizowanych (utajnionych) danych
 nagroda - 1.000.000 $ (wciąż do wygrania!!)
 dotychczasowe najlepsze wyniki
 1. 8.50%, B.Bell i Y.Koren - AT&T Research,
 8. 7.62%, Arek Paterek – Uniwersytet Warszawski

Aplikacje
 Last.fm
 internetowa radiostacja i system muzycznych rekomendacji
 ponad 20 milionów aktywnych użytkowników z 232 krajów
 rekomendacje bazowane na podstawie odsłuchiwanych piosenek i gustach
„muzycznych sąsiadów”
 możliwość rekomendacji przez użytkowników wybranych wykonawców,
utworów lub albumów muzycznych innym użytkownikom
 możliwość tagowania artystów, albumów i utworów, dzięki czemu można
słuchać muzyki oznaczonej w wybrany sposób np. „early british rock”,
„piosenkarze, których X by lubił”

Aplikacje
 Levis / Style Finder
 rekomendacja produktów firmy odzieżowej
Levi StrausTM
 wymagane informacje na temat płci oraz
ocena minimum 4 „napisów”, „subkategorii”
spośród kategorii: muzyka, wygląd, zabawa w
skali 1-7.
 kolaboratywne filtrowanie oparte na
użytkowniku (user-based collaborative
filtering)
 prezentacja listy Top-6 przedmiotów
 wzrost średnio o 33 % wartość zakupów
realizowanych w sklepie internetowym
 87% badanych zadeklarowało, iż kupiłoby
rekomendowany produkt.

Aplikacje
 hakia
 wyszukiwarka internetowa, która
umożliwia kontakt z osobami
szukającymi informacji na
podobny temat
 rekomendacje przedstawiane
przez ludzi (silna analogia do
„ustnej promocji” przedmiotu)


Dziękuję za uwagę!

 Bibliografia
 [1] „What is a Recommender System?”, Juntae Kim
 [2] „Personalizacja portalu jako instrument marketingu”,
http://marketing.nf.pl/Artykul/7623/Personalizacja-portalu-jako-instrument-marketingu/
 [3] „Toward the Next Generation of Recommender Systems: A Survey of the
State-of-the-Art and Possible Extensions”, Gediminas Adomavicius, Alexander
Tuzhilin
 „Content-Boosted Collaborative Filtering for Improved Recommendations”, Prem
Melville and Raymond J. Mooney and Ramadass Nagarajan
 „Recommender Systems in E-Commerce”, J. Ben Schafer, Joseph Konstan, John
Riedl
 „Explanation for Recommender Systems: Satisfaction vs. Promotion”, Mustafa
Bilgic

�ݺ�ߣ

Systemy rekomendacji

More Related Content

Systemy rekomendacji