04 最近邻分类器 (K-Nearest Neighbors)

今天的议题:信用风险评估

假设你是一位信贷经理,一位新客户前来申请贷款。

你的核心任务是:

  • 评估风险:这位客户未来违约的可能性有多大?
  • 做出决策:是批准还是拒绝这笔贷款?

这是一个典型的商业分类问题

数据驱动的解决方案

你并非毫无根据地猜测。你的银行拥有宝贵的历史数据。

  • 现有数据: 数千名历史客户的完整记录。
    • 特征 (Features): 收入、负债、年龄、职业…
    • 结果 (Outcome): 按时还款 ✅ 或 违约 ❌
  • 我们的方法: 利用这些数据,为新客户的风险画像,这就是最近邻 (KNN) 算法的用武之地。

KNN的核心思想:“物以类聚,人以群分”

KNN算法的哲学非常简单:要判断一个新样本的类别,只需看离它最近的几个“邻居”属于哪个类别。

就像你要判断一个陌生人的兴趣爱好,最简单的方法就是看看他交往最密切的朋友们都是些什么样的人。

? 类别 A 类别 B k=3 邻域 2个 类别A, 1个 类别B ⇒ 判定为 类别A

KNN的商业类比

机器学习概念 商业场景类比 (信用评估)
新样本 (未知类别) 一位新的贷款申请人
邻居 (已知类别) 数据库中与新申请人情况最相似的历史客户
类别 ‘会违约’ 或 ‘不会违约’
“近”的度量 客户特征的相似度 (如收入、年龄、负债)
K值 我们参考多少个相似的客户来做决定?

本章学习路线图

  1. 基础理论: 深入理解KNN的三个核心要素 (距离, K值, 决策)。
  2. 代码实战: 使用Python从零开始构建一个乳腺癌诊断分类器。
  3. 模型优化: 学习如何寻找最优K值,并了解加权KNN
  4. 扩展应用: 探索如何将KNN用于回归问题 (如预测房价)。
  5. 效率和挑战: 讨论数据规模高维度带来的挑战及解决方案。
  6. 总结: 全面分析KNN的优缺点及在商业中的应用。

4.1 最近邻规则 (k-NN) 的正式定义

给定一个待分类样本 \(x_n\),KNN的决策过程分为两步:

  1. 寻找邻居: 在整个数据集中,找出与 \(x_n\) 距离最近\(k\) 个样本。
  2. 投票决策: 在这 \(k\) 个邻居中,采用多数表决的方式,将得票最多的那个类别作为 \(x_n\) 的预测类别。

\[ \large{y_n = \underset{c \in \mathcal{Y}}{\arg\max} \sum_{i=1}^k I(y_i = c)} \qquad(1)\]

其中,\(I(\cdot)\) 是指示函数,如果邻居 \(i\) 的类别 \(y_i\) 等于类别 \(c\),则为1,否则为0。这个公式本质上就是在数票数

理解KNN的三个关键要素

要成功应用KNN算法,我们必须明确定义三个核心要素。它们是构建任何KNN模型的基石。

  • 距离度量 (Distance Metric)
    • 如何量化样本之间的“相似性”?
  • \(k\) 值的选择 (The Choice of \(k\))
    • 应该看多少个邻居?一个还是十个?
  • 决策规则 (Decision Rule)
    • 如何根据邻居做出最终判断?(例如,简单投票)

关键要素 1: 距离度量

如何定义“近”?这取决于我们选择的距离度量。

距离度量 两个点之间用一条带刻度的线连接,表示距离的度量。 Distance Metric 样本 A 样本 B d(A, B) = ?

关键要素 2: k值的选择

参考多少个邻居?这是模型复杂度的关键开关。

k值的选择 (The Choice of k) k=3 k=8

关键要素 3: 决策规则

如何汇总邻居的“意见”?最常见的是少数服从多数。

决策规则: 多数投票 (Decision Rule: Majority Vote) k=5 邻居的类别 最终决策: 类别 A (Final Decision: Class A)

深入探讨:距离度量

样本间的相似性是通过距离函数来度量的。对于两个 \(d\) 维的样本 \(x_i\)\(x_j\),常见的距离度量有:

  • 欧几里得距离 (Euclidean Distance): 我们最熟悉的直线距离,也是KNN中最常用的。 \[ \large{L_2(x_i, x_j) = \sqrt{\sum_{l=1}^d (x_{il} - x_{jl})^2}} \]

  • 曼哈顿距离 (Manhattan Distance): 想象在城市街道上开车,只能沿着网格线走。 \[ \large{L_1(x_i, x_j) = \sum_{l=1}^d |x_{il} - x_{jl}|} \]

可视化距离度量

欧几里得距离是“抄近道”,曼哈顿距离是“走街区”。

欧几里得 vs. 曼哈顿距离 (Euclidean vs. Manhattan) 点 A (xA, yA) 点 B (xB, yB) |xₓ - xₐ| |yₐ - yₓ| 曼哈顿距离 (L₁) 只能沿坐标轴移动 如同在城市街区行走 距离是各轴向位移之和 L₁ = |xₓ - xₐ| + |yₐ - yₓ| 欧几里得距离 (L₂) 两点间最短的直线路径 即“抄近道”,基于勾股定理 计算斜边长度。 L₂ = √((xₓ-xₐ)² + (yₐ-yₓ)²)

关键前提:数据标准化

重要提示: 距离度量对特征的尺度 (scale) 非常敏感。

  • 问题: 如果“年收入”(单位:万)和“年龄”(单位:岁)直接计算距离,收入的巨大数值会完全主导距离计算,年龄的作用将微乎其微。
  • 解决方案: 数据标准化 (Standardization)。将所有特征转换到相似的尺度上(例如,均值为0,标准差为1)。

在应用KNN之前,数据标准化几乎是必不可少的一步。

为什么标准化至关重要?

1. 标准化之前 (Before) 收入 (范围: 10k-100k) 年龄 (范围: 20-60) A B 效果: 距离计算被“收入”特征主导。 Δ收入 的巨大数值会完全淹没 Δ年龄 的微小贡献。 2. 标准化之后 (After) 收入 Z-score 年龄 Z-score A' B' 效果: 所有特征都被转换到同一尺度。 ΔZ-收入 ΔZ-年龄 对最终距离 的贡献变得均等且公平。

深入探讨:k值的选择

\(k\) 值的选择直接影响模型的性能,它是一个偏差-方差权衡 (Bias-Variance Tradeoff) 的过程。

  • 较小的 \(k\):
    • 模型更复杂,决策边界更不规则。
    • 容易受到噪声数据的影响,导致过拟合 (Overfitting)
    • 低偏差 (Low Bias),高方差 (High Variance)。
  • 较大的 \(k\):
    • 模型更简单,决策边界更平滑。
    • 会忽略数据中局部的、细微的结构,导致欠拟合 (Underfitting)
    • 高偏差 (High Bias),低方差 (Low Variance)。

小 k值: 高度灵活,容易过拟合

当 k 很小时 (例如 k=1),模型决策边界会变得非常曲折,试图去完美匹配每一个训练数据点,包括噪声。

KNN算法: k=1 如何导致过拟合 (Overfitting) 待分类点 (New Point) 唯一的最近邻 (k=1) (一个噪声/离群点) 1. 找到最近的 1 个邻居。 2. 该邻居是 粉色方块 (一个离群点)。 3. 错误分类: 新点被标记为 粉色 (模型对噪声过于敏感)

大 k值: 高度平滑,容易欠拟合

当 k 很大时 (例如 k=N),模型会忽略数据的局部结构,决策边界变得过于简单,无法捕捉类别间的差异。

KNN算法: k值过大导致欠拟合 (Underfitting) 分类为 蓝色区域 分类为 红色区域 分析 (k 值极大): 1. 邻域(黄圈)几乎包含所有样本。 2. 全局来看, 蓝色圆点 是多数类别。 3. 新点被判为蓝色,局部红色簇被忽略。 → 导致决策边界过于平滑, 产生欠拟合。

寻找最优 k 值

那么,如何找到那个“刚刚好”的 \(k\) 值呢?

  • 答案不是猜的:我们不能凭感觉选择。
  • 系统性方法: 通常使用交叉验证 (Cross-Validation)。我们将数据分成几份,轮流使用一部分作为“迷你测试集”来评估不同 \(k\) 值的表现,最终选择表现最好的那个 \(k\)

我们将在稍后的Python实践中演示这个过程。

让我们通过一个例子来可视化KNN

假设我们有一组关于肿瘤的数据,分为“良性”和“恶性”两类。现在来了一个新的病人(用 ? 表示),我们需要判断其肿瘤是良性还是恶性。

Figure 1: 一个新样本和已标记的肿瘤数据

当 k=1 时: 最近的邻居决定一切

1-NN是最简单的KNN形式。我们只看距离最近的那一个邻居。

在这个例子中,离新病人最近的样本是“恶性”类,所以1-NN会将其分类为恶性。这可能是一个受噪声影响的错误判断。

Figure 2: 1-NN的决策过程

当 k=5 时: 多数投票,结果反转

现在,我们将 \(k\) 增加到 5,考察最近的5个邻居。

  • 在这5个邻居中,有4个是“良性”,1个是“恶性”。
  • 根据多数投票原则 (4 > 1),5-NN会将其分类为良性

这个例子清晰地表明了 \(k\) 值的选择对最终结果有决定性影响。

Figure 3: 5-NN的决策过程

实践:用Python实现KNN进行乳腺癌诊断

理论讲完了,现在我们动手实践。我们将使用一个经典的真实世界数据集——威斯康星州乳腺癌数据集。

  • 目标: 根据肿瘤的多种生理指标(如半径、质地、周长等),预测其是良性还是恶性。
  • 工具: scikit-learn,一个强大的Python机器学习库。
  • 流程:
    1. 数据加载与探索
    2. 数据预处理与划分
    3. 模型训练与预测
    4. 寻找最优k值

Step 1: 加载并探索数据

首先,我们加载scikit-learn内置的数据集,并查看其基本信息。这个数据集包含569个样本和30个数值型特征。

from sklearn.datasets import load_breast_cancer
import pandas as pd

# Load the dataset
cancer = load_breast_cancer()
X_cancer = pd.DataFrame(cancer.data, columns=cancer.feature_names)
y_cancer = pd.Series(cancer.target).map({0: '恶性', 1: '良性'})

print('数据集维度 (样本数, 特征数):', X_cancer.shape)
print('\n前5行数据预览:')
# Display the head of the DataFrame for a quick look at the features
with pd.option_context('display.max_columns', 5, 'display.width', 100):
    print(X_cancer.head())
数据集维度 (样本数, 特征数): (569, 30)

前5行数据预览:
   mean radius  mean texture  ...  worst symmetry  worst fractal dimension
0        17.99         10.38  ...          0.4601                  0.11890
1        20.57         17.77  ...          0.2750                  0.08902
2        19.69         21.25  ...          0.3613                  0.08758
3        11.42         20.38  ...          0.6638                  0.17300
4        20.29         14.34  ...          0.2364                  0.07678

[5 rows x 30 columns]

Step 2: 数据预处理与划分

KNN算法依赖于距离计算,因此特征的尺度统一非常重要。我们将使用StandardScaler进行标准化。

然后,我们将数据划分为训练集(用于训练模型)和测试集(用于评估模型性能)。

from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler

# 1. Standardize the features to have mean=0 and variance=1
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X_cancer)

# 2. Split data into training and testing sets (70% train, 30% test)
# stratify=y_cancer 确保训练集和测试集中的类别比例与原始数据集相同
X_train, X_test, y_train, y_test = train_test_split(
    X_scaled, y_cancer, test_size=0.3, random_state=42, stratify=y_cancer
)

print(f'训练集大小: {X_train.shape} 样本')
print(f'测试集大小: {X_test.shape} 样本')
训练集大小: (398, 30) 样本
测试集大小: (171, 30) 样本

Step 3: 训练KNN模型并进行预测

使用scikit-learn训练一个KNN分类器非常简单。我们先选择一个常见的 \(k=5\) 作为起点。

from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score

# 初始化分类器,并设置 k=5
knn_clf = KNeighborsClassifier(n_neighbors=5)

# 在训练数据上训练模型
knn_clf.fit(X_train, y_train)

# 在未见过的测试数据上进行预测
y_pred = knn_clf.predict(X_test)

# 计算准确率: (正确预测数) / (总预测数)
accuracy = accuracy_score(y_test, y_pred)
print(f'当 k=5 时,模型在测试集上的准确率为: {accuracy:.4f}')
当 k=5 时,模型在测试集上的准确率为: 0.9708

Step 4: 如何找到最优的 k 值?

我们之前提到,\(k\) 值的选择至关重要。我们可以通过循环尝试不同的 \(k\) 值,并计算每个 \(k\) 值对应的测试集准确率,从而找到最优的 \(k\)

import matplotlib.pyplot as plt
import numpy as np
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score

# --- Recalculate from previous cell ---
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
cancer = load_breast_cancer()
y_cancer = pd.Series(cancer.target)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(cancer.data)
X_train, X_test, y_train, y_test = train_test_split(
    X_scaled, y_cancer, test_size=0.3, random_state=42, stratify=y_cancer
)
# --- End recalculate ---

# 我们将测试 k 值从 1 到 30
k_range = range(1, 31)
test_scores = []

# 遍历每个 k 值
for k_val in k_range:
    knn_loop = KNeighborsClassifier(n_neighbors=k_val)
    knn_loop.fit(X_train, y_train)
    y_pred_loop = knn_loop.predict(X_test)
    test_scores.append(accuracy_score(y_test, y_pred_loop))

# 找到准确率最高的 k 值
best_k = k_range[np.argmax(test_scores)]
best_accuracy = max(test_scores)

# --- Visualization ---

plt.figure(figsize=(10, 6))
plt.plot(k_range, test_scores, marker='o', linestyle='--', color='royalblue', mfc='skyblue')
plt.title(f'模型准确率随k值的变化', fontsize=18, pad=15)
plt.xlabel('k值 (邻居数量)', fontsize=14)
plt.ylabel('测试集准确率', fontsize=14)
plt.axvline(best_k, color='red', linestyle=':', linewidth=2, label=f'最优 k = {best_k}\n准确率 = {best_accuracy:.4f}')
plt.xticks(np.arange(0, 31, 2))
plt.grid(True, linestyle='--', alpha=0.6)
plt.legend(fontsize=12)
plt.tight_layout()
plt.show()
Figure 4: 不同k值对模型准确率的影响

结果分析:k=7 时模型性能最佳

上图的分析告诉我们:

  • \(k\) 很小(例如1或2)时,模型可能过拟合,准确率不高。
  • 随着 \(k\) 的增加,准确率先上升后下降。
  • 在这个特定问题中,当 \(k=7\) 时,模型在测试集上的表现最好,准确率达到了约 97.08%

这是一个非常强大的结果,表明KNN可以有效地用于医疗诊断等实际应用。

4.2 加权最近邻分类器 (Weighted k-NN)

标准的KNN模型中,每个邻居的“投票权重”是相等的。但这是否合理?

  • 直觉: 距离更近的邻居应该比距离远的邻居更有发言权。
  • 解决方案: 加权最近邻 (Weighted k-NN)。根据邻居的远近来分配投票权重。

一种常见的加权方式是使用距离的倒数作为权重。

\[ \large{y_n = \underset{c \in \mathcal{Y}}{\arg\max} \sum_{i=1}^k w_i \cdot I(y_i = c) \quad \text{, where } w_i = \frac{1}{\text{distance}(x_n, x_i)}} \]

加权KNN的直观解释

近的邻居“嗓门大”,远的邻居“嗓门小”。

加权KNN (Weighted KNN) 距离越近,权重越大 待分类点 权重: 0.8 权重: 0.3 权重: 0.2 权重累加与决策 标准KNN (k=3): 1票 vs 2票 粉色 加权KNN: Σ W(紫色): 0.8 Σ W(粉色): 0.5 (0.3+0.2) 结论: 分类为紫色

加权KNN在scikit-learn中的实现

scikit-learn中,实现加权KNN非常简单,只需在初始化分类器时设置 weights='distance' 参数。

# --- Recalculate from previous cells to ensure context ---
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score
import pandas as pd
cancer = load_breast_cancer()
y_cancer = pd.Series(cancer.target)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(cancer.data)
X_train, X_test, y_train, y_test = train_test_split(
    X_scaled, y_cancer, test_size=0.3, random_state=42, stratify=y_cancer
)
# --- End recalculate ---

# 我们从上一步骤得知最优k为7
best_k = 7 

# 训练一个标准KNN模型 (权重统一)
knn_standard = KNeighborsClassifier(n_neighbors=best_k, weights='uniform')
knn_standard.fit(X_train, y_train)
accuracy_standard = accuracy_score(y_test, knn_standard.predict(X_test))

# 训练一个加权KNN模型 (权重基于距离)
knn_weighted = KNeighborsClassifier(n_neighbors=best_k, weights='distance')
knn_weighted.fit(X_train, y_train)
accuracy_weighted = accuracy_score(y_test, knn_weighted.predict(X_test))

print(f'标准KNN (k={best_k}) 准确率: {accuracy_standard:.4f}')
print(f'加权KNN (k={best_k}) 准确率: {accuracy_weighted:.4f}')
标准KNN (k=7) 准确率: 0.9649
加权KNN (k=7) 准确率: 0.9649

在这个案例中,加权后的准确率与标准KNN几乎相同,但在其他更复杂的数据集上,加权KNN往往能带来性能提升。

4.3 KNN不仅能分类,还能用于回归预测

KNN的核心思想同样适用于回归问题,即预测一个连续值(如股票价格、房屋售价)。

分类 (Classification)

  • 目标:预测离散的类别
  • 方法:邻居投票
  • 例子:判断邮件是“垃圾”还是“非垃圾”

回归 (Regression)

  • 目标:预测连续的数值
  • 方法:邻居取平均值
  • 例子:预测房屋的售价

KNN回归的数学表达

对于一个新样本,KNN回归模型的预测值是其 \(k\) 个最近邻居的目标值的平均值(或加权平均值)。

\[ \large{\hat{y}_n = \frac{1}{k} \sum_{i=1}^k y_i} \]

其中,\(y_i\) 是第 \(i\) 个邻居的真实数值。

实践:使用KNN预测加州房价

我们使用加州房价数据集,通过房屋的各项特征(如街区收入中位数、房屋年龄)来预测其价格。

import pandas as pd
import numpy as np
from sklearn.datasets import fetch_california_housing
from sklearn.neighbors import KNeighborsRegressor
from sklearn.metrics import mean_squared_error
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler

# 加载并准备数据
housing = fetch_california_housing()
X_h = pd.DataFrame(housing.data, columns=housing.feature_names)
y_h = pd.Series(housing.target) # 目标单位是 $100,000

# 特征标准化和数据划分
scaler_h = StandardScaler()
X_h_scaled = scaler_h.fit_transform(X_h)
X_h_train, X_h_test, y_h_train, y_h_test = train_test_split(X_h_scaled, y_h, test_size=0.3, random_state=42)

# 训练KNN回归模型,k=7
knn_reg = KNeighborsRegressor(n_neighbors=7)
knn_reg.fit(X_h_train, y_h_train)
y_h_pred = knn_reg.predict(X_h_test)

# 使用均方根误差(RMSE)进行评估
rmse = np.sqrt(mean_squared_error(y_h_test, y_h_pred))
print(f'KNN回归模型在测试集上的RMSE为: ${rmse * 100000:,.2f}')
KNN回归模型在测试集上的RMSE为: $64,419.94

可视化KNN回归:阶梯状的预测函数

KNN回归的预测函数不是一条平滑的曲线,而是一个阶梯状的函数。这是因为在一个局部区域内,所有新样本的预测值都将是相同的(即该区域内邻居的平均值)。

Figure 5: KNN回归的阶梯状预测函数 (1维示例)

4.4 现实世界的挑战与解决方案

到目前为止,我们处理的都是理想化的数值型数据。但在商业世界中,数据往往更复杂。

  • 挑战1: 如何处理非数值特征 (如“城市”、“产品类别”)?
  • 挑战2: 当数据量巨大 (百万、千万级) 时怎么办?KNN的预测会变得极慢。

挑战1:处理分类特征 (Categorical Features)

问题: 如何计算包含“北京”和“上海”这类文本特征的样本之间的“距离”?

解决方案:

  1. 独热编码 (One-Hot Encoding): 将分类特征转换为多个0/1的二元特征。这是最常用的方法。
  2. 使用特定的距离度量: 例如,汉明距离 (Hamming Distance),它计算两个等长字符串之间不同位置的字符数。

可视化独热编码 (One-Hot Encoding)

独热编码示意图 一个表格展示了如何将一个'城市'列转换为三个独立的0/1列,用颜色和箭头突出显示转换过程。 城市 北京 上海 广州 转换 城市_京 城市_沪 城市_穗 1 0 0 0 1 0 0 0 1

挑战2:数据规模与预测速度

KNN的一个主要缺点是其计算成本高

  • 训练阶段: 速度极快,几乎没有计算,只是存储数据。
  • 预测阶段: 速度极慢。对于每一个新的待预测样本,都需要计算它与所有训练样本的距离。如果训练集有百万样本,这将是无法接受的。

问题: 如何在不牺牲太多精度的前提下,加快寻找最近邻的速度?

核心思想: 避免“蛮力搜索”

直接计算新样本与所有训练点的距离被称为蛮力搜索 (Brute-force search)

蛮力搜索 (Brute-force Search) 逐一计算所有距离 新样本 (Query) 计算过程: 1. 接收一个新样本点。 2. 遍历数据集中 所有 N 个点。 3. 计算并存储 N 个距离。 (当 N 巨大时成本极高)

加速策略的核心思想是:通过构建智能的数据结构,来快速排除大量不可能成为最近邻的样本点。

加速策略1: KD树 (k-dimensional tree)

KD树是一种经典的空间划分数据结构,它将 \(k\) 维空间递归地划分为一系列超矩形区域。

  • 构建过程:
    1. 选择一个坐标轴(例如,方差最大的轴)。
    2. 找到所有数据点在该轴上的中位数
    3. 用一个垂直于该轴的超平面将空间一分为二。
    4. 对左右两个子空间递归地重复此过程,直到每个区域只包含少量数据点。

KD树如何划分二维空间?

Figure 6: KD树如何递归地划分二维空间

KD树的局限性:高维灾难

虽然KD树在低维空间(例如 \(d < 20\))中非常有效,但随着数据维度 \(d\) 的增加,其性能会迅速下降。

  • 原因: 在高维空间中,所有点之间的距离都趋向于相等,空间变得稀疏,“近邻”这个概念本身也变得模糊。
  • 后果: 当维度很高时,KD树的搜索效率会退化到接近于蛮力搜索。
高维灾难示意图 左侧是一个点分布密集的二维空间,右侧是一个点都分布在遥远角落的抽象高维空间。 低维空间 (d=2) 高维空间 (d >> 20) 所有“邻居”几乎一样远

高维空间的诅咒:为何距离度量会失效?

核心问题:高维空间中的’距离’是什么?

在高维空间中,我们基于低维(2D或3D)生活经验建立的几何直觉往往会失效。

  • 直觉:点与点之间有远有近,总能找到’最近的邻居’。
  • 高维现实:随着维度越来越高,点与点之间的欧氏距离会变得越来越相近。

本讲座旨在通过直观的例子和数学推导,揭示这一反直觉的现象——距离度量的失效

简化模型:切分一个单位超立方体

我们从一个简单的思想实验开始:将单位超立方体 $[0, 1]^d$ 的每个维度都从中点 0.5 处切开。

这会将整个空间分割成 $2^d$ 个相同大小的’小超立方体’。

我们将通过观察一个随机点落在哪个’小立方体’中,来建立对高维空间的初步直觉。

低维直觉:d=1 和 d=2 的情况

在低维空间,靠近原点 (0,0,...) 的区域(即’内层’)和远离原点的区域(‘外壳’)看起来是均衡的。

低维空间切分 一维线段被切分为两部分,二维正方形被切分为四个象限。 维度 d=1 0 0.5 1 内层 [0, 0.5] 外壳 (0.5, 1] 维度 d=2 内层 (1/4) 外壳 (3/4) 0 1 1
Figure 7: 在 d=2 时,$2^2=4$ 个小正方形中,只有一个 ([0, 1/2], [0, 1/2]) 靠近原点。

高维现象:数据点几乎总落在’外壳’上

随着维度 d 的增加,靠近原点的小超立方体的占比 $1/2^d$ 会迅速趋近于0。

维度 (d) 小超立方体总数 (\(2^d\)) 靠近原点的概率 (\(1/2^d\)) 落在’外壳’的概率 (\(1 - 1/2^d\))
1 2 50% 50%
3 8 12.5% 87.5%
10 1,024 ~0.1% 99.9%
100 ~\(1.27 \times 10^{30}\) ~\(7.9 \times 10^{-31}\) ~100%

结论:如果我们在超立方体中随机撒点,当维度足够高时,几乎所有的点都会落在远离原点的’外壳’区域。

从离散到连续:均匀分布下的距离集中

刚才的切分模型是一个简化。现在我们考虑更一般的情况:n 个数据点 $X_1, ..., X_n$ 在单位超立方体 $[0, 1]^d$ 中独立同分布。

核心结论:当维度 d 趋于无穷时,任意两点间距离的最大值与最小值的相对差距趋于0。

\[ \large{ \lim_{d \to \infty} \frac{dist_{max} - dist_{min}}{dist_{min}} = 0 } \]

这意味着,从任何一个点的视角看,其他所有点到它的距离几乎是完全相同的!

数学推导 1:构建距离的随机变量

我们来分析任意两点 $X_i$$X_j$ 之间的距离。

  1. 点的表示: 每个点 $X_j$ 是一个d维向量 $(X_{j1}, ..., X_{jd})^T$
  2. 分量的分布: 每个分量 $X_{jk}$ 独立地服从 U(0, 1) 分布。
    • 期望: $E(X_{jk}) = \frac{1}{2}$
    • 方差: $Var(X_{jk}) = \frac{1}{12}$
  3. 距离的平方: 我们分析欧氏距离的平方 $S_{ij} = ||X_i - X_j||_2^2$,因为它更易于处理。

\[ \large{ S_{ij} = \sum_{k=1}^{d} (X_{ik} - X_{jk})^2 } \]

数学推导 2:计算距离平方的期望

利用期望的线性性质,我们可以计算 $S_{ij}$ 的期望值。

首先,考虑单个维度上差的平方的期望: $E[(X_{ik} - X_{jk})^2]$

根据方差定义 $Var(Y) = E(Y^2) - (E(Y))^2$,我们有: $E[(X_{ik} - X_{jk})^2] = Var(X_{ik} - X_{jk}) + (E[X_{ik} - X_{jk}])^2$

由于 $X_{ik}$$X_{jk}$ 独立同分布:

  • $E[X_{ik} - X_{jk}] = E[X_{ik}] - E[X_{jk}] = \frac{1}{2} - \frac{1}{2} = 0$
  • $Var(X_{ik} - X_{jk}) = Var(X_{ik}) + Var(X_{jk}) = \frac{1}{12} + \frac{1}{12} = \frac{1}{6}$

所以,$E[(X_{ik} - X_{jk})^2] = \frac{1}{6} + 0^2 = \frac{1}{6}$

最终,对所有维度求和: \[ \large{ E(S_{ij}) = E[\sum_{k=1}^{d} (X_{ik} - X_{jk})^2] = \sum_{k=1}^{d} E[(X_{ik} - X_{jk})^2] = \frac{d}{6} } \]

数学推导 3:大数定律的应用

我们已经知道距离平方 $S_{ij}$d 个独立同分布随机变量 $(X_{ik} - X_{jk})^2$ 的和。

根据大数定律,当 d 趋于无穷时,样本均值会依概率收敛于期望值:

\[ \large{ \frac{S_{ij}}{d} = \frac{1}{d} \sum_{k=1}^{d} (X_{ik} - X_{jk})^2 \xrightarrow{p} E[(X_{ik} - X_{jk})^2] = \frac{1}{6} } \]

这意味着,当 d 足够大时,$S_{ij}$ 的值会高度集中在它的期望值 $\frac{d}{6}$ 附近。由于这个结论对任意的 ij 都成立,所以所有点对的距离平方都将趋于同一个值!

概念可视化:距离分布的集中

这个现象可以用距离分布的变化来直观理解。

距离分布的集中现象 一个图表,显示了随着维度d的增加,点对距离的概率分布从宽变窄,最终集中在一个点上。 距离 概率密度 低维度 (d=2) 中等维度 (d=10) 高维度 (d → ∞) E[距离]
Figure 8: 随着维度 d 增加,距离的分布变得越来越窄,最终像一个脉冲函数一样集中在期望值周围。

推广:范数的集中 (Concentration of the Norm)

距离集中的现象不仅仅局限于均匀分布或欧氏距离,它是一个更普遍的规律。

范数集中定理 (直观版): 对于满足某些温和条件的随机向量 $X \in \mathbb{R}^d$ (例如,各分量独立且方差为1),它的L2范数 (即长度) $||X||_2$ 会高度集中在其期望值 $\sqrt{d}$ 附近。

一个更强的结论 (Vershynin, 2018) 表明,对于次高斯向量,这种偏离 $\sqrt{d}$ 的概率会随着维度 d 的增加而指数级衰减。这意味着在高维空间中,随机向量的长度几乎是一个确定性而非随机性的值。

实践意义:为什么’最近邻’会失效?

距离度量的失效对许多依赖于距离计算的算法构成了严峻挑战,特别是 k-最近邻 (k-NN) 算法。

  • k-NN的目标: 找到特征空间中与查询点’最相似’的 k 个邻居。
  • 高维困境: 如果所有邻居到查询点的距离都几乎相等,那么’最近’和’最远’的邻居之间没有实际差别。
  • 结果: 算法的分类或回归结果将变得不稳定且毫无意义,因为选出的’邻居’可能是完全随机的。

总结

  1. 高维几何反直觉: 我们不能将低维空间的直觉直接推广到高维空间。
  2. 质量分布在外壳: 高维空间中的数据点,大概率分布在空间的’边缘’或’外壳’上。
  3. 距离度量集中: 随着维度升高,任意两点间的距离都趋于相等。这种现象被称为距离集中
  4. 算法失效: 这种现象直接导致了依赖距离度量的算法(如k-NN、聚类)在高维数据上的性能严重下降,这就是’高维诅咒’的核心体现之一。

4.5 总结: KNN算法的优缺点

优点 (Pros) 缺点 (Cons)
原理简单,易于实现 计算成本高,预测速度慢
无需训练,模型适应性强 (非参数) ❌ 对内存需求大,需存储所有训练数据
✅ 对数据分布没有假设 ❌ 对不平衡数据敏感 (多数类会主导投票)
✅ 可用于分类和回归 高维灾难问题严重
✅ 决策边界可以非常灵活 ❌ 需要对特征进行标准化

KNN在商业决策中的应用场景

凭借其简单性和灵活性,KNN在多个商业领域都有广泛应用:

  • 金融: 客户信用评级,欺诈交易检测。
  • 市场营销: 客户细分,识别高价值客户群。
  • 推荐系统: “购买了X产品的用户也购买了Y产品”,这是典型的“寻找近邻”问题。
  • 医疗: 疾病诊断,基因模式识别。
  • 零售: 预测顾客购买行为,优化库存。

本章核心知识点回顾

概念 核心思想 关键参数/决策
KNN分类 少数服从多数 k, distance metric
KNN回归 邻居的平均值 k, distance metric
加权KNN 近朱者赤,近墨者黑 weights='distance'
KD树 空间换时间,预先划分 适用于低维数据
维度灾难 高维空间中距离失去意义 特征选择/降维是关键
标准化 让所有特征一视同仁 在计算距离前必须执行

最终思考: KNN成功的关键

要成功应用KNN,经济学家和数据科学家需要关注以下几点:

  1. 特征工程: 选择与问题最相关的特征至关重要。垃圾进,垃圾出。
  2. 距离度量: 为你的特定问题选择合适的距离度量。欧几里得距离并非总是最佳选择。
  3. 参数调优: 使用交叉验证等技术,系统地寻找最优的 \(k\) 值。
  4. 效率考量: 对于大规模数据集,必须考虑使用KD树、Ball Tree等加速算法,或采用近似最近邻搜索。

KNN是进入机器学习世界的一扇极好的大门,它简单、直观且功能强大。

谢谢!

Q & A