Collaborative Filtering with Privacy via Factor Analysis

Data Mining

Seminar im Sommersemester 2005

Prof. Dr. Thomas Hofmann,Dipl. Inform. Steffen Hartmann

TU Darmstadt, Fachbereich InformatikFachgebiet: Intelligente Systeme

Stefan Seiermann

Collaborative Filtering with Privacy via Factor Analysis

21.06.2005 Collaborative Filtering with Privacy via Factor Analysis 2

Inhalt

• Einleitung

• Problemstellungen

• Das Wahrscheinlichkeitsmodell

• Aspekte der Vertraulichkeit

• Verwandte Arbeiten

• Fazit & Ausblick


1 Einleitung

Hintergrund:

Menschen nutzen oft „Empfehlungen“ von anderen Personen mit ähnlichen Interessen, falls Sie keine weiteren Informationen für eine Handlungsauswahl besitzen.

Beispiele: Bücher, CD´s, Restaurants, ...

Automatisierung durch: „Collaborative Filtering“

Berechnung von Ähnlichkeiten zwischen dem eigenem Verhalten und dem Verhaltenvon anderen Benutzern durch den Einsatz von Datenbanken.

• Generiert Aussagen, wie z.B.:„Benutzer wie Sie, haben folgende Artikel betrachtet (gekauft, gemocht, …)“

• Unterstützen den Benutzer bei der Auswahl von Produkten (Entscheidungen)

Beispiel: "Empfehlungen" eines Web-Buchhändlers


1 Einleitung

Anwendungsmöglichkeiten:

• e-Commerce• Empfehlungssysteme („recommendation systems“) für:

Filme, Musik, Restaurants, Nachrichten, Witze, etc.

Die Erhebung der Daten für eine Bewertung:

a) Explizit

• Durch die Bewertung eines Artikels auf einer Skala• Durch das Erstellen einer Rezension (wie z.B. bei Büchern)

b) Implizit

• Durch den Kauf eines Artikels auf einer Web-Seite, meist mit persönlichen Daten verknüpft (Anschrift, etc.)

• Durch das Anklicken, Verweilen, Wechseln einer Web-Seite• Durch Standortinformationen bei der Auswahl

(wie z.B. GSM-, UMTS- oder WLAN-Standorte)

Beispiel: Bewertung eines Artikel durch einen Kunden


1 Einleitung

1.1 Beispiel: „Movielens“

Beispiel für Bewertungen in einer Filmdatenbank (Movielens, 2003)

• Bewertung von Spielfilmen durch die Benutzer, anhand der Vergabe von „Sternen“• Erfordert eine Identifizierung des Benutzers durch das System

Ziel: Personalisierte Empfehlungen von Filmen durch: „Collaborative Filtering“


2 Problemstellungen

a) „Lückenhafte“ Datenbanken ( Kapitel 3)

Beispiel: Ein einzelner Kunde eines Web-Buchladens (z.B. Amazon.com)bewertet nur einen Bruchteil des Angebotes an Büchern.

Die durchschnittliche „Besetzung“ einer Filmdatenbank (z.B. EachMovie) mit Bewertungen beträgt nur ca. 3%, andere Datenbanken erreichen hingegen nur einen Wert von ca. 0.01%-0.1% der möglichen Bewertungen.

Dieses kann zu einer fehlerhaften Interpretation der Daten und somit auch zu fehlerhaften Empfehlungen führen.

b) Vertraulichkeit der Benutzerdaten ( Kapitel 4)

• Die personalisierten Daten der Benutzer können von den Betreibern unkontrolliert weiterverwendet, mit anderen Daten verknüpft oder weitergegeben werden (SPAM).

• Der Anwender hat keinerlei Kontrolle mehr über diese Vorgänge.(Beispiel: Mögliche Kontrolle des Leseverhaltens in US-Buchläden)

Tatsächlich stellen solche Daten aber einen hohen Wert für ein Unternehmen dar.


3 Das Wahrscheinlichkeitsmodell

3.1 GrundlagenZiel: Entwicklung eines Wahrscheinlichkeitsmodells zur Vorhersage des Benutzerverhaltens durch Beobachtung.

Extrapolieren von beobachteten Bewertungen zur Erstellung von Empfehlungen,durch die Verwendung der linearen Faktor-Analyse.

Verwendete Größen:

m Die Anzahl der Benutzer einer Empfehlungsdatenbank

n Die Anzahl der zu bewertenden „Artikel“, wie z.B. Filme in einer Filmdatenbank

k Anzahl der „Benutzerprofile“ (preference space)Diese kann z.B. eine Vorliebe eines Benutzers für bestimmte Filmtypen enthalten.(k liegt zwischen 4 und 20, k<<n, k<<m)



mnnn

m

m

yyy

yyy

yyy

Y

,2,1,

,22,21,2

,12,11,1

...

............

...

...

mkkk

m

m

xxx

xxx

xxx

X

,2,1,

,22,21,2

,12,11,1

...

............

...

...

3.1 Grundlagen (Forts.)Verwendete Matrizen:

Y: Bewertungen

• Dimension: Artikel x Benutzer (n x m)

• Enthält die beobachteten Bewertungen der Benutzer für die zu bewertenden Artikel. Beispiel: yi,j=5 entspricht einer

Bewertung des Benutzers j für den Film i von 5 Punkten, auf einer Werteskala (z.B. von 0 bis 10 Punkte).

X: Benutzerprofile • Dimension: Benutzerprofile x Benutzer (k x m)• Enthält die Vorlieben eines Benutzers für eine bestimmte

Artikelgruppen, z.B. Vorlieben für bestimmte Filmtypen.Diese Matrix wird im Laufe des Algorithmus automatischgeneriert.



3.1 Grundlagen (Forts.)

A: "Zielmatrix"

• Dimension: Artikel x Benutzergruppen (n x k)• Matrix, die durch den Algorithmus berechnet werden soll.

N: Rauschen („Noise“)

• Dimension: Artikel x Benutzer (n x m)• Enthält das typische Rauschen bei der Bewertung eines Artikels durch einen Benutzer.

Varianz über die Bewertung der Artikel:

• VAR (Ni) = Initialisierung mit Gausscher Verteilung• Annahme: Alle VAR(Ni) sind identisch

knnn

k

k

aaa

aaa

aaa

A

,2,1,

,22,21,2

,12,11,1

...

............

...

...

mnnn

m

m

nnn

nnn

nnn

N

,2,1,

,22,21,2

,12,11,1

...

............

...

...

i

Varianz VAR(Ni) =



3.2 Lineare RegressionLineares Modell für eine Bewertungsdatenbank:

a) Falls X und Y zur gleichen Zeit bekannt sein sollten, handelt es sich um ein Problem, welches sich mit linearen Regression lösen lässt.

b) Falls X nicht bekannt sein sollte, handelt es sich um ein Problem, welches sich mit Hilfe der Faktor-Analyse lösen lässt.

Ziele:

• Berechnung von A, wobei X mit Zufallswerten nach einer Gaußschen Verteilung initialisiert wird (lineare Regression). "schnelles" Verfahren

"Lücken" in Y werden mit Mittelwerten (über alle Benutzer & Artikel) gefüllt,aber nur in diesem Berechnungs-Schritt.

• Die somit erhaltenen Werte für A können dann für eine Faktor-Analyse verwendet werden.

NAXY (1)



3.2 Lineare Regression (Forts.)Vorgehen:

• Initialisierung von X mit Zufallswerten nach Gausscher Verteilung• Durchführung der folgenden Berechnungen (ca. 10 Iterationen):

1)(

1T

)(

)(

TTp

T

xxyxA

yAAAx(2)

Hinweise:

• A(p) = Wert von A nach der p. Iteration• A = Wert von A vor der p. Iteration• Alle zu invertierenden Matrizen besitzen die Dimension k x k (Zeitfaktor!)• k ist unabhängig von der Anzahl der Benutzer oder Artikel (4 <= k <=20)• A = (ATA)-1AT : sog. "Pseudoinverse". Vorteil: quadratisch,

Nachteil: AA = (ATA)-1(ATA) = I, aber AA = "nicht immer" I.

A



3.3 Faktor-Analyse

• Statistisches Verfahren

• Gegeben ist eine Vielzahl von möglicherweise voneinander abhängigen Variablen (z.B. Beobachtungen von Personen).

• Gesucht ist eine geringe Anzahl von untereinander unabhängigen „Einfluss-Faktoren“. Diese Faktoren sind nicht „beobachtbar“, sie „verbergen“ sich in den Variablen. Faktoren können aber aus den Variablen isoliert werden.

Ziel: Generierung der Faktoren, mit welchen sich die Merkmale der Variablen (Beobachtungen) besonders gut erklären lassen.

• Anwendungen: Beobachtungen in der Chemie, Psychologie, Wirtschaft (z.B. Kundenverhalten), …

• Beispiel: Automatische, angeborene Faktor-Analyse von menschlichen Gesichtern.

Umkehrung: Visualisierung von Zusammenhängen durch sog. „Chernoff-Gesichter“, für bis zu 19 Dimensionen (Wandmacher, 1993).



3.3 Faktor-Analyse (Forts.)

nn

j

i

I

,...00

...1......

0...00

0...01Zusätzliche Matrix (für jeden Benutzer j):

Ij: "Trimming-Matrix"

• Dimension: Artikel x Artikel (n x n)

• Enthält auf der Hauptdiagonalen eine "1", falls der Benutzer j den Artikel i bewertet hat, sonst "0".

Einschränkung der weiteren Berechnung auf Artikel, die der Benutzer schon bewertet hat. =

I: Einheitsmatrix

• Dimension: Benutzerprofile x Benutzerprofile (k x k)

i

i

1...00

............

0...10

0...01

I



3.3 Faktor-Analyse (Forts.)Algorithmus: EM-FaktoranalyseExpectation Maximization (Newcomb, 1887 Dempster, Laird & Robin, 1977)

Motivation:

• Einfacher rekursiver Algorithmus (2 Schritte, E- & M-Schritt)• Sicherer Umgang mit dünn besetzten Matrizen (keine "Default-Annahmen")• Lässt sich für den vertraulichen Umgang mit Benutzerdaten adaptieren

Vorgehen ("distributed EM-Faktor-Analyse")

• Initialisierung A, mit Werten aus der linearen Regression• Schritt 1: Anwender (Clients) berechnen A', B, C aus A und Server• Schritt 2: "Totalizer" (Server) berechnet neues A und aus allen A', B, C Clients• weiter mir Schritt 1, bis Konvergenz (ca.15-25 Iterationen), oder bei Änderungen

Client: berechnet A',B,C Client: berechnet A',B,CServer: berechnet A,

A, A,

A',B,CA',B,C




jTjjj

jTjj

jj

yAMx

AAIM

AIA

1)( (3)

jTj

jj

Tjj

jj

jTjjj

j

j

yyn

C

xyn

B

MxxIn

A

1

1

)(1'

(4)

= Kronecker-Produkt (Anhang B)

Schritt 1: Berechnungen der Benutzer (Clients):(nur für die eigenen Bewertungen)

Berechnung nur für Artikel, die auch vom Client bewertet wurden

Berücksichtigung der Varianz

aus (2)

Berechnung von A', B, C

Formeln zur Berechnung ergeben sich aus dem Maximize-Schritt (M-Schritt) des EM-Algorithmus




m

j jp

jp

m

j j

m

jj

p

BAspurCm

BLAAL

1

)()(

1

1

1

')(

))((1

)()()(

(5)

Schritt 2: Berechnung der Summen (über alle Benutzer m):

Iterative Berechnung von A und

(L(A) Anhang B)

Formeln zur Berechnung ergeben sichaus dem EM-Algorithmus

Ergebnis (Modell: A, ):

• Dieses Modell wurde aus allen Bewertungen von allen Benutzern berechnet.

• Ein Benutzer kann jetzt mit Hilfe dieses Modells (A, ) sich eigene Empfehlungen, auf der Basis seiner Bewertungen, berechnen lassen.

Aufwand: O(n m k2) je Iteration, günstig bei großen Datenbanken



3.3 Faktor-Analyse (Forts.)Vorhersage einer Bewertung für Benutzer j:

• yj = Bewertungen des Benutzers j• Benutzer j kennt A, • Berechnung von xj aus (3)• Fehlende Bewertungen (=Empfehlungen) durch die Berechnung von y=A xj

"Persönliche Empfehlungen" für Benutzer j:

Korrektur der Mittelwerte:• Annahme der Faktoranalyse ist, dass die

Bewertungen der Benutzer den Mittelwert: 0 haben.• Vor der Berechnung des Modells (A, ) werden die Bewertungen durch einen

Schätzwert korrigiert (subtrahiert). Bei der Verwendung einer Empfehlung (s.O.) muss dieser Schätzwert wieder auf die Empfehlungen addiert werden.

Ermittlung des Schätzwertes:• Mittelwert aller Bewertungen eines Artikels (z.B. falls #Benutzer >> #Artikel)• Mittelwert aller Bewertungen eines Benutzers

)00001030500(jy

)21891033572(jy


4 Aspekte der Vertraulichkeit

Die verteilte Faktor-Analyse kann durch iterative Vektoradditionen der Benutzer-Daten (A', B, C) auf einem Server durchgeführt werden (5).

Wie kann hierbei die Vertraulichkeit der Benutzerdaten sichergestellt werden?

Verschlüsselung mit einem asymmetrischen Schlüssel p: ( nächste Seite)

Jeder Client sendet nur seine verschlüsselten Daten E(Mj) = E(A', B, C)

Nutzung des "Homomorphismus" von Verschlüsselungs-Methoden (z.B. RSA):

Der Server kann die Additionen der Benutzerdaten (A', B, C) durch Multiplikationen der verschlüsselten Nachrichten E(M j) der Benutzer durchführen.

)()()( 2121 MMEMEME (6)

Client 1: berechnet A',B,C Client n: berechnet A',B,CA',B,CA',B,C

4.1 Verschlüsselung

Server



4.2 Key Sharing

Erzeugung eines verteilten El-Gamal-Schlüsselpaares(Nach der Methode von Pendersen)

n = # User, a = # "trusted Users", wähle t, so dass t > (1-a)n Beispiel: Benutzer online = 60% -> t > 0.4n

• Public Key p, dieser ist jedem Benutzer bekannt

• Private Key s, wobei jeder Benutzer nur einen "Teil" des Schlüssels (si) kennt

s kann aber wieder aus t+1 "Teilschlüsseln" si konstruiert werden

A, A,

Server berechnet A, aus den verschlüsselten Werten der Clients

Client 1 Client n



4.2 Key Sharing (Forts.)

• Um das verschlüsselte Ergebnis des Servers (A, ) zu entschlüsseln, müssen die Benutzer dieses jeweils mit Ihrem Teilschlüssel s i entschlüsseln.

• Durch das Zusammensetzten der entschlüsselten (Teil-)Ergebnisse kann nun (A, ) berechnet und nach Kapitel 3.3 eine persönliche Empfehlung generiert werden.

• Bei diesem Protokoll werden zu keiner Zeit unverschlüsselte Bewertungsdaten der Benutzer übertragen

Sicherung der Vertraulichkeit der Benutzerdaten.

Nachteile:

• User können ungültige Werte (z.B. außerhalb der Bewertungsskala) übertragen• Server können Ergebnisse der User unterschlagen oder duplizieren

Einsatz eines ZKP-Protokolls ("zero-knowledge proofs"), sind (A', B, C) gültig?Dieses ist wirksam bis zu einem Anteil von ca. 20% "Betrügern"(Beispiel für den Einsatz von ZKP: Authentifizierungsprotokolle)


5 Verwandte Arbeiten

Vergleich des NMAE ("Normalized Mean Absolut Error", nach Goldberg) mit anderen Methoden:

• "Pearson correlation" ( Anhang C)• "Personality diagnosis"

1. Witz-Datenbank ("Jester")

100 Artikel x 18.000 BenutzerBewertungen: ca. 50 %

Performance: + 14 % (Standard)+ 5 % (Pearson)

2. Film-Datenbank ("EachMovie")

1.600 Artikel x 73.000 BenutzerBewertungen: ca. 3 %

Performance: +18 % (Standard)+ 9 % (Pearson)

Performance-Zugewinn, speziell bei besonders "dünn besetzten" Datenbanken Performance-Vergleiche (Canny, 2002)

"besser"

Standard: Durchschnittliche Bewertung eines Artikel über alle Benutzer

(>0,07%)


6 Fazit und Ausblick

• Mit der Faktor-Analyse, aufbauend auf einem linearen Modell, können effizient Empfehlungen für Produkte, basierend auf den Bewertungen (keine "binäre" Daten) anderer Benutzer, berechnet werden ("Recommending System").

• Dieses ist besonders für lückenhafte, "dünn besetzte" Datenbanken geeignet,wie sie bei Empfehlungssystemen häufig auftreten.

• Durch den Einsatz eines verteilten Systems (Server, Clients) und der Verwendung von verteilten Schlüsseln ist die Vertraulichkeit der Benutzerdaten gewährleistet.

• Durch eine Erweiterung der Methode mit sog. "Meta-Daten" (Attribute) kann eine weitere

Performance-Steigerung erreicht werden. Beispiele: Kategorien, Beschreibungen, Texte, ...

Dieses ist besonders wichtig bei "neuen" Produkten, die bisher noch keinerlei Bewertungen der Benutzer aufweisen.

Der Einsatz von Metadaten (Canny, 2002)


Literaturverzeichnis

Canny, J. (2002). Collaborative Filtering with Privacy via Factor Analysis, Annual ACM Conference on Research and Development in Information Retrieval. Proceedings of the 25th annual international ACM SIGIR conference on Research and development. Retrieved 12.06.2005, from http://www.cs.berkeley.edu/~jfc/'mender/sigir.pdf

Canny, J. (2002). Some techniques for privacy in ubicomp and context-aware applications. In UBICOMP-2002, Goteborg, Sweden, Sept. 2002. Retrieved 12.06.2005, fromhttp://guir.berkeley.edu/pubs/ubicomp2002/privacyworkshop/papers/ubicomp.pdf

Kamps, T. & Frommholz, I. (2004). Industrielle Wissensanwendungen. Skript zur Vorlesung im SS 2004.Fraunhofer Institut für integrierte Publikations- und Informationssysteme. TU-Darmstadt.Retrieved 12.06.2005, from http://www.ipsi.fraunhofer.de/~brocks/IndustrielleWissensanwendungen-SS04.html

Movielens (2003). Movielens - Project Homepage. Group Lens Research.

University of Minnesota. Department of Computer Science and Engineering.Retrieved 12.06.2005, from http://movielens.umn.edu/login

Pedersen, T. (2001). A Gentle Introduction to the EM-Algorithm. Department of Computer Science.University of Minnesota Duluth. Retrieved 12.06.2005, from http://www.d.umn.edu/~tpederse/Pubs/emnlp01-em-slides.pdf

Wandmacher, J. (1993). Mensch-Computer-Kommunikation – Grundwissen 2: Software-Ergonomie. Berlin: Walter de Gruyter.

Wikipedia (2005). Online-Enzyklopädie. Div. Artikel über die lineare Algebra, wie z.B. das Kronecker-Produkt. Wikimedia Foundation. Florida, USA. Retrieved 12.06.2005, from http://de.wikipedia.org/wiki/Kronecker-Produkt


Vielen Dank für Ihre Aufmerksamkeit


Anhang A

Münzwurf als MLE-Beispiel (Pedersen, 2001)

Maximum Likelihood Estimates (am Beispiel von Münzwürfen):


Anhang B

Das Kronecker-Produkt:

Beispiel für die Berechnung des Kronecker-Produkts (Wikipedia, 2005)

L(A) - "Stacking" von A - Beispiel:

43

21A

4231

)(AL


Anhang C

Pearson User to User Korrelation

Berechnung der Pearson-Korrelation (aus: Kamps & Frommholz, 2004)

1. Schritt: Berechnung der Korrelation zwischen den Benutzern a und u:


Anhang C

Pearson User to User Korrelation (Forts.)

2. Schritt: Berechnung der Empfehlungen

Vorhersage für den Artikel i (aus: Kamps & Frommholz, 2004)

• Um für User a Empfehlungen zu generieren, werden die nUser mit höchster Pearson-Korrelation ausgewählt (50<n<200)

• Für jedes Item i wird eine Voraussage pa,i gemacht,wie User a das Item i bewerten würde.

Empfehlung = Items mit höchstem pa,i

Hinweis: Es erfolgt eine Modifizierung der Korrelation, je nach "Güte" (Anzahl der gemeinsam bewerteten Artikel m).

Documents

Collaborative Filtering with Privacy via Factor Analysis