Algoritma k-Nearest Neighbors (k-NN)

Contoh implementasi Data Mining Algoritma k-Nearest Neighbors (k-NN) menggunakan PHP dan MySQL untuk memprediksi kelulusan mahasiswa tepat waktu

Algoritma k-Nearest Neighbors (k-NN) adalah algoritma yang berfungsi untuk melakukan klasifikasi suatu data berdasarkan data pembelajaran (train data sets), yang diambil dari k tetangga terdekatnya (nearest neighbors). Dengan k merupakan banyaknya tetangga terdekat

[ author : cahya dsn, published on : Nov 7, 2018 updated on : Nov 16, 2018 ]

minerva minerva donasi donation

Mau lihat artikel lainya? Dapatkan artikel-artikel lain seputar pemrograman website di sini, dan dapatkan ide-ide baru

Algoritma K-Nearest Neighbor (k-NN) adalah salah satu metode yang menerapkan algoritma supervised (Han, 2006) dimana hasil dari sampel uji yang baru diklasifikasikan berdasarkan mayoritas dari kategori pada k-NN. Ketepatan algoritma k-NN ditentukan oleh ada dan tidak adanya data yang tidak relevan, atau jika bobot fitur tersebut setara dengan relevansinya terhadap klasifikasi (Nugroho, 2015). Algoritma k-NN adalah salah satu metode yang digunakan untuk analisis klasifikasi, namun beberapa dekade terakhir metode k-NN juga digunakan untuk prediksi (Alkhatib, 2013). k-NN termasuk kelompok instance-based learning. Algoritma ini juga merupakan salah satu teknik lazy learning. k-NN dilakukan dengan mencari kelompok k objek dalam data training yang paling dekat (mirip) dengan objek pada data baru atau data testing(Leidiyana, 2010)

Mencari jarak terdekat antara data yang akan dievaluasi dengan k tetangga (neighbor) terdekatnya dalam data pelatihan. Ruang ini dibagi menjadi kelompok-kelompok berdasarkan klasifikasi data training. Sebuah titik pada tempat ini ditandai dengan kelas c, dimana jika kelas c merupakan klasifikasi yang sangat banyak ditemui pada k buah tetangga terdekat titik tersebut. Untuk sistem kerja k-NN data training di proyeksikan ke tempat berdimensi banyak, yang mana dari masing-masing dimensi mempersentasikan fitur dari data (Whidhiasih 2013)

1.1. Cara Kerja Algoritma k-Nearest Neighbors (k-NN)

Tujuan dari algoritma ini adalah mengklasifikasi objek baru berdasakan atribut dan sampel latih. pengklasifikasian tidak menggunakan model apapun untuk dicocokkan dan hanya berdasarkan pada memori. Diberikan titik uji, akan ditemukan sejumlah k objek (titik training) yang paling dekat dengan titik uji. Klasifikasi menggunakan voting terbanyak di antara klasifikasi dari k objek. Algoritma k-NN menggunakan klasifikasi ketetanggaan sebagai nilai prediksi dari sample uji yang baru. Dekat atau jauhnya tetangga biasanya dihitung berdasarkan jarak Eucledian.

Algoritma metode k-NN sangatlah sederhana, bekerja dengan berdasarkan pada jarak terpendek dari sample uji ke sample latih untuk menentukan k-NN nya. Setelah mengumpulkan k-NN, kemudian diambil mayoritas dari k-NN untuk dijadikan prediksi dari sample uji. Data untuk algoritma k-NN terdiri dari beberapa atribut multi-variate Xi yang akan digunakan untuk mengklasifikasikan Y. Data dari k-NN dapat dalam skala ukuran apapun, dari ordinal ke nominal.

Algoritma k- Nearest Neighbor menggunakan klasifikasi ketetanggaan (neighbor) sebagai nilai prediksi dari query instance yang baru. Algoritma ini sederhana, bekerja berdasarkan jarak terpendek dari query instance ke training sample untuk menentukan ketetanggaannya (Rizal, 2013). Langkah-langkah untuk menghitung metode k-Nearest Neighbor antara lain:

  • Menentukan parameter k
  • Menghitung jarak antara data yang akan dievaluasi dengan semua pelatihan
  • Mengurutkan jarak yang terbentuk
  • Menentukan jarak terdekat sampai urutan k
  • Memasangkan kelas yang bersesuaian
  • Mencari jumlah kelas dari tetangga yang terdekat dan tetapkan kelas tersebut sebagai kelas data yang akan dievaluasi

1.1.1. Perhitungan Jarak / Dissimilarity

Perhitungan dissimilarity -- dikenal juga sebagai jarak antar data (d) -- adalah bagian penting dalam algoritma k-Nearest Neighbor (k-NN). Ada banyak ragam perhitungan dissimilarity ini, diantaranya adalah :

1.1.1.1. Jarak Manhattan

Disebut Manhattan ini berdasar pada kota Manhattan yang tersusun menjadi blok-blok. Sehingga sering juga disebut city block distance, juga sering disebut sebagai ablosute value distance atau boxcar distance. Rumusan pencarian jarak Manhattan adalah sebagai berikut:

$$d(x,y)=\sum_{i=1}^n |x_i - y_i|$$
.. [KNN-01]

persamaan jarak Manhattan ini hanya menjumlahkan semua selisih dari $x_{i}$ dan $y_{i}$

1.1.1.2. Jarak Euclidean

Perhitungan jarak yang paling umum dipakai pada perhitungan pada algoritma k-NN adalah menggunakan perhitungan jarak Euclidean. Rumusannya adalah sebagai berikut:

$$d(x,y)=\sqrt(\sum _{{i=1}}^{n}(x_{i}-y_{i})^2)$$
.. [KNN-02]
dimana :
  • $x_{i}$ = sampel data
  • $y_{i}$ = data uji atau data testing
  • $i$ = variabel data
  • $d(x,y)$ = dissimilarity/jarak
  • $n$ = dimensi data

1.1.1.3. Jarak Minkowski

Persamaan ini adalah bentuk umum dari Jarak Euclidean, secara umum, operasi kuadrat bisa diganti dengan operasi nilai mutlak dan pangkat nonnegatif lainnya:
$$d(x,y)=(\sum_{i=1}^n |x_i-y_i|^r)^{1/r}$$
.. [KNN-03]

dimana :
  • $x_{i}$ = sampel data
  • $y_{i}$ = data uji atau data testing
  • $i$ = variabel data
  • $d(x,y)$ = dissimilarity/jarak
  • $n$ = dimensi data
  • $r$ = parameter
Euclidean distance (Jarak Euclidean) adalah kasus khusus persamaan di atas, yaitu dengan $r = 2$.

1.1.1.4. Jarak Chebychev

$$d(x,y)=max_{i=1}^n |x_i-y_i|$$
.. [KNN-04]
persamaan ini mencari jarak yang terbesar antara $x_{i}$ dan $y_{i}$

1.2. Kelebihan dan Kekurangan

Berikut ini beberapa kelebihan dan kekurangan dari algoritma k-Nearest Neighbors (k-NN)

1.2.1. Kelebihan k-NN

Algoritma k-NN memiliki beberapa kelebihan yaitu:

1.2.1.1. Sangat non-liniear

k-NN merupakan salah satu algoritma (model) pembelajaran mesin yang bersifat non-parametrik, yaitu model yang tidak mengasumsikan apa-apa mengenai distribusi instance di dalam dataset. Model non-parametrik biasanya lebih sulit diinterpretasikan, namun salah satu kelebihannya adalah garis keputusan kelas yang dihasilkan model tersebut bisa jadi sangat fleksibel dan non-linear.


Gambar 1 Perbandingan garis keputusan kelas k-NN (garis putus-putus abu-abu) dengan model klasifikasi linear (garis lurus ungu)

Pada ilustrasi di atas, k-NN dapat melakukan klasifikasi dengan tepat karena garis keputusan kelasnya non-linear. Bandingkan dengan model linear (semisal logistic regression) yang tentunya akan menghasilkan banyak mis-klasifikasi jika garis keputusan kelas dalam dataset sebenarnya bersifat non-linear.

1.2.1.2. Mudah dipahami dan diimplementasikan

Dari paparan yang diberikan dan penjelasan cara menghitung jarak dalam artikel ini, cukup jelas bahwa algoritma k-NN mudah dipahami dan juga mudah dimplementasikan. Untuk mengklasifikasi instance x menggunakan k-NN, kita cukup mendefinisikan fungsi untuk menghitung jarak antar-instance, menghitung jarak x dengan semua instance lainnya berdasarkan fungsi tersebut, dan menentukan kelas x sebagai kelas yang paling banyak muncul dalam k instance terdekat

1.2.1.3. Tangguh terhadap data training sample yang noisy

1.2.1.4. Efektif apabila data training sample-nya besar

1.2.1.5. Memiliki konsistensi yang kuat

Ketika jumlah data mendekati tak hingga, algoritma ini menjamin error rate yang tidak lebih dari dua kali Bayes error rate (error rate minimum untuk distribusi data tertentu). Jika tidak ada noise, maka Bayesian error rate = 0.

1.2.1.6. Asymptotically correct

Bayangkan bahwa dataset kita terdiri atas semua instance dalam populasi yang sedang kita cermati. Jika tidak ada noise di dalam dataset tersebut, maka k-NN dengan $k = 1$ akan menghasilkan klasifikasi yang 100% akurat! Penjelasannya sebagai berikut. Misalkan kita ingin mengklasifikasi instance x. Kita cukup mencari satu instance yang paling dekat dari x. Instance ini dijamin memiliki kelas yang sama dengan x. Mengapa? Karena kalau tidak sama, pasti ada instance lain yang lebih dekat dari x dan memiliki kelas yang sama dengan x, mengacu pada asumsi kita memiliki semua instance dan tidak ada noise di dalam dataset. Sangat menakjubkan untuk sebuah algoritma yang sederhana.

1.2.2. Kekurangan k-NN

Sedangkan kelemahan dari k-NN adalah :

1.2.2.1. Perlu Menentukan Parameter k (Jumlah Tetangga Terdekat)

1.2.2.2. Tidak Menangani Nilai Hilang (Missing Value) Secara Implisit

Jika terdapat nilai hilang pada satu atau lebih variabel dari suatu instance, perhitungan jarak instance tersebut dengan instance lainnya menjadi tidak terdefinisi. Bagaimana coba, menghitung jarak dalam ruang 3-dimensi jika salah satu dimensi hilang? Karenanya, sebelum menerapkan kNN kerap dilakukan imputasi untuk mengisi nilai-nilai hilang yang ada pada dataset. Contoh teknik imputasi yang paling umum adalah mengisi nilai hilang pada suatu variabel dengan nilai rata-rata variabel tersebut (mean imputation).

1.2.2.3. Sensitif Terhadap Data Pencilan (Outlier)

Seperti yang telah dijelaskan pada artikel sebelumnya, kNN bisa jadi sangat fleksibel jika k kecil. Fleksibilitas ini mengakibatkan k-NN cenderung sensitif terhadap data pencilan, khususnya pencilan yang terletak di 'tengah-tengah' kelas yang berbeda. Lebih jelasnya, perhatikan ilustrasi di bawah.


Gambar 2 Data pencilan bisa mengakibatkan klasifikasi yang salah dalam k-NN

Pada gambar kiri, seluruh instance bisa diklasifikasikan dengan benar ke dalam kelas biru dan jingga. Tetapi, ketika ditambahkan instance biru di antara instance jingga, beberapa instance jingga menjadi salah terklasifikasi.Perlu dipilih k yang tepat untuk mengurangi dampak data pencilan dalam k-NN.

1.2.2.4. Rentan Terhadap Variabel Yang Non-Informatif

Meskipun kita telah menstandardisasi rentang variabel, k-NN tetap tidak dapat mengetahui variabel mana yang signifikan dalam klasifikasi dan mana yang tidak. Lihat contoh berikut:


Gambar 3 Variabel yang noninformatif bisa mengakibatkan klasifikasi yang salah dalam k-NN

Pada ilustrasi di atas, klasifikasi sebetulnya bisa dilakukan menggunakan variabel a saja (perhatikan garis vertikal yang memisahkan kedua kelas secara linear). Namun, k-NN tidak dapat mengetahui bahwa variabel b tidak informatif. Alhasil, dua instance kelas biru terklasifikasi dengan salah, karena kedua instance tersebut dekat dengan instance kelas jingga dalam dimensi b. Andaikan kita hanya menggunakan variabel a dan membuang variabel b, semua instance akan terklasifikasi dengan tepat.Pemilihan variabel sebelum menerapkan kNN dapat membantu menangani permasalahan di atas. Selain itu, kita juga bisa memberi bobot pada variabel dalam perhitungan jarak antar-instance. Variabel yang kita tahu noninformatif kita beri bobot yang kecil, misalnya: $$d(x_{1},x_{2})=\sqrt(0.97*(x_{11}-x_{21})^2+0.15*(x_{12}-x_{22})^2)$$

1.2.2.5. Rentan Terhadap Dimensionalitas Yang Tinggi

Berbagai permasalahan yang timbul dari tingginya dimensionalitas (baca: banyaknya variabel) menimpa sebagian besar algoritma pembelajaran mesin, dan k-NN adalah salah satu algoritma yang paling rentan terhadap tingginya dimensionalitas. Hal ini karena semakin banyak dimensi, ruang yang bisa ditempati instance semakin besar, sehingga semakin besar pula kemungkinan bahwa nearest neighbour dari suatu instance sebetulnya sama sekali tidak 'near'.


Gambar 4 Dengan jumlah instance yang sama, jarak antar-instance bisa semakin menjauh apabila dimensi bertambah

Masalah tingginya dimensionalitas (terkadang) bisa diatasi dengan pemilihan variabel atau rekayasa fitur, misalnya dengan PCA (Principal component analysis).

1.2.2.6. Rentan Terhadap Perbedaan Rentang Variabel

Dalam perhitungan jarak antar-instance, k-NN menganggap semua variabel setara atau sama penting (lihat bagian penjumlahan pada rumus perhitungan jarak di atas). Jika terdapat variabel p yang memiliki rentang jauh lebih besar dibanding variabel-variabel lainnya, maka perhitungan jarak akan didominasi oleh p. Misalkan ada dua variabel, a dan b, dengan rentang variabel a 0 sampai 1.000 dan rentang variabel b 0 sampai 10. Kuadrat selisih dua nilai variabel b tidak akan lebih dari 100, sedangkan untuk variabel a kuadrat selisihnya bisa mencapai 1.000.000. Hal ini bisa mengecoh k-NN sehingga k-NN menganggap a tidak membawa pengaruh dalam perhitungan jarak karena rentangnya sangat besar dibanding rentang b. Ilustrasinya diberikan di bawah ini.


Gambar 5 Perbedaan rentang variabel bisa mengacaukan klasifikasi k-NN

Manakah yang merupakan nearest neighbour dari instance x? Jika dilihat dari 'kacamata' komputer, nearest neighbour x bukanlah y, melainkan z, Mengapa? Untuk mengatasi perbedaan rentang, biasanya dilakukan preproses berupa standardisasi rentang semua variabel sebelum menerapkan algoritma k-NN. Contohnya yaitu melalui operasi centre-scale atau operasi min-max.

1.2.2.7. Pembelajaran Berdasarkan Jarak Tidak Jelas

Pembelajaran berdasarkan jarak tidak jelas mengenai jenis jarak apa yang harus digunakan dan atribut mana yang harus digunakan untuk mendapatkan hasil yang terbaik

1.2.2.8. Nilai Komputasi yang Tinggi

Untuk mengklasifikasi sebuah instance x, k-NN harus menghitung jarak antara x dengan semua instance lain dalam dataset yang kita miliki. Dengan kata lain, kompleksitas waktu klasifikasi k-NN berbanding lurus dengan jumlah instance latih. Jika dataset yang kita miliki berukuran besar (terdiri dari banyak instance dan/atau banyak variabel), proses ini bisa jadi sangat lambat. Bayangkan, jika kita punya 10.000 instance dengan masing-masing 20 variabel dan kita ingin mengklasifikasi 100 instance baru (instance uji), maka total operasi yang harus dilakukan menjadi:

(100 instance uji * 10.000 instance_latih) * 20 (variabel/instance) * 2 (operasi/variabel) = 4*107 operasi.

Operasi ini bisa dipercepat dengan vektorisasi, namun nyatanya kNN tetap termasuk salah satu algoritma yang paling lambat dalam melakukan klasifikasi. Beberapa cara pengindexan (k-dimensional tree) dan berbagai proses heuristik -- semisal Locality Sensitive Hashing/LSH (Slaney, 2008 ) -- dapat digunakan untuk mereduksi biaya komputasi. Maka dari itu, tidak disarankan menggunakan kNN jika kita punya data latih yang sangat besar (big data).

1.3. Perbandingan Algortima k-NN dengan Algoritma Lain

Kita sudah mengetahui dari penjelasan sebelumnya bahwa algoritma k-Nearest Neighbor adalah sebuah metode klasifikasi terhadap sekumpulan data berdasarkan pembelajaran data yang sudah terklasifikasikan sebelumya. Termasuk dalam supervised learning, dimana hasil query instance yang baru diklasifikasikan berdasarkan mayoritas kedekatan jarak dari kategori yang ada dalam k-NN. Perbandingan antara algoritma k-Nearest Neighbour (k-NN) dengan algoritma C45 , Apriori, Bayesian Classification adalah sebagai berikut:

1.3.1. Algoritma C.45

Algoritma data mining C4.5 [lihat Data Mining Algoritma C4.5] merupakan salah satu algoritma yang digunakan untuk melakukan klasifikasi atau segmentasi atau pengelompokan dan bersifat prediktif. Dasar algoritma C4.5 adalah pembentukan pohon keputusan (decision tree). Cabang-cabang pohon keputusan merupakan pertanyaan klasifikasi dan daun-daunnya merupakan kelas-kelas atau segmen-segmennya.

Algoritma C4.5 merupakan salah satu algoritma machine learning. Dengan algoritma ini, mesin (komputer) akan diberikan sekelompok data untuk dipelajari yang disebut learning dataset. Kemudian hasil dari pembelajaran selanjutnya akan digunakan untuk mengolah data-data yang baru yang disebut test dataset . Karena algoritma C4.5 digunakan untuk melakukan klasifikasi, jadi hasil dari pengolahan test dataset berupa pengelompokkan data ke dalam kelas-kelasnya

1.3.2. Algoritma Apriori

Algoritma Apriori adalah algoritma pengambilan data dengan aturan asosiatif untuk menentukan hubungan asosiatif suatu kombinasi item. Algoritma apriori adalah algoritma pengambilan data dengan aturan asosiatif (Association rule)untuk menentukan hubungan asosiatif suatu kombinasi item (Kusrini 2009). Association Rule yang dimaksud dilakukan melalui mekanisme penghitungan support dan confidence dari suatu hubungan item. Sebuah rule asosiasi dikatakan interesting jika nilai support adalah lebih besar dari minimum support dan juga nilai confidence adalah lebih besar dari minimum confidence. Algoritma apriori ini akan cocok untuk iterapkan bila terdapat beberapa hubungan item yang ingin dianalisa. Salah satunya yang bisa diterapkan adalah di dalam bidang promosi dan penentuan strategi pemasaran.

1.3.3. Bayesian Classification

Klasifikasi Bayesian [lihat Naïve Bayes Classifier] didasarkan pada Teorema Bayes ini. Pengklasifikasi Bayesian adalah pengklasifikasi statistik. Classifier Bayesian mampu memprediksi probabilitas keanggotaan kelas seperti probabilitas bahwa tupel diberikan milik kelas tertentu. Pengantar Klasifikasi Bayesian didasarkan pada Bayes Teorema. Pengklasifikasi Bayesian adalah pengklasifikasi statistik. Classifier Bayesian mampu memprediksi probabilitas keanggotaan kelas seperti probabilitas bahwa tupel diberikan milik kelas tertentu. Dalam klasifikasi statistik classifier Bayes meminimalkan kemungkinan kesalahan klasifikasi.

This document using Dynamic Content Technology for enrichment sample case and reading experience
  • Data yang digunakan BUKAN merupakan data real, tapi data yang digenerate secara otomatis/random/acak dari sistem
  • Data dan Nilai Perhitungan yang ditampilkan akan SELALU BERBEDA jika halaman di refresh/reload
  • Jumlah Data Alternatif yang diperhitungkan ditentukan secara acak/random antara 5 s.d 10

2.1. Pemilihan Data

2.2. Pre-proses/Pembersihan Data

2.3. Transformasi

2.4. Data Mining

2.5. Evaluasi

3.1. Persiapan Database

Sebagai bahan pembelajaran Algoritma k-NN ini; dibuat database (dalam hal ini menggunakan MySQL/MariaDB Database server) sebagai berikut:

CREATE DATABASE IF NOT EXISTS db_dm;
USE db_dm;

Awalnya membuat dulu database dengan nama db_dm jika belum ada database dengan nama tersebut, kemudian gunakan database tersebut dengan memakai sintak USE db_dm;

Dalam hal ini, pembuatan database memakai command console dari database server yang bersangkutan

Sebelum dilakukan perhitungan-perhitungan menggunakan algoritma k-Nearest Neaighbors dengan menggunakan PHP, maka terlebih dahulu kita menyiapkan data yang akan diolah dengan mengambil (fetching) data dari database, dan disimpan (assign) ke dalam variabel-variabel PHP.

3.2.1. Koneksi ke Database

Sebelum melalukan operasi dengan data dari database, perlu dibuat script untuk koneksi ke database terlebih dahulu. Dari database yang sudah dibuat, kita bisa membuat script php untuk membuat koneksi ke database server dengan extension mysqli sebagai berikut:

<?php
//-- konfigurasi database
$dbhost 'localhost';
$dbuser 'root';
$dbpass '';
$dbname 'db_dm';
//-- koneksi ke database server dengan extension mysqli
$db = new mysqli($dbhost,$dbuser,$dbpass,$dbname);
//-- hentikan program dan tampilkan pesan kesalahan jika koneksi gagal
if ($db->connect_error) {
    die(
'Connect Error ('.$db->connect_errno.')'.$db->connect_error);
}
?>;

Sesuaikan nilai-nilai $dbhost,$dbuser,$dbpass dan $dbname dengan konfigurasi database yg digunakan.