Внедрение KNN с различными метриками расстояния с использованием R - PullRequest
Новая
       38

Внедрение KNN с различными метриками расстояния с использованием R

0 голосов
/ 19 мая 2018

Я работаю над набором данных, чтобы сравнить влияние различных метрик расстояния.Я использую алгоритм KNN.

Алгоритм KNN в R по умолчанию использует евклидово расстояние.Поэтому я написал свой собственный.Я хотел бы найти количество правильных совпадений меток классов между ближайшим соседом и целью.

Сначала я подготовил данные.Затем я назвал данные (wdbc_n), я выбрал K = 1.Я использовал евклидово расстояние в качестве теста. 

library(philentropy)
knn <- function(xmat, k,method){
  n <- nrow(xmat)
  if (n <= k) stop("k can not be more than n-1")
  neigh <- matrix(0, nrow = n, ncol = k)
  for(i in 1:n) {
    ddist<- distance(xmat, method)  
    neigh[i, ] <- order(ddist)[2:(k + 1)]
  }
  return(neigh)
}
wdbc_nn <-knn(wdbc_n ,1,method="euclidean")

Надеясь получить аналогичный результат в статье («Об удивительном поведении метрик расстояния в многомерном пространстве») (https://bib.dbvis.de/uploadedFiles/155.pdf, страница431, таблица 3).

Мой вопрос:

Правильно я или нет с кодами?

Буду весьма признателен за любые предложения или рекомендации, которые меня направят.

РЕДАКТИРОВАТЬ

Мои данные (рак молочной железы-Висконсин) (WDBC) имеют размер 

569  32

После нормализации ипри удалении столбца id и target размерность составляет 

dim(wdbc_n)
569  30

Разделение поезда и теста задается как 

wdbc_train<-wdbc_n[1:469,]
wdbc_test<-wdbc_n[470:569,]

1 Ответ

0 голосов
/ 07 декабря 2018

Правильно я или нет с кодами?

Ваш код неверен.

Вызов функции расстояния занимал около 3 секунд каждый раз на моем довольнонедавний ПК, поэтому я сделал только первые 30 строк для k = 3 и заметил, что каждая строка матрицы соседей была идентична.Это почему?Посмотрите на эту строку: 

ddist<- distance(xmat, method)

Каждый цикл подает всю матрицу xmat на функцию расстояния, а затем использует только первую строку из полученной матрицы.Это вычисляет расстояние между строками обучающего набора и делает это n раз, отбрасывая каждую строку, кроме первой.Что не то, что вы хотите сделать.Предполагается, что алгоритм knn рассчитывает для каждой строки в тестовом наборе расстояние с каждой строкой в ​​обучающем наборе.

Давайте рассмотрим документацию для функции расстояния:

расстояние (x, method = "евклидово", p = NULL, test.na = TRUE, unit = "log", est.prob = NULL)

xa числовой data.frame или матрица (сохранениевекторы вероятности) или числовое значение data.frame или матрицы (если указан est.prob).

(...)

в случае nrow (x) = 2: одинзначение расстояния.в случае nrow (x)> 2: матрица расстояний, в которой хранятся значения расстояний для всех парных сравнений векторов вероятности.

В вашем конкретном случае (классификация knn) вы хотите использовать двухстрочную версию.

И последнее: вы использовали order , который будет возвращать позицию k наибольших расстояний в векторе ddist.Я думаю, что вам нужны сами расстояния, поэтому вам нужно использовать sort вместо order .

На основе вашего кода и примера в Lantz (2013)то, на чем, казалось, ваш код основан, вот полное рабочее решение.Я позволил себе добавить несколько строк для создания автономной программы.

Автономные рабочие решения 

library(philentropy)
normalize <- function(x) {
 return ((x - min(x)) / (max(x) - min(x)))
}

knn <- function(train, test, k, method){
  n.test <- nrow(test)
  n.train <- nrow(train)
  if (n.train + n.test <= k) stop("k can not be more than n-1")
  neigh <- matrix(0, nrow = n.test, ncol = k) 
  ddist <- NULL
  for(i in 1:n.test) {
    for(j in 1:n.train) {
      xmat <- rbind(test[i,], train[j,]) #we make a 2 row matrix combining the current test and train rows
      ddist[j] <- distance(as.data.frame(xmat), method, k)  #then we calculate the distance and append it to the ddist vector.
    }
    neigh[i, ] <- sort(ddist)[2:(k + 1)] 
  }
  return(neigh)
}

wbcd <- read.csv("https://resources.oreilly.com/examples/9781784393908/raw/ac9fe41596dd42fc3877cfa8ed410dd346c43548/Machine%20Learning%20with%20R,%20Second%20Edition_Code/Chapter%2003/wisc_bc_data.csv")
rownames(wbcd) <- wbcd$id
wbcd$id <- NULL
wbcd_n <- as.data.frame(lapply(wbcd[2:31], normalize))

wbcd_train<-wbcd_n[1:469,]
wbcd_test<-wbcd_n[470:549,]
wbcd_nn <-knn(wbcd_train, wbcd_test ,3, method="euclidean")

Обратите внимание, что это решение может быть медленнымиз-за многочисленных (100 раз 469) вызовов функции расстояния.Однако, поскольку мы подаем только 2 строки за раз в функцию расстояния, это делает время выполнения управляемым.

Теперь это работает?

Две первые строки теста с использованием пользовательского knnfunction: 

          [,1]      [,2]      [,3]
[1,] 0.3887346 0.4051762 0.4397497
[2,] 0.2518766 0.2758161 0.2790369

Давайте сравним с эквивалентной функцией в пакете FNN: 

library(FNN)
alt.class <- get.knnx(wbcd_train, wbcd_test, k=3, algorithm = "brute")
alt.class$nn.dist

          [,1]      [,2]      [,3]
[1,] 0.3815984 0.3887346 0.4051762
[2,] 0.2392102 0.2518766 0.2758161

Вывод: не слишком потертый.

...