Različne definicije razdalje

Tole besedilo bo malo bolj matematično. Kogar to moti, naj ravna po nasvetu prof. Franceta Križaniča, ki je rad citiral kitajskega pesnika Tu Fuja:

Ko knjige berem,
z vinom se krepčam
in znak preskočim,
če ga ne poznam.

Jaz pa se bom potrudil, da bo besedilo razumljivo tudi brez preskočenih znakov. Sicer pa je primerno mesto, do katerega lahko pohitite sovražniki matematike, tam, kjer je slikica. Poskrolajte.

Recimo, da imamo dva objekta, opisana z nekimi spremenljivkami.

\[ \begin{eqnarray} \mathbf{a} & = & (a_1, a_2, \ldots, a_n)\\ \mathbf{b} & = & (b_1, b_2, \ldots, b_n) \end{eqnarray} \]

Recimo, da gre za podatke o starosti, telesni teži (v kg) in višini (v cm) ter običajnem srčnem utripu (v utripih na minuto). Tedaj to morda izgleda tako

ana = (35, 63, 175, 70)
berta = (38, 56, 163, 75)

Evklidska razdalja

Tale razdelek preskočite, če vas je ob pogledu nanj strah. Ostanek bo (vseeno) razumljiv.

Evklidska razdalja je razdalja, kot smo je vajeni iz resničnega sveta (zračna razdalja) in iz matematike ("običajna" razdalja med dvema točkama, pa Pitagorov izrek pa to). Izračunamo jo kot koren vsote kvadratov razlik. :)

\[d_2(\mathbf{a}, \mathbf{b}) = \sqrt{(a_1 - b_1)^2 + (a_2 - b_2)^2 + \ldots(a_n + b_n)^2}\]

ali, bolj učeno,

\[d_2(\mathbf{a}, \mathbf{b}) = \sqrt{\sum_{i=1}^n (a_i - b_i)^2}\]

ali, manj učeno

\[\begin{eqnarray} d_2(ana, berta) & = & \sqrt{(35 - 38)^2 + (63 - 56)^2 + (175 - 163)^2 + (70 - 75)^2} \\ & = & \sqrt{3^2 + 7^2 + 12^2 + 5^2} \\ & = & \sqrt{227} \\ & = \doteq & 15 \end{eqnarray} \]

Manhattanska razdalja

Manhattansko razdaljo poznajo predvsem prebivalci Manhattana. Če so na križišču 25. ulice in 3. avenije ter jim je priti na križišče 32. ulice in 7. avenije, bodo morali prehoditi 7 + 4 = 11 blokov. Kakorkoli si izberejo pot po teh mreži, razdalja bo takšna.

Učeno:

\[d_1(\mathbf{a}, \mathbf{b}) = |a_1 - b_1| + |a_2 - b_2| + \ldots|a_n + b_n|\]

Še bolj učeno:

\[d_1(\mathbf{a}, \mathbf{b}) = \sum_{i=1}^n |a_i - b_i|\]

In manj učeno:

\[\begin{eqnarray} d_1(ana, berta) & = & |35 - 38| + |63 - 56| + |175 - 163| + |70 - 75| \\ & = & 3 + 7 + 12 + 5 \\ & = & 27 \end{eqnarray} \]

Kosinusna razdalja

Kosinusno podobnost izračunamo kot kosinus kota med vektorjema od izhodišča do točk. Kosinusno razdaljo izračunamo tako, da podobnost odštejemo od 1.

Kosinus kota je, vemo iz srednješolske matematike (za mnoge najbrž bolj: smo vedeli, a smo pozabili), enak skalarnemu produktu normiranih vektorjev.

\[ \begin{eqnarray} d_{cos} & = & 1 - \cos\phi \\ & = & 1 - \frac{\mathbf{a} \circ \mathbf{b}}{|\mathbf{a}| |\mathbf{b}|} \\ & = & 1 - \frac{\sum_{i=1}^n a_i b_i}{\sqrt{\sum_{i=1}^n a_i^2}\sqrt{\sum_{i=1}^n b_i^2}} \end{eqnarray} \]

Za Ano in Berto je to

\[ \begin{eqnarray} d_{cos} & = & 1 - \frac{35 \times 38 + 63 \times 56 + 175 \times 163 + 70 \times 75} {\sqrt{35^2 + 63^2 + 175^2 + 70^2}\sqrt{38^2 + 56^2 + 163^2 + 75^2}} \\ & = & 1 - \frac{38633}{\sqrt{40719} \sqrt{36774}} \\ & = & 0.00758 \end{eqnarray} \]

Ta številka je bistveno manjša od evklidske in manhattanske razdalje. Vendar tega ne moremo neposredno primerjati. Kosinusna je vedno med 0 in 2, oni dve pa sta na merski lestvici, ki ustreza lestvicam spremenljivke. Ta številka izraža veliko podobnost med njima, vendar je tako tudi zato, ker kosinusna razdalja za tale primer ni primerna. Več o tem proti koncu.

Jaccardov indeks

V povzetku predavanja je omenjen tudi Jaccardov indeks. Z njim lahko računamo podobnosti med množicami. Razložen je v zapiskih, v tole zgodbo pa ne sodi.

Grafična primerjava

Evklidska in manhattanska razdalja sta jasni. Pri kosinusni si lahko predstavljamo, da meri kot med točkama; predstavlja ga rdeča črtkana črta. V resnici pa meri 1 - kosinus tega kota. To je, če nisem česa spregledal, rdeča črta, ki kaže, za koliko je kateta onega pravokotnega trikotnika manjša od 1. Bolj ko sta točki po enakim kotom, manjša je ta črtica.

Ampak tule vam dam glede matematike odpustek: predstavljajte si, da je kosinusna razdalja v resnici kot, črtkana črta.

Bolj pomembno je namreč tole: kosinusna razdalja ima, kot smo napisali v zapiskih, to lastnost, da ignorira razdalje in gleda le kote. Če gledamo iz Maribora sta, s perspektive kosinusne razdalja, Ljubljana in Celje čisto blizu eden drugemu (ker sta v isti smer), Ptuj in Slovenska Bistrica pa daleč (ker sta pod pravim kotom). To vedenje je na prvi pogled čudno, slika pa nam pokaže, v čem bi lahko bil smisel. Ker kosinusna razdalja gleda le kot, je vseeno, kje na premici, ki povezuje izhodišče koordinatnega sistema in točko leži točka. Vse točke se v bistvu preslikajo na enotsko krožnico. Zakaj bi bilo to dobro ... bomo izvedeli v naslednjem razdelku.

Postavitev na enake merske lestvice

Vrnimo se k Ani in Berti.

ana = (35, 63, 175, 70)
berta = (38, 56, 163, 75)

Prvi podatek, starost, očitno ni na enaki merski lestvici kot telesna višina. Običajni srčni utrip v mirovanju je pa spet nekaj tretjega: dva osebi se lahko razlikujeta za 60 let starosti, ne pa za 60 srčnih utripov na minuto (v mirovanju!). Zato moramo pred računanjem spraviti vse spremenljivke na enako mersko lestvico.

Navadno to storimo tako, da odštejemo najmanjšo vrednost določene spremenljivke in delimo z razponom. Recimo, da imamo med podatki osebe, ki so stare med 20 in 50 let. V tem primeru bomo Anino starost popravili v \((35 - 20) / (50 - 20) = 15 / 30 = 0.5\). Ana je točno na polovici celotnega razpona starosti. Bertino pa v \((38 - 20) / (50 - 20) = 18 / 30 = 0.6\). Njuna razlika v starosti je torej 0.1, to je, 10 % razpona. Enako storimo še z drugimi spremenljivkami.

Če si predstavljamo tabelo podatkov: vsak stolpec ustreza eni spremenljivki in ob takšnem normiranju popravljamo vsak stolpec, zato da postanejo stolpci med seboj primerljivi.

Takšno normiranje opravimo za evklidsko in manhattansko razdaljo.

Kosinusna se normira sama, vendar drugače. Če se spomnimo formule (ki je, da ne plašim nematematikov, tule ne bom ponavljal): v imenovalcu sta dolžini vektorjev. V geometrijski predstavi sta povzročili, da sta se točki premaknili (projecirali, bi rekli kolegi matematiki) na enotsko krožnico. V smislu tega kar se dogaja s podatki, pa je to normalizacija vrstic. Vsako vrstico delimo z (uh) korenom vsote kvadratov njenih elementov.

Z drugimi besedami: pred evklidsko ali manhattansko razdaljo normaliziramo stolpce, da postanejo primerljivi. Kosinusna razdalja pa (sama od sebe, po definiciji) normira vrstice, da postanejo primerljive.

Kdaj izbrati katero razdaljo?

Evklidsko razdaljo bomo izbrali, kadar imamo neke raznolike podatke: vsak objekt je opisan z nekimi spremenljivkami, ki imajo rezlične pomene -- teža, višina in starost osebe, ali pa število zdravnikov na tisoč prebivalcev, poprečno izobrazbo in bruto družbeni proizvod države.

Kosinusno razdaljo bomo pogosto izbrali, kadar so vrstice opisane s spremenljivkami, ki imajo soroden pomen. Tipičen primer so bili priimki, pri katerih imamo podano pogostosti po občinah. Seveda gre za različne spremenljivke, vendar izražajo isto lastnost na različnih koncih.

Za primer si lahko predstavljamo tidve situaciji.

  • Primerjamo države: v eni imajo visoko število zdravnikov, visoko izobrazbo in visok BDP. V neki drugi državi imajo natančno trikrat manj zdravnikov, trikrat nižjo izobrazbo in trikrat nižji BDP. Bi rekli, da sta si tidve državi zelo podobni? Ne.

    No, kosinusna razdalja bi rekla, da sta si, ker bi normirala vrstici. Ko opazuje podobnost kotov v bistvu opazuje podobnost razmerij. In razmerje med številom zdravnikov in izobrazbo ter BDP je enako v obeh državah, zato je kot med njima enak 0. Seveda pa, matematično gledano, nima veliko smisla opazovati razmerja med številom zdravnikov in izobrazbo, saj gre za različne enote.

    V tem primeru torej uporabimo evklidsko razdaljo.

  • Primerjamo priimke po občinah; dva sta si podobna, če sta enako razmazana po vseh občinah. Prvi priimek je eden najpogostejših v državi; zelo pogosto je v občinah A in B, v C pa ga je zelo malo. Drugi priimek je redkejši; v vseh treh občinah ga je natančno trikrat manj kot prvega. Čeprav je situacija - številsko gledano - enaka kot pri primerjavi držav, bomo za tadva priimka rekli, da sta si zelo podobna, saj je njuna razmazanost po občinah enaka,

    In kosinusna razdalja bo razmišljala natančno tako. Oba priimka bo normirala z njunima splošnima pogostostima. Lahko si predstavljate, da osi na gornji sliki predstavljata pogostosti v dveh občinah. Če sta natančno enaki, le da je en priimek trikrat pogostejši, bosta ležala na isti premici (pod enakim kotom), le da bo eden trikrat dlje od izhodišča.

Manhattansko razdaljo izberemo redko. Problem evklidske je, da zaradi kvadriranja bolj upošteva tiste spremenljivke, v katerih je razlika velika. Če se dva zelo razlikujeta v eni spremenljivki, v vseh ostalih pa čisto malo, bo zelo prevladal vpliv te, velike razlike. Manhattanska razdalja se ne vede tako in enakovredno sešteva male in velike razlike. Manhattansko razdaljo se splača poskusiti, kadar evklidska ne da dobrih rezultatov. Čisto tako, empirično.

Kdaj normirati?

Praktično vedno. No, kosinusne nikoli in tudi Orange tega ne omogoča, ker nima smisla. Tam normalizacija pač teče po definiciji (in po vrsticah, ne stolpcih).

Normalizacijo bi izključili, kadar so spremenljivke že na enaki merski lestvici in to lestvico želimo ohraniti.

Recimo, da dijakinje in dijaki na lestvici od 1 do 100 ocenjujejo, kako so jim všeč romantične komedije, akcijski filmi in dokumentarne oddaje o francoski književnosti v času realizma. Dobimo naslednje rezultate:

        romantika    akcija    franc. realizem
mojca          81        30                 10
luka            9        90                  2

Se pravi

mojca = (81, 30, 10)
luka = (9, 90, 2)

Nadalje recimo, da so bili razponi 0 - 90 za romantiko, 0 - 100 za akcijo in 0 - 10 za dokumentarce o francoskih realistih. Ko normiramo, dobimo naslednje:

mojca = (0.9, 0.3, 1)
luka = (0.1, 0.9, 0.2)

in razlike med njima so

(0.8, 0.6, 0.8)

To najbrž ni to, kar bi želeli: Mojca in Luka imata zelo različen odnos do romantike (tozadevno bo prej ko slej prisiljen prostovoljno popustiti Luka) in še kar različen odnos do akcijskih filmov (Mojca, drži se!), težko pa bi rekli, da imata tudi različen odnos do Zolaja, ki ga družno ne trpita.

Tole je tipičen primer, ko so spremenljivke že na isti lestvici in jih moramo zato pustiti pri miru. Če jih normiramo, bomo napihnili razlike pri spremenljivkah, v katerih so si objekti v resnici podobni.