KNN-邻近算法

K最近邻(K-Nearest Neighbor, KNN)算法是一种基本分类与回归方法，该方法的思想非常简单：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。

算法原理

KNN算法的工作原理可以概括为以下步骤：

计算测试样本与训练集中每个样本的距离
按距离递增排序
选取与当前样本距离最小的k个样本
统计这k个样本中每个类别的频数
返回频数最高的类别作为测试样本的预测类别

距离计算方法

在KNN算法中，常用的距离计算方法有：

欧氏距离（最常用）： $d(x, y) = \sqrt{\sum_{i=1}^{n}(x_i - y_i)^2}$
曼哈顿距离： $d(x, y) = \sum_{i=1}^{n}|x_i - y_i|$
闵可夫斯基距离： $d(x, y) = (\sum_{i=1}^{n}|x_i - y_i|^p)^{\frac{1}{p}}$

代码实现

使用scikit-learn库

from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.datasets import load_iris
from sklearn.metrics import accuracy_score

# 加载鸢尾花数据集
iris = load_iris()
X = iris.data
y = iris.target

# 划分训练集和测试集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

# 创建KNN分类器
knn = KNeighborsClassifier(n_neighbors=5)

# 训练分类器
knn.fit(X_train, y_train)

# 预测
y_pred = knn.predict(X_test)

# 计算准确率
accuracy = accuracy_score(y_test, y_pred)
print(f"KNN分类器的准确率: {accuracy:.4f}")

从零实现KNN算法

import numpy as np
from collections import Counter

class KNN:
    def __init__(self, k=3):
        self.k = k
  
    def fit(self, X, y):
        self.X_train = X
        self.y_train = y
  
    def predict(self, X):
        predictions = [self._predict(x) for x in X]
        return np.array(predictions)
  
    def _predict(self, x):
        # 计算距离
        distances = [np.sqrt(np.sum((x - x_train) ** 2)) for x_train in self.X_train]
  
        # 获取k个最近邻的索引
        k_indices = np.argsort(distances)[:self.k]
  
        # 获取这k个最近邻的标签
        k_nearest_labels = [self.y_train[i] for i in k_indices]
  
        # 进行多数投票
        most_common = Counter(k_nearest_labels).most_common(1)
        return most_common[0][0]

KNN算法的优缺点

优点

简单易于理解和实现
无需训练
对异常值不敏感
适用于多分类问题

缺点

计算复杂度高，尤其是样本量大时
对特征的缩放敏感
需要大量的存储空间
K值的选择很重要，但没有简单的选择方法

应用场景

KNN算法适用于以下场景：

文本分类
推荐系统
医疗诊断
图像识别

小结

KNN是一种简单有效的分类算法，它不需要对数据进行任何假设，直接基于距离度量来进行分类。尽管它有计算复杂度高的缺点，但在许多应用场景中仍然是一个很好的选择，特别是对于小型数据集和概念证明。

算法原理​

距离计算方法​

代码实现​

使用scikit-learn库​

从零实现KNN算法​

KNN算法的优缺点​

优点​

缺点​

应用场景​

小结​