Bagaimana Algoritma K-NN Bekerja

Terjemahan disediakan oleh mesin penerjemah. Jika konten terjemahan yang diberikan bertentangan dengan versi bahasa Inggris aslinya, utamakan versi bahasa Inggris.

Terjemahan disediakan oleh mesin penerjemah. Jika konten terjemahan yang diberikan bertentangan dengan versi bahasa Inggris aslinya, utamakan versi bahasa Inggris.

Algoritma Amazon SageMaker AI k-nearest neighbors (k-NN) mengikuti proses pelatihan multi-langkah yang mencakup pengambilan sampel data input, melakukan pengurangan dimensi, dan membangun indeks. Data yang diindeks kemudian digunakan selama inferensi untuk secara efisien menemukan k-tetangga terdekat untuk titik data tertentu dan membuat prediksi berdasarkan label atau nilai tetangga.

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.

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"
}