格局打开，带你解锁kd树_kd树划分-程序员宅基地
前情回顾KNN：
假如我们现在有一个数据集，当给定一个新的实例时，最简单粗暴的方法就是计算它和所有点的距离，然后找到k个最近邻，最后根据多数表决的规则判断这个实例所属的类。
但是如果这个数据集中的训练实例非常多且密集，而且一个实例就有很多特征，那么就要计算出成千上万个距离，运算量极其庞大。
这时，我们就可以用一个更快速的计算方法——kd树。
什么是kd树
kd 树从根本上看，是一个二叉树结构，根据这个结构对k维空间进行不断的划分，每一个结点就代表了k维超矩形区域。
二维（k=2）的矩形区域：
三维（k=3）的矩形区域：
注意，kd树这里的k代表的是特征的个数，也就是数据的维度，而k近邻中的k指的是距离新实例点最近的k个邻居。
如何构造kd树
原理
输入： k维空间数据集：
T = { x 1 , x 2 , . . . , x n } T=\lbrace x_1,x_2,...,x_n \rbrace T={
x1,x2,...,xn}
xi=(xi(1)，xi(2)，…，xi(k))T，xi(l)的上标代表的是第l个特征值
输出： kd树
1.开始：构造根结点。
在根结点处选择一个最优特征进行切割，一般通过比较每个特征上的方差来决定，方差最大的特征就是我们要选取的坐标轴。
假如我们选出来的是x(1)，以它作为坐标轴，找切分点，将超矩形区域切割为两个子区域。通常选取x(1)方向上数据的中位数作为切分点，由根结点生出深度为 1 的左右子结点，左结点的坐标小于切分点，右结点坐标大于切分点。
2.重复：剩余特征的选取与切割
继续对深度为j的结点，选择x(1)为切分坐标轴，l=j(mod k)+1，以该结点区域中所有实例x(1)坐标的中位数作为切分点，将区域不断分割为两个子区域。
3.停止：得到kd树
直到两个子区域没有实例时停止分割，即得到一棵 kd 树。
例题解说
输入：
T = { ( 2 , 3 ) , ( 5 , 4 ) , ( 9 , 6 ) , ( 4 , 7 ) , ( 8 , 1 ) , ( 7 , 2 ) } T=\lbrace(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)\rbrace T={
(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}
输出： kd 树
为了方便，给数据集里的数据点标号后进行可视化展示：
1.第一次切分
因为该训练数据集的维度是2，那么任选一个特征即可。不妨选择x(1)为坐标轴，将x(1)中的数据按照从小到大排序，分别是：2，4，5，7，8，9
中位数不妨选7，即以（7，2）为根结点，切分整个区域。
左边的就是小于7的子结点，右边的是大于7的子结点。
2.第二次切分
再次划分区域：
对第一个特征加1，以x(2)为坐标轴。
对于第一次切分后的左边区域而言，将x(2)中的数据按照从小到大排序，分别是：2，3，4，7
中位数取4，切分点坐标为 （5，4），再画一条横线进行第二次切分。
同样地，对第一次切分后的右边区域而言，将x(2)中的数据按照从小到大排序，分别是：1，6
因为只有两个点，不妨选择6作为切分点，右边区域切分点坐标为 （9，6） ，画一条横线进行第二次切分。
3.继续切分
第二个特征加1，以x(3)为坐标轴，而这里只有x(1)和x(2)，所以只对x(1)进行划分。或者直接计算2(mod 2)+1=1即可得到所选的特征。
可以明显看出A（2，3），D（4，7），E（8，1） 三个实例点还未切分，那么以这些点为根结点分别画一条垂直于x(1)轴的线进行切分。
4.绘制kd树
这几次划分中的根结点分别是：
第一级：（7，2）
第二级：（5，4），（9，6）
第三级：（2，3），（4，7），（8，1）
根据这个层次绘制出kd树：
如何搜索kd树
原理
输入： 已构造的kd树，目标点是x
输出： x的最近邻
寻找“当前最近点”： 从根结点出发，递归访问kd树，找出包含x的叶结点，以此叶结点为“当前最近点”
回溯： 以目标点和”当前最近点“的距离沿树根部进行回溯和迭代，当前最近点一定存在于该结点一个子结点对应的区域，检查子结点的父结点的另一子结点对应的区域是否有更近的点。
当回退到根结点时，搜索结束，最后的”当前最近点“即为x的最近邻点。
例题解说
以上文生成的那棵kd树为例：
Case 1
输入： kd树，目标点 x=(2.1,3.1)
输出： 该目标的最近邻点
寻找当前最近点： 从根结点开始，x=(2.1,3.1)在根结点（7，2）的左子区域内，继续到（5，4）所确定的左子区域内，继续到（2，3）的右子区域中，（2，3）就是当前最近邻点。
回溯： 以（2.1，3.1）为圆心，以其与已确定的最近邻点之间的距离为半径画一个圆，这个区域里没有其他的点，那就证明（2，3）是（2.1，3.1）的最近邻点。
Case 2
输入： kd树，目标点 x=（2，4.5）
输出： 该目标点的最近邻点
寻找当前最近点： 从根结点开始，x=（2，4.5）在根结点（7，2）的左子区域内，继续到（5，4）所确定的上子区域内，继续到（4，7）的左子区域中，（4，7）就是当前最近邻点。
回溯： 我们以（2，4.5）为圆心，以（2，4.5）到（4，7）两点之间的距离为半径画一个圆，这个区域内有两个结点，分别是（2，3）和（5，4），通过计算（2，4.5）到这两点的距离，得出到（2，3）距离最近，那么（2，3）就是最邻近点。接着再以（2，4.5）为圆心，以（2，4.5）到（2，3）两点之间的距离为半径画一个圆，此时圆里没有其他的结点，说明可以确认（2，3）就是（2，4.5）的最近邻点。
参考资料：
视频资料：
智能推荐
unity android 点击,Unity和Android交互-程序员宅基地
文章浏览阅读820次。前言: 在 Android 软件的开发中,会经常遇到 Unity 调用 Android 中的接口方法,不单是内购和广告的接入,普通的使用 Unity 去调用 Android 的原生消息框都会需要使用到交互相关的知识,接下来我们开始吧.前期需要准备:确认安装 Android Studio 开发软件.整体步骤我分为:基于 AS(Android Studio) 编写接口方法类并打出 jar配置关联 Un..._unity 获取android 点击
JAVA生成压缩文件_java 生成带路径压缩文件-程序员宅基地
文章浏览阅读1.7k次。 package com.wyebd.publicuse;import java.io.*;import java.util.zip.*;public class FileZip { /** * 压缩一层目录下的所有文件或压缩单个文件 * @param filePath 要压缩的文件路径 （单个文件需含文件名） * @param toFilePath 压缩后的文件路径 含文件名 * _java 生成带路径压缩文件
java sql web_GitHub - guohai163/java-sql-web: 一个使用java语言开发的多数据库查询WEB平台...-程序员宅基地
文章浏览阅读286次。JavaSqlWeb - 一个运营环境数据查询系统项目介绍所有企业都面临的一个需求就是需要开发人员连接线上生产库进行数据查询或解决线上问题，但又担心开发人员查询线上敏感数据甚至拖库。一般做法都是：通过限制查询人员、限制查询的表和字段。使用跳板机，所有查询都要在跳板机上进行。进出数据文件要过审查机制。使用第三方系统，记录每人的查询语句，并限制查询。从上向下规则是越来越严。第一级直接由DBA进行查询账..._java项目sql web客户端 github
Java：用数组输出诗歌，横、竖版输出_java输出诗句不挨着怎么办-程序员宅基地
文章浏览阅读3k次，点赞4次，收藏14次。1、定义数组2、用正反循环输出3、判断奇数用“，” 偶数用 “。”public class Poerty { public static void main(String[] args) { char arr[][] = new char[4][]; // 创建一个4行的二维数组 arr[0] = new char[] { '青','山','隐','隐','水','迢','迢'}; // 为每一行赋值 arr[1] = new char[] { '秋','尽','江','南','草','_java输出诗句不挨着怎么办
flutter Android编译打包全过程解析_flutter 编译apk-程序员宅基地
文章浏览阅读8.2k次。文章目录settings.gradle根目录build.gradleapp/build.gradleFlutterPlugin本篇主要讲解一个flutter工程是如何编译打包成一个apk的。注意：这里我们是一个空的flutter项目，然后引入了一个webview-flutter的plugin来模拟一个plugin是如何一起打进去的。flutter版本：2.4.0-5.0.pre.145settings.gradle因为最终产物是apk，所以其实总体上走的还是安卓编译，所以我们先来看settings_flutter 编译apk
恒生UFX交易接口基本介绍-程序员宅基地
文章浏览阅读1.8k次。https://zhidao.baidu.com/question/203296047903136445.html1、恒生UFT和UFX有什么区别？UFT是一个极速交易系统，UFX是一个统一接入系统。交易系统很显然是可以进行股票交易的，UFX是所有后台交易系统的接入系统，不管后台是什么样子的交易系统都是可以通过UFX进行委托交易，UFX将交易系统的差异化屏蔽掉，让周边的接入者不用..._o32投资管理系统ufx接口
随便推点
Echart 柱状图柱子倒序排序_柱状图中的inverse: true-程序员宅基地
文章浏览阅读1.2w次，点赞10次，收藏12次。Echart欢迎使用Markdown编辑器你好！ 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章，了解一下Markdown的基本语法知识。新的改变我们对Markdown编辑器进行了一些功能拓展与语法支持，除了标准的Markdown编辑器功能，我们增加了如下几点新功能，帮助你用它写博客：全新的界面设计 ，将会带..._柱状图中的inverse: true
OpenGL--渲染过程中产生的问题_opengl颜色渲染缺点-程序员宅基地
文章浏览阅读966次，点赞2次，收藏2次。描述：在绘制图形过程中，对于观察者而言，有些部分是可见的，有些是不可见的。如果都进行渲染的话，不可见部分会会影响整体的渲染效果，无法满足预期的效果。那么针对这类问题的解决，就叫做“隐藏面消除”。_opengl颜色渲染缺点
课设——学生成绩管理系统.exe_学生成绩统计系统exe-程序员宅基地
文章浏览阅读1k次，点赞3次，收藏7次。一、系统需求分析1、总需求设计一个实用的小型学生成绩管理程序，具有查询，检索和删除等功能。2、具体需求(1)学生基本信息、考试科目及成绩的信息录入。(2)已有学生信息的显示。(3)学生基本信息的读取和保存输入数据等功能(4)学生基本信息的查询与修改。可以对已有的学生信息进行修改。(5)学生基本信息的删除。(6)对该班各科成绩进行分析；对学生成绩进行统计（包括最高分，最低分，排序，平均成绩，及格率和需要补考的学生）具体源码详见（链接）二、总体设计1、定义四个类Student类、S_学生成绩统计系统exe
使用pdf.js不依赖任何activeX控件_pdfjs view.html怎么传入file文件参数-程序员宅基地
文章浏览阅读971次。使用pdf.js可以直接在浏览器上浏览PDF文件，而且不依赖任何activeX控件~ github上下载生成好的pdf.js工程本机项目：PDFPrintTest下demoviewer.js中要增加CORS跨域访问限制判断，否则不能跨域访问，或者在HOSTED_VIEWER_ORIGINS数组中增加viewer.html所在主机IP:PORT。作为不校验同源的ip_pdfjs view.html怎么传入file文件参数
Python 中 float 计算精度问题_python float 精度-程序员宅基地
文章浏览阅读7.5k次，点赞3次，收藏12次。浮点数不能精确的表示十进制数，并且即使是最简单的数学运算也会产生误差。该错误是由于浮点数的存储方式引起的。_python float 精度
HT合泰单片机入门教程（第一章 HT单片机环境搭建）-程序员宅基地
文章浏览阅读1.3w次，点赞21次，收藏115次。HT合泰单片机入门教程系列文章目录前言一、合泰单片机的优势二、HT-IDE3000安装1.HT-IDE3000下载2.HT-IDE3000安装总结系列文章目录# 第一章 HT单片机环境搭建目录系列文章目录前言一、合泰单片机的优势二、HT-IDE3000安装1.HT-IDE3000下载2.HT-IDE3000安装总结前言工作已经很长一段时间，虽然还是菜鸟一只。但还是有点心得体会。写合泰单片机系列教程的原因：一、是为了记录自己学习过程和学习经历（ps：当初毕业进公司接触到的第一个就是为一款已_合泰单片机入门教程