предисловие
Введение алгоритма
расчет расстояния
Реализация алгоритма
конверсия данных
Выбор значения К
Эпилог

предисловие

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

Ощущения после обучения:

Машинное обучение немного отличается от того, что я себе представлял
KNN действительно прост (~￣△￣)~

Введение алгоритма

KNN — это контролируемый алгоритм классификации, т. е. KNNпомеченНабор образцов используется для обучения, а тестовый объект тестируется с данными набора образцов.Классификацияалгоритм.

Принцип KNN также очень прост: в наборе выборок выбираются K выборок, наиболее близких к тестируемому объекту, а затем классифицируется тестовый объект в соответствии с типом K выборок. Отсюда и буква K в названии алгоритма.

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

расчет расстояния

Когда дело доходит до расчета расстояния, первая формула, которая приходит на ум, такова: $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$ , эта формула может вычислить точку (x_1, y_1) и точка (x_2, y_2) расстояние между. Но формула представляет собой упрощенную форму евклидова расстояния в двумерной плоскости, и полная формула такова:

\begin{align*} d(x, y) = \sqrt{(x_1 - y_1)^2 + (x_2 - y_2)^2 + \dots + (x_n - y_n)^2} \end{align*}

Реализация кода Python для расчета расстояния между тестовым объектом и образцами в наборе образцов по этой формуле:

def euclidean_distance(a, b):
    """Implementation of Euclidean distance calculation.

    Example:
    >>> a = np.array([1, 2, 3])
    >>> b = np.array([[4, 5, 6], [7, 8, 9]])
    >>> euclidean_distance(a, b)
    """
    return np.square(np.tile(a, (b.shape[0], 1)) - b).sum(axis=1) ** 0.5

В приведенном выше коде параметрaЯвляется тестовым объектом, является $1 \times n$ вектор, а параметрbЯвляется $m \times n$ матрица, значит естьобразцы.

В дополнение к формуле евклидова расстояния существуют две широко используемые формулы расчета расстояния, а именно:

Калькулятор расстояния до Манхэттена $d(x, y) = |x_1 - y_1| + |x_2 - y_2| + \dots + |x_n - y_n|$

def manhattan_distance(a, b):
    """Implementation of Manhattan distance calculation.

    Example:
    >>> a = np.array([1, 2, 3])
    >>> b = np.array([[4, 5, 6], [7, 8, 9]])
    >>> manhattan_distance(a, b)
    """
    return np.abs(np.tile(a, (b.shape[0], 1)) - b).sum(axis=1)

Формула расчета расстояния Минковского $d(x, y) = \Bigg(\sum\limits_{i=1}^n|x_i - y_i|^p \Bigg)^\frac{1}{p}$

def minkowski_distance(a, b, p):
    """Implementation of Minkowski distance calculation.

    Example:
    >>> a = np.array([1, 2, 3])
    >>> b = np.array([[4, 5, 6], [7, 8, 9]])
    >>> minkowski_distance(a, b, 3)
    """
    abs_diff = np.abs(np.tile(a, (b.shape[0], 1)) - b)
    return np.power(abs_diff, p).sum(axis=1) ** (1 / p)

В то же время по формуле расстояния Минковского можно знать, что при в формуле p = 2 Тогда расстояние Минковского становится евклидовым расстоянием, и p = 1 становится манхэттенским расстоянием.

Реализация алгоритма

С функцией расчета расстояния можно приступить к реализации алгоритма KNN.Вариант реализации с использованием Python выглядит следующим образом:

def classify0(inx, data_set, labels, k):
    sorted_distances = euclidean_distance(inx, data_set).argsort()

    class_counter = {}
    for i in range(k):
        label = labels[sorted_distances[i]]
        class_counter[label] = class_counter.get(label, 0) + 1

    sorted_class_counter = sorted(
        class_counter.items(), key=operator.itemgetter(1), reverse=True)

    return sorted_class_counter[0][0]

Это очень простая реализация, вход в функцию — вектор тестовых объектов.inx, матрица выборкиdata_set, метка, соответствующая образцу набора образцовlablesиKценность.

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

Среди них методargsortочень полезный метод, в общем случае результат вычисления расстояния часточисло с плавающей запятой, но методargsortРезультат после сортировки результатовцелочисленный индекс. Например:

>>> arr = np.array([1.3, 4.5, 2.5, 6.7, 2.3])
>>> arr.argsort()
array([0, 4, 2, 1, 3], dtype=int64)
>>> [arr[i] for i in arr.argsort()]
[1.3, 2.3, 2.5, 4.5, 6.7]

конверсия данных

Если внимательно посмотреть на предыдущий код, то можно увидеть, что мы делаем предположение о образце и тестовом объекте, то есть все они $1 \times n$ Вектор , а выборка состоит из нескольких выборок $m \times n$ матрица.

Следовательно, перед использованием кода реализации алгоритма KNN необходимо решить проблему: как преобразовать выборки в векторы!

Допустим, наша выборка имеет вид, где значения для разных имён могут быть одинаковыми:

номер образца	Особенность А	Особенность Б	Функция С	Функция D	Пример классификации
1	a1	b1	c1	d1	Категория 1
2	a2	b2	c2	d2	Категория 2
3	a3	b3	c3	d3	Категория 3
…	…	…	…	…	…
n	an	bn	cn	dn	классификация п

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

\begin{align*} \begin{bmatrix} a1 & b1 & c1 & d1 \\ a2 & b2 & c2 & d2 \\ \dots & \dots & \dots & \dots \\ an & bn & cn & dn \\ \end{bmatrix} \end{align*}

Для образцов, чьи собственные значения не являются числовыми, мы можем преобразовать собственные значения в соответствии с количеством собственных значений, например, да и нет можно преобразовать в0и1.

Это означает: KNN применим к числовым и номинальным диапазонам данных (диапазон собственных значений ограничен)

Кроме того, если диапазон собственных значений выборки сильно меняется, например, значение признака А может быть(1, 1000)Значение признака B может быть(1, 2), то мы должны выполнить числовую нормализацию, чтобы избежать чрезмерного взвешивания некоторых собственных значений, таких как обработка диапазона значений как0прибыть1или-1прибыть1между.

Простой способ справиться с этим newVal = (oldVal - min) / (max - min) , в,minиmax- максимальное и минимальное значения каждого признака соответственно.

Код Python реализован следующим образом:

def auto_norm(data_set):
    min_vals, max_vals = data_set.min(0), data_set.max(0)
    ranges = max_vals - min_vals
    m = data_set.shape[0]
    return (data_set - np.tile(min_vals, (m, 1))) / np.tile(ranges, (m, 1))

Выбор значения К

После завершения расчета расстояния и преобразования данных необходимо рассмотреть выбор значения K. На этом этапе нет навыков, полагаясь только напытаться.

Необязательный метод тестированияПерекрестная проверка, Выберите часть из набора образцов в качестве набора образцов, а остальные — в качестве набора тестов, а затем по очереди проверьте правильность разных K.

Если вы хотите использовать перекрестную проверку, вам необходимо учитывать, влияет ли порядок выборки на эффект перекрестной проверки.

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

После завершения выбора K наш алгоритм KNN завершен, и остается только прочитать данные преобразования, протестировать и использовать.

Эпилог

Алгоритм KNN действительно прост, и это единственный алгоритм в книге «Машинное обучение на практике», который не требует обучения, а именно простого и грубого вычисления расстояния от тестируемого объекта до образца.

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

Но также из-за этого алгоритмическая сложность KNN очень высока, а время и пространство высоки.

Когда люди запускают программы на своих компьютерах, люди действительно паникуют (;￣Д￣)

Машинное обучение — алгоритм K-ближайших соседей