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

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

---

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

k-модель ближайшего соседа

---

Модель

---

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

Три элемента

---

1. мера расстояния

   • $p$Расстояние: расстояние между двумя точками экземпляра в пространстве признаков является отражением того, насколько хороши две точки экземпляра. установить пример ввода$L_{p} для x \in \mathbb{R}^{n}, x_{i} и x_{j}$Расстояние определяется как: ​$L_{p}\left(x_{i}, x_{j}\right)=\left(\sum_{l=1}^{n}\left|x_{i}^{l}-x_{j}^{l}\right| p^{p}\right)^{\left(\frac{1}{p}\right)}\qquad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$
   • Евклидово расстояние:$p=2$особые обстоятельства. ​$L_{2}\left(x_{i}, x_{j}\right)=\left(\sum_{l=1}^{n}\left|x_{i}^{(l)}-x_{j}^{(l)}\right|^{2}\right)^{\frac{1}{2}}$
   • Манхэттен Расстояние:$p=1$особые обстоятельства. ​$L_{1}\left(x_{i}, x_{j}\right)=\sum_{l=1}^{n}\left|x_{i}^{(l)}-x_{j}^{(l)}\right|$
   • Расстояние Чебышева:$p={\infty}$особые обстоятельства. ​$L_{\infty}\left(x_{i}, x_{j}\right)=\max _{l}\left|x_{i}^{(l)}-x_{j}^{(l)}\right|$

   

2. Выбор значения k

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

3. Правила принятия решения о классификации

   • Правилом принятия решения о классификации в методе k-ближайших соседей часто является голосование по большинству, то есть класс большинства в k смежных обучающих экземплярах входного экземпляра определяет класс входного экземпляра.
   • Правило голосования по большинству Если функция потерь для классификации$0-1$Функция потерь, функция классификации ​$f: \mathbf{R}^{n} \rightarrow c_{1}, c_{2}, \ldots, c_{k}$Вероятность неправильной классификации ​$P(Y \neq f(X))=1-P(Y=f(X))$для данного экземпляра$x \in \chi_{1}$его ближайший сосед$k$Набор точек обучающего экземпляра$N_{k}(x)$. если покрыто$N_{k}(x)$Региональная категория$c_{j}$, скорость ошибочной классификации ​$\frac{1}{k} \sum_{x_{i} \in N_{k}(x)} I\left(y_{i} \neq c_{j}\right)=1-k \sum_{x_{i} \in N_{k}(x)} I\left(y_{i}=c_{j}\right)$Чтобы свести к минимуму частоту ошибочных классификаций, то есть эмпирический риск, необходимо использовать$\sum_{x_{i} \in N_{k}(x)} I\left(y_{i}=c_{j}\right)$максимум, поэтому правило голосования по большинству эквивалентно минимизации эмпирического риска.
     

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

---

Построить дерево kd

---

• Вход: k-мерный набор пространственных данных:$T=\left\{x_{1}, x_{2}, \cdots, x_{N}\right\}$в,$x_{i}=\left(x_{i}^{(1)}, x_{i}^{(2)}, \cdots, x_{i}^{(k)}\right)^{T}$Выход: kd-дерево

  1. Начало: Построить корневой узел. Выбрать$x^{(1)}$- ось координат со всеми данными в обучающем наборе$x^{(1)}$В качестве точки сечения используется медиана в координатах, сверхпрямоугольная область разрезается на две подобласти, а точка сечения используется как корневой узел. Из корневого узла генерируются левый и правый дочерние узлы с глубиной 1. Соответствующие координаты левого узла меньше точки разделения, а соответствующие координаты правого узла больше точки разделения.
  2. повторение на глубину$j$узел, выбирай$x^{(I)}$ось деления,$I=j(\bmod k)+1$, со всеми экземплярами в области узла$x^{(l)}$медиана координат В качестве точки разделения регион делится на два субрегиона. Глубина генерации$j+1$левый и правый дочерние узлы. Соответствующие координаты левого узла меньше точки разделения, а соответствующие координаты правого узла больше точки разделения.
  3. Останавливайтесь до тех пор, пока в двух субрегионах не останется экземпляров.

• Пример Вход: тренировочный набор:$T=\{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)\}$вывод: kd-дерево

  $x^{(1)}: \quad 2,4,5,7,8,9$начало: выберите$x^{(1)}$- ось координат, а медиана -$7$, который$(7,2)$Для точки разделения разделите всю область

Снова разделите площадь: от$x^{(2)}$Для оси координат выберите медиану, а левая область$4$, правая область$6$. Таким образом, точка сегментации левой области$(5,4)$, координаты точки сегментации в правой области равны$(9,6)$

Разделите левую область: от$x^{(1)}$— ось координат, выберите медиану, а верхняя область —$4$, нижняя область$2$. Таким образом, точка сегментации верхней области$(4,7)$, координаты точки сегментации в нижней области равны$(2,3)$

Разделите правую область: с$x^{(1)}$Для оси координат выберите медиану, верхняя область не имеет точек экземпляра, а нижняя область$8$. Следовательно, координаты точки сегментации в нижней области равны$(8,1)$ Окончательный результат деления

кд дерево

Пока алгоритм готов

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

---

• поиск ближайшего соседа с деревом kd

  • Найдите «текущую ближайшую точку» Найдите ближайший дочерний узел как «текущую ближайшую точку» целевой точки.
  • отступление Вернитесь назад и выполните итерацию вдоль корня дерева по расстоянию между целевой точкой и «текущей ближайшей точкой».
  • Подробное описание Вход: построенное дерево kd, целевая точка x Выход: ближайшие соседи x
    • Найдите «текущую ближайшую точку»
      • Начиная с корневого узла, рекурсивно посещаем дерево kd, чтобы найти конечный узел, содержащий x; Возьмите этот листовой узел как «текущую ближайшую точку»;
    • отступление
      • Если узел ближе к целевой точке, чем «текущая ближайшая точка», обновите «текущую ближайшую точку»;
      • Текущая ближайшая точка должна существовать в области, соответствующей дочернему узлу узла, и проверить, есть ли более близкая точка в области, соответствующей другому дочернему узлу родительского узла дочернего узла.
    • При возврате к корневому узлу поиск заканчивается, и последняя «текущая ближайшая точка» является ближайшим соседом x.

• Пример Вход: дерево kd, целевая точка$x=(2,4.5)$; вывод: ближайший сосед

  первый возврат

Второй возврат, ближайший сосед:$(2,3)$

Если точки экземпляра распределены случайным образом, средняя вычислительная сложность поиска kd-дерева равна$O(\log N)$, здесь$N$- количество обучающих экземпляров. kd-дерево больше подходит для поиска k-ближайших соседей, когда количество обучающих экземпляров намного больше, чем пространственное измерение. когда комитет по космическим измерениям Его эффективность быстро падает по мере приближения к количеству обучающих экземпляров, почти приближаясь к линейной развертке.

код

---

import torch
import random
import matplotlib.pyplot as plt


class DrawTool():
    """画图类"""

    # 画点[数据集，x点，离 x点 最近的点]
    def drawPoint(self, points, x, nearestPoint):
        XMax = max(points[:, 0])  # X 轴范围
        YMax = max(points[:, 1])  # Y 轴范围
        precision = max(XMax, YMax) // 10 + 1  # 坐标轴精度
        #plt.rcParams['font.sans-serif'] = ['SimHei']  # 防止中文乱码
        plt.scatter(points[:, 0], points[:, 1], label="data")
        plt.scatter(x[0], x[1], c='c', marker='*', s=100, label="x(input)")
        plt.scatter(nearestPoint[0], nearestPoint[1], c='r', label="nearest")
        plt.xticks(torch.arange(0, XMax, precision))  # 设置 X 轴
        plt.yticks(torch.arange(0, YMax, precision))  # 设置 Y 轴
        plt.legend(loc='upper left')
        plt.show()


class DataLoader():
    """"数据加载类"""

    # 初始化[creat：人造数据集，random：随机数据集]
    def __init__(self, kind="creat"):
        self.points = None
        if (kind == "creat"):
            self.x = [2, 5, 9, 4, 8, 7]
            self.y = [3, 4, 6, 7, 1, 2]
        elif kind == "random":
            nums = random.randint(20, 40)
            self.x = random.sample(range(0, 40), nums)
            self.y = random.sample(range(0, 40), nums)

    # 处理数据
    def getData(self):
        self.points = [[self.x[i], self.y[i]] for i in range(len(self.x))]
        return self.points

    # 得到一个与数据集不重复的点，作为 x 点
    def getRandomPoint(self):
        points = torch.tensor(self.points)
        x, y, i = -1, -1, 0
        while x == -1 or y == -1:
            if x == -1 and i not in points[:, 0]:
                x = i
            if y == -1 and i not in points[:, 1]:
                y = i
            i += 2
        return x, y


class KDNode():#二叉树
    """"节点类"""

    def __init__(self, point):
        self.point = point
        self.left = None
        self.right = None


class KDTree():
    """KD树"""

    def __init__(self):
        self.root = None
        self.nearestPoint = None
        self.nearestDis = float('inf')

    # 创造和搜索 KD树[数据集，x]
    def creatAndSearch(self, points, x):
        self.root = self.creatTree(points)
        self.searchTree(self.root, x)

    # 创造 KD树[数据集，维度]
    def creatTree(self, points, col=0):
        if len(points) == 0:
            return None
        points = sorted(points, key=lambda point: point[col])
        mid = len(points) >> 1
        node = KDNode(points[mid])
        node.left = self.creatTree(points[0:mid], col ^ 1)
        node.right = self.creatTree(points[mid + 1:len(points)], col ^ 1)
        return node

    # 搜索 KD树[KD树，x，维度]
    def searchTree(self, tree, x, col=0):
        if tree == None:
            return

        # 对应算法中第 1 步
        if x[col] < tree.point[col]:
            self.searchTree(tree.left, x, col ^ 1)
        else:
            self.searchTree(tree.right, x, col ^ 1)

        disCurAndX = self.dis(tree.point, x)
        if disCurAndX < self.nearestDis:
            self.nearestDis = disCurAndX
            self.nearestPoint = tree.point

        # 判断目前最小圆是否与其他区域相交，即判断 |x（按轴读值）-节点（按轴读值）| < 最近的值（圆的半径）
        # 对应算法中第 3 步中的 (b)
        if abs(tree.point[col] - x[col]) < self.nearestDis:
            if tree.point[col] < x[col]:
                self.searchTree(tree.right, x, col ^ 1)
            else:
                self.searchTree(tree.left, x, col ^ 1)

    # 两点间距离[a点，b点]
    def dis(self, a, b):
        return sum([(a[i] - b[i]) ** 2 for i in range(len(a))]) ** 0.5#欧氏距离

    # 前序遍历 KD树（测试使用）[KD树]
    def printTree(self, root):
        if root != None:
            print(root.point)
            self.printTree(root.left)
            self.printTree(root.right)


if __name__ == '__main__':
    drawTool = DrawTool()
    dataLoader = DataLoader("random")
    kdTree = KDTree()

    points = dataLoader.getData()
    x = dataLoader.getRandomPoint()

    kdTree.creatAndSearch(points, x)
    drawTool.drawPoint(torch.tensor(points), x, kdTree.nearestPoint)