Algoritma K-Nearest Neighbors dengan Python dan Scikit-Learn
Algoritma K-nearest neighbor (KNN) adalah jenis algoritma pembelajaran mesin yang diawasi. KNN sangat mudah diimplementasikan dalam bentuk paling dasar, namun melakukan tugas klasifikasi yang cukup kompleks. Ini adalah algoritma pembelajaran malas karena tidak memiliki fase pelatihan khusus. Sebaliknya, ia menggunakan semua data untuk pelatihan sambil mengklasifikasikan titik data atau instance baru. KNN adalah algoritme pembelajaran non-parametrik, yang berarti ia tidak mengasumsikan apa pun tentang data yang mendasarinya. Ini adalah fitur yang sangat berguna karena sebagian besar data dunia nyata tidak benar-benar mengikuti asumsi teoretis apa pun, misalnya keterpisahan linier, distribusi seragam, dll.
Pada artikel ini, kita akan melihat bagaimana KNN dapat diimplementasikan dengan library Scikit-Learn Python . Tapi sebelum itu mari kita telusuri dulu teori di balik KNN dan lihat apa saja kelebihan dan kekurangan dari algoritma tersebut.
Teori
Intuisi di balik algoritma KNN adalah salah satu yang paling sederhana dari semua algoritma pembelajaran mesin yang diawasi. Ini hanya menghitung jarak titik data baru ke semua titik data pelatihan lainnya. Jarak dapat berupa jenis apa pun misalnya Euclidean atau Manhattan dll. Kemudian memilih titik data K-terdekat, di mana K dapat berupa bilangan bulat apa pun. Akhirnya ia menetapkan titik data ke kelas tempat sebagian besar titik data K berada.
Mari kita lihat algoritma ini beraksi dengan bantuan contoh sederhana. Misalkan Anda memiliki dataset dengan dua variabel, yang ketika diplot, terlihat seperti pada gambar berikut.
Tugas Anda adalah mengklasifikasikan titik data baru dengan 'X' ke dalam kelas "Biru" atau kelas "Merah". Nilai koordinat titik data adalah x=45 dan y=50. Misalkan nilai K adalah 3. Algoritma KNN dimulai dengan menghitung jarak titik X dari semua titik. Ia kemudian menemukan 3 titik terdekat dengan jarak terkecil ke titik X. Hal ini ditunjukkan pada gambar di bawah. Tiga titik terdekat telah dilingkari.
Langkah terakhir dari algoritma KNN adalah menetapkan titik baru ke kelas yang mayoritas dari tiga titik terdekat berada. Dari gambar di atas kita dapat melihat bahwa dua dari tiga titik terdekat termasuk kelas "Merah" sedangkan satu milik kelas "Biru". Oleh karena itu titik data baru akan diklasifikasikan sebagai "Merah".
Pro dan Kontra KNN
Pada bagian ini kami akan menyajikan beberapa pro dan kontra menggunakan algoritma KNN.
kelebihan
- Sangat mudah untuk diimplementasikan
- Seperti yang dikatakan sebelumnya, ini adalah algoritma pembelajaran yang malas (lazy learning) dan oleh karena itu tidak memerlukan pelatihan sebelum membuat prediksi waktu nyata. Ini membuat algoritma KNN jauh lebih cepat daripada algoritma lain yang membutuhkan pelatihan misalnya SVM, regresi linier , dll.
- Karena algoritme tidak memerlukan pelatihan sebelum membuat prediksi, data baru dapat ditambahkan dengan mulus.
- Hanya ada dua parameter yang dibutuhkan untuk mengimplementasikan KNN yaitu nilai K dan fungsi jarak (misal Euclidean atau Manhattan dll)
Kontra
- Algoritma KNN tidak bekerja dengan baik dengan data berdimensi tinggi karena dengan jumlah dimensi yang banyak, menjadi sulit bagi algoritma untuk menghitung jarak di setiap dimensi.
- Algoritma KNN memiliki biaya prediksi yang tinggi untuk kumpulan data yang besar. Hal ini dikarenakan pada dataset yang besar biaya perhitungan jarak antara titik baru dengan setiap titik yang ada menjadi lebih tinggi.
- Terakhir, algoritma KNN tidak bekerja dengan baik dengan fitur kategorikal karena sulit untuk menemukan jarak antara dimensi dengan fitur kategoris.
Menerapkan Algoritma KNN dengan Scikit-Learn
Di bagian ini, kita akan melihat bagaimana library Scikit-Learn Python dapat digunakan untuk mengimplementasikan algoritma KNN dalam kurang dari 20 baris kode. Petunjuk pengunduhan dan penginstalan untuk perpustakaan Scikit learn tersedia di sini .
Catatan : Kode yang disediakan dalam tutorial ini telah dieksekusi dan diuji dengan notebook Python Jupyter.
Kumpulan Data
Kami akan menggunakan kumpulan data iris yang terkenal untuk contoh KNN kami. Dataset terdiri dari empat atribut: sepal-width, sepal-length, petal-width dan petal-length. Ini adalah atribut dari jenis tanaman iris tertentu. Tugasnya adalah memprediksi kelas yang dimiliki tanaman ini. Ada tiga kelas dalam dataset: Iris-setosa, Iris-versicolor dan Iris-virginica. Rincian lebih lanjut dari dataset tersedia di sini .
Mengimpor Perpustakaan
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
Mengimpor Kumpulan Data
Untuk mengimpor dataset dan memuatnya ke dalam kerangka data pandas kami, jalankan kode berikut:
url = "https://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data"
# Assign colum names to the dataset
names = ['sepal-length', 'sepal-width', 'petal-length', 'petal-width', 'Class']
# Read dataset to pandas dataframe
dataset = pd.read_csv(url, names=names)
Untuk melihat seperti apa sebenarnya dataset itu, jalankan perintah berikut:
dataset.head()
Menjalankan skrip di atas akan menampilkan lima baris pertama dari dataset kami seperti yang ditunjukkan di bawah ini:
Prapemrosesan
Langkah selanjutnya adalah membagi dataset kita menjadi atribut dan labelnya. Untuk melakukannya, gunakan kode berikut:
X = dataset.iloc[:, :-1].values
y = dataset.iloc[:, 4].values
The Xvariabel berisi empat kolom pertama dataset (yaitu atribut) sedangkan yberisi label.
Perpecahan Uji Kereta
Untuk menghindari over-fitting, kami akan membagi dataset kami menjadi pelatihan dan pengujian, yang memberi kami ide yang lebih baik tentang bagaimana kinerja algoritme kami selama fase pengujian. Dengan cara ini algoritme kami diuji pada data yang tidak terlihat, seperti halnya dalam aplikasi produksi.
Untuk membuat pemisahan pelatihan dan pengujian, jalankan skrip berikut:
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.20)
Skrip di atas membagi dataset menjadi 80% data latih dan 20% data uji. Ini berarti bahwa dari total 150 record, training set akan berisi 120 record dan test set berisi 30 record tersebut.
Penskalaan Fitur
Sebelum membuat prediksi aktual, selalu merupakan praktik yang baik untuk menskalakan fitur sehingga semuanya dapat dievaluasi secara seragam. Wikipedia menjelaskan alasannya dengan cukup baik:
Karena rentang nilai data mentah sangat bervariasi, dalam beberapa algoritme pembelajaran mesin, fungsi objektif tidak akan berfungsi dengan baik tanpa normalisasi. Misalnya, mayoritas pengklasifikasi menghitung jarak antara dua titik dengan jarak Euclidean. Jika salah satu fitur memiliki rentang nilai yang luas, jarak akan diatur oleh fitur khusus ini. Oleh karena itu, jangkauan semua fitur harus dinormalisasi sehingga setiap fitur berkontribusi kira-kira secara proporsional terhadap jarak akhir.
Algoritme penurunan gradien (yang digunakan dalam pelatihan jaringan saraf dan algoritme pembelajaran mesin lainnya) juga menyatu lebih cepat dengan fitur yang dinormalisasi.
Skrip berikut melakukan penskalaan fitur:
from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
scaler.fit(X_train)
X_train = scaler.transform(X_train)
X_test = scaler.transform(X_test)
Pelatihan dan Prediksi
Sangat mudah untuk melatih algoritma KNN dan membuat prediksi dengannya, terutama saat menggunakan Scikit-Learn.
from sklearn.neighbors import KNeighborsClassifier
classifier = KNeighborsClassifier(n_neighbors=5)
classifier.fit(X_train, y_train)
Langkah pertama adalah mengimpor KNeighborsClassifierkelas dari sklearn.neighborsperpustakaan. Pada baris kedua, kelas ini diinisialisasi dengan satu parameter, yaitu n_neigbours. Ini pada dasarnya adalah nilai untuk K. Tidak ada nilai ideal untuk K dan dipilih setelah pengujian dan evaluasi, namun untuk memulai, 5 tampaknya menjadi nilai yang paling umum digunakan untuk algoritma KNN.
Langkah terakhir adalah membuat prediksi pada data pengujian kami. Untuk melakukannya, jalankan skrip berikut:
y_pred = classifier.predict(X_test)
Mengevaluasi Algoritma
Untuk mengevaluasi suatu algoritme, matriks kebingungan, presisi, ingatan, dan skor f1 adalah metrik yang paling umum digunakan. The confusion_matrixdan classification_reportmetode sklearn.metricsdapat digunakan untuk menghitung metrik ini. Perhatikan skrip berikut:
from sklearn.metrics import classification_report, confusion_matrix
print(confusion_matrix(y_test, y_pred))
print(classification_report(y_test, y_pred))
Output dari skrip di atas terlihat seperti ini:
[[11 0 0]
0 13 0]
0 1 6]]
precision recall f1-score support
Iris-setosa 1.00 1.00 1.00 11
Iris-versicolor 1.00 1.00 1.00 13
Iris-virginica 1.00 1.00 1.00 6
avg / total 1.00 1.00 1.00 30
Hasilnya menunjukkan bahwa algoritme KNN kami mampu mengklasifikasikan semua 30 catatan dalam set uji dengan akurasi 100%, yang sangat baik. Meskipun algoritme bekerja sangat baik dengan kumpulan data ini, jangan berharap hasil yang sama dengan semua aplikasi. Seperti disebutkan sebelumnya, KNN tidak selalu berkinerja baik dengan fitur berdimensi tinggi atau kategoris.
Membandingkan Error Rate dengan Nilai K
Di bagian pelatihan dan prediksi kami mengatakan bahwa tidak ada cara untuk mengetahui terlebih dahulu nilai K mana yang memberikan hasil terbaik pada langkah pertama. Kami secara acak memilih 5 sebagai nilai K dan kebetulan menghasilkan akurasi 100%.
Salah satu cara untuk membantu Anda menemukan nilai K terbaik adalah dengan memplot grafik nilai K dan tingkat kesalahan yang sesuai untuk kumpulan data.
Di bagian ini, kami akan memplot kesalahan rata-rata untuk nilai prediksi set uji untuk semua nilai K antara 1 dan 40.
Untuk melakukannya, pertama-tama mari kita hitung rata-rata kesalahan untuk semua nilai prediksi di mana K berkisar dari 1 dan 40. Jalankan skrip berikut:
error = []
# Calculating error for K values between 1 and 40
for i in range(1, 40):
knn = KNeighborsClassifier(n_neighbors=i)
knn.fit(X_train, y_train)
pred_i = knn.predict(X_test)
error.append(np.mean(pred_i != y_test))
Skrip di atas mengeksekusi loop dari 1 hingga 40. Dalam setiap iterasi, kesalahan rata-rata untuk nilai prediksi set pengujian dihitung dan hasilnya ditambahkan ke errordaftar.
Langkah selanjutnya adalah memplot errornilai terhadap nilai K. Jalankan skrip berikut untuk membuat plot:
plt.figure(figsize=(12, 6))
plt.plot(range(1, 40), error, color='red', linestyle='dashed', marker='o',
markerfacecolor='blue', markersize=10)
plt.title('Error Rate K Value')
plt.xlabel('K Value')
plt.ylabel('Mean Error')
Grafik keluaran terlihat seperti ini:
Dari output kita dapat melihat bahwa mean error adalah nol ketika nilai K berada di antara 5 dan 18. Saya menyarankan Anda untuk bermain-main dengan nilai K untuk melihat bagaimana pengaruhnya terhadap keakuratan prediksi.
Kesimpulan
KNN adalah algoritma klasifikasi yang sederhana namun kuat. Ini tidak memerlukan pelatihan untuk membuat prediksi, yang biasanya merupakan salah satu bagian tersulit dari algoritme pembelajaran mesin. Algoritma KNN telah banyak digunakan untuk mencari kesamaan dokumen dan pengenalan pola. Ini juga telah digunakan untuk mengembangkan sistem rekomendasi dan untuk pengurangan dimensi dan langkah-langkah pra-pemrosesan untuk visi komputer, khususnya tugas pengenalan wajah.
Dari sini, saya akan menyarankan Anda untuk mengimplementasikan algoritma KNN untuk dataset klasifikasi yang berbeda. Variasikan ukuran pengujian dan pelatihan bersama dengan nilai K untuk melihat bagaimana hasil Anda berbeda dan bagaimana Anda dapat meningkatkan akurasi algoritme Anda. Koleksi kumpulan data klasifikasi yang bagus tersedia di sini untuk Anda mainkan.
Tidak ada komentar:
Posting Komentar