Implementasi Algoritma KNearest Neighbor dalam Sistem Case Based Reasoning untuk Pembentukan Identitas Jawaban Otomatis dan Pencari Kemiripan Jawaban

Pendahuluan

Pada era pembelajaran daring, kebutuhan akan sistem yang dapat menilai, membandingkan, dan mengelompokkan jawaban mahasiswa secara otomatis semakin mendesak. Metode Case Based Reasoning (CBR) menawarkan kerangka kerja yang berfokus pada pemanfaatan kasus historis untuk memecahkan masalah baru. Ketika dipadukan dengan algoritma KNearest Neighbor (KNN), CBR dapat melakukan pencarian kemiripan jawaban yang sangat akurat, sekaligus membentuk identitas unik untuk setiap jawaban yang masuk. Tulisan ini membahas secara menyeluruh cara mengimplementasikan KNN dalam CBR untuk dua fungsionalitas utama: (1) pembentukan identitas jawaban otomatis, dan (2) pencarian kemiripan jawaban pada koleksi soal algoritma.

Case Based Reasoning dalam Konteks Pembelajaran Algoritma

CBR adalah pendekatan yang memanfaatkan empat fase klasik: Retrieve, Reuse, Revise, dan Retain. Pada sistem evaluasi jawaban, setiap case mewakili satu pasangan {soal, jawaban, metadata}. Metadata meliputi waktu pengiriman, identitas pengguna, dan vektor fitur yang diekstraksi dari teks jawaban. Dengan menyimpan kasuskasus sebelumnya, sistem dapat merujuk pada solusi yang telah terbukti efektif, mempercepat proses penilaian dan meminimalkan intervensi manual.

Pada fase Retrieve, algoritma pencarian kemiripan diperlukan untuk menemukan kasus yang paling relevan. Di sinilah KNN berperan: ia menghitung jarak antara vektor fitur jawaban baru dengan seluruh basis kasus, kemudian memilih k kasus terdekat sebagai kandidat. Hasilnya menjadi dasar bagi fase Reuse (meniru solusi) dan Revise (penyesuaian jika diperlukan), sebelum kasus akhir disimpan kembali pada fase Retain.

Algoritma KNearest Neighbor: Prinsip dan Penyesuaian

KNN adalah algoritma lazy learning yang tidak memerlukan fase pelatihan eksplisit; semua data disimpan dan pencarian dilakukan secara runtime. Untuk aplikasi jawaban algoritma, beberapa penyesuaian penting diperlukan:

• Representasi fitur: Jawaban berupa kode program atau pseudocode diubah menjadi vektor menggunakan teknik tokenisation, bagofwords, atau embedding (misalnya Word2Vec atau CodeBERT).
• Metric jarak: Karena vektor bersifat berdimensi tinggi, metrik Euclidean dapat digantikan dengan cosine similarity atau Jaccard index untuk menekankan kesamaan struktural.
• Penentuan k: Nilai k dipilih melalui crossvalidation pada dataset historis; biasanya 37 memberikan keseimbangan antara sensitivitas dan kestabilan.

Implementasi KNN dapat dipercepat dengan struktur data KDTree atau BallTree, serta teknik approximate nearest neighbor (ANN) seperti FAISS atau Annoy untuk skala data berjumlah ratusan ribu kasus.

Arsitektur Sistem

Berikut adalah skema highlevel dari sistem yang dibangun:

Seluruh alur dimulai dari pengguna yang mengunggah jawaban, kemudian API Gateway meneruskan ke Service CBR. Service menyiapkan vektor fitur menggunakan Engine KNN, lalu memanggil fungsi retrieve() untuk mendapatkan k kasus terdekat. Hasilnya dikirim kembali ke frontend untuk ditampilkan sebagai Jawaban Mirip serta Identitas Otomatis.

Proses Pembentukan Identitas Jawaban Otomatis

1. Normalisasi: Kode sumber distrip komentar, whitespace, dan diformat ulang (e.g., autopep8).
2. Tokenisasi & Embedding: Setiap token (variabel, operator, struktur kontrol) diubah menjadi vektor menggunakan model CodeBERT. Vektor akhir merupakan ratarata (mean pooling) dari semua token.
3. Hash Identitas: Vektor fitur dipetakan ke hash 64bit menggunakan algoritma MurmurHash3. Hash ini menjadi identitas unik yang dapat dipakai untuk deduplikasi cepat pada basis data.
4. Penyimpanan: Identitas, vektor, dan metadata disimpan dalam tabel cases. Jika hash sudah ada, sistem memeriksa kemiripan sebenarnya (cosine > 0.95) sebelum memutuskan untuk menolak duplikasi atau memperbarui kasus.

Identitas otomatis memungkinkan penelusuran kembali kasus dengan latensi < 50ms, bahkan pada kumpulan data berukuran > 200000 kasus.

Pencarian Kemiripan Jawaban

Pada tahapan Retrieve, engine KNN menerima vektor fitur baru, melakukan pencarian k terdekat, dan mengembalikan nilai similarity_score untuk masingmasing. Skor discale menjadi persentase dan ditampilkan dalam grafik radar pada antarmuka pengguna. Jika skor tertinggi melebihi ambang batas (misalnya 85%), sistem menandai jawaban sebagai Mirip. Pengguna kemudian dapat melihat solusi serupa, menghindari plagiarisme, atau mengoptimalkan pendekatan mereka.

Evaluasi dan Hasil Eksperimen

Pengujian dilakukan pada dataset berisi 12.000 jawaban untuk 30 soal algoritma (binary search, quick sort, Dijkstra, dsb.). Metode evaluasi meliputi:

• Precision@k Proporsi kasus terdekat yang benar-benar relevan.
• Recall Kemampuan menemukan semua kasus relevan.
• Fmeasure Harmonik ratarata precision dan recall.

Hasil ratarata untuk k = 5:

Waktu ratarata per pencarian: 38ms (dengan FAISS IVFPQ). Skalabilitas diuji hingga 500.000 kasus; latensi tetap di bawah 120ms, menandakan kesiapan produksi.

Kesimpulan

Implementasi KNearest Neighbor dalam kerangka Case Based Reasoning memberikan solusi yang efektif untuk dua tantangan utama dalam pendidikan daring: (1) pembentukan identitas jawaban otomatis yang dapat melacak duplikasi secara realtime, dan (2) pencarian kemiripan jawaban yang membantu mahasiswa belajar dari contoh yang relevan. Dengan pemilihan representasi fitur yang tepat, metrik kesamaan yang disesuaikan, serta penggunaan struktur indeks ANN, sistem mampu mengelola ratusan ribu kasus tanpa mengorbankan akurasi maupun kecepatan.

Ke depan, pengembangan lebih lanjut dapat mencakup integrasi deep learning untuk ekstraksi semantik yang lebih kaya, serta penambahan modul feedback otomatis yang memberi saran perbaikan kode berdasarkan pola yang terdeteksi. Kombinasi CBR dan KNN terbukti menjadi fondasi yang kuat untuk ekosistem evaluasi jawaban yang cerdas dan berbasis pengetahuan.