Sari la conținut

Distanță Manhattan

De la Wikipedia, enciclopedia liberă
Distanță Manhattan față de distanță euclidiană: Distanțele Manhattan ale căilor roșie, galbenă și albastră au aceeași lungime, 12. În geometria euclidiană, dreapta verde are lungimea și este calea cea mai scurtă.

Distanța Manhattan este o distanță specifică într-o geometrie în care funcția obișnuită de distanță (metrică) din geometria euclidiană este înlocuită cu o nouă metrică în care distanța dintre două puncte este suma diferențelor absolute ale coordonatelor carteziene.[1] Metrica Manhattan este cunoscută și ca distanță L1, distanță L1 sau normă . Denumirea distanței provine de la trama stradală din Manhattan, unde traseele taximetrelor pot avea aceeași lungime pentru diferite căi.

Geometria a fost utilizată în analiza de regresie încă din secolul al XVIII-lea, iar astăzi este adesea denumită LASSO. Interpretarea geometrică datează din geometria neeuclidiană a secolului al XIX-lea și se datorează lui Hermann Minkowski.

Definiția formală

[modificare | modificare sursă]

Distanța Manhattan, , dintre doi vectori într-un spațiu vectorial real n-dimensional cu un sistem de coordonate carteziene, este suma lungimilor proiecțiilor segmentelor dintre puncte pe axele de coordonate. Formal,

unde sunt vectori euclidieni

De exemplu, în plan, distanța Manhattan dintre and este

Proprietăți

[modificare | modificare sursă]

Distanța Manhattan depinde de rotația sistemului de coordonate, dar nu depinde de reflexia față de o axă de coordonate sau de translația acesteia. Geometria Manhattan satisface toate axiomele Hilbert (o formalizare a geometriei euclidiene), cu excepția axiomei LUL (laturăunghi–latură), ca două triunghiuri cu laturi de lungime egală și unghiul dintre ele identic nu sunt de obicei congruente decât dacă elementele menționate se întâmplă să fie paralele.

Cercuri în geometria Manhattan discretă și continuă

Un cerc este o mulțime de puncte situate la o distanță fixă, numită rază, de un punct numit centru. În geometria Manhattan distanța este determinată de o metrică diferită de cea din geometria euclidiană, iar cercurile au altă formă. Cercurile Manhattan sunt pătrate cu laturile orientate la un unghi de 45° față de axele de coordonate. Imaginea alăturată arată de ce acest lucru este adevărat, arătând în roșu mulțimea tuturor punctelor de la aceeași distanță față de un centru, marcat cu albastru. Pe măsură ce dimensiunea cvartalelor din oraș se diminuează, punctele devin mai numeroase și devin un pătrat rotit într-o geometrie Manhattan continuă. În timp ce fiecare latură a acestui pătrat ar avea în metrica euclidiană lungimea unde r este raza cercului, lungimea sa în geometria Manhattan este 2r. Astfel, lungimea circumferinței cercului este 8r. Astfel, în această geometrie valoarea analogului geometric al este 4. Formula cercului unitate în geometria Manhattan este în coordonate carteziene iar în coordonate polare

Un cerc de rază 1 (folosind această distanță) este vecinătatea von Neumann a centrului său.

Un cerc de rază r pentru distanța Cebîșev (metrica L) din plan este tot un pătrat, cu raza 2r, paralel cu axele de coordonate, astfel distanța Cebîșev din plan poate fi considerată echivalentă cu distanța Manhattan rotită și scalată. totuși, această echivalență între metricile L1 și L nu se generalizează pentru dimensiuni superioare.

Ori de câte ori fiecare pereche dintr-o colecție de astfel de cercuri are o intersecție neocupată, există un punct de intersecție pentru întreaga colecție; prin urmare, distanța Manhattan formează un spațiu metric injectiv.

Distanțele la șah

[modificare | modificare sursă]

În șah, distanța dintre pătratele de pe tabla de șah pentru turnuri este distanța Manhattan. Pentru regi și dame este distanța Cebîșev. Pentru nebuni este distanța Manhattan (între pătrate de aceeași culoare) pe tabla de șah rotită cu 45°, adică cu diagonalele sale ca axe de coordonate. Pentru a ajunge de la un pătrat la altul, numai regii necesită numărul de mișcări egale cu distanța lor respectivă; turnurile, damele și nebunii necesită una sau două mutări (pe o tablă goală și presupunând că mutarea este posibilă în cazul nebunului).

Achiziția comprimată

[modificare | modificare sursă]

În rezolvarea unui sistem nedeterminat de ecuații liniare, regularizarea vectorului parametru este exprimată în termeni de geometrie Manhattan, ca -normă.[2] Această abordare apare în cadrul recuperării semnalului numită achiziție comprimată.

Diferențele distribuțiilor de frecvență

[modificare | modificare sursă]

Geometria Manhattan poate fi utilizată pentru a evalua diferențele în distribuțiile discrete de frecvență. De exemplu, în matisarea ARN distribuțiile poziționale ale hexamerilor, care prezintă probabilitatea ca fiecare hexamer să apară la fiecare nucleotidă dată lângă un loc de îmbinare, poate fi comparat cu distanța L1. Fiecare distribuție de poziție poate fi reprezentată ca un vector în care fiecare intrare reprezintă probabilitatea ca hexamerul să înceapă de la un anumit nucleotid. O distanță mare L1 între cei doi vectori indică o diferență semnificativă în natura distribuțiilor, în timp ce o distanță mică denotă distribuții în formă similară. Acest lucru este echivalent cu măsurarea ariei dintre cele două curbe de distribuție, deoarece aria fiecărui segment este diferența absolută dintre probabilitățile celor două curbe în acel moment. Când sunt însumate pentru toate segmentele, oferă aceeași măsură ca distanța L1.[3]

Metrica L1 a fost folosită în analiza de regresie în 1757 de Roger Joseph Boscovich.[4] Interpretarea geometrică datează de la sfârșitul secolului al XIX-lea și dezvoltarea geometriilor neeuclidiene, în special de Hermann Minkowski. În geometria Manhattan inegalitatea lui Minkowski este un caz particular, utilizat în special în geometria numerelor, (Minkowski 1910). Formalizarea spațiilor Lp se datorează lui (Riesz 1910).

  1. ^ en Black, Paul E. „Manhattan distance”. Dictionary of Algorithms and Data Structures. Accesat în . 
  2. ^ en Donoho, David L. (). „For most large underdetermined systems of linear equations the minimal -norm solution is also the sparsest solution”. Communications on Pure and Applied Mathematics. 59 (6): 797–829. doi:10.1002/cpa.20132. 
  3. ^ en Lim, Kian Huat; Ferraris, Luciana; Filloux, Madeleine E.; Raphael, Benjamin J.; Fairbrother, William G. (). „Using positional distribution to identify splicing elements and predict pre-mRNA processing defects in human genes”. Proceedings of the National Academy of Sciences of the United States of America. 108 (27): 11093–11098. Bibcode:2011PNAS..10811093H. doi:10.1073/pnas.1101135108. PMC 3131313Accesibil gratuit. PMID 21685335. 
  4. ^ en Stigler, Stephen M. (). The History of Statistics: The Measurement of Uncertainty before 1900Necesită înregistrare gratuită. Harvard University Press. ISBN 9780674403406. Accesat în . 

Legături externe

[modificare | modificare sursă]