本文共 17151 字，大约阅读时间需要 57 分钟。

第三章 k近邻法

前言

【导读】k近邻法(k-NN)是一种基本的分类与回归的方法。书本只讨论分类问题的k近邻法。该方法的基本思想是“物以类聚，人以群分”或“近朱者赤近墨者黑”。章节结构先叙述k近邻算法，接着讨论k近邻的模型和三个基本要素，最后讲述其中一个实现方法——kd树，介绍构造kd树和搜索kd树的算法。

    关于k近邻法的回归，和分类的主要区别在于最后做预测时候的决策方式不同。k-NN做分类预测时，一般是选择多数表决法，即训练集里和预测的样本特征最近的K个样本，预测为里面有最多类别数的类别。而k-NN做回归时，一般是选择平均法，即最近的k个样本的样本输出的平均值作为回归预测值，它们的思想是一致的。对k-NN回归感兴趣的朋友可以读读这篇文章。

1 理论部分

链接：

提取码：v7w8

1.1 k近邻算法

应用 可用于常见的分类和回归情形，特别是多分类情形。应用场景有字符识别、文本分类、图像识别等领域。

优点

• 简单易懂，精度高，理论成熟；
• 可用于数值型数据和离散型数据。既可以用来做分类，尤其非线性、多分类问题，也可以用来做回归预测；
• 无数据输入假定；
• 对异常值不敏感。
• 由于k-NN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，k-NN方法较其他方法更为适合

缺点

• 面对样本大的情况时，计算效率低，复杂度高；
• 样本不平衡时（即有些类别的样本数量很多，而其它样本的数量很少），对稀有类别的预测准确率低；
• 一般数值很大的时候不用这个，计算量太大。但是单个样本又不能太少，否则容易发生误分；
• 对高维度的数据处理效果不佳；
• 使用懒散学习方法，基本上不学习，导致预测时速度比起逻辑回归之类的算法慢；
• 最大的缺点是无法给出数据的内在含义，无法给出像决策树那样的规则。

算法

主要有以下几个步骤：

• 定k值：没有固定的经验，一般根据样本的分布，选择一个较小的值，可以通过交叉验证选择一个合适的k值；
• 算距离：给定待分类样本，计算它与已分类样本中的每个样本的距离；
• 找邻居：圈定与待分类样本距离最近的K个已分类样本，作为待分类样本的近邻；
• 做分类：根据这K个近邻中的大部分样本所属的类别(majority-voting)来决定待分类样本该属于哪个分类。

k近邻法的特殊情况是k=1的情形，称为最近邻算法，即对于输入的实例点（特征向量）x，最近邻法将训练数据集中与x最邻近的类作为x的类。

Y = P(y | x)：这里概率函数P指某种最小化距离判定公式

k近邻法作为判别模型的一种，判别函数的具体形式也不是很明显。k近邻很好地体现了判别式模型的思想，k近邻不生成概率分布函数。之所以输入样本会被分到不同的类别，其本质就在于在训练样本中存在不均匀的概率密度分布，即某一个区域某一个类别密度占比比其他的类多。

k近邻法没有显式的学习过程，也就是不需要对训练集进行学习。k近邻法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。

维基百科这张图生动地展示了k-NN的特点（实线邻域是3近邻情况，虚线邻域是5近邻情况）

1.2 k近邻模型

模型由三个基本要素——距离度量、k值选择和分类决策规则决定

1.2.1 模型

k近邻法使用的模型实际上对应于特征空间的划分，某种意义上来说，k近邻的模型的假设空间就是样本特征空间本身。

1.2.2 距离度量

特征空间中两个实例点的距离是两个实例点相似程度的一种数字化度量。

设特征空间$\mathcal{X}$是n维实数向量空间${\mathbf{R}}^n$，$x_i,x_j\in \mathcal{X}$, $x_i={\left(x_i^{(1)},x_i^{(2)},\cdots ,x_i^{(n)}\right)}^T$, $x_j={\left(x_j^{(1)},x_j^{(2)},\cdots ,x_j^{(n)}\right)}^{\mathrm{T}}$, $x_i,x_j$的$L_p$或闵可夫斯基距离(Minkowski Distance)距离定义为：

$$L_p\left(x_i,x_j\right)={\left(\sum _{l=1}^n{\left|x_i^{(l)}-x_j^{(l)}\right|}^p\right)}^{\frac{1}{p}}$$

这里$p⩾1$，当$p=2$时，称为欧氏距离（Euclidean distance），即

$$L_2\left(x_i,x_j\right)={\left(\sum _{l=1}^n{\left|x_i^{(l)}-x_j^{(l)}\right|}^2\right)}^{\frac{1}{2}}$$ 这是最常见的两点之间或多点之间的距离表示法。

当$p=1$时，称为曼哈顿距离（Manhattan distance），即

$$L_1\left(x_i,x_j\right)=\sum _{l=1}^n\left|x_i^{(l)}-x_j^{(l)}\right|$$ 我们可以定义曼哈顿距离的正式意义为L1-距离或城市区块距离，也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。 通俗来讲，想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。而实际驾驶距离就是这个“曼哈顿距离”，此即曼哈顿距离名称的来源， 同时，曼哈顿距离也称为城市街区距离(City Block distance)。

当$p=\infty$时，它是各个坐标距离的最大值，即

$$L_{\infty }\left(x_i,x_j\right)=\underset{l}{\max }\left|x_i^{(l)}-x_j^{(l)}\right|$$ 玩过国际象棋的朋友或许知道，国王走一步能够移动到相邻的8个方格中的任意一个。那么国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步？。你会发现最少步数总是max( | x2-x1 | , | y2-y1 | ) 步 。有一种类似的一种距离度量方法就是切比雪夫距离。

$L_p$距离间的关系：

【拓展推荐阅读】想要了解更多的距离度量，墙裂推荐阅读

1.2.3 k值的选择

对于k值的选择，没有一个固定的经验，一般根据样本的分布，选择一个较小的值，可以通过交叉验证选择一个合适的k值。

• 选择较小的k值，就相当于用较小的领域中的训练实例进行预测，训练误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是泛化误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合；

• 选择较大的k值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少泛化误差，但缺点是训练误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。

• 一个极端是k等于样本数N，则完全没有分类，此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单。

1.2.4 分类决策规则

对于分类决策规则，一般都是使用前面提到的多数表决法。

【思考】k-NN回归决策的规则是什么？与分类决策规则有什么区别吗？为什么这样选择？

1.3 k近邻法的实现：kd树

一般说来，索引结构中相似性查询有两种基本的方式：

• 一种是范围查询，范围查询时给定查询点和查询距离阈值，从数据集中查找所有与查询点距离小于阈值的数据
• 另一种是K近邻查询，就是给定查询点及正整数K，从数据集中找到距离查询点最近的K个数据，当K=1时，它就是最近邻查询。

同样，针对特征点匹配也有两种方法：

• 最容易的办法就是线性扫描，也就是我们常说的穷举搜索，依次计算样本集E中每个样本到输入实例点的距离，然后抽取出计算出来的最小距离的点即为最近邻点。此种办法简单直白，但当样本集或训练集很大时，它的缺点就立马暴露出来了，举个例子，在物体识别的问题中，可能有数千个甚至数万个SIFT（尺度不变特征变换Scale-invariant feature transform）特征点，而去一一计算这成千上万的特征点与输入实例点的距离，明显是不足取的。
• 另外一种，就是构建数据索引，因为实际数据一般都会呈现簇状的聚类形态，因此我们想到建立数据索引，然后再进行快速匹配。索引树是一种树结构索引方法，其基本思想是对搜索空间进行层次划分。根据划分的空间是否有混叠可以分为Clipping和Overlapping两种。前者划分空间没有重叠，其代表就是k-d树；后者划分空间相互有交叠，其代表为R树。

课本主要讲述了kd树方法

【推荐阅读】关于R树，推荐阅读

1.3.1 构造kd树

Kd-树是K-dimension tree的缩写，是对数据点在k维空间（如二维(x，y)，三维(x，y，z)，k维(x1，y，z…)）中划分的一种数据结构，主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。本质上说，Kd-树就是一种平衡二叉树。

首先必须搞清楚的是，k-d树是一种空间划分树，说白了，就是把整个空间划分为特定的几个部分，然后在特定空间的部分内进行相关搜索操作。想像一个三维空间，kd树按照一定的划分规则把这个三维空间划分了多个空间，如下图所示：

kd树构造采用的是从N个样本的n维特征中，分别计算n个特征的取值的方差，用方差最大的第k维特征$n_k$来作为根节点。对于这个特征，我们选择特征$n_k$的取值的中位数$n_{kv}$对应的样本作为划分点，对于所有第k维特征的取值小于$n_{kv}$的样本，我们划入左子树，对于第k维特征的取值大于等于$n_{kv}$的样本，我们划入右子树，对于左子树和右子树，我们采用和刚才同样的办法来找方差最大的特征来做更节点，递归的生成kd树。

kd树的构建是一个递归过程，流程如下：

【推荐阅读】

             

1.3.2 搜索kd树

完成了KD树建树后，接下来讨论如何利用KD树进行高效K近邻搜索：

输入：根据train set构造的kd树；目标点x

输出：x的最近邻

• 在KD树中找出包含目标点x的叶节点：从根节点出发，递归地向下访问KD树，若目标点x当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子节点，直到子节点为叶子节点（某个不含训练实例的超矩形区域）为止
• 包含目标点的叶节点对应包含目标点的最小超矩形区域，以此叶节点的实例暂时作为“当前最近点“，注意这里说暂时是因为不一定该叶节点的实例点就真的是最近邻点了，理论上目标点的最近邻一定在以目标点为中心并且圆周通过当前最近点的超球体内部(局部最优原理)，接下来的逆向回溯的目的就是尝试寻找在这个超球体区域内是否还存在其他叶节点内的实例点比“当前最近点”更近
• 以此叶节点为"当前最近点"递归的向上回退，在每个结点(父节点)进行以下操作：重复此过程，依次回退到根节点，搜索结束，最后查看存储的"当前最近点"即为x的最近邻点
  • 如果该结点保存的实例点比当前最近点距离目标点更近，则已该实例点为"当前最近点"
  • 如果该结点的另一子结点的超矩形区域与超球体相交(可能存在另一个局部最优)，那么在相交的区域内寻找与目标点更近的实例点。如果存在这样的点，将此点作为新的当前最近邻点，算法转到更上一级的父节点
  • 如果父节点的另一个子结点的超矩形区域与超球体不相交，说明另一个分支不存在另一个局部最优，则继续该分支的逆向回溯
• 在回退的过程中，不断查找与目标点最邻近的结点，当确定不存在更近的结点时终止。这样搜索就被限制在空间的局部区域上，效率大为提高了(这也是二叉树的核心思想 - 分而治之)

【思考】kd树有什么优缺点，有没有改进的数据结构？

【回答】

可以看到，kd树是可用于有效寻找最近邻的良好数据结构。但是，当面对不均匀数据的数据集时，面临一些基本冲突和挑战：

• 既要求树有完美的平衡结构，又要求区域近似方形
• 更重要的是，矩形、正方形都不是最好的使用形状，原因是它们都有角。处于边界附近的实例点的近邻搜索不太”柔和“，矩形的角是一个很难处理的问题
  这里所谓的平衡结构，就是指树的两边分叉要尽量分布平均，这样可以最大程度地发挥O(logN)的优化效果，但是如果数据点的分布非常不均衡，采用中值的方法也许会在同一个方向上产多多次后续分裂，从而产生瘦长型的超矩形。一个更好的解决方法是采用平均值作为分裂点而不是中位值。这样产生的kd树会更趋向于方形。

但是均值分裂点技术依然无法完全规避KD原生的问题，为此，学界提出了超球分界面代替超矩形分界面的改进方法。

【推荐阅读】

【思考】kd的适用场景。

【回答】kd树更适用于训练实例数远大于空间维数时的k近邻搜索。当空间维数接近训练实例数时，它的效率会迅速下降，几乎接近线性扫描。

2 代码部分

2.1 距离度量

设特征空间$x$是$n$维实数向量空间 ，$x_i,x_j\in \mathcal{X}$,$x_i={\left(x_i^{(1)},x_i^{(2)},\cdots ,x_i^{(n)}\right)}^{\mathrm{T}}$,$x_j={\left(x_j^{(1)},x_j^{(2)},\cdots ,x_j^{(n)}\right)}^{\mathrm{T}}$

，则：$x_i$,$x_j$的$L_p$距离定义为:

$L_p\left(x_i,x_j\right)={\left({\sum }_{i=1}^n{\left|x_i^{(i)}-x_j^{(l)}\right|}^p\right)}^{\frac{1}{p}}$

• $p=1$ 曼哈顿距离
• $p=2$ 欧氏距离
• $p=\infty$ 切比雪夫距离

import mathfrom itertools import combinations

def L(x, y, p=2): # 默认欧式距离    # x1 = [1, 1], x2 = [5,1]    if len(x) == len(y) and len(x) > 1:        sum = 0        for i in range(len(x)):            sum += math.pow(abs(x[i] - y[i]), p)        return math.pow(sum, 1 / p)    else:        return 0

2.2 课本例3.1

x1 = [1, 1]x2 = [5, 1]x3 = [4, 4]

# x1, x2for i in range(1, 5):    r = {
   '1-{}'.format(c): L(x1, c, p=i) for c in [x2, x3]} # r是字典，key是'1-c',value是L(x1, c, p=i)    print(min(zip(r.values(), r.keys()))) # 比较i=1,2,3,4的情况下，c在[x2, x3]哪个L(x1, c, p=i) 最小。zip()是把后面的字典键值对应压缩转化成元组

(4.0, '1-[5, 1]')(4.0, '1-[5, 1]')(3.7797631496846193, '1-[4, 4]')(3.5676213450081633, '1-[4, 4]')

python实现，遍历所有数据点，找出$n$个距离最近的点的分类情况，少数服从多数

import numpy as npimport pandas as pdimport matplotlib.pyplot as plt%matplotlib inlinefrom sklearn.datasets import load_irisfrom sklearn.model_selection import train_test_splitfrom collections import Counter

# datairis = load_iris()df = pd.DataFrame(iris.data, columns=iris.feature_names)df['label'] = iris.targetdf.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label']# data = np.array(df.iloc[:100, [0, 1, -1]])

df

	sepal length	sepal width	petal length	petal width	label
0	5.1	3.5	1.4	0.2	0
1	4.9	3.0	1.4	0.2	0
2	4.7	3.2	1.3	0.2	0
3	4.6	3.1	1.5	0.2	0
4	5.0	3.6	1.4	0.2	0
...	...	...	...	...	...
145	6.7	3.0	5.2	2.3	2
146	6.3	2.5	5.0	1.9	2
147	6.5	3.0	5.2	2.0	2
148	6.2	3.4	5.4	2.3	2
149	5.9	3.0	5.1	1.8	2

150 rows × 5 columns

plt.scatter(df[:50]['sepal length'], df[:50]['sepal width'], label='0') #前50个样本标签是0plt.scatter(df[50:100]['sepal length'], df[50:100]['sepal width'], label='1') #51-100的样本标签是1plt.xlabel('sepal length')plt.ylabel('sepal width')plt.legend()

data = np.array(df.iloc[:100, [0, 1, -1]]) #取前100个样本第一第二与最后一列的值转成数组X, y = data[:,:-1], data[:,-1]X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2) #测试集占的比例为0.2，默认是0.25

【参考】

class KNN:    def __init__(self, X_train, y_train, n_neighbors=3, p=2): #默认3近邻，欧氏距离        """        parameter: n_neighbors 临近点个数        parameter: p 距离度量        """        self.n = n_neighbors        self.p = p        self.X_train = X_train        self.y_train = y_train    def predict(self, X):        # 取出n个点        knn_list = []        for i in range(self.n): #取前n个点            dist = np.linalg.norm(X - self.X_train[i], ord=self.p) #linalg=linear（线性）+algebra（代数），norm则表示范数。            knn_list.append((dist, self.y_train[i]))        for i in range(self.n, len(self.X_train)): #取n+1到100样本            max_index = knn_list.index(max(knn_list, key=lambda x: x[0])) #最大dist的索引            dist = np.linalg.norm(X - self.X_train[i], ord=self.p)            if knn_list[max_index][0] > dist: #如果找到了比n近邻中最大dist的点更小的dist的点，则将其替换                knn_list[max_index] = (dist, self.y_train[i])        # 统计        knn = [k[-1] for k in knn_list] #knn是knn_list的后一个值，即标签        count_pairs = Counter(knn) #标签计数，通过字典的键值，比如本例，标签0有几个，标签1有几个#         max_count = sorted(count_pairs, key=lambda x: x)[-1]        max_count = sorted(count_pairs.items(), key=lambda x: x[1])[-1][0] #count_pairs.items()是dict_itmes，将原来字典类型的键值对转成列表类型的元组对。然后按着元组后一个元素（即标签出现的次数）升序排列，选最后一排（出现最多）元组的第一个元素，就是标签        return max_count    def score(self, X_test, y_test):        right_count = 0        n = 10        for X, y in zip(X_test, y_test): #拿模型预测测试集的结果和测试集的标签比较            label = self.predict(X)            if label == y:                right_count += 1        return right_count / len(X_test) #预测正确的比例，0——1的范围

clf = KNN(X_train, y_train)

clf.score(X_test, y_test)

1.0

test_point = [6.0, 3.0]print('Test Point: {}'.format(clf.predict(test_point)))

Test Point: 1.0

测试结构为标签1

plt.scatter(df[:50]['sepal length'], df[:50]['sepal width'], label='0')plt.scatter(df[50:100]['sepal length'], df[50:100]['sepal width'], label='1')plt.plot(test_point[0], test_point[1], 'bo', label='test_point')plt.xlabel('sepal length')plt.ylabel('sepal width')plt.legend()

2.3 scikit-learn实例

from sklearn.neighbors import KNeighborsClassifier

clf_sk = KNeighborsClassifier() #class sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, *, weights='uniform', algorithm='auto', leaf_size=30, p=2, metric='minkowski', metric_params=None, n_jobs=None, **kwargs)clf_sk.fit(X_train, y_train)

KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',                     metric_params=None, n_jobs=None, n_neighbors=5, p=2,                     weights='uniform')

【参考】

clf_sk.score(X_test, y_test)

1.0

2.4 sklearn.neighbors.KNeighborsClassifier

• n_neighbors: 临近点个数
• p: 距离度量
• algorithm: 近邻算法，可选{‘auto’, ‘ball_tree’, ‘kd_tree’, ‘brute’}
• weights: 确定近邻的权重

2.5 kd树

kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。

kd树是二叉树，表示对$k$维空间的一个划分（partition）。构造kd树相当于不断地用垂直于坐标轴的超平面将$k$维空间切分，构成一系列的k维超矩形区域。kd树的每个结点对应于一个$k$维超矩形区域。

构造kd树的方法如下：

构造根结点，使根结点对应于$k$维空间中包含所有实例点的超矩形区域；通过下面的递归方法，不断地对$k$维空间进行切分，生成子结点。在超矩形区域（结点）上选择一个坐标轴和在此坐标轴上的一个切分点，确定一个超平面，这个超平面通过选定的切分点并垂直于选定的坐标轴，将当前超矩形区域切分为左右两个子区域

（子结点）；这时，实例被分到两个子区域。这个过程直到子区域内没有实例时终止（终止时的结点为叶结点）。在此过程中，将实例保存在相应的结点上。

通常，依次选择坐标轴对空间切分，选择训练实例点在选定坐标轴上的中位数

（median）为切分点，这样得到的kd树是平衡的。注意，平衡的kd树搜索时的效率未必是最优的。

2.6 构造平衡kd树算法

输入：$k$维空间数据集$T＝\{$

x1​，x2​,…,xN​}，

其中$x_i={\left(x_i^{(1)},x_i^{(2)},\cdots ,x_i^{(k)}\right)}^{\mathrm{T}}$ ，$i＝1,2,\dots ,N$；

输出：kd树。

（1）开始：构造根结点，根结点对应于包含$T$的$k$维空间的超矩形区域。

选择$x^{(1)}$为坐标轴，以T中所有实例的$x^{(1)}$坐标的中位数为切分点，将根结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴$x^{(1)}$垂直的超平面实现。

由根结点生成深度为1的左、右子结点：左子结点对应坐标$x^{(1)}$小于切分点的子区域， 右子结点对应于坐标$x^{(1)}$大于切分点的子区域。

将落在切分超平面上的实例点保存在根结点。

（2）重复：对深度为$j$的结点，选择$x^{(1)}$为切分的坐标轴，$l＝j(modk)+1$，以该结点的区域中所有实例的$x^{(1)}$坐标的中位数为切分点，将该结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴$x^{(1)}$垂直的超平面实现。

由该结点生成深度为$j+1$的左、右子结点：左子结点对应坐标$x^{(1)}$小于切分点的子区域，右子结点对应坐标$x^{(1)}$大于切分点的子区域。

将落在切分超平面上的实例点保存在该结点。

（3）直到两个子区域没有实例存在时停止。从而形成kd树的区域划分。

# kd-tree每个结点中主要包含的数据结构如下class KdNode(object):    def __init__(self, dom_elt, split, left, right):        self.dom_elt = dom_elt  # k维向量节点(k维空间中的一个样本点)        self.split = split  # 整数（进行分割维度的序号）        self.left = left  # 该结点分割超平面左子空间构成的kd-tree        self.right = right  # 该结点分割超平面右子空间构成的kd-treeclass KdTree(object):    def __init__(self, data):        k = len(data[0])  # 数据维度        def CreateNode(split, data_set):  # 按第split维划分数据集exset创建KdNode            if not data_set:  # 数据集为空                return None            # key参数的值为一个函数，此函数只有一个参数且返回一个值用来进行比较            # operator模块提供的itemgetter函数用于获取对象的哪些维的数据，参数为需要获取的数据在对象中的序号            #data_set.sort(key=itemgetter(split)) # 按要进行分割的那一维数据排序            data_set.sort(key=lambda x: x[split])            split_pos = len(data_set) // 2  # //为Python中的整数除法            median = data_set[split_pos]  # 中位数分割点            split_next = (split + 1) % k  # cycle coordinates            # 递归的创建kd树            return KdNode(                median,                split,                CreateNode(split_next, data_set[:split_pos]),  # 创建左子树                CreateNode(split_next, data_set[split_pos + 1:]))  # 创建右子树        self.root = CreateNode(0, data)  # 从第0维分量开始构建kd树,返回根节点# KDTree的前序遍历def preorder(root):    print(root.dom_elt)    if root.left:  # 节点不为空        preorder(root.left)    if root.right:        preorder(root.right)

# 对构建好的kd树进行搜索，寻找与目标点最近的样本点：from math import sqrtfrom collections import namedtuple# 定义一个namedtuple,分别存放最近坐标点、最近距离和访问过的节点数result = namedtuple("Result_tuple",                    "nearest_point  nearest_dist  nodes_visited")def find_nearest(tree, point):    k = len(point)  # 数据维度    def travel(kd_node, target, max_dist):        if kd_node is None:            return result([0] * k, float("inf"),                          0)  # python中用float("inf")和float("-inf")表示正负无穷        nodes_visited = 1        s = kd_node.split  # 进行分割的维度        pivot = kd_node.dom_elt  # 进行分割的“轴”        if target[s] <= pivot[s]:  # 如果目标点第s维小于分割轴的对应值(目标离左子树更近)            nearer_node = kd_node.left  # 下一个访问节点为左子树根节点            further_node = kd_node.right  # 同时记录下右子树        else:  # 目标离右子树更近            nearer_node = kd_node.right  # 下一个访问节点为右子树根节点            further_node = kd_node.left        temp1 = travel(nearer_node, target, max_dist)  # 进行遍历找到包含目标点的区域        nearest = temp1.nearest_point  # 以此叶结点作为“当前最近点”        dist = temp1.nearest_dist  # 更新最近距离        nodes_visited += temp1.nodes_visited        if dist < max_dist:            max_dist = dist  # 最近点将在以目标点为球心，max_dist为半径的超球体内        temp_dist = abs(pivot[s] - target[s])  # 第s维上目标点与分割超平面的距离        if max_dist < temp_dist:  # 判断超球体是否与超平面相交            return result(nearest, dist, nodes_visited)  # 不相交则可以直接返回，不用继续判断        #----------------------------------------------------------------------        # 计算目标点与分割点的欧氏距离        temp_dist = sqrt(sum((p1 - p2)**2 for p1, p2 in zip(pivot, target)))        if temp_dist < dist:  # 如果“更近”            nearest = pivot  # 更新最近点            dist = temp_dist  # 更新最近距离            max_dist = dist  # 更新超球体半径        # 检查另一个子结点对应的区域是否有更近的点        temp2 = travel(further_node, target, max_dist)        nodes_visited += temp2.nodes_visited        if temp2.nearest_dist < dist:  # 如果另一个子结点内存在更近距离            nearest = temp2.nearest_point  # 更新最近点            dist = temp2.nearest_dist  # 更新最近距离        return result(nearest, dist, nodes_visited)    return travel(tree.root, point, float("inf"))  # 从根节点开始递归

2.7 例3.2

data = [[2,3],[5,4],[9,6],[4,7],[8,1],[7,2]]kd = KdTree(data)preorder(kd.root)

[7, 2][5, 4][2, 3][4, 7][9, 6][8, 1]

from time import process_timefrom random import random# 产生一个k维随机向量，每维分量值在0~1之间def random_point(k):    return [random() for _ in range(k)] # 产生n个k维随机向量 def random_points(k, n):    return [random_point(k) for _ in range(n)]

ret = find_nearest(kd, [3,4.5])print (ret)

Result_tuple(nearest_point=[2, 3], nearest_dist=1.8027756377319946, nodes_visited=4)

N = 400000t0 = process_time()kd2 = KdTree(random_points(3, N))            # 构建包含四十万个3维空间样本点的kd树ret2 = find_nearest(kd2, [0.1,0.5,0.8])      # 四十万个样本点中寻找离目标最近的点t1 = process_time()print ("time: ",t1-t0, "s")print (ret2)

time:  5.296875 sResult_tuple(nearest_point=[0.09655667956154679, 0.5032638969756525, 0.7944025326469046], nearest_dist=0.0073376508419597366, nodes_visited=52)

---

参考代码：

转载地址：http://vkgbi.baihongyu.com/