Register Now

Login

Lost Password

Lost your password? Please enter your email address. You will receive a link and will create a new password via email.

Add question

Login

Register Now

Your data is secured. So, please complete the form.

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 :

  1. Mengurangi per elemen antar 2 variabel, memutlakannya lalu menjumlahkannya. Sedangkan euclidean distance menghitung jarak antara 2 titik dengan konsep pythagoras.

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 vektor berdimensi n dan r bukan 1 dan 2. why? Karena kalau r=1 maka akan terbntuk 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 ini adalah algoritma yang paling simpel dari semua algoritma machine learning.

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

Bagaimana Kalkulus Menghitung Jarak ?

  • Ketika bekerja dengan dua buah bilangan, jarak diperoleh dari operasi mutlak. Contoh hitung jarak dari 3 ke 5! Maka hasilnya adalah

|3-5|=2

  • Ketika bekerja dengan suatu titik yang memiliki koordinat (x,y), jarak diperoleh dari rumus pythagoras sebagai berikut :

Sumber : youtube 

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

1 = |x_1|+|x_2|

1 = |1|+|0|

1 = |0.5|+|0.5|

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}

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 : careerfutura.com

 

 

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

 

 

About Riad Taufik Lazwardiclever

Lecturer of Mathematics at 1. Kalbis Institute | Managed by Binus (2018-now) 2. Telkom University (2017-2018) 3. UIN Bandung (2015-2018)

Follow Me

Comment ( 1 )

  1. Nice!!! Jadi punya opsi algoritma buat TA 😎

Leave a reply