Python实现KNN与KDTree
2019-06-19 本文已影响0人
To_QT
KNN算法：
KNN的基本思想以及数据预处理等步骤就不介绍了，网上挑了两个写的比较完整有源码的博客。
利用KNN约会分类
KNN项目实战——改进约会网站的配对效果
KNN 代码
'''
Function:
----------
找出距离目标最近的K个特征值
Parameters
----------
target<ndarray>: 目标点的特征值
feature_dataset<ndarray>: 已知数据的特征值
k<int>: 最近的数量
Returns
-------
<ndarray>：目标最近的特征值的索引列表
'''
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<int>: 当前构造节点的深度
n_features<int>: 数据集中特征的数量
Returns
-------
axis_number<int>:第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<KDNode>: 根节点
target<ndarray>: 目标点的特征值
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的运行结果
《参考文献》
- 《统计学习方法》
- 《机器学习实战》
