R kknn package and weighted k-nearest neighbors calculations

user_1491868 0
Viewed 278

I'm trying to hand calculate the distance and weight measures that are output from the R kknn package. I'm able to correctly calculate the euclidean distances and inverse weights, when the data are not scaled, as follows:

euclidean distances

sqrt((6-8)^2 + (4-5)^2) = 2.236068

sqrt((6-3)^2 + (4-7)^2) = 4.242641

sqrt((6-7)^2 + (4-3)^2) = 1.414214

inverse weights

1 / (2.236068 / 4.242641) = 1.897368

1 / (1.414214 / 4.242641) = 3.000000.

I'm not seeing how the rectangular weights are calculated because I get:

1/2 * 1 = 0.50

1/2 * 1 = 0.50

and the kknn package gives 1 and 1.

Lastly, I'm having no luck at all calculating distances and weights when the data are scaled. Any help is appreciated because I'm trying to understand how the kknn package works.

library(kknn)

training <- data.frame(class = c(1, 0, 1), height = c(8, 3, 7), weight = c(5, 7, 3))

training

holdouts <- data.frame(class = 1, height = 6, weight = 4)

holdouts

rectangular_no_scale <- kknn(class ~., training, holdouts, distance = 2, kernel = "rectangular", k = 2, scale = FALSE)

rectangular_no_scale[["D"]]

rectangular_no_scale[["W"]]

inversion_no_scale <- kknn(class ~., training, holdouts, distance = 2, kernel = "inv", k = 2, scale = FALSE)

inversion_no_scale[["D"]]

inversion_no_scale[["W"]]

rectangular_with_scale <- kknn(class ~., training, holdouts, distance = 2, kernel = "rectangular", k = 2, scale = TRUE)

rectangular_with_scale[["D"]]

rectangular_with_scale[["W"]]

inversion_with_scale <- kknn(class ~., training, holdouts, distance = 2, kernel = "inv", k = 2, scale = TRUE)

inversion_with_scale[["D"]]

inversion_with_scale[["W"]]
nearest-neighbor r algorithm
1 Answers

The source code of kknn (just type kknn + return in console mode) helps to understand the calculations :

library(kknn)

training <- data.frame(class = c(1, 0, 1), height = c(8, 3, 7), weight = c(5, 7, 3))

training
#>   class height weight
#> 1     1      8      5
#> 2     0      3      7
#> 3     1      7      3

holdouts <- data.frame(class = 1, height = 6, weight = 4)

holdouts
#>   class height weight
#> 1     1      6      4

# Euclidian distance
d <- sqrt((training$height-holdouts$height)^2 +(training$weight-holdouts$weight)^2)
d <- d[order(d)]
d
#> [1] 1.414214 2.236068 4.242641

rectangular_no_scale <- kknn(class ~., training, holdouts, distance = 2, kernel = "rectangular", k = 2, scale = FALSE)

rectangular_no_scale[["D"]]
#> [1] 1.414214 2.236068
d[1:2]
#> [1] 1.414214 2.236068

rectangular_no_scale[["W"]]
#>      [,1] [,2]
#> [1,]    1    1
# 
# source code:
# if (kernel == "rectangular") 
#   W <- matrix(1, nrow = p, ncol = k)
# This is why you get 1,1 : weights are the same and not normalized

inversion_no_scale <- kknn(class ~., training, holdouts, distance = 2, kernel = "inv", k = 2, scale = FALSE)

inversion_no_scale[["D"]]
#> [1] 1.414214 2.236068
d[1:2]
#> [1] 1.414214 2.236068

inversion_no_scale[["W"]]
#>      [,1]     [,2]
#> [1,]    3 1.897367
#
# Source code :
# W <- D/maxdist
# if (kernel == "inv") 
#   W <- 1/W
max(d)/d[1:2]
#> [1] 3.000000 1.897367

rectangular_with_scale <- kknn(class ~., training, holdouts, distance = 2, kernel = "rectangular", k = 2, scale = TRUE)

height_sd <- sqrt(var(training$height))
weight_sd <- sqrt(var(training$weight))
training_scaled <- training
training_scaled$height <- training$height / height_sd
training_scaled$weight <- training$weight / weight_sd
holdouts_scaled <- holdouts
holdouts_scaled$height <- holdouts$height / height_sd
holdouts_scaled$weight <- holdouts$weight / weight_sd

rectangular_with_scale[["D"]]
#> [1] 0.6267832 0.9063270
d_scaled <- sqrt((training_scaled$height-holdouts_scaled$height)^2 +(training_scaled$weight-holdouts_scaled$weight)^2)
d_scaled <- d[order(d_scaled)]
d_scaled
#> [1] 0.6267832 0.9063270 1.8803495

rectangular_with_scale[["W"]]
#>      [,1] [,2]
#> [1,]    1    1
# Same as before : 1,1


inversion_with_scale <- kknn(class ~., training, holdouts, distance = 2, kernel = "inv", k = 2, scale = TRUE)

inversion_with_scale[["D"]]
#> [1] 0.6267832 0.9063270
d_scaled[1:2]
#> [1] 0.6267832 0.9063270

inversion_with_scale[["W"]]
#>      [,1]     [,2]
#> [1,]    3 2.074692
max(d_scaled)/d_scaled[1:2]
#> [1] 3.000000 2.074692

To summarize, rectangular kernel uses identical weights, and normalizing isn't necessary to find the k nearest neighbours, that's why weights are simply set to 1.
Scaling just divides each column by its standard deviation, and then proceeds with the calculations.

user_135133280
Related