Data publicării: 30.07.2017
Autor articol: Corina Forascu

Un sistem de recomandări este un tip specific de tehnică pentru filtrarea informaţiilor, care încearcă să prezinte anumite tipuri de produse (Kabiljo & Ilic, 2015), cum ar fi filme, muzică, site-uri web, care ar putea să fie de interes pentru utilizatori.

Acestea au o mare importanţă pentru succesul comerţului electronic şi al industriei IT din zilele noastre şi au câştigat popularitate în diverse aplicaţii precum Netflix, Google, Amazon, Youtube etc. Recomandările reprezintă o parte esenţială a tuturor acestor întreprinderi, iar în unele cazuri conduc la procente semnificative din veniturile lor.

Intuitiv, un sistem de recomandări construieşte profilul unui utilizator pe baza înregistrărilor anterioare, îl compară cu unele caracteristici de referinţă şi încearcă să prezică evaluarea sau scorul pe care un utilizator l-ar da unui produs pe care nu l-a evaluat încă.

Pe baza alegerii caracteristicilor de referinţă, un sistem de recomandare s-ar putea construi cu o abordare bazată pe conţinut sau cu o abordare bazată pe filtrarea colaborativă (Collaborative Filtering – CF), sau chiar ambele. După cum o spun şi denumirile lor, abordarea bazată pe conţinut constă în potrivirea profilului utilizatorului pe anumite caracteristici specifice ale unui element, precum apariţia unor cuvinte specifice într-un document, în timp ce filtrarea colaborativă (CF, online) este un proces de filtrare al informaţiilor sau al tiparelor bazate pe colaborarea utilizatorilor sau pe similarităţile dintre produse.

Ideea din spatele motorelor de recomandare este aceea de a prezice ceea ce ar dori oamenii şi de a descoperi relaţiile dintre produse pentru a ajuta procesul de antrenare. Se poate spune chiar că acestea sunt similare motoarelor de căutare, diferenţa dintre ele fiind faptul că, spre deosebire de cele din urmă, sistemele de recomandare încearcă să prezinte oamenilor conţinuturi relevante pe care nu le căutau în mod special, sau de care nici nu au auzit.

De obicei un motor de recomandare încearcă să modeleze conexiunile dintre utilizatori şi un anumit tip de produs. Cu toate acestea, sistemele de recomandări nu se limitează la filme, cărţi sau produse, ci se pot aplica oricăror relaţii de tipul utilizator-produs, produs-produs, precum şi utilizator-utilizator, ca cele pe care le găsim pe reţelele sociale şi ne fac recomandări pentru persoanele pe care s-ar putea să le cunoaştem sau pe care ar trebui să le urmărim mai atent.

Creşterea datelor din mediul online (Data Bottleneck) a făcut mult mai dificilă folosirea multor algoritmi de învăţare automată pe seturi de date complete. Aceasta problemă apare şi în cazurile unor recomandări personalizate, unde eşantionarea datelor nu este întotdeauna o soluţie. În acest caz este necesară găsirea unor modele noi de algoritmi distribuiţi sau descoperirea unor metode personalizate de transformări asupra informaţiilor colectate de la utilizatori, pentru a putea ţine pasul cu aceste seturi de date ce sunt într-o continuă creştere şi schimbare.

Aplicaţia RecMov, realizată în cadrul unei lucrări de licență (Cotruță 2017) constă în realizarea unui sistem de recomandări pentru filme. Datele utilizate pentru teste sunt preluate de la MovieLens (Group Lens) (online), care pun la dispoziţie o gamă variată de seturi de informaţii. Pentru aplicaţia RecMov a fost selectată o bază de date ce conţine aproximativ un milion de evaluări de la aproximativ 6000 de utilizatori pentru 3706 filme.

Un sistem de recomandări construieşte profilul unui utilizator pe baza înregistrărilor anterioare, îl compară cu unele caracteristici de referinţă şi încearcă să prezică evaluarea sau scorul pe care un utilizator l-ar putea da unui produs pe care nu l-a evaluat încă.

La modul general, informaţiile despre preferinţele utilizatorilor sunt de două tipuri: explicite şi implicite. Primul tip constă în principal în date concrete şi anume în evaluarea articolelor la o scară predefinită în funcţie de opinia fiecărui utilizator, în timp ce al doilea tip constă în date ce conţin în locul evaluărilor propriu-zise valori de încredere, rezultate din acţiunile utilizatorilor, precum vizualizările sau accesările.

Scopul a fost acela de a reduce eroarea la antrenare şi la testare pe setul de date, pentru a genera un model cât mai complet şi precis prin găsirea celor mai potriviţi parametri de regularizare. Totodată, pentru o mai bună precizie şi rezultate mai exacte, s-a realizat transformarea setului de date explicit într-unul implicit.

În principiu, în loc să fie modelată direct matricea evaluărilor, acestă abordare tratează datele ca numere reprezentând puterea sau tăria în observaţiile acţiunilor utilizatorilor, cum ar fi numărul de click-uri sau numărul de vizualizări ale aceluiaşi film. Aceste numere sunt apoi legate de nivelul de încredere în preferinţele observate la fiecare utilizator. Modelul încearcă să găsească factori latenţi care pot fi utilizaţi în cele din urma pentru a prezice preferinţa preconizată a unui utilizator pentru un produs.

Sistemul RecMov a fost construit după testare unor sisteme de recomandare existente, care vor fi prezentate în cele ce urmează.

Prima aplicaţie vizată este Netflix, lider mondial în reţeaua de televiziune prin internet, cu peste 100 de milioane de membri în peste 190 de ţări, ce au acces la o varietate de filme, seriale, documentare şi emisiuni TV.

Scopul metodei de învăţare automată utilizată de cei de la Netflix este acela de a oferi recomandări personalizate utilizatorilor. Aceste rezultate ale recomandărilor pot fi prelucrate direct din anumite liste calculate anterior sau pot fi generate pe parcurs, prin intermediul unor algoritmi specifici mediului online, ce utilizează semnale în timp real.

Deoarece Netflix a suferit schimbări dramatice în ultimii ani, iar priorităţile s-au modificat, accentul a fost pus pe sistemele şi pe algoritmii de recomandări. Aceştia au lansat un serviciu de streaming în 2007, fapt ce a schimbat nu numai modul în care membrii interacţionează cu serviciul, cât şi tipul datelor disponibile pentru funcţionarea algoritmilor interni (Amatriain, 2012).

În 2006, compania a anunţat Netflix Prize, un concurs de învăţare automată şi de exploatare a datelor pentru predicţia evaluării filmelor, oferind un milion de dolari drept premiu, celor ce vor reuşi să îmbunătăţească exactitatea sistemului lor de recomandări cu cel puţin 10%. Această competiţie a avut rolul de a găsi noi modalităţi de îmbunătăţire a recomandărilor pe care aplicaţia le oferă utilizatorilor, problema rezumându-se la micşorarea valorii metricii RMSE ((Root Mean Squared Error) a evaluării prezise, de la valoarea iniţială de 0,9525 până la 0,8572, sau chiar mai puţin (Amatriain, 2012).

În urma concursului au fost câştigători doi algoritmi, Matrix Factorization (Singular Value Decomposition) şi Restricted Boltzmann Machine (RBM). SVD a furnizat un RMSE de 0,8914, în timp ce RBM a oferit doar un RMSE competitiv, dar uşor mai rău, de 0,8990. Un amestec liniar dintre aceşti doi algoritmi a redus totuşi eroarea la 0,88, ulterior aceştia fiind integraţi în producţie, fiind utilizaţi şi astăzi în motorul lor de recomandări (Amatriain, 2012).

O altă schimbare majoră a fost trecerea de la un singur site web la sute de dispozitive. Netflix este acum disponibil pe o multitudine de aparate, de la Android, Xbox, la cel mai recent model de AppleTV, bucurându-se de o multitudine de utilizatori care transmit în medie două miliarde de ore de la sute de dispozitive diferite pe trimestru.

Aceştia şi-au adaptat algoritmii de personalizare la acest nou scenariu astfel încât, acum, 75% din ceea ce privesc utilizatorii provine din recomandări. Au ajuns la acest punct prin optimizarea continuă a experienţei membrilor şi au măsurat câştigurile semnificative în ceea ce priveşte satisfacţia acestora ori de câte ori au îmbunătăţit sistemul de personalizare.

Au descoperit de-a lungul anilor că o importanţă foarte mare în succesul lor şi satisfacţia abonaţilor este de a integra recomandări pentru a personaliza cât mai mult posibil Netflix-ul. Un exemplu poate fi situaţia de “Top 10 Movies”. Aceasta este cea mai bună estimare pentru primele zece titluri de filme pe care un utilizator le-ar aprecia cel mai mult. Este importat de reţinut că personalizarea Netflix este destinată să se ocupe de un grup mai mare, precum o familie, în care este posibil să fie oameni diferiţi, cu gusturi diferite. De aceea, în momentul în care vorbim despre „Top 10”, este posibil să descoperim articole atât pentru tată, mamă, copii sau întreaga familie. Pentru a realiza acest lucru, în multe părţi ale sistemului lor, aceştia nu fac optimizări doar pentru acurateţe, ci şi pentru diversitate (Amatriain, 2012).

Un alt element important în personalizara Netflix este conştientizarea. Aceştia vor ca membrii lor să fie conştienţi de modul în care sistemul se adaptează gusturilor lor. Acest lucru nu numai că promovează încrederea în sistem, dar încurajează membrii să acorde feedback, care duce implicit la recomandări mai bune. Sistemul recomandă un film sau o emisiune TV unui utilizator deoarece se potriveşte cu informaţiile pe care le are despre acesta, precum preferinţele explicite ale gusturilor lui şi evaluările, istoricul vizualizărilor sau chiar recomandările prietenilor (Amatriain, 2012).

Unele dintre personalizările cele mai recunoscute în serviciul celor de la Netflix sunt cele pentru colecţiile de genuri(comedie, dramă, groază etc.). Fiecare dintre acestea presupune trei etape în procesul de personalizare: alegerea genului în sine, subgrupul titlurilor selectate din genul respectiv, şi clasamentul acestor titluri (Amatriain, 2012).

Similaritatea este o altă sursă importantă în serviciul de personalizare al celor de la Netflix. Aceştia percep similaritatea într-un sens foarte larg, între filme sau între membri, şi totodată în diverse forme, ca metadate, evaluări sau vizualizări ale datelor. Similitudinea este folosită în mai multe contexte, spre exemplu ca răspuns la acţiunea unui membru, cum ar fi căutarea sau adăugarea unui titlu în lista lui de preferinţe (Amatriain, 2012).

După cum s-a menţionat anterior, rezultatele algoritmice ale celor de la Netflix pot fi calculate fie online, în timp real, offline pe baza unor date existente, sau combinat. Fiecare abordare are avantaje şi dezavantaje, care trebuiesc luate în considerare pentru fiecare caz de utilizare.

Calculul online poate răspunde rapid evenimentelor şi poate utiliza date cât mai recente, un exemplu fiind generarea unei galerii de filme sortate pentru un membru utilizând contextul curent. Componentele online sunt supuse unui Service Level Agreements (SLA) care specifică latenţa maximă a procesului la cererile clientului, timp în care membrul aşteaptă ca recomandările să apară. În această abordare, acest lucru face mai dificilă utilizarea unor algoritmi mai complecşi, care să nu fie costisitori din punct de vedere computaţional. Totodată o abordare pur online poate eşua în îndeplinirea condiţiilor SLA menţionate mai sus în unele circumstanţe, deci este important ca întotdeauna să existe un mecanism rapid de rezervă, cum ar fi revenirea la un rezultat precomputat (Amatriain, 2012).

Pe partea cealaltă, calcului offline permite mai multe alegeri în abordarea algoritmică, cum ar fi algoritmi mai complecşi şi limitări mai mici asupra cantităţii de date care este utilizată. Un exemplu trivial ar putea fi agregarea periodică a statisticilor din milioane de vizualizări ale filmelor, pentru a computa valorile de bază ale popularităţilor pentru recomandări.

Un alt avntaj al acestei abordări este şi faptul că cerinţele tehnice sunt mai mici, standardele SLA ale timpilor de raspuns fiind uşor îndeplinite. Noi algoritmi pot fi utilizaţi în producţie fără a fi nevoie de prea mult efort pentru a regla performanţele. Cu toate acestea, deşi procesarea offline nu are cerinţe puternice de latenţă, nu va reacţiona rapid la schimbările de context sau la datele noi. În cele din urmă, acest lucru poate duce la stagnare, care poate aduce neplăceri experienţei utilizatorilor. Calculul offline necesită de asemenea o infrastructură pentru stocarea, calculul şi accesarea seturilor mari de rezultate precomputate (Amatriain, 2012).

Aceste două abordări ar trebui combinate pentru a obţine rezultate cât mai bune, modelul Matrix Factorization fiind o potrivire cât se poate de naturală pentru acestă modelare ce combina offline-ul cu online-ul. Unii factori pot fi precomputaţi offline, în timp ce alţii pot fi actualizaţi în timp real pentru a crea un rezultat cât mai recent.

O mare parte din calculele care sunt făcute când se rulează algoritmii de învăţare automată pentru personalizări se pot face offline. Asta înseamnă că job-urile pot fi programate să fie executate periodic şi executarea lor nu trebuie să fie sincronă cu solicitarea sau prezentarea rezultatelor. Există două tipuri principale de sarcini care se execută: antrenarea modelului şi computarea rezultatelor intermediare sau finale. În partea de antrenare a modelului se colectează date relevante existente şi se aplică algoritmi de învăţare automată care produc un set de parametri, utilizaţi în continuare în antrenarea celui mai optim model, ce este stocat de obicei pentru a fi utilizat şi pe viitor.

Prin concursul organizat, cei de la Netflix au reuşit să abstractizeze o problemă de recomandare la o întrebare referitoare la precizia evaluării. Evaluările membrilor sunt însă doar una dintre numeroasele surse de date pe care aceştia le deţin, iar predicţiile evaluărilor sunt doar o parte a soluţiei.

De-a lungul timpului aceştia au reformulat problema de recomandare la situaţia de a optimiza probabilitatea unui membru care alege să vizioneze un produs și se bucură de el suficient de mult, astfel încât să utilizeze şi în continuare sistemul. Mai multă disponibilitate de date oferă rezultate mai bune, dar, pentru a obține aceste rezultate, este nevoie de abordări optimizate, metrici adecvate și experimentări rapide, deoarece pentru a excela în personalizarea inovativă, a fi metodici nu este suficient, deoarece spaţiul de explorat este infinit.

Înființată în 2004, compania Facebook are ca obiectiv să ofere oamenilor puterea de a împărtăși și de a face lumea mai deschisă și mai conectată. Oamenii folosesc Facebook pentru a rămâne în legătură cu prietenii și familia, pentru a descoperi ce se întâmplă în lume și pentru a împărtăși și a exprima ceea ce contează pentru ei.

Filtrarea colaborativă este unul dintre domeniile importante în care acest lucru se aplică. La Facebook, aceasta poate include pagini, grupuri, evenimente, jocuri și multe altele. CF se bazează pe ideea că cele mai bune recomandări provin de la oameni care au gusturi similare. Cu alte cuvinte, utilizează evaluări ale articolelor deja existente ale unor oameni care gândesc similar, pentru a prezice modul în care cineva ar evalua un element (Kabiljo, 2015).

Setul mediu de date al Facebook-ului are 100 de miliarde de evaluări, mai mult de un miliard de utilizatori și milioane de articole. În comparație, concursul organizat de cei de la Netflix despre care am vorbit mai sus, a fost prezentat cu un set de date industriale la scară largă, cu 100 de milioane de evaluări, 480.000 de utilizatori și 17.770 de filme (Kabiljo, 2015).

O provocare cu care cei de la Facebook s-au confruntat a fost aceea de a proiecta un algoritm distribuit care să scaleze aceste seturi masive de informaţii și de a depăși problemele care au apărut din cauza anumitor proprietăți ale datelor, cum ar fi informaţiile implicite în locul evaluărilor.

Abordările utilizate în soluțiile existente nu au putut rezolva în mod eficient dimensiunile acestora de date, aşa că au avut nevoie de o nouă soluție. Cei de la Facebook au ales să adapteze nevoilor lor Apache Giraph, o platformă puternică pentru procesarea distribuită, iterativă și grafică. Apache Giraph lucrează extrem de bine pe seturi de date masive, este ușor de extins, prin urmare, a fost alegerea lor evidentă pentru această problemă (Kabiljo, 2015).

În cele din urmă aceştia au venit cu o abordare în care au fost nevoiţi să extindă cadrul Giraph cu mesaje de tipul worker1-to-worker. Utilizatorii sunt în continuare prezentați ca vârfuri ale graficului, dar elementele sunt împărțite în seturi separate, fiecare dintre acestea fiind stocate în datele globale ale unuia dintre workeri.

O abordare comună a CF utilizată de aceştia, este prin matricile de factorizare, în care privim problema ca având un set de utilizatori, un set de elemente și o matrice rară, care reprezintă evaluările date de utilizatori elementelor. Vrem să prezicem valori lipsă în această matrice. Pentru a face acest lucru, reprezentăm fiecare utilizator și fiecare element ca vector al unor caracteristici latente, astfel încât produsele punct ale acestor vectori se potrivesc îndeaproape cu evaluările cunoscute de la un utilizator la altul (Kabiljo, 2015).

Alternating least square (ALS) este soluţia pentru abordarea prezentată mai sus. Aceasta este o metodă utilizată cu modele de regresie neliniară atunci când există două variabile dependente, cum ar fi doi vectori, x și y. Algoritmul fixează unul dintre parametri (vectori de utilizator x), timp în care rezolvă într-un mod optim celălalt parametru (vectori de elemente y), minimizând astfel forma pătrată. Algoritmul oscilează între fixarea vectorilor pentru utilizatori şi actualizarea vectorilor pentru elemente, sau invers, până când sunt îndeplinite criteriile de convergență (Kabiljo, 2015).

Pentru a măsura calitatea recomandărilor, înainte de a efectua un test actual, se poate folosi un eșantion de date existente pentru a calcula unele valori local, despre cât de diferite sunt estimările date de sistem faţă de preferințele reale ale utilizatorului.

În timpul algoritmului, pentru un anumit procent din utilizatori, sistemul celor de la Facebook clasifică toate elementele neclasificate, adică elementele care nu sunt incluse în setul de antrenare și observă unde se află elementele de antrenare și de testare în lista de recomandări clasificate. Apoi, se poate evalua modelul, calculându-se eroarea medie pătrată a rădăcinilor (RMSE), care amplifică contribuțiile erorilor absolute între predicții și valorile reale (Kabiljo, 2015).

Pentru a obține recomandările propriu-zise pentru toți utilizatorii, trebuie să se găsească articolele cu cele mai mari evaluări estimate pentru fiecare utilizator, dar când vine vorba de seturi de date uriașe, acest proces devine imposibil uneori.

O posibilă soluție luată în considerare de cei de la Facebook prin care problema poate fi rezolvată este prin gruparea (clusterizarea) elementelor bazate pe vectorii caracteristicilor elementului (item feature vectors), ceea ce reduce problema de a găsi cele mai bune grupuri (clustere) de recomandări și apoi extragerea elementelor potrivite, bazate pe aceste grupuri. Această abordare accelerează calculele, dar în acelaşi timp aduce o ușoară degradare a calității recomandărilor bazate pe rezultatele experimentale. Pe de altă parte, elementele dintr-un cluster sunt similare și se poate obține un set divers de recomandări, luând un număr limitat de elemente din fiecare cluster (Kabiljo, 2015).

În ceea ce priveşte lucrul cu datele implicite, pentru cei de la Facebook primele iterații au inclus pagini sau grupuri care se alătură ca semnale pozitive. Semnalele negative de pe Facebook nu sunt la fel de frecvente, acestea includ lipsa sau ştergerea unei pagini sau părăsirea unui grup după ceva timp. De asemenea, acest lucru nu înseamnă că un utilizator are un feedback negativ pentru acel element. În schimb, acesta a pierdut interesul faţă de subiect sau nu doreşte să mai primească actualizări (Kabiljo, 2015).

Pentru a primi recomandări bune, există o nevoie semnificativă de a adăuga elemente negative din perechile neevaluate din colecție. Abordările anterioare includ selectarea aleatorie a eșantionului de formare negativă din elementele neevaluate, care conduc la o soluție non-optimă, sau tratarea tuturor evaluărilor necunoscute ca negative, ceea ce crește în mod incredibil complexitatea algoritmului. Aici, cei de la Facebook au implementat adăugarea de evaluări aleatorii negative luând în considerare utilizatorul și gradele de element, adăugând ratinguri negative proporționale cu gradul de utilizare bazat pe distribuția gradului de element, și cântărind ratingurile negative mai puțin decât cele pozitive (Kabiljo, 2015).

Pe de altă parte, exită feedback implicit de la utilizator, indiferent dacă acesta vizionează în mod activ pagina, preferă sau comentează postările dintr-un grup. Facebook a implementat de asemenea şi algoritmul ALS pentru seturile de date implicite. În loc să încerce să modeleze direct matricea evaluărilor, această abordare tratează datele ca o combinație de preferințe binare și valori de încredere. Evaluările sunt apoi legate de nivelul de încredere în preferințele utilizatorilor, mai degrabă decât de evaluările explicite oferite elementelor. Cu toate acestea, după rularea algoritmului de factorizare a matricelor, aceştia au un alt proces Giraph pentru a calcula recomandările propriu-zise pentru toți utilizatorii.

Sistemele de recomandare apar ca instrumente importante pentru estimarea preferințelor utilizatorilor. Cadrul acestora pentru matricile de factorizare și calculul recomandărilor de top ale utilizatorilor este capabil să gestioneze eficient seturile de date masive ale Facebook-ului, cu 100 de miliarde de evaluări. Sistemul este ușor de folosit și se poate extinde cu alte abordări, dar pentru a menţine gradul de noutate, trebuie să fie într-o continuă dezvoltare.

Amazon.com este o companie americană de comerţ online care în 1995 a fost lansată și online, începând cu vânzarea online de cărți și continuând cu produse VHS, DVD, CD-uri cu muzică, programe de calculator, electronice, îmbrăcăminte, mobilier, jucării etc.

Creşterea fantastică a veniturilor Amazon se datorează integrării cu succes a recomandărilor în cadrul experienței de cumpărare. La Amazon, algoritmul de recomandare este utilizat pentru a personaliza magazinul online pentru fiecare client. Magazinul se schimbă radical pe baza intereselor clienților, prezentând titluri de programare unui inginer software și jucării pentru bebeluși unei mame.

Activarea sugestiilor personalizate în comerțul electronic este probabil motivul numărul unu pentru motoarele de recomandare, din cauza obiectelor rare, obscure care nu sunt foarte populare. Recomandarea unor elemente de acest tip către cumpărători este esențială, deoarece, dacă este reușită, are potențialul de a da rentabilitate investiției pe termen lung (Linden, 2003).

Algoritmii de recomandare utilizaţi de cei de la Amazon se bazează pe elemente aparent puține: istoricul de achiziții al unui utilizator, articolele din coșul de cumpărături, articolele pe care le-a evaluat și le-a plăcut și ce alţi clienți au vizionat și cumpărat. Cu toate acestea, pentru un comerciant de talia celor de la Amazon, provocarea apare în momentul în care trebuie să decidă ce recomandări să prezinte și în ce ordine. O problemă secundară este una de diversitate, cum ar fi cum să arate o selecție diversă de elemente în recomandarea utilizatorului. Amazon poate atinge un nivel înalt de relevanță pentru clienți, prin algoritmi bazați pe procesul numit filtrare colaborativă (Linden, 2003).

Importanța sugerării elementului potrivit pentru utilizatorul potrivit poate fi măsurată prin faptul că se estimează că 35% din totalul vânzărilor sunt generate de motorul de recomandare. Amazon investește o mare cantitate de resurse pe îmbunătățirea tehnologiei de învățarea automată pentru a face motoare de recomandare care să învețe și să măsoare mai eficient. Învățarea automată implică o putere de calcul masivă în rețea, pentru a permite forme mai complexe de algoritmi (Linden, 2003).

Amazon utilizează algoritmi de recomandare pentru a-și personaliza site-ul web în funcție de interesele fiecărui client. Deoarece algoritmii de recomandare existenți nu pot scala zeci de milioane de clienți și produse, aceştia au dezvoltat propriul lor algoritm ce măsoară seturi de date masive și produce recomandări de înaltă calitate în timp real.

În loc să potrivească utilizatorul cu clienţi asemănători, algoritmul creat de ei, bazat de filtrarea colaborativă de tipul element-element, potriveşte elementele achiziţionate şi evaluate de utilizator cu elemente similare, apoi combină aceste rezultate într-o listă de recomandări.

Pentru a determina cea mai asemănătoare potrivire pentru un anumit element, algoritmul construiește un tabel de similarităţi prin găsirea de elemente pe care clienții au tendința să le achiziționeze împreună. S-ar putea construi o matrice produs-produs prin trecerea prin toate perechile de elemente și calculând o metrică de similaritate pentru fiecare dintre acestea. Totuşi, multe perechi de produse nu au clienți comuni și, prin urmare, abordarea este ineficientă în ceea ce privește timpul de procesare și utilizarea memoriei (Linden, 2003).

Este posibil ca asemănarea dintre două elemente să se calculeze în diverse moduri, dar o metodă comună este de a folosi măsura cosinusului, în care fiecare vector corespunde unui element mai degrabă decât unui client, iar dimensiunile vectorului corespund clienților care au cumpărat acel element.

Având în vedere un tabel ce conţine similarităţile dintre produse, algoritmul găsește elemente similare cu achizițiile și evaluările fiecăruia dintre utilizatori, agregă articolele respective și apoi recomandă cele mai populare sau corelate elemente. Acest calcul este foarte rapid, depinzând numai de numărul de articole pe care utilizatorul le-a cumpărat sau evaluat (Linden, 2003).

Cheia pentru scalabilitate și performanță, dată de filtrarea colaborativă bazată pe relaţiile de tip element-element, este că generează tabelul cu articole similare offline. Componenta online a algoritmului, care caută elemente similare pentru achizițiile și evaluările utilizatorilor, scade independent de dimensiunea catalogului sau de numărul total de clienți. Este dependentă numai de numărul de titluri pe care le-a cumpărat sau le-a evaluat. Astfel, algoritmul este rapid chiar și pentru seturile de date extrem de mari. Deoarece algoritmul recomandă elemente similare, calitatea recomandărilor este excelentă. Spre deosebire de filtrarea colaborativă tradițională, algoritmul funcționează bine și cu date limitate de utilizatori, producând recomandări de înaltă calitate bazate pe doar două sau trei elemente (Linden, 2003).

În mai 2016, Amazon a lansat această tehnologie ca platformă Cloud. Compania a lansat DSSTNE, un cadru de inteligență artificială open-source, pe care Amazon l-a dezvoltat pentru a-și întări propriul sistem de recomandări de produse (Linden, 2003).

Aceştia au crescut astfel probabilitatea ca un dezvoltator din afara Amazonului să găsească o modalitate de a face sistemul de recomandări mai bun. În cele din urmă, compania dorește să creeze un sistem care să se poată îmbunătăți în ceea ce privește estimarea produselor pe baza unor date mai mici și, desigur, a produselor pe care clienții au mai multe șanse să le vizualizeze și să le cumpere.

Facebook, Netflix şi Amazon nu sunt singurele site-uri care utilizează sisteme de recomandări. Cele mai multe site-uri web comerciale și sociale pe scară largă recomandă utilizatorilor opțiuni, cum ar fi produsele sau persoanele cu care se conectează. Motoarele de recomandare sortează cantități masive de date pentru a identifica preferințele potențiale ale utilizatorilor. Putem găsi sisteme de recomandări în multe alte site-uri web pe care le utilizăm în fiecare zi.

LinkedIn, site-ul de rețele sociale orientate spre afaceri, formulează recomandări utilizatorului pentru persoane pe care le cunoaște, locuri de muncă care s-ar putea să-i placă, grupuri pe care şi-ar dori să le urmărească sau companii despre care ar putea fi interesat. LinkedIn foloseste Apache Hadoop pentru a-şi construi sistemul de recomadări bazat pe filtrarea colaborativă.

Alte site-uri care includ motoare de recomandare sunt Twitter, Google, MySpace, Pandora, site-uri pe care putem asculta muzică gratuită și viziona videoclipuri și site-ul nostru preferat de știri online, utilizarea unui motor de recomandare devenind astfel un element standard al unei prezențe web moderne.

În viitor, este de aşteptat ca industria comerțului să aplice în măsură mai mare algoritmi de recomandare pentru marketingul orientat, atât online, cât și offline. În timp ce firmele de comerț electronic au toate sisteme de personalizare, standardele ridicate ale tehnologiei privite în comparație cu abordările tradiționale, vor face, de asemenea, constrângeri față de comercianții offline pentru utilizarea acestora în corespondența poștală și în alte forme de comunicare cu clienții.

În continuare este prezentat un tabel ce ilustrează diferenţele şi asemănările dintre sistemul de recomadări RecMov şi cele oferite de cei de la Netflix, Facebook şi Amazon.

SistemeRecMovNetflixFacebookAmazon
CF date explicite

CF date implicite

Recomandări user-item

Recomandări user-user

X

x

Recomandări item – item

x

Regularizarea parametrilor pentru micşorarea valorii metricii RMSE

Mediul de lucru utilizat pentru dezvoltarea sistemului RecMov este platforma IntelliJ IDEA deoarece este o platformă pentru construirea de IDE2-uri inteligente, este open source si are un set cuprinzător de componente, printre care:, sistem de fișiere virtuale, interfața UI , editor de text, lexicografie, parsare, sintaxa abstractă, cadre pentru implementarea navigației, completarea codului, inspecții, refactorizări etc., integrarea controlului versiunii.

Un proiect este o unitate organizațională de nivel înalt de dezvoltare în IntelliJ. În forma sa finalizată, un proiect poate reprezenta o soluție software completă. Un proiect are unul sau mai multe module ca părți ale acestuia. IntelliJ IDEA stochează datele de configurare pentru proiecte și componentele acestora în fișiere XML cu text simplu, facilitând gestionarea și partajarea datelor de configurare ale proiectului cu alții.

Deoarece limbajul de programare ales pentru dezvoltarea sistemului RecMov este Scala (Hunt, 2014), s-a optat pentru un proiect ce utilizează modulul SBT3 pentru procesul de build.

SBT este un sistem open source pentru Scala, cât şi pentru Java, inițial fiind proiectat și implementat în Scala.

Caracteristicile cheie ale SBT-ului sunt (Hunt, 2014):

  • configuraţie minimă pentru proiecte simple

  • suport pentru Scala şi multe framnework-uri pentru Scala Tests

  • build tasks scrise în Scala DSL4

  • sprijin pentru dependențe prin Ivy (sistem de gestionare al dependențelor care se ocupă de versiunea și dependențele dintre biblioteci)

  • integrare cu Scala Interpreter

SBT-ul este utilizat în multe proiecte Scala, inclusiv în construcţia limbajului de programare în sine. SBT-ul oferă un mod interactiv în care se poate utiliza o consolă pentru a emite o serie de comenzi și de a controla procesul de build.

Scala este un nou limbaj de programare dezvoltat de Martin Odersky și echipa sa de la EPFL (Ecole Polythenique Fererale de Lausanne, Lausanne, Elveția) și susținută acum de Typesafe5. Numele Scala este derivat din Sca (lable) şi La (nguage) și este un limbaj de programare ce încorporează abordări orientate pe obiecte cu programarea funcțională. Aceasta înseamnă că se pot scrie aplicaţii orientate spre obiecte pure folosind clase, obiecte și trăsături, putând exploata moștenirea, polimorfismul și tehnici de abstractizare și încapsulare (Hunt, 2014). Scala se evidenţiază în special atunci când vine vorba de un software scalabil care utilizează procesarea simultană și sincronă, utilizarea paralelă a mai multor nuclee și prelucrarea distribuită. Natura sa funcțională facilitează scrierea codului sigur și performant cu mai multe fire de execuţie, oferind instrumente puternice pentru organizarea unui sistem concurent la un nivel ridicat de abstractizare. (Odersky, 2010).

Apache Spark este o platformă de calcul pe cluster concepută pentru a fi rapidă, ce extinde modelul popular MapReduce pentru a suporta în mod eficient mai multe tipuri de calcule, inclusiv interogări interactive și procesarea fluxurilor.

Viteza este importantă în prelucrarea seturilor de date mari, deoarece înseamnă diferența dintre explorarea datelor interactiv și așteptarea minutelor sau orelor. Una dintre principalele caracteristici oferite de Spark pentru viteză este capacitatea de a executa calcule în memorie, dar sistemul este totodată și mai eficient decât MapReduce pentru aplicațiile complexe care rulează pe disc (Karau, 2015).

MLlib este biblioteca Spark (Pentreath, 2016) ce conţine funcții de învățare automată. Concepută pentru a funcționa în paralel pe clustere, MLlib conține o varietate de algoritmi de învățare și este accesibil din toate limbajele de programare ale Spark-ului.

Algoritmii de învățare automată încearcă să facă previziuni sau decizii bazate pe antrenarea datelor, adesea maximizând un obiectiv matematic la modul în care ar trebui să se comporte un algoritmul. Există mai multe tipuri de probleme de învățare, inclusiv clasificarea, regresia sau clusterizarea, care au obiective diferite. Toți algoritmii de învățare necesită definirea unui set de caracteristici pentru fiecare element, care va fi introdus în funcția de învățare. De exemplu, pentru un e-mail, unele funcții ar putea include serverul de la care vine, numărul de mențiuni despre un cuvânt sau culoarea textului. În multe cazuri, definirea caracteristicilor corecte este cea mai dificilă parte a utilizării învățării automate. De exemplu, într-o sarcină de recomandare a produsului, pur și simplu adăugarea unei alte caracteristici ar putea da o îmbunătățire importantă a rezultatelor.

Majoritatea algoritmilor (Ryza, 2014) sunt definiți numai pentru cazuri numerice, în mod specific, un vector al numerelor reprezentând valoarea pentru fiecare caracteristică, un pas important fiind extragerea și transformarea caracteristicilor pentru a produce aceşti vectori de caracteristică. De exemplu, pentru clasificarea textului există mai multe metode de a caracteriza datele, cum ar fi numărarea frecvenței fiecărui cuvânt.

Sistemul RecMov are la bază filtrarea colaborativă oferită de librăria MLlib din Spark (Yavuz, 2014) pentru motorul său de recomandări de filme. Aceasta utilizează o bază de date preluată de la cei de la MovieLens (GroupLens) care pun la dispoziţie o gamă variată de seturi de informaţii. Pentru aplicaţia creată s-a ales o bază de date medie, ce conţine peste un milion de evaluări de la aproximativ 6000 de utilizatori pentru 3706 filme.

MLlib include o implementare a Alternating Least Squares (ALS)6, un algoritm popular pentru filtrarea colaborativă. Acesta este situat în clasa mllib.recommendation.ALS. ALS funcționează prin determinarea unui vector caracteristic pentru fiecare utilizator și produs, astfel încât produsul punct al vectorului unui utilizator și al unui produs este aproape de scorul lor. Din punct de vedere matematic, acest algoritm tratează datele utilizatorilor și ale produselor ca și cum ar fi o matrice mare rară A, în care intrarea la rândul i și coloana j există dacă utilizatorul a vizionat filmul j. Acesta factorizează A ca produsul matrice a două matrici mai mici, X și Y. Ambele au mai multe rânduri deoarece A are mai multe rânduri și coloane, dar ambele au doar k coloane. Coloanele k corespund factorilor latenți care sunt utilizați pentru a explica datele de interacțiune (Ryza, 2014).

Sistemul RecMov este structurat în doua părţi principale, una în care modelul este antrenat cu date explicite şi una în care este antrenat cu date implicite. Principala funcţionalitate a aplicaţiei este aceea de a oferi recomandări de filme utilizatorilor, pe baza filmelor deja evaluate de ei. Aceste recomandări se fac prin intermediul modelului generat de algoritmul ALS, antrenat atât cu date explicite, cât şi implicite, care va prezice ulterior preferinţele utilizatorilor.

Cu evaluări explicite, scorul fiecărui utilizator pentru un produs trebuie să fie un număr, iar evaluările prezise vor fi tot scoruri. Cu datele implicite, fiecare evaluare reprezintă o încredere că utilizatorii vor interacționa cu un anumit element, iar elementele prezise vor fi valori de încredere. Urmând aceste pricipii s-au creat câteva reguli care să se muleze pe datele explicite preluate de la cei de la GroupLens, astfel încât să se reușească să se transforme setul de date într-unul implicit.

Pe baza acestor rezultate sunt calculate mai multe metrici ce au rolul de a măsura precizia şi consistenţa modelului, precum RMSE (Root Mean Squared Error) şi MSE (Mean Squared Error) (MAE & RMSE; online), care au ajutat la determinarea parametrilor potriviţi pentru antrenarea modelului, astfel încât să se obţină o eroare cât mai mică, implicit rezultate mai bune.

Pe langă funcţionalitatea de a oferi recomandări de filme utilizatorilor, sistemul RecMov pune la dispoziţie şi serviciul de similaritate, între filme sau între membri. Există posibilitatea de a genera un top de zece filme similare unui anumit film selectat, implicit, posibilitatea de a genera şi utilizatori similari, împreună cu o listă ce conţine cele mai bine cotate filme evaluate de aceştia, pentru a uşura observarea similarităţilor la o primă vedere.

În producție, motoarele de recomandare trebuie adesea să facă recomandări în timp real, deoarece sunt utilizate în contexte precum site-urile de comerț electronic unde recomandările sunt solicitate frecvent pe măsură ce clienții navighează pe paginile cu produse. O abordare viitoare ar putea fi combinarea mai multor algoritmi de învăţare automată pentru a oferi recomandări în timp real utilizatorilor, dar şi îmbunătăţirea acestui algoritm pentru a minimiza valoarea metricii RMSE, pentru un model mai precis. Acest lucru ar putea fi realizat generând parametrii pentru regularizarea modelului într-un mod offline, iar pe baza acestor parametrii rezultaţi să antrenăm modelul pentru a genera recomandări în timp real, problema timpului de execuţie fiind eliminată în acest fel. Totodată, ar fi interesant de observat cum reacţionează aplicaţia la un set de date mult mai mare, fapt ce implică automat rularea pe cluster, pentru a minimiza timpul de execuţie.

Referințe

  • Amatriain, Xavier and Justin Basilico (2012). Netflix Recommendations: Beyond the 5 stars, Aprilie 5, 2012. Disponibil la: http://medium.com/netflix-techblog/netflix-recommendations-beyond-the-5-stars-part-1-55838468f429
  • Collaborative Filtering. Disponibil la: http://spark.apache.org/docs/2.1.0/mllib-collaborative-filtering.html#collaborative-filtering
  • Hunt, John (2014). A Beginner’s Guide to Scala, Object Orientation and Functional Programming, Springer International Publishing Switzerland, 2014
  • Kabiljo, Maja and Aleksandar Ilic (2015). Recommending items to more than a billion people”, Iunie, 2015. Disponibil la: http://code.facebook.com/posts/861999383875667/ recommending-items-to-more-than-a-billion-people/
  • Karau, Holden , Andy Konwinski, Patrick Wendell, and Matei Zaharia (2015). Learning Spark, Published by O’Reilly Media, Inc., 1005 Gravenstein Highway North, Sebastopol, CA, February, 2015
  • Linden, Greg, Brent Smith and Jeremy York (2003). Amazon.com Recommendations Item-to-Item Collaborative Filtering, Ianuarie, 2003. Disponibil la: http://www.cs.umd.edu/~samir/ 498/Amazon-Recommendations.pdf
  • MAE and RMSE — Which Metric is Better?. Disponibil online la: http://medium.com/ human-in-a-machine-world/mae-and-rmse-which-metric-is-better-e60ac3bde13d
  • MovieLens. Disponibil la: http://grouplens.org/datasets/movielens/
  • Odersky, Martin, Lex Spoon and Bill Venners (2010). Programming in Scala, Second Edition, PrePrint™ eBook, 2010
  • Pentreath, Nick (2016). Building a Recommendation Engine with Spark, February, 2016. Disponibil la: http://www.packtpub.com/books/content/building-recommendation-engine-spark
  • Ryza, Sandy, Uri Laserson, Sean Owen, and Josh Wills (2014) Advanced Analytics with Spark, Published by O’Reilly Media, Inc., 1005 Gravenstein Highway North, Sebastopol, CA, January, 2014.
  • Yavuz, Burak, Xiangrui Meng and Reynold Xin (2014). Scalable Collaborative Filtering with Apache Spark MLlib. Engineering Blog. Disponibil la: http://databricks.com/blog/2014/07/23/scalable-collaborative-filtering-with-spark-mllib.html
  • 1 nod ce rulează o aplicaţie Spark pe Cluster

  • 2 Integrated development environment, aplicaţie software care oferă facilităţi complexe pentru dezvoltarea de software

  • 3 Simple Build Tool – instrument de build pentru proiectele Scala

  • 4 Domain Specific Language – limbaj specializat pe un domeniu particular

  • 5 Companie înfiinţată de Martin Odersky, care pune la dispoziţie o platformă open-source pentru a construi aplicaţii pentru JVM

  • 6 „Collaborative filtering“, http://spark.apache.org/docs/2.1.0/ml-collaborative-filtering.html