4 Cara Menghitung Jarak Dan Algoritma KNN

Add post

Username* Please type your username .

E-Mail* Please type your E-Mail .

Post Title* Please choose an appropriate title for the post .

Category* Please choose the appropriate section so easily search for your post .

Tags Please choose suitable Keywords Ex : post , video .

Attachment

Browse

Details

4 Cara Menghitung Jarak Dan Algoritma KNN

Algoritma K-NN merupakan algoritma yang bisa melakukan prediksi. Cara yang digunakan sangat sederhana. Cukup menghitung jarak terdekat. Artinya, apabila ada input objek baru yang tak dikenali,

algoritma knn akan mencari objek terdekat dengan objek yang baru diinput tadi (di dalam database),

kemudian melakukan tindakan (kepada objek yang baru diinput) yang sama dengan tindakan yang dilakukan kepada objek terdekatnya. Sesuai dengan namanya KNN (K Nearest Neighbors).

Contoh, misal kita terbiasa menghindari gorengan. Ketika kita akan memakan ayam goreng otak kita akan membandingkannya dengan gorengan (karena sama-sama digoreng), karenanya kita tidak jadi memakan ayam goreng.

Jadi, tindakan pada objek baru yang didasarkan pada apa yang dilakukan pada “objek terdekatnya” adalah tindakan prediksi. Teknik prediksi yang sederhana, kan?

“Nah, Gimana sih cara menghitung jarak terdekat?”

Ada berbagai cara. Tergantung rumus (metrik/ukuran) apa yang mau dipakai. Pada artikel ini hanya dibahas 4 cara sebagai berikut :

1.Euclidean Distance

$\displaystyle d(x,y)=\sqrt{ \sum_{i=1}^m (x_i-y_i)^2}$

ide rumus ini dari rumus pythagoras

$\displaystyle c=\sqrt {a^2+b^2}$

* $d(x,y)$ dibaca distance antara x dan y.

2.Manhattan Distance

$\displaystyle d(x,y)=\sum_{i=1}^m |x_i - y_i|$

*rumus ini mencari jarak hanya dengan menjumlahkan semua selisih dari jarak $x_i$ dan $y_i$ .

Mungkin idenya dari menghitung jarak dari 3 ke 5 yaitu 2 karena |3-5|=2.

Apa bedanya dengan euclidean distance?

Manhattan distance itu : mengurangi per elemen antar 2 variabel, memutlakannya lalu menjumlahkannya. Sedangkan euclidean distance menghitung jarak antara 2 titik dengan konsep pythagoras, yang kalau divisualisasikan berupa garis miring pada segitiga siku-siku.

3.Minkowsky Distance

$\displaystyle d(x,y)=(\sum_{i=1}^m |x_i-y_i|^r)^{1/r}$

Ide rumus ini diambil dari konsep aljabar dengan objek yang berupa vektor berdimensi n. Tetapi, r bukan 1 dan 2. Why? Karena kalau $r=1$ maka akan diperoleh rumus jarak manhattan distance, kalau $r=2$ euclidean distance.

4.Chebychev Distance

$\displaystyle d(x,y)=\max_{i=1}^n |x_i-y_i|$

*rumus ini mencari jarak yang terbesar antara x_i dan y_i

Fact: Algoritma KNN adalah algoritma yang paling simpel dari semua algoritma machine learning.

Fun : Algoritma ini bisa dipakai untuk “mesin pencari” seperti Google.

Bagaimana Makhluk Kalkulus Menghitung Jarak ?

Kalkulus menghitung jarak dengan operasi mutlak, karena hanya bekerja dengan dua buah bilangan. Contoh hitung jarak dari 3 ke 5! Maka hasilnya adalah

$|3-5|=2$

Ketika bekerja dengan suatu titik yang memiliki koordinat (x,y), Kalkulus menghitung jarak menggunakan rumus pythagoras sebagai berikut :

Sumber : youtube

“Dari gambar di atas, terlihat kan bahwa jaraknya itu adalah sisi miring pada segitiga siku-siku?”

Bagaimana Visualisasi dari Manhattan Distance ?

$\displaystyle d(x,y)=\sum_{i=1}^m |x_i - y_i|$

Misal $d(x,y)=1$ dan berada pada ruang 2 dimensi $x_1$ dan $x_2$ bukan $x_i$ dan $y_i$ seperti rumus di atas, maka diperoleh diagram cartesius berikut

yang mana sumbu vertikalnya $x_2$ dan sumbu horizontalnya $x_1$ . Kemudian kita misalkan jaraknya adalah 1. Kemudian kita cari $x_1$ dan $x_2$ yang apabila dimutlakan lalu dijumlahkan hasilnya menjadi 1.

$1 = |x_1|+|x_2|$

$1 = |1|+|0|$

$1 = |0.5|+|0.5|$

Nah, jika kita plot semua $x_1,x_2$ yang memenuhi $1 = |x_1|+|x_2|$ maka akan diperoleh :

Bagaimana Visualisasi dari Euclidean Distance ?

$d(x,y)=\sqrt{ \sum_{i=1}^m (x_i-y_i)^2}$

Kita akan melakukan hal yang sama ketika kita memvisualisasikan manhattan distance. Misal $d(x,y)=1$ dan kita berada pada ruang dua dimensi $x_1, x_2$ maka

$1=\sqrt{ x_1^2+x_2^2}$

Jika semua $x_1$ dan $x_2$ yang memenuhi persamaan di atas diplot, maka akan diperoleh :

Bagaimana Visualisasi Chebyshev Distance ?

Jika $p \rightarrow \infty$ minkowsky distance akan menjadi chebyshev distance.

Sumber : education to the core

Jika manusia satu dan lainnya bisa dekat karena ada kesamaan dan ada sesuatu yang bisa dishare. Bagaimana cara manusia mendekatkan diri dengan sang pencipta? ~Prof Lang