K-Nearest Neighbors Semi-Terawasi
- Diperkenalkan oleh
- Zhu, X. & Ghahramani, Z. (label propagation); Cover, T. & Hart, P. (KNN base)
- Tahun
- 2002 (semi-supervised extension); 1967 (KNN base)
- Jenis
- Semi-supervised classifier / label propagation
- Keluarga
- Machine learning
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
KNN Semi-Terawasi memperluas algoritma K-nearest neighbors klasik untuk memanfaatkan kumpulan data besar yang tidak berlabel bersama dengan sejumlah kecil data berlabel.
Dengan membangun graf KNN di atas semua observasi dan menyebarkan label yang diketahui melalui sisi-sisi graf, metode ini menyimpulkan label untuk titik-titik yang tidak berlabel tanpa memerlukan anotasi manual yang mahal untuk setiap sampel.
Intuisi di balik metode
Bayangkan sebuah ruang kelas di mana hanya segelintir siswa yang memiliki kartu nama dan sisanya anonim. KNN standar hanya dapat mengklasifikasikan siswa anonim dengan melihat segelintir tetangga yang diberi label di dekatnya. Sebaliknya, KNN Semi-Terawasi memetakan seluruh ruangan sebagai jaringan — setiap siswa terhubung ke tetangga terdekatnya — dan menyebarkan label dari siswa yang diberi label seperti tinta yang menyebar melalui kertas basah. Karena jaringan menangkap struktur data secara keseluruhan, label mencapai titik-titik yang tidak berlabel dengan cara yang terprinsip yang menghormati geometri yang mendasarinya daripada mengabaikan mayoritas yang tidak berlabel.
Sejarah
Propagasi label pada graf KNN disistematisasi oleh Zhu dan Ghahramani pada tahun 2002, berdasarkan SVM transductive Vapnik dan ide-ide difusi berbasis graf sebelumnya. Kerangka kerja ini dikonsolidasikan dalam volume Semi-Supervised Learning (Chapelle et al., 2006) dari MIT Press, yang tetap menjadi referensi standar. Pustaka KNN perkiraan yang dapat diskalakan (FAISS, Annoy) kemudian membuat pendekatan ini praktis pada jutaan titik, dan terus digunakan sebagai baseline yang kuat untuk klasifikasi gambar dan teks semi-terawasi.
Kapan digunakan
Gunakan KNN Semi-Terawasi ketika Anda memiliki sejumlah kecil data berlabel dan kumpulan data besar yang tidak berlabel dari distribusi yang sama, data berada dalam ruang berdimensi relatif rendah (kurang dari sekitar 50 fitur), dan Anda percaya bahwa titik-titik tetangga berbagi kelas yang sama. Metode ini sangat cocok untuk klasifikasi tambalan gambar, kategorisasi teks dengan anotasi yang jarang, dan tugas penyaringan medis di mana pelabelan ahli mahal. Hindari jika data berlabel dan tidak berlabel berasal dari distribusi yang berbeda (pergeseran kovariat), ruang fitur berdimensi sangat tinggi (graf KNN menjadi tidak dapat diandalkan), kumpulan data cukup kecil sehingga KNN yang sepenuhnya terawasi sudah memadai, atau batas kelas tidak sejajar dengan struktur kepadatan lokal data.
Batasan dan pertimbangan
- Konstruksi graf berskala kuadratik dengan ukuran kumpulan data kecuali metode tetangga terdekat perkiraan digunakan.
- Kinerja menurun tajam di ruang berdimensi tinggi di mana metrik jarak kehilangan kekuatan diskriminatif.
- Mengasumsikan data berlabel dan tidak berlabel diambil dari distribusi yang sama; pergeseran kovariat merusak metode.
- Memerlukan penyetelan yang cermat terhadap k, bandwidth sisi graf, dan parameter pencampuran propagasi.
- Propagasi label dapat memperkuat kesalahan pelabelan awal di sebagian besar graf.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Memanfaatkan data tidak berlabel yang murah untuk meningkatkan akurasi melebihi apa yang mungkin dicapai hanya dengan set data berlabel.
- Tidak ada asumsi model parametrik: hanya bergantung pada geometri lingkungan sekitar.
- Secara alami menangani masalah multi-kelas tanpa modifikasi.
- Konstruksi graf KNN transparan dan mudah diperiksa.
- Bekerja dengan baik ketika kelas membentuk kluster yang padat dan terpisah dengan baik dalam ruang fitur.
Penerapan
- Klasifikasi gambar dengan sejumlah kecil gambar berlabel dan korpus besar yang tidak berlabel.
- Kategorisasi teks dan dokumen di mana pelabelan manual mahal.
- Klasifikasi catatan medis atau slide patologi dengan anotasi ahli terbatas.
- Deteksi penipuan ketika hanya sejumlah kecil kasus penipuan yang dikonfirmasi tersedia.
- Pelabelan data sensor di lingkungan IoT industri dengan peristiwa kebenaran dasar yang jarang.
Cara kerjanya
Cara kerjanya
Sebuah graf dibangun di atas semua observasi — baik yang berlabel maupun yang tidak berlabel. Setiap node sesuai dengan satu titik data, dan sisi terarah atau tidak terarah menghubungkan setiap node ke k tetangga terdekatnya dalam ruang fitur. Pilihan k mengontrol seberapa lokal atau global label akan disebarkan: k kecil menjaga propagasi tetap ketat; k besar memungkinkan label melompati celah yang lebih besar.
Bobot sisi menangkap kekuatan kesamaan antara node yang terhubung, biasanya melalui kernel Gaussian (RBF) yang diterapkan pada jarak Euclidean antara vektor fitur. Parameter bandwidth sigma mengontrol seberapa cepat kesamaan menurun seiring jarak. Sisi yang lebih kuat membawa label lebih mudah selama propagasi.
Rumus
w_{ij} = \exp(-\|x_i - x_j\|^2 / \sigma^2)Label disebarkan secara iteratif dari node berlabel ke tetangga yang tidak berlabel. Pada setiap iterasi, setiap node memperbarui distribusi label lunaknya sebagai kombinasi berbobot dari distribusi tetangganya saat ini dan label awalnya sendiri (jika berlabel). Parameter pencampuran alpha menyeimbangkan pengaruh struktur graf versus label keras, dan iterasi berlanjut hingga distribusi konvergen.
Rumus
F \leftarrow \alpha W D^{-1} F + (1-\alpha) YSetelah propagasi konvergen, setiap node yang tidak berlabel ditugaskan kelas dengan skor label lunak tertinggi dalam distribusi konvergennya. Node berlabel dijepit ke label sebenarnya mereka sepanjang waktu, sehingga label yang diketahui tidak pernah ditimpa.
Rumus
\hat{y}_i = \arg\max_c F_{ic}Kesalahan umum
- Konstruksi graf KNN tanpa menormalkan fitur, menyebabkan fitur dengan varians tinggi mendominasi perhitungan jarak.
- Menetapkan k terlalu besar, yang menghaluskan batas kelas yang sebenarnya dan menghasilkan distribusi label yang terlalu halus.
- Mengabaikan kemungkinan bahwa data tidak berlabel berada di luar distribusi relatif terhadap set data berlabel.
- Melaporkan akurasi pada node yang tidak berlabel seolah-olah itu adalah perkiraan set pengujian yang tidak bias — node yang tidak berlabel bocor ke dalam graf selama pelatihan.
- Melewatkan pemeriksaan konvergensi dan menggunakan jumlah iterasi propagasi yang tetap dan sewenang-wenang.
Pertanyaan yang sering diajukan
Bagaimana cara memilih k?
Mulai dengan k dalam kisaran 5-15 dan setel berdasarkan akurasi validasi berlabel yang ditahan. k yang lebih kecil memberikan batas yang lebih tajam dan lebih lokal; k yang lebih besar memungkinkan label menyebar lebih jauh tetapi berisiko melintasi batas kelas yang sebenarnya.
Bisakah saya mengevaluasi metode ini secara jujur ketika sebagian besar data tidak berlabel?
Tahan set pengujian berlabel khusus yang tidak pernah ditambahkan ke graf. Node dalam graf — bahkan yang tidak berlabel — adalah bagian dari pelatihan, jadi node berlabel apa pun yang berpartisipasi dalam konstruksi graf tidak boleh juga berfungsi sebagai titik pengujian.
Bagaimana jika kumpulan data saya terlalu besar untuk membangun graf KNN penuh?
Gunakan pustaka tetangga terdekat perkiraan seperti FAISS atau Annoy untuk membangun graf dalam O(n log n) daripada O(n^2), lalu terapkan propagasi label pada graf perkiraan yang jarang.
Apakah KNN Semi-Terawasi selalu mengungguli KNN Terawasi?
Belum tentu. Jika data yang tidak berlabel berada di luar distribusi atau ruang fitur berdimensi sangat tinggi, grafnya berisik dan propagasi dapat merusak kinerja. Selalu bandingkan dengan baseline KNN terawasi sebelum mengklaim manfaat dari data yang tidak berlabel.
Apakah ini sama dengan penyebaran label atau propagasi label di scikit-learn?
Sangat terkait. LabelPropagation dan LabelSpreading di scikit-learn mengimplementasikan kerangka kerja Zhu dan Ghahramani menggunakan graf kernel KNN atau RBF, sehingga mereka adalah implementasi langsung dari metode yang dijelaskan di sini.
Metode terkait
Sumber
Zhu, X. & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.
Buka referensi publikasiDisalin.Chapelle, O., Scholkopf, B. & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.
ISBN: 978-0-262-03358-9Disalin.