Veri bilimi ve makine öğrenmesi algoritmalarında uzaklık ve benzerlik hesapları olmazsa olmazdır. Bir kaç yazı ile farklı veri türleri için popüler uzaklık ve benzerlik hesaplarını anlatacağım. Bu yazıların ilkinin konusu vektörlerde norm ve uzaklık olacak.
Skaler değerler için uzaklık; 8 ile 10 arasındaki uzaklığın 2 olması gibi iki değerin arasındaki farkın mutlak değeridir. Konu vektörler ve matrisler olduğunda farklı amaçlar için farklı hesaplama türleri bulunmaktadır.
İki konum arasındaki mesafeyi bulmak istediğimizde bu konumlarla ilişkilendirilmiş vektörlere ihtiyaç duyarız. İki boyutlu düzlemde (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" kelimesine anlamca uyumlu olması gerekir. Sola 5 adım gitmem de sağa 5 adım gitmem de aynı uzunlukta mesafe kat etmemle sonuçlanır. Masadaki kalem ile silgi arasındaki mesafe kalemden bakınca farklı, silgiden bakınca farklı değildir. Dolayısıyla uzaklığı bulacak fonksiyon, parametrelerinin 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 de 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 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.
p-Norm, Minkowski Mesafesi
Ortalamalar için "kuvvet ortalaması" ne ise normlar için de p-norm o 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 ile çarpılarak sonuç kümesine eklenmiştir. Bu kod bu haliyle gayet yeterlidir. Fakat bir kaç özel durumu aşağıdaki ekleyeceğim.
L2 Norm, Ö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. Ve hatta {\left \| x \right \|}_2 yerine {\left \| x \right \|} yazılır. Pisagor teorimi ile çözülebilir. Bunu kolayca görmek için (3,4) vektöründe biraz çalışalım.
Bu vektörü bir doğru parçası olarak düşünelim. Uzunluğunu üçgen yardımıyla 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 dolayısıyla (3,4) noktasının orijine (0,0) olan mesafesini verecektir.
Pisagor yöntemi ile çözecek olursak.
x = \sqrt{3^2 + 4 ^ 2} \\
x = \sqrt{9 + 16} \\
x = \sqrt{25} \\
x = 5Şimdi bir de bunun orijine olan mesafesini 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 diğer 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örler matris formuna getirilmeli ve 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 çoğu hesaplama için gereksizdir. Kare kök işlemi çıkartıldığında öğrenme aynı şekilde gerçekleşecektir. Bu kullanımı kaynaklarda "squared distance" olarak görebilirsiniz.
Şayet günü yakalayanlardansanız .net core ile hazır gelen Vector yapılarını kullanabilirsiniz.
var vektör = new Vector2(3, 4);
// Uzunluk
Console.WriteLine(vektör.Length());
// Kareli Uzunluk
Console.WriteLine(vektör.LengthSquared());
//Mesafe
var v1 = new Vector2(1f, 5f);
var v2 = new Vector2(4f, 9f);
Console.WriteLine(Vector2.Distance(v1,v2));
//kareli mesafe
Console.WriteLine(Vector2.DistanceSquared(v1, v2));
L1 Norm, TaxiCab, Manhattan Distance, Absolute Difference
Oldukça basit bir yapıya sahip ama oldukça güçlü, gördüğüm kadarıyla da pek sevilen bir uzaklık ölçüsüdür. Kendisine yapılan Taksi arabası, Manhattan yakıştırmaları oldukça yerindedir. Manhattan blok halinde, Excel tablosu gibi yapılardan oluşmaktadır. Burada bir noktadan başka noktaya gidecek olan bir taksi, binaların içinden geçemeyeceğinden çapraz hareket edemeyecektir. Yatayda ya da dikeyde hareket edebilir ve bu birden fazla en kısa yol oluşturur. Gideceği en kısa yol alternatiflerinin uzunlukları 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);
}Güncel örneği ise şöyle yazılabilir:
var v1 = new Vector2(1f, 5f);
var v2 = new Vector2(4f, 9f);
var vd = Vector2.Abs(v1 - v2);
var l1 = vd.X + vd.Y;
Console.WriteLine(l1);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. Detaya 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 hâle 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 Norm?, Zero Norm?
P değeri 1 in altına indiğinde çıkan değerler norm olma şartlarını sağlamadığı için norm olarak kabul edilmezler. Bu değer 0 olduğunda norm olarak kabul edilmese de vektörün içindeki 0 olmayan eleman sayısını bulmak için kullanılı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.
Canberra Uzaklığı
L1 in ağırlıklandırılması ile hesaplanır. Özellikle değerler pozitif ve 0'a yakın olduğunda kullanılır.Gruplar arası benzerlikleri bulmakta veya sıralı listeler arasındaki mesafelerde kullanılmaktadır.
M_{CAD}\left( \vec{x},\vec{y} \right) =\sum_{i=1}^n{\frac{\mid x_i-y_i\mid}{\mid x_i\mid +\mid y_i\mid}}public static double CanberraMesafe(double[] vx, double[] vy)
{
if (vx.Length != vy.Length)
{
throw new ApplicationException("Vektör boyutları eşit olmalı");
}
return vx.Zip(vy, (x, y) => Math.Abs(x - y) / (Math.Abs(x) + Math.Abs(y))).Sum();
}Biraz daha detay isterseniz:
🌎 https://blog.csiro.au/going-nuts-with-the-canberra-distance/
🌍 http://www.code10.info/index.php?option=com_content&view=article&id=49:articlecanberra-distance&catid=38:cat_coding_algorithms_data-similarity&Itemid=57
Bray Curtis, Sorensen
L1'e oldukça benzediği için listeye aldım. ML uygulamalarında ben pek kullanımına rastlamadım. Şayet bir anektodunuz varsa paylaşmaktan çekinmeyin lütfen.
M_{BCD}\left( \vec{x},\vec{y} \right) =\frac{\sum_{i=1}^n{\mid x_i-y_i\mid}}{\sum_{i=1}^n{x_i+y_i}}public static double BrayCurtisMesafe(double[] vx, double[] vy)
{
if (vx.Length != vy.Length)
{
throw new ApplicationException("Vektör boyutları eşit olmalı");
}
return vx.Zip(vy, (x, y) => Math.Abs(x - y)).Sum() / vx.Zip(vy, (x, y) => Math.Abs(x) + Math.Abs(y)).Sum();
}İlerleyen yazılarda yine bu kavram ilişkili benzerlik hesaplarına değineceğim. Görüşmek üzere.
çocukluk hayalim mesafeler koordinatlar noktalar
Çok güzel ve açıklayıcı anlatmışsın teşekkürler.
Çok güzel ve açıklayıcı olmuş elinize sağlık teşekkürler, ek kaynak vermende çok güzel.