KD树的主要思想跟二叉树类似，我们先来回忆一下二叉树的结构，二叉树中每个节点可以看成是一个数，当前节点总是比左子树中每个节点大，比右子树中每个节点小。而KD树中每个节点是一个向量(也可能是多个向量)，和二叉树总是按照数的大小划分不同的是，KD树每层需要选定向量中的某一维，然后根据这一维按左小右大的方式划分数据。在构建KD树时，关键需要解决2个问题：（1）选择向量的哪一维进行划分（2）如何划分数据。第一个问题简单的解决方法可以是选择随机选择某一维或按顺序选择，但是更好的方法应该是在数据比较分散的那一维进行划分（分散的程度可以根据方差来衡量）。好的划分方法可以使构建的树比较平衡，可以每次选择中位数来进行划分，这样问题2也得到了解决。下面是建立KD树的Python代码：
def build_tree(data, dim, depth):
"""
建立KD树
Parameters
----------
data:numpy.array
需要建树的数据集
dim:int
数据集特征的维数
depth:int
当前树的深度
Returns
-------
tree_node:tree_node namedtuple
树的跟节点
"""
size = data.shape[0]
if size == 0:
return None
# 确定本层划分参照的特征
split_dim = depth % dim
mid = size / 2
# 按照参照的特征划分数据集
r_indx = np.argpartition(data[:, split_dim], mid)
data = data[r_indx, :]
left = data[0: mid]
right = data[mid + 1: size]
mid_data = data[mid]
# 分别递归建立左右子树
left = build_tree(left, dim, depth + 1)
right = build_tree(right, dim, depth + 1)
# 返回树的根节点
return Tree_Node(left=left,
right=right,
data=mid_data,
split_dim=split_dim)
12345678910111213141516171819202122232425262728293031323334353637381234567891011121314151617181920212223242526272829303132333435363738
对于一个新来的数据点x，我们需要查找KD树中距离它最近的节点。KD树的查找算法还是和二叉树查找的算法类似，但是因为KD树每次是按照某一特定的维来划分，所以当从跟节点沿着边查找到叶节点时候并不能保证当前的叶节点就离x最近，我们还需要回溯并在每个父节点上判断另一个未查找的子树是否有可能存在离x更近的点（如何确定的方法我们可以思考二维的时候，以x为原点，当前最小的距离为半径画园，看是否与划分的直线相交，相交则另一个子树中可能存在更近的点），如果存在就进入子树查找。
当我们需要查找K个距离x最近的节点时，我们只需要维护一个长度为K的优先队列保持当前距离x最近的K个点。在回溯时，每次都使用第K短距离来判断另一个子节点中是否存在更近的节点即可。下面是具体实现的python代码：
def search_n(cur_node, data, queue, k):
"""
查找K近邻，最后queue中的k各值就是k近邻
Parameters
----------
cur_node:tree_node namedtuple
当前树的跟节点
data:numpy.array
数据
queue:Queue.PriorityQueue
记录当前k个近邻，距离大的先输出
k:int
查找的近邻个数
"""
# 当前节点为空，直接返回上层节点
if cur_node is None:
return None
if type(data) is not np.array:
data = np.asarray(data)
cur_data = cur_node.data
# 得到左右子节点
left = cur_node.left
right = cur_node.right
# 计算当前节点与数据点的距离
distance = np.sum((data - cur_data) ** 2) ** .5
cur_split_dim = cur_node.split_dim
flag = False # 标记在回溯时是否需要进入另一个子树查找
# 根据参照的特征来判断是先进入左子树还是右子树
if data[cur_split_dim] >cur_data[cur_split_dim]:
tmp = right
right = left
left = tmp
# 进入子树查找
search_n(left, data, queue, k)
# 下面是回溯过程
# 当队列中没有k个近邻时，直接将当前节点入队，并进入另一个子树开始查找
if len(queue) <k:
neg_distance = -1 * distance
heapq.heappush(queue, (neg_distance, cur_node))
flag = True
else:
# 得到当前距离数据点第K远的节点
top_neg_distance, top_node = heapq.heappop(queue)
# 如果当前节点与数据点的距离更小，则更新队列（当前节点入队，原第k远的节点出队）
if - 1 * top_neg_distance >distance:
top_neg_distance, top_node = -1 * distance, cur_node
heapq.heappush(queue, (top_neg_distance, top_node))
# 判断另一个子树内是否可能存在跟数据点的距离比当前第K远的距离更小的节点
top_neg_distance, top_node = heapq.heappop(queue)
if abs(data[cur_split_dim] - cur_data[cur_split_dim]) <-1 * top_neg_distance:
flag = True
heapq.heappush(queue, (top_neg_distance, top_node))
# 进入另一个子树搜索
if flag:
search_n(right, data, queue, k)123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657
以上就是KD树的Python实践的全部内容，由于本人刚接触python不久，可能实现上并不优雅，也可能在算法理解上存在偏差，如果有任何的错误或不足，希望各位赐教。
如何设计好词袋模型的类类型回顾过去自己写过的一些词袋模型，比如 BoW图像检索Python实战 、 图像检索(CBIR)三剑客之BoF、VLAD、FV 以及Bag of Words cpp实现，这些写出来的要么只是助于自己理解词袋模型的有关理论，要么也只是面向实验的一些验证，或者更直接点可以说只是些小玩具摆了。
在我2016年的计划列表里，存放着一条由2015年拖过来的目标，就是写出一个可以面向商业级别的词袋模型，这条计划伴随着成功将VLfeat的一些c接口打通而变成了可能，并且在过去的大半年里，自己也一直留意在具体编写的时候选用哪些库比较合适的问题。机缘巧合，这一段时间又重新开始造起了轮子，并有了初步的成功，所以在此梳理总结一下。在谈怎样设计一个词袋模型的类类型之前，先谈谈库的选用问题。
选取合适的库
在具体编写一个面向应用级别的词袋模型的时候，大概会经历这么几个步骤：SIFT特征抽取，特征采样，聚类，构建KD树，统计词频，计算词频权重，计算词频直方图，保存数据。这8个步骤在具体实现的时候，会设计到一些库的选取问题，下面对其进行细谈。
1) SIFT特征抽取提取选用哪个库？
提取SIFT的库有很多，主要有以下几个大家用得比较多：
Lowe的 SIFT ，效果只提供SIFT的二进制可执行文件，弃用；
Robwhess的 OpenSIFT ，开源，效果也还不错，需要一些别的依赖库，不再更新，弃用；
OpenCV的SIFT，这个当然在使用上是最方便的，文档全，不依赖别的库，但SIFT的实现效果并不是很好，弃用；
VLfeat里的 SIFT ，SIFT的实现效果是比较好的，缺点是c接口文档不怎么全，网上提供的资料也比较少，但多读读它的C源码，还是可以搞定的，而且在不用依赖其他的库，所以选择这个库来提取SIFT还是很好的，在实际提取的时候，我选用的是 covdet 函数来提取SIFT，它是一个功能更强大的提取co-variant特征提取器。
在去年的时候，基本弄清了VLfeat中的一些函数的C接口调用方式，covdet这个函数通过阅读写给matlab的接口源码转成的C，对比matlab提取的结果和自己转成C之后提取的结果，两者完全一致。
2) 矩阵运算库的选取
虽然使用矩阵操作并不是必须的，除了OpenCV的矩阵，还有可能引入其他的矩阵运算库，这些矩阵的引入会给后面的实现带来巨大的方便，比如聚类，KD树的构建以及后面词频统计等。作为运算的基础库，在矩阵库的选择上主要有下面几个用得比较多：
Eigen ，使用的只需要把头文件包含进工程里即可，提供了多个平台的版本，比如可以运行于安卓上，矩阵运算操作还是比较方便的，更新得比较快，不过在PC平台上开发，我比较倾向于使用下面要说的Armadillo。
Armadillo ，这个库是我非常喜欢的矩阵运算库，此矩阵库在使用语法上Matlabjie借鉴了Matlab的语法使用习惯，所以熟悉Matlab的开发者在使用此库的时候会觉得非常的舒服，并且有名的MLPack是建立在它的基础之上，另外它的矩阵运算效率也是非常高的，使用的时候同Eigen一样只需要包含头文件目录即可，最新版本中添加了KMeans聚类。因而，基于以上这些优点，在实现词袋模型的时候，对于矩阵运算库的选取，选择这个无疑是最优的。
选用矩阵库虽然能极大的方便我们的程序编写，但是会涉及到数据类型的转换，比如STL的vector存储的数据要转成Armadillo的矩阵进行运算，如果数据频繁的进行类型的转换，必然会降低程序的运行效率，因而在程序的编写中，不必要转换的尽量避免转换。
3) 多线程并行处理
为了使程序的SIFT特征提取、KMeans聚类、统计词频等过程支持并行处理，在选择并行计算库的时候，有两种选择，一种是采用OpenMP，另一种是选择MPI。OpenMP是采用的是内存共享的方式，只需要对原程序进行小幅调整即可实现并行处理，并且语法易读已写；MPI需要对原来的程序进行大幅重构，写出来的代码也不是很好读。所以，在多线程并处计算库选择这块，选择OpenMP是比较好的。
词袋模型的类类型设计
终于可以讲核心的了，这一部分讲讲在编写程序的时候自己对词袋模型的类类型设计的一点心得。先上自己写的词袋模型的类类型，设计了两个类，一个是 SIFT特征提取的类类型 ，另一个是 词袋模型的类类型 。先谈谈 SIFT特征提取的类类型 ：
class siftDesctor{
public:
siftDesctor(){}
std::string imageName
std::vector<std::vector<float>>frame
std::vector<std::vector<float>>desctor
void covdet_keypoints_and_descriptors(cv::Mat &img, std::vector<std::vector<float>>&frames, std::vector<std::vector<float>>&desctor, bool rooSIFT, bool verbose)
std::vector<float>rootsift(std::vector<float>&dst)
void Serialize(std::ofstream &outfile) const {
std::string tmpImageName = imageName
int strSize = (int)imageName.size()
outfile.write((char *)&strSize, sizeof(int))
outfile.write((char *)&tmpImageName[0], sizeof(char)*strSize)// 写入文件名
int descSize = (int)desctor.size()
outfile.write((char *)&descSize, sizeof(int))
// 写入sift特征
for(int i = 0i <descSizei++ ){
outfile.write((char *)&(desctor[i][0]), sizeof(float) * 128)
outfile.write((char *)&(frame[i][0]), sizeof(float) * 6)
}
}
static siftDesctor Deserialize(std::ifstream &ifs) {
siftDesctor siftDesc
int strSize = 0
ifs.read((char *)&strSize, sizeof(int))// 写入文件名
siftDesc.imageName = ""
siftDesc.imageName.resize(strSize)
ifs.read((char *)&(siftDesc.imageName[0]), sizeof(char)*strSize)// 读入文件名
int descSize = 0
ifs.read((char *)&descSize, sizeof(int))
// 读入sift特征和frame
for(int i = 0i <descSizei++ ){
std::vector<float>tmpDesc(128)
ifs.read((char *)&(tmpDesc[0]), sizeof(float) * 128)
siftDesc.desctor.push_back(tmpDesc)
std::vector<float>tmpFrame(6)
ifs.read((char *)&(tmpFrame[0]), sizeof(float) * 6)
siftDesc.frame.push_back(tmpFrame)
}
return siftDesc
}
}
在设计SIFT特征提取的类类型的时候，对于每一幅图像，提取SIFT特征之后，由于需要保存图像名、128维的SIFT特征以及6维的frame，因为 imageName 、 desctor 和 frame 这三个成员是必须的，这里说一下对于 imageName 这个成员，在最后保存方式文件名的时候，更合理的方式是不应该带入文件所在目录路径的，因为最终写入的数据有可能转移到别的计算机上，带入路径不便于共享后使用者对数据的处理，这个地方我在刚开始设计的时候有欠考虑。另外，刚开始在设计 covdet_keypoints_and_descriptors() 方法的时候，是在方法里读入图片然后在提取特征的，当时想得是想让这样一个特征提取器更加的方便使用(只需要传入图像待路径的文件名就可以处理)，但后来发现其实根本没必要这么设计这个方法，这种蹩脚的方式使得后面在显示结果的时候，你需要再次读入图片，降低了程序的执行效率，因而改成了现在的这种传入已读入数据的方式。
上面除了三个重要的成员变量，两个序列化和反序列化的方法是极其重要的，序列化的目的使得上面三个重要的成员变量得以保存，这样可以避免当我们想再次聚类时又要提取特征的尴尬；反序列化使得我们可以读取保存的数据，因而，三个成员变量加两个方法都是必不可少的。
再谈 词袋模型的类类型 ，先看类定义：
class bowModel {
public:
bowModel(){}
bowModel(int _numWords,std::vector<siftDesctor>_imgFeatures, std::vector<std::vector<int>>_words):numWords(_numWords),imgFeatures(_imgFeatures),words(_words){}
int numNeighbors = 1
int numWords
std::vector<siftDesctor>imgFeatures
std::vector<std::vector<int>>words
cv::Mat centroids_opencvMat
cv::flann::Index opencv_buildKDTree(cv::Mat ¢roids_opencvMat)
void Serialize(std::ofstream &outfile) const {
int imgFeatsSize = (int)imgFeatures.size()
outfile.write((char *)&imgFeatsSize, sizeof(int))
// 写入imgFeatures和words
for(int i = 0i <imgFeatsSizei++ ){
imgFeatures[i].Serialize(outfile)
outfile.write((char *)&(words[i][0]), sizeof(int) * imgFeatures[i].desctor.size())
}
}
static bowModel Deserialize(std::ifstream &ifs) {
bowModel BoW
int imgFeatsSize
ifs.read((char *)&imgFeatsSize, sizeof(int))
BoW.words.resize(imgFeatsSize)
for (int i = 0i <imgFeatsSizei++) {
// 读入imgFeatures
auto siftDesc = siftDesctor::Deserialize(ifs)
BoW.imgFeatures.push_back(siftDesc)
// 读入words
BoW.words[i].resize(siftDesc.desctor.size())
ifs.read((char *)&(BoW.words[i][0]), sizeof(int) * siftDesc.desctor.size())
}
return BoW
}
}
上面最重要的有三个东西，一是成员 std::vector<siftDesctor>imgFeatures ，另外是序列化和反序列化方法。对于每一个图片提取的特征，将 imageName 、 desctor 和 frame 通过实例化一个siftDesctor将其保存起来，这样我们将所有图片的siftDesctor实例用STL的vector保存下来，在序列化的时候，对每一个实例通过调用 SIFT特征提取的类类型 中定义的序列化方法将其保存下来，读取数据的时候，其过程基本就是原来的一个拟过程。通过这样设计这样两个 SIFT特征提取的类类型 和 词袋模型的类类型 ，在数据读写的时候，通过内外两重循环，内部循环完成一个实例的数据读写，外部循环完成所有图片实例的读写，使得我们可以比较优雅地完成图片的特征提取、数据保存以及读写。
对于数据读写，做过一番调研，一种是通过HDF5的方式，一种是通过BOOST库。HDF5很适合大数据量的保存，而且读写高效，但在C++里，写起来没有在Python里使用HDF5方便，BOOST也查阅过相应的资料，写起来也比较繁杂，所以最后选择了只用fstream来进行数据读写保存了，测了一下，数据读写还是比较高效的，所以暂且采用这种方案。
机器学习方面的面试主要分成三个部分：
算法和理论基础
2. 工程实现能力与编码水平
3. 业务理解和思考深度
理论方面，我最经典的一本书《统计学习方法》，这书可能不是最全的，但是讲得最精髓，薄薄一本，适合面试前突击准备。
我认为一些要点是：
统计学习的核心步骤：模型、策略、算法，你应当对logistic、SVM、决策树、KNN及各种聚类方法有深刻的理解。能够随手写出这些算法的核心递归步的伪代码以及他们优化的函数表达式和对偶问题形式。
非统计学习我不太懂，做过复杂网络，但是这个比较深，面试可能很难考到。
数学知识方面，你应当深刻理解矩阵的各种变换，尤其是特征值相关的知识。
算法方面：你应当深刻理解常用的优化方法：梯度下降、牛顿法、各种随机搜索算法（基因、蚁群等等），深刻理解的意思是你要知道梯度下降是用平面来逼近局部，牛顿法是用曲面逼近局部等等。
2. 工程实现能力与编码水平
机器学习从工程实现一般来讲都是某种数据结构上的搜索问题。
你应当深刻理解在1中列出的各种算法对应应该采用的数据结构和对应的搜索方法。比如KNN对应的KD树、如何给图结构设计数据结构？如何将算法map-red化等等。
一般来说要么你会写C，而且会用MPI，要么你懂Hadoop，工程上基本都是在这两个实现。实在不济你也学个python吧。
3. 非常令人失望地告诉你尽管机器学习主要会考察1和2
但是实际工作中，算法的先进性对真正业务结果的影响，大概不到30%。当然算法必须要足够快，离线算法最好能在4小时内完成，实时算法我没搞过，要求大概
更高。
机器学习大多数场景是搜索、广告、垃圾过滤、安全、系统等等。对业务有深刻的理解对你做出来的系统的结果影响超过70%。这里你没做过实际的项目，是
完全不可能有任何体会的，我做过一个系统，没有什么算法上的高大上的改进，主要是业务逻辑的创新，直接就提高了很明显的一个CTR（具体数目不太方便
透露，总之很明显就是了）。如果你做过实际的项目，一定要主动说出来，主动让面试官知道，这才是最大最大的加分项目。
最后举个例子，阿里内部机器学习挑战赛，无数碾压答主10000倍的大神参赛。最后冠军没有用任何高大上的算法而是基于对数据和业务的深刻理解和极其细致
的特征调优利用非常基本的一个算法夺冠。所以啥都不如真正的实操撸几个生产项目啊。
