diklatkerja | Memahami Algoritma K-Nearest Neighbor (K-NN)

Dalam statistik, algoritma k-nearest neighbours (k-NN) adalah metode pembelajaran terawasi non-parametrik yang awalnya dirancang oleh Evelyn Fix dan Joseph Hodges pada tahun 1951, kemudian diperluas oleh Thomas Cover. Ini melayani tujuan dalam tugas klasifikasi dan regresi, dengan mengandalkan k contoh pelatihan terdekat dari kumpulan data untuk komputasi. Hasilnya bervariasi tergantung pada apakah k-NN digunakan untuk klasifikasi atau regresi:

Dalam klasifikasi k-NN, algoritma menentukan keanggotaan kelas. Setiap objek diklasifikasikan berdasarkan suara mayoritas di antara k tetangga terdekatnya, dan objek tersebut ditugaskan ke kelas yang paling umum dalam kumpulan ini. Biasanya, k adalah bilangan bulat positif, sering kali dibuat kecil. Ketika k sama dengan 1, objek tersebut ditugaskan ke kelas tetangga terdekatnya.
Sebaliknya pada regresi k-NN, hasilnya adalah nilai properti objek. Nilai ini dihitung sebagai rata-rata nilai properti k tetangga terdekat. Sekali lagi, ketika k sama dengan 1, hasilnya langsung diberi nilai tetangga terdekatnya.

k-NN dicirikan sebagai pendekatan klasifikasi di mana perkiraan fungsi hanya terjadi secara lokal, dengan semua komputasi ditangguhkan pada evaluasi fungsi. Khususnya, ketika fitur mewakili unit fisik yang berbeda atau mencakup skala yang berbeda, normalisasi data pelatihan akan meningkatkan akurasi algoritme secara signifikan.

Baik dalam tugas klasifikasi maupun regresi, peningkatan umum melibatkan pemberian bobot pada kontribusi lingkungan. Pembobotan tersebut memprioritaskan pengaruh tetangga terdekat pada rata-rata yang dihitung, sering kali menggunakan sistem di mana setiap tetangga diberi bobot berbanding terbalik dengan jaraknya dari objek yang diteliti.

Khususnya, tetangga diambil dari objek dengan kelas yang diketahui (dalam klasifikasi k-NN) atau nilai fitur objek (dalam regresi k-NN), yang secara efektif merupakan kumpulan pelatihan algoritme, meskipun tanpa memerlukan langkah pelatihan yang berbeda. Ciri khas algoritma k-NN terletak pada sensitivitasnya terhadap struktur lokal data

Pengaturan statistik

Misalkan kita mempunyai pasangan $(X_{1},Y_{1}),(X_{2},Y_{2}),\dots ,(X_{n},Y_{n})$ mengambil nilai-nilai in $\mathbb {R} ^{d}\times \{1,2\}$ , dimana Y adalah label kelas dari X, sehingga $X|Y=r\sim P_{r}$ untuk $r=1,2$ (dan distribusi probabilitas $P_{r}$ ).Mengingat beberapa norma $\|\cdot \|$ dalam $\mathbb {R} ^{d}$ dan poin �∈�� $x\in \mathbb {R} ^{d}$ , let $(X_{(1)},Y_{(1)}),\dots ,(X_{(n)},Y_{(n)})$ menjadi menyusun ulang data pelatihan sedemikian rupa $\|X_{(1)}-x\|\leq \dots \leq \|X_{(n)}-x\|$ .

Algoritma k-Nearest Neighbors

Algoritme k-Nearest Neighbors (k-NN), yang merupakan pendukung dalam bidang pembelajaran mesin, menawarkan solusi serbaguna untuk tugas klasifikasi. Kesederhanaannya memungkiri keefektifannya, menjadikannya pilihan populer di berbagai domain.

Fase Pelatihan dan Klasifikasi:

Pada fase pelatihan, algoritme hanya menyimpan vektor fitur dan label kelas dari sampel pelatihan. Pada tahap klasifikasi, konstanta k yang ditentukan pengguna mulai berlaku. Vektor tak berlabel, atau titik kueri, diklasifikasikan dengan memberi label paling umum di antara k sampel pelatihan terdekat.

Memilih Metrik Jarak yang Tepat:

Pilihan metrik jarak memainkan peran penting dalam kinerja algoritma. Untuk variabel kontinu, jarak Euclidean adalah yang utama, sedangkan untuk variabel diskrit seperti klasifikasi teks, metrik alternatif seperti metrik tumpang tindih atau jarak Hamming ikut berperan. Dalam domain khusus seperti analisis data microarray ekspresi gen, koefisien korelasi seperti Pearson dan Spearman berfungsi sebagai metrik yang tepat.

Mengatasi Distribusi Kelas yang Miring:

Tantangan muncul ketika distribusi kelas tidak seimbang, sehingga menghasilkan prediksi yang bias dan lebih memilih kelas yang lebih sering digunakan. Untuk memitigasi hal ini, pembobotan klasifikasi berdasarkan jarak dari titik pengujian ke k tetangga terdekatnya terbukti efektif. Alternatifnya, abstraksi dalam representasi data, seperti yang terlihat pada peta yang dapat diatur sendiri (SOM), dapat mengurangi kesenjangan dengan mengelompokkan titik-titik serupa tanpa memandang kepadatannya.

Pemilihan parameter

Pemilihan Parameter dan Penskalaan Fitur:

Pemilihan nilai k optimal bergantung pada data yang ada. Nilai k yang lebih besar mengurangi kebisingan tetapi mengaburkan batasan kelas. Teknik heuristik membantu dalam memilih k yang sesuai. Selain itu, keakuratan algoritme rentan terhadap fitur yang berisik atau tidak relevan serta skala fitur yang tidak konsisten. Teknik penskalaan fitur, seperti algoritme evolusioner atau penskalaan berbasis informasi timbal balik, dapat membantu dan memastikan hasil klasifikasi yang kuat.

Klasifikasi Biner dan Optimasi Empiris:

Dalam klasifikasi biner, memilih k ganjil mencegah suara terikat, sehingga meningkatkan akurasi klasifikasi. Teknik optimasi empiris, seperti metode bootstrap, membantu dalam memilih k optimal untuk tugas yang ada.

Algoritma K-Nearest Neighbor Klasifikasi

K-Nearest Neighbor (K-NN) adalah algoritma klasifikasi sederhana namun powerful dalam pembelajaran mesin. Ide dasarnya adalah mengklasifikasikan data baru berdasarkan kemiripannya dengan data pelatihan yang telah berlabel. Berikut adalah penjelasan lebih detailnya:

K-NN bekerja dengan menghitung jarak antara data baru dengan seluruh data pelatihan. Kemudian, algoritma ini mengambil K tetangga terdekat berdasarkan jarak tersebut. Label data baru ditentukan berdasarkan mayoritas label dari K tetangga terdekat. Semakin besar nilai K, semakin halus keputusan batasnya, tetapi dapat meningkatkan bias. Sebaliknya, nilai K yang kecil dapat menyebabkan model terlalu sensitif terhadap noise.

Salah satu keunggulan K-NN adalah kesederhanaan implementasinya. Namun, kekurangannya adalah kebutuhan komputasi yang tinggi ketika dataset sangat besar. Untuk mengatasi ini, kita dapat menggunakan algoritma pencarian tetangga terdekat aproksimasi.

K-NN juga memiliki beberapa properti menarik. Sebagai contoh, ketika jumlah data pelatihan mendekati tak hingga, error rate dari klasifikasi dua kelas dengan K-NN dijamin tidak lebih dari dua kali Bayes error rate (error minimum yang dapat dicapai). Selain itu, K-NN dapat dianggap sebagai kasus khusus dari estimator kernel densitas dengan kernel seragam.

Untuk meningkatkan performa K-NN, kita dapat melakukan pembelajaran metrik dan ekstraksi fitur. Pembelajaran metrik digunakan untuk mempelajari metrik baru yang lebih sesuai dengan data. Sementara ekstraksi fitur bertujuan untuk mereduksi dimensi data masukan sehingga mengurangi efek kutukan dimensi tinggi.

Secara keseluruhan, K-NN adalah algoritma klasifikasi yang sederhana namun kuat. Dengan penyesuaian yang tepat seperti pemilihan nilai K, pembelajaran metrik, dan ekstraksi fitur, K-NN dapat memberikan performa yang sangat baik dalam banyak kasus.

Memahami Regresi k-NN dan Deteksi Pencilan

Dalam k-NN regression, algoritma k-NN digunakan untuk memperkirakan variabel kontinu. Salah satu algoritma tersebut menggunakan rata-rata terbobot dari k tetangga terdekat, dengan bobot yang berbanding terbalik dengan jarak mereka. Langkah-langkahnya adalah sebagai berikut:

Hitung jarak Euclidean atau Mahalanobis dari contoh query ke contoh yang telah dilabeli.
Urutkan contoh yang telah dilabeli berdasarkan jarak yang meningkat.
Temukan jumlah tetangga terdekat yang optimal secara heuristik, berdasarkan RMSE. Ini dilakukan menggunakan validasi silang.
Hitung rata-rata terbobot invers dari k-tetangga multivariat terdekat.

Dalam konteks deteksi outlier, jarak ke tetangga terdekat ke-k juga dapat dianggap sebagai estimasi kepadatan lokal dan menjadi skor outlier yang populer. Semakin besar jarak ke tetangga ke-k, semakin rendah kepadatan lokalnya, dan semakin mungkin titik query adalah outlier. Meskipun sederhana, model outlier ini, bersama dengan metode penambangan data klasik lainnya, faktor outlier lokal, terbukti efektif dalam perbandingan dengan pendekatan yang lebih baru dan kompleks, menurut analisis eksperimental berskala besar.

Disadur dari: id.wikipedia.org/en.wikipedia.org