Bagaimana Algoritma K-NN Bekerja

Langkah 1: Sampel

Untuk menentukan jumlah total titik data yang akan diambil sampelnya dari kumpulan data pelatihan, gunakan parameternyasample_size. Misalnya, jika dataset awal memiliki 1.000 titik data dan sample_size diatur ke 100, di mana jumlah total instance adalah 2, setiap pekerja akan mengambil sampel 50 poin. Satu set total 100 titik data akan dikumpulkan. Pengambilan sampel berjalan dalam waktu linier sehubungan dengan jumlah titik data.

Langkah 2: Lakukan Pengurangan Dimensi

Implementasi algoritma k-NN saat ini memiliki dua metode pengurangan dimensi. Anda menentukan metode di dimension_reduction_type hyperparameter. signMetode ini menentukan proyeksi acak, yang menggunakan proyeksi linier menggunakan matriks tanda acak, dan fjlt metode menentukan transformasi Johnson-Lindenstrauss yang cepat, metode berdasarkan transformasi Fourier. Kedua metode mempertahankan jarak produk L2 dan bagian dalam. fjltMetode ini harus digunakan ketika dimensi target besar dan memiliki kinerja yang lebih baik dengan inferensi CPU. Metode berbeda dalam kompleksitas komputasi mereka. signMetode ini membutuhkan waktu O (ndk) untuk mengurangi dimensi batch n titik dimensi d menjadi dimensi target k. fjltMetode ini membutuhkan waktu O (nd log (d)), tetapi konstanta yang terlibat lebih besar. Menggunakan pengurangan dimensi memperkenalkan noise ke dalam data dan noise ini dapat mengurangi akurasi prediksi.

Langkah 3: Membangun Indeks

Selama inferensi, algoritme menanyakan indeks untuk k-nearest-neighbors titik sampel. Berdasarkan referensi ke poin, algoritma membuat klasifikasi atau prediksi regresi. Itu membuat prediksi berdasarkan label kelas atau nilai yang disediakan. k-NN menyediakan tiga jenis indeks yang berbeda: indeks datar, indeks terbalik, dan indeks terbalik dengan kuantisasi produk. Anda menentukan jenis dengan index_type parameter.

Serialisasi Model

Ketika algoritma K-NN menyelesaikan pelatihan, ia membuat serial tiga file untuk mempersiapkan inferensi.

• model_algo-1: Berisi indeks serial untuk menghitung tetangga terdekat.

• model_algo-1.labels: Berisi label serial (format biner np.float32) untuk menghitung label yang diprediksi berdasarkan hasil kueri dari indeks.

• model_algo-1.json: Berisi metadata model berformat JSON yang menyimpan parameter dan hiper dari pelatihan untuk inferensi bersama dengan status relevan lainnya. k predictor_type

Dengan implementasi k-NN saat ini, Anda dapat memodifikasi file metadata untuk mengubah cara prediksi dihitung. Misalnya, Anda dapat mengubah k ke 10 atau mengubah predictor_type ke regressor.

{
  "k": 5,
  "predictor_type": "classifier",
  "dimension_reduction": {"type": "sign", "seed": 3, "target_dim": 10, "input_dim": 20},
  "normalize": False,
  "version": "1.0"
}