Ansätze für gemeinschaftliches Filtering
Matthias Attenbrunner 06.Dezember 2013
Seminar zur Personalisierung großer Daten
Übersicht:
1. Problemdarstellung
2. Definition von gemeinschaftlichen Filtering
3. Arten des gemeinschaftlichen Filtering
4. Grundlagen des gemeinschaftlichen Filtering
5. Model Based (Modellbasierende) Algorithmen
6. Memory Based (Speicherbasierende) Algorithmen
a) User-Based Collaborated Filtering
b) Item-Based Collaborated Filtering
c) Vergleich
7. Vor- und Nachteile
8. Einsatzgebiete
2 Ansätze für gemeinschaftliches Filtering
1. Problemdarstellung:
• Große Informationsflut seit Anfang der 90er
Verlust der Übersicht des Einzelnen über die Informationen, die er benötigt oder nützlich sind
Unternehmen müssen neue Wege finden die Informationen neu zu bewerten und zu nutzen
4 Ansätze für gemeinschaftliches Filtering
1. Problemdarstellung:
• Unterschiede des Internets zu andere Massenmedien
One-To-Many-Kommunikation: Fernsehen, Radio, etc
Many-To-Many-Kommunikation: Internet
5 Ansätze für gemeinschaftliches Filtering
4. Grundlagen des gemeinschaftlichen Filtering:
Grundidee:
Hat man eine große Anzahl an Benutzern und ihre
Bewertungen bzw Gewohnheiten, kann man diese
vergleichen, Ähnliche finden und daraus Lücken in den
Bewertungen dieser Benutzer schließen.
11 Ansätze für gemeinschaftliches Filtering
4. Grundlagen des gemeinschaftlichen Filtering:
13 Ansätze für gemeinschaftliches Filtering
• Erhebung von Benutzerdaten:
– Logindaten (z.B.: Seitenaufrufe, Logindauer, …)
– Suchanfragen
– Kommentare
– Befragungen
– Bewertungen • nominale Daten (z.B.: Augenfarbe, Gut/Schlecht, 1/0, …)
• ordinale Daten (z.B.: {schlechter, schlecht, neutral, gut, besser})
• interval (z.B.: Kalenderdaten, Temperatur in Grad/Fahrenheit, …)
• Ratio (z.B: Alter, Längenangaben, …)
– sekundäre Erhebung (z.B.: Ankauf von existierenden Matrizen)
4. Grundlagen des gemeinschaftlichen Filtering:
14 Ansätze für gemeinschaftliches Filtering
• Proximitätsberechnung:
Berechnung der Ähnlichkeit zwischen dem aktiven Benutzer
bzw. dessen bewertete Items mit denen in der Datenbank
gespeicherten.
4. Grundlagen des gemeinschaftlichen Filtering:
15 Ansätze für gemeinschaftliches Filtering
• Auswahl der Mentoren:
1. Ähnlichkeit muss berechnet worden sein
2. Die Mentoren müssen sich um mindestens einmal unterscheiden
3. Die Mentoren können eine Mindestähnlichkeit besitzen
4. Die Mentoren können nur eine positive Mindestähnlichkeit besitzen
4. Grundlagen des gemeinschaftlichen Filtering:
16 Ansätze für gemeinschaftliches Filtering
• Prognose:
Berechnung von Prognosen auf der Bewertungen der zuvor ausgewählten Mentoren.
• Grundidee:
1. Auswahl sog. Trainingssets (eine aus der Datenmatrix ausgewählte Teilmatrix)
2. Offlineberechnung der Parameter eines Modells
3. Berechnung der Prognose auf Basis der Parameter
Ansätze für gemeinschaftliches Filtering 18
5. Model Based (Modellbasierende) Algorithmen:
• Vorteile:
Prognose, die online berechnet wird, ist viel schneller
• Nachteile:
Bei der Modellbildung kann ein Informationsverlust entstehen
Ansätze für gemeinschaftliches Filtering 19
5. Model Based (Modellbasierende) Algorithmen:
• Arten:
– Clustermodelle
– Bayessche Netzwerke
– Regelbasierende (rule-based) Annäherung
– Neuronale Netzwerke
– ….
Ansätze für gemeinschaftliches Filtering 20
5. Model Based (Modellbasierende) Algorithmen:
Definition:
– Liste von m Benutzer : U = {u1, u2, … , um}
– Liste von n items (Artikel/Objekte): I = {i1, i2, … , in}
– Liste von items von Benutzer ui : Iui
– Liste von Benutzer von item ii : Uii
– Aktiver Benutzer: ua
– Rating von Benutzer u und item i : rui
Ansätze für gemeinschaftliches Filtering 22
6. Memory Based (Speicherbasierende) Algorithmen:
Grundlagen:
1. Die Ähnlichkeiten der Benutzer berechnen und in eine
(Benutzer X Benutzer) – Matrix eintragen
2. Auswahl der k ähnlichsten Nachbarn (Mentoren)
3. Berechnung der Fehlenden Bewertungen auf Basis der k Mentoren
Ansätze für gemeinschaftliches Filtering 23
6. Memory Based (Speicherbasierende) Algorithmen: a) User-Based Collaborated Filtering
Ansätze für gemeinschaftliches Filtering 24
6. Memory Based (Speicherbasierende) Algorithmen: a) User-Based Collaborated Filtering
Proximitätsberechnung:
• Betrachtung der Informationen als Vektoren • Berechnung der Ähnlichkeit über die Cosinus-Vektor-Ähnlichkeit
ba
baba
xx
xxxx
),cos(
6. Memory Based (Speicherbasierende) Algorithmen: a) User-Based Collaborated Filtering
Proximitätsberechnung:
• Übertragen auf das Bewertungssystem indem ein Benutzer u als xu betrachtet wird
• xui = rui falls eine Bewertung bei i vor liegt und anders 0
Formel für Benutzer u und v:
Iuv beschreibt die Items die beide Benutzer bewertet haben
Ansätze für gemeinschaftliches Filtering 25
vu
uv
Ij
vj
Ii
ui
Ii
viui
vu
rr
rr
xxvuCV22
),cos(),(
6. Memory Based (Speicherbasierende) Algorithmen: a) User-Based Collaborated Filtering
Proximitätsberechnung:
Rausfilten der Mittleren Differenz und der Unterschiedlichen Bewertungsarten der Benutzer u und v
Verwendung der Pearson Korrelation
Ansätze für gemeinschaftliches Filtering 26
uvuv
uv
Ii
vvi
Ii
uui
Ii
vviuui
rrrr
rrrr
vuPC22 )()(
))((
),(
6. Memory Based (Speicherbasierende) Algorithmen: a) User-Based Collaborated Filtering
Berechnung der wahrscheinlichen Bewertung:
• Berechnung über das arithmetisches Mittel:
wobei rvi = 0 falls nicht bewertet und
Ansätze für gemeinschaftliches Filtering 27
Uv
vi
Uv
vi
uirf
r
r)(
ˆ
:}1,0{: f {0, falls keine Bewertung vorliegt
1, falls eine Bewertung vorliegt
6. Memory Based (Speicherbasierende) Algorithmen: a) User-Based Collaborated Filtering
Berechnung der wahrscheinlichen Bewertung:
• Berechnung über die Summation der Top-N-Bewertungen:
wobei N(u) die k-nähesten-Nachbarn von u sind und Ni(u) die das Item i bewertet haben.
Problem: Alle Mentoren zählen gleich viel
Ansätze für gemeinschaftliches Filtering 28
)()(
1ˆ
uNv
vi
i
ui
i
ruN
r
6. Memory Based (Speicherbasierende) Algorithmen: a) User-Based Collaborated Filtering
Berechnung der wahrscheinlichen Bewertung:
• Berechnung über die gewichtete Summation der Top-N-Bewertungen :
wobei wuv die Ähnlichkeit der Benutzer angibt.
Problem: Benutzer verwenden verschiedene Bewertungen
Ansätze für gemeinschaftliches Filtering 29
)(
)(ˆ
uNv
uv
uNv
viuv
ui
i
i
w
rw
r
6. Memory Based (Speicherbasierende) Algorithmen: a) User-Based Collaborated Filtering
Berechnung der wahrscheinlichen Bewertung:
• Berechnung über den Ansatz von Resnick und Breese (Mittlere Zentrierung):
wobei das arithmetische Mittel.
Problem: Erfasst nicht wie weit die Bewertungen variieren
Ansätze für gemeinschaftliches Filtering 30
)(
)(
)(
ˆ
uNv
uv
uNv
vviuv
uui
i
i
w
rrw
rr
ur
ur
6. Memory Based (Speicherbasierende) Algorithmen: a) User-Based Collaborated Filtering
Berechnung der wahrscheinlichen Bewertung:
• Berechnung über Z-score Normierung:
wobei die Standartabweichung ist.
Ansätze für gemeinschaftliches Filtering 31
)(
)(
/)(
ˆ
uNv
uv
v
uNv
vviuv
uuui
i
i
w
rrw
rr
u
Grundlagen:
1. Die Ähnlichkeiten der Benutzer berechnen und in eine
(Item X Item) – Matrix eintragen
2. Auswahl der k ähnlichsten Nachbarn (Mentoren)
3. Berechnung der Fehlenden Bewertungen auf Basis der Ähnlichkeiten
Ansätze für gemeinschaftliches Filtering 32
6. Memory Based (Speicherbasierende) Algorithmen: b) Item-Based Collaborated Filtering
Proximitätsberechnung:
Berechnung mittels korrelationsbasierende Ähnlichkeit:
beschreibt die Benutzer der beide Items bewertet haben
Ansätze für gemeinschaftliches Filtering 33
6. Memory Based (Speicherbasierende) Algorithmen: b) Item-Based Collaborated Filtering
ijij
ij
Uu
juj
Uu
iui
Uu
jujiui
rrrr
rrrr
jiPC22 )()(
))((
),(
ijU
6. Memory Based (Speicherbasierende) Algorithmen: b) Item-Based Collaborated Filtering
Berechnung der wahrscheinlichen Bewertung:
• Berechnung über Z-score Normierung:
wobei die Standartabweichung ist.
Ansätze für gemeinschaftliches Filtering 34
)(
)(
/)(
ˆ
iNj
ij
j
iNj
jujij
iiui
u
u
w
rrw
rr
i
• Genauigkeit:
– Wenigere vertrauenswürdigere Mentoren sind besser – Viel weniger Items als Benutzer in der Matrix vorhanden
Item-Based besser
– Viel weniger Benutzer als Items in der Matrix vorhanden
User-Based besser
• Effizienz:
– Weniger Items als Benutzer in der Matrix vorhanden
Item-Based besser
– Weniger Benutzer als Items in der Matrix vorhanden
User-Based besser
Ansätze für gemeinschaftliches Filtering 35
6. Memory Based (Speicherbasierende) Algorithmen: c) Vergleich
• Stabilität:
– Bei gleichbleibender Item-Angebot
Item-Based besser
– Bei gleichbleibender User-Pool
User-Based besser
• Neue Empfehlungen:
User-Based ergibt hin und wieder Vorschläge aus anderen Bereichen
Ansätze für gemeinschaftliches Filtering 36
6. Memory Based (Speicherbasierende) Algorithmen: c) Vergleich
7. Vor- und Nachteile
Vorteile
• Ermitteln von Objekteigenschaften entfallen
• Austausch von Erfahrungen vieler Benutzer
• Beziehungen von Benutzern werden aufgedeckt
• Empfehlungen auch wenn nicht danach gesucht wird
Nachteile
• Cold-Start-Problem
• Black-Box-Problem
• Synonym-Problem
• Shilling attacks
• Zufällige zusammenhänge Falsche Empfehlungen
• Objekteigenschaften nicht miteinbezogen
• geringer Datenschutz
Ansätze für gemeinschaftliches Filtering 38
8. Einsatzgebiete
• große Benutzer- und Objektanzahl
• keine Einordnung der Items in objektive Eigenschaften möglich bzw. subjektive Bewertungen besser
Literatur, Musik, Videos, Filme, Websieten, Restaurants
Amazone, Ebay, etc
Ansätze für gemeinschaftliches Filtering 40