  ̌      ̌   
P 47 (2019/2020) 622
Priporočanje z algoritmom Slope One
M B̌
Priporočilni sistemi se v zadnjem desetletju vse
bolj uporabljajo v različne namene. Najpogosteje jih
najdemo v spletnih trgovinah, socialnih omrežjih, is-
kalnikih in tudi v storitvah za pretočnost video in
avdio vsebin. V tem prispevku opisujemo pristop
sodelovalnega priporočanja Slope One, ki deluje na
podlagi povratnih informacij, pridobljenih s strani
drugih uporabnikov.
Denimo, da se odpravljate na morje in želite na
plaži prebrati dobro knjigo. Da bi izbrali knjigo, ki
bi jo res z veseljem brali, omejite izbiro na žanre, av-
torje ali pa tudi dolžino knjige. Velika možnost je, da
bo po začetni omejitvi izbire na voljo še vedno pre-
več knjig in potrebujete še nekaj več informacij, da
bi izbrali tisto pravo knjigo, ki vam bo ustrezala na
plaži. Velikokrat se v takšnih primerih obrnemo na
prijatelje oziroma pregledamo mnenja in recenzije
knjig na spletu. Ker se mnenja velikokrat razliku-
jejo, saj smo ljudje različni, želimo ugotoviti, kateri
ljudje imajo podoben okus kot mi.
V opisani situaciji hitro vidimo, da izvajamo neke
vrste filtriranje med veliko množico knjig. V svetu
priporočilnih sistemov (recommender systems) poz-
namo dva osnovna pristopa k pridobivanju ustre-
znega rezultata. Prvi pristop je vsebinsko filtriranje
(content-based filtering). Pri tem pristopu nastopa
računalniški sistem, ki mu podamo potrebne infor-
macije (npr. tematiko knjige), vrne pa nam seznam
priporočil, ki jih računalniški sistem izračuna s po-
močjo metrike vsebinske podobnosti. Drugi pristop
je sodelovalno filtriranje (collaborative filtering), kjer
pa računalniškemu sistemu podamo le naše prete-
kle stike (npr. oceno knjige na lestvici med 1 in 5),
dobimo pa seznam priporočil, ki jih računalniški sis-
tem izračuna s pomočjo metrike podobnosti. Pri tem
računalniški sistem upošteva tudi ostale bralce is-
tih knjig. V nadaljevanju prispevka bomo predstavili
algoritem sodelovalnega filtriranja Slope One, ki bo
znal glede na pretekle ocene knjig priporočati naju-
streznejšo knjigo, ki je še nismo prebrali.
Algoritem Slope One
Področje sodelovalnega filtriranja pozna veliko algo-
ritmov, ki se samostojno ali kot skupek večih algorit-
mov uporabljajo še danes v zelo razširjenih spletnih
storitvah, kot sta YouTube in Amazon. Algoritem
Slope One se prvič pojavi leta 2005 kot nov, preprost
in hiter način za priporočanje s sodelujočim filtrira-
njem. Prednosti algoritma sta natančnost priporočil
in možnost enostavne paralelizacije.
Algoritem Slope One deluje tako, da na podlagi
kombinacije uporabnikov in njihovih že obstoječih
ocen poskuša predvidevati, kako bi drugi uporab-
niki ocenili tiste elemente, ki si jih še niso ogledali.
V našem primeru so elementi priporočanja knjige,
ki so jih bralci že ocenili, z algoritmom Slope One
pa želimo predvideti našo oceno za vse knjige, ki
jih še nismo ocenili. Ideja algoritma Slope One je
ustvarjanje linearne relacije med elementi priporo-
čanja in uporabniki, ki je podobna linearni funkciji
f(x) = ax + b. Gre za linearno funkcijo, kjer je
smerni koeficient oz. naklon a enak 1; od tod izvira
tudi ime algoritma Slope One. Prvi korak algoritma
je torej ustrezna predstavitev uporabniških ocen in
knjig. Le-to zelo elegantno predstavimo z matriko,
kjer vrstice predstavljajo uporabnike, stolpci pred-
stavljajo knjige, številčne vrednosti pa oceno med 1
in 5, s katero je uporabnik ocenil knjigo. Oznaka −
pomeni, da oseba še ni ocenila knjige.
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
Tina − 3 4
Mateja 3 4 −
Marko 5 2 3
KA KB KC
Iz takšne predstavitve lahko tvorimo vektorje, ki
jih uporabimo v naslednjih korakih algoritma. Re-
cimo, da želimo izračunati, kako bi Tina ocenila knji-
go KA. Najprej izračunamo povprečni razdalji med
KA in KB ter med KA in KC . To storimo z operacijo
odštevanja vektorjev, kjer v primeru, da za knjigo
  ̌      ̌   
P 47 (2019/2020) 6 23
nimamo podane ocene (oznaka −), razlike med oce-
nami ne bo mogoče izračunati. V tem primeru izlo-
čimo pripadajočo vrstico v vektorjih (enačba 1):
di,j = Ki −Kj . (1)
Rezultat odštevanja dveh vektorjev, kjer ni podane
ocene (oznaka −), je nov vektor, kjer izločitev vrstice
(in s tem tudi knjige) ponazorimo z oznako −, pri
nadaljnjih izračunih pa uporabimo ustrezno preobli-
kovan vektor (v tem primeru je to vektor [4 0]T ):


7
4
−

−


3
4
1

 =


4
0
−


Hkrati si beležimo število ocenjenih skupnih knjig
Ni,j , saj želimo izračunati povprečno razliko med
ocenami za obravnavane knjige. Ni,j ustreza šte-
vilu nemanjkajočih komponent vektorja. Če delamo
v prostoru z dimenzijo D, potem povprečno razliko
med ocenami izračunamo po enačbi 2. Pri tem velja,
da ocena obstaja (dki,j ≠ −):
d̄i,j =
1
Ni,j
D∑
k=0
dki,j (2)
V tem koraku izračunamo povprečne razlike v oce-
nah:
dA,B =


5
3
−

−


2
4
3

 =


3
−1
−

 ;NA,B = 2
dA,C =


5
3
−

−


3
−
4

 =


2
−
−

 ;NA,C = 1
d̄A,B =
(3+ (−1))
2
= 2
2
= 1
d̄A,C =
2
1
= 2
Zadnji korak je izračun vrednosti sprememb ocen
r , kjer upoštevamo povprečno razliko v ocenah d̄i,j
in oceno uporabnika y (enačba 3). Vrednosti spre-
memb ocen za uporabnika in knjige r(y)i,j upora-
bimo v izračunu predvidene ocene, ki pove, kako bi
uporabnik y ocenil knjigo x. To izračunamo z enač-
bo 4, ki predpostavlja linearno relacijo med uporab-
nikom y in njegovo oceno knjige x na podlagi ocen
preostalih uporabnikov, ki so preostale knjige ocenili
podobno kot uporabnik x:
r(y)i,j = ocena(y)j + d̄i,j (3)
SlopeOne(x,y) =
∑n
i=1Nx,i · r(y)x,i∑n
i=1Nx,i
(4)
Za Tino in knjigo A je izračun v zadnjem koraku sle-
deč:
r(Tina)A,B = ocena(Tina)B + d̄A,B = 3+ 1 = 4
r(Tina)A,C = ocena(Tina)C + d̄A,C = 4+ 2 = 6
SlopeOne(A,Tina) =
= NA,B · r(Tina)A,B +NA,C · r(Tina)A,C
NA,B +NA,C
= 2 · 4+ 1 · 6
2+ 1 =
14
3
= 4,667
Z algoritmom Slope One predvidevamo, da bi Tina
ocenila knjigo A z oceno 4,667, kar je zelo blizu Mar-
kovi oceni za knjigo A. Če primerjamo njune ocene
ostalih knjig, opazimo, da so tudi te zelo podobne.
Iz tega lahko sklepamo, da imata Tina in Marko zelo
podoben okus. Vidimo tudi, kako je na Tinino pred-
videno oceno knjige A vplivala nižja ocena Mateje.
Prikazan postopek v praksi izvedemo za vsako
neocenjeno knjigo. Tako dobimo
predvidene ocene neocenjenih knjig, ki jih lahko ure-
dimo po velikosti padajoče. S tem tvorimo seznam
priporočil, ki ga lahko omejimo s številom zadetkov
na izhodu θ. Seznam priporočil ponavadi omejimo
na 3 do 5 zadetkov.
Zgled
Priporočanje z algoritmom Slope One prikažimo še
na praktičnem zgledu, kjer imamo pet oseb (Luka,
Jakob, Nika, Sara in Anja) in osem knjig (označimo
jih s K1 − K8). Tvorimo tabelo ocen, kjer oznaka −
pomeni, da oseba še ni ocenila knjige, številčna vre-
dnost pa predstavlja oceno med 1 (zelo slabo) in 5
(odlično).
Ustvarili bomo priporočila za Jakoba, ki je rela-
tivno kritičen in nov bralec, kot je razvidno iz tabele
ocen. Izračunali bomo predvidene ocene za K1, K3,
K5, K6, K7 in K8. Oglejmo si postopek izračuna pred-
videnih ocen.
  ̌      ̌   
P 47 (2019/2020) 624
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
Anja − − 4 4 − − − 4
Sara 2 2 − − 5 − − −
Nika 5 4 5 − 2 − 4 −
Jakob − 1 − 3 − − − −
Luka 3 − − 2 − 4 5 5
K1 K2 K3 K4 K5 K6 K7 K8
Najprej z enačbo 1 izračunajmo razliko med oce-
nami knjig, ki jih je Jakob že ocenil (K2 = 1, K4 = 3),
in ocenami knjig, ki jih želimo priporočati. V pri-
meru, da za knjigo nimamo podane ocene (oznaka
−), razlike med ocenami ne bo možno izračunati:
d1,2 = K1 −K2 =


3
−
5
2
−


−


−
1
4
2
−


=


−
−
1
0
−


;N1,2 = 2
d1,4 = K1 −K4 =


3
−
5
2
−


−


2
3
−
−
4


=


1
−
−
−
−


;N1,4 = 1
Hkrati si beležimo tudi število ocenjenih skupnih
knjig Ni,j , ki ga bomo potrebovali za izračun pov-
prečne razlike med ocenami za obravnavane knjige
(enačba 2):
d̄1,2 =
1
N1,2
·
∑
dk∈d1,2
dk = 0.5
d̄1,4 =
1
N1,4
·
∑
dk∈d1,4
dk = 1
Sledi izračun predvidene ocene za knjigo K1 z enač-
bama 3 in 4:
r(Jakob)1,2 = ocena(Jakob)2 + d̄1,2 = 1,5
r(Jakob)1,4 = ocena(Jakob)4 + d̄1,4 = 4
SlopeOne(1, Jakob) =
∑n
i=1N1,i · r(Jakob)1,i∑n
i=1N1,i
= N1,2 · r(Jakob)1,2 +N1,4 · r(Jakob)1,4
N1,2 +N1,4
= 2,333
Z izračunom vrednosti Slope One predvidevamo, da
bi Jakob knjigo K1 ocenil z oceno 2,333. Na enak
način pridobimo še vrednosti za preostale knjige:
RJakob=
〈
K1 K2 K3 K4 K5 K6 K7 K8
2,333 1 2 3 1,5 5 4 4,5
〉
.
Knjige s pripadajočimi predvidenimi ocenami zapi-
šemo v seznam, ki ga uredimo po velikosti ocene
padajoče. Seznam lahko omejimo na pet zadetkov
(npr. θ = 5), ki ga nato posredujemo Jakobu.
RθJakob =
〈
K6 K8 K7 K1 K3
5 4,5 4 2,333 2
〉
.
V tem prispevku opisan algoritem sodelovalnega pri-
poročanja lahko uporabimo tudi za priporočanje fil-
mov, pesmi, ljudi, izdelkov v trgovinah in drugih iz-
delkov, ki jih uporabniki lahko ocenijo. Iz tega sledi
tudi glavna pomanjkljivost vsakega algoritma sode-
lovalnega priporočanja. To je t. i. problem hladnega
začetka (cold-start problem), saj bomo na začetku ve-
dno potrebovali množico ocen, da bomo sploh lahko
izvedli priporočanje. Vsebinsko filtriranje rešuje ta
problem, vendar gre za kompleksnejše metode raču-
nanja podobnosti, hkrati pa se lahko po določenem
času priporočila začnejo ponavljati. Iz tega razloga
se sodobni priporočilni sistemi poslužujejo tako vse-
binskega kot sodelovalnega filtriranja. To so hibridni
priporočilni sistemi (hybrid recommender systems),
ki vedno bolj uporabljajo pristope globokega učenja
in se tudi že uporabljajo v praksi.
Literatura
[1] D. Lemire in A. Maclachlan, Slope One Predic-
tors for Online Rating-Based Collaborative Filte-
ring, Proceedings of the 2005 SIAM Internatio-
nal Conference on Data Mining, 471–475, 2005.
[2] P. Melville in V. Sindhwani, Recommender Sy-
stems, Encyclopedia of Machine Learning, Sprin-
ger, 829–838, 2010.
[3] F. Ricci, L. Rokach in B. Shapira, Introduction to
Recommender Systems Handbook, Recommen-
der Systems Handbook, Springer, 1–35, 2011.
[4] R. Burke, Hybrid Recommender Systems: Sur-
vey and Experiments, User Modeling and User-
Adapted Interaction, 12(4), 331–370, 2002.
×××