Babeş-bolyai university of cluj-napoca

3.2 Algoritmi și clasificări

Sarcina fundamentală în filtrarea prin colaborare este de a prezice un set de evaluări lipsă pentru un anumit utilizator (utilizatorul activ), pe baza datelor conținute de matricea evaluărilor (denumită uneori și ca baza de date a utilizatorului). Există următoarele două abordări generale pentru filtrarea prin colaborare:

1. 
   Algoritmi pe bază de memorie - acești algoritmi funcționează online peste întreaga matrice de rating-uri pentru a calcula predicții.
   
2. 
   Algoritmi bazați pe model - spre deosebire de algoritmii pe bază de memorie, aceștia utilizează matricea de rating-uri într-un mod offline pentru a estima un model, care mai apoi este folosit pentru predicții;
   

Algoritmii pe bază de memorie, de obicei, oferă rezultate generale mai bune și sunt mult mai adaptabili la medii dinamice, în care matricea de rating-uri este des modificată. Pe de altă parte, aceasta abordare este foarte costisitoare din punct de vedere al procesării, astfel aplicațiile care utilizează seturi mari de date preferă abordarea oferită de algoritmii pe bază de modele.

În cele ce urmează vom examina câțiva dintre cei mai populari algoritmi utilizați în filtrarea prin colaborare. Printre algoritmii prezentați se regăsesc algoritmii bazați pe (k) – cei mai apropiați vecini: User-User Nearest Neighbors Algorithm și Item-Item Nearest Neighbors Algorithm - aceștia fiind probabil cei mai importanți algoritmi din categoria celor pe bază de memorie, Random Algorithm (algoritmul aleatoriu) și Mean Algorithm – doi algoritmi simpli, utilizați cu scopul de a evidenția performanțele celorlalți.

3.2.1 Algoritmul aleatoriu (Random Algorithm)

Conform ”definiției” de mai sus, algoritmul aleatoriu este un algoritm asemănător celor bazați pe modele, mai mult decât celor pe bază de memorie. Fiecare predicție a acestuia este o valoare aleatorie uniform distribuită pe scara de valorilor rating-ului. Pentru utilizatorii statici a și j acesta va prezice întotdeauna aceeași valoare aleatorie . Păstrarea acestei constrângeri asigură că previziunile algoritmului rămân aleatorii, dar comportamentul acestuia este invariabil chiar și atunci când este implicat în mai multe rulări.

3.2.2. Mean Algorithm

Algoritmul Mean este un algoritm foarte simplu, dar surprinzător de eficient încadrându-se în categoria algoritmilor bazați pe memorie. Uneori este menționat cu numele de Average Algorithm sau POP, fiind clasificat în categoria așa numitelor tehnici de predicție a popularității. Predicția este calculată ca valoarea medie a tuturor evaluărilor oferite de utilizatorul j (~ scorul mediu al utilizatorului j). Dacă este un set de utilizatori care au evaluat utilizatorul j, atunci media scorului pentru acest utilizator este definită astfel (3.1):

= (3.1)

aceasta fiind, de asemenea, și predicția (). Se poate observa ușor că aceasta abordare ignoră complet informațiile introduse în sistem de utilizatorul activ.

Acest algoritm împreună cu algoritmul aleatoriu sunt utilizați cu scopul de a crea o comparație în eficiența față de alți algoritmi prezenți.

3.2.3 User-based Nearest Neighbors Algorithm

Acest algoritm prezice rating-ul unui utilizator u, pentru un element nou i, utilizând rating-urile acordate elementului i de către cei mai mulți utilizatori similari cu u, numiți astfel cei mai apropiați vecini. Să presupunem că pentru fiecare utilizator v u avem o valoare ce reprezintă preferințele similare utilizatorului u și v. K - cei mai apropiați vecini (k-NN) ai utilizatorului u, notat cu , sunt primii k, v utilizatori cu cea mai mare similitudine față de u. Totuși, doar utilizatorii care au evaluat elementul i, pot fi utilizați în predicția , și considerăm, în schimb, k cei mai similari utilizatori pentru u care au evaluat i. Notăm acest set de vecini cu . Rating-ul poate fi estimat ca medie a rating-urilor oferite elementului i de către acești vecini (3.2):

(3.2)

O problemă în (3.2) este că nu se ia în calcul faptul că vecinii pot avea diferite nivele de similitudine. Fiind considerat exemplul din Figura 3.3, dacă cei mai apropiați vecini a lui Eric sunt Lucy și Diane, ar fi o greșeală să considerăm rating-urile lor egale pentru filmul ”Titanic”, din moment ce gusturile lui Lucy sunt mult mai apropiate de cele a lui Eric.

Figura 3.3

O soluție comună pentru rezolvarea acestei probleme este de a nota contribuția fiecărui vecin prin similitudinea lui față de u. Cu toate acestea, în cazul în care suma acestor contribuții nu este 1, rating-urile prezise pot ieși din raza valorilor permise. În consecință, se obișnuiește ca aceste valori ale contribuțiilor să fie normalizate, astfel că rating-ul prezis devine:

(3.4)

În numitorul (3.4), este utilizat în schimbul deoarece valorile negative pot produce rating-uri în afara razei permise. De asemenea, poate fi înlocuit de , unde α > 0 este un factor de amplificare. Când α > 1, așa cum este acesta cel mai des utilizat, este oferită o importanță mai mare vecinilor lui u.

Exemplu: Să presupunem că dorim să prezicem rating-ul lui Eric pentru filmul ”Titanic” (Figura 3.3) utilizând rating-urile lui Lucy și Dianei pentru acest film. Mai mult decât atât, presupunem că valorile de similaritate dintre acești vecini și Eric sunt 0,75, respectiv, 0,15. Rating-ul prezis va fi:

care este mai aproape de rating-ul lui Lucy decât cel al Dianei.

Ecuația 3.4 are, de asemenea, un defect important: se omite în calcul faptul că utilizatorii pot folosi diferite valori ale rating-ului pentru a cuantifica același nivel de apreciere pentru un element. De exemplu, un utilizator poate oferi cea mai mare valoare a rating-ului doar câtorva elemente deosebite, în timp ce un utilizator mai puțin dificil poate oferi această valoare majorității elementelor care îi sunt pe plac. Această problemă este, de obicei, abordată prin conversia rating-urilor vecinilor la cele normalizate , oferind următoarea predicție:

(3.5)

De reținut faptul că rating-ul prezis trebui transformat din nou la scara originală, datorită lui din ecuație.

3.2.3 Item-based Nearest Neighbors Algorithm

În timp ce algoritmul bazat pe cei mai apropiați utilizatori se utilizează opinia utilizatorilor cu preferințe asemănătoare pentru a prezice un rating, algoritmii bazați pe elemente verifică rating-urile acordate elementelor similare. Vom prezenta în cele ce urmează un exemplu bazat pe Figura 3.3.

Exemplu: În loc de a se consulta cu vecinii lui, Eric determină în schimb dacă filmul ”Titanic” este potrivit pentru el luând în considerare filmele pe care deja le-a vizionat. El observă că utilizatorii care au evaluat acest film, au dat rating-uri similare filmelor ”Forest Gump” și ”Wall-E”. Din moment ce Eric a fost plăcut impresionat de aceste două filme, el ajunge la concluzia că va dori, de asemenea, să vizioneze filmul ”Titanic”.

Această idee poate fi formulată după cum urmează. Notăm cu elementele apreciate de utilizatorul u care sunt similare elementului i. Predicția rating-ului lui u pentru i este obținută ca medie a rating-urilor oferite de utilizatorul u elementelor :

(3.6)

Exemplu: Să presupunem că prezicerea noastră se calculează, din nou, utilizând două aprecieri ale celor mai apropiați vecini, și că elementele cele mai similare cu ”Titanic” sunt ”Forest Gump” și ”Wall-E”, cu valori ale similarității egale cu 0,85, respectiv 0,75. Din moment ce rating-urile oferite de Eric acestor două filme sunt 5 și 4, rating-ul prezis pentru filmul ”Titanic” este calculat astfel:

Din nou, diferențele de scalare în evaluările individuale ale utilizatorilor pot fi normalizate utilizând un h:

(3.7)

Mai mult decât atât, putem defini, de asemenea, o abordare bazată pe clasificarea elementelor. În acest caz, elementele j evaluate de utilizatorul u, votează pentru rating-ul ce trebuie oferit unui element i, iar aceste voturi sunt calculate ca fiind similitudinile dintre i și j. Versiunea normalizată a acestei abordări poate fi exprimată după cum urmează:

= (3.8)