Un avantaj al distanței Manhattan este că este rapid de calculat. Dacă suntem Facebook și încercăm să găsim cine dintre un milion de utilizatori este cel mai asemănător cu micuțul Danny din Kalamazoo, rapid este bine.
Teorema lui Pitagora
S-ar putea să vă amintiți teorema lui Pitagora din trecutul vostru educațional îndepărtat. Aici, în loc să găsim distanța Manhattan între Amy și doamna X (care era 4), vom calcula distanța liniei drepte,
Teorema lui Pitagora ne spune cum să calculăm această distanță.
Această linie dreaptă o numim distanță euclidiană. Formula este
√((x1 – x2)2 + (y1 – y2)2)
Amintiți-vă că x1 este cât de mult i-a plăcut persoanei 1 Dragon Tattoo și x2 este cât de mult i-a plăcut persoanei 2; y1 este cât de mult i-a plăcut persoanei 1 Snow Crash, iar y2 este cât de mult i-a plăcut persoanei 2.
Amy a evaluat atât Snow Crash, cât și Dragon Tattoo cu 5; Eluziva doamnă X a evaluat Dragon Tattoo cu 2 și Snow Crash cu 4. Deci distanța euclidiană dintre
√((5 – 2)2 + (5 – 4)2) = √(32 + 12) = √10 = 3,16
Calculând restul distanțelor obținem
| Distanța de la D-na X | |
| Amy | 3.16 |
| Bill | 3.61 |
| Jim | 3.61 |
Gândirea N-dimensională
Să ne depărtăm ușor de simpla examinare a evaluării a două cărți (și, prin urmare, 2D) pentru a arunca o privire la ceva mai complex. Să presupunem că lucrăm pentru un serviciu de muzică de streaming online și vrem să facem experiența mai convingătoare recomandând trupe. Să presupunem că utilizatorii pot evalua trupele pe un sistem de stele de la 1 la 5 și pot acorda evaluări și pe jumătate de stea (de exemplu, puteți acorda unei trupe 2,5 stele). Următorul grafic arată 8 utilizatori și evaluările lor de opt trupe.
| 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 | – | – |
Cratimele din tabel indică faptul că un utilizator nu a evaluat trupa respectivă. Deocamdată vom calcula distanța pe baza numărului de trupe pe care le-au evaluat amândoi. De exemplu, atunci când calculăm distanța dintre Angelica și Bill, vom folosi ratingurile pentru Blues Traveler, Broken Bells, Phoenix, Slightly Stoopid și Vampire Weekend. Deci distanța Manhattan ar fi:
| 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 |
| Distanța Manhattan: | 9 |
Rândul pentru distanța Manhattan, ultimul rând al tabelului, este pur și simplu suma diferențelor: (1,5 + 1,5 + 3 + 2 + 1).
Calculul distanței euclidiene este similar. Folosim doar trupele pe care le-au recenzat amândoi:
| Angelica | Bill | Diferența | Diferența2 | |
| Blues Traveler | 3.5 | 2 | 1.5 | 2.25 |
| Broken Bells | 2 | 3.5 | 1.5 | 2.25 |
| Deadmau5 | – | 4 | ||
| Norah Jones | 4.5 | – | ||
| Phoenix | 5 | 2 | 3 | 9 |
| Slightly Stoopid | 1.5 | 3.5 | 2 | 4 |
| The Strokes | 2.5 | – | – | |
| Vampire Weekend | 2 | 3 | 1 | 1 |
| Suma pătratelor | 18.5 | |||
| Distanța euclidiană | 4.3 |
Pentru a analiza ceva mai mult:
Euclidian = √((3,5 – 2)2 + (2 – 3,5)2 + (5 – 2)2 + (1,5 – 3,5)2 + (2 – 3)2) = √(1,52 + (-1,5)2 + 32 + (- 2)2 + (-1)2) = √(2,25 + 2,25 + 9 + 4 +1) = √18,5 = 4,3
Ai înțeles? Încearcă propriul tău exemplu.
| 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 | – | – |
Ascute-ți creionul. Calculează distanța euclidiană dintre Hailey și Veronica.
Calculează distanța euclidiană dintre Hailey și Jordyn
Soluție:
Calculul distanței euclidiene dintre Hailey și Veronica:
= √((4 – 5)2 + (4 – 3)2) = √(1 + 1) = √2 = 1,414
Calculul distanței euclidiene dintre Hailey și Jordyn:
= √((4 – 4,5)2 + (1 – 4)2 + (4 – 5)2 + (4 – 4)2 + (1 – 4)2) = √((—0,5)2 + (—3)2 + (-1)2 + (0)2 + (—3)2) = √(0,25 + 9 + 1 + 0 + 9) = √19,25 = 4,387
Un defect
Se pare că am descoperit un defect la utilizarea acestor măsurări de distanță. Când am calculat distanța dintre Hailey și Veronica, am observat că au evaluat doar două trupe în comun (Norah Jones și The Strokes), în timp ce când am calculat distanța dintre Hailey și Jordyn, am observat că au evaluat cinci trupe în comun. Acest lucru pare să distorsioneze măsurarea distanței noastre, deoarece distanța Hailey-Veronica este în 2 dimensiuni, în timp ce distanța Hailey-Jordyn este în 5 dimensiuni. Distanța Manhattan și distanța euclidiană funcționează cel mai bine atunci când nu lipsesc valorile. Abordarea valorilor lipsă este un domeniu activ de cercetare științifică. Mai târziu vom vorbi despre cum să rezolvăm această problemă. Deocamdată trebuie să fiți conștient de defect.
O generalizare
Putem generaliza distanța Manhattan și distanța euclidiană la ceea ce se numește metrica distanței Minkowski:
d(x,y) = Σk=1n ( | xk – yk |r)1/r
Când
- r = 1: Formula este distanța Manhattan.
- r = 2: Formula este distanța euclidiană
- r = ∞: Distanța supremă
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
Eseuri filosofice
Descoperă universul gândirii critice și al reflecției profunde!
Ghidul autorului de cărţi electronice
Descoperă cum să devii autor de succes în era digitală!
Ghid marketing pe Internet
Autor: Nicolae Sfetcu (Ediţia a doua, Revizia 2) Unul din cele mai vechi ghiduri pentru marketing pe Internet în limba română, dar şi unul din cele mai concise şi mai practice ghiduri. Deşi au trecut mulţi ani de la scrierea … Citeşte mai mult
Lasă un răspuns