0x00 引言

在之前的文章《机器学习的敲门砖：kNN算法（中）》中，我们探讨了kNN分类算法的应用，涵盖了如何划分数据集、评估模型精度、以及寻找最佳超参数等内容。然而，在实际应用中，我们常常会忽略一个关键步骤——数据归一化。本文将详细介绍数据归一化的重要性及其具体实现方法。此外，我们将总结kNN算法的优势和劣势，并讨论如何优化该算法，特别是通过引入KD树。

0x01 数据归一化

1.1 为何需要数据归一化

在实际应用中，样本的各个特征可能有不同的单位，这会导致某些特征在计算距离时占据主导地位。例如，在比较两个样本时，肿瘤大小和发现时间的差异可能会导致计算结果偏向某一特征。因此，我们需要将所有数据统一到同一尺度，以避免这种偏差。

数据归一化通常有两种方法：

• 最大最小归一化：将所有数据映射到0到1之间。这种方法适用于特征分布有明确界限的情况，但容易受到异常值的影响。

  [ x{text{scale}} = frac{x - x{text{min}}}{x{text{max}} - x{text{min}}} ]

• 均值方差归一化：将所有数据转换为均值为0、方差为1的分布。这种方法适用于数据中不存在明显界限且可能存在异常值的情况。

  [ x{text{scale}} = frac{x - x{text{mean}}}{S} ]

1.2 实现最大最小归一化

为了更好地理解最大最小归一化，我们可以通过生成一些随机数据来进行演示。例如，创建100个随机数，并将其归一化。

```python import numpy as np

创建100个随机数

x = np.random.randint(0, 100, size=100)

计算最小值和最大值

xmin = np.min(x) xmax = np.max(x)

归一化

xnormalized = (x - xmin) / (xmax - xmin)

绘制归一化后的数据

import matplotlib.pyplot as plt plt.scatter(range(len(x)), x_normalized) plt.show() ```

1.3 实现均值方差归一化

同样地，我们也可以通过生成随机数据来演示均值方差归一化。

```python import numpy as np

创建100个随机数

X = np.random.randint(0, 100, (50, 2)).astype(float)

归一化

X[:, 0] = (X[:, 0] - np.mean(X[:, 0])) / np.std(X[:, 0]) X[:, 1] = (X[:, 1] - np.mean(X[:, 1])) / np.std(X[:, 1])

绘制归一化后的数据

plt.scatter(X[:, 0], X[:, 1]) plt.show() ```

1.4 使用Scikit-Learn进行归一化

在实际应用中，我们可以使用Scikit-Learn库提供的StandardScaler类来实现数据归一化。

```python import numpy as np from sklearn import datasets from sklearn.modelselection import traintest_split from sklearn.preprocessing import StandardScaler

加载鸢尾花数据集

iris = datasets.load_iris() X = iris.data y = iris.target

划分数据集

Xtrain, Xtest, ytrain, ytest = traintestsplit(X, y, testsize=0.2, randomstate=666)

初始化标准化器

scaler = StandardScaler()

训练标准化器

scaler.fit(X_train)

归一化数据

Xtrainstandard = scaler.transform(Xtrain) Xteststandard = scaler.transform(Xtest) ```

1.5 自定义实现均值方差归一化

我们也可以自己实现一个类似于Scikit-Learn的标准化器。

```python import numpy as np

class StandardScaler: def init(self): self.mean_ = None self.scale_ = None

def fit(self, X):
    assert X.ndim == 2, "The dimension of X must be 2"
    self.mean_ = np.mean(X, axis=0)
    self.scale_ = np.std(X, axis=0)
    return self

def transform(self, X):
    assert X.ndim == 2, "The dimension of X must be 2"
    assert self.mean_ is not None and self.scale_ is not None, "must fit before transform"
    assert X.shape[1] == len(self.mean_), "the feature number of X must be equal to mean_ and scale_"
    resX = (X - self.mean_) / self.scale_
    return resX

```

0x02 kNN算法的优缺点

优点

• 成熟且直观：kNN算法的思想简单易懂，既可用于分类也可用于回归。
• 多分类能力强：kNN算法能够自然处理多分类问题。
• 无需假设：与其他需要特定假设的算法相比，kNN对数据没有过多假设。
• 对异常值不敏感：kNN算法主要依赖于周围的少数样本，因此对异常值不敏感。
• 适用于交叉类域：当类域交叉较多时，kNN算法较为适用。

缺点

• 计算量大：kNN算法的计算复杂度较高，尤其是在高维数据上。
• 效率低：即使采用优化算法，效率仍然不高。
• 数据相关性强：kNN算法高度依赖数据，样本不平衡时对稀有类别预测准确率较低。
• 可解释性差：与决策树模型相比，kNN模型的可解释性较差。
• 维数灾难：随着维度增加，看似相近的两个点之间距离增大，kNN算法对此依赖较大。

0x03 KD树

3.1 KD树的原理

KD树是一种用于存储k维空间中实例点的数据结构，可以快速检索最近邻。它是一种二叉树，每个节点都是一个k维样本点，每个节点代表一个超平面，将空间划分为两个部分。

3.2 KD树的构建

构建KD树的过程如下：

• 循环选择数据点的各维度作为切分维度。
• 选择中值作为切分超平面，将数据点分为左右子树。
• 递归处理子树。

构建KD树时有两个优化点：

• 选择切分维度：根据数据点在各维度上的分布情况，方差越大，分布越分散，优先选择该维度。
• 确定中值点：预先对原始数据点在所有维度上排序，提升构建速度。

3.3 KD树的检索

KD树的检索是kNN算法的关键步骤，通过深度优先遍历来找到最近邻。例如，在二维空间中查找(3,5)的最近邻时，可以逐步排除不可能的区域。

3.4 Scikit-Learn中的KDTree

Scikit-Learn提供了KDTree的实现，可以用于k近邻搜索和指定半径范围内的搜索。

```python import numpy as np from matplotlib import pyplot as plt from matplotlib.patches import Circle from sklearn.neighbors import KDTree

生成随机点

np.random.seed(0) points = np.random.random((100, 2))

构建KD树

tree = KDTree(points)

查询最近邻

point = points[0] dists, indices = tree.query([point], k=3) print(dists, indices)

查询半径范围内的点

indices = tree.query_radius([point], r=0.2) print(indices)

绘制图形

fig = plt.figure() ax = fig.addsubplot(111, aspect='equal') ax.addpatch(Circle(point, 0.2, color='r', fill=False)) X, Y = [p[0] for p in points], [p[1] for p in points] plt.scatter(X, Y) plt.scatter([point[0]], [point[1]], c='r') plt.show() ```

0xFF 总结

通过以上内容，我们回顾了kNN算法的基本概念、数据归一化、优缺点以及KD树的应用。我们希望这些内容能帮助读者更好地理解和应用kNN算法。尽管kNN算法简单，但在某些情况下依然非常有效。希望通过本文，大家能够对机器学习有一个更加清晰的认识。