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.

Send Message

Add post

Add question

You must login to ask question.

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

Artikel ini mudah difahami ?

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 Lazwardiexcellent

"In the middle of difficulties lies opportunities"

Follow Me

Comment ( 1 )

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

Leave a reply