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

Алгоритм k-ближайших соседей продолжает серию статей о Топ-10 data mining алгоритмах.

kNN (k-Nearest Neighbors) – это алгоритм классификации, однако это – ленивый классификатор.

Что значит ленивый классификатор? Это означает, что в процессе обучения он не делает ничего, а только хранит тренировочные данные. Он начинает классификацию только тогда, когда появляются новые немаркированные данные.

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

Какими классификаторами являются C4.5, SVM и AdaBoost? В отличие от kNN, они все – активные классификаторы.

Вот почему:

C4.5 строит дерево решений в процессе обучения;

SVM строит гиперплоскость;

AdaBoost строит ансамблевую классификацию.

Что делает kNN? kNN не строит никакую классификационную модель. Вместо этого он просто сохраняет размеченные тренировочные данные.

Когда появляется новые неразмеченные данные, kNN проходит по 2 базовым шагам:

Сначала он ищет k ближайших размеченных точек данных – другими словами, k ближайших соседей.

Затем, используя классы соседей, kNN решает, как лучше классифицировать новые данные.

Как kNN понимает, какие точки находятся ближе всего? Для непрерывных данных kNN использует дистанционную метрику, например, Евклидову дистанцию (метрику). Выбор метрики зависит от типа данных. Некоторые советуют даже выбирать дистанционную метрику на основании тренировочных данных. Есть очень много нюансов, описанных во многих работах по дистанционным метрикам kNN.

При работе с дискретными данными, они сначала преобразуются в непрерывные. Вот 2 примера:

Использование расстояния Хэмминга как метрики для определения «близости» двух текстовых строк;

Преобразование дискретных данных в бинарные числа.

2 треда со Stack Overflow предлагают еще несколько решений:

kNN классификация категорийных данных;

Использование kNN в R с категорийными величинами.

Как kNN классифицирует новые данные, если соседи «не согласны»? kNN легко решает, к какому классу отнести данные, если все соседи принадлежат одному классу. Логика проста – если все соседи «согласны», то новые данные отводятся в их класс.

Как kNN решает, к какому классу отнести данные, если соседи не принадлежат одному классу?

Для решения этой проблемы используются 2 классические техники:

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

2. Проделать то же самое, но дать ближайшим соседям больший вес. Самый простой способ сделать это – использовать квантиль расстояния. Если сосед отстоит на 5 единиц, то его вес будет 1/5. При увеличении дистанции вес становится все меньше и меньше. Это как раз то, что нам нужно.

Требует ли этот метод обучения или он самообучающийся? Этот метод требует обучения, поскольку kNN необходим размеченный набор данных.

Почему именно kNN? kNN легок в понимании и легко реализуем – это две главные причины. В зависимости от выбора дистанционной метрики, kNN может показывать достаточно точные результаты.

Вот 5 вещей, за которыми нужно следить:

1. kNN может быть очень ресурсозатратным, если пытаться определить ближайших соседей на большом наборе данных.
2. Зашумленные данные могут испортить kNN-классификацию.
3. Нужно учитывать количество значений. Характеристики с большим количеством значений могут оказывать влияние на дистанционную метрику, по отношению к характеристикам с меньшим количеством значений.
4. Поскольку обработка данных «откладывается», kNN обычно требует больше места, чем активные классификаторы.
5. Выбор правильной дистанционной метрики очень важен для точности kNN.

Где он используется? Существуют несколько реализаций:

MATLAB kNN классификация

scikit-learn KNeighborsClassifier

kNN классификация в R

Источник

Алгоритм kNN (видео)

Реализация kNN в R

Документация: пакет «kknn», другой knn

Пример 1. Классификация ирисов

library(class) #Has the knn function
set.seed(4948493) #Set the seed for reproducibility
#Sample the Iris data set (70% train, 30% test)
ir_sample<-sample(1:nrow(iris),size=nrow(iris)*.7)
ir_train<-iris[ir_sample,] #Select the 70% of rows
ir_test<-iris[-ir_sample,] #Select the 30% of rows
 
#First Attempt to Determine Right K####
iris_acc<-numeric() #Holding variable
 
for(i in 1:50){
 #Apply knn with k = i
 predict<-knn(ir_train[,-5],ir_test[,-5],
 ir_train$Species,k=i)
 iris_acc<-c(iris_acc,
 mean(predict==ir_test$Species))
}
#Plot k= 1 through 30
plot(1-iris_acc,type="l",ylab="Error Rate",
 xlab="K",main="Error Rate for Iris With Varying K")
 
#Try many Samples of Iris Data Set to Validate K####
trial_sum<-numeric(20)
trial_n<-numeric(20)
set.seed(6033850)
for(i in 1:100){
 ir_sample<-sample(1:nrow(iris),size=nrow(iris)*.7)
 ir_train<-iris[ir_sample,]
 ir_test<-iris[-ir_sample,]
 test_size<-nrow(ir_test)
 for(j in 1:20){
 predict<-knn(ir_train[,-5],ir_test[,-5],
 ir_train$Species,k=j)
 trial_sum[j]<-trial_sum[j]+sum(predict==ir_test$Species)
 trial_n[j]<-trial_n[j]+test_size
 }
}
 
plot(1-trial_sum / trial_n,type="l",ylab="Error Rate",
 xlab="K",main="Error Rate for Iris With Varying K (100 Samples)")

library(class) #Has the knn function

set.seed(4948493) #Set the seed for reproducibility

#Sample the Iris data set (70% train, 30% test)

ir_sample<-sample(1:nrow(iris),size=nrow(iris)*.7)

ir_train<-iris[ir_sample,] #Select the 70% of rows

ir_test<-iris[-ir_sample,] #Select the 30% of rows

#First Attempt to Determine Right K####

iris_acc<-numeric() #Holding variable

for(i in 1:50){

#Apply knn with k = i

predict<-knn(ir_train[,-5],ir_test[,-5],

ir_train$Species,k=i)

iris_acc<-c(iris_acc,

mean(predict==ir_test$Species))

}

#Plot k= 1 through 30

plot(1-iris_acc,type="l",ylab="Error Rate",

xlab="K",main="Error Rate for Iris With Varying K")

#Try many Samples of Iris Data Set to Validate K####

trial_sum<-numeric(20)

trial_n<-numeric(20)

set.seed(6033850)

for(i in 1:100){

ir_sample<-sample(1:nrow(iris),size=nrow(iris)*.7)

ir_train<-iris[ir_sample,]

ir_test<-iris[-ir_sample,]

test_size<-nrow(ir_test)

for(j in 1:20){

predict<-knn(ir_train[,-5],ir_test[,-5],

ir_train$Species,k=j)

trial_sum[j]<-trial_sum[j]+sum(predict==ir_test$Species)

trial_n[j]<-trial_n[j]+test_size

}

plot(1-trial_sum / trial_n,type="l",ylab="Error Rate",

xlab="K",main="Error Rate for Iris With Varying K (100 Samples)")

Источник примера 1

Пример 2.

install.packages(c('FNN', 'plyr'))
library(FNN)
library(plyr)

#Here are some random points on the plane to show you the interface
neartop = ldply(1:50, function(i){
  c(  x = rnorm(1)
    , y = 1 + rnorm(1, sd=0.5))
})

nearbottom = ldply(1:50, function(i){
  c(  x = rnorm(1)
    , y = -1 + rnorm(1, sd=0.5))
})

# the first 50 are near the top, the rest are near the bottom
points = rbind(neartop, nearbottom)

#the vector of classification labels is easy to construct. Since the labels are TRUE/FALSE, the question we're asking is, "is this point in the set near the top?"
points[,'label'] = (1:100 < 51)


plot(points$x, points$y)

#split into training/testing sets by sampling 60 numbers from the set of 1--100, using them for training, and the rest for testing.
train_i = sample(1:100, 60)
train = points[train_i,c('x','y')]
test = points[-train_i,c('x','y')]

results = knn(
  train
  , test
  , cpt_vecs
  , cl = points[train_i,'label']
  , k=1) #k = 1 just assigns a point to its nearest neighbor.

#percent correct
sum(points[-train_i,'label'] == results) / nrow(test)

install.packages(c('FNN', 'plyr'))

library(FNN)

library(plyr)

#Here are some random points on the plane to show you the interface

neartop = ldply(1:50, function(i){

c( x = rnorm(1)

, y = 1 + rnorm(1, sd=0.5))

})

nearbottom = ldply(1:50, function(i){

c( x = rnorm(1)

, y = -1 + rnorm(1, sd=0.5))

})

# the first 50 are near the top, the rest are near the bottom

points = rbind(neartop, nearbottom)

#the vector of classification labels is easy to construct. Since the labels are TRUE/FALSE, the question we're asking is, "is this point in the set near the top?"

points[,'label'] = (1:100 < 51)

plot(points$x, points$y)

#split into training/testing sets by sampling 60 numbers from the set of 1--100, using them for training, and the rest for testing.

train_i = sample(1:100, 60)

train = points[train_i,c('x','y')]

test = points[-train_i,c('x','y')]

results = knn(

train

, test

, cpt_vecs

, cl = points[train_i,'label']

, k=1) #k = 1 just assigns a point to its nearest neighbor.

#percent correct

sum(points[-train_i,'label'] == results) / nrow(test)

Источник примера 2

Ещё примерчик

Реализация kNN в Python

Пример 1. Nearest Neighbors regression

# generate sample data
import numpy as np
import matplotlib.pyplot as plt
from sklearn import neighbors

np.random.seed(0)
X = np.sort(5 * np.random.rand(40, 1), axis=0)
T = np.linspace(0, 5, 500)[:, np.newaxis]
y = np.sin(X).ravel()

# Add noise to targets
y[::5] += 1 * (0.5 - np.random.rand(8))

#fit regression model
n_neighbors = 5

for i, weights in enumerate(['uniform', 'distance']):
    knn = neighbors.KNeighborsRegressor(n_neighbors, weights=weights)
    y_ = knn.fit(X, y).predict(T)

    plt.subplot(2, 1, i + 1)
    plt.scatter(X, y, c='k', label='data')
    plt.plot(T, y_, c='g', label='prediction')
    plt.axis('tight')
    plt.legend()
    plt.title("KNeighborsRegressor (k = %i, weights = '%s')" % (n_neighbors,
                                                                weights))

plt.show()

# generate sample data

import numpy as np

import matplotlib.pyplot as plt

from sklearn import neighbors

np.random.seed(0)

X = np.sort(5 * np.random.rand(40, 1), axis=0)

T = np.linspace(0, 5, 500)[:, np.newaxis]

y = np.sin(X).ravel()

# Add noise to targets

y[::5] += 1 * (0.5 - np.random.rand(8))

#fit regression model

n_neighbors = 5

for i, weights in enumerate(['uniform', 'distance']):

knn = neighbors.KNeighborsRegressor(n_neighbors, weights=weights)

y_ = knn.fit(X, y).predict(T)

plt.subplot(2, 1, i + 1)

plt.scatter(X, y, c='k', label='data')

plt.plot(T, y_, c='g', label='prediction')

plt.axis('tight')

plt.legend()

plt.title("KNeighborsRegressor (k = %i, weights = '%s')" % (n_neighbors,

weights))

plt.show()

Источник примера 1

Пример 2. Классификация ирисов

import csv
import random
import math
import operator
 
def loadDataset(filename, split, trainingSet=[] , testSet=[]):
	with open(filename, 'rb') as csvfile:
	    lines = csv.reader(csvfile)
	    dataset = list(lines)
	    for x in range(len(dataset)-1):
	        for y in range(4):
	            dataset[x][y] = float(dataset[x][y])
	        if random.random() < split:
	            trainingSet.append(dataset[x])
	        else:
	            testSet.append(dataset[x])
 
 
def euclideanDistance(instance1, instance2, length):
	distance = 0
	for x in range(length):
		distance += pow((instance1[x] - instance2[x]), 2)
	return math.sqrt(distance)
 
def getNeighbors(trainingSet, testInstance, k):
	distances = []
	length = len(testInstance)-1
	for x in range(len(trainingSet)):
		dist = euclideanDistance(testInstance, trainingSet[x], length)
		distances.append((trainingSet[x], dist))
	distances.sort(key=operator.itemgetter(1))
	neighbors = []
	for x in range(k):
		neighbors.append(distances[x][0])
	return neighbors
 
def getResponse(neighbors):
	classVotes = {}
	for x in range(len(neighbors)):
		response = neighbors[x][-1]
		if response in classVotes:
			classVotes[response] += 1
		else:
			classVotes[response] = 1
	sortedVotes = sorted(classVotes.iteritems(), key=operator.itemgetter(1), reverse=True)
	return sortedVotes[0][0]
 
def getAccuracy(testSet, predictions):
	correct = 0
	for x in range(len(testSet)):
		if testSet[x][-1] == predictions[x]:
			correct += 1
	return (correct/float(len(testSet))) * 100.0
	
def main():
	# prepare data
	trainingSet=[]
	testSet=[]
	split = 0.67
	loadDataset('iris.data', split, trainingSet, testSet)
	print 'Train set: ' + repr(len(trainingSet))
	print 'Test set: ' + repr(len(testSet))
	# generate predictions
	predictions=[]
	k = 3
	for x in range(len(testSet)):
		neighbors = getNeighbors(trainingSet, testSet[x], k)
		result = getResponse(neighbors)
		predictions.append(result)
		print('> predicted=' + repr(result) + ', actual=' + repr(testSet[x][-1]))
	accuracy = getAccuracy(testSet, predictions)
	print('Accuracy: ' + repr(accuracy) + '%')
	
main()

import csv

import random

import math

import operator

def loadDataset(filename, split, trainingSet=[] , testSet=[]):

with open(filename, 'rb') as csvfile:

lines = csv.reader(csvfile)

dataset = list(lines)

for x in range(len(dataset)-1):

for y in range(4):

dataset[x][y] = float(dataset[x][y])

if random.random() < split:

trainingSet.append(dataset[x])

else:

testSet.append(dataset[x])

def euclideanDistance(instance1, instance2, length):

distance = 0

for x in range(length):

distance += pow((instance1[x] - instance2[x]), 2)

return math.sqrt(distance)

def getNeighbors(trainingSet, testInstance, k):

distances = []

length = len(testInstance)-1

for x in range(len(trainingSet)):

dist = euclideanDistance(testInstance, trainingSet[x], length)

distances.append((trainingSet[x], dist))

distances.sort(key=operator.itemgetter(1))

neighbors = []

for x in range(k):

neighbors.append(distances[x][0])

return neighbors

def getResponse(neighbors):

classVotes = {}

for x in range(len(neighbors)):

response = neighbors[x][-1]

if response in classVotes:

classVotes[response] += 1

else:

classVotes[response] = 1

sortedVotes = sorted(classVotes.iteritems(), key=operator.itemgetter(1), reverse=True)

return sortedVotes[0][0]

def getAccuracy(testSet, predictions):

correct = 0

for x in range(len(testSet)):

if testSet[x][-1] == predictions[x]:

correct += 1

return (correct/float(len(testSet))) * 100.0

def main():

# prepare data

trainingSet=[]

testSet=[]

split = 0.67

loadDataset('iris.data', split, trainingSet, testSet)

print 'Train set: ' + repr(len(trainingSet))

print 'Test set: ' + repr(len(testSet))

# generate predictions

predictions=[]

k = 3

for x in range(len(testSet)):

neighbors = getNeighbors(trainingSet, testSet[x], k)

result = getResponse(neighbors)

predictions.append(result)

print('> predicted=' + repr(result) + ', actual=' + repr(testSet[x][-1]))

accuracy = getAccuracy(testSet, predictions)

print('Accuracy: ' + repr(accuracy) + '%')

main()

Источник примера 2

Документация по sklearn.neighbors и другие примеры

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

Алгоритм kNN (видео)

Реализация kNN в R

Реализация kNN в Python

Искать

Недавнее

Тематика

Data Scientist # 1

Данные — новый актив!

Войдите в свой аккаунт