当前课程知识点:机器学习概论 > 第六章 基于实例的学习 > 6.4 K邻近算法 > K近邻算法
我们上堂课讲到 到底怎么判断你这个权制是什么
其实有很多种不同的做法 但其中有一种做法呢
我们觉得还是比较 比较合理的做法之一是用互信息 互信息呢
其实你们应该上过 你们上过什么概率课
然后应该知道什么是互信息吧 还是不知道呀
知道什么是互信息的同学举一下手 好像 很个别的同学知道
好 没关系 我把公式放在这儿了
x和y它的mutual information互信息一般用 i(x y) 表示
它呢 就是等于H(X)+H(Y)墒你们一定知道
因为我们在 哪怕你之前没学过你在我们决策树学习里面也学过
就等于那个H(X)+H(Y)- H(X,Y)就joint entropy
这个联合商等于什么呢
就是-p 还是-plog(p) 就是负的x和y它的联合概率
乘以xy的概率的log值 然后去求和加到一起就行了
所以那我们其实是可以用互信息
就是这个互信息是什么和什么的互信息呢
是我们每一个属性和你最终的 label就你最终把它分成哪一类
这个之间的互信息来去描述的
其实也就相当于看你这个属性跟这个类别之间有我多大的关联程度
有多大的相关性 有多大的信息量就是
所以事实上是用这个我们可以很好地来衡量
如果一个属性它是决定你这个 label的很关键的信息
那你接下来你就可以给它比较大的权值
但当然还有其他的方法哈 那么我们在KNN的这个里面呢
它是讨论第三个问题 我们刚才在讨论了距离有
其实有更多的距离函数可选 然后还讨论了如果怎么样处理属性
属性就是你要做规划 你可以给属性不同的权值
对了 当你这个权值等于零的时候 也就意味着你去掉了这个属性
这个是可以的 如果你学到发现这个权值它应该是零也是可以的
多说一句 这种去除呀 我们把它叫做 soft的这种去除
就是说你是通过参数和权重来去去掉这个feature的 去掉这个属性的
而不是hard的去除 就是硬去除 硬去除就属于你在数据处理的时候
你压根儿就没把这个feature 提出来 那个是硬去除
一般来说我们会觉得soft的这种方式会比hard的方式要更灵活
然后也有可能会效果更好
但是要注意 soft的时候如果你这个 如果已经小到
比如说你这个weight 变成0.0001了 那你索性就把它变成0就好了
因为你的数据很有可能不足以支持它变成这么微妙的敏感的变化
那有可能你这个值是由于 overfitting 带来的
你不如就把它认为就把它变成0就好
就让它变得这样就会让它变得更鲁棒一些
第三个问题我们刚才说的那些都是离散的输出 yes或者no
good或者poor 那么如果是连续输出 连续的目标函数怎么办
因为离散输出我其实三个 KNN K等于三的时候你投票就好了
如果有连续的呢 其实最简单的做法就是求均值
看一下它们的平均值取到多少就是多少
给大家来看一下一些连续输出的这个例子
比如说红线是它我们原始的就是其实它
你知道它应该是就是这个样子 然后上面的这些点
这些带十字号的这个点是我们观察到的样例
红色的是它背后真实的那个 那个目标函数应该是这个样子
如果用1NN最近临来看 我们学到的是蓝色的这样的一个
一个不能叫曲线 就是它阶梯状的这样的形状
如果是3NN呢 是这种样子 5NN就是这种
从这个上面你会看到 可能3nn会比3近临会比5近临稍微好一点
就是它的这个突的这个部分建模的还凑合 但是它在这个这个
这两端它的那个损失就比较大 比如说在这端 1近临呢
看起来其实每一个点 fit的很好 但是它特别抖动
就是它不是那么的平滑 但这个是用KNN的方法得到的结果
看起来似乎不是那么好 别着急我们还有办法的
但我们现在讨论另外一个问题啊
就是K 刚才有同学在下面问K值应该怎么选
K呢 非常多的情况 By default的情况 我们一般不会让K等于太多
通常一般默认值你如果什么都不知道
你可以先试一试K等于3 3或者5这样的
不知道大家注意到了没有 我说的时候
基本上说的都是单数 135 我没有说K等于2 K等于4 因为
要投票
对 偶数非常容易出现投票的冲突
只有单数如果尤其在二分类的时候 单数就比较好
但是然后呢 其实大家一定要有这样的概念 K并不是越大越好
刚才你从那个例子里面会看到K等于5的时候它已经
已经损失掉了非常多的信息了 到底怎么样选K呢
我们其实有一个做法 是用cross validation的方法来做
现在大家会觉得交叉验证cross validation
不是一个很复杂的名词了
就是我们在上一堂那个理论课 机器学习理论课上已经提到
但这个呢 是用最特殊的一种方法 我们把它叫做Leave one out
我们之前上堂课介绍的时候是说 我们比如说k-fold validation 是我们有一个
有一份数据我们把它分成了K份 然后呢 每次用一份来去测试
你还可用另外一份来做验证 剩下的八份来做train 等等
总之就是有一份测试等等这种k-fold validation 有一种最极端的情况Leave one out
就是我每次拿一个数据点验证 其他所有的都可以拿来做训练
这样的话 你的数据规模有多大 你其实就可以重复这个实验多少次
就不是k-fold 了 你如果有一百个点 那你每次Leave one out
你就可以重复一百次 测试它的效果是怎么样的
然后这种方法呢 我们引用Leave one out
也会把它叫做throw one out或者hold one out都有这样的叫法
好 然后呢 一般来说 我们通常就是你测试一下 你给不同的
取不同的K值 K等于3的时候train一下 validation set上面有一个结果
然后呢用K等于5的时候 有一个结果 然后通过学习的办法
通过那个training 和 validation 的方法来去选一个合适的K值就行了
所以呢 总的来说 KNN是比较稳定的
就是因为它你的如果训练样例里面的比较小的扰动
其实不会特别那么显著的影响结果
当然碰巧你如果那天K个邻居全都是或者K个邻居里面绝大多
占大多数的优势的都是噪声 那可能这个结果会错了
但它也只是影响那一片的那个结果而已
所以KNN相对比较稳定 但是呢 有一种特殊的情况
就是它可能会有ties 就是死锁了 就比如说如果你是有三个类
然后你的K还等于3 然后现在呢就会发现 你就不好办了
这个时候怎么办呢 有什么办法大家可以想一想 分别说一下
简单的办法
最近的
用最近的那个 好 这是一种思路
考虑第四个
考虑第四个特别好 还有吗 就都是可行的办法哦 都很好 还有吗
把距离分两块儿
很好 你可以声音再大一点
就是距离衡量的那个函数可以不止用一个
是一个挺好的思路 对 还有吗
我有没有可能还是用 这么多点呢
挺好的 其实是这个思路 这是比较复杂的描述方法
其中有一种情况是说你怎么重构这个函数呢 我们后面会提到
而且会作为我们后面的一个重要的一个方式
还有一些大家没提到 比如说你 对 就最近的呀
或者是neighbor 或者你取三分之一用新的距离
你也可以得random地选一个等等都可以
后面有一种方法我们在efficiency这个 topic之后
会作为一个新类的一个新的要讨论的话题来去介绍给大家
然后我们在此之前 先讨论一下 的问题 效率这个问题
其实是一个挺核心 挺关键的东西 就是你看我们在这个算法里面
也就是训练的时候 大多数什么都没做就是你就把它存下来了而已
然后 但是你计算的时候 你做最终预测的时候 你来了一个点
你需要跟每一个你存过的点都计算一下距离 计算完了之后
求出最小的K来 然后以某种方式输出
每一个样例你都得这么算一遍 而且这个你没办法提前算
因为你算的不是已知样例之间的距离
而是你新来的测试里和已知之间的样例 所以只有等样例来了才能算
这个就特别慢 大家想一想看你就会知道
假设你的训练样例有一千个呢 你就得算一千个距离
如果更大规模就很惨 也不是什么办法都没有呀
就是有人提出来一种做法叫做构建一个KD树 但这个KD树呢
这个D不是指 这个D指的是dimension
它的纬度 K呢 是指有多少个维
然后这个它是一种基于树的一个存储结构
就是我们其实就是用空间来换时间 然后呢 基本上它的思路是这样的
假设我们用二维的情况 就是用2D的二维的情况来去描述
这个比较简单一点 但事实上你的数据的 feature一般会更多
好 假设这个是在一个二维平面上你有着这些点
我们存的时候怎么存呢 不是就把它放在那儿了
而是想想看 我能不能有可能把它存得更有效率里面
这样未来我计算的时候能够计算的更好一点 首先我们会把这个点
你原来有一些点 然后接下来呢 我们要把这些点分成两组
基于其中的某一个特征 然后如果这个特征大于一个值
它就是在一组 另外一个小于一个值就在另外一组
所以其实它相当于是你把这个平面做了一个partation 做了一个分割
在一个纬度上做了一个分割 然后现在呢 再接下来呢
我们取其中的一部分来看 就一半一半的来做
这个在大家的学过数据结构的同学就是会对这个已经非常有概念
就只要提到树的结构 你一定会有这样的recursive 的这种做法
然后看其中的这一半呢 我们再把它分割 这个分割的时候
也有可能是从另外一个纬度
但其实也有可能是从它同样的纬度再继续去分割的
总之呢 你就再分割一下 然后事实上分到最后呢
其实你就把这个空间分割成了很多个不同的空间
就是一半一半的这种去分割
然后其实呢就把它构造成了这样的一棵树 存储这个data
这是一个存储上面的结构 存储完了之后 其中的一个区域
就对应有你对应在你的这个树上面的一个节点
或者说你树上的一个节点就对应其中的一个区域 叶子节点呢
对应的是你最小这个力度的区域 但是非叶子节点
它其实对应的也是想应的是有一个区域 比较重要的一个是
这一步是挺重要 后面会利用到 就是你在这个存储的时候啊
你这个节点不止存储有哪些点
同时还要存储一下在这个区域上面的最紧致的边界
这个bounds要把它存在你的数据里面 这是你在存的时候很容易可以
可以记的 就是可以提前存下来的
这样的是我们这个K维树的构建的方式 它有什么好处呢
它能够加速我们的查找 就是树的结构
就是我觉得天然就是为了快速的查找而存在的
-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聚类
-第八章作业



