#define KDTREE_H
#include <cassert>
#include <algorithm>
#include <cstddef>
#include <vector>
#include <cmath>
#include <iostream>
using ::std::vector
using ::std::cout
using ::std::endl
namespace sx {
typedef float DataType
typedef unsigned int UInt
struct Feature {
vector<DataType> data
int id
Feature() {}
Feature(const vector<DataType> & d, int i)
: data(d), id(i) {}
} /* optional variable list */
template <UInt K>
class KDTree {
public:
KDTree()
virtual ~KDTree()
KDTree(const KDTree & rhs)
const KDTree & operator = (const KDTree & rhs)
void Clean()
void Build(const vector<Feature> & matrix_feature)
int FindNearestFeature(const Feature & target) const
int FindNearestFeature(const Feature & target,
DataType & min_difference) const
void Show() const
private:
struct KDNode {
KDNode * left
KDNode * right
Feature feature
int depth
KDNode(const Feature & f, KDNode * lt, KDNode * rt, int d)
: feature(f), left(lt), right(rt), depth(d) {}
} /* optional variable list */
KDNode * root_
struct Comparator {
int index_comparator
Comparator(int ix)
: index_comparator(ix) {}
bool operator () (const Feature & lhs, const Feature & rhs) {
return lhs.data[index_comparator] < rhs.data[index_comparator]
}
} /* optional variable list */
KDNode * Clone(KDNode * t) const
void Clean(KDNode * & t)
void SortFeature(vector<Feature> & features, int index)
void Build(const vector<Feature> & matrix_feature,
KDNode * & t, int depth)
DataType Feature2FeatureDifference(const Feature & f1,
const Feature & f2) const
int FindNearestFeature(const Feature & target,
DataType & min_difference, KDNode * t) const
void Show(KDNode * t) const
}
template <UInt K>
KDTree<K>::
KDTree()
: root_(NULL) {}
template <UInt K>
KDTree<K>::
~KDTree() {
Clean()
}
template <UInt K>
KDTree<K>::
KDTree(const KDTree & rhs) {
*this = rhs
}
template <UInt K>
const KDTree<K> & KDTree<K>::
operator = (const KDTree & rhs) {
if (this != &rhs) {
Clean()
root_ = Clone(rhs.root_)
}
return *this
}
template <UInt K>
void KDTree<K>::
Clean() {
Clean(root_)
}
template <UInt K>
void KDTree<K>::
Build(const vector<Feature> & matrix_feature) {
if (matrix_feature.size() != 0) {
assert(matrix_feature[0].data.size() == K)
}
Build(matrix_feature, root_, 0)
}
template <UInt K>
int KDTree<K>::
FindNearestFeature(const Feature & target) const {
DataType min_difference
return FindNearestFeature(target, min_difference)
}
template <UInt K>
int KDTree<K>::
FindNearestFeature(const Feature & target, DataType & min_difference) const {
min_difference = 10e8
return FindNearestFeature(target, min_difference, root_)
}
template <UInt K>
void KDTree<K>::
Show() const {
Show(root_)
return
}
template <UInt K>
typename KDTree<K>::KDNode * KDTree<K>::
Clone(KDNode * t) const {
if (NULL == t) {
return NULL
}
return new KDNode(t->feature, t->left, t->right, t->depth)
}
template <UInt K>
void KDTree<K>::
Clean(KDNode * & t) {
if (t != NULL) {
Clean(t->left)
Clean(t->right)
delete t
}
t = NULL
}
template <UInt K>
void KDTree<K>::
SortFeature(vector<Feature> & features, int index) {
sort(features.begin(), features.end(), Comparator(index))
}
template <UInt K>
void KDTree<K>::
Build(const vector<Feature> & matrix_feature, KDNode * & t, int depth) {
if (matrix_feature.size() == 0) {
t = NULL
return
}
vector<Feature> temp_feature = matrix_feature
vector<Feature> left_feature
vector<Feature> right_feature
SortFeature(temp_feature, depth % K)
int length = (int)temp_feature.size()
int middle_position = length / 2
t = new KDNode(temp_feature[middle_position], NULL, NULL, depth)
for (int i = 0 i < middle_position ++i) {
left_feature.push_back(temp_feature[i])
}
for (int i = middle_position + 1 i < length ++i) {
right_feature.push_back(temp_feature[i])
}
Build(left_feature, t->left, depth + 1)
Build(right_feature, t->right, depth + 1)
return
}
template <UInt K>
DataType KDTree<K>::
Feature2FeatureDifference(const Feature & f1, const Feature & f2) const {
DataType diff = 0.0
assert(f1.data.size() == f2.data.size())
for (int i = 0 i < (int)f1.data.size() ++i) {
diff += (f1.data[i] - f2.data[i]) * (f1.data[i] - f2.data[i])
}
return sqrt(diff)
}
template <UInt K>
int KDTree<K>::
FindNearestFeature(const Feature & target, DataType & min_difference,
KDNode * t) const {
if (NULL == t) {
return -1
}
DataType diff_parent = Feature2FeatureDifference(target, t->feature)
DataType diff_left = 10e8
DataType diff_right = 10e8
int result_parent = -1
int result_left = -1
int result_right = -1
if (diff_parent < min_difference) {
min_difference = diff_parent
result_parent = t->feature.id
}
if (NULL == t->left && NULL == t->right) {
return result_parent
}
if (NULL == t->left /* && t->right != NULL */) {
result_right = FindNearestFeature(target, diff_right, t->right)
if (diff_right < min_difference) {
min_difference = diff_right
result_parent = result_right
}
return result_parent
}
if (NULL == t->right /* && t->left != NULL */) {
result_left = FindNearestFeature(target, diff_left, t->left)
if (diff_left < min_difference) {
min_difference = diff_left
result_parent = result_left
}
return result_parent
}
int index_feature = t->depth % K
DataType diff_boundary =
fabs(target.data[index_feature] - t->feature.data[index_feature])
if (target.data[index_feature] < t->feature.data[index_feature]) {
result_left = FindNearestFeature(target, diff_left, t->left)
if (diff_left < min_difference) {
min_difference = diff_left
result_parent = result_left
}
if (diff_boundary <
Feature2FeatureDifference(target, t->left->feature)) {
result_right = FindNearestFeature(target, diff_right, t->right)
if (diff_right < min_difference) {
min_difference = diff_right
result_parent = result_right
}
}
} else {
result_right = FindNearestFeature(target, diff_right, t->right)
if (diff_right < min_difference) {
min_difference = diff_right
result_parent = result_right
}
if (diff_boundary <
Feature2FeatureDifference(target, t->right->feature)) {
result_left = FindNearestFeature(target, diff_left, t->left)
if (diff_left < min_difference) {
min_difference = diff_left
result_parent = result_left
}
}
}
return result_parent
}
template <UInt K>
void KDTree<K>::Show(KDNode * t) const {
cout << "ID: " << t->feature.id << endl
cout << "Data: "
for (int i = 0 i < (int)t->feature.data.size() ++i) {
cout << t->feature.data[i] << " "
}
cout << endl
if (t->left != NULL) {
cout << "Left: " << t->feature.id << " -> " << t->left->feature.id << endl
Show(t->left)
}
if (t->right != NULL) {
cout << "Right: " << t->feature.id << " -> " << t->right->feature.id << endl
Show(t->right)
}
return
}
} /* sx */
#endif /* end of include guard: KDTREE_H */
KD Tree 是KNN算法中用于计算最近邻的快速简便的构建方式。
当样本量少的时候，用 brute 直接搜索最近邻的方式是可行的。即计算到所有样本的距离。但当样本量庞大时，直接计算所有样本距离的工作量很大，这种情况使用 KD Tree 可以节约大量时间成本。
KD树采用从m个样本的n维特征中，分别计算n个特征取值的方差，用 方差最大 的第k维特征n k 作为 根节点 。对于这个特征，选择取值中的 中位数 n kv 作为样本的划分点，对于小于该值的样本划分到 左子树 ，对于大于等于该值的样本划分到 右子树 ，对左右子树采用同样的方式找 方差最大的特征 作为 根节点 ，递归产生KD Tree。
为什么要选择方差最大的进行划分？
构建树的目的是加快我的搜索过程。
既然我想加快我的搜索过程，要就意味着我最终的数据落在某个叶子节点上。我希望只需搜索整个二叉树的某一些列即可，那么最好的划分方式，就是让我的每个分支上数据的差异性最大化。
那么衡量数据差异性的最基础的数学指标是什么？
是方差。方差越大，意味着数据的离散程度就越大，我将离散程度由大到小的数据一分为二，方差小意味着数据更集中到了一起。
现在有一个二维样本: {(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}
1、计算x1和x2每一列对应的方差
a、通过pandas计算出的是 样本方差:
/ (n-1)
0|6.966667
1|5.366667
dtype: float64
b、通过numpy计算出的是 总体方差:
/ n
[[2 3]
[5 4]
[9 6]
[4 7]
[8 1]
[7 2]]
[ 5.80555556 4.47222222]
[ 5.80555556 4.47222222]
第一个树的划分：基于x 1 进行划分
[2,4,5,7,8,9]的中位数是5和7的平均值6。
虽然严格意义上说中位数是6，但是在计算机中我们人为得定义x 1 的中位数是7。
左侧：（2,3）（5,4）（4,7） （7,2）
右侧: （9,6）（8,1）
第二个树的划分：根据右侧（9,6）（8,1）的x 2 进行划分
下侧：x 2 ≤ 6；上侧x 2 ＞6
第二个树的划分：根据左侧（2,3）（5,4）（4,7） （7,2）的x 2 进行划分
寻找2、3、4、7的中位数 4 进行划分
....
注意：每次生成的划分都是一个矩形。当叶子节点无法被继续划分的时候，KD树的构建完成，递归结束。
我们生成了KD Tree后，现在就可以去预测测试集里面的样本目标点了。
1、对于一个目标点，先在KD树里找到包含目标点的叶子节点。
2、以目标点为圆心，以 目标点 到 叶子节点样本实例 的距离为半径，得到一个超球体，最近邻的点一定在这个超球体内部。
3、然后返回叶子节点的父节点，检查另一个子节点包含的超矩形体是否和超球体相交。
4、如果相交就倒这个子节点寻找着是否有更加近的近邻，有的话就更新最近邻。
5、如果不相交，直接返回父节点中的父节点，在另一个子树继续搜索最近邻。当回溯到根节点时，算法结束。
6、此时保存的最近邻节点就是最终的最近邻。
如果现在想找(2,4.5)这点的最近邻，该如何 *** 作？
1、画出二叉树：
2、寻找(2,4.5)这点：
一个比较好的理解方式：首先找到第一个最近邻，然后画出一个圆。然后逐渐收缩圆的半径，查看每次缩小后的圆是否能够和矩形相交于一个更小的最近邻点，如果有则更新。直到回到根节点。
KNN算法的重要步骤是对所有的实例点进行快速k近邻搜索。如果采用线性扫描（linear scan），要计算输入点与每一个点的距离，时间复杂度非常高。因此在查询 *** 作时，可以使用kd树对查询 *** 作进行优化。
Kd-树是K-dimension tree的缩写，是对数据点在k维空间（如二维(x，y)，三维(x，y，z)，k维(x1，y，z..)）中划分的一种数据结构，主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。本质上说，Kd-树就是一种平衡二叉树。
k-d tree是每个节点均为k维样本点的二叉树，其上的每个样本点代表一个超平面，该超平面垂直于当前划分维度的坐标轴，并在该维度上将空间划分为两部分，一部分在其左子树，另一部分在其右子树。即若当前节点的划分维度为d，其左子树上所有点在d维的坐标值均小于当前值，右子树上所有点在d维的坐标值均大于等于当前值，本定义对其任意子节点均成立。
必须搞清楚的是，k-d树是一种空间划分树，说白了，就是把整个空间划分为特定的几个部分，然后在特定空间的部分内进行相关搜索 *** 作。想像一个三维(多维有点为难你的想象力了)空间，kd树按照一定的划分规则把这个三维空间划分了多个空间，如下图所示：
首先，边框为红色的竖直平面将整个空间划分为两部分，此两部分又分别被边框为绿色的水平平面划分为上下两部分。最后此4个子空间又分别被边框为蓝色的竖直平面分割为两部分，变为8个子空间，此8个子空间即为叶子节点。
常规的k-d tree的构建过程为：
对于构建过程，有两个优化点：
例子：采用常规的构建方式，以二维平面点(x,y)的集合(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2) 为例结合下图来说明k-d tree的构建过程：
如上算法所述，kd树的构建是一个递归过程，我们对左子空间和右子空间内的数据重复根节点的过程就可以得到一级子节点（5,4）和（9,6），同时将空间和数据集进一步细分，如此往复直到空间中只包含一个数据点。
如之前所述，kd树中，kd代表k-dimension，每个节点即为一个k维的点。每个非叶节点可以想象为一个分割超平面，用垂直于坐标轴的超平面将空间分为两个部分，这样递归的从根节点不停的划分，直到没有实例为止。经典的构造k-d tree的规则如下：
kd树的检索是KNN算法至关重要的一步，给定点p，查询数据集中与其距离最近点的过程即为最近邻搜索。
如在构建好的k-d tree上搜索(3,5)的最近邻时，对二维空间的最近邻搜索过程作分析。
首先从根节点(7,2)出发，将当前最近邻设为(7,2)，对该k-d tree作深度优先遍历。
以(3,5)为圆心，其到(7,2)的距离为半径画圆（多维空间为超球面），可以看出(8,1)右侧的区域与该圆不相交，所以(8,1)的右子树全部忽略。
接着走到(7,2)左子树根节点(5,4)，与原最近邻对比距离后，更新当前最近邻为(5,4)。
以(3,5)为圆心，其到(5,4)的距离为半径画圆，发现(7,2)右侧的区域与该圆不相交，忽略该侧所有节点，这样(7,2)的整个右子树被标记为已忽略。
遍历完(5,4)的左右叶子节点，发现与当前最优距离相等，不更新最近邻。所以(3,5)的最近邻为(5,4)。
举例：查询点（2.1,3.1）
星号表示要查询的点（2.1,3.1）。通过二叉搜索，顺着搜索路径很快就能找到最邻近的近似点，也就是叶子节点（2,3）。而找到的叶子节点并不一定就是最邻近的，最邻近肯定距离查询点更近，应该位于以查询点为圆心且通过叶子节点的圆域内。为了找到真正的最近邻，还需要进行相关的‘回溯' *** 作。也就是说，算法首先沿搜索路径反向查找是否有距离查询点更近的数据点。
举例：查询点（2，4.5）
一个复杂点了例子如查找点为（2，4.5），具体步骤依次如下：
上述两次实例表明，当查询点的邻域与分割超平面两侧空间交割时，需要查找另一侧子空间，导致检索过程复杂，效率下降。
一般来讲，最临近搜索只需要检测几个叶子结点即可，如下图所示：
但是，如果当实例点的分布比较糟糕时，几乎要遍历所有的结点，如下所示：
研究表明N个节点的K维k-d树搜索过程时间复杂度为： 。
同时，以上为了介绍方便，讨论的是二维或三维情形。但在实际的应用中，如SIFT特征矢量128维，SURF特征矢量64维，维度都比较大，直接利用k-d树快速检索（维数不超过20）的性能急剧下降，几乎接近贪婪线性扫描。假设数据集的维数为D，一般来说要求数据的规模N满足N»2D，才能达到高效的搜索。
Sklearn中有KDTree的实现，仅构建了一个二维空间的k-d tree，然后对其作k近邻搜索及指定半径的范围搜索。多维空间的检索，调用方式与此例相差无多。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）