kd tree python_Python实现KNN与KDTree

KNN算法：

KNN的基本思想以及数据预处理等步骤就不介绍了，网上挑了两个写的比较完整有源码的博客。

利用KNN约会分类

KNN项目实战——改进约会网站的配对效果

KNN 代码

'''

Function:

----------

找出距离目标最近的K个特征值

Parameters

----------

target: 目标点的特征值

feature_dataset: 已知数据的特征值

k: 最近的数量

Returns

-------

：目标最近的特征值的索引列表

'''

def _KNN(target, feature_dataset, k: int):

# 获取已知数据的数量

dataSetSize = feature_dataset.shape[0]

# 将目标数据复制dataSetSize份，然后计算欧式距离

diffMat = np.tile(target, (dataSetSize, 1)) - feature_dataset

sqDiffMat = diffMat ** 2

sqDistances = sqDiffMat.sum(axis=1)

distances = sqDistances ** 0.5

# 按照距离进行排序，排序结果为索引

sortedDistIndicies = distances.argsort()

for i in range(k):

print(feature_dataset[sortedDistIndicies[i]])

print(type(sortedDistIndicies))

return sortedDistIndicies

KD树

KD树构建与查询导图

学习KD树中的疑问：

需要预测的值若已经存在于KD树中，应该咋办？

在二分查找的过程中，记录下“走过”每一个节点时对应的距离。当遍历至叶子节点时，“重复点”一定被记录下来了。

KD树怎么样回溯父节点？怎样记录遍历的路径？

考虑二叉树的后续遍历代码

用一个栈记录。

怎么存储K个节点及其标签？

维护一个k个大小的最小堆即可

KD树是非完全二叉树咋办？

如果一开始创建的话，是不存在这个问题的，因为你每次取得都是中位数啊，但是，如果你后期加数据的话，那么可能会有这样的情况产生。

可以借助平衡二叉树的思想对其进行调整

其实无所谓，如果刚好停止于有单边子树的节点，在回溯的时候依然可以考虑到另一边子树的情况。但是要增加判断。

KD树代码

KD 树节点数据结构

主要是记录一些每个点的信息：包括：每一个数据的特征值，对应的标签，左、右孩子，KD树构建过程中划分的维度编号，该数据在KD树中所处的深度。

class KDNode(object):

def __init__(

self, features, label,

left=None, right=None,

axis_no=0, depth=0

):

# 每个节点的特征值

self.features = features

# 每个节点对应的标签

self.label = label

# 节点的左孩子

self.left = left

# 节点的右孩子

self.right = right

# 划分维度编号

self.axis_no = axis_no

# 节点所在的深度

self.depth = depth

KD 树的数据结构：

KD树的初始化

按照某个维度划分子树的依据

按照划分依据计算中位数

计算距离

创建KD树

搜索KD树

KD树的初始化

class KDTree(object):

def __init__(self, n_features):

# 根节点

self.root = None

# 记录维度，总共有多少个特征

self.dimensions = n_features

# 用于记录最近的K个节点

self.k_neighbour = []

# 用于记录搜索的路径

self.path = []

KD树按照某个维度划分子树的依据

'''

Function:

----------

根据树的深度确定划分轴的编号

Parameters

----------

depth: 当前构造节点的深度

n_features: 数据集中特征的数量

Returns

-------

axis_number:第depth层应该在第.axis_number 划分数据

Notes

-------

对于有n_features个特征的数据集，

深度为j的节点，选择X(L)为切分坐标轴，

L=j mod k

'''

def getAxis(self, depth: int, n_features: int)->int:

return depth % n_features

按照划分依据计算中位数(按照指定维度排序之后取中间值)

'''

Function:

----------

按照指定列对矩阵进行排序

Parameters

----------

depth : int

当前构造节点的深度

n_features : int

数据集中特征的数量

Returns

-------

axis_number : int

第depth层应该在第.axis_number 划分数据

Notes

-------

对于有n_features个特征的数据集，

深度为j的节点，选择X(L)为切分坐标轴，

L=j mod k

Examples

-------

a = np.array([

[300, 1, 10, 999],

[200, 2, 30, 987],

[100, 3, 10, 173]

])

sort_index = np.argsort(a, axis=0)

print(sort_index)

>>>

[[2 0 0 2]

[1 1 2 1]

[0 2 1 0]]

sort_index[:, 3]

>>>

[2 1 0]

print(a[sort_index[:, 3]])

>>>

[[100 3 10 173]

[200 2 30 987]

[300 1 10 999]]

'''

def getSortDataset(self, dataset, axis_no):

# 将矩阵按列排序，获取每一列升序结果的索引，结果仍为一个矩阵

sort_index = np.argsort(dataset, axis=0)

return dataset[sort_index[:, axis_no]]

计算距离

'''

Function:

----------

计算距离

Parameters

----------

node: 根节点

target: 目标点的特征值

Returns

-------

两点之间的距离

'''

def getDist(self, node, target):

sqDiffMat = (node.features - target)**2

sqDistances = sqDiffMat.sum(axis=0)

distances = sqDistances ** 0.5

return distances

创建KD树

'''

Function:

----------

构造KD树

Parameters

----------

depth : int

当前构造节点的深度

dataset : numpy.ndarray

只包含特征的矩阵

label : list

包含所有标签的列表

Returns

-------

构造好的KDTree

Notes

-------

1. 如果数据集中只有一条数据，则赋予空的叶子节点

2. 如果不止一条数据，则进行如下操作：

a. 根据构造树当前的深度，选定划分轴(根据哪个特征进行划分)

b. 根据划分轴(该特征)，对数据集按照该特征从小到大排序

c. 选出中位数、排序特征中大于、小于中位数的子数据集

d. 递归调用自身，构造KDTree

'''

def create(self, feature_dataset, label, depth):

samples = feature_dataset.shape[0]

if samples < 1:

return None

if samples == 1:

new_node = KDNode(

feature_dataset[0], label,

depth=depth

)

else:

# 获取分隔坐标轴编号

axis_no = self.getAxis(depth, self.dimensions)

# 获取按第 axis_no 轴排好序的矩阵

sorted_dataset = self.getSortDataset(feature_dataset, axis_no)

# 获取第 axis_no 轴的中位数

median_no = samples//2

# 获取需要设置在左子树的数据集及标签

left_dataset = sorted_dataset[: median_no, :]

left_label = label[: median_no]

# print('left_dataset')

# print(left_dataset)

# 获取需要设置在右子树的数据集及标签

right_dataset = sorted_dataset[median_no+1:, :]

right_label = label[median_no+1:]

# 构造KDTree的节点

new_node = KDNode(

sorted_dataset[median_no, :],

label[median_no],

axis_no=axis_no,

depth=depth

)

# 构造左子树与右子树

new_node.left = self.create(

left_dataset, left_label,

depth + 1

)

new_node.right = self.create(

right_dataset, right_label,

depth + 1

)

return new_node

计算KD树的深度(在搜索和构造中并没有什么卵用)

'''

Function:

----------

计算KD树的深度

Parameters

----------

node: 根节点

Returns

-------

以该节点为根节点的树深度

Notes

-------

'''

def getDepth(self, node: KDNode):

if node is None:

return 0

else:

return max(

self.getDepth(node.left),

self.getDepth(node.right)

) + 1

搜索KD树

'''

Function:

----------

搜索KD树

Parameters

----------

node: 根节点

target: 目标值

Returns

-------

找到距离目标最近的K个值

Notes

-------

'''

def KDTree_NN(self, node: KDNode, target: np.ndarray, k: int):

if k < 1:

raise ValueError("k must be greater than 0.")

else:

if node is None:

raise ValueError("KDTree is None.")

else:

if target.shape[0] != self.dimensions:

raise ValueError("target node's dimension unmatched KDTree's dimension")

else:

self._KDTree_NN(node, target, k)

def _KDTree_NN(self, node: KDNode, target: np.ndarray, k: int):

if node is None:

return

else:

# 计算一下距离，在下一步中看看是不是真的要走这个分支

distance = self.getDist(node, target)

# 因为维护的是最小堆，每个新节点的距离需要和最小堆中的最大值进行比较，所以放在前面了

self.k_neighbour.reverse()

if (len(self.k_neighbour) < k) or (distance < self.k_neighbour[0]['distance']):

# 先顺着左边走到底，然后在看右边的

self._KDTree_NN(node.left, target, k)

self._KDTree_NN(node.right, target, k)

# 把走过的节点都记录下来

self.path.append(node)

# 3.将该点加入堆中，维护一个最小堆，按照distance进行排序

self.k_neighbour.append({

'node': node,

'distance': distance

})

self.k_neighbour = heapq.nsmallest(

k, self.k_neighbour, key=lambda s: s['distance']

)

return

'''

运行结果

以这棵树的数据为例：

构造的KD树

搜索的路径：

KD树的搜索路径

KNN与KD Tree的运行结果

《参考文献》

《统计学习方法》

《机器学习实战》