Zastosowanie algorytmów grupowania w
sieci WWW i e-biznesie
Wykład 2
Systemy rekomendujące
(w systemach
sprzedaży)
Katedra Systemów Informacyjnych i Sieci Komputerowych
Urszula Kużelewska
Zastosowanie algorytmów grupowania w
sieci WWW i e-biznesie
Wykład 2
Systemy rekomendujące
(w systemach
sprzedaży)
Katedra Systemów Informacyjnych i Sieci Komputerowych
Urszula Kużelewska
Źródła danych
●
Dane o użytkowniku:
–
dane demograficzne,
–
zainteresowania i preferencje
,
–
lista znajomych.
●
Dane o użytkowaniu:
–
wybór zasobów (przeglądanie),
–
czas poświęcony na zainteresowanie zasobem,
–
oceny punktowe
,
–
oceny słowne (komentarze),
–
zakupy
.
Systemy rekomendujące (RS)
●
Poszukiwanie osób o podobnym guście
–
Podobne oceny dla danych przedmiotów
–
Podobne zainteresowania, grupa wiekowa, itp.
●
Stworzenie profilu użytkownika
●
Nowej osobie proponujemy to, co jest wysoko
ocenione przez osoby do niej podobne (np. z
profilu)
●
Ocena podobieństwa na podstawie badania
zachowania nowego użytkownika
Techniki stosowane w RS
●
Oparte na danych demograficznych
–
np. „przy kupnie samochodu kobiety sugerują się
jego wyglądem”
–
zbyt ogólne
●
Podsumowania statystyczne
–
Liczba osób/grupa osób, które kupiły dany produkt
–
Średnia ocen, najczęściej polecane
●
Wykorzystujące korelację atrybutów
–
Czerwone buty+czerwona torebka
–
Książka w promocji+ przeceniona płyta
–
„Miś”, „Alternatywy 4”+”Jolka, Jolka, pamiętasz”
●
Analiza koszykowa
–
np. „w weekendy większość osób, które kupują
pieluszki, kupują też piwo”
Techniki stosowane w RS
●
Algorytmy grupujące
–
Stworzenie profili na podstawie grup wydzielonych przez
algorytm grupujący
–
Stworzenie modelu
danych
●
Collaborative filtering
–
Bezpośrednia analiza podobieństwa pomiędzy obiektami
–
Brak wymaganego etapu wydzielania profili
(heurystyczne)
–
Ranking
przedmiotów
Przykłady profili rzeczywistych
●
Źródło: behavia.pl
●
Collaborative filtering
●
Macierz m
x
n 0 (nie lubi),1 (lubi) ,- (?)
●
Co osoba o2 sądzi o p5?
●
Czy osoba o4 będzie zainteresowana p1, p2, p3,
p4, p5?
p1
p2
p3
p4
p5
o1
0
1
1
1
0
o2
0
0
0
0
-
o3
1
-
0
0
-
o4
-
-
-
-
1
o5
1
1
1
0
-
Collaborative filtering
●
Określa się lokalne podobieństwo (sąsiadów)
pomiędzy osobami (na podstawie ich zakupów)
●
Podobieństwo: m.in. miara kosinusowa,
współczynnik korelacji
●
Rekomendacje: przedmioty z koszyków
sąsiadów
●
Szybkie?
●
Długa lista rekomendacji?
Ranking przedmiotów
●
Jeśli lista podobnych przedmiotów jest długa
jest ona sortowana wg kryteriów:
–
Nowości
–
Popularność przedmiotów
–
Waga oceny - zwykły użytkownik/autorytet
–
Społeczne przekonania – szybciej polubimy to, co
nasi znajomi
Jeśli Jacek i Hania lubią pływanie, a Hania lubi też
tenis, to prawdopodobnie Jacek też lubi tenis
Jest to bardziej prawdopodobne, jeśli Jacek i Hania
się znają
Podział metod collaborative filtering
●
User-to-user - rekomendacje
są generowane w oparciu
o podobieństwo pomiędzy
samymi użytkownikami
●
Item-to-item – badane jest
podobieństwo pomiędzy
przedmiotami (na podstawie
akcji użytkowników)
●
Search-based – konstrukcja
zapytania na podstawie
danego przedmiotu
●
Content-based – (item-to-user) porównanie
opisu przedmiotu do profilu użytkownika
Mary: kupiła przedmiot D,
rekomenduje się jej
przedmiot A ?
Algorytmy user-to-user
•
v
i,j
= ocena użytkownika i dla przedmiotu j
•
I
i
= lista przedmiotów ocenionych przez użytkownika i
•
Średnia ocena użytkownika i:
•
Przewidywana ocena nowego użytkownika a dla
przedmiotu j
waga n podobnych użytkowników
Stała
normalizująca
Algorytmy item-to-item
•
Obliczanie wag:
–
Wybór K najbliższych sąsiadów
–
Współczynnik korelacji Pearsona
–
Miara kosinusowa
∈
=
else
0
)
neighbors(
if
1
)
,
(
a
i
i
a
w
Ocena skuteczności algorytmu
1.Podział zbioru na uczący i testowy (A)
2.W każdym przypadku i ze zbioru testowego:
1. Dla każdej oceny j z badanego przypadku testowego
określić różnicę pomiędzy oceną oszacowaną a
rzeczywistą
2. Obliczyć wartość pierwiastka błędu
średniokwadratowego (RSME
i
):
3.Obliczyć ogólną wartość pierwiastka błędu
średniokwadratowego (RSME)
̂
r
ij
̂
r
ij
r
ij
Algorytm item-to-item Amazonu
●
opatentowany!!!
●
buduje się binarną
macierz użytkownik-
przedmiot
●
oblicza
podobieństwo
(cosinus) pomiędzy
wektorami macierzy
●
rekomendacje
Item1->Item3
Item2->Item3
Item3->Item1,Item2
Podobieństwo
przedmiotów
●
cos(f1,f2)=1/(
√
12
√
2)=1/
(2
√
6)<0.5
●
cos(f1,f8)=0<0.5
●
cos(f7,f6)=2/(
√
4
√
5)≈0.5
●
Użytkownikowi, który
kupi f7 zostanie
zarekomendowany f6
nr
uż\film
f1
f2
f3
f4
f5
f6
f7
f8
f9
f10
1
1
1
0
0
0
1
0
0
0
0
2
1
0
0
0
0
0
0
0
0
0
3
1
0
0
0
0
0
0
0
0
0
4
1
0
0
0
0
0
1
0
0
0
5
1
0
0
0
0
0
0
0
0
0
6
0
0
0
0
0
0
0
0
0
0
7
1
0
0
0
0
0
0
0
1
0
8
0
0
0
0
0
1
0
0
0
0
9
1
0
0
0
0
1
1
0
0
1
10
0
0
0
0
0
0
0
0
0
0
11
0
0
0
1
0
0
1
1
0
1
12
0
0
0
0
0
1
1
0
0
1
13
1
0
0
0
0
1
0
0
0
0
14
0
1
0
0
0
0
0
0
0
0
15
1
0
0
0
0
0
0
0
0
0
16
1
0
0
0
0
0
0
0
0
0
17
0
0
0
0
0
0
0
0
0
0
18
1
0
0
0
0
0
0
0
0
0
19
1
0
0
0
0
0
0
0
0
0
20
0
0
0
0
1
0
0
0
0
0
Użytkownikowi, który wypożyczy f7 zostanie
zarekomendowany f6
6|Shanghai Triad (Yao a yao yao dao waipo qiao) (1995)|01-
Jan-1995)|0|0|0|0|0|0|0|0|1|0|0|0|0|0|0|0|0|0|0
7|Twelve Monkeys (1995)|01-Jan-1995|0|0|0|0|0|0|0|0|1|0|0|0|
0|0|0|1|0|0|0
Unknown|0, Action|1, Adventure|2, Animation|3, Children's|4,
Comedy|5, Crime|6, Documentary|7, Drama|8, Fantasy|9,
Film-Noir|10, Horror|11, Musical|12, Mystery|13, Romance|14,
Sci-Fi|15, Thriller|16, War|17, Western|18
user-to-user
●
cos(x,o1)=(1·1+0·1+0·0+0·
0+0·0+0·1+0·0+0·0+1·0+0
·0)/
(
√
1
2
+0
2
+0
2
+0
2
+0
2
+0
2
+0
2
+0
2
+1
2
+0
2
·
√
1
2
+1
2
+0
2
+0
2
+0
2
+1
2
+0
2
+0
2
+0
2
+0
2
)=1/
√
6<0.5
●
cos(x,o2)=1/
√
2>0.5
●
cos(x,o7)=1
Rekomendacje?
nr
uż\film
f1
f2
f3
f4
f5
f6
f7
f8
f9
f10
1
1
1
0
0
0
1
0
0
0
0
2
1
0
0
0
0
0
0
0
0
0
3
1
0
0
0
0
0
0
0
0
0
4
1
0
0
0
0
0
1
0
0
0
5
1
0
0
0
0
0
0
0
0
0
6
0
0
0
0
0
0
0
0
0
0
7
1
0
0
0
0
0
0
0
1
0
8
0
0
0
0
0
1
0
0
0
0
9
1
0
0
0
0
1
1
0
0
1
10
0
0
0
0
0
0
0
0
0
0
11
0
0
0
1
0
0
1
1
0
1
12
0
0
0
0
0
1
1
0
0
1
13
1
0
0
0
0
1
0
0
0
0
14
0
1
0
0
0
0
0
0
0
0
15
1
0
0
0
0
0
0
0
0
0
16
1
0
0
0
0
0
0
0
0
0
17
0
0
0
0
0
0
0
0
0
0
18
1
0
0
0
0
0
0
0
0
0
19
1
0
0
0
0
0
0
0
0
0
20
0
0
0
0
1
0
0
0
0
0
f1 f2 f3 f4 f5 f6 f7 f8 f9
f10
1 0 0 0 0 0 0 0 1
0
user-to-user
●
cos(x,o1)=(1·1+0·1+0·0+0·
0+0·0+0·1+0·0+0·0+1·0+0
·0)/
(
√
1
2
+0
2
+0
2
+0
2
+0
2
+0
2
+0
2
+0
2
+1
2
+0
2
·
√
1
2
+1
2
+0
2
+0
2
+0
2
+1
2
+0
2
+0
2
+0
2
+0
2
)=1/
√
6<0.5
●
cos(x,o2)=1/
√
2>0.5
●
cos(x,o7)=1
nr
uż\film
f1
f2
f3
f4
f5
f6
f7
f8
f9
f10
1
1
1
0
0
0
1
0
0
0
0
2
1
0
0
0
0
0
0
0
0
0
3
1
0
0
0
0
0
0
0
0
0
4
1
0
0
0
0
0
1
0
0
0
5
1
0
0
0
0
0
0
0
0
0
6
0
0
0
0
0
0
0
0
0
0
7
1
0
0
0
0
0
0
0
1
0
8
0
0
0
0
0
1
0
0
0
0
9
1
0
0
0
0
1
1
0
0
1
10
0
0
0
0
0
0
0
0
0
0
11
0
0
0
1
0
0
1
1
0
1
12
0
0
0
0
0
1
1
0
0
1
13
1
0
0
0
0
1
0
0
0
0
14
0
1
0
0
0
0
0
0
0
0
15
1
0
0
0
0
0
0
0
0
0
16
1
0
0
0
0
0
0
0
0
0
17
0
0
0
0
0
0
0
0
0
0
18
1
0
0
0
0
0
0
0
0
0
19
1
0
0
0
0
0
0
0
0
0
20
0
0
0
0
1
0
0
0
0
0
f1 f2 f3 f4 f5 f6 f7 f8 f9
f10
1 0 0 0 0 0 0 0 1
0
Nowemu użytkownikowi zostaną
zaproponowane filmy kupione
przez użytkowników 2 i 7
Algorytm rating-based filtering Slope One
●
f(x)=x+b
●
b – średnia różnica w
ocenach innych osób
●
x – ocena danego
użytkownika
●
Informacje innych
użytkowników o
danym przedmiocie
Informacje o innych
przedmiotach
ocenianych przez
danego użytkownika
Algorytm rating-based filtering Slope One
1. Średnia różnica pomiędzy elementami i i j:
O
ci
, O
cj
– oceny przedmiotów i,j przez użytkownika c
2. Przewidywana ocena przedmiotu i przez uż. t:
●
O
tc
– oceny przedmiotu c przez użytkownika t
●
w
ic
– liczba użytkowników, którzy ocenili przedmiot i
oraz c (
zwiększa wagę częściej ocenianych przedmiotów
)
●
S(u
t
) – podzbiór elementów ocenionych przez uż. t
Algorytm rating-based filtering Slope One
Średnia różnica pomiędzy elementami i i j:
●
Rekomendacje na podstawie przedmiotu E
i
obejmują
wszystkie elementy, dla których obliczono średnią
różnicę posortowane rosnąco
●
Rekomendacje dla użytkownika na podstawie
przedmiotu E
i
to elementy, dla których wyliczono
przewidywaną ocenę posortowane malejąco
Prosty przykład Slope One
●
f(x)=x+b
●
Średnia różnica: D
12
=3
●
Przewidywana ocena:
P
B2
=f(x)=4+(2-5)=1
P1
P2
A
5
2
B
4
?
Algorytm rating-based filtering Slope One
●
Średnia różnica
D12
:
●
Średnia różnica
D23
:
D
12
=
3−5+4−3
2
=−
0.5
D
23
=
2−3+5−2
2
=
1
Algorytm rating-based filtering Slope One
Jaką ocenę wystawi
Mark dla P
3
?
D31:2-5=-3
●
f(x)=3-3=0
ale też f(x)=4+1=5
skąd?
ostatecznie P
MarkP3
=
skąd?
0⋅15⋅2
21
=
3.33
Algorytm rating-based filtering Slope One
Jaką ocenę wystawi
Mark dla P
3
?
D31:2-5=-3
●
f(x)=3-3=0
ale też f(x)=4+1=5
skąd?
ostatecznie P
MarkP3
=
0 - wyliczone na podstawie jednej opinii,
5 – na podstawie dwóch
0⋅15⋅2
21
=
3.33
Modyfikacje
●
Wymagania:
macierz binarna
●
0 brak danych
→
●
1,2 nie lubi (0)
→
●
3,4,5 lubi (1)
→
nr
użytk\fi
lm
f1
f2
f3
f4
f5
f6
f7
f8
f9
f10
1
5
4 ?
?
?
4 ?
?
?
?
2
3 ?
?
?
?
?
?
?
?
?
3
4 ?
?
?
?
?
?
?
?
?
4
3 ?
?
?
?
?
5 ?
?
?
5
3 ?
?
?
?
?
?
?
?
?
6 ?
?
?
?
?
?
?
?
?
?
7
4 ?
?
?
?
2 ?
?
4 ?
8
1 ?
?
?
?
4 ?
?
?
?
9
5 ?
?
?
?
4
5 ?
?
4
10 ?
2 ?
?
?
?
?
?
?
?
11
2 ?
?
4 ?
?
3
3 ?
4
12 ?
?
?
?
?
4
5 ?
?
5
13
5 ?
?
?
?
4 ?
?
?
?
14 ?
4 ?
?
?
?
?
?
?
?
15
5 ?
?
?
?
?
?
?
?
?
16
5 ?
?
?
?
?
?
?
?
?
17 ?
?
?
?
?
?
?
?
?
?
18
4 ?
?
?
?
?
?
?
?
?
19
5 ?
?
?
?
?
?
?
?
?
20 ?
?
?
?
3 ?
?
?
?
?
Przykład
●
P
7
do P
10
=
(3-4+5-4+5-5)/3=0
●
P
7
do P
8
=(3-3)=0
●
f(x)=4+0=4 i
●
f(x)=3+0=3
●
f(x)
całk
=(4∙3+3∙1)/
/(3+1)=15/4≈
4
nr
użytk\f
ilm
f1
f2
f3
f4
f5
f6
f7
f8
f9
f10
1
5
4 ?
?
?
4 ?
?
?
?
2
3 ?
?
?
?
?
?
?
?
?
3
4 ?
?
?
?
?
?
?
?
?
4
3 ?
?
?
?
?
5 ?
?
?
5
3 ?
?
?
?
?
?
?
?
?
6 ?
?
?
?
?
?
?
?
?
?
7
4 ?
?
?
?
2 ?
?
4 ?
8
1 ?
?
?
?
4 ?
?
?
?
9
5 ?
?
?
?
4
5 ?
?
4
10 ?
2 ?
?
?
?
?
?
?
?
11
2 ?
?
4 ?
?
3
3 ?
4
12 ?
?
?
?
?
4
5 ?
?
5
13
5 ?
?
?
?
4 ?
?
?
?
14 ?
4 ?
?
?
?
?
?
?
?
15
5 ?
?
?
?
?
?
?
?
?
16
5 ?
?
?
?
?
?
?
?
?
17 ?
?
?
?
?
?
?
?
?
?
18
4 ?
?
?
?
?
?
?
?
?
19
5 ?
?
?
?
?
?
?
?
?
20 ?
?
?
?
3 ?
?
?
?
?
f1 f2 f3 f4 f5 f6 f7 f8 f9
f10
?
?
?
?
?
?
5
3
?
4
rzeczywista ocena
Porównanie algorytmów
●
●
X'-zbiór testowy
●
S(u) – zbiór przedmiotów ocenionych przez użytkownika u
●
count(X'), count(S(u)) – liczności X' i S(u)
●
u
i
,P(u
i
) – odp. ocena lub predykcja oceny dla użytkownika u
Wybór metody rekomendacji
Czynniki determinujące:
●
cel działania/rodzaj systemu,
●
branża,
●
sezonowość rynku/zmienność danych,
●
tzw. grupa docelowa użytkowników/klientów,
●
rodzaj danych wejściowych,
●
rozmiar listy rekomendacji,
●
rozmiar danych,
●
liczba użytkowników,
Często stosuje się hybrydę metod
(BellKor's
Pragmatic Chaos: kilkadziesiąt!)
Problemy
●
Wymagane jest pewne działanie początkowe
nowego użytkownika
●
Dane w postaci macierzy rzadkich
●
(Ponowna) identyfikacja użytkownika
●
Nie uwzględniają zmian:
–
np. dodanie nowego przedmiotu do oferty –
przedmiot nigdy nie znajdzie się na liście
rekomendacji
–
Zainteresowanie użytkownika nowym
przedmiotem
●
Sezonowość niektórych przedmiotów
Praktyczne wykorzystanie SlopeOne
●
G. Zięba „Implementacja algorytmu
personalizacji w systemie rekomendacji
produktów na przykładzie wybranego sklepu
internetowego”, praca magisterska, AGH,
Kraków, 2010
●
Open SlopeOne*+PHP+MySQL
*http://code.google.com/p/openslopeone/
,
Wykorzystanie SlopeOne – G.Zięba
●
Oceny w systemie:
–
Oceny użytkowników:
●
Manualnie
●
Automatycznie
–
Korelacja pomiędzy
przedmiotami
●
Identyfikacja użytkownika
–
Cookies – dla każdego użytkownika
–
Logowanie – składanie zamówienia/wola
użytkownika asocjacja wygenerowanych przed tą
→
akcją ocen z bieżącym użytkownikiem
Wykorzystanie SlopeOne – G.Zięba
●
Oceny w systemie:
–
Oceny użytkowników:
●
Manualnie
●
Automatycznie
–
Korelacja pomiędzy
przedmiotami
●
Identyfikacja użytkownika
–
Cookies – dla każdego użytkownika
–
Logowanie – składanie zamówienia/wola
użytkownika asocjacja wygenerowanych przed tą
→
akcją ocen z bieżącym użytkownikiem
Aktualizowane w tabeli
BD na bieżąco
Tabela korelacji
pomiędzy przedmiotami
aktualizowana raz na dobę
Wykorzystanie SlopeOne – G.Zięba
●
Redukcja anomalii:
–
Odrzucanie skrajnych wartości ocen
–
Usuwanie zbyt wielu ocen użytkowników
●
liczona jest średnia ocen użytkowników
●
usuwanie do 0.1% ocen dla użytkowników, którzy
wystawili znacznie więcej ocen niż średnia
●
Wykorzystano nierówność Czebyszewa
Wdrożenie w sklepie internetowym sprzedającym
przedmioty religijne G.Zięba
Dane: - 70% zamówień 32% zysku,
→
mała wartość < średniej
- 30% zamówień 68% zysku
→
duża wartość > średniej
- 16% osób ponawia zakupy
- 30% z nich w ciągu miesiąca
Cel: zwiększenie średniej
wartości zamówienia
Dobór ocen
Źródło: G. Zięba
automatycznych:
- na podstawie danych
archiwalnych
- analiza koszykowa +
zestawienia statystyczne
●
Oceny manualne:
–
Wystawiane przez użytkownika w skali 1 - 6
Wyniki:
●
Czas testów: 35 dni
●
Równolegle: dotychczasowy system
Źródło: G. Zięba
Wyniki
●
Cel : zwiększenie wartości pojedynczego
zamówienia
Źródło: G. Zięba
Podsumowanie wyników
Źródło: G. Zięba
Bibliografia
●
W. W. Cohen: Collaborative Filtering: A Tutorial, Carnegie Mellon University
●
G. Zięba: „Implementacja algorytmu personalizacji w systemie rekomendacji
produktów na przykładzie wybranego sklepu internetowego”, praca
magisterska, AGH, Kraków, 2010
●
D. Lemire, A. Maclachlan, Slope One Predictors for Online Rating-Based
Collaborative Filtering, in SIAM Data Mining, 21-23, 2005
●
Wikipedia: en.wikipedia.org