k-nearest neighbors Distance – kNNDist

By | October 23, 2021
1,487 Views

— k-nearest neighbors Distance – kNNDist  adalah salah satu function yang digunakan menghitung nilai eucleid distance antara i dengan i+1 … n pada sebuah dataset. Function KnnDist seringkali digunakan untuk menghitung jumlah K / kelas pada algoritma dbscan. Algoritma Clustering DBScan berbeda dengan KMeans Clustering, dimana untuk KMeans Clustering terlebih dahulu ditentukan jumlah K/kelas nya, adapun untuk DBScan menggunakan minOBj (minimal anggota pada setiap kelas) dan epsilon sebagai jarak antar record.

function k-nearest neighbors Distance – kNNDist

Lebih jelasnya bisa kalian baca dokumentasinya disini https://www.rdocumentation.org/packages/dbscan/versions/1.1-5/topics/kNNdist  –

Fast calculation of the k-nearest neighbor distances in a matrix of points. The plot can be used to help find a suitable value for the eps neighborhood for DBSCAN. Look for the knee in the plot.

Untuk menggunakannnya pastikan kalian sudah install package dbscan. yuk kita coba saja k-nearest neighbors Distance – kNNDist menggunakan RStudio

data(iris)
iris <- as.matrix(iris[,1:4])

## Find the 4-NN distance for each observation (see ?kNN
## for different search strategies)
jarak_knn = kNNdist(iris, k=3,all=TRUE)
head(jarak_knn,5)

hasilnya

             1         2         3
[1,] 0.1000000 0.1414214 0.1414214
[2,] 0.1414214 0.1414214 0.1414214
[3,] 0.1414214 0.2449490 0.2645751
[4,] 0.1414214 0.1732051 0.2236068
[5,] 0.1414214 0.1414214 0.1732051

tapi kalian tentu penasaran dengan angka hasil diatas, bukan? data iris diatas kita hitung jarak terkecil setiap anggota yang dirangking 3 terkecil dengan arti bahwa jarak terkecil yang akan diambil/terbaik. Untuk lebih jelasnya bisa kalian gunakan function kNN di RStudio.

k-nearest neighbors – KNN

Kita langsung gunakan saja properties id untuk menampilkan id

jarak_knn_detail = kNN(iris,k=3)
head(jarak_knn_detail$dist,5)
head(jarak_knn_detail$id,5)

hasilnya

> head(jarak_knn_detail$dist,5)
             1         2         3
[1,] 0.1000000 0.1414214 0.1414214
[2,] 0.1414214 0.1414214 0.1414214
[3,] 0.1414214 0.2449490 0.2645751
[4,] 0.1414214 0.1732051 0.2236068
[5,] 0.1414214 0.1414214 0.1732051
> head(jarak_knn_detail$id,5)
      1  2  3
[1,] 18  5 40
[2,] 35 46 13
[3,] 48  4  7
[4,] 48 30 31
[5,] 38  1 18

artinya adalah record 1 punya jarak terpendek dengan record ke 18, 5, dan 40. Cara hitung  nya adalah, yuk kita buat function buat hitung jarak eucledian.

#atau cara dibawah ini  bila ingin membuktikan
ecl <- function(a, b) sqrt(sum((a - b)^2))

Kita lakukan saja looping biar mudah

no = c(1:nrow(iris))
isi_jarak = c(1:nrow(iris))

record_ke = 1

for(i in c(1:nrow(iris))){
    jarak = ecl(iris[record_ke,],iris[i,])
    isi_jarak[i]=jarak
}

jarak_knn_manual = data.frame(no,isi_jarak)
jarak_knn_manual = jarak_knn_manual %>% arrange(isi_jarak)
head(jarak_knn_manual,5)

hasilnya

  no isi_jarak
1  1 0.0000000
2 18 0.1000000
3  5 0.1414214
4 40 0.1414214
5 28 0.1414214

kalian bisa melihat 18, 5, dan 40 adalah jarak terkecil 3 besar, kita coba dengan record_ke = 2 hasilnya

  no isi_jarak
1  2 0.0000000
2 35 0.1414214
3 46 0.1414214
4 13 0.1414214
5 10 0.1732051

record 2 punya jarak terkecil dengan record 35, 46, dan 13. Bila kode diatas terasa ribet karena bila ada jutaan record tentu looping jadi terasa sangat lambat! maka kalian bisa gunakan teknik apply dengan cara berikut

jarak = apply(iris,1, function(x) ecl(iris[record_ke,],x))

Kita susun menjadi berikut

jarak_knn_manual2 = data.frame(no,jarak)
jarak_knn_manual2 = jarak_knn_manual2 %>% arrange(jarak)
head(jarak_knn_manual2,5)

hasilnya

  no     jarak
1  2 0.0000000
2 35 0.1414214
3 46 0.1414214
4 13 0.1414214
5 10 0.1732051

Kesimpulan

kNNDist sesuai namanya k-Nearest Neighbor distance yang bertujuan untuk menghitung jarak terkecil antar record satu dengan yang lain

See also  Cara menghitung term frequency dan inverse document frequency

ref:

https://softscients.com/2020/03/26/klasifikasi-knn/#gsc.tab=0

https://medium.com/bee-solution-partners/cara-kerja-algoritma-k-nearest-neighbor-k-nn-389297de543e

https://www.rdocumentation.org/packages/dbscan/versions/1.1-5/topics/kNNdist

https://search.r-project.org/CRAN/refmans/dbscan/html/kNN.html

https://www.statology.org/euclidean-distance-in-r/