«Это 11-й день моего участия в ноябрьском испытании обновлений, ознакомьтесь с подробностями события: [Испытание последнего обновления 2021 года] (nuggets.capable/post/702364… "nuggets.capable/post/702364…

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

Алгоритм KNN

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

выбор метрики расстояния

Евклидово расстояние: евклидова метрика (также известная как евклидово расстояние) — это обычно используемое определение расстояния, которое относится к истинному расстоянию между двумя точками в ?-мерном пространстве или к вектору естественной длины (то есть к расстоянию от этой точки до Происхождение). Евклидово расстояние в 2D и 3D пространстве — это фактическое расстояние между двумя точками.

Дистанционная формула:

Манхэттенское расстояние: представьте, что вы едете от одного перекрестка к другому по городской дороге.Является ли расстояние вождения расстоянием по прямой между двумя точками? По-видимому, нет, если только вы не сможете пройти через здание. Фактическое расстояние вождения - это «Манхэттенское расстояние». Отсюда и название Манхэттенское расстояние, также известное как расстояние городского квартала.

Формула расстояния:

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

Формула расстояния:

Расстояние Минковского: наиболее часто используется расстояние Минковского, когда ? принимает значение 1 или 2. ? = 2 — евклидово расстояние, а ? = 1 — манхэттенское расстояние. Когда ? достигает предела бесконечности, можно получить расстояние Чебышева.

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

Формула расстояния:

Косинусное сходство: когда два вектора имеют одинаковое направление, значение косинусного сходства равно 1; когда угол между двумя векторами равен 90°, значение косинусного сходства равно 0; когда два вектора указывают в строго противоположных направлениях, значение косинусного сходства равен 0. Сходство имеет значение -1. Предполагая, что ? и ? являются двумя ?-мерными векторами, ? есть ?1, ?2,..., ?? и ? есть ?1, ?2,..., ??, тогда косинус угла между ? и ? равен:

алгоритм выбора knn

кд деление дерева:

KD-дерево (K-Dimension Tree), также известное как K-мерное дерево, может делить пространство с более высокой эффективностью, а его структура очень удобна для поиска ближайших соседей и обнаружения столкновений. Предполагая, что есть 6 двумерных точек данных, процесс построения дерева KD: ? = { (2,3), (5,7), (9,6), (4,5), (6,4) , (7 ,2)}.

1. Начиная с оси ?, согласно значениям оси ? 2, 5, 9, 4, 6, 7, медиана равна 6, поэтому разделительная линия: ? = 6.

2. В соответствии с дисперсией данных по оси ? и оси ? в качестве первого витка оси деления может быть выбрана ось с наибольшей дисперсией.

Левое подпространство (обозначаемое как ?1) содержит точки (2,3), (4,5), (5,7), а ось деления вращается, начиная с оси ?, а линия деления: ? = 5 .

Правое подпространство (вспомним ?2) содержит точки (9, 6), (7, 2), вращение отрезанного вала, отделенное от вала, линия разреза: ? = 6.

3. Левое подпространство ?1 (обозначается как ?3) содержит точку (2,3), а ось деления вращается, начиная с оси x, а линия деления: ? = 2.

Его левое подпространство обозначается ?7 , а правое подпространство обозначается ?8 . Так как ?7 , ?8 не содержат точек, мы не продолжаем разбивать по ним.

Правое подпространство ?1 (обозначается как ?4) содержит точку (5,7), а ось деления вращается, начиная с оси x, а линия деления: ? = 5.

Его левое подпространство обозначается ?9, а правое подпространство обозначается ?10. Поскольку ?9 и ?10 не содержат точек, мы не будем продолжать их разбивать.

4. Левое подпространство ?2 (обозначается как ?5) содержит точку (7,2), а ось деления вращается, начиная с оси x, а линия деления: ? = 7.

Его левое подпространство обозначается ?11, а правое подпространство обозначается ?12. Поскольку ?11, ?12 не содержат точек, мы не продолжаем их разбивать.

Правое подпространство ?2 (обозначаемое как ?6) не содержит точек, поэтому прекратите расщепление.

Блок-схема выглядит следующим образом:

поиск по дереву kd

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

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

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

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

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

4. При возврате к корневому узлу алгоритм завершается, и ближайший соседний узел, сохраненный в это время, является окончательным ближайшим соседом. После обхода левого и правого листовых узлов (4,5) обнаруживается, что расстояние равно текущему оптимальному расстоянию, а ближайший сосед не обновляется. Таким образом, ближайшим соседом (4,4) является (4,5).

KNN-регрессия

Регрессия с использованием алгоритма knn

Для новой выборки в качестве прогнозируемого значения используется среднее значение меток ее ? ближайших соседей обучающих выборок.

Внедрение тестов классификации рукописных цифр

Реализовано с использованием алгоритма knn, инкапсулированного в библиотеке sklearn. Картинки рукописных цифр выглядят следующим образом:

import numpy as np
from os import listdir
from sklearn.neighbors import KNeighborsClassifier as KNN

"""
函数说明:将32x32的二进制图像转换为1x1024向量
"""


def img2vector(filename):
    # 创建1x1024零向量
    returnVect = np.zeros((1, 1024))
    # 打开文件
    fr = open(filename)
    # 按行读取
    for i in range(32):
        # 读一行数据
        lineStr = fr.readline()
        # 每一行的前32个元素依次添加到returnVect中
        for j in range(32):
            returnVect[0, 32 * i + j] = int(lineStr[j])
    # 返回转换后的1x1024向量
    return returnVect


"""
函数说明:手写数字分类测试
"""


def handwritingClassTest():
    # 训练集的Labels
    hwLabels = []
    # 返回trainingDigits目录下的文件名
    trainingFileList = listdir('trainingDigits')
    # 返回文件夹下文件的个数
    m = len(trainingFileList)
    # 初始化训练的Mat矩阵,训练集
    trainingMat = np.zeros((m, 1024))
    # 从文件名中解析出训练集的类别
    for i in range(m):
        # 获得文件的名字
        fileNameStr = trainingFileList[i]
        # 获得分类的数字
        classNumber = int(fileNameStr.split('_')[0])
        # 将获得的类别添加到hwLabels中
        hwLabels.append(classNumber)
        # 将每一个文件的1x1024数据存储到trainingMat矩阵中
        trainingMat[i, :] = img2vector('trainingDigits/%s' % (fileNameStr))
    # 构建kNN分类器
    neigh = KNN(n_neighbors=3, algorithm='kd_tree')
    # 拟合模型, trainingMat为训练矩阵,hwLabels为对应的标签
    neigh.fit(trainingMat, hwLabels)
    # 返回testDigits目录下的文件列表
    testFileList = listdir('testDigits')
    # 错误检测计数
    errorCount = 0.0
    # 测试数据的数量
    mTest = len(testFileList)
    # 从文件中解析出测试集的类别并进行 分类测试
    for i in range(mTest):
        # 获得文件的名字
        fileNameStr = testFileList[i]
        # 获得分类的数字
        classNumber = int(fileNameStr.split('_')[0])
        # 获得测试集的1x1024向量,用于训练
        vectorUnderTest = img2vector('testDigits/%s' % (fileNameStr))
        # 获得预测结果
        classifierResult = neigh.predict(vectorUnderTest)
        print("分类返回结果为%d\t真实结果为%d" % (classifierResult, classNumber))
        if (classifierResult != classNumber):
            errorCount += 1.0
    print("总共错了%d个数据\n错误率为%f%%" % (errorCount, errorCount / mTest * 100))


"""
函数说明:main函数
"""
if __name__ == '__main__':
    handwritingClassTest()

Используйте алгоритм как kd-дерево.

Прогнозируемый результат: