假设你是一位信贷经理,一位新客户前来申请贷款。
你的核心任务是:
这是一个典型的商业分类问题。
你并非毫无根据地猜测。你的银行拥有宝贵的历史数据。
KNN算法的哲学非常简单:要判断一个新样本的类别,只需看离它最近的几个“邻居”属于哪个类别。
就像你要判断一个陌生人的兴趣爱好,最简单的方法就是看看他交往最密切的朋友们都是些什么样的人。
机器学习概念 | 商业场景类比 (信用评估) |
---|---|
新样本 (未知类别) | 一位新的贷款申请人 |
邻居 (已知类别) | 数据库中与新申请人情况最相似的历史客户 |
类别 | ‘会违约’ 或 ‘不会违约’ |
“近”的度量 | 客户特征的相似度 (如收入、年龄、负债) |
K值 | 我们参考多少个相似的客户来做决定? |
给定一个待分类样本 \(x_n\),KNN的决策过程分为两步:
\[ \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模型的基石。
如何定义“近”?这取决于我们选择的距离度量。
参考多少个邻居?这是模型复杂度的关键开关。
如何汇总邻居的“意见”?最常见的是少数服从多数。
样本间的相似性是通过距离函数来度量的。对于两个 \(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}|} \]
欧几里得距离是“抄近道”,曼哈顿距离是“走街区”。
重要提示: 距离度量对特征的尺度 (scale) 非常敏感。
在应用KNN之前,数据标准化几乎是必不可少的一步。
\(k\) 值的选择直接影响模型的性能,它是一个偏差-方差权衡 (Bias-Variance Tradeoff) 的过程。
当 k 很小时 (例如 k=1),模型决策边界会变得非常曲折,试图去完美匹配每一个训练数据点,包括噪声。
当 k 很大时 (例如 k=N),模型会忽略数据的局部结构,决策边界变得过于简单,无法捕捉类别间的差异。
那么,如何找到那个“刚刚好”的 \(k\) 值呢?
我们将在稍后的Python实践中演示这个过程。
假设我们有一组关于肿瘤的数据,分为“良性”和“恶性”两类。现在来了一个新的病人(用 ?
表示),我们需要判断其肿瘤是良性还是恶性。
1-NN是最简单的KNN形式。我们只看距离最近的那一个邻居。
在这个例子中,离新病人最近的样本是“恶性”类,所以1-NN会将其分类为恶性。这可能是一个受噪声影响的错误判断。
现在,我们将 \(k\) 增加到 5,考察最近的5个邻居。
这个例子清晰地表明了 \(k\) 值的选择对最终结果有决定性影响。
理论讲完了,现在我们动手实践。我们将使用一个经典的真实世界数据集——威斯康星州乳腺癌数据集。
scikit-learn
,一个强大的Python机器学习库。首先,我们加载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]
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) 样本
使用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
我们之前提到,\(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()
上图的分析告诉我们:
这是一个非常强大的结果,表明KNN可以有效地用于医疗诊断等实际应用。
标准的KNN模型中,每个邻居的“投票权重”是相等的。但这是否合理?
一种常见的加权方式是使用距离的倒数作为权重。
\[ \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)}} \]
近的邻居“嗓门大”,远的邻居“嗓门小”。
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往往能带来性能提升。
KNN的核心思想同样适用于回归问题,即预测一个连续值(如股票价格、房屋售价)。
分类 (Classification)
回归 (Regression)
对于一个新样本,KNN回归模型的预测值是其 \(k\) 个最近邻居的目标值的平均值(或加权平均值)。
\[ \large{\hat{y}_n = \frac{1}{k} \sum_{i=1}^k y_i} \]
其中,\(y_i\) 是第 \(i\) 个邻居的真实数值。
我们使用加州房价数据集,通过房屋的各项特征(如街区收入中位数、房屋年龄)来预测其价格。
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的一个主要缺点是其计算成本高。
问题: 如何在不牺牲太多精度的前提下,加快寻找最近邻的速度?
直接计算新样本与所有训练点的距离被称为蛮力搜索 (Brute-force search)。
加速策略的核心思想是:通过构建智能的数据结构,来快速排除大量不可能成为最近邻的样本点。
KD树是一种经典的空间划分数据结构,它将 \(k\) 维空间递归地划分为一系列超矩形区域。
虽然KD树在低维空间(例如 \(d < 20\))中非常有效,但随着数据维度 \(d\) 的增加,其性能会迅速下降。
在高维空间中,我们基于低维(2D或3D)生活经验建立的几何直觉往往会失效。
本讲座旨在通过直观的例子和数学推导,揭示这一反直觉的现象——距离度量的失效。
我们从一个简单的思想实验开始:将单位超立方体 $[0, 1]^d$
的每个维度都从中点 0.5
处切开。
这会将整个空间分割成 $2^d$
个相同大小的’小超立方体’。
我们将通过观察一个随机点落在哪个’小立方体’中,来建立对高维空间的初步直觉。
在低维空间,靠近原点 (0,0,...)
的区域(即’内层’)和远离原点的区域(‘外壳’)看起来是均衡的。
$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 } \]
这意味着,从任何一个点的视角看,其他所有点到它的距离几乎是完全相同的!
我们来分析任意两点 $X_i$
和 $X_j$
之间的距离。
$X_j$
是一个d维向量 $(X_{j1}, ..., X_{jd})^T$
。$X_{jk}$
独立地服从 U(0, 1)
分布。
$E(X_{jk}) = \frac{1}{2}$
$Var(X_{jk}) = \frac{1}{12}$
$S_{ij} = ||X_i - X_j||_2^2$
,因为它更易于处理。\[ \large{ S_{ij} = \sum_{k=1}^{d} (X_{ik} - X_{jk})^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} } \]
我们已经知道距离平方 $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}$
附近。由于这个结论对任意的 i
和 j
都成立,所以所有点对的距离平方都将趋于同一个值!
这个现象可以用距离分布的变化来直观理解。
d
增加,距离的分布变得越来越窄,最终像一个脉冲函数一样集中在期望值周围。
距离集中的现象不仅仅局限于均匀分布或欧氏距离,它是一个更普遍的规律。
范数集中定理 (直观版): 对于满足某些温和条件的随机向量 $X \in \mathbb{R}^d$
(例如,各分量独立且方差为1),它的L2范数 (即长度) $||X||_2$
会高度集中在其期望值 $\sqrt{d}$
附近。
一个更强的结论 (Vershynin, 2018) 表明,对于次高斯向量,这种偏离 $\sqrt{d}$
的概率会随着维度 d
的增加而指数级衰减。这意味着在高维空间中,随机向量的长度几乎是一个确定性而非随机性的值。
距离度量的失效对许多依赖于距离计算的算法构成了严峻挑战,特别是 k-最近邻 (k-NN) 算法。
k
个邻居。优点 (Pros) | 缺点 (Cons) |
---|---|
✅ 原理简单,易于实现 | ❌ 计算成本高,预测速度慢 |
✅ 无需训练,模型适应性强 (非参数) | ❌ 对内存需求大,需存储所有训练数据 |
✅ 对数据分布没有假设 | ❌ 对不平衡数据敏感 (多数类会主导投票) |
✅ 可用于分类和回归 | ❌ 高维灾难问题严重 |
✅ 决策边界可以非常灵活 | ❌ 需要对特征进行标准化 |
凭借其简单性和灵活性,KNN在多个商业领域都有广泛应用:
概念 | 核心思想 | 关键参数/决策 |
---|---|---|
KNN分类 | 少数服从多数 | k , distance metric |
KNN回归 | 邻居的平均值 | k , distance metric |
加权KNN | 近朱者赤,近墨者黑 | weights='distance' |
KD树 | 空间换时间,预先划分 | 适用于低维数据 |
维度灾难 | 高维空间中距离失去意义 | 特征选择/降维是关键 |
标准化 | 让所有特征一视同仁 | 在计算距离前必须执行 |
要成功应用KNN,经济学家和数据科学家需要关注以下几点:
KNN是进入机器学习世界的一扇极好的大门,它简单、直观且功能强大。
Q & A