[背景音乐]
翻译: RyukaSuu |审阅: 19waa
Coursera Global Translator Community 好消息是，确实存在改进方法 我们接下来就讨论其中的一些 首先，我们要介绍KD-树 KD-树是一种数据结构，能够高效地表示我们需要的数据 具体来说，可以用KD-树把文档所在的空间分区 具体来说，可以用KD-树把文档所在的空间分区 分区面平行于对应坐标轴 每个分区内的点存在一个列表中 通过这样一个数据结构 我们可以对搜索域进行高效剪枝 也就是说不是每一个查询都需要遍历所有点 有时是必须的，有时则不 在中低维空间内，KD-树都很有效 空间维度对应着特征数目，对这点我们稍后详谈 首先，我们看一下KD-树的构造过程 我们取数据表格 例子中只有两个不同特征 特征1和特征2 假设这个是词汇表中的第一个词 这个是第二个，这列是数据点的索引 这些事观测点的索引值 这些点如图中所示 这个是，特征 1 这个是，特征2 首先，我们把表格中的点分成两组 首先，我们把表格中的点分成两组 方法是选择一个分区维度，也就是用哪个特征分区 以及分区值是多少，即分区阈值 以及分区值是多少，即分区阈值 例子中，我们以0.5作为分区值 用第一个特征分区 所以所有右侧的点，第一个特征值都大于0.5， 所有左侧的点，第一个特征的值都小于等于0.5 所有左侧的点，第一个特征的值都小于等于0.5 现在，我们回到数据点。若第一个特征的值小于0.5， 我们把它放入右侧的YES表中 否则我们就把它放入左侧的NO表中 然后我们对每一个表格做递归操作 然后我们对每一个表格做递归操作 也就是说把每个表格再分为两组 之前的分区值是0.5 现在我们要选择一个新分区值 我们选特征二作为分区维度 我们选特征二作为分区维度 并选0.1作为分区值 假设这里是0.1 这些是特征二大于0.1的情况 这些是特征二小于等于0.1的情况 图中的这些点对应着表中的这些点 这些点的x1的值小于0.5 所以落在竖线的左侧 又因为它们的x2的值小于0.1 所以它们落在横线的下方 所以条件判断结果是NO, NO，这些点落在这个表格里 接下来我们重复之前的过程，继续分割，分割 并构造出一个二叉树 在树的叶子结点 我们得到了对应分区内的一组点 每一个叶子结点里包含的数据点 表示该分区内的观测点 换句话说，如果我们从根结点下溯到任一叶子结点 这里的数据点满足路径上所有分叉的条件 这里的数据点满足路径上所有分叉的条件 这里的数据点满足路径上所有分叉的条件 这里的数据点满足路径上所有分叉的条件 这里的数据点满足路径上所有分叉的条件 此外我们还要保存一项对最近邻搜索很关键的信息 此外我们还要保存一项对最近邻搜索很关键的信息 对树中的任一给定结点， 我们保存如下信息 首先是分区维度 然后是分区值 也就是哪里是分区的阈值 第三项是最小外接盒子 即包含该结点内所有观测点的最小盒子 或者说包含了满足该结点条件的所有点的最小盒子 在包含所有的点前提下，这个外接盒子应取最小值 在包含所有的点前提下，这个外接盒子应取最小值 在包含所有的点前提下，这个外接盒子应取最小值 在包含所有的点前提下，这个外接盒子应取最小值 如图所示 这里是第三点 好，希望我讲清楚了 这种存储数据的结构非常直观 但像这一讲中的许多情景一样， KD树的构造也需要做很多重要的决策 KD树的构造也需要做很多重要的决策 KD树的构造也需要做很多重要的决策 比如，如何选择分区维度和分区值 以及何时终止分割 实际应用中我们采用启发式方法 比如 选择分区维度时优先分割取值范围最大的维度 假设有一个二维的外接盒子 我们比较x2和x1的值 如果x1比x2大，也许我们就选择分割x1 或者也可以交替分割各个维度 然后，关于如何选择分区值 一个方法是选择外接盒子内观测点的中位数 或者也可以不考虑盒子内数据点的分布，选择盒子的中心点 或者也可以不考虑盒子内数据点的分布，选择盒子的中心点 那么何时终止呢？ 我们有几种方案 一是当盒子里的点数少于某一定值时，终止分割 假设剩m个数据点 或者，如果盒子的最小宽度达到某个值 同样的，第二种方案无视了盒子内的数据分布 而第一种方案使用了数据点的个数来确定终止条件 我们举个例子说明这些决策有多重要 下面这个例子里， 依据数据分布的以中位数分割的启发式算法， 和用取值范围中点分割的算法，得出的数据结构完全不同 接下来我们将说明这对最近邻搜索的复杂度有怎样的影响 接下来我们将说明这对最近邻搜索的复杂度有怎样的影响 [背景音乐]
翻译: RyukaSuu |审阅: 19waa
Coursera Global Translator Community