Studieguide for TDT4215 Anbefalingssystemer

Grunnideen

Innholdsbasert filtrering (content-based filtering, CB) anbefaler elementer som ligner på det brukeren har likt tidligere. Systemet representerer hvert element som en vektor av egenskaper (features), bygger en brukerprofil fra brukerens historikk, og beregner likhet mellom profilen og ubesøkte elementer.

Fordelen er at metoden er uavhengig av andre brukere — den fungerer for nye brukere med litt historikk og er fullt forklarbar («vi anbefaler dette fordi du likte X som har egenskapene Y og Z»).

Representasjon av elementer

Elementer kodes som vektorer. For en filmapplikasjon kan vektoren inneholde: sjanger (action=1/0, komedie=1/0, ...), regissør (one-hot), skuespillere, produksjonsår (normalisert), spilletid. For nyhetsartikler brukes typisk TF-IDF-vektorer over ord.

Formell notasjon: element $i$ representeres som $\mathbf{x}_i \in \mathbb{R}^d$ der $d$ er antall egenskaper.

Brukerprofil

Brukerprofilen $\mathbf{p}_u$ er et vektet snitt av egenskapsvektorene til elementer brukeren har samhandlet med, vektet etter brukerens rating: $\displaystyle \mathbf{p}_u = \frac{\sum_{i \in I_u} r_{ui} \cdot \mathbf{x}_i}{\sum_{i \in I_u} r_{ui}}$ der $I_u$ er mengden av elementer brukeren $u$ har vurdert og $r_{ui}$ er ratingen.

Likhetsmål — kosinuslikhet

Kosinuslikhet er det vanligste likhetsmålet i CB: $\displaystyle \text{cos}(\mathbf{a}, \mathbf{b}) = \frac{\mathbf{a} \cdot \mathbf{b}}{\|\mathbf{a}\| \cdot \|\mathbf{b}\|}$. Verdien ligger mellom -1 og 1 (for enhetsvektorer: 0 til 1). Resultatet er uavhengig av vektorenes lengde — to dokumenter med samme innhold men ulikt antall ord gir kosinuslikhet 1.

TF-IDF for tekstbasert CB

Når elementbeskrivelsene er tekst (artikler, produktbeskrivelser), brukes TF-IDF til å lage vektorer: $\displaystyle \text{TF-IDF}(t, d) = \frac{f_{t,d}}{\sum_k f_{k,d}} \cdot \log\frac{N}{df_t}$ der $f_{t,d}$ er antall forekomster av term $t$ i dokument $d$, $N$ er totalt antall dokumenter, og $df_t$ er antall dokumenter som inneholder $t$. TF-IDF gir høy vekt til termer som er vanlige i dokumentet men sjeldne i korpuset.

Diskriminerende ord — Gini-indeks

I innholdsbaserte systemer vil vi velge ut ord/egenskaper som best skiller mellom relevante og ikke-relevante elementer for en bruker. Gini-indeksen for et ord $w$ måler hvor «ren» ratingfordelingen er blant elementene som inneholder ordet: $\displaystyle \text{Gini}(w) = 1 - \sum_{j=1}^{t} p_j(w)^2$, der $p_j(w)$ er andelen elementer med rating-verdi $j$ (f.eks. interessant / ikke-interessant) blant elementene som inneholder $w$. Lav Gini betyr at ordet er sterkt diskriminerende (nær 0 = perfekt skille); høy Gini (nær $1-1/t$) betyr at ordet er lite informativt.

k-NN-klassifisering og tekstforbehandling

Innholdsbasert anbefaling kan implementeres som k-NN-klassifisering: representer hvert element som en termvektor og klassifiser et nytt element etter de $k$ nærmeste naboene. Tekstforbehandling påvirker resultatene:

• Stoppordfjerning gjør dokumenter mer ulike (fjerner felles «støy») — øker typisk recall og senker presisjon.
• Stemming/lemmatisering gjør dokumenter mer like (slår sammen bøyningsformer) — øker recall, senker presisjon, og krymper ordboken.
• Frasekstraksjon gjør dokumenter mer ulike (mer spesifikke trekk).
• Stoppordfjerning og lemmatisering reduserer ordbokstørrelsen og dermed beregningskompleksiteten. k-NN kan ytterligere akselereres med klyngebasert (clustering) forhåndsfiltrering.

Fordeler og begrensninger

• Fordel: Ingen kaldstartproblem for nye elementer (trenger bare egenskapsvektoren).
• Fordel: Forklarbar — «anbefalt fordi du likte filmer med egenskapene X».
• Fordel: Ingen privat data om andre brukere trengs.
• Begrensning: Overspecialisering (serendipity-problem) — systemet anbefaler bare mer av det samme, brukeren oppdager aldri ny sjanger.
• Begrensning: Kaldstartproblem for nye brukere — ingen historikk = ingen profil.
• Begrensning: Feature engineering er krevende — kvaliteten avhenger av om egenskapene er godt valgt.