Data Mining: Reprezentarea datelor în Python

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=1ⁿ | x_k – y_k |

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=1ⁿ (x_k – y_k)²

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