kd树 机器学习_机器学习 kd_tree - CSDN
  • 机器学习04 kd树

    2019-05-01 11:13:13
    为什么要使用kd树 k近邻法最简单的实现是线性扫描(穷举搜索),即要计算输入实例与每一个训练实例的距离。计算并存储好以后,再查找K近邻。当训练集很大时,计算非常耗时。 为了提高kNN搜索的效率,可以考虑使用...

    为什么要使用kd树
    k近邻法最简单的实现是线性扫描(穷举搜索),即要计算输入实例与每一个训练实例的距离。计算并存储好以后,再查找K近邻。当训练集很大时,计算非常耗时。

    为了提高kNN搜索的效率,可以考虑使用特殊的结构存储训练数据,以减小计算距离的次数。
    什么是kd树
    kd树:为了避免每次都重新计算一遍距离,算法会把距离信息保存在一棵树里,这样在计算之前从树里查询距离信息,尽量避免重新计算。其基本原理是,如果A和B距离很远,B和C距离很近,那么A和C的距离也很远。有了这个信息,就可以在合适的时候跳过距离远的点。
    1989年,另外一种称为Ball Tree的算法,在kd Tree的基础上对性能进一步进行了优化。感兴趣的读者可以搜索Five balltree construction algorithms来了解详细的算法信息。
    如何使用kd树
    1.建立kd树
    kd树(K-dimension tree)是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。kd树是一种二叉树,表示对k维空间的一个划分,构造kd树相当于不断地用垂直于坐标轴的超平面将K维空间切分,构成一系列的K维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。利用kd树可以省去对大部分数据点的搜索,从而减少搜索的计算量。
    在这里插入图片描述
    2.最近邻域搜索
    在这里插入图片描述
    案例:
    有如下样本:
    T={(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}
    第一步:

    按照x轴数据进行排序:2 4 5 7 8 9
    按照Y轴数据排序 1 2 3 4 6 7

    第二步:

    通过对比得出x轴的数据比Y轴的数据更加离散(方差计算)
    所以选择从X轴的树中找到一个中间数,可以选择(7.2)也可以选择(5.4),这里选择(7.2)

    第三步:

    在这里插入图片描述
    在这里插入图片描述
    做题:
    查找点(2.1,3.1)
    在这里插入图片描述
    查找点(2,4.5)
    在这里插入图片描述
    从二叉树找到4.7为最佳结点,以2,4.5为圆心,到4.7的距离为半径,发现5.4和2.3在圈内

    或者以4.7为最佳结点,回溯到5.4 发现 5.4里面还有一个2.3所以再测试一下2.3 最后对比,发现还是2.3最近

    对比的都是各个结点到2,4.5的半径

    展开全文
  • 笔者是一个痴迷于挖掘数据中的价值的学习人,希望在平日的工作学习中,挖掘数据的价值,找寻数据的秘密,笔者认为,数据的价值不仅仅只体现在企业中,个人也可以体会到数据的魅力,用技术力量探索行为密码,让大数据...

    笔者是一个痴迷于挖掘数据中的价值的学习人,希望在平日的工作学习中,挖掘数据的价值,找寻数据的秘密,笔者认为,数据的价值不仅仅只体现在企业中,个人也可以体会到数据的魅力,用技术力量探索行为密码,让大数据助跑每一个人,欢迎直筒们关注我的公众号,大家一起讨论数据中的那些有趣的事情。

    我的公众号为:livandata

    1)KD树

    kd树(K-dimension tree)是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。kd树是是一种二叉树,表示对k维空间的一个划分,构造kd树相当于不断地用垂直于坐标轴的超平面将K维空间切分,构成一系列的K维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。利用kd树可以省去对大部分数据点的搜索,从而减少搜索的计算量,类似于二分法。

    2) KNN(K近邻算法:根据距离来做排序,距离哪些同类的数据比较近则属于哪一类):

    KNN是通过测量不同特征值之间的距离进行分类。它的思路是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别,其中K通常是不大于20的整数。KNN算法中,所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

    下面通过一个简单的例子说明一下:如下图,绿色圆要被决定赋予哪个类,是红色三角形还是蓝色四方形?如果K=3,由于红色三角形所占比例为2/3,绿色圆将被赋予红色三角形那个类,如果K=5,由于蓝色四方形比例为3/5,因此绿色圆被赋予蓝色四方形类。

     由此也说明了KNN算法的结果很大程度取决于K的选择。

    在KNN中,通过计算对象间距离来作为各个对象之间的非相似性指标,避免了对象之间的匹配问题,在这里距离一般使用欧氏距离或曼哈顿距离:

     

    同时,KNN通过依据k个对象中占优的类别进行决策,而不是单一的对象类别决策。这两点就是KNN算法的优势。

       接下来对KNN算法的思想总结一下:就是在训练集中数据和标签已知的情况下,输入测试数据,将测试数据的特征与训练集中对应的特征进行相互比较,找到训练集中与之最为相似的前K个数据,则该测试数据对应的类别就是K个数据中出现次数最多的那个分类,其算法的描述为:

    1)计算测试数据与各个训练数据之间的距离;

    2)按照距离的递增关系进行排序;

    3)选取距离最小的K个点;

    4)确定前K个点所在类别的出现频率;

    5)返回前K个点中出现频率最高的类别作为测试数据的预测分类。

    其缺陷为对密集度不同的数据之间的度量不准确:

     

    展开全文
  • KNN算法和KD树

    2020-01-15 12:12:28
    一、KNN算法 KNN(k-NearestNeighbor)(邻近算法,或者说K最近邻分类算法)是数据挖掘分类技术中最简单的方法之一。所谓K最近邻,就是k个最近的邻居的意思,说的是每个样本都可以用它最接近的k个邻居来代表。...

    一、KNN算法

    KNN(k-NearestNeighbor)(邻近算法,或者说K最近邻分类算法)是数据挖掘分类技术中最简单的方法之一。所谓K最近邻,就是k个最近的邻居的意思,说的是每个样本都可以用它最接近的k个邻居来代表。

    kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 kNN方法在类别决策时,只与极少量的相邻样本有关。由于kNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,kNN方法较其他方法更为适合。

    所以,KNN算法的主要流程是假定给定一个训练集,其中的实例类别已定,分类时,对新的实例,根据K个最邻近的实例的类别,通过多数表决的方式进行预测,因此,KNN算法不具有显示的学习过程。

    KNN算法流程:

    1. 输入:训练集T={(x1,y1),(x2,y2)...(xm,ym)}T=\left \{(x_1,y_1),(x_2,y_2)...(x_m,y_m) \right \}
    2. 根据给定的距离度量方法,在训练集TT中找到与xx最近邻的K个点,涵盖这K个点的xx的邻域记做Nk(x)N_k(x)
    3. Nk(x)N_k(x)中根据分类决策规则(多数表决)决定xx的类别yy.

    KNN算法的基本要素:

    1. K值的选择: K值得选择一般通过交叉验证选择,当K较小时,模型更复杂,容易发生过拟合现象;K较大时,模型会变得简单,学习的近似误差会增大,估计误差会减小;但是不能取K=m。
    2. 距离度量: 一般使用三种距离度量方式
      闵可夫斯基距离:Lp(xi,xj)=(l=1nxilxjlp)1pL_p(x_i,x_j)=(\sum_{l=1}^{n}|x_i^{l}-x_j^{l}|^p)^{\frac{1}{p}}
      欧氏距离:L2(xi,xj)=(l=1nxilxjl2)12L_2(x_i,x_j)=(\sum_{l=1}^{n}|x_i^{l}-x_j^{l}|^2)^{\frac{1}{2}}
      曼哈顿距离:L1(xi,xj)=(l=1nxilxjl)L_1(x_i,x_j)=(\sum_{l=1}^{n}|x_i^{l}-x_j^{l}|)
    3. 分类决策规则: 多数表决

    KNN优点:

    1. 简单,易于理解,易于实现,无需估计参数,无需训练;
    2. 适合对稀有事件进行分类;
    3. 特别适合于多分类问题(multi-modal,对象具有多个类别标签), kNN比SVM的表现要好。

    KNN缺点:

    1. 当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数。
    2. 计算量较大,因为对每一个待分类的文本都要计算它到全体已知样本的距离,才能求得它的K个最近邻点。
    3. 可理解性差,无法给出像决策树那样的规则。

    二、KD树

    KD树是一种对K维空间中的实例进行存储以便对其进行快速检索的树形数据结构,利用kd树可以省去对大部分数据点的搜索,从而减少搜索的计算量。因此,KD树可有效提高KNN算法的搜索效率。

    构建KD树:
    在这里插入图片描述
    kd 树是每个节点均为k维数值点的二叉树,其上的每个节点代表一个超平面,该超平面垂直于当前划分维度的坐标轴,并在该维度上将空间划分为两部分,一部分在其左子树,另一部分在其右子树。即若当前节点的划分维度为d,其左子树上所有点在d维的坐标值均小于当前值,右子树上所有点在d维的坐标值均大于等于当前值。

    如:集合(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)
    在这里插入图片描述

    1. 构建根节点时,切分维度为x(维度的选择依照方差进行,选择较大方差的维度进行切分,因为更为分散的维度,我们就更容易的将其分开),如上点集合在x维从小到大排序为(2,3),(4,7),(5,4),(7,2),(8,1),(9,6);其中值为(7,2)。(2,4,5,7,8,9在数学中的中值为(5 + 7)/2=6,但因该算法的中值需在点集合之内,所以中值计算用的是 len(points)//2=3, points[3]=(7,2) )
    2. (2,3),(4,7),(5,4)挂在(7,2)节点的左子树,(8,1),(9,6)挂在(7,2)节点的右子树。
    3. 构建(7,2)节点的左子树时,点集合(2,3),(4,7),(5,4)此时的切分维度为y,中值为(5,4)作为分割平面,(2,3)挂在其左子树,(4,7)挂在其右子树。
    4. 构建(7,2)节点的右子树时,点集合(8,1),(9,6)此时的切分维度也为y,中值为(9,6)作为分割平面,(8,1)挂在其左子树。
    5. 至此k-d tree构建完成。

    搜索KD树:
    在这里插入图片描述
    例如:寻找图中目标点的最近邻点
    在这里插入图片描述

    1. 首先假设(4,7)为当前最近邻点,计算其与目标查找点的距离为3.202。回溯到(5,4),计算其与查找点之间的距离为3.041,小于3.202,所以“当前最近邻点”变成(5,4)。
    2. 以目标点(2,4.5)为圆心,以目标点(2,4.5)到“当前最近邻点”(5,4)的距离(即3.041)为半径作圆,如上图所示。可见该圆和y = 4超平面相交,所以需要进入(5,4)左子空间进行查找,即回溯至(2,3)叶子节点。
    3. (2,3)距离(2,4.5)比(5,4)要近,所以“当前最近邻点”更新为(2,3),最近距离更新为1.5。
    4. 回溯至(7,2),以(2,4.5)为圆心1.5为半径作圆,并不和x = 7分割超平面交割。
    5. 至此,搜索路径回溯完。返回最近邻点(2,3),最近距离1.5。
    展开全文
  • 一、 一、

    K最近邻算法链接,点击这里,我们直接来了解有关Kd树的知识点

    一、KD树基本解释

    1.1、基础概念

             特征点匹配和数据库查、图像检索本质上是同一个问题,都可以归结为一个通过距离函数在高维矢量之间进行相似性检索的问题,如何快速而准确地找到查询点的近邻。
             一般说来,索引结构中相似性查询有两种基本的方式:
    ● 一种是范围查询,范围查询时给定查询点和查询距离阈值,从数据集中查找所有与查询点距离小于阈值的数据
    ● 另一种是K近邻查询,就是给定查询点及正整数K,从数据集中找到距离查询点最近的K个数据,当K=1时,它就是最近邻查询。

    同样,针对特征点匹配也有两种方法:

             最容易的办法就是线性扫描,也就是我们常说的穷举搜索,依次计算样本集E中每个样本到输入实例点的距离,然后抽取出计算出来的最小距离的点即为最近邻点。此种办法简单直白,但当样本集或训练集很大时,它的缺点就立马暴露出来了,举个例子,在物体识别的问题中,可能有数千个甚至数万个SIFT特征点,而去计算这成千上万的特征点与输入实例点的距离,明显是不足取的。
             另外一种,就是构建数据索引,因为实际数据一般都会呈现簇状的聚类形态,因此我们想到建立数据索引,然后再进行快速匹配。索引树是一种树结构索引方法,其基本思想是对搜索空间进行层次划分。根据划分的空间是否有混叠可以分为Clipping和Overlapping两种。前者划分空间没有重叠,其代表就是k-d树;后者划分空间相互有交叠,其代表为R树
            如下图形式的把空间划分为多个部分的k-d树。
                            这里写图片描述

    1.2、什么是KD树

            Kd-树就是一种平衡二叉树k-d树是一种空间划分树,说白了,就是把整个空间划分为特定的几个部分,然后在特定空间的部分内进行相关搜索操作。
                                     这里写图片描述

    1.3、KD树的构建

    下表表示的是Kd-树中每个节点中主要包含的数据结构:

    域名 数据类型 描述
    Node-data 数据矢量 数据集中某个数点,是n维矢量(这里也就是k维)
    Range 空间矢量 该节点所代表的空间范围
    split 整数 垂直于分割超平面的方向轴序号
    Left k-d树 由位于该节点分割超平面左子空间内所有数据点所构成的k-d树
    Right k-d树 由位于该节点分割超平面右子空间内所有数据点所构成的k-d树
    parent k-d树 父节点

    ● Range域表示的是节点包含的空间范围。
    ● Node-data域就是数据集中的某一个n维数据点。分割超面是通过数据点Node-Data并垂直于轴
    ● split的平面,分割超面将整个空间分割成两个子空间。
    ● 令split域的值为i,如果空间Range中某个数据点的第i维数据小于Node-Data[i],那么,它就属于该节点空间的左子空间,否则就属于右子空间。
    ● Left,Right域分别表示由左子空间和右子空间空的数据点构成的Kd-树。

    从上面对k-d树节点的数据类型的描述可以看出构建k-d树是一个逐级展开的递归过程。下面的代码构建了kd树,通过前序遍历可以进行验证。

    1.3.1、算法的实现

    输入:数据点集Data-set和其所在的空间Range
    输出:Kd,类型为k-d tree
    1、If Data-set为空,则返回空的k-d tree

    2、调用节点生成程序:
              (1)确定split域:对于所有描述子数据(特征矢量),统计它们在每个维上的数据方差。以SURF特征为例,描述子为64维,可计算64个方差。挑选出最大值,对应的维就是split域的值。数据方差大表明沿该坐标轴方向上的数据分散得比较开,在这个方向上进行数据分割有较好的分辨率;
              (2)确定Node-data域:数据点集Data-set按其第split域的值排序。位于正中间的那个数据点被选为Node-data。此时新的Data-set’ = Data-set\Node-data(除去其中Node-data这一点)。

    3、dataleft = {d属于Data-set’ && d[split] ≤ Node-data[split]}Left_Range = {Range && dataleft} dataright = {d属于Data-set’ && d[split] > Node-data[split]}Right_Range = {Range && dataright}

    4.、eft = 由(dataleft,Left_Range)建立的k-d tree,即递归调用createKDTree(dataleft,Left_Range)。并设置left的parent域为Kd;right = 由(dataright,Right_Range)建立的k-d tree,即调用createKDTree(dataright,Right_Range)。并设置right的parent域为Kd。

    1.3.2、构造代码部分
    # -*- coding: utf-8 -*-
    #from operator import itemgetter
    import sys
    reload(sys)
    sys.setdefaultencoding('utf8')
    
    # kd-tree每个结点中主要包含的数据结构如下 
    class KdNode(object):
        def __init__(self, dom_elt, split, left, right):
            self.dom_elt = dom_elt  # k维向量节点(k维空间中的一个样本点)
            self.split = split      # 整数(进行分割维度的序号)
            self.left = left        # 该结点分割超平面左子空间构成的kd-tree
            self.right = right      # 该结点分割超平面右子空间构成的kd-tree
    
    class KdTree(object):
        def __init__(self, data):
            k = len(data[0])  # 数据维度
    
            def CreateNode(split, data_set): # 按第split维划分数据集exset创建KdNode
                if not data_set:    # 数据集为空
                    return None
                # key参数的值为一个函数,此函数只有一个参数且返回一个值用来进行比较
                # operator模块提供的itemgetter函数用于获取对象的哪些维的数据,参数为需要获取的数据在对象中的序号
                #data_set.sort(key=itemgetter(split)) # 按要进行分割的那一维数据排序
                data_set.sort(key=lambda x: x[split])
                split_pos = len(data_set) // 2      # //为Python中的整数除法
                median = data_set[split_pos]        # 中位数分割点             
                split_next = (split + 1) % k        # cycle coordinates
    
                # 递归的创建kd树
                return KdNode(median, split, 
                              CreateNode(split_next, data_set[:split_pos]),     # 创建左子树
                              CreateNode(split_next, data_set[split_pos + 1:])) # 创建右子树
    
            self.root = CreateNode(0, data)         # 从第0维分量开始构建kd树,返回根节点
    
    # KDTree的前序遍历
    def preorder(root):  
        print root.dom_elt  
        if root.left:      # 节点不为空
            preorder(root.left)  
        if root.right:  
            preorder(root.right)  
    
    if __name__ == "__main__":
        data = [[2,3],[5,4],[9,6],[4,7],[8,1],[7,2]]
        kd = KdTree(data)
        preorder(kd.root)

           再举一个简单直观的实例来介绍k-d树构建算法。假设有6个二维数据点{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)},数据点位于二维空间内,如下图所示。为了能有效的找到最近邻,k-d树采用分而治之的思想,即将整个空间划分为几个小部分,首先,粗黑线将空间一分为二,然后在两个子空间中,细黑直线又将整个空间划分为四部分,最后虚黑直线将这四部分进一步划分。

                                    这里写图片描述

    1.3.2、具体步骤

           1、确定:split域=x。具体是:6个数据点在x,y维度上的数据方差分别为39,28.63,所以在x轴上方差更大,故split域值为x;
           2、确定:Node-data = (7,2)。具体是:根据x维上的值将数据排序,6个数据的中值(所谓中值,即中间大小的值)为7,所以Node-data域位数据点(7,2)。这样,该节点的分割超平面就是通过(7,2)并垂直于:split=x轴的直线x=7;
           3、确定:左子空间和右子空间。具体是:分割超平面x=7将整个空间分为两部分:x<=7的部分为左子空间,包含3个节点={(2,3),(5,4),(4,7)};另一部分为右子空间,包含2个节点={(9,6),(8,1)};

           与此同时,经过对上面所示的空间划分之后,我们可以看出,点(7,2)可以为根结点,从根结点出发的两条红粗斜线指向的(5,4)和(9,6)则为根结点的左右子结点,而(2,3),(4,7)则为(5,4)的左右孩子(通过两条细红斜线相连),最后,(8,1)为(9,6)的左孩子(通过细红斜线相连)。如此,便形成了下面这样一棵k-d树:
                                   这里写图片描述

    二、KD树基本操作

    2.1、KD树查找

    KD树的查找算法:
    在k-d树中进行数据的查找也是特征匹配的重要环节,其目的是检索在k-d树中与查询点距离最近的数据点。 对于kd树的检索,其具体过程为:
            ● 从根节点开始,将待检索的样本划分到对应的区域中(在kd树形结构中,从根节点开始查找,直到叶子节点,将这样的查找序列存储到栈中)


            ● 以栈顶元素与待检索的样本之间的距离作为最短距离min_distance


            ● 执行出栈操作:
                    ◆ 向上回溯,查找到父节点,若父节点与待检索样本之间的距离小于当前的最短距离min_distance,则替换当前的最短距离min_distance



                    ◆ 以待检索的样本为圆心(二维,高维情况下是球心),以min_distance为半径画圆,若圆与父节点所在的平面相割,则需要将父节点的另一棵子树进栈,重新执行以上的出栈操作


            ● 直到栈为

    举例
            以先前构建好的kd树为例,查找目标点(3,4.5)的最近邻点。同样先进行二叉查找,先从(7,2)查找到(5,4)节点,在进行查找时是由y = 4为分割超平面的,由于查找点为y值为4.5,因此进入右子空间查找到(4,7),形成搜索路径:(7,2)→(5,4)→(4,7),取(4,7)为当前最近邻点。以目标查找点为圆心,目标查找点到当前最近点的距离2.69为半径确定一个红色的圆。然后回溯到(5,4),计算其与查找点之间的距离为2.06,则该结点比当前最近点距目标点更近,以(5,4)为当前最近点。用同样的方法再次确定一个绿色的圆,可见该圆和y = 4超平面相交,所以需要进入(5,4)结点的另一个子空间进行查找。(2,3)结点与目标点距离为1.8,比当前最近点要更近,所以最近邻点更新为(2,3),最近距离更新为1.8,同样可以确定一个蓝色的圆。接着根据规则回退到根结点(7,2),蓝色圆与x=7的超平面不相交,因此不用进入(7,2)的右子空间进行查找。至此,搜索路径回溯完,返回最近邻点(2,3),最近距离1.8。

               这里写图片描述
    如果实例点是随机分布的,kd树搜索的平均计算复杂度是O(logN)O(logN),这里N是训练实例数。kd树更适用于训练实例数远大于空间维数时的k近邻搜索。当空间维数接近训练实例数时,它的效率会迅速下降,几乎接近线性扫描。

    2.2、查找代码实现

    from math import sqrt
    from collections import namedtuple
    # 定义一个namedtuple,分别存放最近坐标点、最近距离和访问过的节点数
    result = namedtuple("Result_tuple", "nearest_point  nearest_dist  nodes_visited")
    
    def find_nearest(tree, point):
        k = len(point) # 数据维度
        def travel(kd_node, target, max_dist):
            if kd_node is None:     
                return result([0] * k, float("inf"), 0) # python中用float("inf")和float("-inf")表示正负无穷
    
            nodes_visited = 1
    
            s = kd_node.split        # 进行分割的维度
            pivot = kd_node.dom_elt  # 进行分割的“轴”
    
            if target[s] <= pivot[s]:           # 如果目标点第s维小于分割轴的对应值(目标离左子树更近)
                nearer_node  = kd_node.left     # 下一个访问节点为左子树根节点
                further_node = kd_node.right    # 同时记录下右子树
            else:                               # 目标离右子树更近
                nearer_node  = kd_node.right    # 下一个访问节点为右子树根节点
                further_node = kd_node.left
    
            temp1 = travel(nearer_node, target, max_dist)  # 进行遍历找到包含目标点的区域
    
            nearest = temp1.nearest_point       # 以此叶结点作为“当前最近点”
            dist = temp1.nearest_dist           # 更新最近距离
    
            nodes_visited += temp1.nodes_visited  
    
            if dist < max_dist:     
                max_dist = dist    # 最近点将在以目标点为球心,max_dist为半径的超球体内
    
            temp_dist = abs(pivot[s] - target[s])    # 第s维上目标点与分割超平面的距离
            if  max_dist < temp_dist:                # 判断超球体是否与超平面相交
                return result(nearest, dist, nodes_visited) # 不相交则可以直接返回,不用继续判断
    
            #----------------------------------------------------------------------  
            # 计算目标点与分割点的欧氏距离  
            temp_dist = sqrt(sum((p1 - p2) ** 2 for p1, p2 in zip(pivot, target)))     
    
            if temp_dist < dist:         # 如果“更近”
                nearest = pivot          # 更新最近点
                dist = temp_dist         # 更新最近距离
                max_dist = dist          # 更新超球体半径
    
            # 检查另一个子结点对应的区域是否有更近的点
            temp2 = travel(further_node, target, max_dist) 
    
            nodes_visited += temp2.nodes_visited
            if temp2.nearest_dist < dist:        # 如果另一个子结点内存在更近距离
                nearest = temp2.nearest_point    # 更新最近点
                dist = temp2.nearest_dist        # 更新最近距离
    
            return result(nearest, dist, nodes_visited)
    
        return travel(tree.root, point, float("inf"))  # 从根节点开始递归

    2.3、KD树的插入

            元素插入到一个K-D树的方法和二叉检索树类似。本质上,在偶数层比较x坐标值,而在奇数层比较y坐标值。当我们到达了树的底部,(也就是当一个空指针出现),我们也就找到了结点将要插入的位置。生成的K-D树的形状依赖于结点插入时的顺序。给定N个点,其中一个结点插入和检索的平均代价是O(log2N)。
    这里写图片描述
            应该清楚,这里描述的插入过程中,每个结点将其所在的平面分割成两部分。因比,Chicago 将平面上所有结点分成两部分,一部分所有的结点x坐标值小于35,另一部分结点的x坐标值大于或等于35。同样Mobile将所有x坐标值大于35的结点以分成两部分,一部分结点的Y坐标值是小于10,另一部分结点的Y坐标值大于或等于10。后面的Toronto、Buffalo也按照一分为二的规则继续划分。

    2.4、KD树的删除

             KD树的删除可以用递归程序来实现。我们假设希望从K-D树中删除结点(a,b)。如果(a,b)的两个子树都为空,则用空树来代替(a,b)。否则,在(a,b)的子树中寻找一个合适的结点来代替它,譬如(c,d),则递归地从K-D树中删除(c,d)。一旦(c,d)已经被删除,则用(c,d)代替(a,b)。假设(a,b)是一个X识别器,那么,它得替代节点要么是(a,b)左子树中的X坐标最大值的结点,要么是(a,b)右子树中x坐标最小值的结点。
            具体操作如下:
    这里写图片描述

            从一个K-D树中删除结点(a,b)的问题变成了在(a,b)的子树中寻找x坐标为最小的结点。不幸的是寻找最小x坐标值的结点比二叉检索树中解决类似的问题要复杂得多。特别是虽然最小x坐标值的结点一定在x识别器的左子树中,但它同样可在y识别器的两个子树中。因此关系到检索,且必须注意检索坐标,以使在每个奇数层仅检索2个子树中的一个。
            从K-D树中删除一个结点是代价很高的,很清楚删除子树的根受到子树中结点个数的限制。用TPL(T)表示树T总的路径长度。可看出树中子树大小的总和为TPL(T)+N。 以随机方式插入N个点形成树的TPL是O(N*log2N),这就意味着从一个随机形成的K-D树中删除一个随机选取的结点平均代价的上界是O(log2N) 。

    最终结果如下:
    这里写图片描述

    三、算法改进:BBF

    我们在回顾一下KD树的算法过程

    算法步骤如下:
           ● 从根节点开始,将待检索的样本划分到对应的区域中(在kd树形结构中,从根节点开始查找,直到叶子节点,将这样的查找序列存储到栈中)
           ● 以栈顶元素与待检索的样本之间的距离作为最短距离min_distance
           ● 执行出栈操作:
                  ◆ 向上回溯,查找到父节点,若父节点与待检索样本之间的距离小于当前的最短距离min_distance,则替换当前的最短距离min_distance
                  ◆ 以待检索的样本为圆心(二维,高维情况下是球心),以min_distance为半径画圆,若圆与父节点所在的平面相割,则需要将父节点的另一棵子树进栈,重新执行以上的出栈操作
           ● 直到栈为空
            当回退到根结点时,搜索结束,最后的“当前最近点”即为x 的最近邻点。

            如果实例点是随机分布的,那么kd树搜索的平均计算复杂度是O(NlogN),这里的N是训练实例树。所以说,kd树更适用于训练实例数远大于空间维数时的k近邻搜索,当空间维数接近训练实例数时,它的效率会迅速下降,一降降到“解放前”:线性扫描的速度。
            从上述标准的kd树查询过程可以看出其搜索过程中的“回溯”是由“查询路径”决定的,并没有考虑查询路径上一些数据点本身的一些性质。一个简单的改进思路就是将“查询路径”上的结点进行排序,如按各自分割超平面(也称bin)与查询点的距离排序,也就是说,回溯检查总是从优先级最高(Best Bin)的树结点开始。

    具体步骤和思路如下:

    ● 在某一层,分割面是第ki维,分割值是kv,那么 abs(q[ki]-kv) 就是没有选择的那个分支的优先级,也就是计算的是那一维上的距离;
    ● 同时,从优先队列里面取节点只在某次搜索到叶节点后才发生,计算过距离的节点不会出现在队列的,比如1~10这10个节点,你第一次搜索到叶节点的路径是1-5-7,那么1,5,7是不会出现在优先队列的。换句话说,优先队列里面存的都是查询路径上节点对应的相反子节点,比如:
            搜索左子树,就把对应这一层的右节点存进队列。
            此算法能确保优先检索包含最近邻点可能性较高的空间,此外,BBF机制还设置了一个运行超时限定。采用了BBF查询机制后,kd树便可以有效的扩展到高维数据集上

    事例
            1、将(7,2)压人优先队列中;
            2、提取优先队列中的(7,2),由于(2,4.5)位于(7,2)分割超平面的左侧,所以检索其左子结点(5,4)。同时,根据BBF机制”搜索左/右子树,就把对应这一层的兄弟结点即右/左结点存进队列”,将其(5,4)对应的兄弟结点即右子结点(9,6)压人优先队列中,此时优先队列为{(9,6)},最佳点为(7,2);然后一直检索到叶子结点(4,7),此时优先队列为{(2,3),(9,6)},“最佳点”则为(5,4);
            3、提取优先级最高的结点(2,3),重复步骤2,直到优先队列为空。
    这里写图片描述

    四、VP树与MVP树简介

          高维特征向量的距离索引问题是基于内容的图像检索的一项关键技术,目前经常采用的解决办法是首先对高维特征空间做降维处理,然后采用包括四叉树、kd树、R树族等在内的主流多维索引结构,这种方法的出发点是:目前的主流多维索引结构在处理维数较低的情况时具有比较好的效率,但对于维数很高的情况则显得力不从心(即所谓的维数危机) 。

          实验结果表明当特征空间的维数超过20 的时候,效率明显降低,而可视化特征往往采用高维向量描述,一般情况下可以达到10^2的量级,甚至更高。在表示图像可视化特征的高维向量中各维信息的重要程度是不同的,通过降维技术去除属于次要信息的特征向量以及相关性较强的特征向量,从而降低特征空间的维数,这种方法已经得到了一些实际应用。

          然而这种方法存在不足之处采用降维技术可能会导致有效信息的损失,尤其不适合于处理特征空间中的特征向量相关性很小的情况。另外主流的多维索引结构大都针对欧氏空间,设计需要利用到欧氏空间的几何性质,而图像的相似性计算很可能不限于基于欧氏距离。这种情况下人们越来越关注基于距离的度量空间高维索引结构可以直接应用于高维向量相似性查询问题。

    ⊙拓展:二叉排序树,点击这里

    展开全文
  • kd树实现k近邻时当训练数据量较大时,采用线性扫描法(将数据集中的数据与查询点逐个计算距离比对)会导致计算量大效率低下.这时可以利用数据本身蕴含的结构信息,构造数据索引进行快速匹配.索引树便是其中常用的一...
  • 机器学习kd

    2019-11-01 20:29:09
    参考自:...mid=2247483793&idx=1&sn=d42f4f06225cd1f792912dfecdc800ea&chksm=ebb43945dcc3b0538ba10187c999a050137b96a05f402b9fe99f0a972d7ba0bce50...
  • kd树个人理解--基础、通俗!
  • 机器学习总结之——KD树小白理解   KD树是k-dimension树的简称。KD树是一种树形的数据结构,目的是为了提高数据查找的效率。可以把KD树类比为一维的折半查找,只不过它是针对多维数据的。一维折半查找需要把数据...
  • 文章目录1.5 kd树学习目标1 kd树简介1.1 什么是kd树1.2 原理2 构造方法3 案例分析3.1 树的建立3.2 最近领域的搜索3.2.1 查找点(2.1,3.1)3.2.2 查找点(2,4.5)4 总结 1.5 kd树 学习目标 目标 知道kd树构建和搜索过程...
  • 今天是机器学习的第15篇文章,之前的文章当中讲了Kmeans的相关优化,还讲了大名鼎鼎的EM算法。有些小伙伴表示喜欢看这些硬核的,于是今天上点硬菜,我们来看一个机器学习领域经常用到的数据结构——KD-Tree。 从...
  • 引用博客:https://www.cnblogs.com/eyeszjwang/articles/2429382.html1. Kd树的构建:《统计学习方法》第三章2. kd树的最临近搜索方法: 树的效果显示为: 在k-d树中进行数据的查找也是特征匹配的重要环节,其...
  • C++实现K最邻近算法, 使用KD树来实现, 在面对大量数据时可以提高搜索效率. 代码干净, 整洁, 有注释, 可直接使用.
  • k近邻可以算是机器学习中易于理解、实现的一个算法了,《机器学习实战》的第一章便是以它作为介绍来入门。而k近邻的算法可以简述为通过遍历数据集的每个样本进行距离测量,并找出距离最小的k个点。但是这样一来一旦...
  • kd树kd树简介构造平衡kd树算法原理kd树代码实现案例地址 kd树简介 kdkdkd树是一种对kkk维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。 kdkdkd树构造方法: 构造根结点 使根结点对应于kkk维空间中...
  • 机器学习 KNN、KD树、偏差 and 方差 KNN 算法步骤 距离度量 K 的选取 多数表决规则 KNN 特点 KD 树 偏差与方差
  • 之前blog内曾经介绍过SIFT特征匹配算法,特征点匹配和数据库查、图像检索本质上是同一个问题,都可以归结为一个通过距离函数在高维矢量之间进行相似性检索的问题,如何快速而准确地找到查询点的近邻,不少人提出了很...
  • Kd树的具体实现

    2020-04-26 19:16:28
    Kd树的实现pythonKd树的原理李航的统计学习方法介绍的Kd树网上大部分创建Kd树的思路Kd树的实现sklearn 库中的iris作为本次实验数据集python实现 Kd树的原理 李航的统计学习方法介绍的Kd树 输入:m维空间数据集S={x1,...
  • 在做毕业设计的时候,遇到这样一个需求: 给定一万五千个点,再给定一个目标点...kd树的原理在李航的《机器学习》书籍中有详细的介绍,包括kd树的构建和kd树的搜索,但是李航的书里面只有kd树搜索最近邻 关于原理...
  • 物以类聚、人以群分 KNN算法主要是通过K个最近样本的类型判断当前样本的...由于算法简单且分类精度较高,在实际当中也有一定的应用,也是入门机器学习的一个比较典型的算法。 很多人会把它跟K-Means算法混淆,因...
  • python+sklearn实现KNN及KD树算法 from sklearn import datasets# 导入内置数据集模块 from sklearn.neighbors import KNeighborsClassifier# 导入sklearn.neighbors模块中KNN类 import numpy as np from sklearn....
1 2 3 4 5 ... 20
收藏数 3,008
精华内容 1,203
关键字:

kd树 机器学习