Skip to content
Kembali ke hasil pencarian

Pembelajaran Aktif K-Nearest Neighbors

Diperkenalkan oleh
Settles, B. (active learning framework); Fix & Hodges (KNN base)
Tahun
1951–2010
Jenis
Active learning with KNN base learner
Keluarga
Machine learning

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Pembelajaran aktif dengan K-nearest neighbors menggabungkan prediksi berbasis instans KNN dengan strategi kueri iteratif yang memilih contoh tak berlabel yang paling informatif untuk anotasi.

Model meminta label hanya untuk instans di mana margin pemungutan suara lingkungan terdekat paling sempit, mencapai akurasi yang kompetitif dengan contoh berlabel yang jauh lebih sedikit daripada KNN yang sepenuhnya diawasi pada data tabular.

Intuisi di balik metode

KNN mengklasifikasikan sebuah titik dengan melihat k tetangga berlabel terdekatnya dan melakukan pemungutan suara mayoritas. Ketika tetangga-tetangga tersebut hampir terbagi rata antara kelas-kelas, model benar-benar tidak yakin — dan ketidakpastian itu menunjukkan contoh tak berlabel mana yang paling berharga untuk diberi label. Pembelajaran aktif memanfaatkan sinyal ini: pada setiap iterasi, algoritma menemukan titik tak berlabel yang lingkungannya paling terbagi rata, meminta sebuah oracle untuk memberi label, menambahkannya ke kumpulan berlabel, dan mengulanginya. Hasilnya adalah upaya pelabelan terkonsentrasi di dekat batas keputusan, di mana label baru paling banyak mengajarkan.

Sejarah

Klasifikasi K-nearest neighbors berasal dari Fix dan Hodges (1951) dan diformalkan oleh Cover dan Hart (1967). Pembelajaran aktif sebagai kerangka kerja yang berprinsip secara sistematis disurvei oleh Burr Settles (2010), yang mendokumentasikan pengambilan sampel ketidakpastian berbasis kumpulan, kueri-berdasarkan-komite, dan strategi berbobot kepadatan. KNN telah ditampilkan sebagai pembelajar dasar dalam tolok ukur pembelajaran aktif berbasis kumpulan sejak setidaknya karya dasar Cohn, Atlas, dan Ladner (1994), dihargai karena sinyal ketidakpastiannya yang transparan dan biaya pelatihan ulang nol per iterasi.

Kapan digunakan

Gunakan pembelajaran aktif dengan KNN ketika data berlabel langka atau mahal untuk diperoleh, instans tak berlabel melimpah, ruang fitur berdimensi sedang, dan batas keputusan diharapkan mulus secara lokal. Ini sangat praktis dalam proyek klasifikasi tahap awal di mana pelabelan harus dihemat. Hindari ketika dataset berdimensi sangat tinggi (metrik jarak KNN menurun dalam dimensi tinggi, kutukan dimensionalitas), ketika kumpulan berlabel sudah besar (KNN pasif sudah cukup), ketika prediksi latensi rendah diperlukan dalam skala besar (prediksi KNN adalah O(n) dalam kumpulan berlabel), atau ketika anggaran label sangat kecil sehingga perkiraan lingkungan tidak dapat diandalkan.

Batasan dan pertimbangan

  • Biaya prediksi berskala linier dengan ukuran set berlabel, membuat inferensi lambat seiring bertambahnya kumpulan melalui iterasi.
  • Ketidakpastian berbasis jarak menurun tajam dalam ruang berdimensi tinggi karena kutukan dimensionalitas.
  • Batas atas akurasi KNN berada di bawah metode ensemble; strategi aktif tidak dapat mengkompensasi kapasitas terbatas pembelajar dasar.
  • Sensitif terhadap pilihan k dan metrik jarak; default yang buruk mengarah pada estimasi ketidakpastian yang tidak dapat diandalkan.
  • Semua titik berlabel disimpan dalam memori; anggaran besar menghasilkan konsumsi memori tinggi.

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Non-parametrik dan bebas asumsi: tidak ada asumsi distribusi tentang data yang diperlukan.
  • Estimasi ketidakpastian alami dan dapat diinterpretasikan — ini secara langsung mencerminkan pembagian suara di antara tetangga terdekat.
  • Pembelajaran malas berarti tidak ada biaya pelatihan ulang per iterasi; set berlabel yang diperluas adalah model yang diperbarui.
  • Efektif dalam mengkonsentrasikan label di dekat batas keputusan, menghasilkan resolusi batas yang baik dengan sedikit anotasi.
  • Bekerja dengan baik pada data tabular berdimensi sedang dengan fitur kontinu dan biner.

Penerapan

  • Anotasi catatan medis atau gambar di mana waktu pelabelan ahli terbatas dan batas keputusan mulus secara lokal.
  • Klasifikasi teks atau dokumen dengan korpus berlabel kecil dan dokumen tak berlabel yang melimpah menggunakan jarak berbasis embedding.
  • Tugas deteksi kesalahan sensor dan industri di mana hanya sebagian peristiwa yang dapat diverifikasi secara manual.
  • Tugas survei ekologi di mana konfirmasi lapangan label spesies mahal dan terlokalisasi secara lokal.
  • Prototipe klasifikasi tahap awal sebelum beralih ke model berkapasitas lebih tinggi setelah label yang cukup dikumpulkan.

Cara kerjanya

Cara kerjanya

1

Kumpulan kecil instans berlabel awal dikumpulkan untuk memulai proses, bersama dengan kumpulan instans tak berlabel yang lebih besar. Seleksi acak bertingkat direkomendasikan untuk memastikan setidaknya satu contoh per kelas ada, memberikan KNN lingkungan awal yang bermakna sebelum loop aktif dimulai.

2

Klasifikasi KNN dipasang pada set berlabel saat ini menggunakan metrik k dan jarak yang dipilih (umumnya Euclidean atau kosinus). Karena KNN malas dan menyimpan semua titik pelatihan, pemasangan instan, tetapi biaya prediksi berskala linier dengan ukuran set berlabel — pertimbangan yang relevan karena kumpulan tumbuh melalui iterasi.

3

Setiap instans tak berlabel diberi skor berdasarkan kriteria informativitas. Pengambilan sampel margin menghitung celah antara pangsa suara dua kelas teratas di seluruh k tetangga; pengambilan sampel entropi menghitung H(y-hat | x) atas semua proporsi kelas. Instans dengan margin terkecil atau entropi tertinggi dikueri: x* = argmax H(y-hat | x).

Rumus
x^* = \arg\max_{x \in U} H(\hat{y} \mid x)
4

Instans yang dikueri dikirim ke oracle — anotator manusia atau mekanisme pelabelan otomatis — untuk label sejatinya. Label ditambahkan ke set pelatihan dan instans dihapus dari kumpulan tak berlabel. Keandalan anotator harus dipantau, karena label yang berisik menurunkan kinerja KNN secara tajam di dekat batas.

5

Karena KNN adalah pembelajar malas, tidak diperlukan pelatihan ulang eksplisit; set berlabel yang diperluas segera merupakan model baru. Siklus kueri-skor-label berulang sampai anggaran pelabelan habis, ambang batas akurasi validasi tercapai, atau jumlah iterasi maksimum tercapai. Kinerja akhir dilaporkan pada set uji independen yang ditahan.

Kesalahan umum

  • Kegagalan menormalisasi fitur sebelum menghitung jarak, menyebabkan fitur dengan magnitudo tinggi mendominasi lingkungan.
  • Menggunakan set pengujian untuk memandu atau mengevaluasi pemilihan kueri, yang merupakan kebocoran data.
  • Menetapkan k terlalu kecil (k=1) di dekat batas keputusan, menghasilkan skor ketidakpastian yang sangat bervariasi yang tidak mencerminkan ambiguitas sebenarnya.
  • Mengabaikan ketidakseimbangan kelas dalam set benih, yang membiaskan kueri awal ke arah batas kelas mayoritas.
  • Memperlakukan akurasi pembelajaran aktif sebagai setara dengan baseline yang diawasi sepenuhnya tanpa melaporkan jumlah label yang digunakan.

Pertanyaan yang sering diajukan

Mengapa menggunakan KNN daripada model yang lebih kuat sebagai pembelajar dasar pembelajaran aktif?

Ketidakpastian pembagian suara KNN murah untuk dihitung dan tidak memerlukan pelatihan ulang — menambahkan titik berlabel baru segera memperbarui model. Ini membuatnya menarik ketika biaya komputasi per iterasi penting. Untuk akurasi maksimum pada anggaran label tetap, pembelajar dasar ensemble seperti random forest atau gradient boosting biasanya mengungguli KNN.

Bagaimana cara memilih k untuk pembelajaran aktif?

Rentang awal yang umum adalah k = 5 hingga 15. Nilai k yang lebih kecil menghasilkan estimasi ketidakpastian yang lebih berisik; nilai k yang lebih besar menghaluskan batas tetapi mungkin melewatkan ambiguitas yang terperinci. Lakukan validasi silang k pada set benih berlabel awal dan sesuaikan seiring bertambahnya kumpulan berlabel.

Apakah penskalaan fitur penting?

Ya, sangat penting. Jarak KNN didominasi oleh fitur magnitudo tinggi jika fitur tidak dinormalisasi. Selalu terapkan penskalaan min-max atau standardisasi z-score sebelum menghitung jarak dan skor ketidakpastian.

Berapa banyak contoh berlabel awal yang dibutuhkan?

Minimal, satu atau dua instans berlabel per kelas diperlukan agar KNN dapat membentuk lingkungan untuk semua kelas. Dalam praktiknya, 5–20 instans berlabel memberikan estimasi ketidakpastian awal yang lebih stabil; lebih sedikit berisiko lingkungan yang degeneratif yang menghasilkan kueri awal yang tidak informatif.

Kapan saya harus menghentikan loop aktif?

Tetapkan anggaran pelabelan terlebih dahulu, atau pantau akurasi validasi dan berhenti ketika peningkatan per label baru jatuh di bawah ambang batas yang bermakna. Jangan pernah menggunakan set pengujian sebagai sinyal penghentian, karena ini membocorkan informasi ke dalam proses kueri.

Metode terkait

Sumber

  1. Settles, B. (2010). Active Learning Literature Survey. Computer Sciences Technical Report 1648, University of Wisconsin-Madison.

    Buka referensi publikasi
    Disalin.
  2. Zhu, X., Lafferty, J., & Ghahramani, Z. (2003). Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions. Proceedings of the ICML 2003 Workshop on the Continuum from Labeled to Unlabeled Data, 58–65.

    Buka referensi publikasi
    Disalin.