当前课程知识点:机器学习概论 >  第六章 基于实例的学习 >  6.5 KD树 >  KD树

返回《机器学习概论》慕课在线视频课程列表

KD树在线视频

下一节:距离加权的K近邻算法

返回《机器学习概论》慕课在线视频列表

KD树课程教案、知识点、字幕

然后在查找之前

我们来看一看有几个细节 第一就是怎么样分割

就是我们是说刚才你可以横着切 也可以竖着切

我应该选哪个维度去切呢

一个简单的思路就是看剩下的哪个维度很宽

我就从哪个去切 这个宽其实就说看你现在剩下的那个点上面

他们的分布 最大的和最小的之间的宽

第二个 就是我们应该从哪儿切

就是这一刀应该划在3这个值 还是2这个值 还是2.5呢

我们一般会用中值来去切 注意呀 我们这里用的是median而不是min

为什么呢 为什么不是在就是我们现在在这个上面有好多个点

我们是取了诶呦这画得 好吧 假设这个是中值

我们在中值这儿去切一刀 而不是取他们的min

可能是在这个位置 为什么取中值

它占的数比较均匀

对的 就是因为这个原因 所以大家会想一想啊

当我们去构造你的算法的时候 你一定要考虑到 你的目的是为了

是为了方便查找的 所以平衡的树呢

一般来说相对比较容易查找一些 然后那么所以呢

我们为了让这个两边的点的个数差不多 所以呢

我们事实上就是均衡地分布 分布在这个区域两端的那个那个数

所以我们会看到我们刚才切出来的那个不是方方正正

那就变成田字格了 我们其实不是切出来的田字格的样子

然后什么时候要停呢 就是你其实规则很简单

你也不用一直无限地切下去 就是你把它分了一些组就行

你如果觉得一个区域内的点已经足够少了 就不用再分了

或者呢 如果你觉得你的宽度已经小于 就是它已经尽管很密

但是它已经足够窄了 那你也不用再分了

所以呢 刚才我们已经基于这些点你会看到

我们不是方方正正的切 所以得到了这样的一个构建好了KD树

这个KD树是我们存储的时候用的 那么现在来了一个新的点

过来要做判断的时候 要计算距离的时候

计算谁离它最近的时候 怎么做呢

我们把它叫做KD树的 过程 查询的过程 那这个呢

你其实就是对它做一个便利

但是这个便利你看我们以前你得每一个都计算一遍吧

现在假设这里来了一个点 就是这里有一个红色的点 那怎么做呢

首先我们来先找它最近的这个点 然后你首先去看一看

它落在了哪一个大的这个区域内 从这个树上来看

因为你其实是有X大于什么小于什么的

所以你就很容易找到了它的分支 它在哪一个大的区域内

然后从这个区域内呢 你事实上会找到这样就先看到了这半区

然后接下来这半区呢 你又根据它的第二次分割呢

会发现它又到了右半边的这个分支上 然后再接下来呢

又会发现它在左边的这个分支上 这是根据你刚才构造的时候

你构造树的时候已经知道了 所以很容易就先落到了这个上面

落到了这里上面呢 你就会发现看一看它在这个区域内的

所有的点里面 哪个距离最近 比如说你会发现它的这个距离最近

但是并不能就此停止 对吗 我们从这个图上你已经看到了

这个点事实上并不是全局最近的点

那这个时候你接下来要做的事情呢 是你要去比较一下

你要做一个backtrack 就刚才它已经落在这儿了之后

你要去backtrack它旁边的这个other branch 就是你刚才访问过的

看过的那些other branch 然后现在在other branch里面呢

再去找我是不是有最近的那个节点 如果有就把它update一下

你当前的最小点的距离 然后再接下来比的时候呢

再去看另外一个branch的时候 还记得吗

我们刚才让你记了这个branch里面的边界

所以其实你去跟这个branch比的时候啊 你是先跟它的边界比

如果你发现它已经比边界距离就是都更大了

就它到边界的距离都已经大于你当前的最近的距离了

那这个整个就不用再比了 你并不需要比这个里面的所有的点

你去比它的那个 的那个边界就可以了 所以呢 这样会发现

这个太大 所以这些点呢你可以不用比

然后刚才还有这一半也没trance过呀 那它跟这个trance的边界一比

发现这个距离也远大于它当前的最近距离 所以这边也不用比了

因为它这个边界你已经记录下来了 用这种办法你就会发现

你实际上这些都是不用比的 你只需要做有限次的判断

就是你其实只比了这些点而已 就找到了它的最近邻

这是最近邻的做法

当然如果你要去找三近邻 五近邻 就是类似的算法

你稍微扩展一下就行 就是你update你的记录的那个score就可以了

用这种办法你能够非常快速的加快我们最后查找的过程

好 那基本上到现在为止 我们就把KNN这个算法终于介绍完了

那其实你会看到它概念非常简单

但其实它能够用来解决非常复杂的问题

因为你比如说你其他的模型 你最会有一个有一个假设

认为它应该是线性的或者是什么样的 然后你能力是有限

但是KNN不是这样 KNN它甚至有可能对呀 就是有可能能够

能够判断我们刚才给大家看到KDtree里面那样的

或者是或者是voronoi图里面的这样的复杂的一个

学出来的边界都是有可能的 然后呢 它也对噪声比较鲁棒

尤其是当K不等于1的时候 当K大于1的时候

它对噪声是比较鲁棒的 因为它是对多个邻居的平均

然后它其实也比较容易理解 因为你就很容易可以从因为近朱者赤

近墨者黑这个来去解释 因为它和A的这个表现很像

所以它应该是这一类的

然后还有呢 就是特别大的优点是 它在数据存储的这个

在training的阶段 它是没有数据损失的 就是因为所有的样例都被存下来了

它不像你预先定义一个model的时候 你会有一些信息被损失掉

而且有可能是有bias 然后实现也很简单就KNN

因为你只需要求一个距离的计算公式就行了 如果你考虑效率

当然你需要去构建这样的KDtree的结构来存储它

但是总的来说还是比较简单

而且这个特别适合做leave one out的test leave one out

test特别就是挺重要的 尤其在你数据规模没那么大的时候

你想要重复很多遍 你比如说你一共就一百个样本

你想重复一百次你随便做抽样那个其实会有点麻烦

但是你如果就一百个样本 你每次抽出一个来

这种你就可以很容易重复一百次

但是它有缺点 缺点是什么呢 memory cost 它就是很耗内存

就是因为你得把它都存下来 然后当然你如果用

KDtree的方式去存还好吧 但是你还得存边界呀

就总之你的memory cost 它不像 不像你的

我们之前教过的所有的这些model啊

那些model如果你学完了之后你的训练数据都不用存了

你的系统里面你去做测试的时候 你就只记一个公式就够了

比如说就是你只记住这个参数和公式是什么就行了

其他你扔掉都没关系 除非你要重新训练 所以呢

那个是没有什么memory 但是在这个里面 你去做的时候

你所有原来的原始数据都还得在这个里面

然后呢 你还得去计算 就是所有的pair之间的那个这个距离

然后KDtree呢 会让你的这个计算的内存会小一点

然后CPU cost 因为你得算那么多的数 然后还有就是其实刚才我们问

多个怎么办的时候 有那边有同学回答说我可以再选一个距离函数

但其实吧 就是思路是可以的 确实是可行的 但有一个问题是

距离函数其实不好选 合适的距离函数基本上是KNN这个

这一类算法里面最大的难题之一 就别的问题都还好解决

但是我应该用什么距离函数这个东西 目前没有人

没有一个证明说什么样的问题就应该用什么距离函数

通常大家就是基于经验值试一试 试试A 试试B 试试C

然后试一些 看看哪个效果更好 因为你很难 绝大多数情况下

你不知道它们数据之间是怎么体现它们的相似性的

就是很难去证明出来它应该用什么函数去代表

还有就是无关的feature 它可能会影响到我们的距离的计算

就是特征 但是这个特征到底 所以我们才需要引入特征的权重

但是这个权重我们需要有一些方法来计算

需要去一定程度上缓解这个问题 然后以上就是

我们今天跟大家介绍的所有关于KNN的问题 但是我们的课程呢

还没有结束 是因为我们还有非常exciting的方法

就是接下来的一个问题啊

就是我们刚才说了 K等于3的时候 如果有tie不够用 那么怎么办

然后有人说我可以再加一个再加一个neighbor 但是我们再回过头来想想这个办法

这个问题 是不是这K个邻居对我当前的这个样例点的贡献是一样的

其实不一定 对吧 它有可能和有一个点很近

离其他的两个点其实有可能已经非常远了

所以刚才我们有同学跟大家说

有一个办法也许是我们找一个函数 把这个函数来映射和计算一下

能够把它变换成别的东西 那么其实呢 用简单的办法来说

我们其实是不是可以找到这样的一个加权的办法 这个加权呢

是加到了你当前的这个K个邻居上 所以你可以还是用K个邻居

但是每个邻居呢 我看它的重要性不一样

就是我要把距离更近的那个邻居让它起到的影响更大

远一点的邻居呢 影响稍微小一点

这个其实对于我们按照常理来说也是比较合理的reasonable的对吧

所以呢 这个就是一类新的方法 我们把它叫做distance weighted nearest neighbor

就是基于距离加权的近邻方法 怎么近邻加权呢

这是我们今天要讲的第三套 所以我们在这个里面呢 需要一个函数

这个函数我们通常会喜欢把它叫做kernel function 叫做核函数

所以我其实在考虑我这节课到底是讲KNN 还是讲SVM的时候

犹豫了一下 但是我觉得和函数这个概念

可能在KNN的instance based learning里面去引入比较自然

所以我们先讲这个下堂课再去讲SVM那个也有核函数的问题

这个kernel function呢 事实上就说你本来是有一个这个距离X

就是两个点之间的距离的你是欧式距离等等也好

那事实上呢我就构建一个函数 这个函数和这个距离有关

它会就这个距离做一个放缩 那么我最终呢

事实上输出的时候 做predict的时候 事实上是把你的输出值

乘以了这个经过和函数变换过的权重 然后做了一个normalization

这个核函数怎么变换呢 常见有很多种核函数

比如说我这里列出来了三种非常常用的 一种是平方分之一

其实你也可以是三次方分之一 四次方分之一

但是平方分之一会比较多 比如说就是距离的平方的倒数

这个就是距离越大 你的这个核函数做过来 它的那个相似度就越小

就是经过核函数变换的这个就会越小 还有呢 是E的-d次方

它是一个指数函数 然后或者呢是1+d分之一

就事实上就都是距离越大 我的这个重要性贡献就越小

就你可以认为它的这个权值就越小

然后呢 总之它应该是和你的距离是取反的

因为你表示的是这个样例对你的

对当前你要判断的预测的这个点的影响是多大

机器学习概论课程列表:

第一章 绪论

-1.1 课程介绍

--课程介绍(1)

--课程介绍(2)

-1.2 机器学习的背景

--机器学习的背景

-1.3 什么是机器学习

--什么是机器学习

-1.4 机器学习系统设计

--机器学习系统设计(1)

--机器学习系统设计(2)

-第一章作业

-第一章课件

第二章 决策树学习(I)

-2.1 决策树的基本概念

--决策树的基本概念

-2.2 决策树的实例和发展历史

--决策树的实例和发展历史

-2.3 经典决策树算法ID3

--经典决策树算法ID3(1)

--经典决策树算法ID3(2)

--经典决策树算法ID3(3)

-2.4 过拟合和前剪枝

--过拟合和前剪枝

-第二章作业

-第二章课件

第三章 决策树学习(II)和贝叶斯学习

-3.1 下午茶时间:勒索软件

--下午茶时间:勒索软件

-3.2 后剪枝

--后剪枝

-3.3 决策树的改进和归纳学习假设

--决策树的改进和归纳学习假设

-3.4 贝叶斯学习的背景

--贝叶斯学习的背景

-3.5 极大似然假设、朴素贝叶斯和最小描述长度

--极大似然假设、朴素贝叶斯和最小描述长度

-第三章作业

-第三章课件

第四章 马尔可夫模型和隐马尔可夫模型

-4.1 下午茶时间:微博的垃圾检测

--下午茶时间:微博的垃圾检测

-4.2 马尔可夫模型

--马尔可夫模型

-4.3 隐马尔可夫模型

--隐马尔可夫模型

-4.4 评估问题

--评估问题(1)

--评估问题(2)

-4.5 解码问题

--解码问题

-4.6 隐马尔可夫模型的应用

--隐马尔可夫模型的应用

-第四章课件

-第四章作业

第五章 假设检验

-5.1 下午茶时间:图灵奖

--下午茶时间:图灵奖(1)

--下午茶时间:图灵奖(2)

-5.2 假设评估

--假设评估(1)

--假设评估(2)

--假设评估(3)

-5.3 置信度和置信区间

--置信度和置信区间(1)

--置信度和置信区间(2)

--置信度和置信区间(3)

-5.4 有限数据下的比较

--有限数据下的比较

-第五章课件

-第五章作业

第六章 基于实例的学习

-6.1 下午茶时间:黑洞照片

--下午茶时间:黑洞照片

-6.2 基于实例的学习的基本概念

--基于实例的学习的基本概念

-6.3 最近邻算法

--最近邻算法

-6.4 K邻近算法

--K近邻算法

-6.5 KD树

--KD树

-6.6 距离加权的K近邻算法

--距离加权的K近邻算法

-第六章课件

-第六章考试

第七章 支持向量机(I)

-7.1 支持向量机的背景

--支持向量机的背景

-7.2 线性支持向量机

--线性支持向量机(1)

--线性支持向量机(2)

--线性支持向量机(3)

--线性支持向量机(4)

--线性支持向量机(5)

-第七章课件

-第七章作业

第八章 支持向量机(II)和无监督学习

-8.1 核函数支持向量机

--核函数支持向量机:向量空间

--核函数支持向量机:核函数(1)

--核函数支持向量机:核函数(2)

-8.4 支持向量机总结

--支持向量机总结

-8.5 无监督学习简介

--无监督学习简介(1)

--无监督学习简介(2)

-8.6 层次聚类

--层次聚类

-8.7 K-means聚类和K-medoids聚类

--K-means聚类和K-medoids聚类

-第八章课件

-第八章作业

KD树笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。