Matematica
Atunci când vedeți astfel de formule într-o carte, aveți mai multe opțiuni. O opțiune este să treceți rapid peste ele. Cealaltă opțiune este să studiați cu atenție formula, și să o disecați.
De multe ori veți găsi formula destul de ușor de înțeles. Să o disecăm acum. Când r = l formula se reduce la distanța Manhattan:
d(x,y) = Σk=1n | xk – yk |
Deci, pentru exemplul muzical pe care l-am folosit anterior, x și y reprezintă două persoane și d(x,y) reprezintă distanța dintre ele. n este numărul de trupe pe care le-au evaluat ambele (atât x cât și y au evaluat trupa respectivă). Am făcut deja acest calcul:
Angelica | Bill | Diferența | |
Blues Traveler | 3.5 | 2 | 1.5 |
Broken Bells | 2 | 3.5 | 1.5 |
Deadmau5 | – | 4 | |
Norah Jones | 4.5 | – | |
Phoenix | 5 | 2 | 3 |
Slightly Stoopid | 1.5 | 3.5 | 2 |
The Strokes | 2.5 | – | – |
Vampire Weekend | 2 | 3 | 1 |
Manhattan Distance: | 9 |
Coloana diferenței reprezintă valoarea absolută a diferenței și le însumăm pentru a obține 9.
Când r = 2, obținem distanța euclidiană:
d(x,y) = √ Σk=1n (xk – yk)2
Cu cât r este mai mare, cu atât mai mult diferența mare într-o dimensiune va influența diferența totală.
Reprezentarea datelor în Python
Există mai multe moduri de a reprezenta datele din tabelul de mai sus folosind Python. Voi folosi dicționarul Python (numit și tablou asociativ sau tabel hash):
users = { | |
“Angelica”: | “Slightly Stoopid”: 1.5, “The Strokes”: 2.5, “Vampire Weekend”: 2.0}, |
“Bill”: | {“Blues Traveler”: 2.0, “Broken Bells”: 3.5, “Deadmau5”: 4.0, “Phoenix”: 2.0, “Slightly Stoopid”: 3.5, “Vampire Weekend”: 3.0}, |
“Chan”: | {“Blues Traveler”: 5.0, “Broken Bells”: 1.0, “Deadmau5”: 1.0, “Norah Jones”: 3.0, “Phoenix”: 5, “Slightly Stoopid”: 1.0}, |
“Dan”: | {“Blues Traveler”: 3.0, “Broken Bells”: 4.0, “Deadmau5”: 4.5, “Phoenix”: 3.0, “Slightly Stoopid”: 4.5, “The Strokes”: 4.0, “Vampire Weekend”: 2.0}, |
“Hailey”: | {“Broken Bells”: 4.0, “Deadmau5”: 1.0, “Norah Jones”: 4.0, “The Strokes”: 4.0, “Vampire Weekend”: 1.0}, |
“Jordyn”: | {“Broken Bells”: 4.5, “Deadmau5”: 4.0, “Norah Jones”: 5.0, “Phoenix”: 5.0, “Slightly Stoopid”: 4.5, “The Strokes”: 4.0, “Vampire Weekend”: 4.0}, |
“Sam”: | {“Blues Traveler”: 5.0, “Broken Bells”: 2.0, “Norah Jones”: 3.0, “Phoenix”: 5.0, “Slightly Stoopid”: 4.0, “The Strokes”: 5.0}, |
“Veronica”: | : {“Blues Traveler”: 3.0, “Norah Jones”: 5.0, “Phoenix”: 4.0, “Slightly Stoopid”: 2.5, “The Strokes”: 3.0} |
} |
Putem obține evaluările unui anumit utilizator după cum urmează:
>>> users[“Veronica”]
{“Blues Traveler”: 3.0, “Norah Jones”: 5.0, “Phoenix”: 4.0, “Slightly Stoopid”: 2.5, “The Strokes”: 3.0}
>>>
Codul pentru calcularea distanței Manhattan
Aș dori să scriu o funcție care calculează distanța Manhattan după cum urmează:
def manhattan(rating1, rating2):
“””Computes the Manhattan distance. Both rating1 and rating2 are
dictionaries of the form
{‘The Strokes’: 3.0, ‘Slightly Stoopid’: 2.5 …”””
distance = 0
for key in rating1:
if key in rating2:
distance += abs(rating1[key] – rating2[key])
return distance
Pentru a testa funcția:
>>> manhattan(users[‘Hailey’], users[‘Veronica’])
2.0
>>> manhattan(users[‘Hailey’], users[‘Jordyn’])
7.5
>>>
Acum o funcție pentru a găsi cea mai apropiată persoană (de fapt, aceasta returnează o listă sortată cu cea mai apropiată persoană):
def computeNearestNeighbor(username, users):
“””creates a sorted list of users based on their distance to
username”””
distances = []
for user in users:
if user != username:
distance = manhattan(users[user], users[username])
distances.append((distance, user))
# sort based on distance — closest first
distances.sort()
return distances
Și doar un test rapid al acestei funcții:
>>> computeNearestNeighbor(“Hailey”, users)
[(2.0, ”Veronica’), (4.0, ‘Chan’),(4.0, ‘Sam’), (4.5, ‘Dan’), (5.0, ‘Angelica’), (5.5, ‘Bill’), (7.5, ‘Jordyn’)]
În cele din urmă, vom pune totul împreună pentru a face recomandări. Să presupunem că vreau să fac recomandări pentru Hailey. Găsesc cea mai apropiată vecină a ei – Veronica în acest caz. Voi găsi apoi trupe pe care Veronica le-a apreciat, dar Hailey nu. De asemenea, voi presupune că Hailey ar fi evaluat trupele la fel ca (sau cel puțin foarte asemănător) cu Veronica. De exemplu, Hailey nu a apreciat marea trupă Phoenix. Veronica a evaluat Phoenix cu „4”, așa că vom presupune că Hailey se va bucura și ea de trupă. Iată funcția mea de a face recomandări.
def recommend(username, users):
“””Give list of recommendations”””
# first find nearest neighbor
nearest = computeNearestNeighbor(username, users)[0][1]
recommendations = []
# now find bands neighbor rated that user didn’t
neighborRatings = users[nearest]
userRatings = users[username]
for artist in neighborRatings:
if not artist in userRatings:
recommendations.append((artist, neighborRatings[artist]))
# using the fn sorted for variety – sort is more efficient
return sorted(recommendations,
key=lambda artistTuple: artistTuple[1],
reverse = True)
Și acum să facem recomandări pentru Hailey:
>>> recommend(‘Hailey’, users)
[(‘Phoenix’, 4.0), (‘Blues Traveler’, 3.0), (‘Slightly Stoopid’, 2.5)]
Asta se potrivește cu așteptările noastre. După cum am văzut mai sus, cel mai apropiat vecin al lui Hailey a fost Veronica, iar Veronica i-a dat lui Phoenix un „4”. Să încercăm încă câteva:
>>> recommend(‘Chan’, users)
[(‘The Strokes’, 4.0), (‘Vampire Weekend’, 1.0)]
>>> recommend(‘Sam’, users)
[(‘Deadmau5’, 1.0)]
Credem că lui Chan îi va plăcea The Strokes și, de asemenea, prezice că lui Sam nu-i va plăcea Deadmaus.
>>> recommend(‘Angelica’, users)
[]
Hmm. Pentru Angelica am primit înapoi un set gol, adică nu avem recomandări pentru ea. Să vedem ce a greșit:
>>> computeNearestNeighbor(‘Angelica’, users)
[(3.5, ‘Veronica’), (4.5, ‘Chan’), (5.0, ‘Hailey’), (8.0, ‘Sam’), (9.0, ‘Bill’), (9.0, ‘Dan’), (9.5, ‘Jordyn’)]
Cel mai apropiat vecin al Angelicăi este Veronica. Când ne uităm la evaluările lor:
Angelica | Bill | Chan | Dan | Hailey | Jordyn | Sam | Veronica | |
Blues Traveler | 3.5 | 2 | 5 | 3 | – | – | 5 | 3 |
Broken Bells | 2 | 3.5 | 1 | 4 | 4 | 4.5 | 2 | – |
Deadmau5 | – | 4 | 1 | 4.5 | 1 | 4 | – | – |
Norah Jones | 4.5 | – | 3 | – | 4 | 5 | 3 | 5 |
Phoenix | 5 | 2 | 5 | 3 | – | 5 | 5 | 4 |
Slightly Stoopid | 1.5 | 3.5 | 1 | 4.5 | – | 4.5 | 4 | 2.5 |
The Strokes | 2.5 | – | – | 4 | 4 | 4 | 5 | 3 |
Vampire Weekend | 2 | 3 | – | 2 | 1 | 4 | – | – |
Vedem că Angelica a evaluat fiecare trupă pe care a făcut-o Veronica. Nu avem noi evaluări, deci nu avem recomandări.
Pe scurt, vom vedea cum să îmbunătățim sistemul pentru a evita aceste cazuri.
Exerciții
1) Implementați funcția Minkowski Distance.
2) Modificați funcția computeNearestNeighbor pentru a utiliza distanța Minkowski.
Soluție
1) Implementați funcția distanța Minkowski.
def minkowski(rating1, rating2, r):
“””Computes the Minkowski distance.
Both rating1 and rating2 are dictionaries of the form
{‘The Strokes’: 3.0, ‘Slightly Stoopid’: 2.5}”””
distance = 0
commonRatings = False
for key in rating1:
if key in rating2:
distance +=
pow(abs(rating1[key] – rating2[key]), r)
commonRatings = True
if commonRatings:
return pow(distance, 1/r)
else:
return 0 #Indicates no ratings in common
2) Modificați funcția computeNearestNeighbor pentru a utiliza distanța Minkowski.
Trebuie doar să modificați linia distanța = la
distance = minkowski(users[user], users[username], 2)
(argumentul 2 ca r implementează distanța euclidiană)
Sursa: Ron Zacharski, A Programmer’s Guide to Data Mining – The Ancient Art of the Numerati. Licența CC BY-NC 3.0. Traducere și adaptare: Nicolae Sfetcu
Articol oferit sub licență CC BY-NC 3.0
Lasă un răspuns