Algoritma K-Nearest Neighbors (KNN) dengan R

Konsep K-Nearest Neighbors (KNN)

K-Nearest Neighbors (KNN) merupakan metode populer dalam bidang machine learning. Konsep dasar algoritma KNN adalah mencari k-nearest neighbors atau k tetangga terdekat dari suatu observasi berdasarkan jarak euclidean ataupun ukuran jarak lainnya. KNN umumnya digunakan untuk pemodelan klasifikasi namun dapat digunakan juga pada pemodelan regresi.

Dalam model klasifikasi, algoritma KNN menghitung jarak antara amatan yang akan diklasifikasikan dengan dataset yang sudah memiliki label kelas, dan memilih k tetangga terdekat dengan amatan tersebut berdasarkan jarak tersebut. Setelah itu, dari k tetangga tersebut, dilihat kelas apa yang paling banyak (mayoritas) menjadi tetangga terdekatnya. Hasil akhir yaitu mengklasifikasikan amatan tersebut masuk ke dalam kelas mayoritas yang diperoleh.

Prinsip Dasar dan Proses KNN

Jarak: KNN mengukur kesamaan antara data dengan menghitung jarak antara titik data dalam ruang fitur. Jarak ini dapat diukur menggunakan berbagai metrik, seperti Euclidean, Manhattan, atau Minkowski distance.
K-Neighbors: “K” dalam KNN menunjukkan jumlah tetangga terdekat yang akan digunakan untuk membuat prediksi. Algoritma ini memeriksa label k tetangga terdekat suatu titik data dan menentukan label mayoritas sebagai prediksi.

Langkah-Langkah KNN

Menentukan Parameter k: Pemilihan nilai k adalah bagian kritis dari algoritma KNN. Nilai k yang terlalu kecil dapat menyebabkan model rentan terhadap noise, sedangkan nilai k yang besar dapat mengaburkan batas keputusan yang sebenarnya.
Menghitung Jarak: Algoritma menghitung jarak antara titik data yang akan diprediksi dengan semua titik data dalam set pelatihan.
Menentukan Tetangga Terdekat: Algoritma memilih k tetangga terdekat berdasarkan jarak yang dihitung sebelumnya.
Menentukan Kelas Prediksi: kelas mayoritas dari tetangga terdekat digunakan sebagai prediksi untuk titik data yang dipertanyakan.

Ilustrasi di atas menunjukkan data historis mengenai karakteristik anak ayam yang baru menetas menurut dua kriteria yaitu tinggi dan bobot. Warna biru menunjukkan anak ayam betina dan orange anak ayam jantan. Secara visual dapat dilihat bahwa kecenderungan anak ayam jantan memiliki bobot dan tinggi yang lebih besar dibandingkan anak ayam betina. Pertanyaannya adalah jika kita memiliki 3 anak ayam yang baru menetas (misal amatan denganw arna merah), dan belum diketahui jenis kelaminnya bagaimana kita dapat memprediksi jenis kelamin dari ketiga anak ayam tersebut.

Penentuan kelas prediksi pada algoritma KNN diukur dari kedekatan jarak data baru tersebut dengan tetangga terdekatnya. Sebagai contoh, berdasarkan k=3 tetangga terdekat, anak ayam a kemungkinan akan diprediksi sebagai pejantan karena tiga tetangga terdekatnya adalah pejantan. Begitu pula anak ayam b akan diprediksi sebagai betina. Untuk anak ayam c, 2 dari 3 tetangga terdekatnya adalah pejantan maka akan diprediksi sebagai pejantan.

Untuk memperoleh model KNN yang baik, parameter penting yang perlu ditentukan adalah nilai k, atau jumlah tetangga terdekat yang akan digunakan. Nilai k tentu saja akan berbeda tergantung dari permasalahan dan data yang dihadapi. Penentuan nilai k optimal ini dapat dilakukan melalui proses tuning hyperparameter.

Penyiapan Data

Dataset yang digunakan memiliki format csv sehingga kita dapat membacanya menggunakan fungsi read.csv. Peubah respon atau kelas pada dataset tersimpan pada kolom quality dengan nilai LOW atau HIGH. Sementara kolom lainnya seluruhnya bertipe numerik.

data <- read.csv("https://raw.githubusercontent.com/sainsdataid/dataset/main/wine-quality-binary.csv")

str(data)

## 'data.frame':    1143 obs. of  13 variables:
##  $ id                  : int  1 2 3 4 5 6 7 8 9 10 ...
##  $ fixed.acidity       : num  7.4 7.8 7.8 11.2 7.4 7.4 7.9 7.3 7.8 6.7 ...
##  $ volatile.acidity    : num  0.7 0.88 0.76 0.28 0.7 0.66 0.6 0.65 0.58 0.58 ...
##  $ citric.acid         : num  0 0 0.04 0.56 0 0 0.06 0 0.02 0.08 ...
##  $ residual.sugar      : num  1.9 2.6 2.3 1.9 1.9 1.8 1.6 1.2 2 1.8 ...
##  $ chlorides           : num  0.076 0.098 0.092 0.075 0.076 0.075 0.069 0.065 0.073 0.097 ...
##  $ free.sulfur.dioxide : num  11 25 15 17 11 13 15 15 9 15 ...
##  $ total.sulfur.dioxide: num  34 67 54 60 34 40 59 21 18 65 ...
##  $ density             : num  0.998 0.997 0.997 0.998 0.998 ...
##  $ pH                  : num  3.51 3.2 3.26 3.16 3.51 3.51 3.3 3.39 3.36 3.28 ...
##  $ sulphates           : num  0.56 0.68 0.65 0.58 0.56 0.56 0.46 0.47 0.57 0.54 ...
##  $ alcohol             : num  9.4 9.8 9.8 9.8 9.4 9.4 9.4 10 9.5 9.2 ...
##  $ quality             : chr  "LOW" "LOW" "LOW" "HIGH" ...

Dari struktur di atas dapat pula kita lihat terdapat kolom id. kolom ini hanya berisi urutan data dari 1, 2… sampai 1143 sesuai banyaknya data dan bukanlah peubah yang berkaitan dengan kelas data sehingga bisa kita hapus saja. Kita juga sebaiknya merubah tipe dari peubah respon menjadi factor. Hal ini nantinya dapat mempermudah pengukuran pada proses-proses selanjutnya.

Pada kode di bawah ini, kita juga menampilkan banyaknya data serta komposisinya menurut peubah quality. Dari total 1143 observasi, terdapat 621 yang masuk sebagai kelas "HIGH" dan 522 sebagai kelas "LOW". Berdasarkan proporsinya kedua kelas relatif seimbang yaitu dengan komposisi sekitar 54% data dengan kelas "HIGH" berbanding 46% data dengan kelas "LOW".

# menghapus kolom `id`
data$id <- NULL

# mengubah tipe kolom `quality` menjadi factor
data$quality <- as.factor(data$quality)

# melihat jumlah dan komposisi masing-masing kategori
quality <- data.frame(table(data$quality))

quality$Prop <- round(quality$Freq/sum(quality$Freq), 3)

print(quality)

##   Var1 Freq  Prop
## 1 HIGH  621 0.543
## 2  LOW  522 0.457

Pembagian Data Latih dan Data Uji

Membagi data menjadi data latih dan data uji merupakan tahapan penting dalam algoritma machine learning termasuk KNN. Pembagian ini diperlukan agar algoritma dapat diuji menggunakan data yang belum pernah dilihat selama proses pelatihan. Pada saat pelatihan, data yang digunakan hanya data latih saja. Adapun data uji nantinya digunakan untuk mengukur performa algoritma. Hal ini penting agar pengukuran performa lebih “fair” karena menggunakan data baru yang belum pernah digunakan untuk proses pelatihan.

Pembagian data pada bahasa R dapat dilakukan menggunakan fungsi createDataPartition dari pustaka caret. Proporsi banyaknya data untuk pelatihan dan pengujian dapat ditentukan dengan mengatur parameter p. Pada contoh ini, kita akan menggunakan 70% dataset sebagai data latih dan 30% sisanya menjadi data uji.

# Membagi data sebagai data Latih dan data uji

library(caret)

## Warning: package 'caret' was built under R version 4.4.1

## Loading required package: ggplot2

## Loading required package: lattice

set.seed(100)  # mengatur seed tertentu untuk hasil yang dapat direproduksi

# data latih = 70%, data uji = 30%
trainIndex <- createDataPartition(data$quality, p = 0.70, list = FALSE, times = 1)

# Buat data latih dan data uji berdasarkan indeks yang dihasilkan
data.train <- data[trainIndex, ]
data.test <- data[-trainIndex, ]

# melihat komposisi setiap kelas pada data train dan test
cbind("train" = table(data.train$quality), "test" = table(data.test$quality))

##      train test
## HIGH   435  186
## LOW    366  156

Features Scaling

KNN merupakan model berbasis jarak sehingga ukuran jarak merupakan hal penting. Perbedaan skala data antar fitur akan mempengaruhi performa model yang dihasilkan. Untuk menghindari hal tersebut, disarankan untuk selalu melakukan scaling terhadap fitur, khususnya ketika perbedaan skala sangat besar. Metode scaling yang dapat digunakan salah satunya adalah normalisasi (MinMax Scaling), yaitu membuat setiap fitur memiliki nilai minimum 0 dan maksimum 1.

Proses scaling pada R dapat menggunakan fungsi preProcess dari pustaka caret. Parameter method="range" menunjukkan scaling dengan metode normalisasi. Dapat dilihat dari output di bawah ini, bahwa fitur hasil scaling seluruhnya memiliki nilai minimum 0 dan maksimum 1.

# Menerapkan scaling menggunakan preProcess untuk semua fitur numerik
preproc.params <- preProcess(data.train[, -12], method = "range")

scaled.data.train <- predict(preproc.params, data.train[, -12])
scaled.data.test <- predict(preproc.params, data.test[, -12])

summary(scaled.data.train)

##  fixed.acidity    volatile.acidity  citric.acid     residual.sugar   
##  Min.   :0.0000   Min.   :0.0000   Min.   :0.0000   Min.   :0.00000  
##  1st Qu.:0.2212   1st Qu.:0.2231   1st Qu.:0.1139   1st Qu.:0.07752  
##  Median :0.3009   Median :0.3306   Median :0.3165   Median :0.10078  
##  Mean   :0.3318   Mean   :0.3377   Mean   :0.3445   Mean   :0.12456  
##  3rd Qu.:0.3982   3rd Qu.:0.4298   3rd Qu.:0.5443   3rd Qu.:0.13178  
##  Max.   :1.0000   Max.   :1.0000   Max.   :1.0000   Max.   :1.00000  
##    chlorides       free.sulfur.dioxide total.sulfur.dioxide    density      
##  Min.   :0.00000   Min.   :0.0000      Min.   :0.0000       Min.   :0.0000  
##  1st Qu.:0.08488   1st Qu.:0.1154      1st Qu.:0.0530       1st Qu.:0.4212  
##  Median :0.10875   Median :0.2308      Median :0.1166       Median :0.5034  
##  Mean   :0.12409   Mean   :0.2780      Mean   :0.1406       Mean   :0.5092  
##  3rd Qu.:0.13793   3rd Qu.:0.3846      3rd Qu.:0.1908       3rd Qu.:0.5933  
##  Max.   :1.00000   Max.   :1.0000      Max.   :1.0000       Max.   :1.0000  
##        pH           sulphates         alcohol      
##  Min.   :0.0000   Min.   :0.0000   Min.   :0.0000  
##  1st Qu.:0.2920   1st Qu.:0.1026   1st Qu.:0.1719  
##  Median :0.3805   Median :0.1474   Median :0.2656  
##  Mean   :0.3841   Mean   :0.1712   Mean   :0.3093  
##  3rd Qu.:0.4690   3rd Qu.:0.2115   3rd Qu.:0.4219  
##  Max.   :1.0000   Max.   :1.0000   Max.   :1.0000

KNN dengan paket ‘class’

Untuk membuat prediksi berdasarkan algoritma KNN kita dapat menggunakan fungsi knn dari pustaka class. Fungsi knn langsung menghasilkan output berupa prediksi dari kelas pada data uji yang diberikan. Pada contoh berikut, kita melakukan prediksi data uji berdasarkan data latih dengan mengambil nilai k=5.

library(class)

pred.knn <- knn(train=scaled.data.train, test=scaled.data.test, 
             cl=data.train$quality, k=5)

# Menampilkan hasil prediksi
print(pred.knn)

##   [1] LOW  LOW  LOW  LOW  LOW  LOW  LOW  LOW  LOW  LOW  LOW  LOW  HIGH HIGH LOW 
##  [16] LOW  LOW  LOW  LOW  HIGH LOW  LOW  LOW  HIGH LOW  LOW  LOW  HIGH LOW  HIGH
##  [31] LOW  LOW  HIGH HIGH LOW  LOW  LOW  LOW  LOW  LOW  LOW  HIGH LOW  LOW  HIGH
##  [46] HIGH HIGH LOW  LOW  LOW  HIGH LOW  LOW  LOW  HIGH LOW  HIGH HIGH LOW  HIGH
##  [61] LOW  LOW  HIGH LOW  HIGH HIGH HIGH HIGH HIGH LOW  LOW  HIGH HIGH HIGH HIGH
##  [76] HIGH HIGH HIGH HIGH HIGH HIGH HIGH LOW  LOW  HIGH LOW  LOW  HIGH HIGH LOW 
##  [91] HIGH LOW  LOW  HIGH HIGH HIGH HIGH HIGH HIGH HIGH LOW  HIGH HIGH LOW  LOW 
## [106] HIGH HIGH HIGH HIGH HIGH HIGH HIGH HIGH HIGH LOW  HIGH HIGH LOW  HIGH LOW 
## [121] HIGH HIGH LOW  HIGH HIGH HIGH HIGH LOW  LOW  HIGH LOW  HIGH HIGH LOW  LOW 
## [136] LOW  LOW  LOW  LOW  LOW  LOW  LOW  LOW  LOW  LOW  HIGH HIGH HIGH LOW  LOW 
## [151] LOW  HIGH LOW  LOW  LOW  LOW  HIGH LOW  HIGH LOW  LOW  LOW  HIGH HIGH LOW 
## [166] LOW  LOW  LOW  LOW  LOW  LOW  LOW  LOW  LOW  HIGH LOW  LOW  LOW  HIGH LOW 
## [181] LOW  LOW  HIGH HIGH HIGH HIGH HIGH HIGH HIGH LOW  LOW  LOW  HIGH HIGH LOW 
## [196] LOW  LOW  LOW  HIGH HIGH HIGH HIGH HIGH HIGH HIGH HIGH HIGH HIGH HIGH LOW 
## [211] HIGH LOW  LOW  HIGH HIGH HIGH HIGH HIGH LOW  LOW  HIGH HIGH LOW  HIGH HIGH
## [226] HIGH HIGH HIGH HIGH HIGH HIGH HIGH LOW  LOW  HIGH HIGH HIGH HIGH LOW  HIGH
## [241] HIGH HIGH HIGH LOW  HIGH HIGH HIGH HIGH LOW  HIGH LOW  HIGH HIGH LOW  HIGH
## [256] HIGH HIGH HIGH HIGH LOW  LOW  HIGH LOW  HIGH HIGH LOW  HIGH HIGH LOW  LOW 
## [271] LOW  HIGH LOW  HIGH HIGH LOW  HIGH HIGH LOW  HIGH HIGH LOW  LOW  HIGH HIGH
## [286] LOW  LOW  HIGH LOW  LOW  HIGH HIGH HIGH LOW  LOW  LOW  LOW  HIGH HIGH HIGH
## [301] LOW  LOW  HIGH LOW  HIGH HIGH HIGH HIGH HIGH HIGH LOW  HIGH HIGH HIGH HIGH
## [316] HIGH LOW  HIGH HIGH LOW  HIGH HIGH LOW  HIGH LOW  LOW  HIGH HIGH HIGH HIGH
## [331] LOW  HIGH LOW  HIGH LOW  HIGH LOW  HIGH HIGH HIGH LOW  HIGH
## Levels: HIGH LOW

# Evaluasi hasil prediksi pada data uji
conf_matrix <- confusionMatrix(pred.knn, data.test$quality)
print(conf_matrix)

## Confusion Matrix and Statistics
## 
##           Reference
## Prediction HIGH LOW
##       HIGH  136  48
##       LOW    50 108
##                                           
##                Accuracy : 0.7135          
##                  95% CI : (0.6624, 0.7608)
##     No Information Rate : 0.5439          
##     P-Value [Acc > NIR] : 9.525e-11       
##                                           
##                   Kappa : 0.4231          
##                                           
##  Mcnemar's Test P-Value : 0.9195          
##                                           
##             Sensitivity : 0.7312          
##             Specificity : 0.6923          
##          Pos Pred Value : 0.7391          
##          Neg Pred Value : 0.6835          
##              Prevalence : 0.5439          
##          Detection Rate : 0.3977          
##    Detection Prevalence : 0.5380          
##       Balanced Accuracy : 0.7117          
##                                           
##        'Positive' Class : HIGH            
##

Berdasarkan output di atas, disajikan prediksi kelas dari data uji. Misalkan pada data uji yang pertama diprediksi masuk kelas LOW, data uji kedua masuk kelas LOW sampai dengan data uji terakhir diprediksi masuk sebagai kelas HIGH. Hasil ini selanjutnya dapat dibandingkan dengan kelas sebenarnya pada data uji melalui confusion matrix.

Secara keseluruhan, nilai akurasi prediksi sebesar 0.7135 atau algoritma KNN berhasil memprediksi benar 71,35% dari data uji. Jika dilihat menurut masing-masing kelas, dari 186 data uji dengan kelas HIGH, 136 diprediksi benar, sementara 50 salah. Hasil ini memberikan nilai sensitivity (prediksi benar kelas positif) sebesar 0.7312. Selanjutnya, dari 156 data uji dengan kelas LOW, 108 diprediksi benar dan 48 salah atau memiliki nilai spesifisitas sebesar 0.6923.

KNN dengan paket ‘caret’

Pustaka caret memiliki fungsi train yang dapat dimanfaatkan untuk melakukan iterasi berbagai nilai k. Selain melakukan iterasi, fungsi train juga memungkinkan kita melakukan validasi silang sehingga hasil yang diperoleh bisa lebih dapat dipercaya dan dapat mengurangi kecenderungan overfitting.

Kode berikut ini menunjukkan bagaimana penggunaan fungsi train untuk mencari nilai k terbaik pada algoritma KNN.

set.seed(100)  # mengatur seed tertentu untuk hasil yang dapat direproduksi

# proses pengukuran menggunakan k-fold cv dengan 5 fold
control = trainControl(method = "cv", number = 5)

# pencarian dilakukan untuk k=1,2,...30
grid = expand.grid(k = 1:30)

knn.grid <- train(x=scaled.data.train, 
                   y=data.train$quality, 
                   method = "knn",
                   trControl = control,
                   tuneGrid = grid)

# Menampilkan hasil model
print(knn.grid)

## k-Nearest Neighbors 
## 
## 801 samples
##  11 predictor
##   2 classes: 'HIGH', 'LOW' 
## 
## No pre-processing
## Resampling: Cross-Validated (5 fold) 
## Summary of sample sizes: 641, 641, 641, 641, 640 
## Resampling results across tuning parameters:
## 
##   k   Accuracy   Kappa    
##    1  0.7091227  0.4126780
##    2  0.6529503  0.2973395
##    3  0.6966770  0.3874821
##    4  0.7029503  0.4015506
##    5  0.7204425  0.4333700
##    6  0.7129581  0.4194087
##    7  0.7191693  0.4314914
##    8  0.7266848  0.4464642
##    9  0.7129658  0.4194162
##   10  0.7117314  0.4166171
##   11  0.7092236  0.4119548
##   12  0.7017236  0.3965814
##   13  0.7029658  0.3999190
##   14  0.6904969  0.3724202
##   15  0.6942081  0.3807460
##   16  0.6967158  0.3877130
##   17  0.7029658  0.3997832
##   18  0.7029891  0.4004082
##   19  0.7092314  0.4128985
##   20  0.7017081  0.3980471
##   21  0.7142158  0.4224141
##   22  0.7117391  0.4176401
##   23  0.6967624  0.3868755
##   24  0.7054658  0.4041047
##   25  0.7042081  0.4011766
##   26  0.7054814  0.4041193
##   27  0.7141925  0.4216292
##   28  0.7104581  0.4141541
##   29  0.7142003  0.4211373
##   30  0.7216925  0.4369388
## 
## Accuracy was used to select the optimal model using the largest value.
## The final value used for the model was k = 8.

Hasil di atas menunjukkan bahwa nilai k yang menghasilkan akurasi tertinggi berdasarkan validasi silang adalah k=8 yaitu sebesar 0.7266. Namun, perlu diingat bahwa nilai tersebut adalah berdasarkan data latih. Kita perlu mengukur performa sebenarnya menggunakan data uji seperti sebelumnya. Evaluasi pada data uji menunjukkan nilai akurasi sebesar 0,7047 sementara nilai sensitivity sebesar 0,7366 dan specificity sebesar 0,6667.

set.seed(100)

# Membuat prediksi untuk data uji
predictions <- predict(knn.grid, newdata = scaled.data.test)

# Evaluasi model
conf_matrix <- confusionMatrix(predictions, data.test$quality)
print(conf_matrix)

## Confusion Matrix and Statistics
## 
##           Reference
## Prediction HIGH LOW
##       HIGH  137  52
##       LOW    49 104
##                                           
##                Accuracy : 0.7047          
##                  95% CI : (0.6532, 0.7525)
##     No Information Rate : 0.5439          
##     P-Value [Acc > NIR] : 8.382e-10       
##                                           
##                   Kappa : 0.4039          
##                                           
##  Mcnemar's Test P-Value : 0.8423          
##                                           
##             Sensitivity : 0.7366          
##             Specificity : 0.6667          
##          Pos Pred Value : 0.7249          
##          Neg Pred Value : 0.6797          
##              Prevalence : 0.5439          
##          Detection Rate : 0.4006          
##    Detection Prevalence : 0.5526          
##       Balanced Accuracy : 0.7016          
##                                           
##        'Positive' Class : HIGH            
##

Selamat mencoba!

Sumber: Algoritma K-Nearest Neighbors (KNN) dengan R