Preporuka je, prema definiciji iz [17], povoljno pismeno ili usmeno mišljenje, odnosno povoljna ocjena o svojstvima koga ili čega. Svakodnevno se, pri donošenju i najjednostavnijih odluka, oslanjamo na preporuke osoba iz svoje okoline. Bilo da se radi o prehrambenoj namirnici, odjevnom predmetu, knjizi ili novom filmu, uvijek nas unaprijed zanima isplati li se na to utrošiti vrijeme i novac. Kako bismo dobili informacije o novim stvarima najčešće o njima raspravljamo s osobama iz okoline. Ukoliko znamo da nam je netko blizak po ukusu, njegovu preporuku uvažavamo više i obratno te u skladu s tim rangiramo stvari i odlučujemo.

Devedesetih godina prošlog stoljeća trgovine, knjižare i kina pronašli su svoje mjesto u virtualnom svijetu što im je omogućilo veću ponudu proizvoda od one na fizičkim policama (engl. long tail phenomen1).

Veliki broj proizvoda i ograničen prikaz informacija o proizvodima korisnicima je otežao pretragu i odlučivanje o njima. Također, trgovcu u klasičnoj trgovini moguće je postaviti pitanje kako bi nam preporučio proizvod sličan onom koji smo nedavno kupili, ali gotovo je nemoguće bilo postaviti isto pitanje internet trgovini i dobiti željeni odgovor. Već na samom početku razvoja internet trgovina, kina i knjižara bilo je očito da standardni način preporuke i otkrivanja novih stvari ima velike nedostatke i ograničenja, a posebice pri razmjeni novih informacija. Za više informacija vidi [1].

Upravo je to potaknulo istraživače na kreiranje automatiziranih sustava koji bi pomogli korisniku pretražiti proizvode i ubrzati on-line kupnju, a istovremeno bili pouzdani i točni. Kako bi ti sustavi postali što sličniji pravim trgovcima i korisnikovim poznanicima trebali bi naučiti ukus svakog pojedinog korisnika ili prepoznati korisnike sa sličnim ukusom te na temelju tih informacija svakom korisniku pružiti personaliziranu preporuku o onome što bi sljedeće mogao pregledati i kupiti.

Srećom, takvi sustavi su ubrzo razvijeni i danas se nalaze u pozadini gotovo svake internetske trgovine, knjižare, aplikacije za gledanje filmova ili slušanje glazbe. Prilikom posjeta YouTube-u, Amazon-u ili Netflix-u već na početnoj stranici aplikacije prikazuje se sadržaj koji bi nam se mogao svidjeti, a u njihovoj pozadini nalaze se spomenuti sustavi koje nazivamo sustavi za preporuke.

Sustavi za preporuke zajedničko je ime za algoritme koji na temelju informacija o korisnicima i proizvodima daju korisnicima preporuke za nove proizvode koji bi im se mogli svidjeti. Dvije su osnovne kategorije sustava za preporuke, kolaborativno filtriranje (engl. collaborative filtering, u nastavku CF sustavi) i kontekstno bazirani sustavi za preporuke (engl. content based, CB). Algoritmi iz skupine kontekstno baziranih sustava za preporuke stvaraju preporuku na temelju proizvoda koje je korisnik kupio ili pozitivno rangirao te preporučuju proizvode sličnoga tipa. Suprotno tome, sustavi za preporuke bazirani na kolaborativnom filtriranju stvaraju preporuku na temelju usporedbe s ostalim korisnicima i preporučuju proizvode koje su njemu slični korisnici kupili ili pozitivno rangirali. Kombinaciju kontekstno baziranih sustava i kolaborativnog filtriranja nazivamo hibridni sustavi za preporuke.

Povijesno gledano, možemo reći da je začetnik automatiziranih sustava za preporuke Grundy, računalni program za knjižnicu (1979. godine) (za više informacija vidjeti [15]). Xerox PARC razvio je 1992. godine Tapestry, platformu koja je korisnicima omogućila označavanje emailova i pretraživanje istih na temelju tih oznaka. Najpoznatija primjena sustava za preporuke je ona na domeni Amazon.com2. Sustavi za preporuku najveću pozornost privukli su 2006. godine kada je Netflix3 objavio Netflix Prize, nagradu od milijun dolara za kreiranje algoritma koji bi za 10% ubrzao njihov tadašnji algoritam.4 Danas najpoznatiji online sustav za iznajmljivanje filmova, Netflix, pokrenut je 1999. godine, a njegov izvorni sustav za preporuke poznat je pod imenom Cinematch. Netflix prize problem riješen je tek 2009. godine kada su snage ujedinili natjecatelji koji su do tada bili najbliži rješenju u tim pod imenom BellKor's Pragmatic Chaos, a njihov algoritam detaljno je opisan u [12]. Danas su poznate različite vrste sustava za preporuke i njihovi tipovi, a neke od njih predstavit ćemo u ovom radu.

Ovaj rad baziran je na diplomskom radu [5], gdje se može pronaći detaljnija implementacija nekih algoritama koji su opisani u nastavku. U ovom radu opisani su specijalno sustavi za preporuke bazirani na kolaborativnom filtriranju, odnosno jedan tip takvih sustava. U drugom poglavlju su navedene opće karakteristike i podjela sustava za preporuke. U trećem poglavlju opisan je jedan tip sustava za preporuke, točnije kolaborativno filtriranje bazirano na modelu orijentiranom prema proizvodu (engl. item model based collaborative filtering RS) i njegov algoritam temeljen na faktorizaciji matrice i redukciji dimenzije. Dodavanje novog korisnika u sustav i kreiranje preporuka za njega opisano je također u trećem poglavlju, a u četvrtom poglavlju su testirani opisani algoritmi koji su implementirani u programskom paketu Matlab.

Sustavi za preporuke razvijeni su kako bi se što bolje suočilo s eksponencijalnim rastom informacija, u smislu filtriranja podataka. Oni uče iz akcija korisnika o njihovom ukusu kako bi im u skladu s tim predložili nove proizvode, stoga ih istovremeno možemo promatrati kao dio rudarenja podataka i strojnog učenja. Području rudarenja podataka pripadaju zbog svoje namjene, olakšavaju korisniku pretraživanje podataka, a u područje strojnog učenja možemo ih smjestiti jer na temelju podataka o korisniku i proizvodima, uče o njima i prema tome generiraju preporuke.

Iako se sustavi za preporuke intenzivno razvijaju već tridesetak godina, tehnike koje se koriste u algoritmima za generiranje preporuke ostale su relativno jednostavne. Kako bismo objasnili tehnike korištene u algoritmima za preporuke i same algoritme potrebno je prvo navesti osnovne pojmove koji se u njima koriste. Korisnici i proizvodi su dvije osnovne klase entiteta i povezani su tako da korisnici imaju preferencije prema određenim proizvodima, a o njima se zaključuje iz podataka o korisniku ili ih daju sami korisnici. Podatci o vezi korisnika i proizvoda spremaju se u matricu koju nazivamo matrica korisnosti (engl. utility/rating matrix), vidi Tablicu 1.

Svaki element matrice korisnosti predstavlja jedan par korisnik-proizvod i on označava razinu koliko se promatranom korisniku sviđa dani proizvod. Razina sviđanja najčešće se prikazuje vrijednostima iz uređenog skupa elemenata kao što su prirodni brojevi od 1 do 5 koji mogu predstavljati rangiranje proizvoda zvjezdicama. Također, moguće je koristiti binarnu ili ternarnu skalu5, dok je unarna skala najbolja za sustave internet trgovina jer jasno predstavlja povijest korisnikove kupnje. Ako korisnik i proizvod nisu povezani tada se na pripadnom mjestu u matrici nalazi nepoznata vrijednost, odnosno ne postoji izražen stupanj sviđanja korisnika prema proizvodu. Pretpostavka je da je matrica korisnosti rijetko popunjena matrica (engl. sparse matrix), a glavni cilj sustava je predvidjeti vrijednosti na praznim mjestima u matrici korisnosti, što je prikazano na Slici 1.

Slika 1: Ilustracija algoritma za preporuku

Pri modeliranju sustava za preporuke mogu se promatrati i svojstva proizvoda te iz tih sličnosti predvidjeti vrijednosti na praznim mjestima matrice korisnosti. Vrlo je bitno da nije potrebno izračunati svaku nepoznatu vrijednost u matrice korisnosti, nego je dovoljno otkriti samo neke vrijednosti za svaki redak, koje bi potencijalno mogle biti velike. Točnije, kako je navedeno u [9], bitno je pronaći takav podskup nepoznatih vrijednosti za svaki redak za koje predviđamo da će njihove vrijednosti biti među najvećima.

Dvije su osnovne vrste sustava za preporuke, kontekstno bazirani i kolaborativno filtriranje.

Kontekstno bazirani sustavi za preporuke generiraju preporuke tako da za svakog korisnika pronalaze proizvode slične onima koje je korisnik pregledao ili kupio i takvi proizvodi postaju dobri kandidati za preporuku. Kod ovakvih sustava rangiranje je manje bitno, puno je bitnije pronaći sličan sadržaj u skupu svih proizvoda. Ukoliko je takav sustav namijenjen npr. internet videoteci on će generirati preporuke korisniku s obzirom na žanr filmova koje je već pogledao i preporučiti mu bliske filmove. Tehnika kojom se pronalaze slični proizvodi u skupu svih proizvoda jest TF-IDF (engl. term frequency – inverse document frequency) koja predstavlja mjeru koliko je važan neki izraz u skupu dokumenata i ovdje se koristi kako bi sustav mogao zaključiti o ukusu pojedinog korisnika iz njegovih akcija. U takvom sustavu svaki korisnik se promatra kao vektor čiji elementi predstavljaju svojstva proizvoda u sustavu. Vrijednost svakog elementa u tom vektoru su težine za pripadno svojstvo u odnosu na promatranog korisnika.

Dobar primjer domene koja koristi kontekstno bazirani sustav jest pandora.com. Ovakvi sustavi za preporuke korisniku uzastopno preporučuju proizvode koji su slični po svojstvima, što je ujedno njihova prednost i mana (engl. over-specialized search)6. Korisnik mora na neki način sam pokazati interes prema nekom novom tipu proizvoda kako bi mu sustav u buduće mogao preporučiti proizvode s tim svojstvima, što nije slučaj kod kolaborativnog filtriranja. Kod sustava za preporuke baziranih na kolaborativnom filtriranju preporuke se generiraju na temelju korisnikova rangiranja proizvoda, a ne na temelju svojstava proizvoda. Kako je navedeno u [1], osnovni cilj CF sustava je učiti o korisnikovu ukusu na temelju neke mjere (skale) te usporediti promatranog korisnika s ostalim korisnicima tog sustava i pronaći njemu slične korisnike. Važno je da skala kojom će se rangirati proizvodi dovoljno dobro odražava stav korisnika prema proizvodima koji se trebaju rangirati.

Glavna pretpostavka na kojoj se temelje svi CF sustavi jest da ukoliko isti proizvod dva korisnika isto rangiraju, oni će vjerojatno dijeliti isto mišljenje o još nekim proizvodima. Odnosno, ako se jednom od dva slična korisnika sviđa neki proizvod za koji drugi korisnik ne zna, prethodna tvrdnja govori da taj proizvod možemo preporučiti drugom korisniku i on će mu se vjerojatno svidjeti. Sličnost korisnika ili proizvoda računa se unaprijed definiranom funkcijom koju nazivamo funkcija sličnosti (engl. similarity function), a skup najsličnijih korisnika ili proizvoda u odnosu na promatranog korisnika ili proizvod nazivamo susjedstvo (engl. neighbourhood). Zadaća funkcije sličnosti je da numerički predstavi udaljenost između dva korisnika ili proizvoda kako bi se moglo definirati njihovo susjedstvo, odnosno najbliži korisnici ili proizvodi. Neke od najčešće korištenih funkcija sličnosti su euklidska udaljenost, Pearsonova korelacija i kosinus udaljenost. CF sustavi koji se baziraju na pronalasku sličnih korisnika za nekog promatranog korisnika nazivamo sustavi orijentirani prema korisniku (engl. user based), dok CF sustave koji pronalaze slične proizvode za neki promatrani proizvod nazivamo sustavi orijentirani prema proizvodu (engl. item based).

Algoritmi CF sustava orijentirani prema korisniku vode se pretpostavkom da “slični korisnici vole slične proizvode”, dok se oni orijentirani prema proizvodu vode se pretpostavkom da “slične proizvode vole slični korisnici”, kao na Slici 2 gdje je grafički prikazana funkcija sličnosti.

Iako su ova dva pristupa vrlo slična, ovisno o sustavu unutar kojeg su implementirani mogu uvelike utjecati na njegovu skalabilnost7. Ukoliko promatramo sustav sa puno većim brojem korisnika od broja proizvoda, algoritmi orijentirani prema korisniku su loš odabir jer će pronalazak najbližih susjeda biti puno teži u dimenziji korisnika nego što bi mogao biti u dimenziji proizvoda, kojih je manje u bazi. Nadalje, može se reći da je dimenzija korisnika najčešće više dinamička od dimenzije proizvoda, odnosno skup korisnika se češće mijenja od skupa proizvoda, pa je pouzdanije računati sličnosti unutar skupa proizvoda. No, ako promatramo sustav za preporuke u sklopu internetskih novina, tada se skup proizvoda (novosti) sigurno češće mijenja i veći je od skupa korisnika i u tom slučaju algoritmi orijentirani prema korisniku imaju prednost nad algoritmima orijentiranim prema proizvodu. Još jedna prednost algoritama orijentiranih prema proizvodu jest da korisniku mogu dati jasnije objašnjenje preporuke. Činjenica da je neki proizvod preporučen korisniku jer je sličan ostalim proizvodima koji su mu se svidjeli je korisniku ugodnija od one da je proizvod preporučen jer se svidio sličnom korisniku.

 
Slika 2: Grafički prikaz funkcije sličnosti

Uz podjelu CF sustava na orijentirane prema proizvodu i orijentirane prema korisniku, CF sustave možemo podijeliti na one bazirane na modelu (engl. model based) i memorijski bazirane (engl. memory based).

Memorijski baziranima CF sustavima smatramo one kod kojih algoritam računa sličnosti u memoriji, bez prethodno generiranog modela i često se za njih kaže da su bazirani na susjedstvu (engl. neighbourhood based) jer u skupu najboljih susjeda pronalaze najbolje kandidate. Takvi algoritmi podatke o korisnicima i proizvodima drže u memoriji i direktno računaju preporuke, odnosno sličnost među susjedstvom računa se svaki put kada se korisniku želi dati preporuka, još se kaže da je to on-line generiranje preporuke.

CF sustavi bazirani na modelu generiraju model sustava i na temelju njega generiraju preporuku. Kod pristupa baziranom na modelu kažemo da se model kreira off-line odnosno unaprijed, a preporuka se generira on-line na temelju modela. Ova vrsta algoritma doživjela je procvat tijekom istraživanja za Netflix prize 2006. godine, a pobjednički algoritam koristio je tehniku baziranu na modelu. Pri generiranju modela koristi se faktorizacija matrice korisnosti korisnika i proizvoda na dvije matrice u kojima je moguće zaključiti o nekim skrivenim faktorima u sustavu (npr. žanr filma), ali ti faktori često nisu izravno povezani sa stvarnim svojstvima proizvoda ili korisnika. Iako imaju dosta nedostataka, danas su najviše koriste CF sustavi bazirani na modelu koji koriste faktorizaciju matrice korisnika i proizvoda za kreiranje modela. Najveći nedostatak algoritama baziranih na modelu jest da bi se model trebao računati svaki puta kada dođe do veće promjene u početnoj matrici, odnosno svaki puta kada korisnik rangira neki od proizvoda ili se doda novi korisnik u sustav.

Sustavi za preporuke mogu imati vrlo veliku ulogu u marketingu organizacije koja ga koristi, ukoliko je on pouzdan i brzo daje preporuke visoke kvalitete. Može se reći da je porast dobiti organizacije koja koristi sustav za preporuke poželjna posljedica točnih i brzih preporuka. Takvi sustavi najčešće su integrirani u okruženjima s mnogo korisnika i proizvoda zbog čega naizgled laki zadatci postaju vrlo zahtjevni, a primjer tome su domene kao što su Youtube, Netflix, Amazon, eBay8 i slično.

U stvarnim primjerima i primjenama sustavi za preporuke se moraju nositi s različitim problemima, a istaknuli bismo neke od njih: slaba popunjenost podataka, sinonimi, gray sheep i shilling attacks. Više detalja vezano za spomenute probleme može se pronaći u [5, 4].

U okviru ovog rada istaknuli bismo da se slaba popunjenost podataka pojavljuje jer najčešće matrice sustava su vrlo velikih dimenzija zbog mnogo korisnika i proizvoda u okruženju. No, veliki broj korisnika i proizvoda nisu povezani pa su te matrice najčešće jako slabo popunjene (engl. extremely sparse). Slaba popunjenost najveći problem predstavlja pri dodavanju novog korisnika u sustav (engl. cold start problem), tj. kada korisnik još nema niti jedan rangiran proizvod i nema dovoljno informacija o njemu (engl. new user problem). Također, ako se doda novi proizvod, nemoguće je predložiti ga kao preporuku ukoliko ga nitko još nije rangirao (engl. new item problem). Problem popunjenosti podataka može se riješiti smanjenjem dimenzije sustava, a najčešće korištena tehnika za to je SVD dekompozicija matrice sustava.

Nadalje, problem skalabilnosti sustava za preporuke nastaje ukoliko broj korisnika i proizvoda jako brzo raste. Primjerice, za sustav sa deset milijuna korisnika (M) i milijun proizvoda (N), kada bi CF algoritam bio složenosti O(N) on bi bio prespor uzimajući u obzir da algoritam mora raditi jako brzo u stvarnom vremenu. Ovaj problem se isto može riješiti redukcijom dimenzije pomoću SVD dekompozicije. Problem nastaje kod dodavanja novog korisnika ili podataka u matricu, jer ono zahtijeva ponovno računanje dekompozicije dopunjene matrice, ali i on se može vješto riješiti inkrementalnim računanjem novog modela. Što je sustav brži, to je skalabilnost sustava veća, ali posljedica tome je smanjena kvaliteta preporuke. Upravo je to najveći izazov sustava za preporuke, tj. kako u isto vrijeme zadržati što veću kvalitetu preporuke i povećati skalabilnost sustava.

U sljedećem poglavlju opisat ćemo algoritme za CF sustave bazirane na modelu orijentiranom prema proizvodu koji koriste dekompoziciju na singularne vrijednosti (SVD).

Prije nego što uvedemo dekompoziciju na singularne vrijednosti, prisjetimo se da za matricu Q\in\mathbb{R}^{n\times n} kažemo da je ortogonalna ukoliko je Q^{T}Q = I. Analogno, za U\in \mathbb{C}^{n\times n} kažemo da je unitarna ukoliko je U^{*}U = I.

Dekompozicija na singularne vrijednosti ili SVD (engl. singular value decomposition) je metoda matrične dekompozicije koja danu matricu A \in \mathbb{R}^{m\times n} faktorizira na matrice U \in \mathbb{R}^{m\times m}, S\in \mathbb{R}^{m\times n} i V \in \mathbb{R}^{n\times n} čija su svojstva iskazana Teoremom 1.

U ovom poglavlju iskazat ćemo neke od osnovnih svojstava singularne dekompozicije matrice, a više detalja može se pronaći u [2, 8, 6].

Stupce matrice U zovemo lijevi, a stupce matrice V desni singularni vektori matrice A, dok dijagonalne elemente matrice S nazivamo singularnim vrijednostima.

Poznato je da koristeći SVD dekompoziciju možemo efikasno odrediti rang matrice kao i prostor koji razapinje sliku, odnosno jezgru matrice. Naime, prema [8] vrijedi sljedeći teorem.

Prema [14, 2, 6] u nastavku je naveden Teorem 3 koji govori da je pomoću SVD dekompozicije uistinu moguće matricu aproksimirati matricom nižeg ranga tako da je navedena aproksimacija ujedno i najbolja moguća, pri čemu se pogreška aproksimacije mjeri koristeći spektralnu normu [2].

Matrica A_{k} dobivena je korištenjem trojki (u_{i}, \sigma_{i},v_{i}^{T}), i=1,\dots,k koje pripadaju najvećim singularnim vrijednostima. Ona daje aproksimaciju matrice A matricom ranga k. Štoviše, to je najbolja aproksimacija nižeg ranga u skupu matrica ranga manjeg ili jednakog k, za bilo koju unitarnu invarijantnu normu11. Specijalno, ako pogrešku mjerimo u Frobeniusovoj normi (\Vert \cdot\Vert _{F}), vrijedi da je:

Ovaj teorem je od velike važnosti za CF sustave jer omogućuje znatno smanjenje količine podataka koje CF sustav treba obraditi. Umjesto s velikom matricom A reda m \times n sustav može raditi s matricom manjeg ranga A_{k} koja se u faktoriziranom obliku može efikasno zapisati sve dok je k \ll r. Točnije, ovaj teorem daje najbolji mogući način kako se matrica može aproksimirati matricom ranga koji je najviše k.

Matrica S tada se očito aproksimira matricom S_{k} tako da se na dijagonali zadrži najvećih k singularnih vrijednosti, dok se matrice U i V aproksimiraju matricama U_{k} i V_{k}. Matrica U_{k} nastaje zadržavanjem prvih k stupaca iz matrice U, dok zadržavanjem prvih k stupaca matrice V nastaje matrica V_{k} i tada je A_{k}=U_{k}S_{k}V_{k}^{T}.

Jedna od najbitnijih svojstava sustava za preporuke je kvaliteta preporuke. Kvaliteta preporuke može se mjeriti na više različitih načina, a prema [4] osnovni tipovi su: metrike obzirom na predikciju (engl. predictive accurancy metrics), metrike obzirom na rang (engl. rank accurancy metrics) i normalizirana metrika obzirom na udaljenost (engl. normalized distance-based performance metrics).

Tip metrike koji će se koristiti ovisi o namijeni sustava za preporuke. Najčešće korištena metrika je prosječna apsolutna pogreška (engl. mean absolute error, MAE), iz skupa metrika obzirom na predikciju, koja računa prosječnu apsolutnu razliku između procijenjene vrijednosti i prave vrijednosti.

Računamo li točnost preporuke za proizvod j, MAE možemo računati po slijedećoj formuli:

Pri tome je m je broj korisnika, sa R označavamo matricu korisnosti sustava, a prediction_{ij} je procjena za element r_{ij} matrice sustava R, odnosno za procjena za i-tog korisnika i j-ti proizvod. Što je vrijednost za MAE manja, to je preporuka točnija, odnosno kvalitetnija. Iako ovakvi tipovi metrike mogu pomoći kako bi se odredila kvaliteta sustava, odnosno njegove preporuke, korisnicima ponekad nisu od velike koristi kao u slučaju kada korisnik želi nekakav novi, neočekivani rezultat preporuke koji nije u skladu s njegovim dotadašnjim preferencijama. Za takve slučajeve mogu se koristiti metrike nekog drugog tipa, a u ovom radu koristi se navedena MAE metrika pri analizi kvalitete preporuke u ovisnosti o parametrima promatranog algoritma.

Standardni algoritmi za preporuke podijeljeni su u dva osnovna koraka. Prvi korak predstavlja off-line izgradnju modela sustava (engl. model-building step), dok drugi korak (engl. execution step) radi on-line i računa preporuke. Prema [3], algoritam koji će biti predstavljen u nastavku sastoji se od tri osnovna koraka: definiranje matrice korisnika i proizvoda, formuliranje susjedstva i generiranje preporuke.

Prije iskaza samoga algoritma potrebno je uvesti osnovne oznake:

Za određenog korisnika u_{i} potrebno je kreirati preporuku, odnosno predvidjeti koliko će mu se svidjeti proizvod p_{j}, što se može postići sljedećim postupkom.

Algoritam 1 (prema [3])

Slika 3: Ilustracija izračunavanja 5-susjedstva za proizvod i

Uočimo da se u 1. i 2. koraku algoritma matrica sustava konstruira i priprema za daljnji postupak normalizacijom. 3. korak algoritma računa SVD dekompoziciju matrice što je moguće zbog Teorema 1. Zbog tvrdnje iz Teorema 3 korektan je i 4. korak algoritma jer na taj način dobijemo najbolju aproksimaciju nižeg ranga početne matrice sustava. U skladu sa tvrdnjama iz teorema 2 u 5. koraku algoritma možemo promatrati matricu \sqrt{S_{k}}V_{k}^{T} dimenzije k\times n kao matricu k pseudo korisnika i n proizvoda. Zbog svojstva SVD dekompozicije iz Teorema 2 i Teorema 3, koristeći SVD dekompoziciju matrice, u prethodnim koracima smo dobili dobru aproksimaciju početne matrice. 6. korak algoritma koristeći prilagođenu kosinus funkciju sličnosti računa sličnosti između proizvoda i susjedstvo zadanog proizvoda, dok 7. korak prema danoj formuli računa predikciju za zadanog korisnika i proizvod. U tom zadnjem koraku predikcija se za danog korisnika u_{i} i proizvod p_{j} računa uzimajući u obzir proizvode iz skupa l-susjeda za proizvod p_{j}, a svakom pripadnom pseudo korisniku \hat{r}_{ik}, za k=1,\ldots,l mora se dodati prosjek retka za pripadnog korisnika, tj. \overline{r_{i}}, koji je bio oduzet u 2. koraku pri normalizaciji.

Prema [3] složenost standardnog algoritma bez koraka redukcije je \mathcal{O}(mn^{2}), a s redukcijom dimenzije na rang k\ll m, kako je navedeno u 4. koraku prethodnog algoritma, složenost je \mathcal{O}(kn^{2}). Stoga se može zaključiti da je zbog redukcije početne matrice, što je moguće zbog Teorema 3, povećana skalabilnost sustava, smanjena potreba za količinom on-line memorije i ubrzano izvršavanje algoritma.

Dva su osnovna parametra koja mogu utjecati na kvalitetu ovoga algoritma, a to su: parametar k koji određuje dimenziju reduciranog sustava i parametar l koji određuje dimenziju susjedstva promatranog proizvoda.

Kako je prethodno navedeno, parametar k određuje broj singularnih vrijednosti matrice S koje će se zadržati u matrici S_{k}, odnosno određuje rang matrice R_{k} i broj pseudo korisnika u reduciranom sustavu. Parametar k bira se tako da bude što manji kako bi utjecao na poboljšanje brzine i efikasnosti te ujedno mora biti takav da reducirani sustav zadrži što više svojstava početnog sustava, ali da ne bude preblizak početnom sustavu (engl. overfitting). Fiksiranjem parametra l može se eksperimentom za različite k odrediti onaj koji prema MAE daje najbolju preporuku za dani sustav. Slika 4 prikazuje rezultate eksperimenta koji je u [3] proveden na sustavu od 943 korisnika i 1682 proizvoda za različite vrijednosti parametra k, k={2,4,6,8,10,15,20,25} i fiksan parametar l=60. Obzirom na promjenu parametra k mijenja se kvaliteta preporuke mjerena metrikom MAE. U početku povećanjem parametra k MAE brzo doseže minimum za k=6, odnosno kvaliteta doseže maksimum za k=6, daljnjim povećanjem parametra k MAE raste i kvaliteta se smanjuje, pa se za najbolji k uzima k=6. Svakako, odabir najboljeg parametra k ovisi o veličini danog sustava i popunjenosti matrice korisnosti. Što je k veći, podatci u reduciranoj matrici sustava biti će bliži podatcima početnog sustava, odnosno biti će raspršeniji pa će i preporuka biti lošija.

Slika 4: Eksperiment za različite vrijednosti parametra k. Prikaz prosječne apsolutne pogreške (MAE) za sustavu od 943 korisnika i 1682 proizvoda za različite vrijednosti parametra k, k={2,4,6,8,10,15,20,25} i fiksan parametar l=60.Najbolja kvaliteta postiže se za k=6 .

Veličina susjedstva, l, koje se promatra za određeni proizvod također ima utjecaj na kvalitetu preporuke. Najčešće slučaj je da je za blisko susjedstvo kvaliteta prema MAE niska, zatim proširenjem susjedstva MAE dostiže minimum, odnosno postiže se maksimalna kvaliteta za određeni broj susjeda. Nakon toga MAE postepeno raste što je prikazano na Slici 5, a to znači da kvaliteta predikcije opada za veliko susjedstvo. Eksperiment sa slike proveden je u [3] na sustavu koji sadrži 943 korisnika i 1682 proizvoda. Za različite vrijednosti parametra l, l=\lbrace 10,20,30,40,60,80,100,120,140\rbrace i k=6 ispitana je kvaliteta sustava u odnosu na MAE metriku, a za najbolje susjedstvo određeno je ono od 10 proizvoda. Očito je da veliko susjedstvo negativno utječe na kvalitetu preporuke jer su podatci tada raspršeniji, također optimalne vrijednosti za oba parametra, k i l, ovisit će o skupu podataka nad kojima se određuju.

Slika 5: Eksperiment za različite vrijednosti parametra l. Prikaz prosječne apsolutne pogreške (MAE) za sustav od 943 korisnika i 1682 proizvoda za različite vrijednosti parametra l, l=\lbrace 10,20,30,40,60,80,100,120,140\rbrace i fiksan parametar k=6. Najbolja kvaliteta postiže se za l=10 .

Nedostatak CF algoritama baziranih na SVD dekompoziciji jest da se vrijeme računanja SVD dekompozicije povećava povećanjem broja proizvoda i korisnika u sustavu. Nadalje, dodavanjem novog korisnika u sustav ili pri promjeni početne matrice zbog novih vrijednosti iznova se mora off-line računati SVD dekompozicija sustava, što nije trivijalan postupak. U nastavku je opisan algoritam koji inkrementalno osvježava početni sustav nakon dodavanja novog korisnika.

Glavni problem prethodnog algoritma jest kako dodati korisnika u sustav bez ponovnog računanja modela cijelog sustava, odnosno bez ponovnog računanja SVD dekompozicije cijele matrice korisnosti. U matričnom jeziku, za dani novi vektor r_{new} i već poznatu matricu R potrebno je napraviti SVD dekompoziciju nove matrice \left[ \begin{array}{c} R \\ r_{new} \end{array} \right] koristeći već postojeću SVD dekompoziciju matrice R. U [13] je dan postupak kako je moguće u sustav dodati novi vektor korisnika r_{new}\in\mathbb{R}^{1\times n} bez ponovnog računanja SVD dekompozicije matrice sustava.

Algoritam 2

Nakon folding-in metode ponovno se izvršavaju koraci 5., 6. i 7. iz Algoritma 1, samo umjesto matrice U_{k} koristimo matricu \hat{U_{k}}.

Postupak je moguće ponavljati više puta pri dodavanju jednog ili više korisnika odjednom. Nakon nekoliko iteracija, ovisno o količini i strukturi podataka koji su dodani, sustav će izgubiti na kvaliteti te će se morati ponovno off-line izračunati SVD dekompozicija za matricu R i nove podatke. Algoritam 2 je vrlo jeftin i dobar način osvježavanja za sustave u kojima se novi korisnici ne dodaju često. No, kako se matrice V_{k} i S_{k} nikada ne mijenjaju, kvaliteta preporuke se postupno smanjuje dodavanjem sve većeg broja korisnika, a ponovno računanje SVD dekompozicije sustava je neizbježno, ponekad i nakon samo par novih korisnika. Primjer dodavanja novog korisnika u sustav dan je u Poglavlju 4.3.

Update metoda osvježavanja sustava pri dodavanju novog korisnika je složenija od folding-in metode, no krajnji rezultat ove metode je točna SVD dekompozicija novog sustava, do na pogrešku zaokruživanja, bez ponovnog računanja cijele SVD dekompozicije. Ovim postupkom se pri dodavanju novog korisnika u sustav odmah osvježava i prostor proizvoda u sustavu.

Pretpostavimo da u sustav želimo dodati novog korisnika kojeg možemo prikazati pomoću vektora r_{new}\in\mathbb{R}^{1\times n}. Matrica sustava je prethodno izračunata matrica R_{k} = U_{k}S_{k}V_{k}^{T} i poznajemo sve \overline{s_{j}} prosjeke stupaca matrice R. Zadaća metode update je osvježiti matrice U_{k}, S_{k}, V_{k} novim podatcima i prosjeke svih stupaca \overline{s_{j}} te dodati nove podatke u sustav. Prema [9],[13] i [11] algoritam za metodu update možemo iskazati na sljedeći način:

Algoritam 3

Nakon postupka update metode ponovno se izvršavaju koraci 5., 6. i 7. iz Algoritma 1, ali koristeći nove osvježene matrice \hat{S_{k}}, \hat{U_{k}} i \hat{V_{k}} i s osvježenom matricom sustava.

Prema [11], ukoliko se u jednoj iteraciji algoritma želi u sustav dodati više od jednog korisnika, točnije p korisnika, možemo to učiniti na sljedeći način.

Algoritam 4

Također, kao kod Algoritma 3, nakon što se provede postupka update metode ponovno se izvršavaju koraci 5., 6. i 7. iz Algoritma 1, ali koristeći nove osvježene matrice \hat{S_{k}}, \hat{U_{k}} i \hat{V_{k}} i s osvježenom matricom sustava.

Lako se može zaključiti da i ova metoda osvježavanja ima nedostatke, pogotovo ukoliko se odjednom u sustav dodaje mnogo korisnika. Prema [13] navedeni problem može se riješiti paralelizacijom algoritma, no to nije u opsegu ovog rada.

Metoda koja može smanjiti trošak osvježavanja sustava i zadržati kvalitetu preporuke je hibridna metoda folding-up koja je kombinacija metoda folding-in i update. Ideja metode je da u početku koristi metodu folding-in do unaprijed određenog udjela novih korisnika u sustavu. Nakon toga da se pokreće metoda update nad novim korisnicima kako bi se sustav vratio u ravnotežu i osvježio prostor proizvoda, taj proces se iterativno nastavlja kombiniranjem te dvije metode.

Osim teorijskih iskaza SVD algoritama za CF sustave, u ovome radu provedeni su eksperimenti za dane algoritme. Uz pomoć programskog paketa Matlab, implementirani je algoritam zasnovan na SVD dekompoziciji s redukcijom dimenzije te algoritmi za osvježavanje sustava folding-in i update metodom.

Prije same implementacije, potrebno je prikupiti i pripremiti podatke za testiranje. Testiranje algoritama provedeno je na manjem primjeru, odnosno na bazi od 11 korisnika i 11 proizvoda, a podatci za matricu korisnosti R, prikazanu Tablicom 2, prikupljeni su pomoću Google ankete15. Ispitani korisnici su trebali ponuđene filmove rangirati ocjenom iz skupa \lbrace 1,2,3,4,5\rbrace, a filmove koje nisu pogledali označiti sa 0.

Filmovi navedeni u matrici su redom: The Martian(2015), The Illusionist(2006), Now You See Me(2013), The Intouchables(2011), Ice Age(2002), Ted(2012), The Man Who Knew Infinity(2015), The Choice(2016), The Secret Life Of Pets(2016), Me Before You(2016) i Race(2016).

Algoritam zasnovan na SVD dekompoziciji s redukcijom dimenzije implementiran je u programskom paketu Matlab prema Algoritmu 1.

U ovom poglavlju promatraju se rezultati implementiranog algoritma i njegova točnost. Prvo su navedeni osnovni rezultati algoritma neophodni za predikciju, zatim su dani primjeri predikcije za zadanog korisnika u_{i} i film p_{j} i svojstva predikcije za slične proizvode i korisnike te je na kraju algoritam testiran za različite parametre k i l kako bi se odredili najbolji.

Kako je navedeno u algoritmu, prvi korak kod generiranja preporuke zasnovane na SVD dekompoziciji s redukcijom dimenzije jest popunjavanje i normalizacija matrice korisnosti. Prije svega normalizirali smo početnu matricu sustava R i dobivena matrica R_{norma} dana je sa:

Prema algoritmu sljedeći korak je SVD dekompozicija matrice R_{norm} i redukciju dimenzije na prethodno zadanu dimenziju obzirom na parametar k. Koristeći SVD dekompoziciju i Teorem 3 izračunali smo k-dimenzionalnu aproksimaciju matrice R_{norm} i rezultat je matrica R_{k}=U_{k}S_{k}V_{k}^{T}. Za k=4 i prethodno dobivenu matricu R_{norm}, matrica R_{k} je dana s:

i to je model testnog sustava.

Iz Primjera 4.c očito je da parametri k i l mogu bitno utjecati na rezultat algoritma pa je važno provesti analizu za oba parametra i pronaći one koji najbolje odgovaraju sustavu.

Analiza parametra k:
Testiranje za parametar k provedeno je za k=2,\ldots,8 i fiksan l=3, a rezultat je prikazan na Slici 6. Sukladno analizi, za najprikladniji k može se uzeti k=3, odnosno najbolja aproksimacije matrice R je matrica ranga k=3.

Slika 6: Za sustav dan Tablicom 2 provedena je analiza parametar k. Za fiksan l=3 testirani su k\in\lbrace 2,...,8\rbrace i dobiveno je da je za parametar k najbolje uzeti k=3 . 

Analiza parametra l: Testiranje za parametar l provedeno je za l=2,\ldots,8 i fiksan k=3, a rezultat je prikazan na Slici 7. Analizom je pokazano da je najprikladnije za parametar l uzeti l=4. Točnije, ovdje je za susjedstvo nekog filma najprikladnije promatrati njemu četiri najsličnija filma.

Slika 7: Za sustav dan Tablicom 2 provedena je analiza parametar l. Za fiksan k=3 testirani su l\in\lbrace 2,...,8\rbrace i dobiveno je da je za parametar l najbolje uzeti l=4 . 

Pri dodavanju svakog novog korisnika u sustav, dodaje se novi redak u matricu korisnosti, no ideja folding-in metode nije ponovno računanje SVD dekompozicije nego dodavanje korisnika u već reducirani sustav.

Odstupanje predikcije za novog korisnika rasti će dodavanjem sve većeg broja korisnika te bi se za sustav mogao promatrati i maksimalan broj korisnika koji se može dodati bez značajnog gubitka na kvaliteti. Kod većih sustava taj broj bi se mogao razmatrati, no u malim sustavima kao što je sustav iz primjera opadanje kvalitete je vidljivo već u samom startu. Osvježavanje sustava omogućuje dodavanje novog korisnika u sustav, a time rješava i cold start problem u CF sustavima.

Također, može se promotriti razlika u predikciji ukoliko se novi korisnik doda folding-in metodom ili se on dodaje u početni sustav ponovno računajući cijelu SVD dekompoziciju, što je prikazano u sljedećem primjeru.

U ovoj cjelini na testnom sustavu od 11 korisnika i 11 proizvoda ilustrirana je metoda update, implementirana kako je opisano u Algoritmima 3 i 4.

Kod folding-in metode će dodavanjem sve većeg broja korisnika opadati kvaliteta predikcija, no u ovom slučaju kvaliteta se neće mijenjati bez obzira na broj novih korisnika. Primjerice, ako se dodaju tri korisnika kao korisnik K5, preporuka za K12 i film F5 iznosi 4.1697.

Kao prethodno, može se promotriti razliku u predikciji ukoliko se novi korisnik doda metodom update ili se doda u početni sustav ponovno računajući cijelu SVD dekompoziciju, što je prikazano u sljedećem primjeru.

U zadnjem primjeru promotrimo kakva će biti početna preporuka, ako se u sustav doda korisnik koji nije pogledao niti jedan film.