当前课程知识点:机器学习概论 > 第六章 基于实例的学习 > 6.5 KD树 > 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 机器学习系统设计
-第一章作业
-2.1 决策树的基本概念
--决策树的基本概念
-2.2 决策树的实例和发展历史
-2.3 经典决策树算法ID3
-2.4 过拟合和前剪枝
--过拟合和前剪枝
-第二章作业
-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 下午茶时间:图灵奖
-5.2 假设评估
--假设评估(1)
--假设评估(2)
--假设评估(3)
-5.3 置信度和置信区间
-5.4 有限数据下的比较
--有限数据下的比较
-第五章作业
-6.1 下午茶时间:黑洞照片
-6.2 基于实例的学习的基本概念
-6.3 最近邻算法
--最近邻算法
-6.4 K邻近算法
--K近邻算法
-6.5 KD树
--KD树
-6.6 距离加权的K近邻算法
-第六章考试
-7.1 支持向量机的背景
--支持向量机的背景
-7.2 线性支持向量机
-第七章作业
-8.1 核函数支持向量机
-8.4 支持向量机总结
--支持向量机总结
-8.5 无监督学习简介
-8.6 层次聚类
--层次聚类
-8.7 K-means聚类和K-medoids聚类
-第八章作业