Метод k-ближайших соседей

Понятия метода k-ближайших соседей

Здравствуйте и вновь добро пожаловать на занятия по теме «Машинное обучение с учителем на языке Python».

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

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

Не забывайте, что основная наша задача – обучение и прогнозирование. Обучение простое: нам нужно лишь хранить все обучающие данные, чтобы мы могли просмотреть их позже. Прогнозирование – вот где идёт основная работа.

У нас есть новая точка, для которой мы не знаем метку. Предположим, k = 3, то есть у нас метод 3 ближайших соседей. Тогда мы просто смотрим на три ближайшие к этой новой точки, и если большинство из них красные – то наш прогноз «красная», если большинство зелёные – то наш прогноз «зелёная». В нашем случае большинство – зелёные, поэтому мы выбираем ответ «зелёная». Если бы мы использовали 5 ближайших соседей, то наш ответ был бы «красная», поскольку три из пяти точек – красные.

Хотя концепция метода k-ближайших соседей проста, её реализация может оказаться сложной. Для начала реализуем метод 1-ближайшего соседа. Это простейший случай, поскольку нам надо лишь отслеживать минимальное расстояние.

def predict(x0):

    closest_distance = inf, closest_class = -1

    for x, y in training_data:

    d = dist(x, x0)

    if d < closest_distance:

        closest_distance = d, closest_class = y

    return closest_class

Отслеживание же произвольного количества расстояний отнюдь не так просто. К примеру, если у нас есть три точки данных, находящихся на расстоянии 1, 2 и 3, а k = 3, а потом мы видим следующую точку на расстоянии 1,5 – то как проверить, вошла ли она в наш набор из уже существующих трёх ближайших точек?

Для начала предположим, что у нас есть n учебных точек. Тогда мы должны рассмотреть все из них для каждого прогноза, чтобы найти ближайшую, так что для 1 ближайшего соседа каждый прогноз имеет сложность O(N). Если мы примем наивный подход и будем просматривать каждую из K ближайших уже найденных точек, чтобы убрать самую дальнюю и добавить новую более близко лежащую, то это будет алгоритм O(NK). Но, как вы знаете, поиск по списку не является алгоритмом O(K). На самом деле, если у нас есть возможность сохранять отсортированный список, то это будет алгоритм O(log(K)). Есть даже лучшие способы оптимизации, такие как методы дерева сфер или kd деревьев, но их описание выходит за рамки данного курса.

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

Собрав k ближайших соседей, всё, что нам нужно сделать, – это создать другой словарь, где класс будет ключом, а количество его появлений – значением. После этого мы просто выбираем класс с наибольшим числом «голосов».

У вас может возникнуть вопрос: а что, если в итоге подсчёта у нас получится ничья? В этом случае есть несколько вариантов. Простейший из них – взять то, что предлагает функция argmax. Мы не знаем, что выберет argmax, поэтому оставляем это на её усмотрение. Второй способ – сделать выбор случайным образом. Последний способ – взвесить расстояние свободного члена каждого соседа до проверочной точки. В нашем случае мы воспользуемся чем-то вроде первого варианта: будем перебирать все имеющиеся «голоса» и выбирать класс с наибольшим количеством голосов, который попадётся первым.

Важный вопрос метода k-ближайших соседей: как выбрать k? Тут нет простого ответа. Это то, что называется гиперпараметром, и исследователи часто выбирают его значение, исходя из предыдущего опыта. Может помочь перекрёстная проверка; её мы обсудим позже.

И последнее замечание о методе k-ближайших соседей – это пример того, что именуют «ленивым классификатором». Это связано с тем, что при обучении модели мы ничего не делаем, кроме сохранения входных данных для позднейшего использования. Что же касается длительности каждого этапа, то вы увидите, что обучение происходит почти мгновенно, зато прогноз займёт много времени.

Метод k-ближайших соседей в коде и база MNIST

Сейчас мы реализуем метод k-ближайших соседей в коде и используем его для базы данных MNIST.

Вам может понадобиться библиотека, которой, возможно, у вас ещё есть – Sortedcontainers. Для её установки просто наберите в командной строке команду

sudo pip install sortedcontainers

Нужный для этой лекции файл называется knn.py.

Но вначале быстро пройдёмся по файлу util.py, находящемся в той же папке, в частности, по функции get_data. Она использует библиотеку Pandas для чтения CSV-файлов одной строкой. Мы также воспользуемся as_matrix, чтобы преобразовать данные в массив Numpy и перемешаем данные, чтобы они шли в случайном порядке. Кроме того, поскольку данные содержат целые числа от 0 до 255, нам необходимо отмасштабировать их так, чтобы они находились между 0 и 1. Если вы просматривали данные, то знаете, что первый столбец – это метки, а остальные столбцы – данные изображений. Поэтому нашим X будет всё, кроме первого столбца, а Y – только первый столбец. Кроме того, мы устанавливаем предел по количеству данных, чтобы работа алгоритма не заняла чересчур много времени. Можете поэкспериментировать с его значением и посмотреть, будет ли при этом какая-то разница. Разумеется, чересчур малое количество не годится ввиду опасности переобучения.

def get_data(limit=None):

    print(“Reading in and transforming data…”)

    df = pd.read_csv(‘../large_files/train.csv’)

    data = df.as_matrix()

    np.random.shuffle(data)

    X = data[:, 1:] / 255.0 # data is from 0..255

    Y = data[:, 0]

    if limit is not None:

        X, Y = X[:limit], Y[:limit]

    return X, Y

Итак, начнём с декларирования класса KNN.

import numpy as np

from sortedcontainers import SortedList

# Note: You can’t use SortedDict because the key is distance

# if 2 close points are the same distance away, one will be overwritten

from util import get_data

from datetime import datetime

class KNN(object):

    def __init__(self, k):

        self.k = k

Функция fit. Поскольку это «ленивый классификатор», то всё, что она делает, – сохраняет X и Y:

    def fit(self, X, y):

        self.X = X

        self.y = y

Далее функция predict. В ней мы создаём отсортированный список и вводим параметр load, чтобы регулировать величину списка. В нашем случае она равна K. Для определения расстояния используется квадратичное расстояние, но поскольку квадратичная функция монотонно увеличивается, не важно, используете ли вы евклидово или квадратичное расстояние – результат будет тот же.

    def predict(self, X):

        y = np.zeros(len(X))

        for i,x in enumerate(X):

            sl = SortedList(load=self.k)

            for j,xt in enumerate(self.X):

                diff = x – xt

                d = diff.dot(diff)

                if len(sl) < self.k:

                    sl.add( (d, self.y[j]) )

                else:

                    if d < sl[-1][0]:

                        del sl[-1]

                        sl.add( (d, self.y[j]) )

            votes = {}

            for _, v in sl:

                votes[v] = votes.get(v,0) + 1

            max_votes = 0

            max_votes_class = -1

            for v,count in votes.iteritems():

                if count > max_votes:

                    max_votes = count

                    max_votes_class = v

            y[i] = max_votes_class

        return y

Следующее – функция score.

    def score(self, X, Y):

        P = self.predict(X)

        return np.mean(P == Y)

Переходим к функции main.

Мы ограничим наши данные двумя тысячами штук, где первая тысяча будет учебным набором данных, а последняя – проверочным. Кроме того, проверим нашу модель для разных значений K, устанавливаяего значение равным 1, 2, 3, 4, 5.

if __name__ == ‘__main__’:

    X, Y = get_data(2000)

    Ntrain = 1000

    Xtrain, Ytrain = X[:Ntrain], Y[:Ntrain]

    Xtest, Ytest = X[Ntrain:], Y[Ntrain:]

    for k in (1,2,3,4,5):

        knn = KNN(k)

        t0 = datetime.now()

        knn.fit(Xtrain, Ytrain)

        print “Training time:”, (datetime.now() – t0)

        t0 = datetime.now()

        print “Train accuracy:”, knn.score(Xtrain, Ytrain)

        print “Time to compute train accuracy:”, (datetime.now() – t0), “Train size:”, len(Ytrain)

        t0 = datetime.now()

        print “Test accuracy:”, knn.score(Xtest, Ytest)

        print “Time to compute test accuracy:”, (datetime.now() – t0), “Train size:”, len(Ytest)

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

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

Так что, если будет такое желание, приостановите лекцию и сначала попробуйте сами.

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

Итак, перейдём к коду.

Нам нужно, конечно же, импортировать Numpy, а также Matplotlib, чтобы иметь возможность отобразить график. Сам класс для метода k-ближайших соседей писать необходимости нет, ведь мы это уже сделали.

import numpy as np

import matplotlib.pyplot as plt

from knn import KNN

Итак, функция get_data. Установим значение ширины и высоты равными 8, так чтобы у нас получилась сетка 8х8 – то есть всего 64 точки. Разумеется, это двухмерные данные, иначе мы бы просто не смогли их отобразить.

def get_data():

    width = 8

    height = 8

    N = width * height

    X = np.zeros((N, 2))

    Y = np.zeros(N)

    n = 0

    start_t = 0

    for i in xrange(width):

        t = start_t

        for j in xrange(height):

            X[n] = [i, j]

            Y[n] = t

            n += 1

            t = (t + 1) % 2

        start_t = (start_t + 1) % 2

    return X, Y

Следующее – наша фунция main.

if __name__ == ‘__main__’:

    X, Y = get_data()

    plt.scatter(X[:,0], X[:,1], s=100, c=Y, alpha=0.5)

    plt.show()

    model = KNN(3)

    model.fit(X, Y)

    print “Train accuracy:”, model.score(X, Y)

Итак, видим нашу сетку чередующихся точек.

Как видите, точность обучения – 0%.

Метод k-ближайших соседей и проблема XOR

Попробуем использовать метод k-ближайших соседей для решения проблемы XOR. Но мы не будем решать её в простейшем виде с только 4 входными точками, поскольку мы уже знаем, как метод k-ближайших соседей с ней справляется – представьте себе сетку из предыдущей лекции в качестве расширенной версии XOR. Вместо этого будем считать, что всё, что выше 0,5 и ниже 1, – истинно, а всё, что ниже 0,5 и выше 0 – ложным. Таким образом мы создадим область точек в районе от 0 до 1 по оси x и от 0 до 1 по оси y.

Итак, напишем для этого код, чтобы вы могли уяснить, как это всё выглядит.

Прежде всего импортируем уже написанный класс KNN, а также функцию get_xor из файла util.py. Ну, и библиотеку Matplotlib, чтобы отобразить диаграмму.

from knn import KNN

from util import get_xor

import matplotlib.pyplot as plt

Всё, что остаётся, только написать функцию main.

if __name__ == ‘__main__’:

    X, Y = get_xor()

    plt.scatter(X[:,0], X[:,1], s=100, c=Y, alpha=0.5)

    plt.show()

    model = KNN(3)

    model.fit(X, Y)

    print “Accuracy:”, model.score(X, Y)

Итак, видим данные для модифицированной проблемы XOR. Как видите, это нелинейная задача – не получится провести прямую для разделения двух классов. Но метод k-ближайших соседей даёт весьма приличную точность.

Метод k-ближайших соседей и проблема пончика

В заключение используем метод k-ближайших соседей для решения «проблемы пончика». «Проблема пончика» – это когда у нас один класс находится внутри другого. Мы знаем, что линейный классификатор вовсе не может решить эту задачу, поскольку нет такой прямой, чтобы разделила два таких класса.

Итак, вначале обратимся к файлу util.py, где определена функция get_donut. У нас есть 200 точек, внутренний радиус равен 5, а внешний – 10:

def get_donut():

    N = 200

    R_inner = 5

    R_outer = 10

    # distance from origin is radius + random normal

    # angle theta is uniformly distributed between (0, 2pi)

    R1 = np.random.randn(N/2) + R_inner

    theta = 2*np.pi*np.random.random(N/2)

    X_inner = np.concatenate([[R1 * np.cos(theta)], [R1 * np.sin(theta)]]).T

    R2 = np.random.randn(N/2) + R_outer

    theta = 2*np.pi*np.random.random(N/2)

    X_outer = np.concatenate([[R2 * np.cos(theta)], [R2 * np.sin(theta)]]).T

    X = np.concatenate([ X_inner, X_outer ])

    Y = np.array([0]*(N/2) + [1]*(N/2))

return X, Y

Переходим к файлу knn_donut.py.

Первым делом, конечно, импортируем уже написанный класс KNN и только что показанную функцию get_donut, а также Matplotlib для вывода графика.

from knn import KNN

from util import get_donut

import matplotlib.pyplot as plt

Этот файл очень похож на knn_xor.py с тем лишь различием, что вместо функции get_xor мы используем get_donut. Установим k = 3, но вы, если хотите, можете поменять значение.

if __name__ == ‘__main__’:

    X, Y = get_donut()

    plt.scatter(X[:,0], X[:,1], s=100, c=Y, alpha=0.5)

    plt.show()

    model = KNN(3)

    model.fit(X, Y)

    print “Accuracy:”, model.score(X, Y)

Итак, видим «пончики» – синий внутри красного.

И имеем очень хорошую точность, почти идеальную.

Андрей Никитенко
Андрей Никитенко
Задать вопрос эксперту
Понравилась статья? Поделить с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: