Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
Aj´anl´orendszerek Engedy Bal´azs Budapesti M˝ uszaki ´ es Gazdas´ agtudom´ anyi Egyetem Sz´ am´ıt´ astudom´ any szakir´ any
Nagy adathalmazok kezel´ese” ” c´ım˝ u t´ argy el˝ oad´ asa 2010. ´ aprilis 21.
Engedy Bal´ azs
Aj´ anl´ orendszerek
1/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
Tartalom 1
2
Bevezet´es T¨ort´enelem Gazdas´agi el˝ony¨ok Form´alis le´ır´as Csoportos´ıt´as Tartalomalap´ u rendszerek ´ Attekint´es Dokumentumprofil k´esz´ıt´ese Felhaszn´al´oi profil k´esz´ıt´ese Hasznoss´agbecsl´es El˝ony¨ok ´es h´atr´anyok Engedy Bal´ azs
3
4
Kollaborat´ıv rendszerek ´ Attekint´ es Felhaszn´al´ok hasonl´os´aga Hasonl´ o ´ızl´es˝ u felhaszn´al´ok ´ ekel´esek aggreg´al´asa Ert´ El˝ ony¨ ok ´es h´atr´anyok Kitekint´es Hibrid rendszerek Gradiensm´odszer Faktorm´atrixok Forr´asok, v´ege!
Aj´ anl´ orendszerek
2/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
T¨ ort´ enelem Gazdas´ agi el˝ ony¨ ok Form´ alis le´ır´ as Csoportos´ıt´ as
Dehomogeniz´al´od´o piacok
Joseph Pine: “Mass Customization” (1993) A ’90-es ´evekben v´egbemen˝ o piaci v´altoz´asokat t´argyalja, miszerint: a szabv´anyos, egyenv´as´arl´ ora tervezett t¨omegterm´ekek ideje lej´art, t¨obbf´ele v´as´arl´ o t¨ obbf´ele ig´eny´et kiel´eg´ıt˝o heterog´en (sokf´ele) term´ekek gy´art´as´anak ir´any´aba kell elmozdulni.
Engedy Bal´ azs
Aj´ anl´ orendszerek
3/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
T¨ ort´ enelem Gazdas´ agi el˝ ony¨ ok Form´ alis le´ır´ as Csoportos´ıt´ as
Aj´anl´orendszerek Jeff Bezos (CEO, Amazon) Ha 2 milli´o v´as´arl´om van a Weben, akkor 2 milli´ o boltom kell ” hogy legyen a Weben!” A heterogenit´as dilemm´aja Megvan a sokf´ele term´ek, v´altozatos k´ın´alat De ´ıgy a v´as´arl´ onak rengeteg lehet˝ os´egb˝ ol kell v´alasztani Inform´aci´ os t´ ulterhel´es ⇒ /
A k´ın´alatot meg kell sz˝ urni! Egy lehets´eges megold´as: aj´anl´ orendszerek
A v´as´arl´ onak csak relev´ans term´ekeket mutatunk Egy´enre- avagy testreszabott v´as´arl´as ⇒ , Engedy Bal´ azs
Aj´ anl´ orendszerek
4/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
T¨ ort´ enelem Gazdas´ agi el˝ ony¨ ok Form´ alis le´ır´ as Csoportos´ıt´ as
Aj´anl´orendszerek Jeff Bezos (CEO, Amazon) Ha 2 milli´o v´as´arl´om van a Weben, akkor 2 milli´ o boltom kell ” hogy legyen a Weben!” A heterogenit´as dilemm´aja Megvan a sokf´ele term´ek, v´altozatos k´ın´alat De ´ıgy a v´as´arl´ onak rengeteg lehet˝ os´egb˝ ol kell v´alasztani Inform´aci´ os t´ ulterhel´es ⇒ /
A k´ın´alatot meg kell sz˝ urni! Egy lehets´eges megold´as: aj´anl´ orendszerek
A v´as´arl´ onak csak relev´ans term´ekeket mutatunk Egy´enre- avagy testreszabott v´as´arl´as ⇒ , Engedy Bal´ azs
Aj´ anl´ orendszerek
4/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
T¨ ort´ enelem Gazdas´ agi el˝ ony¨ ok Form´ alis le´ır´ as Csoportos´ıt´ as
Gazdas´agi el˝ony¨ok az elad´ok sz´am´ara 1
B¨ong´esz˝okb˝ol v´as´arl´ ok → V´ as´ arl´ oi kos´ ar l´ etrej¨ on Ha a webshop b¨ ong´esz´ese k¨ ozben ´erdekes term´ekekkel tal´alkozik a v´as´arl´ o, tal´an v´as´arolni is fog!
2
J´arul´ekos elad´asok → Kos´ ar-´ atlagm´ eret n¨ ovekszik Ha v´as´arl´as k¨ozben tov´abbi ´erdekes term´ekekkel tal´alkozik a v´as´arl´ o, tal´an azokb´ ol is v´as´arolni fog!
3
H˝ us´eges v´as´arl´ok → V´ as´ arl´ asok sz´ ama n¨ ovekszik Ha a konkurenci´ahoz k´epest n´alunk ´erdekesebb term´ekekkel tal´alkozik a v´as´arl´ o – mert a r´egebbi t´enyked´eseib˝ol ´ep´ıtett v´as´arl´ oi profil szerint aj´anlunk kedv´ere val´ ot –, tal´an emiatt m´ar legk¨ ozelebb is ink´abb hozz´ank t´er be v´as´arolni!
Engedy Bal´ azs
Aj´ anl´ orendszerek
5/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
T¨ ort´ enelem Gazdas´ agi el˝ ony¨ ok Form´ alis le´ır´ as Csoportos´ıt´ as
Gazdas´agi el˝ony¨ok az elad´ok sz´am´ara 1
B¨ong´esz˝okb˝ol v´as´arl´ ok → V´ as´ arl´ oi kos´ ar l´ etrej¨ on Ha a webshop b¨ ong´esz´ese k¨ ozben ´erdekes term´ekekkel tal´alkozik a v´as´arl´ o, tal´an v´as´arolni is fog!
2
J´arul´ekos elad´asok → Kos´ ar-´ atlagm´ eret n¨ ovekszik Ha v´as´arl´as k¨ozben tov´abbi ´erdekes term´ekekkel tal´alkozik a v´as´arl´ o, tal´an azokb´ ol is v´as´arolni fog!
3
H˝ us´eges v´as´arl´ok → V´ as´ arl´ asok sz´ ama n¨ ovekszik Ha a konkurenci´ahoz k´epest n´alunk ´erdekesebb term´ekekkel tal´alkozik a v´as´arl´ o – mert a r´egebbi t´enyked´eseib˝ol ´ep´ıtett v´as´arl´ oi profil szerint aj´anlunk kedv´ere val´ ot –, tal´an emiatt m´ar legk¨ ozelebb is ink´abb hozz´ank t´er be v´as´arolni!
Engedy Bal´ azs
Aj´ anl´ orendszerek
5/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
T¨ ort´ enelem Gazdas´ agi el˝ ony¨ ok Form´ alis le´ır´ as Csoportos´ıt´ as
Gazdas´agi el˝ony¨ok az elad´ok sz´am´ara 1
B¨ong´esz˝okb˝ol v´as´arl´ ok → V´ as´ arl´ oi kos´ ar l´ etrej¨ on Ha a webshop b¨ ong´esz´ese k¨ ozben ´erdekes term´ekekkel tal´alkozik a v´as´arl´ o, tal´an v´as´arolni is fog!
2
J´arul´ekos elad´asok → Kos´ ar-´ atlagm´ eret n¨ ovekszik Ha v´as´arl´as k¨ozben tov´abbi ´erdekes term´ekekkel tal´alkozik a v´as´arl´ o, tal´an azokb´ ol is v´as´arolni fog!
3
H˝ us´eges v´as´arl´ok → V´ as´ arl´ asok sz´ ama n¨ ovekszik Ha a konkurenci´ahoz k´epest n´alunk ´erdekesebb term´ekekkel tal´alkozik a v´as´arl´ o – mert a r´egebbi t´enyked´eseib˝ol ´ep´ıtett v´as´arl´ oi profil szerint aj´anlunk kedv´ere val´ ot –, tal´an emiatt m´ar legk¨ ozelebb is ink´abb hozz´ank t´er be v´as´arolni!
Engedy Bal´ azs
Aj´ anl´ orendszerek
5/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
T¨ ort´ enelem Gazdas´ agi el˝ ony¨ ok Form´ alis le´ır´ as Csoportos´ıt´ as
Gazdas´agi el˝ony¨ok az elad´ok sz´am´ara 1
B¨ong´esz˝okb˝ol v´as´arl´ ok → V´ as´ arl´ oi kos´ ar l´ etrej¨ on Ha a webshop b¨ ong´esz´ese k¨ ozben ´erdekes term´ekekkel tal´alkozik a v´as´arl´ o, tal´an v´as´arolni is fog!
2
J´arul´ekos elad´asok → Kos´ ar-´ atlagm´ eret n¨ ovekszik Ha v´as´arl´as k¨ozben tov´abbi ´erdekes term´ekekkel tal´alkozik a v´as´arl´ o, tal´an azokb´ ol is v´as´arolni fog!
3
H˝ us´eges v´as´arl´ok → V´ as´ arl´ asok sz´ ama n¨ ovekszik Ha a konkurenci´ahoz k´epest n´alunk ´erdekesebb term´ekekkel tal´alkozik a v´as´arl´ o – mert a r´egebbi t´enyked´eseib˝ol ´ep´ıtett v´as´arl´ oi profil szerint aj´anlunk kedv´ere val´ ot –, tal´an emiatt m´ar legk¨ ozelebb is ink´abb hozz´ank t´er be v´as´arolni!
Engedy Bal´ azs
Aj´ anl´ orendszerek
5/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
T¨ ort´ enelem Gazdas´ agi el˝ ony¨ ok Form´ alis le´ır´ as Csoportos´ıt´ as
Az aj´anl´asi feladat form´alis le´ır´asa Input C v´as´arl´ohalmaz, |C| = m S term´ekhalmaz, |S| = n u : C × S → R hasznoss´agf¨ uggv´eny (pl. rating 1–10-ig) / Kev´es f¨ uggv´eny´ert´ek ismert (pl. amely filmeket ´ert´ekelte) / Az m ´es n pedig nagyon nagy (milli´ ok)
Output ∀c ∈ C v´as´arl´o sz´am´ara a leg´erdekesebb/leghasznosabb u ´j term´ek(ek) megad´asa, azaz: sc ∈ S, hogy u (c, sc ) maxim´ alis Engedy Bal´ azs
Aj´ anl´ orendszerek
6/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
T¨ ort´ enelem Gazdas´ agi el˝ ony¨ ok Form´ alis le´ır´ as Csoportos´ıt´ as
Aj´anl´orendszerek csoportos´ıtsa Az aj´anland´o term´ekekhez eljuthatunk a k´erd´eses felhaszn´al´o ´altal kedvelt term´ekeken kereszt¨ ul, azokhoz hasonl´ ot keresve; vagy a k´erd´eses felhaszn´al´ohoz hasonl´ o ´ızl´es˝ u felhaszn´al´ okon kereszt¨ ul, azok ´altal k¨oz¨osen kedvelt term´eket keresve. ´Igy teh´at: Tartalomalap´ u aj´anl´as A felhaszn´al´ onak olyan term´ekeket aj´anlunk, melyek tartalmukban hasonl´ok azokhoz, amelyeket a m´ ultban magasra ´ert´ekelt. Kollaborat´ıv aj´anl´as A felhaszn´al´ onak olyan term´ekeket aj´anlunk, melyeket m´as, hasonl´ o ´ızl´es˝ u felhaszn´al´ok magasra ´ert´ekeltek. Hibrid m´odszerek A fenti k´et m´ odszert egy¨ uttesen alkalmazzuk, vagy nem is k¨ ul¨ on´ıtj¨ uk el kategorikusan a k´et ir´anyt. Engedy Bal´ azs
Aj´ anl´ orendszerek
7/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
´ Attekint´ es Dokumentumprofil k´ esz´ıt´ ese Felhaszn´ al´ oi profil k´ esz´ıt´ ese Hasznoss´ agbecsl´ es El˝ ony¨ ok ´ es h´ atr´ anyok
Tartalomalap´u aj´anl´orendszerek
Engedy Bal´ azs
Aj´ anl´ orendszerek
8/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
´ Attekint´ es Dokumentumprofil k´ esz´ıt´ ese Felhaszn´ al´ oi profil k´ esz´ıt´ ese Hasznoss´ agbecsl´ es El˝ ony¨ ok ´ es h´ atr´ anyok
Tartalomalap´u aj´anl´orendszerek Egy adott felhaszn´al´ o sz´am´ara egy term´ek hasznoss´ag´at a hasonl´o term´ekek ugyanazon felhaszn´al´ o ´altal megadott 1 hasznoss´agaib´ol becs¨ ulj¨ uk : uˆ (c, s) ← ∀u (c, si ) alapj´ an, ahol: s ∼ si Klasszikusan sz¨oveges dokumentumokra alkalmazzuk A dokumentumokat tartalmilag pl. kulcsszavak gyakoris´ag´aval, fontoss´ag´aval jellemezhetj¨ uk, a tov´abbiakban e skal´arjellemz˝ okb˝ ol ´all´ o ennes k´epviseli a dokumentumot K´et dokumentum hasonl´ o, ha tartalmuk, ´ıgy jellemz˝o kulcsszavaik hasonl´ oak Felt´etelezz¨ uk, hogy tartalm´aban a m´ar olvasott (´es kedvelt) dokumentumokhoz hasonl´ ora v´agyik a felhaszn´al´o 1
´es a legnagyobb becs¨ ultet aj´ anljuk Engedy Bal´ azs
Aj´ anl´ orendszerek
9/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
´ Attekint´ es Dokumentumprofil k´ esz´ıt´ ese Felhaszn´ al´ oi profil k´ esz´ıt´ ese Hasznoss´ agbecsl´ es El˝ ony¨ ok ´ es h´ atr´ anyok
Az aj´anl´as menete
1
Az egyes dokumentumokhoz tartalmi profilt k´esz´ıt¨ unk: ∀s ∈ S : s → Content (s)
2
Az ´ert´ekelt dokumentumok alapj´an felhaszn´al´oi profil k´esz¨ ul: ∀c ∈ C : {(Content (s) , u (c, s)) | s ∈ Sc } → ContentBasedProf (c)
3
Ezek alapj´an az ismeretlen hasznoss´agokat becs¨ ulj¨ uk: uˆ (c, s) = score (Content (s) , ContentBasedProfile (c))
Engedy Bal´ azs
Aj´ anl´ orendszerek
10/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
´ Attekint´ es Dokumentumprofil k´ esz´ıt´ ese Felhaszn´ al´ oi profil k´ esz´ıt´ ese Hasznoss´ agbecsl´ es El˝ ony¨ ok ´ es h´ atr´ anyok
Dokumentumprofil k´esz´ıt´ese (egy lehets´eges heurisztika) Legyenek a rendszerben nyilv´antartott kulcsszavak: σ1 , σ2 , . . . σk Az si dokumentumban σj kulcssz´ o gyakoris´aga: fi,j Egy dokumentum profilja legyen az a vektor, mely az o¨sszes kulcsszavak wi,j fontoss´agait tartalmazza erre a dokumentumra: Content (si ) = w ~ si = wi,1 , wi,2 , . . . wi,k Engedy Bal´ azs
Aj´ anl´ orendszerek
11/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
´ Attekint´ es Dokumentumprofil k´ esz´ıt´ ese Felhaszn´ al´ oi profil k´ esz´ıt´ ese Hasznoss´ agbecsl´ es El˝ ony¨ ok ´ es h´ atr´ anyok
Dokumentumprofil k´esz´ıt´ese (egy lehets´eges heurisztika) Egy kulcssz´o fontoss´aga sokf´elek´epp defini´alhat´o, de pl. mondhatjuk, hogy ar´anyos a normaliz´alt el˝ ofordul´asi gyakoris´ag´aval: fi,j TFi,j = max∀z fi,z A t´ ul sok dokumentumban szerepl˝ o kulcsszavak viszont nem t´ ul informat´ıvak, ezek s´ uly´at hivatott cs¨ okkenteni az inverse document-frequency t´enyez˝ o: n o n IDFj = log , ahol nj = i | fi,j > 0 nj ´Igy a fontoss´ag: wi,j = TFi,j · IDFj Engedy Bal´ azs
Aj´ anl´ orendszerek
12/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
´ Attekint´ es Dokumentumprofil k´ esz´ıt´ ese Felhaszn´ al´ oi profil k´ esz´ıt´ ese Hasznoss´ agbecsl´ es El˝ ony¨ ok ´ es h´ atr´ anyok
Felhaszn´al´oi profil k´esz´ıt´ese (egy lehets´eges heurisztika) A felhaszn´al´o profilja lehet pl. szint´en egy vektor, mely a m´ ultban elolvasott dokumentumok alapj´an az adott felhaszn´al´o egyes kulcsszavakra vonatkoz´ o vi,j preferenci´ait tartalmazza: ContentBasedProfile (ci ) = ~vci = vi,1 , vi,2 , . . . vi,k
A preferenci´ak meghat´aroz´as´ara t¨ ort´enhet a m´ar ´ert´ekelt dokumentumok w ~ si vektorainak valamilyen ´atlagol´as´aval. ´Igy a ~v preferenciavektor szint´en tekinthet˝ o egy TF-IDF vektornak
Engedy Bal´ azs
Aj´ anl´ orendszerek
13/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
´ Attekint´ es Dokumentumprofil k´ esz´ıt´ ese Felhaszn´ al´ oi profil k´ esz´ıt´ ese Hasznoss´ agbecsl´ es El˝ ony¨ ok ´ es h´ atr´ anyok
Hasznoss´agbecsl´es (egy lehets´eges heurisztika)
A hasznoss´agot pedig defini´alhatjuk pl. a ~v ´es w ~ vektorok ´altal bez´art sz¨og koszinuszak´ent: uˆ (ci , sl ) = score (Content (sl ) , ContBasedProfile (ci )) = = cos ~vci , w ~ sl
Pk ~vci · w ~ sl j =1 vi,j · wl,j = = q qP Pk k ~vci · w ~ sl 2 2 j =1 vi,j · j =1 wl,j
Engedy Bal´ azs
Aj´ anl´ orendszerek
14/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
´ Attekint´ es Dokumentumprofil k´ esz´ıt´ ese Felhaszn´ al´ oi profil k´ esz´ıt´ ese Hasznoss´ agbecsl´ es El˝ ony¨ ok ´ es h´ atr´ anyok
Hasznoss´agbecsl´es (modellalap´u m´odszerek) Az im´ent bemutatott vektoros becsl´es a heurisztikus m´odszerek csal´adj´aba tartozik, ´es term´eszetesen csak egy a sok lehets´eges algoritmus k¨ oz¨ ul Vannak m´eg u ´n. modell-alap´ u m´ odszerek Content (s) itt is valamilyen statisztika a dokumentumokr´ol ContentBasedProfile (c) viszont valamilyen bonyolultabb modell A hasznoss´agbecsl´es a modell kimenet´en jelenik meg, az adott dokumentum profilj´at a bemenet´ere adva: uˆ (ci , sl ) = Model ci (Content (sl )) Pl. Naiv bayesi oszt´alyoz´ o fel´ep´ıt´ese a kulcssz´ ogyakoris´agokb´ol Pl. Rosta (winnow) algoritmus, neur´alis h´al´ ozatok Engedy Bal´ azs
Aj´ anl´ orendszerek
15/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
´ Attekint´ es Dokumentumprofil k´ esz´ıt´ ese Felhaszn´ al´ oi profil k´ esz´ıt´ ese Hasznoss´ agbecsl´ es El˝ ony¨ ok ´ es h´ atr´ anyok
El˝ony¨ok
F¨ uggetlens´eg a t¨ obbi felhaszn´al´ ot´ ol Egy´altal´an nem haszn´aljuk a becsl´eshez a t¨obbi felhaszn´al´or´ol t´arolt inform´aci´ okat, csak a k´erd´eses felhaszn´al´o preferenci´ait ´Igy ak´ar egyetlen felhaszn´al´ o eset´en is ´eletk´epes a rendszer
A hasznoss´agf¨ uggv´eny opcion´alis A felhaszn´al´ oi profil ak´ar egy u hasznoss´agf¨ uggv´eny n´elk¨ ul l´etrehozhat´ o A rendszer ekkor is ´eletk´epes, olyan ´ertelemben, hogy a m´ar megtekintett term´ekekhez hasonl´ okat akkor is tud aj´anlani
Engedy Bal´ azs
Aj´ anl´ orendszerek
16/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
´ Attekint´ es Dokumentumprofil k´ esz´ıt´ ese Felhaszn´ al´ oi profil k´ esz´ıt´ ese Hasznoss´ agbecsl´ es El˝ ony¨ ok ´ es h´ atr´ anyok
H´atr´anyok Term´ekjellemz˝ok el˝ o´all´ıt´as´anak probl´em´aja Sz¨ oveges dokumentumok eset´en j´ ol automatiz´alhat´o M´as term´ekek (pl. filmek, k´epek) eset´en viszont manu´alisan k´ene megadni (m˝ ufaj, szerepl˝ ok. . . ) → sok munka / Megint m´as term´ekekn´el esetleg egy´altal´an nem tudunk olyan (skal´ar) jellemz˝ oket megadni, melyen kereszt¨ ul ´ertelmesen osszehasonl´ıthatn´ank ˝ oket ¨
Megk¨ ul¨onb¨oztethetetlens´eg probl´em´aja Ha k´et term´ek jellemz˝ oi azonosak (a k´et ennes megegyezik), a rendszer sz´am´ara megk¨ ul¨ onb¨ oztethetetlenek Pl. Egy j´ ol ´es egy rosszul meg´ırt cikk ugyanabban a t´em´aban Pl. Egy j´ o ´es egy rossz 22 collos, TN-paneles, 1680 × 1050 felbont´as´ u LCD-monitor Engedy Bal´ azs
Aj´ anl´ orendszerek
17/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
´ Attekint´ es Dokumentumprofil k´ esz´ıt´ ese Felhaszn´ al´ oi profil k´ esz´ıt´ ese Hasznoss´ agbecsl´ es El˝ ony¨ ok ´ es h´ atr´ anyok
H´atr´anyok T´ ulspecializ´aci´o Elk´epzelhet˝ o, hogy nem mindig a m´ar (magasan) ´ert´ekeltekhez legink´abb hasonl´ o term´ekek aj´anl´asa lenne az ide´alis Megold´as: mesters´egesen zajt kell az eredm´enyhez keverni ´ Pl. Etteremaj´ anl´ o-rendszer: amennyiben a felhaszn´al´o m´eg csak k´ınai ´es magyar ´ızeket k´ ostolt, soha nem fogunk neki g¨or¨og ´ettermet aj´anlani (m´eg ha az is a legjobb a v´arosban), hiszen t´ uls´agosan k¨ ul¨ onb¨ oz˝ o az eddig ´ert´ekelt term´ekekt˝ol” ”
´ felhaszn´al´o probl´em´aja Uj
Egy u ´j felhaszn´al´ onak egy darabig nem tudunk ´ertelmesen aj´anlani, hiszen t´ uls´agosan kev´es ´ert´ekelt term´ekb˝ol k´ene a profilj´at fel´ep´ıten¨ unk
Engedy Bal´ azs
Aj´ anl´ orendszerek
18/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
´ Attekint´ es Felhaszn´ al´ ok hasonl´ os´ aga Hasonl´ o ´ızl´ es˝ u felhaszn´ al´ ok ´ ekel´ Ert´ esek aggreg´ al´ asa El˝ ony¨ ok ´ es h´ atr´ anyok
Kollaborat´ıv aj´anl´orendszerek
Engedy Bal´ azs
Aj´ anl´ orendszerek
19/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
´ Attekint´ es Felhaszn´ al´ ok hasonl´ os´ aga Hasonl´ o ´ızl´ es˝ u felhaszn´ al´ ok ´ ekel´ Ert´ esek aggreg´ al´ asa El˝ ony¨ ok ´ es h´ atr´ anyok
Kollaborat´ıv aj´anl´orendszerek A tov´abbiakban egy term´ek (pl. film) hasznoss´ag´an mindig egy adott sk´al´an mozg´ o ´ert´ekel´est (rating) ´ert¨ unk, azaz, hogy egy felhaszn´al´o milyen magasra pontozta, ´ert´ekelte (volna) az adott term´eket. Ennek megfelel˝ oen a k¨ ovetkez˝o jel¨ol´est vezetj¨ uk be: rc,s ≡ u (c, s) Egy adott felhaszn´al´ o sz´am´ara egy adott (m´eg nem ´ert´ekelt) term´ek ´ert´ekel´es´et most a hasonl´ o ´ızl´es˝ u felhaszn´al´ok ´altal a term´ekre adott ´ert´ekel´esek ¨ osszes´ıt´es´eb˝ ol becs¨ ulj¨ uk2 : rˆc,s ← ∀rci ,s alapj´ an, ahol: c ∼ ci 2
´es itt is a legnagyobb becs¨ ultet aj´ anljuk Engedy Bal´ azs
Aj´ anl´ orendszerek
20/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
´ Attekint´ es Felhaszn´ al´ ok hasonl´ os´ aga Hasonl´ o ´ızl´ es˝ u felhaszn´ al´ ok ´ ekel´ Ert´ esek aggreg´ al´ asa El˝ ony¨ ok ´ es h´ atr´ anyok
Az aj´anl´as menete 1
Felhaszn´al´op´arok hasonl´ os´agi faktor´anak meg´allap´ıt´asa: ∀x , y ∈ C : sim (x , y) meghat´ aroz´asa
2
Adott felhaszn´al´ohoz hasonl´ o ´ızl´es˝ u felhaszn´al´ok megkeres´ese: ∀c ∈ C : c → Cˆ = {c 0 | c 0 ∈ C, sim(c, c 0 ) nagy}
3
A hasonl´o ´ızl´es˝ u felhaszn´al´ ok ´altal adott ´ert´ekek aggreg´al´as´aval az ismeretlen ´ert´ekel´es becsl´ese: rˆc,s = aggr∀c 0 ∈Cˆ rc 0 ,s
Engedy Bal´ azs
Aj´ anl´ orendszerek
21/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
´ Attekint´ es Felhaszn´ al´ ok hasonl´ os´ aga Hasonl´ o ´ızl´ es˝ u felhaszn´ al´ ok ´ ekel´ Ert´ esek aggreg´ al´ asa El˝ ony¨ ok ´ es h´ atr´ anyok
Felhaszn´al´op´arok hasonl´os´aga ´ aban a felhaszn´al´ Altal´ ok ´altal k¨ oz¨ osen ´ert´ekelt Sxy term´ekhalmaz alapj´an dolgozunk: n o Sxy = s ∈ S | rx ,s , ∅, ry,s , ∅ A mindkettej¨ uk ´altal ´ert´ekelt term´ekek pontsz´amait egy-egy ~x ´es ~y vektork´ent tekintve itt is defini´alhatjuk a hasonl´os´agot az ezek ´altal bez´art sz¨ og koszinuszak´ent: P s∈Sxy rx ,s · ry,s ~x · ~y sim(x , y) = cos (~x , ~y ) = = qP qP ~x · ~y r2 · r2 s∈Sxy x ,s
Engedy Bal´ azs
Aj´ anl´ orendszerek
s∈Sxy y,s
22/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
´ Attekint´ es Felhaszn´ al´ ok hasonl´ os´ aga Hasonl´ o ´ızl´ es˝ u felhaszn´ al´ ok ´ ekel´ Ert´ esek aggreg´ al´ asa El˝ ony¨ ok ´ es h´ atr´ anyok
Felhaszn´al´op´arok hasonl´os´aga Egyes felhaszn´al´ok szigor´ ubban pontozhatnak, mint m´asok, ezt hivatott orvosolni a Pearson-f´ele korrel´aci´ os egy¨ utthat´o:
sim(x , y) = cos (~xn , ~yn ) = √P
P
s∈Sxy
s∈Sxy
(rx ,s −r x )·(ry,s −r y ) √P 2 s∈Sxy (ry,s −r y )
(rx ,s −r x )2 ·
ahol ~xn , ~yn az ~x , ~y vektorok nulla-´atlag´ ura norm´alva, azaz: ~xn ~yn
= ~x − (r x , . . . r x ) = ~y − r y , . . . r y
ahol r x , r y az x , y felhaszn´al´ ok ´ert´ekel´eseinek ´atlagai
Engedy Bal´ azs
Aj´ anl´ orendszerek
23/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
´ Attekint´ es Felhaszn´ al´ ok hasonl´ os´ aga Hasonl´ o ´ızl´ es˝ u felhaszn´ al´ ok ´ ekel´ Ert´ esek aggreg´ al´ asa El˝ ony¨ ok ´ es h´ atr´ anyok
Hasonl´o ´ızl´es˝u felhaszn´al´ok megkeres´ese Adott egy c felhaszn´al´ o, a hozz´a legink´abb hasonl´o ´ızl´es˝ u n´eh´any m´asikat szeretn´enk megtal´alni Kisz´am´ıthatjuk minden x , y felhaszn´al´ op´arra sim (x , y)-t, majd rendezz¨ uk → lass´ u lehet nagy adathalmazok eset´en, mivel az adatok nem f´ernek el a operat´ıv mem´ori´aban Gr´afot ´ep´ıthet¨ unk a felhaszn´al´ okb´ ol, ahol a hasonl´o ´ızl´es˝ uek valamilyen szempontb´ ol k¨ ozel” helyezkednek el egym´ashoz ” A k¨ovetkez˝o fejezetben l´atni fogunk egy m´ odszert, mellyel a sim (x , y) ´ert´ekeket csak k¨ ozel´ıtj¨ uk, de ´ıgy legal´abb elf´er¨ unk a mem´ori´aban
Engedy Bal´ azs
Aj´ anl´ orendszerek
24/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
´ Attekint´ es Felhaszn´ al´ ok hasonl´ os´ aga Hasonl´ o ´ızl´ es˝ u felhaszn´ al´ ok ´ ekel´ Ert´ esek aggreg´ al´ asa El˝ ony¨ ok ´ es h´ atr´ anyok
´ ekel´esek aggreg´al´asa Ert´ Valamilyen ´atlag, p´eld´aul: (a) Egyszer˝ u ´atlag rˆc,s =
1 X rc 0 ,s , ahol N = Cˆ N 0 ˆ ∀c ∈C
(b) Felhaszn´al´ ok hasonl´ os´ag´aval s´ ulyozott ´atlag rˆc,s = k ·
X
sim(c, c 0 ) · rc 0 ,s , ahol k = P
ˆ ∀c 0 ∈C
ˆ ∀c 0 ∈C
1 |sim(c, c 0 )|
(c) S´ ulyozott ´atlag, normaliz´alt ´ert´ekel´esekkel X rˆc,s = r c + k · sim(c, c 0 ) · rc 0 ,s − r c 0 ˆ ∀c 0 ∈C Engedy Bal´ azs
Aj´ anl´ orendszerek
25/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
´ Attekint´ es Felhaszn´ al´ ok hasonl´ os´ aga Hasonl´ o ´ızl´ es˝ u felhaszn´ al´ ok ´ ekel´ Ert´ esek aggreg´ al´ asa El˝ ony¨ ok ´ es h´ atr´ anyok
Modellalap´u m´odszerek Az im´ent bemutatott becsl´es szint´en a heurisztikus m´odszerek csal´adj´aba tartozik Kollaborat´ıv esetben is vannak modell-alap´ u m´odszerek Az ´ert´ekel´esekb˝ ol egy bonyolultabb modellt ´ep´ıt¨ unk A modell kimenet´en becsli rc,s nem ismert ´ert´ekeit Pl. Klaszterez´esen alapul´ o m´ odszerek: a hasonl´ o ´ızl´es˝ u felhaszn´al´ okat egy-egy oszt´alyba soroljuk, ezen bel¨ ul naiv bayesi oszt´alyoz´ ot haszn´alunk a becsl´esre Pl. Bayes-h´al´ ok: a csom´ opontok a term´ekek, lehets´eges ´allapotaik az egyes ´ert´ekel´esek (pl. 1–10-ig) Pl. Egy´eb g´epi tanul´asi m´ odszerek
Engedy Bal´ azs
Aj´ anl´ orendszerek
26/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
´ Attekint´ es Felhaszn´ al´ ok hasonl´ os´ aga Hasonl´ o ´ızl´ es˝ u felhaszn´ al´ ok ´ ekel´ Ert´ esek aggreg´ al´ asa El˝ ony¨ ok ´ es h´ atr´ anyok
El˝ony¨ok
Tetsz˝oleges t´ıpus´ u term´ekek A felhaszn´al´ oink ´ert´ekrendj¨ uk szerint l´enyeg´eben b´armilyen t´ıpus´ u term´eket k´epesek pontozni, ´ıgy mindenf´ele term´ekhez rendelhet˝ o egy skal´ar (a hasznoss´ag) A term´ekeknek klasszikus ´ertelemben nem is kell osszehasonl´ıthat´ onak lenni¨ uk ¨
Minden megk¨ ul¨onb¨ oztethet˝ o A felhaszn´al´ ok ´ert´ekel´eskor a teljes tartalmat n´ezik, ´ıgy nem lehet olyan probl´ema, mint a tartalomalap´ u esetben, hogy a kivont jellemz˝ ok megegyeznek, ´ıgy egy j´ o ´es egy rossz filmet ne tudn´ank megk¨ ul¨ onb¨ oztetni
Engedy Bal´ azs
Aj´ anl´ orendszerek
27/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
´ Attekint´ es Felhaszn´ al´ ok hasonl´ os´ aga Hasonl´ o ´ızl´ es˝ u felhaszn´ al´ ok ´ ekel´ Ert´ esek aggreg´ al´ asa El˝ ony¨ ok ´ es h´ atr´ anyok
H´atr´anyok ´ felhaszn´al´o probl´em´aja (mint el˝ Uj obb) ´ term´ek probl´em´aja Uj Am´ıg egy term´ekre nem ´erkezik el´eg sok ´ert´ekel´es, nem fogjuk tudni aj´anlani (sok´aig nem lesz olyan felhaszn´al´o lesz, aki hasonl´ o ´ızl´es˝ u a k´erd´eses felhaszn´al´ ohoz ´es ´ert´ekelte) Megold´as: hibrid m´ odszerek
Ritkas´ag ´ aban csak kev´es rc,s ´ert´ek ismert, ezek alapj´an kell j´ol Altal´ aj´anlanunk A megfelel˝ o m˝ uk¨ od´eshez m´eg ´ıgy is kell egy kritikus t¨omeg (felhaszn´al´ okb´ ol), hogy: (1) minden felhaszn´ al´ ohoz legyen el´eg sok hasonl´ o ´ızl´es˝ u, (2) akik r´ aad´ asul ´ert´ekelt´ek is a k´erd´eses term´eket
Engedy Bal´ azs
Aj´ anl´ orendszerek
28/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
Hibrid rendszerek Gradiensm´ odszer Faktorm´ atrixok Forr´ asok, v´ ege!
Hibrid aj´anl´orendszerek
Engedy Bal´ azs
Aj´ anl´ orendszerek
29/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
Hibrid rendszerek Gradiensm´ odszer Faktorm´ atrixok Forr´ asok, v´ ege!
Hibrid aj´anl´orendszerek
A becsl´es jav´ıthat´o, ha az egyes megk¨ ozel´ıt´eseket kombin´aljuk: 1
A k¨ ul¨on alkalmazott tartalomalap´ u, illetve kollaborat´ıv aj´anl´ok eredm´enyeit kombin´aljuk
2
Tartalomalap´ u aj´anl´ ot kollaborat´ıv elemekkel eg´esz´ıtj¨ uk ki
3
Kollaborat´ıv aj´anl´ ot tartalomalap´ u elemekkel eg´esz´ıtj¨ uk ki
4
Egys´eges modellt dolgozunk ki, mely egyszerre dolgozik a k´et megk¨ozel´ıt´es szerint, nem v´alasztja sz´et a k´et ir´anyt
Engedy Bal´ azs
Aj´ anl´ orendszerek
30/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
Hibrid rendszerek Gradiensm´ odszer Faktorm´ atrixok Forr´ asok, v´ ege!
Hasonl´os´agbecsl´es gradiensm´odszerrel Alap¨otlet: Az el˝ oz˝ o fejezetben a felhaszn´al´ ok hasonl´ os´ag´anak kisz´am´ıt´as´ara manu´alisan adtunk k´epletet (koszinusz, Pearson) B´ızzuk ezt is az aj´anl´ orendszerre: tanuljon alkalmas hasonl´ os´ag´ert´ekeket u ´gy, hogy a v´egeredm´eny j´o legyen
Az egyes felhaszn´al´ ok hasonl´ os´ag´at le´ır´ o sim (i , j ) f¨ uggv´enyt rendezz¨ uk egy H m´atrixba: h i H = hi,j = sim (i , j ) Ekkor az al´abbi m´ odon becs¨ ult hasznoss´agok ¨osszes (n´egyzetes) hib´aj´at akarjuk minimaliz´alni: P ∀c 0 ∈C hc,c 0 · rc 0 ,s , ahol Cs = c | c ∈ C, rc,s , ∅ rˆc,s = P s ∀c 0 ∈Cs hc,c 0 Engedy Bal´ azs
Aj´ anl´ orendszerek
31/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
Hibrid rendszerek Gradiensm´ odszer Faktorm´ atrixok Forr´ asok, v´ ege!
Hasonl´os´agbecsl´es gradiensm´odszerrel A minimaliz´aland´ o hibaf¨ uggv´eny teh´at : E (H, L) =
X 1 X rˆc,s (H) − rc,s 2 + γ hi,j , 2 i<j rc,s ∈L
ahol L a tan´ıt´ohalmaz, γ a regulariz´aci´ os konstans Az u ´n. sztochasztikus gradiensm´ odszert haszn´alva az egyes tan´ıt´opontokkal egyenk´ent jav´ıtjuk egy adott rc,s p´eld´aban ´erintett hc,i param´etereket: ! ∂ˆrc,s u ´j r´ egi r´ egi hc,i = hc,i − η · sign rˆc,s − rc,s − ηγhc,i , ∂hc,i ahol η a b´ators´agi t´enyez˝ o Engedy Bal´ azs
Aj´ anl´ orendszerek
32/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
Hibrid rendszerek Gradiensm´ odszer Faktorm´ atrixok Forr´ asok, v´ ege!
Faktorm´atrixok (a gradiensm´odszerhez) A gradiensm´odszer probl´em´aja, hogy kis sz´am´ u tan´ıt´opontb´ol akarunk rengeteg hi,j hasonl´ os´ag´ert´eket meghat´arozni, ´ıgy hajlamos a t´ ultanul´asra (´es a mem´ ori´aban sem f´er el!) Cs¨ okkents¨ uk a szabads´agi fokot, a param´eterek sz´am´at! Erre egy lehets´eges megold´as, hogy a H m´atrixot k´et u ´n. faktorm´atrix szorzatak´ent ´ırjuk fel: n×n n×k
k ×n
H=P · Q
´Igy az eredeti m´atrix egy k -rang´ u approxim´aci´oj´at kaptuk A becs¨ ult rˆc,s ´ert´ekek az ´ıgy kapott pi,j , qi,j param´eterek szerint tov´abbra is deriv´alhat´ ok, ´ıgy ezek betanul´as´ara a gradiensm´odszer hasonl´ oan alkalmazhat´ o Engedy Bal´ azs
Aj´ anl´ orendszerek
33/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
Hibrid rendszerek Gradiensm´ odszer Faktorm´ atrixok Forr´ asok, v´ ege!
A faktorm´atrixok szeml´eletes jelent´ese
A P · Q m´atrixszorz´asra u ´gy is tekinthet¨ unk, hogy a H i -edik sor´at Q egyes sorainak pi,1 , . . . pi,k -egy¨ utthat´ os line´aris kombin´aci´oj´aval k¨ ozel´ıtj¨ uk: hi =
k X
pi,j · qj
j =1
Engedy Bal´ azs
Aj´ anl´ orendszerek
34/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
Hibrid rendszerek Gradiensm´ odszer Faktorm´ atrixok Forr´ asok, v´ ege!
A faktorm´atrixok szeml´eletes jelent´ese
Ez szeml´eletesen azt jelenti, hogy Q soraiban az egyes felhaszn´al´o-sztereot´ıpi´akat le´ır´ o vektorok jelennek meg, P soraiban pedig az, hogy az adott felhaszn´al´ o mennyire tartozik bele az adott sztereot´ıpi´aba Engedy Bal´ azs
Aj´ anl´ orendszerek
35/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
Hibrid rendszerek Gradiensm´ odszer Faktorm´ atrixok Forr´ asok, v´ ege!
Forr´asok Gediminas Adomavicius and Alexander Tuzhilin. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions. IEEE Trans. on Knowl. and Data Eng., 17(6):734–749, 2005. J. Ben Schafer, Joseph Konstan, and John Riedi. Recommender systems in e-commerce. In EC ’99: Proceedings of the 1st ACM conference on E. commerce, pages 158–166, New York, USA, 1999. ACM. Andreas T¨oscher, Michael Jahrer, and Robert Legenstein. Improved neighborhood-based algorithms for large-scale recommender systems. In NETFLIX ’08: Proceedings of the 2nd KDD Workshop, pages 1–6, New York, NY, USA, 2008. ACM. Engedy Bal´ azs
Aj´ anl´ orendszerek
36/ 37
Bevezet´ es Tartalomalap´ u rendszerek Kollaborat´ıv rendszerek Kitekint´ es
Hibrid rendszerek Gradiensm´ odszer Faktorm´ atrixok Forr´ asok, v´ ege!
Engedy Bal´ azs
Aj´ anl´ orendszerek
V´ege!
37/ 37
