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

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

Количество соседей

Буква k в аббревиатуре kNN означает количество образцов, по которым нужно проводить усреднение, чтобы получить конечный результат. Если бы данные были идеальными, то достаточно было бы взять k = 1, то есть выбрать ближайшего соседа и вернуть его цену в качестве ответа. Но в реальном мире всегда существуют отклонения от идеала. Чтобы их смоделировать, мы специально добавили шум (случайным образом увеличили или уменьшили цену на 20%). Кому-то повезет совершить очень выгодную сделку, а неинформированный покупатель может здорово переплатить, ориентируясь на ближайшего соседа. Поэтому, чтобы подавить шум, лучше взять нескольких соседей и усреднить для них цену.

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

Рис. 8.1. Алгоритм kNN в случае, когда соседей слишком мало

Обратите внимание, что прогноз цены слишком сильно зависит от случайных вариаций. Если бы вы пользовались этой далекой от плавности кривой для выработки прогноза, то решили бы, что между 15-летним и 16-летним вином существует большой ценовой скачок, хотя на самом деле это всего лишь результат различия в цене двух конкретных бутылок.

С другой стороны, выбор слишком большого числа соседей снижает точность, поскольку алгоритм будет усреднять данные по образцам,

Рис. 8.2. Алгоритм kNN в случае, когда соседей слишком много

которые совсем не похожи на изучаемый. На рис. 8.2 представлен тот же самый набор данных, но кривая цен усреднена по 20 ближайшим соседям.

Понятно, что усреднение слишком многих цен приводит к недооценке вин, достигших 25-летней отметки. Выбор правильного количества соседей можно делать вручную или воспользоваться оптимизацией.

Определение подобия

Первое, что необходимо сделать для применения алгоритма kNN, – найти способ измерения схожести образцов. На страницах этой книги вы уже встречались с различными метриками. В данном случае мы воспользуемся евклидовым расстоянием. Добавьте функцию euclidian в файл numpredict.py: def euclidean(v1,v2): d=0.0

for i in range(len(v1)):

d+=(v1[i]-v2[i])**2 return math.sqrt(d)

В интерактивном сеансе вызовите эту функцию для какой-нибудь пары точек из набора данных:

>>> reload(numpredict)

<module ‘numpredict’ from ‘numpredict.py’>

>>> data[0][‘input’]

(82.720398223643514, 49.21295829683897)

>>> data[1][‘input’]

(98.942698715228076, 25.702723509372749)

>>> numpredict.euclidean(data[0][‘input’],data[1][‘input’])

28.56386131112269

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

Реализация алгоритма k-ближайших соседей

Алгоритм kNN реализовать довольно просто. Он потребляет много вычислительных ресурсов, но обладает одним достоинством – не требует повторного обучения при каждом добавлении новых данных. Добавьте в файл numpredict.py функцию getdistances, которая вычисляет расстояния от заданного образца до всех остальных образцов в исходном наборе данных:

def getdistances(data,vec1): distancelist=[] for i in range(len(data)): vec2=data[i][‘input’]

distancelist.append((euclidean(vec1,vec2),i)) distancelist.sort( ) return distancelist

Эта функция в цикле вызывает функцию distance, передавая ей заданный вектор и каждый из остальных векторов в наборе данных. Вычисленные расстояния помещаются в большой список. Затем этот список сортируется, так что ближайший образец оказывается в начале. Алгоритм kNN выполняет усреднение по первым k образцам в получившемся списке. Добавьте в файл numpredict.py функцию knnestimate: def knnestimate(data,vec1,k=3):

#    Получить отсортированный список расстояний dlist=getdistances(data,vec1)

avg=0.0

#    Усреднить по первым k образцам for i in range(k):

idx=dlist[i][1] avg+=data[idx][‘result’] avg=avg/k return avg

Теперь можно получить оценку цены нового образца: >>> reload(numpredict)

>>> numpredict.knnestimate(data,(95.0,3.0))

29.176138546872018

>>> numpredict.knnestimate(data,(99.0,3.0))

22.356856188108672

>>> numpredict.knnestimate(data,(99.0,5.0)) 37.610888778473793

>>> numpredict.wineprice(99.0,5.0) # Получить фактическую цену

30.306122448979593

>>> numpredict.knnestimate(data,(99.0,5.0),k=1) # Уменьшить число соседей

38.078819347238685

Поэкспериментируйте с различными параметрами и значениями k и посмотрите, как это отразится на результатах.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100