机器学习：KNN 算法详解
引言
想象一下，你要判断一个新来的同学是什么性格：
- 方法1：观察他的所有特征，分析他的行为模式（复杂方法）
- 方法2：看看他身边最亲近的几个朋友是什么性格，他很可能也是类似的性格（简单方法）
KNN（K-Nearest Neighbors，K近邻）算法就像第二种方法——通过观察"最近的邻居"来判断。它基于一个简单的哲学：物以类聚，人以群分。
本文将用生动的类比、数学表示和实际代码，帮你深入理解 KNN 算法的原理和应用。
第一部分：KNN 算法是什么？
什么是 KNN？
**KNN（K-Nearest Neighbors）**是一种基于实例的学习算法，通过找到与待预测样本最相似的 K 个训练样本，来预测新样本的类别或值。
类比理解：
- 就像"近朱者赤，近墨者黑"——看周围人的特点
- 就像"物以类聚"——相似的东西聚在一起
- 就像"人以群分"——相似的人在一起
核心思想：
- 相似性假设：相似的样本应该有相似的标签
- 局部性假设：局部区域内的样本应该相似
- 懒惰学习：不需要训练过程，直接使用训练数据
类比理解：
- 就像不需要提前学习，遇到新问题时直接找相似的例子
- 就像不需要记忆规律，直接参考相似的情况
KNN 的特点
- 简单直观：算法逻辑简单，容易理解
- 无需训练：不需要训练过程，直接使用数据
- 非参数：不对数据分布做假设
- 适合小数据集：在小数据集上表现良好
- 计算成本高：预测时需要计算所有距离
类比理解：
- 就像不需要提前准备，遇到问题直接找答案
- 就像不需要学习规律，直接参考相似情况
第二部分：KNN 算法的核心原理
基本原理
KNN 算法的核心步骤：
- 计算距离：计算待预测样本与所有训练样本的距离
- 选择邻居：选择距离最近的 K 个样本（K 个邻居）
- 投票决策：根据 K 个邻居的标签进行投票或平均
- 得出结果：选择得票最多的类别（分类）或平均值（回归）
类比理解：
- 就像问周围的 K 个邻居，他们是什么类型，然后投票决定
- 就像看 K 个最相似的人，他们有什么特点，然后推断
数学表示
分类问题
给定训练数据集：
$$
D = {(x_1, y_1), (x_2, y_2), ..., (x_n, y_n)}
$$
其中：
- $x_i$：第 $i$ 个样本的特征向量
- $y_i \in {1, 2, ..., C}$：第 $i$ 个样本的类别标签
- $C$：类别数量
对于新样本 $x$：
-
计算距离：
$$
d(x, x_i) = |x - x_i|
$$ -
找到 K 个最近邻：
$$
N_k(x) = {x_{i_1}, x_{i_2}, ..., x_{i_k}}
$$
其中 $d(x, x_{i_1}) \leq d(x, x_{i_2}) \leq ... \leq d(x, x_{i_k})$。
- 投票决策：
$$
\hat{y} = \arg\max_{c} \sum_{x_i \in N_k(x)} \mathbb{1}(y_i = c)
$$
其中 $\mathbb{1}(y_i = c)$ 是指示函数，如果 $y_i = c$ 则为 1，否则为 0。
类比理解：
- $d(x, x_i)$：就像两个样本的相似度
- $N_k(x)$：就像 K 个最相似的邻居
- $\hat{y}$：就像投票结果
回归问题
对于回归问题，预测值是 K 个邻居的平均值：
$$
\hat{y} = \frac{1}{K} \sum_{x_i \in N_k(x)} y_i
$$
类比理解：
- 就像问 K 个邻居的价格，然后取平均值
- 就像看 K 个相似房子的价格，然后估算
第三部分：KNN 算法详解
算法步骤详解
步骤 1：计算距离
距离度量方法：
1. 欧氏距离（Euclidean Distance）
$$
d(x, y) = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2}
$$
类比理解：
- 就像两点之间的直线距离
- 就像在空间中直接测量的距离
2. 曼哈顿距离（Manhattan Distance）
$$
d(x, y) = \sum_{i=1}^{n} |x_i - y_i|
$$
类比理解：
- 就像在城市中走路的距离（只能沿着街道走）
- 就像只能横着或竖着走的距离
3. 闵可夫斯基距离（Minkowski Distance）
$$
d(x, y) = \left(\sum_{i=1}^{n} |x_i - y_i|^p\right)^{1/p}
$$
其中：
- $p = 1$：曼哈顿距离
- $p = 2$：欧氏距离
- $p = \infty$：切比雪夫距离
代码示例：
import numpy as np
from scipy.spatial.distance import euclidean, cityblock, minkowski
# 示例数据
x1 = np.array([1, 2, 3])
x2 = np.array([4, 5, 6])
# 欧氏距离
euclidean_dist = euclidean(x1, x2)
print(f"欧氏距离：{euclidean_dist:.3f}")
# 曼哈顿距离
manhattan_dist = cityblock(x1, x2)
print(f"曼哈顿距离：{manhattan_dist:.3f}")
# 闵可夫斯基距离（p=3）
minkowski_dist = minkowski(x1, x2, p=3)
print(f"闵可夫斯基距离（p=3）：{minkowski_dist:.3f}")
# 手动计算欧氏距离
manual_euclidean = np.sqrt(np.sum((x1 - x2)**2))
print(f"手动计算欧氏距离：{manual_euclidean:.3f}")
输出：
欧氏距离：5.196
曼哈顿距离：9.000
闵可夫斯基距离（p=3）：4.327
手动计算欧氏距离：5.196
步骤 2：选择 K 个最近邻
K 值的选择：
K 值的影响：
- K 太小：容易受噪声影响，不稳定
- K 太大：可能包含不相关的样本，边界模糊
- K 合适：平衡稳定性和准确性
类比理解：
- K=1：就像只看最近的一个邻居，可能不准确
- K=3：就像看最近的三个邻居，比较平衡
- K=10：就像看最近的十个邻居，可能太泛化
代码示例：
def find_k_nearest_neighbors(X_train, x_new, k=3, distance_metric='euclidean'):
"""
找到 K 个最近邻
参数：
X_train: 训练数据
x_new: 新样本
k: 邻居数量
distance_metric: 距离度量方法
"""
distances = []
for i, x_train in enumerate(X_train):
if distance_metric == 'euclidean':
dist = np.sqrt(np.sum((x_new - x_train)**2))
elif distance_metric == 'manhattan':
dist = np.sum(np.abs(x_new - x_train))
else:
dist = np.sqrt(np.sum((x_new - x_train)**2))
distances.append((i, dist))
# 按距离排序，选择前 K 个
distances.sort(key=lambda x: x[1])
k_nearest_indices = [idx for idx, _ in distances[:k]]
return k_nearest_indices, [dist for _, dist in distances[:k]]
# 示例
X_train = np.array([[1, 2], [2, 3], [3, 4], [5, 6], [6, 7]])
x_new = np.array([2.5, 3.5])
k = 3
indices, distances = find_k_nearest_neighbors(X_train, x_new, k=k)
print(f"新样本：{x_new}")
print(f"K={k} 个最近邻的索引：{indices}")
print(f"距离：{[f'{d:.3f}' for d in distances]}")
print(f"对应的训练样本：")
for idx in indices:
print(f" 样本 {idx}: {X_train[idx]}")
输出：
新样本：[2.5 3.5]
K=3 个最近邻的索引：[1, 2, 0]
距离：['0.707', '0.707', '1.581']
对应的训练样本：
样本 1: [2 3]
样本 2: [3 4]
样本 0: [1 2]
步骤 3：投票决策（分类）
多数投票（Majority Voting）：
def knn_classify(X_train, y_train, x_new, k=3):
"""
KNN 分类
参数：
X_train: 训练特征
y_train: 训练标签
x_new: 新样本
k: 邻居数量
"""
# 找到 K 个最近邻
indices, _ = find_k_nearest_neighbors(X_train, x_new, k)
# 获取 K 个邻居的标签
neighbor_labels = y_train[indices]
# 投票：统计每个类别的票数
from collections import Counter
votes = Counter(neighbor_labels)
# 返回得票最多的类别
predicted_class = votes.most_common(1)[0][0]
return predicted_class, votes
# 示例
X_train = np.array([[1, 2], [2, 3], [3, 4], [5, 6], [6, 7], [7, 8]])
y_train = np.array([0, 0, 0, 1, 1, 1]) # 两类：0 和 1
x_new = np.array([2.5, 3.5])
k = 3
predicted_class, votes = knn_classify(X_train, y_train, x_new, k)
print(f"新样本：{x_new}")
print(f"K={k} 个邻居的投票：{dict(votes)}")
print(f"预测类别：{predicted_class}")
输出：
新样本：[2.5 3.5]
K=3 个邻居的投票：{0: 3}
预测类别：0
步骤 4：平均值计算（回归）
def knn_regress(X_train, y_train, x_new, k=3):
"""
KNN 回归
参数：
X_train: 训练特征
y_train: 训练目标值
x_new: 新样本
k: 邻居数量
"""
# 找到 K 个最近邻
indices, _ = find_k_nearest_neighbors(X_train, x_new, k)
# 获取 K 个邻居的目标值
neighbor_values = y_train[indices]
# 计算平均值
predicted_value = np.mean(neighbor_values)
return predicted_value, neighbor_values
# 示例
X_train = np.array([[1], [2], [3], [5], [6], [7]])
y_train = np.array([10, 20, 30, 50, 60, 70])
x_new = np.array([2.5])
k = 3
predicted_value, neighbor_values = knn_regress(X_train, y_train, x_new, k)
print(f"新样本：{x_new}")
print(f"K={k} 个邻居的值：{neighbor_values}")
print(f"预测值（平均值）：{predicted_value:.2f}")
输出：
新样本：[2.5]
K=3 个邻居的值：[20 30 10]
预测值（平均值）：20.00
第四部分：KNN 解决什么问题？
1. 分类问题（Classification）
问题类型： 预测离散的类别标签
实际应用：
- 图像分类：识别图片中的物体
- 文本分类：判断邮件是正常邮件还是垃圾邮件
- 医疗诊断：根据症状判断疾病类型
- 推荐系统：根据用户行为推荐商品类别
类比理解：
- 就像判断一个新来的人是朋友还是陌生人
- 就像判断一个水果是苹果还是香蕉
完整示例：
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score, classification_report
import matplotlib.pyplot as plt
import numpy as np
# 加载数据
iris = load_iris()
X, y = iris.data, iris.target
# 划分数据集
X_train, X_test, y_train, y_test = train_test_split(
X, y, test_size=0.3, random_state=42
)
# 训练 KNN 分类器
knn_classifier = KNeighborsClassifier(n_neighbors=3)
knn_classifier.fit(X_train, y_train)
# 预测
y_pred = knn_classifier.predict(X_test)
# 评估
accuracy = accuracy_score(y_test, y_pred)
print(f"KNN 分类准确率：{accuracy:.3f}")
print("\n分类报告：")
print(classification_report(y_test, y_pred, target_names=iris.target_names))
输出示例：
KNN 分类准确率：1.000
分类报告：
precision recall f1-score support
setosa 1.00 1.00 1.00 19
versicolor 1.00 1.00 1.00 13
virginica 1.00 1.00 1.00 13
accuracy 1.00 45
macro avg 1.00 1.00 1.00 45
weighted avg 1.00 1.00 1.00 45
2. 回归问题（Regression）
问题类型： 预测连续的数值
实际应用：
- 房价预测：根据房子特征预测价格
- 销量预测：根据历史数据预测未来销量
- 温度预测：根据历史温度预测未来温度
- 股票价格：根据历史价格预测未来价格
类比理解：
- 就像根据周围房子的价格估算新房子价格
- 就像根据相似商品的价格估算新商品价格
完整示例：
from sklearn.datasets import make_regression
from sklearn.neighbors import KNeighborsRegressor
from sklearn.metrics import mean_squared_error, r2_score
import matplotlib.pyplot as plt
# 生成回归数据
X_reg, y_reg = make_regression(n_samples=100, n_features=1,
noise=10, random_state=42)
# 划分数据集
X_train_reg, X_test_reg, y_train_reg, y_test_reg = train_test_split(
X_reg, y_reg, test_size=0.3, random_state=42
)
# 训练 KNN 回归器
knn_regressor = KNeighborsRegressor(n_neighbors=5)
knn_regressor.fit(X_train_reg, y_train_reg)
# 预测
y_pred_reg = knn_regressor.predict(X_test_reg)
# 评估
mse = mean_squared_error(y_test_reg, y_pred_reg)
rmse = np.sqrt(mse)
r2 = r2_score(y_test_reg, y_pred_reg)
print(f"KNN 回归结果：")
print(f" RMSE：{rmse:.2f}")
print(f" R²：{r2:.3f}")
# 可视化
plt.figure(figsize=(10, 6))
plt.scatter(X_test_reg, y_test_reg, alpha=0.5, label='真实值')
plt.scatter(X_test_reg, y_pred_reg, alpha=0.5, label='预测值')
plt.xlabel('特征')
plt.ylabel('目标值')
plt.title('KNN 回归结果')
plt.legend()
plt.grid(True, alpha=0.3)
plt.show()
第五部分：K 值的选择
K 值的影响
不同 K 值的效果：
from sklearn.datasets import make_classification
from sklearn.model_selection import cross_val_score
# 生成分类数据
X_clf, y_clf = make_classification(n_samples=200, n_features=2,
n_redundant=0, n_informative=2,
n_clusters_per_class=1, random_state=42)
# 测试不同的 K 值
k_values = range(1, 21)
cv_scores = []
for k in k_values:
knn = KNeighborsClassifier(n_neighbors=k)
scores = cross_val_score(knn, X_clf, y_clf, cv=5, scoring='accuracy')
cv_scores.append(scores.mean())
# 可视化
plt.figure(figsize=(10, 6))
plt.plot(k_values, cv_scores, 'o-', linewidth=2, markersize=8)
plt.xlabel('K 值')
plt.ylabel('交叉验证准确率')
plt.title('K 值对模型性能的影响')
plt.grid(True, alpha=0.3)
plt.axvline(x=np.argmax(cv_scores) + 1, color='r', linestyle='--',
label=f'最优 K={np.argmax(cv_scores) + 1}')
plt.legend()
plt.show()
print(f"最优 K 值：{np.argmax(cv_scores) + 1}")
print(f"最优准确率：{max(cv_scores):.3f}")
K 值选择的经验法则：
- K = 1：最敏感，容易过拟合
- K = 3 或 5：常用选择，平衡稳定性和准确性
- K = sqrt(n)：其中 n 是训练样本数，常用启发式方法
- K 为奇数：避免平票（分类问题）
类比理解：
- K=1：就像只看最近的一个邻居，可能不准确
- K=3-5：就像看最近的几个邻居，比较平衡
- K=10+：就像看很多邻居，可能太泛化
第六部分：KNN 算法的优缺点
优点
- 简单直观：算法逻辑简单，容易理解和实现
- 无需训练：不需要训练过程，直接使用数据
- 非参数：不对数据分布做假设，适应性强
- 适合非线性问题：可以处理复杂的非线性关系
- 多分类友好：天然支持多分类问题
类比理解：
- 就像不需要提前学习，遇到问题直接找答案
- 就像不需要假设数据规律，直接参考相似情况
缺点
- 计算成本高：预测时需要计算所有距离
- 内存消耗大：需要存储所有训练数据
- 对噪声敏感：K 值太小时容易受噪声影响
- 特征缩放重要：不同特征的尺度影响距离计算
- 不适合高维数据：高维空间中距离失效（维度灾难）
类比理解：
- 就像每次都要检查所有数据，计算量大
- 就像需要记住所有数据，内存消耗大
- 就像在很高维的空间中，距离概念失效
改进方法
1. 使用 KD 树加速
from sklearn.neighbors import KNeighborsClassifier
from sklearn.neighbors import KDTree
# KD 树加速查找
knn_kdtree = KNeighborsClassifier(n_neighbors=3, algorithm='kd_tree')
knn_kdtree.fit(X_train, y_train)
类比理解：
- 就像用索引快速查找，而不是遍历所有数据
- 就像用目录快速定位，而不是逐页查找
2. 特征标准化
from sklearn.preprocessing import StandardScaler
# 标准化特征
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)
# 使用标准化后的数据
knn_scaled = KNeighborsClassifier(n_neighbors=3)
knn_scaled.fit(X_train_scaled, y_train)
y_pred_scaled = knn_scaled.predict(X_test_scaled)
类比理解：
- 就像统一单位，让不同特征可以公平比较
- 就像统一尺度，让距离计算更准确
3. 加权 KNN
# 使用距离加权（距离越近权重越大）
knn_weighted = KNeighborsClassifier(n_neighbors=5, weights='distance')
knn_weighted.fit(X_train, y_train)
类比理解：
- 就像给更近的邻居更高的投票权重
- 就像更信任更相似的人的意见
第七部分：KNN 算法的实际应用
应用 1：手写数字识别
from sklearn.datasets import load_digits
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score, confusion_matrix
import seaborn as sns
# 加载手写数字数据
digits = load_digits()
X_digits, y_digits = digits.data, digits.target
# 划分数据集
X_train_digits, X_test_digits, y_train_digits, y_test_digits = train_test_split(
X_digits, y_digits, test_size=0.2, random_state=42
)
# 训练 KNN 分类器
knn_digits = KNeighborsClassifier(n_neighbors=3)
knn_digits.fit(X_train_digits, y_train_digits)
# 预测
y_pred_digits = knn_digits.predict(X_test_digits)
# 评估
accuracy_digits = accuracy_score(y_test_digits, y_pred_digits)
print(f"手写数字识别准确率：{accuracy_digits:.3f}")
# 混淆矩阵
cm = confusion_matrix(y_test_digits, y_pred_digits)
plt.figure(figsize=(10, 8))
sns.heatmap(cm, annot=True, fmt='d', cmap='Blues')
plt.title('手写数字识别混淆矩阵')
plt.ylabel('真实标签')
plt.xlabel('预测标签')
plt.show()
应用 2：房价预测
import pandas as pd
from sklearn.preprocessing import StandardScaler
# 生成房价数据
np.random.seed(42)
n_samples = 200
data = {
'面积': np.random.randint(50, 200, n_samples),
'房间数': np.random.randint(1, 6, n_samples),
'距离地铁': np.random.uniform(0.5, 5.0, n_samples)
}
df_house = pd.DataFrame(data)
df_house['价格'] = (df_house['面积'] * 3 +
df_house['房间数'] * 50 +
df_house['距离地铁'] * (-10) +
np.random.normal(0, 20, n_samples))
# 准备数据
X_house = df_house[['面积', '房间数', '距离地铁']].values
y_house = df_house['价格'].values
# 划分数据集
X_train_house, X_test_house, y_train_house, y_test_house = train_test_split(
X_house, y_house, test_size=0.2, random_state=42
)
# 标准化
scaler_house = StandardScaler()
X_train_house_scaled = scaler_house.fit_transform(X_train_house)
X_test_house_scaled = scaler_house.transform(X_test_house)
# 训练 KNN 回归器
knn_house = KNeighborsRegressor(n_neighbors=5)
knn_house.fit(X_train_house_scaled, y_train_house)
# 预测
y_pred_house = knn_house.predict(X_test_house_scaled)
# 评估
rmse_house = np.sqrt(mean_squared_error(y_test_house, y_pred_house))
r2_house = r2_score(y_test_house, y_pred_house)
print(f"房价预测结果：")
print(f" RMSE：{rmse_house:.2f} 万元")
print(f" R²：{r2_house:.3f}")
# 可视化
plt.figure(figsize=(10, 6))
plt.scatter(y_test_house, y_pred_house, alpha=0.6)
plt.plot([y_test_house.min(), y_test_house.max()],
[y_test_house.min(), y_test_house.max()], 'r--', lw=2)
plt.xlabel('真实价格（万元）')
plt.ylabel('预测价格（万元）')
plt.title('房价预测结果')
plt.grid(True, alpha=0.3)
plt.show()
应用 3：推荐系统
# 简单的推荐系统示例
# 根据用户的历史行为，推荐相似用户喜欢的物品
# 用户-物品评分矩阵（示例）
user_item_matrix = np.array([
[5, 4, 0, 0, 3], # 用户1
[4, 5, 3, 0, 0], # 用户2
[0, 0, 5, 4, 0], # 用户3
[0, 0, 4, 5, 0], # 用户4
[3, 0, 0, 0, 5] # 用户5
])
def recommend_items(user_id, user_item_matrix, k=2):
"""
使用 KNN 推荐物品
参数：
user_id: 用户ID（0-based）
user_item_matrix: 用户-物品矩阵
k: 邻居数量
"""
# 找到 K 个最相似的用户
user_vector = user_item_matrix[user_id]
similarities = []
for i, other_user in enumerate(user_item_matrix):
if i != user_id:
# 计算余弦相似度
similarity = np.dot(user_vector, other_user) / (
np.linalg.norm(user_vector) * np.linalg.norm(other_user) + 1e-10
)
similarities.append((i, similarity))
# 选择最相似的 K 个用户
similarities.sort(key=lambda x: x[1], reverse=True)
k_nearest_users = [uid for uid, _ in similarities[:k]]
# 推荐这些用户喜欢但当前用户未评分的物品
recommendations = {}
for uid in k_nearest_users:
for item_id in range(len(user_item_matrix[uid])):
if user_item_matrix[user_id, item_id] == 0 and user_item_matrix[uid, item_id] > 0:
if item_id not in recommendations:
recommendations[item_id] = 0
recommendations[item_id] += user_item_matrix[uid, item_id]
# 按评分排序
sorted_recommendations = sorted(recommendations.items(),
key=lambda x: x[1], reverse=True)
return sorted_recommendations
# 为用户0推荐物品
recommendations = recommend_items(0, user_item_matrix, k=2)
print("为用户0推荐的物品：")
for item_id, score in recommendations:
print(f" 物品 {item_id}：推荐分数 {score:.2f}")
第八部分：KNN 算法的可视化
决策边界可视化
from matplotlib.colors import ListedColormap
def plot_decision_boundary(X, y, model, title="KNN 决策边界"):
"""
可视化 KNN 的决策边界
"""
# 创建网格
h = 0.02
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
np.arange(y_min, y_max, h))
# 预测网格点
Z = model.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
# 绘制
plt.figure(figsize=(10, 8))
cmap_light = ListedColormap(['#FFAAAA', '#AAFFAA', '#AAAAFF'])
cmap_bold = ListedColormap(['#FF0000', '#00FF00', '#0000FF'])
plt.contourf(xx, yy, Z, cmap=cmap_light, alpha=0.8)
plt.scatter(X[:, 0], X[:, 1], c=y, cmap=cmap_bold, edgecolors='black', s=50)
plt.title(title)
plt.xlabel('特征1')
plt.ylabel('特征2')
plt.show()
# 生成2D分类数据
X_2d, y_2d = make_classification(n_samples=200, n_features=2,
n_redundant=0, n_informative=2,
n_clusters_per_class=1, random_state=42)
# 训练不同 K 值的模型
for k in [1, 3, 10]:
knn_k = KNeighborsClassifier(n_neighbors=k)
knn_k.fit(X_2d, y_2d)
plot_decision_boundary(X_2d, y_2d, knn_k, title=f"KNN 决策边界 (K={k})")
第九部分：KNN 算法的变体
1. 加权 KNN
距离加权： 距离越近的邻居权重越大
# 使用距离加权
knn_weighted = KNeighborsClassifier(n_neighbors=5, weights='distance')
knn_weighted.fit(X_train, y_train)
类比理解：
- 就像更信任更相似的人的意见
- 就像给更近的邻居更高的投票权重
2. 半径 KNN
基于半径： 选择距离小于某个半径的所有邻居
from sklearn.neighbors import RadiusNeighborsClassifier
# 基于半径的 KNN
radius_knn = RadiusNeighborsClassifier(radius=1.0)
radius_knn.fit(X_train, y_train)
类比理解：
- 就像选择一定范围内的所有邻居
- 就像选择距离小于某个值的所有样本
3. 局部敏感哈希（LSH）
加速高维数据： 使用哈希表加速查找
类比理解：
- 就像用索引快速查找
- 就像用哈希表加速搜索
总结
核心概念回顾
-
KNN 算法：基于实例的学习算法
- 核心思想：物以类聚，人以群分
- 通过 K 个最近邻进行预测
-
算法步骤：
- 计算距离
- 选择 K 个最近邻
- 投票决策（分类）或平均值（回归）
-
距离度量：
- 欧氏距离：直线距离
- 曼哈顿距离：城市距离
- 其他距离：闵可夫斯基距离等
-
K 值选择：
- K 太小：容易过拟合
- K 太大：可能欠拟合
- 常用：K=3 或 5，或 K=sqrt(n)
-
优缺点：
- 优点：简单直观、无需训练、非参数
- 缺点：计算成本高、内存消耗大、对噪声敏感
关键要点
KNN 的核心思想：
- 相似性假设：相似的样本应该有相似的标签
- 局部性假设：局部区域内的样本应该相似
- 懒惰学习：不需要训练过程，直接使用数据
适用场景：
- 小到中等规模的数据集
- 非线性问题
- 多分类问题
- 需要可解释性的场景
不适用场景：
- 大规模数据集（计算成本高）
- 高维数据（维度灾难）
- 需要快速预测的场景
类比总结
理解 KNN 算法，就像理解"物以类聚"的道理：
- 核心思想：就像看周围人的特点，推断一个人的特点
- 算法步骤：就像找最近的 K 个邻居，然后投票决定
- 距离度量：就像衡量两个人有多相似
- K 值选择：就像决定问几个人，问太少不准确，问太多太泛化
掌握 KNN 算法，你就能理解基于实例学习的核心思想！
参考资料
- Cover, T., & Hart, P. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13(1), 21-27.
- Altman, N. S. (1992). An introduction to kernel and nearest-neighbor nonparametric regression. The American Statistician, 46(3), 175-185.
- Scikit-learn KNN 文档