Классификация K-ближайших соседей с нуля

Пошаговый пример в R без сторонних библиотек

В этой статье мы рассмотрим пошаговый подход к созданию алгоритма K-ближайших соседей без помощи какой-либо сторонней библиотеки. На практике этот алгоритм должен быть достаточно полезен для нас, чтобы классифицировать наши данные всякий раз, когда мы уже сделали классификацию (в данном случае по цвету), которая послужит отправной точкой для поиска соседей.

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

Обучайте и тестируйте генерацию образцов

Мы создадим два разных набора образцов:

Обучающий набор: он будет содержать 75 % наших рабочих данных, выбранных случайным образом. Этот набор будет использоваться для создания нашей модели.
Тестовый набор: оставшиеся 25 % наших рабочих данных будут использоваться для проверки точности нашей модели за пределами выборки. Как только наши прогнозы для этих 25% будут сделаны, мы проверим «процент правильных классификаций», сравнив прогнозы с реальными значениями.

# Load Data
library(readr)
RGB <- as.data.frame(read_csv("RGB.csv"))
RGB$x <- as.numeric(RGB$x)
RGB$y <- as.numeric(RGB$y)
print("Working data ready")
# Training Dataset
smp_siz = floor(0.75*nrow(RGB))
train_ind = sample(seq_len(nrow(RGB)),size = smp_siz)
train =RGB[train_ind,]
# Testting Dataset
test=RGB[-train_ind,]
OriginalTest <- test
paste("Training and test sets done")

Тренировочные данные

Мы можем заметить, что данные нашего поезда разделены на 3 кластера в зависимости от цвета.

# We plot test colored datapoints
library(ggplot2)
colsdot <- c("Blue" = "blue", "Red" = "darkred", "Green" = "darkgreen")
ggplot() + 
  geom_tile(data=train,mapping=aes(x, y), alpha=0) +
  ##Ad tiles according to probabilities
  ##add points
  geom_point(data=train,mapping=aes(x,y, colour=Class),size=3 ) + 
  scale_color_manual(values=colsdot) +
  #add the labels to the plots
  xlab('X') + ylab('Y') + ggtitle('Train Data')+
  #remove grey border from the tile
  scale_x_continuous(expand=c(0,.05))+scale_y_continuous(expand=c(0,.05))

Тестовые данные

Несмотря на то, что мы знаем исходную цветовую классификацию наших тестовых данных, мы попытаемся создать модель, которая может угадать свой цвет, основываясь исключительно на обоснованном предположении. Для этого мы удалим их оригинальные цвета и сохраним их только для целей тестирования; как только наша модель сделает свой прогноз, мы сможем рассчитать точность модели, сравнив оригинал с нашим прогнозом.

# We plot test colored datapoints
colsdot <- c("Blue" = "blue", "Red" = "darkred", "Green" = "darkgreen")
ggplot() + 
  geom_tile(data=test,mapping=aes(x, y), alpha=0) +
  ##Ad tiles according to probabilities
  ##add points
  geom_point(data=test,mapping=aes(x,y),size=3 ) + 
  scale_color_manual(values=colsdot) +
  #add the labels to the plots
  xlab('X') + ylab('Y') + ggtitle('Test Data')+
  #remove grey border from the tile
  scale_x_continuous(expand=c(0,.05))+scale_y_continuous(expand=c(0,.05))

Алгоритм K-ближайших соседей

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

В частности, нам необходимо:

Нормализация данных: хотя в данном случае это не требуется, поскольку все значения имеют одинаковую шкалу (десятичные числа от 0 до 1), рекомендуется нормализовать их, чтобы получить «стандартную метрику расстояния». .
Определить, как мы измеряем расстояние. Мы можем определить расстояние между двумя точками в этом двумерном наборе данных как евклидово расстояние между ними. Мы рассчитаем расстояния L1 (сумма абсолютных разностей) и L2 (сумма квадратов разностей), хотя окончательные результаты будут рассчитаны с использованием L2, так как он более неумолим, чем L1.
Расчет расстояний: нам нужно рассчитать расстояние между каждой проверенной точкой данных и каждым значением в нашем наборе данных поезда. Нормализация здесь имеет решающее значение, поскольку в случае строения тела расстояние по весу (1 кг) и росту (1 м) несопоставимо. Мы можем ожидать большее отклонение в KG, чем в метрах, что приведет к неверным общим расстояниям.
Сортировка расстояний. После того, как мы вычислим расстояние между каждой тестовой и тренировочной точками, нам нужно отсортировать их в порядке убывания.
Выбор лучших K ближайших соседей: мы выберем первые K ближайших точек данных поезда, чтобы проверить, к какой категории (цветам) они принадлежат, чтобы также назначить эту категорию нашей тестируемой точке. Поскольку мы можем использовать несколько соседей, мы можем получить несколько категорий, и в этом случае мы должны вычислить вероятность.

# We define a function for prediction
KnnL2Prediction <- function(x,y,K) {
    
  # Train data
  Train <- train
  # This matrix will contain all X,Y values that we want test.
  Test <- data.frame(X=x,Y=y)
    
  # Data normalization
  Test$X <- (Test$X - min(Train$x))/(min(Train$x) - max(Train$x))
  Test$Y <- (Test$Y - min(Train$y))/(min(Train$y) - max(Train$y))
  Train$x <- (Train$x - min(Train$x))/(min(Train$x) - max(Train$x))
  Train$y <- (Train$y - min(Train$y))/(min(Train$y) - max(Train$y))
  # We will calculate L1 and L2 distances between Test and Train values.
  VarNum <- ncol(Train)-1
  L1 <- 0
  L2 <- 0
  for (i in 1:VarNum) {
    L1 <- L1 + (Train[,i] - Test[,i])
    L2 <- L2 + (Train[,i] - Test[,i])^2
  }
    
  # We will use L2 Distance
  L2 <- sqrt(L2)
  
  # We add labels to distances and sort
  Result <- data.frame(Label=Train$Class,L1=L1,L2=L2)
  
  # We sort data based on score
  ResultL1 <-Result[order(Result$L1),]
  ResultL2 <-Result[order(Result$L2),]
  
  # Return Table of Possible classifications
  a <- prop.table(table(head(ResultL2$Label,K)))
  b <- as.data.frame(a)
  return(as.character(b$Var1[b$Freq == max(b$Freq)]))
}

Поиск правильного параметра K с помощью перекрестной проверки

Для этого мы будем использовать метод, называемый «перекрестная проверка». Это означает, что мы будем делать прогнозы в самих обучающих данных и повторять их для множества различных значений K для множества различных сверток или перестановок данных. Как только мы закончим, мы усредним наши результаты и получим лучший K для нашего алгоритма «K-ближайших» соседей.

# We will use 5 folds
FoldSize = floor(0.2*nrow(train)) 
# Fold1
piece1 = sample(seq_len(nrow(train)),size = FoldSize ) 
Fold1 = train[piece1,]
rest = train[-piece1,] 
# Fold2
piece2 = sample(seq_len(nrow(rest)),size = FoldSize)
Fold2 = rest[piece2,]
rest = rest[-piece2,] 
# Fold3
piece3 = sample(seq_len(nrow(rest)),size = FoldSize)
Fold3 = rest[piece3,]
rest = rest[-piece3,] 
# Fold4
piece4 = sample(seq_len(nrow(rest)),size = FoldSize)
Fold4 = rest[piece4,]
rest = rest[-piece4,] 
# Fold5
Fold5 <- rest
# We make folds
Split1_Test <- rbind(Fold1,Fold2,Fold3,Fold4)
Split1_Train <- Fold5
Split2_Test <- rbind(Fold1,Fold2,Fold3,Fold5)
Split2_Train <- Fold4
Split3_Test <- rbind(Fold1,Fold2,Fold4,Fold5)
Split3_Train <- Fold3
Split4_Test <- rbind(Fold1,Fold3,Fold4,Fold5)
Split4_Train <- Fold2
Split5_Test <- rbind(Fold2,Fold3,Fold4,Fold5)
Split5_Train <- Fold1
# We select best K
OptimumK <- data.frame(K=NA,Accuracy=NA,Fold=NA)
results <- train
for (i in 1:5) {
  if(i == 1) {
    train <- Split1_Train
    test <- Split1_Test
  } else if(i == 2)  {
    train <- Split2_Train
    test <- Split2_Test
  } else if(i == 3)  {
    train <- Split3_Train
    test <- Split3_Test
  } else if(i == 4)  {
    train <- Split4_Train
    test <- Split4_Test
  } else if(i == 5)  {
    train <- Split5_Train
    test <- Split5_Test
  }
    for(j in 1:20) {
      results$Prediction <- mapply(KnnL2Prediction, results$x, results$y,j)
      # We calculate accuracy
      results$Match <- ifelse(results$Class == results$Prediction, 1, 0)
      Accuracy <- round(sum(results$Match)/nrow(results),4)
      OptimumK <- rbind(OptimumK,data.frame(K=j,Accuracy=Accuracy,Fold=paste("Fold",i)))
    
    }
}
OptimumK <- OptimumK [-1,]
MeanK <- aggregate(Accuracy ~ K, OptimumK, mean)
ggplot() + 
  geom_point(data=OptimumK,mapping=aes(K,Accuracy, colour=Fold),size=3 ) +
  geom_line(aes(K, Accuracy, colour="Moving Average"), linetype="twodash", MeanK) +
  scale_x_continuous(breaks=seq(1, max(OptimumK$K), 1))

Как видно на графике выше, мы можем наблюдать, что точность прогнозирования нашего алгоритма находится в диапазоне 88%-95% для всех сгибов и снижается от K = 3 и далее. Мы можем наблюдать самые высокие стабильные результаты точности при K = 1 (3 также является хорошей альтернативой).

Прогнозирование на основе первых ближайших соседей.

Точность модели

# Predictions over our Test sample
test <- OriginalTest
K <- 1
test$Prediction <- mapply(KnnL2Prediction, test$x, test$y,K)
head(test,10)
# We calculate accuracy
test$Match <- ifelse(test$Class == test$Prediction, 1, 0)
Accuracy <- round(sum(test$Match)/nrow(test),4)
print(paste("Accuracy of ",Accuracy*100,"%",sep=""))

Как видно из приведенных выше результатов, мы можем ожидать «угадывания правильного класса или цвета» в 93% случаев.

Исходные цвета

Ниже мы можем наблюдать исходные цвета или классы нашего тестового образца.

ggplot() + 
  geom_tile(data=test,mapping=aes(x, y), alpha=0) +
  geom_point(data=test,mapping=aes(x,y,colour=Class),size=3 ) + 
  scale_color_manual(values=colsdot) +
  xlab('X') + ylab('Y') + ggtitle('Test Data')+
  scale_x_continuous(expand=c(0,.05))+scale_y_continuous(expand=c(0,.05))

Предсказанные цвета

Используя наш алгоритм, мы получаем следующие цвета для нашего изначально бесцветного набора данных.

ggplot() + 
  geom_tile(data=test,mapping=aes(x, y), alpha=0) +
  geom_point(data=test,mapping=aes(x,y,colour=Prediction),size=3 ) + 
  scale_color_manual(values=colsdot) +
  xlab('X') + ylab('Y') + ggtitle('Test Data')+
  scale_x_continuous(expand=c(0,.05))+scale_y_continuous(expand=c(0,.05))

Как видно на графике выше, несмотря на то, что наш алгоритм правильно классифицировал большинство точек данных, он потерпел неудачу с некоторыми из них (отмечены красным).

Ограничения на принятие решений

Наконец, мы можем визуализировать наши «пределы принятия решений» по нашему исходному набору тестовых данных. Это обеспечивает отличное визуальное представление того, насколько хорошо наша модель классифицирует наши данные и пределы ее классификационного пространства.

Проще говоря, мы смоделируем 160 000 точек данных (матрица 400x400) в пределах диапазона нашего исходного набора данных, который при последующем построении заполнит большинство пустых пространств цветами. Это поможет нам подробно описать, как наша модель будет классифицировать это 2D-пространство в рамках изученных классов цветов. Чем больше точек мы создадим, тем лучше будет наше «разрешение», как у пикселей в телевизоре.

# We calculate background colors
x_coord = seq(min(train[,1]) - 0.02,max(train[,1]) + 0.02,length.out = 40)
y_coord = seq(min(train[,2]) - 0.02,max(train[,2]) + 0.02, length.out = 40)
coord = expand.grid(x = x_coord, y = y_coord)
coord[['prob']] = mapply(KnnL2Prediction, coord$x, coord$y,K)
# We calculate predictions and plot decition area
colsdot <- c("Blue" = "blue", "Red" = "darkred", "Green" = "darkgreen")
colsfill <- c("Blue" = "#aaaaff", "Red" = "#ffaaaa", "Green" = "#aaffaa")
ggplot() + 
  geom_tile(data=coord,mapping=aes(x, y, fill=prob), alpha=0.8) +
  geom_point(data=test,mapping=aes(x,y, colour=Class),size=3 ) + 
  scale_color_manual(values=colsdot) +
  scale_fill_manual(values=colsfill) +
  xlab('X') + ylab('Y') + ggtitle('Decision Limits')+
  scale_x_continuous(expand=c(0,0))+scale_y_continuous(expand=c(0,0))

Как видно выше, цветная область представляет области, которые наш алгоритм определил бы как «цветную точку данных». Понятно, почему не удалось правильно классифицировать некоторые из них.

Последние мысли

K-ближайшие соседи — это простой алгоритм, который, кажется, дает отличные результаты. Несмотря на то, что здесь мы можем классифицировать объекты на глаз, эта модель также работает в случаях более высоких измерений, когда мы не можем просто наблюдать за ними невооруженным глазом. Чтобы это работало, нам нужен обучающий набор данных с существующими классификациями, который мы позже будем использовать для классификации данных вокруг него, что означает, что это алгоритм контролируемого машинного обучения.

К сожалению, этот метод представляет трудности в таких сценариях, как наличие сложных шаблонов, которые не могут быть представлены простым прямым расстоянием, как в случае радиальных или вложенных кластеров. У него также есть проблема с производительностью, поскольку для каждой классификации новой точки данных нам нужно сравнивать ее с каждой отдельной точкой в нашем обучающем наборе данных, что требует больших ресурсов и времени, поскольку требует репликации и итерации полного набора.