online od 1999 roku!

O mierzeniu odległości

30.09.2010. 13:51
opublikowane przez: Przemys�aw Szydzik

Jak daleko jest z punktu A do punktu B?
Zanim spróbujemy odpowiedzieć na pytanie, ustalmy, że ograniczamy się w naszych rozważaniach do sytuacji dwuwymiarowej. Uogólnienia na wyższe wymiary są przynajmniej w większości omawianych przykładów sprawą całkowicie naturalną.
Zatem jak wygląda odpowiedź na tak postawione pytanie?
Zapewne permanentny pesymista powiedziałby, że zbyt daleko. Co jednak ma odpowiedzieć człowiek chcący jak najdokładniej opisać stan faktyczny?

Pierwsza myśl zapewne podąża w kierunku poznanego w szkole pojęcia odległości między punktami. Zlokalizujmy więc oba punkty przyjmując jakiś układ odniesienia. Wówczas każdy punkt ma swoje współrzędne w przyjętym układzie.

Niech oraz .

Wówczas odległość między punktami jest prostą konsekwencją twierdzenia Pitagorasa (rysunek obok).
Stąd odległość między punktami:


Obrany przez nas sposób mierzenia odległości nazywa się w matematyce metryką, a podany wyżej przepis na mierzenie odległości nazywa się metryką euklidesową.

Definicja Metryką na płaszczyźnie nazywamy dowolną funkcję spełniającą warunki:

dla dowolnych

dla dowolnych

dla dowolnych

Odtąd będziemy stosować oznaczenie na odległość między punktami i w metryce .

Czego od funkcji będącej metryką wymagają warunki definicji?
Pierwszy mówi, że odległość punktu od niego samego wynosi 0. Drugi warunek, to zapisanie naturalnego spostrzeżenia, że odległość między dwoma punktami nie zależy od tego, który punkt obierzemy za pierwszy w procesie mierzenia. Trzeci to znany ze szkoły warunek istnienia trójkąta dla punktów niewspółliniowych. Dla punktów leżących na jednej prostej zachodzi równość.

---

Rozważmy następującą funkcję określoną wzorem:


Pokażemy, że jest ona metryką na . W tym celu należy sprawdzić trzy warunki definicji:

(i) wynika wprost z definicji funkcji ,
(ii) wynika wprost z definicji funkcji ,
(iii) Rozbijmy go dla jasności na trzy przypadki:

I. Wówczas:

II. Wówczas:



III. Wówczas:

Wiemy już, że funkcja jest metryką. Metryka ta odpowiada na pytanie, czy dwa dowolne punkty są różne, czy nie. Nie jest to naturalna metoda mierzenia odległości, bo pozwala ona wyłącznie zidentyfikować różne punkty. Stosowanie jej daje jednak ciekawe konsekwencje, o których będzie później.

Jakie są inne metryki na płaszczyźnie? Jest ich dużo, nieskończenie wiele. Dowodzi się, że każda funkcja zdefiniowana wzorem:

jest metryką dla na oraz

Zauważmy, że dla mamy znaną nam metrykę euklidesową. Będziemy ją czasem oznaczać . Nie są to jednak wszystkie możliwości.
Zanim poznamy kolejne ciekawe metryki, przyjrzyjmy się metryce , która nazywana jest czasem metryką taksówkową czy samochodową. Oznaczać będziemy ją Potoczną nazwę tej metryki tłumaczy rysunek poniżej:

Metryka taksówkowa
Odległość pomiędzy dwoma punktami liczona jest w dobrym przybliżeniu tak, jak liczy ją kierowca taksówki.
Inną metryką, która ma bardzo realistyczną interpretację, jest tak zwana metryka "rzeka". Wzięła się ona z obserwacji podróży pomiędzy afrykańskimi wioskami.
Formalnie określamy funkcję daną wzorem:



Wioski położone są w pobliżu rzeki, do której prowadzi jedyna droga wychodząca z miasta. Aby przemieścić się z wioski do wioski , należy dojść do rzeki, przepłynąć przez nią łodzią na wysokość wioski i dojść prowadzącą od brzegu do wioski . Obrazuje to poniższy schemat przedstawiający sytuację, gdy :


Metryka rzeka

---

Po wprowadzeniu charakterystycznych metryk, zajmijmy się konsekwencjami jakie niesie za sobą wybór metryki. Takim swoistym odczynnikiem będzie kula. Przypomnijmy, że kulą domkniętą o środku w punkcie i promieniu nazywamy zbiór:


Jak widać definicja kuli zależy od sposobu mierzenia odległości między punktami czyli od metryki. Zatem wybór metryki może mieć (i ma!) wpływ na kształt kuli.

Pierwszą zaskakującą własnością jest to, że zbiór może zależeć od promienia .
Weźmy pod uwagę metrykę . Wówczas kula:

jest złożona z jednego elementu, albo jest całą płaszczyzną!

Innym zaskakującym faktem jest wygląd kuli. W niektórych metrykach kula zupełnie nie przypomina kształtem kuli w z naszych wyobrażeń.
Nie jest wielkim zaskoczeniem, że w metryce euklidesowej kulą jest koło o środku w punkcie i promieniu . Weźmy pod lupę metrykę taksówkową .

Aby znaleźć kształt kuli w tej metryce rozwiążemy problem:

Wprowadzając oznaczenia: oraz i rozważając wszystkie cztery możliwości otrzymujemy warunki:


które opisują kształt kuli w metryce :

Kula K(0,1) w metryce taksówkowej
Jak widać kula w tej metryce jest ... kwadratowa (nie mylić z kwadraturą koła!). Jest to dość zaskakująca obserwacja. Z taką "kwadratową" kulką mamy do czynienia również w metryce .
Naszkicujmy kulę w tej metryce:

Rozważmy dwa przypadki:

I.
Wówczas i stosując podstawienie otrzymujemy

II.
Wówczas i stosując podstawienie otrzymujemy

Kula K(0,1) w metryce max
Powyższe przykłady dają szersze spojrzenie na pojęcie metryki. Wiele wymienionych metryk ma swoje realne zastosowanie, jednak ich dalsza analiza przysparza ciekawych i efektownych konsekwencji.

Na zakończenie szybkie spojrzenie na 1 wymiar. Na zbiorze naturalną metryką jest wartość bezwzględna.
Jak wygląda kula w metryce na zbiorze ?

Kula K(0,1) na prostej
Jest to po prostu odcinek . Łatwo się o tym przekonać mając pod ręką stół i monetę. Kładziemy monetę na stole i patrzymy na nią z góry traktując blat stołu jako płaszczyznę. Jeśli jednak zniżymy wzrok dokładnie na wysokość stolika tak, aby krawędź stolika wydawała się odcinkiem (częścią prostej), to z okrągłej monety zostaje jedynie odcinek długości średnicy monety.


Literatura:
1. J. Górnicki Okruchy matematyki, PWN 2009
2. http://wazniak.mimuw.edu.pl/index.php?title=Analiza_matematyczna_2/Wyk%C5%82ad_1:_Przestrzenie_metryczne

Czy wiesz że...? (wersja beta)
Metryka probabilistyczna – funkcja definiująca odległość pomiędzy zmiennymi bądź wektorami losowymi. Funkcja ta nie jest, jak sugeruje nazwa, metryką, gdyż nie spełnia jej pierwszego aksjomatu, jakim jest identyczność przedmiotów nierozróżnialnych. Należy jednak zauważyć, że funkcja ta jest metryką w przestrzeni probabilistycznej, co więcej, jest to metryka wyznaczona przez normę tej przestrzeni. METEOR (Metric for Evaluation of Translation with Explicit ORdering) jest metryką używaną do ewaluacji tłumaczenia maszynowego. Metryka ta bazuje na średniej harmonicznej n-gramów precyzji i pokrycia, przy czym pokrycie ma większą wagę niż precyzja. METEOR zawiera także inne cechy, których nie znajdziemy w innych metrykach. Są to na przykład: dopasowanie synonimów (metryka dopasowuje nie tylko słowa będące dosłownym tłumaczeniem, ale również wyrazy bliskoznaczne). Przykładowo, jeśli słowo „dobry” występuje w tłumaczeniu referencyjnym a słowo „niezły” występuje w ocenianym tłumaczeniu, system ewaluujący policzy to jako dobre dopasowanie. Metryka zawiera również narzędzie, które odwołuje się do formy bazowej danego słowa i dopasowuje formy podstawowe. Metryka METEOR została zaprojektowana aby naprawić błędy pojawiające się w bardziej znanej i częściej używanej metryce BLEU oraz aby stworzyć korelację z ewaluacją dokonywaną przez człowieka na poziomie zdań i segmentów. Różnica pomiędzy metryką METEOR a BLEU polega na tym, że BLEU szuka korelacji na poziomie korpusu. Długość fizyczna — miara fizyczna odległości pomiędzy dwoma punktami, liczona zgodnie z metryką euklidesową (zwykłym sposobem mierzenia odległości), albo w linii prostej (np. długość fali — odległość między jej dwoma węzłami) albo po krzywej (np. długość drogi przebytej przez ciało).

Metryka książki – informacje dotyczące wydawniczych i technicznych aspektów wydania książki, leżące na czwartej stronie (czyli na kolumnie redakcyjnej) tzw. czwórki tytułowej czyli pierwszych czterech stron książki. Strona ta składa się z dwóch części: na górze jest metryka wydawnicza, a na dole metryka drukarska. W wydawnictwach bibliofilskich, oraz o najwyższym poziomie edytorskim, spotykana jest również metryka typograficzna. Spójność oprogramowania – metryka kodu wskazująca, na ile jest on łatwy do utrzymywania (rozwoju), testowania, powtórnego użycia, a nawet do zrozumienia. Jako przeciwstawna jest zestawiana ze zależnością oprogramowania. Obie te metryki zaproponował Larry Constantine na podstawie dobrych praktyk programowania.

Daktyl (stgr. δάκτυλος dáktylos, dosł. "palec") – w metryce iloczasowej stopa metryczna składająca się z trzech sylab: jednej długiej i dwóch krótkich. Bierze swą nazwę stąd, że grecki wyraz dáktylos ma właśnie taki układ sylab. Versus pythius (łac. = wiersz pytyjski) – w metryce antycznej wiersz dystychiczny złożony z daktylicznego heksametru i jambicznego dymetru lub trymetru. Metryka pytyjska była charakterystyczna dla formy przepowiedni Pytii delfickiej, występuje także w niektórych epodach Horacego.

Iloczas – zjawisko prozodyjne, charakteryzujące się różnicowaniem długości trwania sylab lub głosek. W niektórych językach iloczas różnicuje znaczenie wyrazów. W metryce antycznej iloczas był podstawą organizacji metrum wierszowego. Amfibrach (gr. amphíbrachys, dosł. z obu stron krótki) w metryce iloczasowej to stopa metryczna składająca się z trzech sylab: jednej długiej między dwiema krótkimi.

Zależność oprogramowania – metryka kodu wskazująca stopień powiązania danego modułu z innymi. Jako przeciwstawna jest zestawiana ze spójnością oprogramowania. Niska zależność zwykle oznacza wysoką spójność i vice versa. Obie te metryki zaproponował Larry Constantine na podstawie dobrych praktyk programowania.

Definicja intuicyjna:
Kula to zbiór punktów oddalonych nie bardziej niż pewna zadana odległość (promień kuli) od wybranego punktu (środek kuli)

Anapest (gr. anápaiston) w metryce iloczasowej to stopa metryczna składająca się z trzech sylab: dwóch krótkich i jednej długiej. Punkt funkcyjny – metryka złożoności oprogramowania podawana jako liczba bezwymiarowa określająca efektywną względną miarę wartości funkcji oferowanej przez program użytkownikowi. Najczęściej jest podstawą do oszacowania m.in. pracochłonności wytworzenia danego oprogramowania. Pojęcie to zaproponował w 1979 r. A. J. Albrecht z firmy IBM.

Jonik (od łac. pes Ionicus, stopa jońska) – w greckiej i łacińskiej metryce iloczasowej sześciomorowa stopa metryczna składająca się z czterech sylab: dwóch długich i dwóch krótkich. W zależności od kolejności sylab wyróżniamy dwa typy joników:

Dodano: 30.09.2010. 13:51