2018-09-29 11:36:45 weixin_42715356 阅读数 313

机器学习总结之——KD树小白理解

  KD树是k-dimension树的简称。KD树是一种树形的数据结构,目的是为了提高数据查找的效率。可以把KD树类比为一维的折半查找,只不过它是针对多维数据的。一维折半查找需要把数据先排序,做成查找表,或是做成二叉查找树,即每个节点左子树均小于节点值,而右子树均大于节点值。对多维的情况下,就需要构造KD树了。

小白理解:KD树就是一棵二叉树的变形,它是将二叉树对数据集进行划分从一维拓广到K维。对K维数据集进行子节点的划分,KD树主要进行如下处理:
(1)选择维度:因为KD树所划分的数据是K维的,KD对于K维数据的处理就是从K维中选择其中一个维度作为划分的依据,并将该维度记录在节点里面(方便后续的数据查找)。选择的方式有:

  • 按顺序依次选,比如对于三维数据(X,Y,Z)先选X维,后Y维再到Z维然后又选X维依次循环;
  • 计算在该父节点内各个维度数据的方差,选择方差最大的维度(属性)作为划分的维度。

(2)选择分割值:维度选好了,还需要根据这个维度选择一个分割值将父节点内数据划分入左右节点,KD的处理方式是根据该维度(属性)的值,先将数据排好序,然后取中间的那个数据作为父节点,比处于中间数据左边的数据划入该父节点的左子树、处于中间数据右边的数据划入该父节点的右子树。

(3)对每一颗非叶子节点的子树重复上述过程,直至生成完整一棵二叉树为止。

PS:选择分割值时取中间值作为父节点的目的是为了保证所生成的二叉树是平衡的,因为左右节点所包含的数据数量是一样的(严格来说当父节点共有偶数个数据时,左子树会出现比右子树大1);

相关树:ball-tree(在子节点划分方式上不同,利用球形计算,适合于高维度)

2018-12-16 18:01:01 qq_35946969 阅读数 54

上一节结束了线性回归、逻辑回归,今天一节来介绍机器学习中最简单的算法:  

 K近邻(KNN,全称K-nearst Neighbor)

      概述:判断一个样本的label只需要判断该样本周围其他样本的label。简言之,朋友选啥我选啥。

      具体实现

          对于特征为X(X可以是多个),样本为y的训练集,当我们需要预测的时候,直接将需要预测的目标样本yi拿过来,在训练集中遍历,寻找与目标样本yi的特征Xi距离相近的点(距离相近的意思可以是欧几里的距离,也可以是其他,距离的大小由我们人为规定)。

         找到我们距离相近的点(可能是多个,这个点要多少由我们认为规定。这些点被称为近邻点)之后:

         如果是分类问题,那么就对这些点的label进行投票法(就是选数量最多的那个类别)或者加权投票法(把距离的倒数作为权值,加权求和)。

         如果是回归问题,就对这些点的label求平均值,或者加权平均值作为目标样本的结果。

       调参(需要我们给定的参数)

         (1)、K值,即判断样本需要几个近邻点。过大容易欠拟合,过小容易过拟合。

        (2)、距离的度量:一般使用欧几里的距离。

        (3)、决策规则:使用投票法、平均法,还是加权投票法、加权平均法。

KD树

  按照上面的思路,在训练集中遍历寻找近邻点的方法叫做暴力搜索,显然这种暴力搜索的开销是极其巨大的,每一次预测都要遍历整个训练集,在数据集较大的时候我们采用另一种方法来寻找近邻点,那就是KD树。

  构建KD树:

      对于具有两个特征值X1和X2的样本,计算样本中两个特征的方差,对方差大的特征取中位数,将中位数作为根结点的判断条件,小于中位数的放在左子树,大于中位数的放在右子树。

      对左、右子树进行同样的操作,如:在左子树的样本中,计算两个特征的方差,对方差大的特征取中位数,将中位数作为根结点的判断条件……

    如此循环,直到样本点分完,KD树构建完成。

   以上是对于两个特征,N个特征的时候也是一样的。

 

  如何预测?

     第一步,在KD树中找到包含目标点的叶子节点。

     第二步,以目标点为圆心,以目标点到这个叶子节点的的距离为半径,画图,最近邻点一定在这个圆里面。(对于对于多个特征,这里就是超球体了)。

      第三步,找到这个叶子节点的父节点A,检查该父节点A的另一子树的所有结点构成的超矩形体是否和超球体有相交(就是另一子树的结点是否有结点落在这个圆、超球体里面,相交就可能有),若相交,遍历此节点下是否有更加近的近邻点,有就更新。

     第四步,若没有,就返回第三步中说的的父节点A的父节点B,对B进行第三步中的操作,检查是否有相交,是否有更近的近邻点。

  下图为一个二维特征的KD树预测过程,x,y轴分别为两个特征属性。

  

 

 

       

2017-10-04 14:44:29 qq_33267669 阅读数 334

概述

k近邻法不具有显式的学习过程,实际上是利用训练数据集对特征向量空间进行划分,并作为其分类的模型。
k值的选择, 距离度量分类决策规则是k近邻算法的三个基本要素。

简单描述为:给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最近邻的k个实例,这k个实例的多数属于某个类,就把该输入实例分为这个类。其中,当k=1时为最近邻搜索,即找到该输入实例在训练数据集中的最近实例;k>1时是范围搜索;以上描述的分类决策规则为多数表决,即由输入实例的k个近邻的训练实例中的多数类决定输入实例的类;距离度量一般采用欧式距离。
图解k近邻
图中绿色圆点即为新的输入实例,其余点为训练数据,其中共有两个分类,分别为蓝色和红色。现在要给新的绿色实例分配类别,k近邻的思想是选择与新实例最近的k个实例,这k个实例中的多数类别作为新实例的类别。当k为1,2,3时,类别为红色实例对应的类别;当k为5时,选择最近的5个实例,其中3个为蓝色,2个为红色,那么新的输入实例的类别就是蓝色。由此可见k值的选择会影响分类结果,同时新输入实例与训练数据实例点之间的距离计算距离的度量规则也是k近邻算法的关键。

k值的选择

如果k值较小,就相当于用较小的邻域中的训练实例进行预测,只有与输入实例较近的训练实例才会对预测结果起作用,预测结果会对近邻的实例点非常敏感,意味着整体模型变得复杂,容易发生过拟合。(过拟合:一味追求提高对训练数据的预测能力,所选择的模型复杂度往往比真实模型更高,指学习时选择的模型包含的参数过多,以致于这一模型对已知数据(训练数据)预测的很好,而对未知数据预测的很差)
如果k值较大,则相当于用较大邻域中的训练实例进行预测,这时与训练实例较远的训练实例也会对预测起作用,k值增大意味着整体模型变的简单。
实际应用中,k值一般取一个比较小的数据(不超过20),然后根据训练结果选择最优值。

距离度量

两个实例点的距离是两个实例点相似程度的反映。
Lp距离的定义如下:

Lp(xi,xj)=[l=1nxlixljp]1p

$L_p距离$
当p=2时,称为欧式距离,即
L2(xi,xj)=[l=1nxlixlj2]12

当p=1时,称为曼哈顿距离,即
L1(xi,xj)=l=1nxlixlj

曼哈顿距离又称城市街角距离,图中(12, 12)点对应的曼哈顿距离为1,它是各坐标轴绝对轴距之和。(想象为从街角一头走到另一个街角,不能直穿大楼,走过的距离为城市街角距离)
当p=时,它是各个距离坐标的最大值。
我们一般使用p=2时的欧式距离;k=1是k近邻法的特殊情况,称为最近邻算法,对于输入实例点(特征向量)x,最近邻法将训练数据集中与x最近点的类作为特征向量x的类。

决策规则

一般使用多数表决,即由输入实例的k个近邻的训练实例中的多数类决定输入实例的类。

k近邻算法

输入:训练数据集T,实例特征向量x
输出:实例x所属类别y

  1. 根据给定的距离度量,在训练集T中找出与x最近邻的k个点,涵盖着k个点的x的邻域记作Nk(x)
  2. Nk(x)中根据分类决策规则决定x的类别y

实现k近邻算法

针对k近邻的特征点匹配有两种方法:
最容易的是线性扫描,依次计算样本集合中每个样本到输入实例点之间的距离,按距离排序,选择k个样本,这k个样本中的多数对应的类别作为新的输入实例的类别。这种方法需要计算所有样本点与新输入实例点的距离,当训练数据很大时,非常耗时,不可取。
另一种是构建数据索引,然后进行快速匹配,索引树是一种树结构索引方法,基本思想是对搜索空间进行层次划分,以减少计算距离的次数。具体方法很多,本文介绍kd树方法。

线性扫描法

数据集来源于《机器学习实战》“使用k近邻算法改进约会网站的配对效果”,数据集下载链接: https://pan.baidu.com/s/1boAADC7 密码: me77
数据描述:共四列数据,分别代表每年获得的飞行常客里程数、每周消费的冰淇淋公升数、玩视频游戏所耗的时间百分比,最后一列为该实例对应的类别,分别为不喜欢、魅力一般、极具魅力。(我想不通男人的魅力和冰淇淋有啥关系)

数据导入

import numpy as np
from operator import itemgetter

def get_train_data(filename):
    return np.array([label.strip().split() for label in open(filename)])

# 将数据以字符串类型读入numpy数组
train_data = get_train_data('datingTestSet.txt')
# 提取训练数据及对应的类别
train_data, labels = train_data[:,:3].astype(float), train_data[:,3]
# 将类别转化为数值类型,每个数值代表一个类别
index_labels = list(set(labels))
labels = [index_labels.index(label) for label in labels.tolist()]

特征值归一化

输出训练数据集train_data为:

array([['40920', '8.326976', '0.953952', 'largeDoses'],
       ['14488', '7.153469', '1.673904', 'smallDoses'],
       ['26052', '1.441871', '0.805124', 'didntLike'],
       ..., 
       ['26575', '10.650102', '0.866627', 'largeDoses'],
       ['48111', '9.134528', '0.728045', 'largeDoses'],
       ['43757', '7.882601', '1.332446', 'largeDoses']], 
      dtype='|S10')

第一列是每年的飞行常客里程数,采用欧式距离度量方法计算两个实例点之间的距离时,差值最大的飞行常客里程数对计算结果的影响最大:

(4092014488)2+(8.3269767.153469)2+(0.9539521.673904)2

而这三种特征是同样重要的,因此我们采用以下公式将任意取值范围的特征值全部转化为0到1之间的值:
new_value = (old_value - min) / (max - min)

def autoNorm(dataSet):
    min_value = dataSet.min(0) # 0代表axis=0,获取每列最小值
    max_value = dataSet.max(0)
    ranges = max_value - min_value
    m = dataSet.shape[0]
    norm_dataSet = dataSet - np.tile(min_value, (m, 1)) # np.tile()复制第一个参数为第二个参数给出的形状
    norm_dataSet /= np.tile(ranges, (m, 1)) # numpy的/代表矩阵对应元素相除
    return norm_dataSet, ranges, min_value

获得归一化后的数据集:

norm_mat, ranges, min_value = autoNorm(train_data)

输出norm_mat如下所示:

array([[ 0.44832535,  0.39805139,  0.56233353],
       [ 0.15873259,  0.34195467,  0.98724416],
       [ 0.28542943,  0.06892523,  0.47449629],
       ..., 
       [ 0.29115949,  0.50910294,  0.51079493],
       [ 0.52711097,  0.43665451,  0.4290048 ],
       [ 0.47940793,  0.3768091 ,  0.78571804]])

分类

# inX: 被分类的输入向量
# labels:数据集中每个样本的分类,和dataSet对应
# k: 选择最近邻个数
def classify0(inX, dataSet, labels, k):
    # 计算当前输入向量与训练集中所有点之间的距离, 并按距离依次排序
    diff_mat = np.tile(inX, (dataSet.shape[0], 1)) - dataSet
    distances = ((diff_mat**2).sum(axis=1))**0.5
    sorted_distances_index = distances.argsort() # 从小到大排序, 返回数组对应值的索引
    # 选取k个点
    class_count = {}
    for i in range(k):
        vote_label = labels[sorted_distances_index[i]]
        class_count[vote_label] = class_count.get(vote_label, 0) + 1
    # 确定前k个点的对应类别出现频率, 并按频率排序
    sorted_class_count = sorted(class_count.items(), key=itemgetter(1), reverse=True)
    # 返回最近的k个实例中出现次数最多的类别
    return sorted_class_count[0][0]

测试

测试上述分类器的准确率:

def datingClassTest(norm_data_set, labels):
    # 选取训练集个数的10%作为测试数据,其余90%作为已知样本点
    num_test_vecs = int(norm_data_set.shape[0] * 0.1)
    error_count = 0
    for i in range(num_test_vecs):
        classifier_result = classify0(norm_data_set[i,:], norm_data_set[num_test_vecs:, :], labels, 3)
        if classifier_result != labels[i]: error_count += 1
    return float(error_count) / num_test_vecs

测试结果为0.7

kd树法

kd树是二叉树,表示对k维空间的一个划分,构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分,构成一系列的k维超矩形区域。

kd树就是把整个空间划分为特定的几个部分,然后在特定空间的部分内进行相关搜索操作。通常依次选择坐标轴对空间进行切分,选择训练实例点在选定坐标轴上的中位数为切分点,这样得到的kd树是平衡的,但平衡kd树的搜索效率未必是最优的。

构建kd树

输入:k维空间数据集T
输出:kd树
以数据集T={(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)}为例构造平衡kd树。
划分空间为:
特征空间划分

首先选择切分坐标轴,计算数据集所有维度上的方差,选择最大值所在维度为split域,6个实例点在x0x1维度上的方差分别为39,28.63,因此split域为x0。(数据方差最大表明沿坐标轴方向上数据点分散的比较开,这个方向上进行数据分割可以获得最好的分辨率)。x0轴上的中位数为7,x=7的超平面将数据集划分为两部分,x0<7作为根结点(7,2)的左子树,其余为右子树。
接着再次选择切分坐标轴xbb=(split + 1) % k,当前split为0,k代表数据维度,此处为2,因此选择x1作为切分坐标轴,x1=4将左矩形划分为两个子矩形;x1=6将右矩形划分为两个子矩形。
再次选择切分坐标轴xb时,b=(1+1)%2=0,切分坐标轴为x0
如此递归得到如下所示kd树:
kd树实例
树结点:

class KDNode(object):
    def __init__(self, dom_elt, split, left_node, right_node):
        self.dom_elt = dom_elt # 保存结点数据
        self.split = split # 进行分割的维度
        self.left_node = left_node
        self.right_node = right_node

构造kd树:

class KDTree(object):

    def __init__(self, data_set):
        # 取数据维度
        k = data_set.shape[1]

        def create_node(split, data_set):
            if data_set.shape[0] == 0: return None
            # 按某列排序,并返回排序后原数组的索引
            sorted_index = np.argsort(data_set[:,split], axis=0)
            new_data_set = data_set[sorted_index]
            # 取中位数所在索引
            split_index = new_data_set.shape[0] // 2 # //为整除
            median_data = new_data_set[split_index]
            next_split = (split + 1) % k # 选择切分坐标轴
            return KDNode(median_data, split, create_node(next_split, new_data_set[:split_index]), create_node(next_split, new_data_set[split_index + 1:]))

        # 确定初始split域
        # 计算每个维度的数据的方差
        var_result = np.var(data_set, axis=0)
        split_num = list(var_result).index(var_result.max())
        self.root_node = create_node(split_num, data_set)

kd树的最近邻搜索

利用kd树可以省去大部分数据点的搜索,这里以最近邻(k=1)为例,同样的方法可以应用到k近邻范围搜索。
输入:已构造的kd树,目标点x
输出:x的最近邻

  1. 找出包含目标点x的叶结点:从根结点出发,递归地向下访问,若目标点x当前维的坐标小于被访问结点的切分点的坐标,则移动到左子结点,否则移动到右子结点,直到叶结点,以此叶结点为当前最近点
  2. 从叶结点开始递归地向上回退,在每个结点处进行以下操作:
    a. 若该实例点比当前最近点与目标点的距离更近,则以该实例点为当前最近点
    b. 检查该结点的另一子结点对应的区域是否与以目标点为球心、以目标点与当前最近点之间的距离为半径的超球体相交。若相交,则移动到另一子结点递归进行最近邻搜索;若不相交则向上回退。
  3. 回退到根结点时,搜索结束,当前最近点为目标点x的最近邻点。

根据上述构造的kd树,给定目标点(3, 4.5),搜索目标点的最近邻。

寻找目标点(3, 4.5)的最近邻,首先从根结点(7, 2)出发,切分坐标轴为x0,3<7,移动到左子结点(5, 4),切分坐标轴为x1,4.5>4,移动到右子结点(4, 7),该结点为包含目标点的叶结点,以该叶结点为当前最近点,目标点的最近邻一定在以目标点为中心并通过当前最近点的超球体内部
然后从叶结点出发,返回当前结点的父结点(5, 4):
该父结点比当前最近点(4, 7)更接近目标点,因此更新当前最近点为(5, 4);该父结点的另一子结点(2, 3)对应的区域与以目标点为中心、以当前最近点与目标点的距离为半径的超球体相交,移动到子结点(2 ,3)。
实例点(2, 3)比当前最近点(5, 4)距离目标点更近,更新当前最近点为(2, 3),该结点不存在子结点,因此向上回退到根结点(7, 2)。
根结点不比当前最近点距离目标点更近;且根结点的另一子结点(9, 6)对应的区域不与以目标点为中心、以目标点与当前最近点(2, 3)的距离为半径的超球体相交。回溯结束,返回当前最近点(2, 3)。
另外,(2, 3)与绿色超球体相交、(9, 6)不与蓝色超球体相交的依据是:
实例点(2, 3)的切分坐标轴为xo,由图可知x0=2的超平面与绿色超球体相交;而实例点(9, 6)的切分坐标轴为x1x1=6的超平面与蓝色超球体不相交。

from collections import namedtuple

class KDNode(object):
    def __init__(self, dom_elt, split, left_node, right_node):
        self.dom_elt = dom_elt # 保存结点数据
        self.split = split # 进行分割的维度
        self.left_node = left_node
        self.right_node = right_node

find_result = namedtuple('Result_tuple', 'nearest_point nearest_dist nodes_visited')

class KDTree(object):

    def __init__(self, data_set):
        # 取数据维度
        k = data_set.shape[1]

        def create_node(split, data_set):
            if data_set.shape[0] == 0: return None
            # 按某列排序,并返回排序后原数组的索引
            sorted_index = np.argsort(data_set[:,split], axis=0)
            new_data_set = data_set[sorted_index]
            # 取中位数所在索引
            split_index = new_data_set.shape[0] // 2
            median_data = new_data_set[split_index]
            next_split = (split + 1) % k
            return KDNode(median_data, split, create_node(next_split, new_data_set[:split_index]), create_node(next_split, new_data_set[split_index + 1:]))

        # 确定split域
        var_result = np.var(data_set, axis=0)
        split_num = list(var_result).index(var_result.max())
        self.root_node = create_node(split_num, data_set)


    # KD树的最近邻搜索 (k=1)
    def find(self, target_point):
        # 取数据维度 (不同于k近邻的k)
        k = len(target_point)

        def travel(kd_node, target_point, min_dist):
            if kd_node is None: return find_result([0]*k, float('inf'), 0)            
            # 找到叶结点
            nodes_visited = 1
            split = kd_node.split # 进行分割的维度
            pivot = kd_node.dom_elt # 当前结点的数据
            if target_point[split] <= pivot[split]: 
                nearer_node = kd_node.left_node
                further_node = kd_node.right_node
            else:
                nearer_node = kd_node.right_node
                further_node = kd_node.left_node
            # 从叶结点回退,直到根结点
            nearest_point, nearest_dist, return_visited1 = travel(nearer_node, target_point, min_dist)
            nodes_visited += return_visited1
            if nearest_dist < min_dist:
                min_dist = nearest_dist
            if min_dist < abs(pivot[split] - target_point[split]): # 超球体与超平面是否相交
                return find_result(nearest_point, nearest_dist, nodes_visited) # 不相交直接向上回退
            # 相交则转到另一子结点
            temp_dist = np.sqrt(np.sum((pivot - target_point)**2)) # 计算欧式距离
            if temp_dist < nearest_dist:
                nearest_point = pivot
                nearest_dist = temp_dist
                min_dist = temp_dist
            # 检查另一个子结点是否为更近的点
            nearest_point2, nearest_dist2, return_visited2 =travel(further_node, target_point, min_dist)
            nodes_visited += return_visited2
            if nearest_dist2 < temp_dist:
                nearest_point = nearest_point2
                nearest_dist = nearest_dist2
            return find_result(nearest_point, nearest_dist, nodes_visited)
        return travel(self.root_node, target_point, float('inf'))

构造kd树并执行最近邻搜索:

kdtree =KDTree(np.array([[2,3], [5,4], [9,6], [4,7], [8,1], [7,2]]))
kdtree.find(np.array([3, 4.5]))

输出如下:

Result_tuple(nearest_point=array([2, 3]), nearst_dist=1.8027756377319946, nodes_visited=4)

参考文章:
http://www.cnblogs.com/21207-iHome/p/6084670.html
http://blog.csdn.net/likika2012/article/details/39619687

2019-04-29 12:25:40 singularity1980 阅读数 39

为什么要使用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的半径

2019-10-31 23:18:37 qq_42185999 阅读数 20

参考自:https://mp.weixin.qq.com/s?__biz=MzI4MDYzNzg4Mw==&mid=2247483793&idx=1&sn=d42f4f06225cd1f792912dfecdc800ea&chksm=ebb43945dcc3b0538ba10187c999a050137b96a05f402b9fe99f0a972d7ba0bce5067bf7efb3&mpshare=1&scene=23&srcid=1029EnTdXfHf4b45SihbuUI5&sharer_sharetime=1572360664183&sharer_shareid=d8bca9e359802bb5fd2f5f050eec21a4#rd

 

一、构造 kd 树

实现 k 近邻法时,主要考虑的问题是如何对训练数据进行快速 k 近邻搜索,为了提高搜索的效率,可以使用特殊的结构存储训练数据,以减少计算距离的次数,这里介绍的就是 kd 树方法。

kd 树的结构:

kd树是一个二叉树结构,它的每一个节点记载了【特征坐标,切分轴,指向左枝的指针,指向右枝的指针】。其中,特征坐标是线性空间 Rn 中的一个点 (x1,x2,…,xn)切分轴由一个整数 r 表示,这里 1≤r≤n,是我们在 n 维空间中沿第 r维进行一次分割。节点的左枝和右枝分别都是 kd 树,并且满足:如果 y 是左枝的一个特征坐标,那么 yr≤xr(左分支结点);并且如果 z 是右枝的一个特征坐标,那么 zr≥xr(右分支结点)。

给定一个数据样本集 S⊆Rn 和切分轴 r,以下递归算法将构建一个基于该数据集的 kd 树,每一次循环制作一个节点:

−− 如果 |S|=1,记录 S 中唯一的一个点为当前节点的特征数据,并且不设左枝和右枝。(|S| 指集合 S 中元素的数量)
−− 如果 |S|>1

  • 将 S 内所有点按照第 r 个坐标的大小进行排序

  • 选出该排列后的中位元素(如果一共有偶数个元素,则选择中位左边或右边的元素,左随便哪一个都无所谓),作为当前节点的特征坐标,并且记录切分轴 r;

  • 将 SL设为在 S 中所有排列在中位元素之前的元素; SR 设为在 S 中所有排列在中位元素后的元素;

  • 当前节点的左枝设为以 SL 为数据集并且 r 为切分轴制作出的 kd 树;当前节点的右枝设为以 SR 为数据集并且 r为切分轴制作出的 kd 树。再设 r←(r+1)modn。(这里,我们想轮流沿着每一个维度进行分割;modn 是因为一共有 n 个维度,沿着最后一个维度进行分割之后再重新回到第一个维度。

 

案例:

给定一个二维空间的数据集:T = {(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}, 构造一个平衡kd树。为了方便,我这里进行编号A(2,3)、B(5,4)、C(9,6)、D(4,7)、E(8,1)、F(7,2)初始值r=0,对应x轴。可视化数据点如下:

首先先沿 x 坐标进行切分,我们选出 x 坐标的中位点,获取最根部节点的坐标,对数据点x坐标进行排序得:

A(2,3)、D(4,7)、B(5,4)、F(7,2)、E(8,1)、C(9,6)

则我们得到中位点为B或者F,我这里选择F作为我们的根结点,并作出切分(并得到左右子树),如图:

 

 

对应的树结构如下:

 

 

根据算法,此时r=r+1=1,对应y轴,此时对应算法|S|>1,则我们分别递归的在F对应的左子树与右子树按y轴进行分类,得到中位节点分别为B,C点,如图所示:

 

对应树结构为:

 

而到此时,B的左孩子为A,右孩子为D,C的左孩子为E,均满足|S|==1,此时r = (r+1)mod2 = 0,又满足x轴排序,对x轴划分!则如图所示:

对应树结构如下:

到这里为止,给定的kd树构造完成啦,所有的数据点都能在树上的每个结点找到!

 

二、搜索 kd 树

 

(1)在kd树中找出包含目标点x的叶结点:从根结点出发,递归地向下访问kd树,若目标点x当前维的坐标小于切分点的坐标,则移动到左子节点,否则移动到右子结点.直到子结点为叶结点位置.

(2)以此叶结点为“当前最近点”

(3)递归地向上回退,在每个结点进行以下操作:

  1. 如果该结点保存的实例点比当前最近点距离目标点更近,则以该实例点为“当前最近点”.
  2. 当前最近点一定存在于该结点一个子结点对应的区域.检查该子结点的父结点的另一个子结点对应的区域是否有更近的点.具体地,检查另一子结点对应的区域是否以目标点为球心、以目标点与“当前最近点”间为半径的超球体相交。如果不相交,向上回退。

(4)当回退到根结点时,搜索结束。最后的“当前最近点”即为最近邻点.2

 

 

案例:

沿用上面的 kd 树,输入目标实例为K(8.5,1),求K的最近邻。

首先我们由上面可以给出,T的kd树对应如下:

 

我们此时的 K(8.5,1),根据算法第一步得:第一层的 x 轴 K 点为 8.5 大于F点的7,所以进入F(7,2)的右子树,进入下面红色线条区域:

到了第二层,分割平面坐标为y轴,K点y轴坐标为1,小于C点y轴坐标6,则向左走,在下图红色线条区域内:

则此时算法对应第(1)部分完成,我们找到了叶子节点E(8,1)。我们进行算法第(2)步,把E(8,1)作为最近邻点。此时我们算一下KE之间的距离为0.5(便于后面步骤用到).

然后进行算法第(3)步,递归的往上回退,每个结点进行相同步骤,好,我现在从E点回退到C点,对应图片如下;

此时对C点进行第(3)步的(a)操作,判断一下KC距离与保存的最近邻距离(这时是KE)比较,KC距离为点K(8.5,1)与点C(9,6)之间的距离>最近邻0.5。

于是不更新最近邻点。然后对C点进行第(3)步的(b)操作,判断一下当前最近邻的距离画一个圆是否与C点切割面相交,如图所示:

我们很容易看到与C点切割面并没有相交,于是执行由C点回退到它的父结点F点。如图:

 

对F点进行(a),(b)操作,进行(a)步骤,判断 FK 的距离是否小于当前保存的最小值,FK=\sqrt{(7-8.5)^{2}+(2-1)^{2}} = \sqrt{1.25} > 0.5,所以不改变最小距离。

下面我们进行(b)步骤,为了判断F点的另一半区域是否有更小的点,判断一下当前最近邻的距离画一个圆是否与F点切割面相交,如图所示:

发现与任何分割线都没有交点,那么执行算法最后一步,此时F点已经是根结点,无法进行回退,那么我们可以得到我们保留的当前最短距离点E点就是我们要找的最近邻点!任务完成。

并且根据算法流程,我们并没有遍历所有数据点,而是F点的左孩子根本没有遍历,节省了时间,但是并不是所有的kd树都能到达这样的效果。

 

 

三、kd树的不足以及最差情况举例:

 

以下通过一个例子来直观说明!

给定一个二维空间的数据集:T = {(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)},输入目标实例为K(8,3),求K的最近邻。

首先我们由上面可以给出,T的kd树对应如下:

我们此时的K(8,3),根据算法第一步得:第一层的x轴K点为8大于F点的7,所以进入F(7,2)的右子树,进入下面红色线条区域:

(注意:这里叶子节点画不画分割线都没有关系!)

到了第二层,分割平面坐标为y轴,K点y轴坐标为3,小于C点y轴坐标6,则继续向左走,在下图红色线条区域内:

则此时算法对应第(1)部分完成,我们找到了叶子节点E(8,1)。

我们进行算法第(2)步,把E(8,1)作为最近邻点。此时我们算一下KE之间的距离为2(便于后面步骤用到).

然后进行算法第(3)步,递归的往上回退,每个结点进行相同步骤,好,我现在从E点回退到C点,对应图片如下;

 

此时对C点进行第(3)步的(a)操作,判断一下KC距离与保存的最近邻距离(这时是KE)比较,KC距离为点K(8,3)与点C(9,6)之间的距离>最近邻2,于是不更新最近邻点。

然后对C点进行第(3)步的(b)操作,判断一下当前最近邻的距离画一个圆是否与C点切割面相交,如图所示:

我们很容易看到与C点切割面并没有相交,于是执行由C点回退到它的父结点F点。如图:

对F点进行(a),(b)操作!进行(a)步骤,判断FK的距离是否小于当前保存的最小值,FK=<2,所以将最小距离替换为FK的距离!

下面我们进行(b)步骤,为了判断F点的另一半区域是否有更小的点,判断一下当前最近邻的距离画一个圆是否与F点切割面相交,如图所示:

我们可以看出,此时圆与F点有交点,那么说明F点左侧是有可能存在与K点距离更小的点(注:这里我们人为看起来好像没有,但是计算机不知道,必须搜索下去,只要以当前最小值画圆发现与节点切割面有交点,那么一定要进行搜索,不然数据如果是下图:)

如果不进行搜索,我们就可能会漏掉Z数据点,因为KZ比当前最小值KF小!

此时相交,我们就需要再F点的左孩子进行搜索,一直搜索到叶子节点A,然后进行(a),(b)步骤,继续回溯到它的父亲结点B,以及最后到达F点,完成最后的最近邻是F点。

这里几乎遍历了所有数据点,几乎退化了为线性时间0(n)了。这也是kd树的最差的情况。

 

kd树个人理解--基础、通俗!

博文 来自: cgwang_1580
没有更多推荐了,返回首页