Scikit Learn - K-Nearest Neighbours (KNN)
Bab ini akan membantu Anda memahami metode tetangga terdekat di Sklearn.
Metode pembelajaran berbasis tetangga ada dua jenis yaitu supervised dan unsupervised. Pembelajaran berbasis tetangga yang diawasi dapat digunakan untuk masalah klasifikasi serta prediksi regresi tetapi, ini terutama digunakan untuk masalah prediksi klasifikasi dalam industri.
Metode pembelajaran berbasis tetangga tidak memiliki fase pelatihan khusus dan menggunakan semua data untuk pelatihan saat klasifikasi. Itu juga tidak mengasumsikan apa pun tentang data yang mendasarinya. Itulah alasan mereka malas dan non-parametrik.
Prinsip utama di balik metode tetangga terdekat adalah -
Untuk menemukan jumlah lemari sampel pelatihan yang telah ditentukan dalam jarak ke titik data baru
Prediksi label dari jumlah sampel pelatihan ini.
Di sini, jumlah sampel dapat berupa konstanta yang ditentukan pengguna seperti dalam pembelajaran tetangga terdekat K atau bervariasi berdasarkan kepadatan titik lokal seperti dalam pembelajaran tetangga berbasis radius.
Modul sklearn.neighbour
Scikit-learn miliki sklearn.neighborsmodul yang menyediakan fungsionalitas untuk metode pembelajaran berbasis tetangga yang tidak diawasi dan diawasi. Sebagai masukan, kelas dalam modul ini dapat menangani array NumPy atauscipy.sparse matriks.
Jenis algoritma
Berbagai jenis algoritma yang dapat digunakan dalam implementasi metode berbasis tetangga adalah sebagai berikut -
Paksaan
Penghitungan brute-force jarak antara semua pasangan titik dalam kumpulan data memberikan implementasi pencarian tetangga yang paling naif. Secara matematis, untuk sampel N dalam dimensi D, pendekatan brute force berskala sebagai0[DN2]
Untuk sampel data kecil, algoritme ini bisa sangat berguna, tetapi menjadi tidak layak jika dan ketika jumlah sampel bertambah. Pencarian brute force neighbour dapat diaktifkan dengan menuliskan kata kuncialgorithm=’brute’.
KD Tree
Salah satu struktur data berbasis pohon yang telah ditemukan untuk mengatasi inefisiensi komputasi dari pendekatan brute-force, adalah struktur data pohon KD. Pada dasarnya pohon KD merupakan struktur pohon biner yang disebut dengan pohon berdimensi K. Ini secara rekursif mempartisi ruang parameter di sepanjang sumbu data dengan membaginya menjadi wilayah ortografi bersarang tempat titik data diisi.
Keuntungan
Berikut adalah beberapa keuntungan dari algoritma pohon KD -
Construction is fast - Karena partisi hanya dilakukan sepanjang sumbu data, konstruksi pohon KD sangat cepat.
Less distance computations- Algoritma ini membutuhkan komputasi jarak yang sangat sedikit untuk menentukan tetangga terdekat dari sebuah titik kueri. Itu hanya butuh[ ()] perhitungan jarak.
Kekurangan
Fast for only low-dimensional neighbor searches- Ini sangat cepat untuk pencarian tetangga berdimensi rendah (D <20) tetapi saat dan ketika D tumbuh itu menjadi tidak efisien. Karena partisi hanya dilakukan di sepanjang sumbu data,
Pencarian KD tree Neighbor dapat diaktifkan dengan menulis kata kunci algorithm=’kd_tree’.
Pohon Bola
Seperti yang kita ketahui bahwa KD Tree tidak efisien dalam dimensi yang lebih tinggi, maka untuk mengatasi inefisiensi KD Tree ini dikembangkan struktur data Ball tree. Secara matematis, secara rekursif membagi data, menjadi node yang ditentukan oleh centroid C dan jari-jari r, sedemikian rupa sehingga setiap titik dalam node terletak di dalam hyper-sphere yang ditentukan oleh centroid.C dan radius r. Ini menggunakan ketidaksamaan segitiga, yang diberikan di bawah ini, yang mengurangi jumlah poin kandidat untuk pencarian tetangga
$$ \ arrowvert X + Y \ arrowvert \ leq \ arrowvert X \ arrowvert + \ arrowvert Y \ arrowvert $$Keuntungan
Berikut adalah beberapa keuntungan dari algoritma Ball Tree -
Efficient on highly structured data - Karena pohon bola mempartisi data dalam serangkaian hyper-spheres bersarang, hal ini efisien pada data yang sangat terstruktur.
Out-performs KD-tree - Pohon bola mengungguli pohon KD dalam dimensi tinggi karena memiliki geometri bola dari simpul pohon bola.
Kekurangan
Costly - Mempartisi data dalam serangkaian hyper-spheres bersarang membuat konstruksinya sangat mahal.
Pencarian tetangga pohon bola dapat diaktifkan dengan menuliskan kata kunci algorithm=’ball_tree’.
Memilih Algoritma Tetangga Terdekat
Pilihan algoritme yang optimal untuk kumpulan data tertentu bergantung pada faktor-faktor berikut -
Jumlah sampel (N) dan Dimensi (D)
Ini adalah faktor terpenting untuk dipertimbangkan saat memilih algoritma Tetangga Terdekat. Itu karena alasan yang diberikan di bawah ini -
Waktu kueri algoritme Brute Force bertambah sebagai O [DN].
Waktu query dari algoritma pohon Bola tumbuh sebagai O [D log (N)].
Waktu kueri dari algoritma pohon KD berubah dengan D dengan cara yang aneh yang sangat sulit untuk dikarakterisasi. Ketika D <20, biayanya adalah O [D log (N)] dan algoritma ini sangat efisien. Di sisi lain, ini tidak efisien jika D> 20 karena biaya meningkat hampir O [DN].
Struktur data
Faktor lain yang mempengaruhi kinerja algoritma ini adalah dimensi intrinsik dari data atau ketersebaran data. Itu karena waktu kueri dari pohon Bola dan algoritma pohon KD dapat sangat dipengaruhi olehnya. Sedangkan waktu query algoritma Brute Force tidak diubah oleh struktur data. Umumnya, algoritma pohon Bola dan pohon KD menghasilkan waktu kueri yang lebih cepat ketika ditanamkan pada data yang lebih jarang dengan dimensi intrinsik yang lebih kecil.
Jumlah Tetangga (k)
Jumlah tetangga (k) yang diminta untuk sebuah titik kueri memengaruhi waktu kueri dari pohon Ball dan algoritme pohon KD. Waktu kueri mereka menjadi lebih lambat karena jumlah tetangga (k) meningkat. Sedangkan waktu query Brute Force akan tetap tidak terpengaruh oleh nilai k.
Jumlah titik kueri
Karena membutuhkan tahap konstruksi, baik algoritma KD tree maupun Ball tree akan efektif jika ada banyak titik query. Di sisi lain, jika jumlah titik kueri lebih kecil, algoritme Brute Force bekerja lebih baik daripada algoritme KD tree dan Ball tree.