kdtreepython
Ⅰ python里的kdtree能不能进行汉明距离的搜索
KDTree也是一种特殊的二叉树，同二叉搜索树类似，也是可以边加入新节点，边维护树结构的。
建议用numpy
通过python3中numpy库实现汉明距离(Hamming distance)的计算
汉明距离的定义：两个等长字符串s1 与s2 之间的汉明距离定义为将其中一个变为另外一个所需要做的最小替换次数。例如字符串―1111‖与―1001‖之间的汉明距离为2。
应用：信息编码（为了增强容错性，应使得编码间的最小汉明距离尽可能大）。
程序实现：
通过对应向量（或矩阵）相减，结果中元素中非零元素个数即为汉明距离
例如：
vector1 = mat([1,1,0,1,0,1,0,0,1])
vector2 = mat([0,1,1,0,0,0,1,1,1])
vector3 = vector1-vector2= [[ 1 0 -1 1 0 1 -1 -1 0]]
通过函数nonzero（vector3）以矩阵的形式返回输入值中非零元素的信息如下：
(matrix([[0, 0, 0, 0, 0, 0]], dtype=int32), matrix([[0, 2, 3, 5, 6, 7]], dtype=int32))
再通过shape函数是读取返回值中矩阵的长度，即为汉明距离的长度。
代码如下：
from numpy import *
vector1 = mat([1,1,0,1,0,1,0,0,1])
vector2 = mat([0,1,1,0,0,0,1,1,1])
vector3 = vector1-vector2
print("vector3 = vector1-vector2",vector3)
smstr = nonzero(vector1-vector2);
print (smstr)
print (shape(smstr[0])[1])
程序运行结果如下：
vector3 = vector1-vector2 [[ 1 0 -1 1 0 1 -1 -1 0]]
(matrix([[0, 0, 0, 0, 0, 0]], dtype=int32), matrix([[0, 2, 3, 5, 6, 7]], dtype=int32))
6
Ⅱ PyOD主要算法（KNN、IForest 和 MCD）的原理及使用
https://pyod.readthedocs.io/en/latest/pyod.models.html
Python Outlier Detection（PyOD）是当下最流行的Python异常检测工具库（toolkit）。该工具库的主要亮点包括：
对于特征空间中的一个样本，如果与之最相似的（即特征空间中距离最近的）k个样本中的大多数都属于某一类别，则该样本的分类结果也是这个类别。
https://www.cnblogs.com/lesleysbw/p/6074662.html
① 什么叫做KD_tree
K：K邻近查询中的k；D：空间是D维空间（Demension）tree：二叉树
② 建树过程
K-D tree的建立就是分裂空间的过程
首先，我们对整个区间 [1 , 15] 建树：先计算区间中所有点在第一维（也就是 x 坐标）上的方差：
平均值 ： ave_1 =5.4
方差 ： varance_1 =9.04
再计算区间中所有点在第二维（也就是 y 坐标）上的方差：
平均值：ave_2 =6.8
方差：varance_2 =10.96
明显看见，varance_2 > varance_1 ，那么我们在本次建树中， 分裂方式 ：split_method =2 ， 再将所有的点按照第2维的大小 从小到大排序 ，得到了新的点的一个排列：
（4,2） （1,4） （5,8） （7,9） （10,11）
取中间的点作为分裂点 sorted_mid =（5，8）作为根节点，再把区间 [1 , 2] 建成左子树 , [4 , 5] 建成右子树，此时，直线 ： y = 8 将平面分裂成了两半，前面一半给左儿子，后面一半给了右儿子，如图：
建左子树 [1, 3] 的时候可以发现，这时候 第一维的方差大 ，分裂方式就是1 ，把区间 [ 1, 2 ] 中的点按照 第一维 的大小，从小到大排序 ，取 中间点（1,4） 根节点，再以区间 [ 2, 2] 建立右子树 得到节点 （4,2）
建右子树 [4 , 5] 的时候可以发现，这时还是第一维的方差大， 于是，我们便得到了这样的一颗二叉树 也就是 K-D tree，它把平面分成了如下的小平面， 使得每个小平面中最多有一个点 ：
③ 查询过程：
查询，其实相当于我们要将一个点“添加”到已经建好的 K-D tree 中，但并不是真的添加进去，只是找到他应该 处于的子空间 即可，所以查询就显得简单的。
每次在一个区间中查询的时候，先看这个区间的 分裂方式 是什么，也就是说，先看这个区间是按照哪一维来分裂的，这样如果这个点对应的那一维上面的值比根节点的小，就在根节点的左子树上进行查询操作，如果是大的话，就在右子树上进查询操作。
每次回溯到了根节点（也就是说，对他的一个子树的查找已经完成了）的时候，判断一下，以该点为圆心，目前 找到的最小距离为半径 ，看是否和分裂区间的那一维所构成的平面相交，要是相交的话，最近点可能还在另一个子树上，所以还要再查询另一个子树，同时，还要看能否用根节点到该点的距离来更新我们的最近距离。为什么是这样的，我们可以用一幅图来说明：
https://github.com/YinghongZhang/BallTree-MIPS
① 原理
为了改进KDtree的二叉树树形结构，并且沿着笛卡尔坐标进行划分的低效率，ball tree将在一系列嵌套的超球体上分割数据。也就是说： 使用超球面而不是超矩形划分区域 。虽然在构建数据结构的花费上大过于KDtree，但是在 高维 甚至很高维的数据上都表现的很高效。
球树递归地将数据划分为 由质心C和半径r定义的节点 ，使得节点中的每个点都位于由r和C定义的超球内。通过使用三角不等式来减少邻居搜索的候选点数量。
② 建树过程
选择一个距离当前圆心最远的观测点A，和距离A最远的观测点B，将圆中所有离这两个点最近的观测点都赋给这两个簇的中心，然后计算每一个簇的中心点和包含所有其所属观测点的最小半径。对包含n个观测点的超圆进行分割，只需要线性的时间。
③ 查询
使用ball tree时，先自上而下找到包含target的叶子结点（c, r），从此结点中找到离它最近的观测点。这个距离就是 最近邻的距离的上界 。检查它的 兄弟结点 中是否包含比这个上界更小的观测点。方法是： 如果目标点距离兄弟结点的圆心的距离d > 兄弟节点所在的圆半径R + 前面的上界r，则这个兄弟结点不可能包含所要的观测点 。否则，检查这个兄弟结点是否包含符合条件的观测点。
用一个随机超平面来切割数据空间, 直到每个子空间里面只有一个数据点为止。切割次数的多少可用来区分异常。
https://www.jianshu.com/p/5af3c66e0410
iForest 由t个iTree孤立树组成，每个iTree是一个二叉树，其实现步骤如下：
可以看到d最有可能是异常，因为其最早就被孤立（isolated）了。
获得t个iTree之后，iForest 训练就结束，然后我们可以用生成的iForest来评估测试数据了。对于一个训练数据x，我们令其遍历每一棵iTree，然后计算x最终落在每个树第几层（x在树的高度），得到x在每棵树的高度平均值。获得每个测试数据的average path length后，我们可以设置一个阈值，低于此阈值的测试数据即为异常。
IForest具有线性时间复杂度。
IForest不适用于特别高维的数据。
最小协方差行列式（Minimum Covariance Determinant）
https://max.book118.com/html/2017/1217/144650709.shtm
论文《Minimum covariance determinant and extensions》中有更详细描述。
论文《A Fast Algorithm for the Minimum Covariance Determinant Estimator》有更详细描述。
Ⅲ python 如何画出KD数
简单的KNN算法在为每个数据点预测类别时都需要遍历整个训练数据集来求解距离，这样的做法在训练数据集特别大的时候并不高效，一种改进的方法就是使用kd树来存储训练数据集，这样可以使KNN分类器更高效。
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)
对于一个新来的数据点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)525354555657
以上就是KD树的Python实践的全部内容，由于本人刚接触python不久，可能实现上并不优雅，也可能在算法理解上存在偏差，如果有任何的错误或不足，希望各位赐教。
Ⅳ python如何在众多的点中找到与特定点最近的点的算法
首先目测一下查询大概不止一次所以前面那些统统乘个Q就大爆炸吧。
平民的做法写个kdtree基本sqrt n复杂度对付10w的数据量应该轻松愉快，动态的话套个替罪羊。
泥垢无聊的话动态v图欢迎入坑 传闻是logn的我没写过不知道会不会比上面的慢。
啊找到了我记得这个大轮子应该可以很简单（不如手写）的解决你的问题
PCL - Point Cloud Library (PCL)
-
单纯的替罪羊套kdt放到这种场合可能不大合适……毕竟修改一次可能锁死整个子树……（当然可以不用替罪羊，缓存sqrt n个修改，然后每sqrt n个修改暴力重构整个树，重构完成之前就先用原来的，然后再加上各种奇怪的优化……。）
然后再YY一下，我个人觉得他们可能是这样干的，首先把地图切成一块一块的每块足够小。然后随便YY一下按照每个地方人数的多少，取一个合适的am^2范围内最多有x人，然后只要这个x够小，查询的时候只查询当前用户所在的区块和周围的几个区块就好了，然后你就可以用轮子哥那样的sql查询啦～
如果还是有问题要么加服务器，或者最不济还可以对这个区块再维护kdtree。而且这样修改起来还方便。
至于用户周围都没有人，最近的有人区块在几十公里外…
Ⅳ 如何设计好词袋模型的类类型
如何设计好词袋模型的类类型
回顾过去自己写过的一些词袋模型，比如 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 = 0; i < descSize; i++ ){
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 = 0; i < descSize; i++ ){
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 = 0; i < imgFeatsSize; i++ ){
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 = 0; i < imgFeatsSize; i++) {
// 读入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来进行数据读写保存了，测了一下，数据读写还是比较高效的，所以暂且采用这种方案。