wordpress 商城站下载,怎么用单位电脑做网站服务器,甘肃高端建设网站,沈阳seo团队三、 kd 树 问题导⼊#xff1a; 实现k 近邻算法时#xff0c; 主要考虑的问题是如何对训练数据进⾏快速 k 近邻搜索。这在特征空间的维数⼤及训练数据容量⼤时尤其必要。 k 近邻法最简单的实现是线性扫描#xff08;穷举搜索#xff09;#xff0c;即要计算输⼊实例与… 三、 kd 树 问题导⼊ 实现k 近邻算法时 主要考虑的问题是如何对训练数据进⾏快速 k 近邻搜索。这在特征空间的维数⼤及训练数据容量⼤时尤其必要。 k 近邻法最简单的实现是线性扫描穷举搜索即要计算输⼊实例与每⼀个训练实例的距离。计算并存储好以后再 查找 K 近邻。 当训练集很⼤时计算⾮常耗时。 为了提⾼ kNN 搜索的效率可以考虑使⽤特殊的结构存储训练数据以减⼩计算距离的次数。 3.1 kd 树简介 3.1.1 什么是 kd 树 根据 KNN 每次需要预测⼀个点时我们都需要计算训练数据集⾥每个点到这个点的距离然后选出距离最近的 k 个点进 ⾏投票。 当数据集很⼤时这个计算成本⾮常⾼针对 N 个样本 D 个特征的数据集其算法复杂度为 O DN 2 。 kd 树 为了避免每次都重新计算⼀遍距离算法会把距离信息保存在⼀棵树⾥这样在计算之前从树⾥查询距离信息 尽量避免重新计算。其基本原理是如果 A 和 B 距离很远 B 和 C 距离很近那么 A 和 C 的距离也很远 。有了这个信息 就可以在合适的时候跳过距离远的点。 这样优化后的算法复杂度可降低到 O DNlog N 。感兴趣的读者可参阅论⽂ Bentley J.L. Communications of the ACM 1975 。 1989 年另外⼀种称为 Ball Tree 的算法在 kd Tree 的基础上对性能进⼀步进⾏了优化。感兴趣的读者可以搜索 Five balltree construction algorithms 来了解详细的算法信息。 1. 树的建⽴ 2. 最近邻域搜索 Nearest-Neighbor Lookup kd 树 (K-dimension tree) 是 ⼀种对 k 维空间中的实例点进⾏存储以便对其进⾏快速检索的树形数据结构。 kd 树是⼀种⼆叉 树表示对k 维空间的⼀个划分 构造 kd 树相当于不断地⽤垂直于坐标轴的超平⾯将 K 维空间切分构成⼀系列的 K 维超 矩形区域 。 kd 树的每个结点对应于⼀个 k 维超矩形区域。 利⽤ kd 树可以省去对⼤部分数据点的搜索从⽽减少搜索的计 算量。 类⽐ “ ⼆分查找 ” 给出⼀组数据 [9 1 4 7 2 5 0 3 8] 要查找 8 。如果挨个查找线性扫描那么将会把数据集都遍历 ⼀遍。⽽如果排⼀下序那数据集就变成了[0 1 2 3 4 5 6 7 8 9] 按前⼀种⽅式我们进⾏了很多没有必要的查找现在 如果我们以5 为分界点那么数据集就被划分为了左右两个 “ 簇 ” [0 1 2 3 4] 和 [6 7 8 9] 。 因此根本就没有必要进⼊第⼀个簇可以直接进⼊第⼆个簇进⾏查找。把⼆分查找中的数据点换成 k 维数据点这样 的划分就变成了⽤超平⾯对k 维空间的划分。空间划分就是对数据点进⾏类 “ 挨得近 ” 的数据点就在⼀个空间⾥⾯。 2 构造⽅法 1 构造根结点使根结点对应于 K 维空间中包含所有实例点的超矩形区域 2 通过递归的⽅法不断地对 k 维空间进⾏切分⽣成⼦结点。 在超矩形区域上选择⼀个坐标轴和在此坐标轴上的⼀ 个切分点确定⼀个超平⾯这个超平⾯通过选定的切分点并垂直于选定的坐标轴将当前超矩形区域切分为左右两个子区域⼦结点这时实例被分到两个⼦区域。 3 上述过程直到⼦区域内没有实例时终⽌终⽌时的结点为叶结点 。在此过程中将实例保存在相应的结点上。 4 通常循环的选择坐标轴对空间切分选择训练实例点在坐标轴上的中位数为切分点这样得到的 kd 树是平衡的 平衡⼆叉树它是⼀棵空树或其左⼦树和右⼦树的深度之差的绝对值不超过1 且它的左⼦树和右⼦树都是平衡⼆ 叉树。 KD 树中每个节点是⼀个向量和⼆叉树按照数的⼤⼩划分不同的是 KD 树每层需要选定向量中的某⼀维然后根据这 ⼀维按左⼩右⼤的⽅式划分数据。在构建 KD 树时关键需要解决 2 个问题 1 选择向量的哪⼀维进⾏划分 2 如何划分数据 第⼀个问题简单的解决⽅法可以是随机选择某⼀维或按顺序选择但是 更好的⽅法应该是在数据⽐较分散的那⼀维进⾏ 划分分散的程度可以根据⽅差来衡量 。 第⼆个问题中好的划分⽅法可以使构建的树⽐较平衡可以每次选择中位数来进⾏划分。
