KNN（k-Nearest Neighbor）算法原理

本文主要是介绍KNN（k-Nearest Neighbor）算法原理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

KNN（k-Nearest Neighbor）算法是一种基于实例的学习方法，常用于分类和回归问题。下面是KNN算法的原理和步骤，以及欧式距离和曼哈顿距离的计算原理：

原理

KNN算法基于一个假设：与一个样本最相似的其他k个样本的类别可以用来预测该样本的类别。KNN算法将所有的训练数据看作一个点集，根据他们与新样本之间的距离进行分类。

步骤

KNN算法的实现步骤如下：

计算测试数据与训练数据之间的距离（可以使用欧式距离或曼哈顿距离）。
选取距离测试数据最近的k个点。
统计k个点中各类别出现的次数。
将出现次数最多的类别作为测试数据的预测结果。

欧式距离计算原理

欧式距离,也称L2距离，是一种常用的距离度量方式，其计算公式为：

$d(x,y) = sqrt(sum(xi-yi)^2)$

其中，x和y是两个向量，xi和yi分别表示向量中的第i个元素。

简单来说，欧式距离就是把两个点的各个坐标分别相减后平方再相加，最后再取平方根。

曼哈顿距离计算原理

曼哈顿距离,也称L1距离，也叫城市街区距离，其计算公式为：

$d (x, y) = s u m (∣ x i - y i ∣)$

其中，x和y是两个向量，xi和yi分别表示向量中的第i个元素。

简单来说，曼哈顿距离就是把两个点的各个坐标分别相减后取绝对值再相加。

KNN（K-Nearest Neighbors，K近邻算法）是一种基本的分类和回归算法，它的原理非常简单直观，即通过计算待分类数据点与已有数据集中所有数据点的距离，选择其中距离最小的K个数据点（最近邻），并把它们的类别作为待分类数据点的类别进行分类。

以下是KNN算法的代码实现示例：

import numpy as np
from collections import Counterdef euclidean_distance(x1, x2):return np.sqrt(np.sum((x1 - x2)**2))class KNN:def __init__(self, k=3):self.k = kdef fit(self, X, y):self.X_train = Xself.y_train = ydef predict(self, X):y_pred = [self._predict(x) for x in X]return np.array(y_pred)def _predict(self, x):#Compute distances between x and all examples in the training setdistances = [euclidean_distance(x, x_train) for x_train in self.X_train]#Sort by distance and return indices of the first k neighborsk_idx = np.argsort(distances)[:self.k]#Extract the labels of the k nearest neighbor training samplesk_neighbor_labels = [self.y_train[i] for i in k_idx]  #Return the most common class labelmost_common = Counter(k_neighbor_labels).most_common(1)return most_common[0][0]

这个代码实现的KNN类可以接受一个超参数K和训练数据集（X_train，y_train），并且能够对给定的测试数据集X做出预测。可以使用以下代码进行测试：

from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_scoredata = datasets.load_iris()
X = data.data
y = data.targetX_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=123)knn = KNN(k=3)
knn.fit(X_train, y_train)
y_pred = knn.predict(X_test)print("Accuracy:", accuracy_score(y_test, y_pred))