KNN adalah model
sederhana untuk tugas-tugas regresi dan klasifikasi. Ketetanggan adalah
representasi dari contoh pelatihan dalam ruang metrik. Ruang metrik adalah
ruang fitur di mana jarak antara semua anggota set didefinisikan. Berkaitan
dengan masalah pizza pada bab sebelumnya, contoh data latih diwakili dalam
ruang metrik karena jarak antara semua diameter pizza ditentukan. Ketetanggan
ini digunakan untuk memperkirakan nilai variabel respon untuk contoh uji.
Hyperparameter k menentukan berapa banyak tetangga yang dapat digunakan
dalam estimasi. Hyperparameter adalah parameter yang mengontrol bagaimana
algoritma belajar; hiperparameter tidak diperkirakan dari data pelatihan dan
kadang-kadang ditetapkan secara manual. Akhirnya, k tetangga yang
dipilih adalah yang terdekat dengan instan uji, yang diukur dengan beberapa
fungsi jarak.
Untuk tugas-tugas
klasifikasi, satu set tupel vektor fitur dan label kelas terdiri dari set
pelatihan. KNN adalah klasifikasi biner, multi-kelas, dan multi-label; kita
akan mendefinisikan tugas-tugas ini nanti, dan kita akan fokus pada klasifikasi
biner dalam bab ini. Klasifikasi KNN yang paling sederhana menggunakan mode
label KNN untuk mengklasifikasikan contoh uji, tetapi strategi lain dapat
digunakan. K sering diatur ke angka ganjil untuk mencegah ikatan. Dalam
tugas regresi, vektor fitur masing-masing dikaitkan dengan variabel respons yang
mengambil skalar bernilai nyata alih-alih label. Prediksi adalah rata-rata atau
bobot rata-rata dari variabel respons KNN.
Apa
itu KNN?
Algoritma K-Nearest
Neighbor (K-NN) adalah sebuah metode klasifikasi terhadap sekumpulan data berdasarkan
pembelajaran data yang sudah terklasifikasikan sebelumya. Termasuk dalam
supervised learning, dimana hasil query instance yang baru diklasifikasikan
berdasarkan mayoritas kedekatan jarak dari kategori yang ada dalam K-NN.
Ilustrasi cerita dari K-NN
adalah sebagai berikut:
“Bertanya pada
Tetangga – Anda diundang ke sebuah pertemuan. Namun, Anda tidak tahu tema
pertemuan tersebut, maupun kegiatan apa saja yang akan dilakukan di pertemuan
tersebut. Anda benar-benar tidak tahu apakah pertemuan itu akan bermanfaat atau
tidak untuk Anda. Yang Anda tahu, beberapa orang teman Anda juga diundang ke
acara yang sama. Dalam kondisi seperti itu, apa yang Anda lakukan?
Cara yang biasanya
dilakukan oleh banyak orang dalam menangani masalah seperti itu adalah dengan
bertanya kepada teman-teman apakah mereka akan datang ke pertemuan tersebut
atau tidak. Biasanya, orang-orang yang pertama ditanya adalah orang-orang yang
dekat dengan Anda. Maka, Anda mencoba mengontak enam orang teman yang biasa
jadi teman main Anda. Dari enam orang tersebut, empat orang menyatakan akan
datang, tapi dua orang ternyata memutuskan tidak datang, entah mengapa
alasannya. Keputusan apa yang Anda akan ambil?”
Gambar di atas
menggambarkan ide dari algoritma k-Nearest Neighbours (kNN). Anda ingin
mengambil sebuah keputusan (kelas) antara datang atau tidak datang ke sebuah
pertemuan. Untuk mendukung pengambilan keputusan tersebut, Anda melihat
mayoritas dari keputusan teman atau tetangga Anda (instance lainnya). Teman
atau tetangga tersebut Anda pilih berdasarkan kedekatannya dengan Anda. Ukuran
kedekatan pertemanan ini bisa bermacam-macam: satu hobi, satu kelas, atau
hal-hal lainnya. Ukuran-ukuran tersebut bisa juga digunakan bersamaan, misalnya
si A itu tetangga, satu hobi, dan satu kelas; sedangkan si B hanya satu kelas
saja.
Dekat atau jauhnya
tetangga biasanya dihitung berdasarkan Euclidean Distance, atau dapat
juga menggunakan rumus jarak yang lain, seperti yang dijelaskan pada artikel Vector
Space Model dan Pengukuran Jarak.
Kedekatan dapat dianggap
sebagai invers jarak, alias berbanding terbalik dengan jarak. Semakin kecil
jarak antara dua instance, semakin besar “kedekatan” antara dua instance
tersebut. Dengan demikian, k nearest neighbours dari sebuah instance x
didefinisikan sebagai k instance yang memiliki jarak terkecil (kedekatan
terbesar, nearest) dengan x.
Tahapan
Langkah Algoritma K-NN
1. Menentukan parameter k (jumlah
tetangga paling dekat).
2. Menghitung kuadrat jarak eucliden
objek terhadap data training yang diberikan.
3. Mengurutkan hasil no 2 secara
ascending (berurutan dari nilai tinggi ke rendah)
4. Mengumpulkan kategori Y (Klasifikasi
nearest neighbor berdasarkan nilai k)
5. Dengan menggunakan kategori nearest
neighbor yang paling mayoritas maka dapat dipredisikan kategori objek.
Klasifikasi
dengan KNN
Tujuan tugas klasifikasi
adalah menggunakan satu atau lebih fitur untuk memprediksi nilai variabel
respons diskrit. Mari kita selesaikan masalah klasifikasi mainan. Asumsikan
bahwa Anda harus menggunakan tinggi dan berat badan seseorang untuk memprediksi
jenis kelaminnya. Masalah ini disebut klasifikasi biner karena variabel respons
dapat mengambil satu dari dua label. Tabel berikut mencatat sembilan contoh
pelatihan:
Tinggi
|
Berat
|
Label
|
158
cm
|
64
kg
|
Laki-laki
|
170
cm
|
66
kg
|
Laki-laki
|
183
cm
|
84
kg
|
Laki-laki
|
191
cm
|
80
kg
|
Laki-laki
|
155
cm
|
49
kg
|
Perempuan
|
163
cm
|
59
kg
|
Perempuan
|
180
cm
|
67
kg
|
Perempuan
|
158
cm
|
54
kg
|
Perempuan
|
178
cm
|
77
kg
|
Perempuan
|
Tidak seperti masalah
regresi linier sederhana bab sebelumnya, kita sekarang menggunakan fitur dari
dua variabel penjelas (explanatory) untuk memprediksi nilai variabel
respons. KNN tidak terbatas pada dua fitur; algoritma dapat menggunakan
sejumlah fitur yang semaunya, tetapi lebih dari tiga fitur tidak dapat
divisualisasikan. Mari memvisualisasikan data dengan membuat plot scatter
dengan matplotlib:
import numpy as np
import matplotlib.pyplot as plt
X_train = np.array([
[158, 64],
[170, 86],
[183,
84],
[191, 80],
[155, 49],
[163, 59],
[180, 67],
[158, 54],
[178, 77]
])
y_train = ['laki-laki',
'laki-laki', 'laki-laki', 'laki-laki', 'perempuan', 'perempuan',
'perempuan','perempuan', 'perempuan']
plt.figure()
plt.title('Tinggi & Berat
Manusia berdasarkan jenis kelamin')
plt.xlabel('Tinggi Badan dalam
cm')
plt.ylabel('Berat Badan dalam
kg')
for i, x in enumerate(X_train):
# Gunakan penanda 'x' untuk contoh
laki-laki dan penanda 'D' diamond untu
contoh perempuan
plt.scatter(x[0], x[1], c='k', marker='x'
if y_train[i] == 'laki-laki' else 'D')
plt.grid(True)
plt.show()
Dari plot kita dapat melihat bahwa pria, dilambangkan dengan x marker, cenderung lebih tinggi dan lebih berat daripada wanita. Pengamatan ini mungkin konsisten dengan pengalaman Anda. Sekarang mari kita gunakan KNN untuk memprediksi apakah seseorang dengan tinggi dan berat badan yang diberikan adalah pria atau wanita. Mari kita asumsikan bahwa kita ingin memprediksi jenis kelamin seseorang yang tingginya 155 cm dan yang beratnya 70 kg. Pertama, kita harus menentukan ukuran jarak kita. Dalam hal ini, kita akan menggunakan jarak Euclidean, jarak garis lurus antara titik-titik dalam ruang Euclidean. Jarak Euclidean dalam ruang dua dimensi diberikan oleh rumus berikut:
Kita akan menetapkan k sampai 3 dan memilih tiga contoh pelatihan terdekat. Script berikut menghitung jarak antara contoh uji dan contoh pelatihan, dan mengidentifikasi jenis kelamin yang paling umum dari tetangga terdekat:
x = np.array([[155, 70]]) #
tinggi dan berat badan yang akan diprediksi
distances = np.sqrt(np.sum((X_train
- x)**2, axis=1)) # hitung jarak euclidean (centroid)
distances # tampilkan
output : array([6.70820393, 21.9317122,
31.30495168, 37.36308338, 21., 13.60147051, 25.17935662, 16.2788206,
24.04163056])
nearest_neighbor_indices =
distances.argsort()[:3] # urutkan index aray dari kecil ke besar
nearest_neighbor_genders =
np.take(y_train, nearest_neighbor_indices) # ambil array terurut, jadikan array
baru
nearest_neighbor_genders #
tampilkan
Output: array(['laki-laki',
'perempuan', 'perempuan'], dtype='<U9')
from collections import Counter
b = Counter(np.take(y_train,
distances.argsort()[:3])) # hitung jumlah elemet yang sama
b.most_common(1)[0][0] # ambil
1 element yang paling sering muncul
Output: 'perempuan'
Plot berikut contoh query-nya,
ditunjukkan oleh lingkaran, dan tiga tetangga terdekatnya:
import numpy as np
import matplotlib.pyplot as plt
X_train = np.array([
[158, 64],
[170, 86],
[183, 84],
[191, 80],
[155, 49],
[163, 59],
[180, 67],
[158, 54],
[178, 77]
])
y_train = ['laki-laki',
'laki-laki', 'laki-laki', 'laki-laki', 'perempuan', 'perempuan',
'perempuan','perempuan', 'perempuan']
plt.figure()
plt.title('Tinggi & Berat
Manusia berdasarkan jenis kelamin')
plt.xlabel('Tinggi Badan dalam
cm')
plt.ylabel('Berat Badan dalam
kg')
for i, x in enumerate(X_train):
# Gunakan penanda 'x' untuk contoh
laki-laki dan penanda 'D' diamond untuk contoh perempuan
plt.scatter(x[0], x[1], c='k', marker='x' if
y_train[i] == 'laki-laki' else 'D')
plt.scatter(158, 64, s=200,
c='k', marker='x') #tetangga terdekat
plt.scatter(163, 59, s=200,
c='k', marker='D') #tetangga terdekat
plt.scatter(158, 54, s=200,
c='k', marker='D') #tetangga terdekat
plt.scatter(155, 70, s=200,
c='k', marker='o') #yang diprediksi
plt.grid(True)
plt.show()
Dua tetangga adalah perempuan dan satu laki-laki. Oleh karena itu kita memperkirakan
bahwa contoh uji adalah perempuan. Sekarang mari kita gunakan klasifikasi
KNN dengan scikit-learn:
from sklearn.preprocessing
import LabelBinarizer
from sklearn.neighbors import
KNeighborsClassifier
lb = LabelBinarizer()
y_train_binarized =
lb.fit_transform(y_train)
y_train_binarized
Output:
array([[0],
[0],
[0],
[0],
[1],
[1],
[1],
[1],
[1]])
K = 3 # tentukan jumlah
tetangga
# klasifikasi KNN
clf =
KNeighborsClassifier(n_neighbors=K)
# jadikan array 1 dimensi dalam
1 baris = [0 0 0 0 1 1 1 1 1]
clf.fit(X_train,
y_train_binarized.reshape(-1))
print(y_train_binarized);
print()
print(y_train_binarized.reshape(-1));
print()
prediction_binarized =
clf.predict(np.array([155, 70]).reshape(1, -1))[0]
print(np.array([155, 70]));
print()
print(np.array([155,
70]).reshape(1, -1)); print()
predicted_label =
lb.inverse_transform(prediction_binarized)
print(prediction_binarized);
print()
predicted_label
Output:
array(['perempuan'], dtype='<U9')
Label kita adalah
string; pertama-tama kita menggunakan LabelBinarizer untuk mengubahnya menjadi bilangan
integer. LabelBinarizer mengimplementasikan antarmuka
transformator, yang terdiri dari metode fit, transform, dan fit_transform. Metode fit
mempersiapkan transformer; dalam hal ini, ia menciptakan pemetaan dari string
label ke integer. Metode transform menerapkan pemetaan untuk memasukkan
label. Metode fit_transform adalah metode yang lebih nyaman untuk
memanggil fit dan transform
sekaligus.
Selanjutnya, kita
menginisialisasi KNeighborsClassifier. Meskipun KNN adalah pembelajar yang malas,
masih menerapkan antarmuka estimator. Kita menyebutnya fit dan predict seperti yang kita lakukan dengan objek regresi
linier sederhana. Terakhir, kita dapat menggunakan LabelBinarizer yang sesuai untuk membalik transformasi dan
mengembalikan label string. Sekarang mari kita gunakan classifier kita untuk
membuat prediksi untuk set uji, dan mengevaluasi kinerja classifier kita:
Tinggi
|
Berat
|
Label
|
168
cm
|
65
kg
|
Laki-laki
|
180
cm
|
96
kg
|
Laki-laki
|
160
cm
|
52
kg
|
Perempuan
|
169
cm
|
67
kg
|
Perempuan
|
X_test = np.array([
[168, 65],
[180, 96],
[160, 52],
[169, 67]
])
y_test = ['laki-laki',
'laki-laki', 'perempuan', 'perempuan']
y_test_binarized =
lb.transform(y_test) # konversi label ke biner
print('Label Biner: %s' %
y_test_binarized.T[0]) # 0=laki-laki, 1=perempuan
predictions_binarized =
clf.predict(X_test)
print('Biner Prediksi: %s' %
predictions_binarized) # prediksi terbiner
print('Label Prediksi: %s' %
lb.inverse_transform(predictions_binarized)) # prediksi bentuk label
Output:
Label Biner: [0 0 1 1]
Biner Prediksi: [1 0 1 1]
Label Prediksi: ['perempuan'
'laki-laki' 'perempuan' 'perempuan']
Dengan membandingkan
label pengujian kita dengan prediksi pengklasifikasi kita, dtemukan bahwa salah
memrediksikan bahwa salah satu contoh uji laki-laki adalah perempuan.
Ada dua jenis kesalahan dalam tugas pengklasifikasian biner: false positive
dan false negative. Ada banyak pengukuran kinerja untuk pengklasifikasi;
beberapa pengukuran lebih cocok digunakan daripada yang lain, tergantung pada
konsekuensi dari jenis kesalahan pada aplikasi Anda. Kita akan menilai
klasifikasi kita menggunakan beberapa pengukuran kinerja secara umum, antara
lain: akurasi, presisi, dan recall. Akurasi adalah proporsi contoh uji yang
diklasifikasikan dengan benar. Model kita mengklasifikasikan salah satu dari
empat instance secara tidak benar, sehingga akurasinya adalah 75%:
from sklearn.metrics import
accuracy_score
print('Akurasi: %s' %
accuracy_score(y_test_binarized, predictions_binarized))
Output: Akurasi: 0.75
Presisi adalah proporsi
contoh uji yang diprediksi positif yang benar-benar positif. Dalam contoh ini,
kelas positif adalah laki-laki. Penujukkan laki-laki dan perempuan ke kelas positif dan negatif adalah semaunya,
dan bisa dibalik. Klasifikasi kita memperkirakan bahwa salah satu contoh uji
adalah kelas positif.
from sklearn.metrics import
precision_score
print('Presisi: %s' %
precision_score(y_test_binarized, predictions_binarized))
Output: Presisi:
0.6666666666666666
Recall adalah proporsi
contoh uji benar-benar positif yang diprediksi positif. Pengklasifikasi kita
memperkirakan bahwa salah satu dari dua contoh uji yang benar-benar positif
adalah positif.
from sklearn.metrics import
recall_score
print('Recall: %s' % recall_score(y_test_binarized,
predictions_binarized))
Output: Recall: 1.0
------------
Kode program dapat di download di: https://drive.google.com/file/d/1uzCZEMNA4RJLvmIduLkny9RargykrxX5/view?usp=sharing
Materi: https://drive.google.com/file/d/1y-d-0757cOLobRkDn1lpntZL5BN0WL05/view?usp=sharing k-Nearest Neighbors , klasifikasi , knn
No comments:
Post a Comment