机器学习40讲_20_19_非参数化的局部模型K近邻
你好，我是王天一。
今天我和你分享的主题是非参数化的局部模型k近邻。
到目前为止呢，我们专栏里介绍的机器学习模型，它都属于参数模型。
他们是利用训练数据求出关于待解决问题的这个一般性的知识。
再把这些知识呢通过全局模型的结构，还有参数加以外化。
一旦说模型的结构和参数被确定了，那么这个时候呢，这个模型就不会对训练数据再产生任何的依赖性，而是可以直接用于未知数据的预测。
镜像机盒子出现呢在一定程度上打破了这种规律。
他把普世的全局特性打散，成为若干个局部特性的组合。
每个局部特性呢只能在它所覆盖的这个近邻区域之内得以保持。
这样产生的非结构化的模型，能够具有更加灵活的表示能力。
在我看来啊，局部化的核心作用就是模型复杂度，还有拟合精确性的一个折中。
如果说我把整个的输入空间看作一个大的整体区间的话，把它视为一个整体对它进行全局式的建模。
那么单个模型呢就足以描述输入输出之间的规律。
但这也不可避免的会给简单模型本身的表达能力造成比较大的限制。
一个极端的情形是什么呢？我让所有输入的输出都等于同一个常数。
不管你这个输入它到底是多少啊，只要在我的输入空间之内啊，我就直接给它赋值一个常数。
这样的模型呢显然毫无信息量可言。
但是在另一个极端呢，如果说我把局部的特性继续的来加以细化，细化到让每一个数据点都定义出不同局部特性的子区间。
那么这时候得到的结果呢就是基于实力的学习。
基于实力的学习呢，它也叫基于记忆的学习。
它学的不是明确的泛化模型，而是样本之间的关系。
当新的样本到来的时候，这种学习方式呢不会使用拟合好的这个算式。
啊，比方说一个线性的或者多项式的模型去计算输出结果啊，或者说计算输出结果的概率，而是根据这个新样本和已有的训练样本之间的关系来确定它的输出。
那么在本地化的语境里呢，这可以称作近朱者赤，近墨者黑。
在基于实力的这个学习方法当中呢，最典型的代表就是k锦林。
K近邻算法。
它可能是最简单的机器学习算法。
它将每一个训练是否是成为高维特征空间里的一个点。
那么在解决分类问题的时候呢，k近邻首先找到在这个高维空间中核心样本，也就是未知的实力，最接近的k ke训练实力。
再根据少数服从多数的原则，这个实例当中哪个类别所占的比例比较大。
然后呢将这k个实例当中出现最多的类别标签啊，分配给未知的实例，就是这么简单的一个过程啊，从原理上讲非常非常的简单。
那么从贝叶斯的角度看呢，按照少数服从多数的方式来分配类别，实际上它和后验概率的最大化。
那两者是等效的。
点击文稿呢，你可以看到k吉林算法一个简单的图例。
这里面训练数据属于两个不同的类别啊，分别用蓝色的方框，还有红色的三角形来表示。
绿色圆圈呢它代表的是待分类的数据点啊，也就是新样本要用k近邻算法进行分类的话可以看到当k等于三啊，也就是我选择三个近邻的时候，离未知数据最近的三个点是两红一蓝，所以呢数据会被归类为红色的三角。
可是当这个k从三增加到五的时候啊，这时候多出来的这两个近邻都是蓝色的。
这样呢就会导致分类结果发生一个逆转。
这个例子说明了k近零算法的一个特点啊，也就是超参数k对性能的影响。
作为一种局部的加权模型，k近邻本身它并不形成关于数据生成机制的全局性的假设。
啊，我不知道它是怎么来的，我也不想知道。
它作用是什么呢？是刻画了数据在不同局部结构上的规律。
那么这个局部结构的范围就是由k来定义的。
本质上说超参数k和镜像集核啊，还有其他各式各样的核函数都是一样的。
只不过镜像集合呢在定义局部结构的时候，它使用的是连续分布的圈值。
所有的数据对局部特征，它都有或大或小的一个贡献。
离得近的话贡献比较大啊，那么离得远的话贡献就比较小。
相比之下，KG零使用的呢是离散分布的圈值，只有那一部分足够接近的数据，才有资格去定义局部特征。
从这个角度看，它也可以看成是可变带宽的一个镜像集合。
啊，我的带宽不是固定的，它会根据每一个数据点不同的特性而发生变化。
另一方面呢，超参数k它也表示了模型的复杂度，准确的说它是和模型的复杂度成一个反比的关系。
如果说训练集的容量为大n,那么算法的有效参数的数目就可以近似的表示为n除以k k均值的分类结果。
它实质上是近邻区域当中多个训练实力的平均越大的k值，意味着近邻区域包含的点数越多，那它的平均化的程度也就越高。
平均化程度高有什么好处呢？对于训练实例当中，噪声的平滑效果会更好，相应的这个模型的复杂度也就越低。
那么k的一个极端取值是它直接等于训练集的容量。
这相当于用所有的数据共同定义了同一个局部结构啊，也就是整个的输入空间。
这时候呢k金林就会退化，成为稳定的全局模型。
反过来，越小的k值意味着近邻的区域呢越狭窄，它平均化的程度也就越低。
这时候分类结果只由离未知数据点比较近的那几个少量的训练实例来决定。
这样的话呢就更容易受到实力当中噪声的影响也会表现出更强的过拟合倾向。
当k等于一的时候啊，未知数据的类别只取决于离它最近的这个训练实例。
这时候呢我们可以画出每个训练实例，它所对应的近邻边界，所有的近邻边界共同构成了对特征空间的一个walal内的划分。
当训练实力较多的时候，这种一技零算法计算出来的边界会非常复杂，淡化性能呢自然也比较差。
除了超参数k之外，k近零算法的另一个变量是对距离的定义方式，也就是如何衡量哪些点才算是近邻的这个标准。
最常用的距离度量呢无疑是这个欧式距离啊，也就是我们常见的这个意义上的距离。
除此之外，明可夫斯基距离、曼哈顿距离，还有马氏距离都可以应用到k几零算法当中。
那么不同的距离，度量代表的其实是对于相似性的一个不同的理解啊，我怎么来定义相似性呢？那么不同的距离实际上给出了不同的说法。
那么在不同意义的相似性之下啊，它的分类结果往往也会有所区别。
这些距离是如何来定义的呢？那么你可以自己去查阅相关的资料，对于距离的依赖性，给k金零算法带来了一个新问题，那就是为数灾难。
在之前介绍维数灾难的时候，我曾经留过一个扣啊，那么现在呢就到时候来解开它了。
简而言之，维数灾难对k近邻算法的影响在于说在高维空间当中啊，曾经的近邻并没有那么近了。
不管特征空间的维数是多少啊，你的近邻区域它的维度和特征空间的维度都是一致的。
特征要是一维啊，那我这个近邻区域就是一维，特征是一百维呢，我的近邻区域也要覆盖到相应的一百维。
那么在这个前提之下，想要在特征维度增加的时候，维持对于特征空间的覆盖率不变。
近邻区域它在每个维度上的尺度就会随着维度的增加，变得越来越大维数。
灾难的几何意义呢其实也可以直观的想象出来。
假设特征空间，它是一条单位长度的这个一维直线啊，那么任意一个长度为零点一的线段，都能够覆盖到这个特征空间之上，百分之十的区域。
可是一旦说特征空间变成二维的话，要在一个面积为一啊，也就是边长为一的正方形里圈出一个面积为零点一的小正方形，这个小正方形的边长就多少呢？零点一开根号等于零点三一六。
在一维的情况下啊，我只需要一条长度为零点一的直线，就能够覆盖整个特征空间的百分之十。
但维度增加到二维的时候啊，我同样覆盖百分之十，这个比例啊需要的长度就变成了零点三。
这样一来呢，在数据点的数目不变的情况下，维度的升高会导致原始的低维近邻点它变得越来越稀疏。
由近邻点所定义的局部结构也会越来越大。
这样的话，这种局部结构它其实就不再具有局部的含义了。
不再具有局部含义呢，想让算法保证精确的分类性能也就越来越困难。
解决维数灾难呢最直接有效的方式就是增加数据点的数量。
啊，我增加训练数据，把整个的高维空间全都给填满。
这时候呢就不存在所谓灾难的问题。
但是当数据点的数量没有办法增加的时候，我们就得退而求其次，想办法呢来降低特征空间的维度。
你不是维数灾难吗？那我把你的维数降下来啊，这灾难自然而然就消解掉。
那你还记得降维的主要方法吗？特征选择和特征提取都可以用来对k近零算法进行数据的预处理。
作为典型的非参数方法，k近零算法的运行方式和以线性回归为代表的这个参数方法呢是截然相反。
线性回归的运算量主要花在参数的拟合上。
我用大量的训练数据来拟合出一组军方误差最小的这样的参数。
一旦这一组参数被计算出来，那训练数据它的历史使命就完成了。
新来的数据都可以直接用这种参数来进行处理。
但是对于k七零来说呢，它的训练过程没有那么复杂，只需要把所有的数据点给它存储下来，就OK了。
但是一旦进来一个新样本啊，我要对这个新样本进行分类的时候，k近零算法就要找到离它最近的这k个训练实例。
你要是连近邻都找不到，还怎么去做分类啊？找到这k ke训练实例，这才是算法。
它最主要的一个运算负荷，虽说都属于这个频率主义的方法，但是以核函数和k近林为代表的这个非参数方法呢，也可以用来完成贝叶斯统计当中概率密度估计的一个任务。
如果说用参数方法来进行密度估计呢，我首先需要确定待估计的概率密度的形式，再根据训练数据来计算它的数字特征。
比方说啊我已经假定了这个概率密度，它就是一个正态。
接下来呢这个任务就是利用训练数据来估计它的均值，还有方差。
再比如说我假定这个概率密度已经具有指数分布的形式，那么训练数据的作用就是用来估计指数分布的这个参数。
显然，参数化的密度估计对于概率密度形式的假设具有很强的依赖性，我依赖于这个先验。
如果说对于概率分布的形式本身就判断错误的话，那系数计算的再精确，得到的结果也只能是南辕北辙啊，差的越来越多。
相比之下呢，非参数的密度估计就不会对待，估计的分布做出什么鲜艳。
假设啊它只有一个假设所有数据满足独立同分布的条件啊，要是连这个基础假设都没有的话啊，那也就不用去学习了。
这种方法呢具有更高的灵活性，要讨论非参数的密度估计方法啊，我们还是要从一种参数方法啊直方图来说起。
在统计学生成绩的时候呢，我们会通常对这个分数来划分一个分数段来计算。
小于六十分六十分到七十分七七十到八十十分八十分到九十啊，以以九九十分以上这五个分段段内各有多少人通过这个数据来大致的绘除成绩的一个分布。
那么这么得到的结果呢，就是一个典型的直方图。
直方图的方法，它是将样本的取值范围划分成若干个等间隔的子区间。
然后呢，再统计出现在每个子区间上样本的数目。
那么在直方图上第i个字区间，它上面的概率可以表示成NI除以大n啊，再除以德耳塔。
这里面呢NI是落在这个子区间当中的样本，数目大n是整个的样本容量。
那么delta呢表示的是每个子区间的宽度，这个德耳塔决定了直方图的分辨率。
如果德耳塔取值太小呢，会让直直图图过于细腻，让过多的局部细掩掩盖掉。
分布的整体趋取值过大，又会让直方图过于平滑，体现不出潜在的多模式的结构。
所以说要对概率密度做出精确的估计呢，必须要选择合适的区间宽度。
那这也是一个涉及到超参数选择的问题。
直方图方法啊，它的一个问题在于说它计算出来的概率密度不是连续的函数。
我既然已经将样本的取值范围划分成若干个子区间啊，那么得到的结果也对应着这个子区间的结果啊是离散的。
要解决这个问题呢，就可以将原始的样条子区间啊替换成平滑的连续函数。
在每个子序间之上啊，我不是单独的使用一个数值来表示它啊，而是用一个高斯型的这个连续函数啊或者其他形式的连续函数来对它进行建模。
这样做的好处就可以让整体的概率密度等于所有局部概率密度的叠加，从而呢避免了不连续点的出现。
那么用来插值的这个连续函数应该满足什么样的条件呢？这个平滑的特性，连续的特性决定了它不能只管自己啊也要刻画数据的局部特性。
那么刻画局部特性的工具是什么呢？就是恒安数嘛，把核函数用于密度估计，就是非参数化的这个核密度估计方法。
点击文稿。
你可以看到直方图，还有核密度估计的一个示意图。
但光有核函数不够啊，我们还需要确定它的带宽。
在密度估计当中，核函数的带宽和这个直方图的子区间，它的宽度类似，都决定了局部结构的范围。
如果核安柱的带宽过大，那会导致过度的平滑。
带宽过小呢则会导致欠平化啊，那么在实际应用当中呢，也可以通过最优化类似于均方误差的指标来进行确定核密度估计。
啊，在算出连续概率密度的同时啊，它也会带来新的问题啊，你解决一个问题，总归要付出一点代价，那就是所有的局部结构都由相同的贷款所定义。
从这个角度来看呢，它仍然是一个参数化的模型。
但是在特征空间之上啊，我不同区域的数据的密度不同，它的局部结构也应该有所区别。
这呢就对应着KG零算法的思想。
在基于近邻的这个密度估计当中，近零点的数目k是唯一的参数。
每个数据点的带宽呢就是第k个近邻点和它的距离。
那么和核密度估计当中的带宽一样，这个k值同样定义了局部结构的性质。
所以在选择的时候呢也要慎重又慎重。
不管是核密度估计还是近邻密度估计，都可以从一个统一的宏观视角来加以审视。
在高维空间当中，如果将数据x的局部结构定义为二，那么它的概率密度就可以表示成为PX,等于k除以NV.这里面呢k表示了局部结构，r中数据点的数目，v呢表示了r的体积，它们实际上都是不确定的量。
如果说设置成v固定k可变来，估计这个概率密度这时候得到的呢就是核密度估计啊，相当于我提前把这个局部结构给它定义好了。
如果说设置成为k固定v可变来估计概率密度就是近邻密度估计，相当于我把这个近邻的数目先给大家确定好。
当样本数量n趋近于正无穷的时候，体积b会随着n的增加而缩小，来保证r上的概率密度是一个常数。
我在一个局部结构，它真正具有局部的特性。
反过来k呢则会随着n的增加而增加，以保证r上面的概率密度存在一个明显的峰值。
这时候呢只要数据越来越多，这两种非参数的估计结果都会渐渐的收敛到真实的概率密度上，和支持限量机一样。
那k麒零算法呢也通常用来解决分类问题。
利用SK learn当中的k neighbors, classifially可以计算出曼城希布朗数据集，也就是这个线性不可分的数据集当中的分类边界。
这里面呢超参数k的取值被设置为一七，还有十五啊，这样三个取值可以看到啊。
当k等于一的时候，所有的训练数据都能够被正确分类，那这是由它的特性决定。
而当k等于十五的时候呢，误分类率会超过百分之十。
这说明呢当超参数k的取值逐渐变大的时候，训练数据的误分类率实际上是在不断的上升的。
但是观察这个图形你也会发现计算出来的分类边界，它也会变得越来越平滑。
这实际上呢就是偏差和方差折中的一个典型的体现。
点击文稿，你可以看到KG零算法的分类结果。
今天我和你分享的基于实例的学习方法以及它的典型代表KG零算法包含着以下四个要点。
第一，基于实例的学习方法学的不是明确的泛化模型，而是样本之间的关系。
第二，KG零算法是非参数的局部化模型，具有无需训练的优点。
但是对新样本进行分类的时候呢，计算复杂度比较高。
第三，k技零算法的性能取决于超参数k的取值和距离的定义方式。
第四，核方法和近邻算法都可以用于数据的概率密度。
估计k金林算法呢它是一种消极学习的方法，他并不会从训练数据里直接获取泛化的决策，而是要把它延迟到新样本出现的时候。
那么前面介绍的其他方法相比之下呢都属于积极学习方法。
在新样本出现之前就做好了泛化工作。
那么，你觉得消极方法和积极方法在原理和性能上各自存在着哪些优缺点呢？欢迎分享你的观点。