Programlamada ve veri biliminde sürekli uzaklık hesabı yapmak durumunda kalıyoruz. İki sayının birbirinden uzaklığını fark alma işlemi sayesinde kolayca buluyoruz. Fakat, farklı veri tiplerinde farklı farklı yaklaşımlar söz konusu. Bu yazıda çeşitli türler için kullanılan yöntemleri özet olarak sunacağım. Başlayalım.
Vektör Uzunlukları
İki konum arasındaki mesafeyi bulmak istediğimizde bu konumlarla ilişkilendirilmiş 2 ya da 3 boyutlu bir vektöre ihtiyaç duyarız. (5,4) ve (1,2) şeklinde iki noktanın arasındaki mesafeyi bulmak için yapmam gereken öncelikle basit bir çıkarma işlemi olacaktır (5,4) - (1,2) = (4,2) bulduğum bu yeni vektörün uzunluğu bana mesafeyi verecektir. Peki ama (4,2) nin uzunluğu kaçtır? Bu vektörü alıp uzunluğunu verecek bir fonksiyon gerecektir. Bu fonksiyonun da "uzunluk" terimine uyumlu olması gerekir. Sola 5 adım gitmem de sağa 5 adım gitmem de aynı uzunlukta mesafe kat etmemle sonuçlanır. Dolayısıyla fonksiyon çıkarmanın sırasından etkilenmemelidir. (1,2) - (5,4) = (-4,-2) sonucunun da uzunluğu (4,2) ile aynı olmalıdır. 5 adım gitmem ile 10 adım gitmem arasındaki gibi oransal ilişkinin bu fonksiyonda görülmesi beklenir.
Norm Kavramı
Norm, bir önceki paragrafın terimleşmiş haline verilen isimdir. Norm, verilen vektör için sonucu negatif olmayan, homojen, alttoplamsal (bunu yazının devamında örnekledim) fonksiyonlardır. Norm, genellikle |x| \left \| x \right \|, {\left \| x \right \|}_p veya N(x) şeklinde gösterilmektedir. Buradaki "p" değerine aşağıda değineceğim.
Öklid Uzayında Vektör Uzunlukları
Özellikle farklı bir uzayda, düzlemde çalışıldığı belirtilmiyorsa o Öklid uzayıdır. Windows uygulaması yazarken Button'a verdiğimiz konum bence biz yazılımcılara güzel bir örnek olacaktır.
p-Norm, Minkowski Mesafesi
Ortalamalar için "kuvvet ortalaması" ne ise normlar için de p-norm'dur. Genelleştirilmiş bir formül sunar. O formül ise şu:
\left \| \overrightarrow{x} \right \|_p = { \left ( {\sum_{i=1}^{n}{\mid x_i \mid ^ p} } \right )} ^ {1 / p}Bu formül n boyutlu vektörler için "p" değerine göre uzunluk ve mesafe bulabilmektedir. Formülü mesafe bulmak için kullanmak istersek ya önce iki vektörü birbirinden çıkartıp yukarıdaki formülü uygulayabilir ya da iki işlemi birleştirip şu hale getirebiliriz.
M(\overrightarrow{x},\overrightarrow{y})_p = { \left ( {\sum_{i=1}^{n}{\mid x_i -y_i \mid ^ p} } \right )} ^ {\frac{1}{p}}Bu da karşımıza Minkowski mesafesi olarak çıkmaktadır. Bunu C# için yazalım.
public static double Mesafe(double[] vx, double[] vy, double p)
{
if (vx.Length != vy.Length)
{
throw new ApplicationException("Vektör boyutları eşit olmalı");
}
return Math.Pow(vx.Zip(vy, (x, y) => Math.Pow(Math.Abs(x - y), p))
.Sum(),
1.0 / p);
}İşlem adımlarında belki Zip fonksiyonu size yabancı gelmiş olabilir. Zip metodu aslında Select metoduna oldukça benzer. vz.Select(z=> z * 2); örneğinde vz'nin her bir değerinin 2 katı alınarak sonuç kümesine eklenmiştir. vz.Zip(vt, (z,t) => v * t); örneğinde ise vx ve vt dizilerinin aynı sıradaki elemanları bir birileri çarpılarak sonuç kümesine eklenmiştir.
L2 , Öklid Uzaklığı, Euclidean Distance
Günlük hayatta en sık kullandığımız uzaklık yöntemidir. "p" değerinin 2 alınmasıyla bulunabilir. Pisagor teorimi ile çözülebilir. Bunu kolayca görmek için (3,4) vektörün biraz çalışalım.
Bu vektörü bir doğru parçası olarak düşünelim. Uzunluğunu bulmak için herhangi bir eksene dikme inip, dik üçgen haline getirebiliriz.
Üçgen sizi ilkokul sıralarına götürmüş olmalı. Bu üçgenin hipotenüsü vektörümüzün uzunluğunu ve (3,4) noktasının orijine (0,0) olan mesafesini verecektir.
Pisagor ile çözecek olursak.
x = \sqrt{3^2 + 4 ^ 2} \\
x = \sqrt{9 + 16} \\
x = \sqrt{25} \\
x = 5Bunun orijine olan mesafesini bir de Minkowski uzaklığı ile çözelim.
M(\overrightarrow{x},\overrightarrow{(0,0)})_2 = {\left ( {\mid 3 \mid ^2 - \mid 0 \mid} ^2 + {\mid 4 \mid ^2 - \mid 0 \mid} ^ 2 \right )} ^ {1/2}
\\ ... \\ = 5Değişen bir şey olmadığı açık. Konuyla ilgili akılda olması gereken bir durum ise iç çarpım meselesidir. Öklid uzaklığı için bir vektörün norm'u aynı zamanda o vektörün kendisi ile iç çarpımının kareköküne eşittir.
İki vektörün iç çarpımı, matris çarpımı olarak yazılabilir, bu durumda vektörlerden birisi transpoze edilmelidir.
{\left \| \overrightarrow{x} \right \|}2 = \sqrt{{x}^\intercal {x} }Aynı nokta için hesabı buna göre yapalım.
\lVert \vec{x} \rVert _2=\sqrt{\left( \begin{array}{c}
3\\
4\\
\end{array} \right) \left( \begin{matrix}
3& 4\\
\end{matrix} \right)}
\\
\lVert \vec{x} \rVert _2=\,\,\sqrt{\left( 3 * 3 \right)+\left( 4 * 4 \right)}
\\ ...
\\
= 5
Makine öğrenmesi sırasında L2 normunun olduğu gibi kullanımından genellikle kaçınılır. Bunun iki büyük nedeni vardır.
- Değerler 0'a yakın olduğunda ayırt ediciliğinin azalmasıdır. Bunun önüne geçmek için L1 normu kullanılır.
- Uzaklığın karesi de farkın büyüklüğünü anlamakta yeterli olmaktadır. Bundan dolayı en sondaki kare kök işlemi hesaplama için gereksizdir. Kare kök işlemi çıkarıldığında öğrenme aynı şekilde gerçekleşecektir.
L1, TaxiCab, Manhattan Distance
Oldukça basit yapıyı sahip ama oldukça da güçlü, gördüğüm kadarıyla pek sevilen bir uzaklık ölçüsü. Kendisine yakıştırılan Taksi arabası, Manhattan yakıştırmaları oldukça yerindedir. Manhattan blok halinde yapılardan oluşmaktadır. Burada bir noktadan başka noktaya gidecek olan normal bir taksi, çapraz hareket edemeyeceğinden gideceği en kısa yollar her iki eksendeki değerlerin toplamı kadar olacaktır.
(3,4) noktamız için orijine olan uzaklık 3 + 4 = 7 olacaktır. Uzun uzun formüle koyalım:
M(\overrightarrow{x},\overrightarrow{(0,0)})_1 = {\left ( {\mid 3 \mid ^1 - \mid 0 \mid} ^1 + {\mid 4 \mid ^1 - \mid 0 \mid} ^ 1 \right )} ^ {1/1}
\\
M(\overrightarrow{x},\overrightarrow{(0,0)})_1 = {\left ( {\mid 3 \mid - \mid 0 \mid} + {\mid 4 \mid - \mid 0 \mid} \right )}
\\
M(\overrightarrow{x},\overrightarrow{(0,0)})_1 = {\left ( {\mid 3 \mid} + {\mid 4 \mid} \right )}
\\ = 7Böylesine basit bir işlem için C# kodunu da sadeleştirmek güzel olacaktır.
public static double Mesafe(double[] vx, double[] vy, double p)
{
if (vx.Length != vy.Length)
{
throw new ApplicationException("Vektör boyutları eşit olmalı");
}
if(p == 1)
{
return vx.Zip(vy, (x, y) => Math.Abs(x - y)).Sum();
}
return Math.Pow(vx.Zip(vy, (x, y) => Math.Pow(Math.Abs(x - y), p))
.Sum(),
1.0 / p);
}L1 makine öğrenmesinde en sık kullanılan uzaklık ölçümüdür.
En Büyük Normu, Lmax, Chebyshev Distance, Chessboard Distance
Bu yöntem de ise p değeri sonsuz büyük olarak kabul edilir. Lafa girmeden,(3,4) noktasının orijine uzaklığını formülde yerine koyalım.
M\left( \overrightarrow{x},\overrightarrow{\left( 0,0 \right) } \right) _{\max}=\left( \mid 3\mid ^{\infty}-\mid 0\mid ^{\infty}+\mid 4\mid ^{\infty}-\mid 0\mid ^{\infty} \right) ^{\frac{1}{\infty}}
\\
M\left( \overrightarrow{x},\overrightarrow{\left( 0,0 \right) } \right) _{\max}=\left( 3^{\infty}+4^{\infty} \right) ^{\frac{1}{\infty}}Sonsuz kuvveti nasıl hesaplayacağım? Peki bir sayının sonsuz dereceden kökü nedir? 1/sonsuz ne demektir. Öncesinde mevcut C# kodumuzu aşağıdaki şekilde çağırarak sonucu görmek istiyorum:
var sonuc = Mesafe(new[] { 0D, 0D }, new[] { 3D, 4D }, double.PositiveInfinity);Çalıştırdığımda karşıma çıkan sonuç 1, çünkü C# kodumuz formülü aşağıdaki gibi devam ettirecek:
M\left( \overrightarrow{x},\overrightarrow{\left( 0,0 \right) } \right) _{\max}=\left( \infty +\infty \right) ^{\frac{1}{\infty}}
\\
M\left( \overrightarrow{x},\overrightarrow{\left( 0,0 \right) } \right) _{\max}=\left( \infty \right) ^{\frac{1}{\infty}}
\\
M\left( \overrightarrow{x},\overrightarrow{\left( 0,0 \right) } \right) _{\max}=\left( \infty \right) ^0
\\
M\left( \overrightarrow{x},\overrightarrow{\left( 0,0 \right) } \right) _{\max}=1Fakat bu hatalıdır. Bunun sebebi kullandığımız veri türü olan double'ın sonsuz sayıda basamak alamamasıdır. 3'ün sonsuz kuvvetini hesaplamayamaz ve "sonsuz" der. 1 / sonsuz ise aslında 0 değildir. Fakat o kadar küçüktür ki double da en yakın değer 0 dır ve sonucu 0 olarak alacaktır.
Yapmamız gereken ise limit uygulamak olacaktır. Bunun için p değerini büyüterek sonucu inceleyelim:
for (int i = 1; i < 100; i++)
{
var sonuc = Mesafe(new[] { 0D, 0D }, new[] { 3D, 4D }, i);
Console.WriteLine($"p={i} => {sonuc}");
}Kodun çıktısı aşağıdaki gibi olacaktır:
p=1 => 7
p=2 => 5
p=3 => 4.497941445275415
p=4 => 4.284572294953817
p=5 => 4.174027662897746
p=6 => 4.110704132575835
p=7 => 4.072242319397026
p=8 => 4.04799203437848
p=9 => 4.032307299196485
p=10 => 4.021974149822332
p=11 => 4.015071076052405
p=12 => 4.010408520546921
p=13 => 4.0072309746728
p=14 => 4.005049203883416
p=15 => 4.003541555587008
p=16 => 4.002493952812106
p=17 => 4.001762467080604
...
p=96 => 4.000000000000042
p=97 => 4.000000000000031
p=98 => 4.000000000000023
p=99 => 4.000000000000018Buradan da sonucun p arttıkça 4'e yaklaştığını anlayabiliriz. Sonuç sayılardan büyük olan çıkacaktır. Formül de L1 de olduğu gibi sadeleştirildiğinde aslında şu hale dönecektir.
M\left( \overrightarrow{x},\overrightarrow{\left( 0,0 \right) } \right) _{\max}=\max \left( \mid 3\mid -\mid 0\mid ,\mid 4\mid -\mid 0\mid \right)Bu yeni bilgi ile C# metodumuzu düzenleyelim:
public static double Mesafe(double[] vx, double[] vy, double p)
{
if (vx.Length != vy.Length)
{
throw new ApplicationException("Vektör boyutları eşit olmalı");
}
if (p == double.PositiveInfinity)
{
return vx.Zip(vy, (x, y) => Math.Abs(x-y)).Max();
}
if(p == 1)
{
return vx.Zip(vy, (x, y) => Math.Abs(x - y)).Sum();
}
return Math.Pow(vx.Zip(vy, (x, y) => Math.Pow(Math.Abs(x - y), p))
.Sum(),
1.0 / p);
}L0
Aslında bir norm olmayan bu durum vektörün içindeki 0 olmayan eleman sayısını bulmak için kullanılır. Norm değildir çünkü yukarıda yazdığımız norm olma şartlarını sağlamamaktadır. Formülümüzde "p" için 0 verdiğimizde kuvvet 1/0 olacaktır ki kendisi tanımsızdır. Dolayısıyla 0 dan farklı değerler için C# kodumuzu şu şekle sokabiliriz:
public static double Mesafe(double[] vx, double[] vy, double p)
{
if (vx.Length != vy.Length)
{
throw new ApplicationException("Vektör boyutları eşit olmalı");
}
if (p == 0)
{
return vx.Zip(vy, (x, y) => Math.Abs(x - y) != 0).Count(x=>x);
}
if (p == double.PositiveInfinity)
{
return vx.Zip(vy, (x, y) => Math.Abs(x - y)).Max();
}
if (p == 1)
{
return vx.Zip(vy, (x, y) => Math.Abs(x - y)).Sum();
}
return Math.Pow(vx.Zip(vy, (x, y) => Math.Pow(Math.Abs(x - y), p))
.Sum(),
1.0 / p);
}Norm 0? için işin içine kompleks sayıların da dahil olduğu F uzayında farklı formüller bulunmaktadır.
Haversine Formülü
Dünya üzerindeki iki konum arasındaki mesafeyi alırken, enlem ve boylam bilgilerini Öklid uzaklığı ile kullanmak gerçek mesafe arttıkça giderek daha hatalı sonuçlar verecektir. Sebebini biliyorsunuz, Dünya yuvarlak ve harita ise düz. Harita üzerinde cetvelle çizeceğimiz dümdüz bir çizgi, o haritayı küre (geoid) hale getirdiğinizde en kısa yol olmayacaktır. İşte burada Haversine yöntemini kullanmak gerçeğe yakın sonuçlar almamızı sağlıyor. Yakın; çünkü bu yöntem Dünya'nın mükemmel bir küre olduğunu varsaymaktadır.
\Delta \sigma =\mathrm{arc}\tan \frac{\sqrt{\left( \cos \phi _2\sin \left( \Delta \lambda \right) \right) ^2+\,\,\left( \cos \phi _1\sin \phi _2-\sin \phi _1\cos \phi _2\cos \left( \Delta \lambda \right) \right) ^2}}{\sin \phi _1\sin \phi _2+\cos \phi _1\cos \phi _2\cos \left( \Delta \lambda \right)}
Formülde 4 adet parametre var \phi enlem açılarını, $$\lambda$$ boylam açılarını temsil ediyor. \Delta işareti ise fark işlemi anlamına geliyor (\Delta \lambda = \mid \lambda_1 - \lambda_2 \mid).
Burada yapılanı şöyle düşünebilirsiniz, bir top üzerine kalemle iki noktadan işaret koyun. Bu iki işaret arasını çizin. Bu en kısa çizgi bir doğru olmayacaktır. Bu eğimli parçaya jeodezik eğri adı veriliyor. Bu eğriyi devam ettirdiğinizde bir çember elde edeceksiniz. Topun çevresini biliyoruz, sıra bu eğrinin uzunluğunu bulmakta. Bu iki noktanın, enlem, boylam bilgileri yayın merkeze yaptığı açıyı bulmamızı sağlayacaktır. Gerisi oran/orantı olacaktır.
C# içerisinde bu formül hazır olarak bulunmaktadır. Yine de uygulamasını görmek isterseniz şu adrese bakın: https://www.geeksforgeeks.org/haversine-formula-to-find-distance-between-two-points-on-a-sphere/
Fakat hazır olanı neden kullanmayalım?
var konum1 = new GeoCoordinate(39.9, 32.8);
var konum2 = new GeoCoordinate(36.8, 30.7);
var mesafe = konum1.GetDistanceTo(konum2);Vincenty Formülü
Şayet Haversine yönteminden çok daha gerçek sonuçlar elde etmek istiyorsanız kullanabileceğiniz bir alternatiftir. Mantığı benzer olmakla beraber çember yerine elips üzerinde çalışmaktadır. Fakat, bu daha yüksek işlem gücü gerektirecektir.
Daha fazla detay için şu adrese bakabilirsiniz.
http://www.movable-type.co.uk/scripts/latlong-vincenty.html
Bunu C# da uygulanabilmesi için https://github.com/janantala/GPS-distance/blob/master/java/Distance.java adresindeki uyarladım. Kendisi şu şekilde:
public static double GetVincentyDistance(double lat1, double lon1, double lat2, double lon2)
{
const double a = 6378137.0;
const double b = 6356752.314245;
const double f = 1.0 / 298.257223563;
var lat1Rad = Math.PI / 180.0 * lat1;
var lat2Rad = Math.PI / 180.0 * lat2;
var l = Math.PI / 180.0 * (lon2 - lon1);
var u1 = Math.Atan((1.0 - f) * Math.Tan(lat1Rad));
var u2 = Math.Atan((1.0 - f) * Math.Tan(lat2Rad));
double sinU1 = Math.Sin(u1), cosU1 = Math.Cos(u1);
double sinU2 = Math.Sin(u2), cosU2 = Math.Cos(u2);
double cosSqAlpha, sinSigma, cos2SigmaM, cosSigma, sigma;
double lambda = l, lambdaP, iterLimit = 100.0;
do
{
double sinLambda = Math.Sin(lambda), cosLambda = Math.Cos(lambda);
sinSigma = Math.Sqrt(cosU2 * sinLambda
* (cosU2 * sinLambda)
+ (cosU1 * sinU2 - sinU1 * cosU2 * cosLambda)
* (cosU1 * sinU2 - sinU1 * cosU2 * cosLambda)
);
if (sinSigma == 0) { return 0; }
cosSigma = sinU1 * sinU2 + cosU1 * cosU2 * cosLambda;
sigma = Math.Atan2(sinSigma, cosSigma);
var sinAlpha = cosU1 * cosU2 * sinLambda / sinSigma;
cosSqAlpha = 1.0 - sinAlpha * sinAlpha;
cos2SigmaM = cosSigma - 2.0 * sinU1 * sinU2 / cosSqAlpha;
var c = f / 16.0 * cosSqAlpha * (4.0 + f * (4.0 - 3.0 * cosSqAlpha));
lambdaP = lambda;
lambda = l + (1.0 - c) * f * sinAlpha
* (sigma + c * sinSigma
* (cos2SigmaM + c * cosSigma
* (-1.0 + 2.0 * cos2SigmaM * cos2SigmaM)
)
);
} while (Math.Abs(lambda - lambdaP) > 1e-12 && --iterLimit > 0.0);
if (iterLimit == 0) { return 0; }
var uSq = cosSqAlpha * (a * a - b * b) / (b * b);
var A = 1.0 + uSq / 16384.0
* (4096.0 + uSq * (-768.0 + uSq * (320.0 - 175.0 * uSq)));
var B = uSq / 1024.0 * (256.0 + uSq * (-128.0 + uSq * (74.0 - 47.0 * uSq)));
var deltaSigma =
B * sinSigma
* (cos2SigmaM + B / 4.0
* (cosSigma
* (-1.0 + 2.0 * cos2SigmaM * cos2SigmaM) - B / 6.0 * cos2SigmaM
* (-3.0 + 4.0 * sinSigma * sinSigma)
* (-3.0 + 4.0 * cos2SigmaM * cos2SigmaM)));
var s = b * A * (sigma - deltaSigma);
return s;
}Haversine kısmındaki hesaplamayı öklid,haversine ve vincenty yöntemleri ile sırasıyla 373376.922951633m;
377667.534085103m;376986.078702478m çıkacaktır (hesap hatası yapmadıysam). Hassasiyete göre kendiniz karar vereceksiniz.
C# uygulamsı için
haversine
Hamming
JACCARD
