面试题详解

什么是 KNN 算法 ？

KNN（k 最近邻）是一种基本且广泛应用的分类和回归的算法。

KNN 算法的核心思想是找出一个样本最近的 k 个邻居（其他样本），然后根据这些邻居的信息来进行预测。

算法步骤
  • 选择k的值：确定邻居的数量 k。k值的选择会影响算法的结果，太小会增加噪声的影响，太大则可能包含太多不相关的元素。
  • 计算距离：对于每一个训练集中的数据点，计算它与待分类点之间的距离。
  • 排序：将这些距离排序。
  • 选取最近的 k 个点：选择距离最近的 k 个点。
  • 决策：对于分类问题，根据这 k 个点的类别通过投票等方式进行决策；对于回归问题，则是取这些点的平均值。

它具有如下特点。

  1. 简单有效：算法理论简单，易于理解和实现。
  2. 无需训练：KNN 是一种懒惰学习算法，不需要在训练阶段进行学习。
  3. 适应性：可以用于分类和回归任务。
  4. 局部决策：算法的决策只依赖于局部数据。

aaa

下面是一个使用 scikit-learn 实现 KNN 的一个简单的分类案例。

from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.datasets import make_classification
from sklearn.metrics import classification_report, accuracy_score

X, y = make_classification(n_samples=100, n_features=4, n_classes=2, random_state=42)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(X_train, y_train)
predictions = knn.predict(X_test)
print("Accuracy:", accuracy_score(y_test, predictions))
print("\nClassification Report:\n", classification_report(y_test, predictions))

image-20231207114516798

如何理解 KNN 中的 K 值？

K 值在 KNN（k-最近邻）算法中扮演着核心角色，K值代表在进行分类或回归时考虑的最近邻居的数量。简单来说，当你有一个新的数据点需要分类时，你会查找训练集中离这个点最近的K个点。在分类任务中，这 K 个点中出现最频繁的类别将被赋予新点；在回归任务中，通常是这些点的输出值的平均或中位数。

K值的影响
  1. 过拟合与欠拟合：一个较小的 K 值意味着模型可能会对训练数据中的噪声更敏感，导致过拟合。相反，一个较大的 K 值可能会使模型过于泛化，忽略了数据中的重要模式，导致欠拟合。
  2. 决策边界：较小的 K 值会导致决策边界更加复杂和不规则，而较大的 K 值通常会产生更平滑的决策边界。
选择合适的 K 值
  1. 交叉验证：通常使用交叉验证来选择最佳的 K 值。这意味着对一系列的 K 值进行实验，通过比较它们在验证集上的性能来选择最佳值。
  2. 数据的特性：选择 K 值时也应考虑数据集的特性。

KNN 算法中常⽤的距离度量⽅法有哪些 ？

在 KNN（k-最近邻）算法中，选择合适的距离度量方法对于确保良好的性能至关重要。以下是几种在 KNN 算法中常用的距离度量方法：

  1. 欧氏距离

欧氏距离是最常用的距离度量方法，它用于衡量多维空间中两点之间的直线距离。在数学上，如果我们有两个点 \(p\) 和 \(q\)，其中点 \(p\) 在 \(n\) 维空间的坐标是 \((p_1,p_2,...,p_n)\)，点 \(q\) 的坐标是 \((q_1,q_2,...,q_n)\)，那么点 \(p\) 和点 \(q\) 之间的欧氏距离 \(d(p,q)\) 可以表示为：

\(\(d(p, q) = \sqrt{\sum_{i=1}^{n} (q_i - p_i)^2}\)\)

  1. 曼哈顿距离

曼哈顿距离是一种用于度量多维空间中两个点在标准坐标系上的绝对轴距总和的距离度量方法。

\(\(D(p, q) = \sum_{i=1}^{n} |q_i - p_i|\)\)

  1. 切比雪夫距离

切比雪夫距离是指两个点之间的最大差值。

\(\(d(p, q) = \max_i |q_i - p_i|\)\)

  1. 闵可夫斯基距离

闵可夫斯基距离是欧氏距离和曼哈顿距离的一般化形式。可以通过改变参数来调整计算的距离类型。

\(\(d(p, q) = \left( \sum_{i=1}^{n} |q_i - p_i|^r \right)^{\frac{1}{r}}\)\)

当 r=2 时，变为欧氏距离；当 r=1 时，变为曼哈顿距离。

aaa

在使用 KNN 算法之前，为什么要进行数据标准化或归一化？

在使用 K近邻算法（KNN）时，通常需要对数据进行归一化。 因为 KNN 算法依赖于距离度量，如果数据具有不同的尺度和范围，则可能对距离计算造成影响。 归一化可以确保所有特征具有相同的权重，从而减少特征之间的偏差。 此外，还可以提高计算效率，当所有特征都在同一量级时，距离计算更加快速，减少了计算资源的消耗，特别是在处理大规模数据集时。

在 KNN算法中如何对不同邻居的贡献进行权重分配？

在 KNN（k-最近邻）算法中，对不同邻居的贡献进行权重分配是一种提高算法性能的常用策略。这种方法的核心思想是给予距离目标点更近的邻居更大的权重，因为它们更有可能与目标点具有相似的特征或标签。

以下是几种常用的权重分配方法：

  1. 均等权重：这是 KNN 算法中最简单的形式，即不考虑邻居的具体距离，每个邻居的投票权重相等。
  2. 距离权重：在这种方法中，邻居的权重与其到目标点的距离成反比。常用的权重计算公式是 \(\frac{1}{\text{distance}}\) 或 \(\frac{1}{\text{distance}^2}\) 这样，距离较近的邻居将对最终结果产生更大的影响。
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score

# 加载数据集
iris = datasets.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)

# 数据标准化
scaler = StandardScaler()
X_train = scaler.fit_transform(X_train)
X_test = scaler.transform(X_test)

# KNN模型，使用均等权重
knn_uniform = KNeighborsClassifier(n_neighbors=5, weights='uniform')
knn_uniform.fit(X_train, y_train)
y_pred_uniform = knn_uniform.predict(X_test)
print("Uniform Weight Accuracy:", accuracy_score(y_test, y_pred_uniform))

# KNN模型，使用距离权重
knn_distance = KNeighborsClassifier(n_neighbors=5, weights='distance')
knn_distance.fit(X_train, y_train)
y_pred_distance = knn_distance.predict(X_test)
print("Distance Weight Accuracy:", accuracy_score(y_test, y_pred_distance))

KNN 算法优缺点？

KNN（k-最近邻）算法是一种基于实例的学习方法，它在各种分类和回归任务中广泛使用。

以下是 KNN 算法的一些优点和缺点：

优点
  1. 简单直观：KNN算法概念简单，易于理解和实现。
  2. 无需训练：作为一种惰性学习算法，KNN在训练阶段不需要构建模型，只需存储数据即可。
  3. 适应性强：由于没有训练过程，KNN 可以动态地添加新的数据而不需要重新训练。
  4. 多功能性：KNN 可以用于分类和回归问题。
  5. 非参数方法：KNN 是非参数的，这意味着它不假设数据的分布，对于不规则分布的数据也能很好地工作。
缺点
  1. 计算成本高：KNN 在每一个新数据点分类时，都需要对所有训练数据进行距离计算，这在大数据集上可能非常耗时。
  2. 存储需求大：由于需要存储所有训练数据，对存储空间的需求可能非常高。
  3. 距离度量选择：KNN的性能很大程度上依赖于距离度量的选择，不同的距离度量会导致不同的分类结果。

aaa