K-Nearest Neighbors
- Diperkenalkan oleh
- Cover, T.M. & Hart, P.E.
- Tahun
- 1967
- Jenis
- Instance-based (non-parametric) learning
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
K-Nearest Neighbors (KNN), yang diformalkan oleh Cover dan Hart pada tahun 1967, adalah metode non-parametrik berbasis instans yang mengklasifikasikan atau memprediksi observasi baru dengan melihat k contoh terdekat dalam data pelatihan.
Untuk klasifikasi, ia mengambil suara mayoritas di antara tetangga-tetangga tersebut; untuk regresi, ia merata-ratakan nilai mereka.
Intuisi di balik metode
Idenya sederhana: input yang serupa cenderung memiliki output yang serupa. Untuk memberi label pada titik baru, KNN menemukan segelintir contoh pelatihan yang paling dekat dengannya dalam ruang fitur dan membiarkan mereka memutuskan. Tidak ada persamaan yang dipasang sebelumnya — data pelatihan itu sendiri adalah modelnya, dan prediksi dibuat hanya ketika titik baru tiba.
Sejarah
Klasifikasi pola tetangga terdekat diberikan pijakan statistik formalnya oleh Thomas Cover dan Peter Hart dalam makalah mereka tahun 1967 di IEEE Transactions on Information Theory, yang menganalisis tingkat kesalahan aturan tetangga terdekat. KNN menjadi salah satu metode pembelajaran berbasis instans paling awal dan paling bertahan lama dan tetap menjadi pengklasifikasi dasar standar.
Kapan digunakan
Gunakan KNN untuk klasifikasi atau prediksi pada data tabular dengan fitur kontinu, biner, atau ordinal dan setidaknya sekitar 30 observasi. Ia tidak mengasumsikan distribusi tertentu, tetapi ia mensyaratkan bahwa fitur dinormalisasi dan jumlah fitur tetap kecil relatif terhadap ukuran sampel (p jauh lebih kecil dari n lebih disukai). Dalam sampel kecil atau berdimensi tinggi, kutukan dimensionalitas mendominasi — jarak tetangga menjadi tidak informatif — dan model parametrik seperti regresi logistik atau Naive Bayes adalah pilihan yang lebih baik.
Batasan dan pertimbangan
- Peka terhadap penskalaan fitur; tanpa standardisasi, fitur berskala besar mendominasi jarak.
- Menurun dengan cepat dalam dimensi tinggi (kutukan dimensionalitas), di mana jarak tetangga kehilangan makna.
- Setiap prediksi memerlukan pemindaian seluruh set pelatihan, yang lambat pada waktu prediksi pada data besar.
- Membutuhkan setidaknya ukuran sampel sedang; dalam sampel kecil, jarak tetangga terdekat tidak bermakna.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Secara konseptual sederhana dan mudah dijelaskan: tidak ada persamaan waktu pelatihan, data adalah modelnya.
- Non-parametrik — tidak membuat asumsi tentang distribusi yang mendasarinya.
- Secara alami menangani masalah multi-kelas dan batas keputusan nonlinier yang kompleks.
- Bekerja untuk klasifikasi dan regresi dengan ide dasar yang sama.
Penerapan
- Klasifikasi data tabular ke dalam dua kategori atau lebih.
- Prediksi numerik (regresi) dengan merata-ratakan contoh terdekat.
- Dasar yang sederhana dan dapat diinterpretasikan sebelum mencoba model yang lebih kompleks.
- Pengenalan pola di mana kesamaan dengan contoh yang diketahui mendorong keputusan.
Cara kerjanya
Cara kerjanya
Untuk observasi baru, KNN mengukur seberapa jauh jaraknya dari setiap contoh pelatihan, biasanya menggunakan jarak Euclidean di seluruh fitur. Karena jarak peka terhadap skala, fitur harus distandardisasi terlebih dahulu — jika tidak, variabel yang diukur pada skala numerik besar akan mendominasi perhitungan dan mendistorsi tetangga mana yang dianggap terdekat.
Rumus
d(x, x_i) = \sqrt{\sum_{j=1}^{p}(x_j - x_{ij})^2}k titik pelatihan dengan jarak terkecil ke observasi baru dipilih sebagai tetangganya. Nilai k mengontrol seberapa lokal keputusannya: k kecil mengikuti data dengan cermat tetapi peka terhadap kebisingan, sementara k yang lebih besar menghaluskan batas. k harus dipilih melalui validasi silang (misalnya, metode siku) daripada ditebak.
Tetangga memutuskan prediksi: untuk klasifikasi, titik baru mengambil kelas yang paling umum di antara k tetangganya (suara mayoritas), dan untuk regresi, ia mengambil rata-rata nilai mereka. Hal ini membuat metode mudah dipahami, tetapi setiap prediksi memerlukan pemindaian set pelatihan.
Rumus
\hat{y} = \text{mode/mean of the } k \text{ nearest neighbors}Kesalahan umum
- Melewatkan standardisasi fitur, sehingga satu variabel berskala besar secara diam-diam mengontrol jarak.
- Memilih k secara manual daripada memilihnya dengan validasi silang.
- Menerapkan KNN dengan banyak fitur dan sedikit observasi, di mana rasio dimensi/sampel merusaknya.
- Melaporkan hanya akurasi daripada presisi, recall, F1, dan matriks kebingungan.
Pertanyaan yang sering diajukan
Bagaimana cara memilih nilai k?
k harus dipilih dengan validasi silang daripada ditebak — misalnya dengan mencoba berbagai nilai dan menggunakan metode siku untuk menemukan di mana kesalahan berhenti membaik. k kecil mengikuti data dengan cermat tetapi peka terhadap kebisingan, sementara k yang lebih besar menghaluskan batas keputusan.
Mengapa saya harus menstandardisasi fitur?
KNN memutuskan siapa yang 'terdekat' menggunakan jarak, yang peka terhadap skala. Jika satu fitur memiliki skala numerik yang jauh lebih besar daripada yang lain, ia mendominasi jarak dan mendistorsi set tetangga. Menstandardisasi fitur (misalnya dengan StandardScaler) diperlukan agar setiap fitur berkontribusi secara adil.
Mengapa KNN kesulitan dengan banyak fitur?
Dalam ruang berdimensi tinggi, semua titik menjadi berjarak kira-kira sama — kutukan dimensionalitas — sehingga tetangga 'terdekat' tidak lagi bermakna dekat. Kinerja KNN menurun dengan cepat, dan model parametrik seperti Naive Bayes atau regresi logistik biasanya lebih disukai. Menjaga p jauh lebih kecil dari n membantu.
Apakah ada langkah pelatihan?
Tidak dalam arti biasa. KNN berbasis instans (malas): ia hanya menyimpan data pelatihan dan melakukan semua pekerjaan pada waktu prediksi, ketika ia menghitung jarak untuk menemukan tetangga terdekat dari titik baru.
Metode terkait
Sumber
Cover, T.M. & Hart, P.E. (1967). Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), 21–27.
Buka referensi DOIDisalin.