湖南省做网站那个企业便宜,上海房产网二手房出售,上海公司有哪些,本地人才招聘网K近邻法(k-nearst neighbors,KNN)是一种很基本的机器学习方法了#xff0c;在我们平常的生活中也会不自主的应用。比如#xff0c;我们判断一个人的人品#xff0c;只需要观察他来往最密切的几个人的人品好坏就可以得出了。这里就运用了KNN的思想。KNN方法既可以做分类…K近邻法(k-nearst neighbors,KNN)是一种很基本的机器学习方法了在我们平常的生活中也会不自主的应用。比如我们判断一个人的人品只需要观察他来往最密切的几个人的人品好坏就可以得出了。这里就运用了KNN的思想。KNN方法既可以做分类也可以做回归这点和决策树算法相同。
KNN做回归和分类的主要区别在于最后做预测时候的决策方式不同。KNN做分类预测时一般是选择多数表决法即训练集里和预测的样本特征最近的K个样本预测为里面有最多类别数的类别。而KNN做回归时一般是选择平均法即最近的K个样本的样本输出的平均值作为回归预测值。由于两者区别不大虽然本文主要是讲解KNN的分类方法但思想对KNN的回归方法也适用。由于scikit-learn里只使用了蛮力实现(brute-force)KD树实现(KDTree)和球树(BallTree)实现本文只讨论这几种算法的实现原理。其余的实现方法比如BBF树MVP树等在这里不做讨论。 KNN算法原理
1.从训练数据集合中获取K个离待预测样本距离最近的样本数据2.根据获取得到的K个样本数据来预测当前待预测样本的目标属性值。
如下图绿色圆是要被决定赋予哪个类如果K3由于红色三角形所占比例为2/3绿色圆就被认为是红色三角形类如果K5由于蓝色正方形所占比例为3/5蓝色圆就被认为是蓝色正方形类。 在理想情况下K值选择为1即值选择最近邻居。在现实生活中往往没有这么理想比如对于价格来说有些孤噩消息闭塞可以回为“最近邻居”多付很多钱所以应当货币三家多选一些邻居取均值来减少噪声。实际上K值过大过小都会影响最终结果。
KNN算法三要素
KNN算法我们主要要考虑三个重要的要素对于固定的训练集只要这三点确定了算法的预测方式也就决定了。这三个最终的要素是k值的选取距离度量的方式和分类决策规则。
分类决策规则在分类模型中主要使用多数表决法或者加权多数表决法在回归模型中主要使用平均值法或者加权平均值法。
对于k值的选择没有一个固定的经验一般根据样本的分布选择一个较小的值可以通过交叉验证选择一个合适的k值。选择较小的k值就相当于用较小的领域中的训练实例进行预测训练误差会减小只有与输入实例较近或相似的训练实例才会对预测结果起作用与此同时带来的问题是泛化误差会增大换句话说K值的减小就意味着整体模型变得复杂容易发生过拟合选择较大的k值就相当于用较大领域中的训练实例进行预测其优点是可以减少泛化误差但缺点是训练误差会增大。这时候与输入实例较远不相似的训练实例也会对预测器作用使预测发生错误且K值的增大就意味着整体的模型变得简单。一个极端是k等于样本数m则完全没有分类此时无论输入实例是什么都只是简单的预测它属于在训练实例中最多的类模型过于简单。
对于距离的度量我们有很多的距离度量方式但最常用的是欧式距离即对于两个n维向量x和y两者的欧式距离定义为 大多数情况下欧式距离可以满足我们的需求我们不需要再去操心距离的度量。当然我们也可以用他的距离度量方式。比如曼哈顿距离: 更加通用点比如闵可夫斯基距离(Minkowski Distance)定义为 可以看出欧式距离是闵可夫斯基距离距离在p2时的特例而曼哈顿距离是p1时的特例。
KNN分类预测规则
KNN在分类应用中一般采用多数表决法或者加权多数表决法。
多数表决法每个邻近样本的权重一样的也就是说最终预测的结果为出现类别最多的那个类比如下图中蓝色最终类别为红色加权多数表决法每个邻近样本的权重是不一样的一般情况下采用权重和距离成反比的方式来计算也就是说最终预测结果是出现权重最大的那个类别。比如下图中假设三个红色点到待预测样本的距离为2两个黄色点到待预测样本点距离为1那么蓝色圆最终的类别是黄色。KNN回归预测规则
在KNN回归应用中一般采用平均值法或是加权平均值法。
平均值法每个邻近样本的权重是一样的也就是说最终预测的结果为所有邻近样本的目标值比如下图中蓝色圆圈的最终预测值为2.6加权平均值法每个邻近样本的权重是不一样的一般情况下采用权重和距离惩罚比的方式计算也就是数在计算均值的时候进行加权操作比如下图假设上面三个点到待预测样本点的距离均为2下面两个点到待预测样本点距离为1那么蓝色圆圈的最终预测值为2.43权重分别为1/7和2/7KNN算法实现方式
KNN算法的重点在于找出k个最邻近的点主要方式有以下几种
蛮力实现brute计算预测样本到所有训练集样本的距离然后选择最小的K个距离即可得到k个最近邻点。缺点在于当特征数比较多、样本数比较多的时候算法 的执行效率比较低。KD树kd_treeKD树算法中首先是对训练数据进行建模构建KD树然后在根据建好的模型来获取邻近样本的数据。
除此之外还有一些从KD_Tree修改后的求解最邻近点的算法比如Ball Tree、BBF Tree、MVP Tree等
KNN算法蛮力实现
既然我们要找到k个最近的邻居来做预测那么我们只需要计算预测样本和所有训练集中的样本的距离然后计算出最小的k个距离即可接着多数表决很容易做出预测。这个方法的确简单直接在样本量少样本特征少的时候有效。但是在实际运用中很多时候用不上为什么呢因为我们经常碰到样本的特征数有上千以上样本量有几十万以上如果我们这要去预测少量的测试集样本算法的时间效率很成问题。因此这个方法我们一般称之为蛮力实现。比较适合于少量样本的简单模型的时候用。
KNN算法之KD树实现原理
KD树算法没有一开始就尝试对测试样本分类而是先对训练集建模建立的模型就是KD树建好了模型再对测试集做预测。所谓的KD树就是K个特征维度的树注意这里的K和KNN中的K的意思不同。KNN中的K代表特征输出类别KD树中的K代表样本特征的维数。为了防止混淆后面我们称特征维数为n。
KD树算法包括三步第一步是建树第二部是搜索最近邻最后一步是预测。
KD树的建立
我们首先来看建树的方法。KD树建树采用的是从m个样本的n维特征中分别计算n个特征的取值的方差用方差最大的第k维特征来作为根节点。对于这个特征我们选择特征的取值的中位数对应的样本作为划分点对于所有第k维特征的取值小于的样本我们划入左子树对于第k维特征的取值大于等于的样本我们划入右子树对于左子树和右子树我们采用和刚才同样的办法来找方差最大的特征来做更节点递归的生成KD树。
具体流程如下图 比如我们有二维样本6个{(2,3)(5,4)(9,6)(4,7)(8,1)(7,2)}构建kd树的具体步骤为
找到划分的特征。6个数据点在xy维度上的数据方差分别为6.975.37所以在x轴上方差更大用第1维特征建树。确定划分点7,2。根据x维上的值将数据排序6个数据的中值(所谓中值即中间大小的值)为7所以划分点的数据是7,2。这样该节点的分割超平面就是通过7,2并垂直于划分点维度的直线x7确定左子空间和右子空间。 分割超平面x7将整个空间分为两部分x7的部分为左子空间包含3个节点{(2,3),(5,4),(4,7)}另一部分为右子空间包含2个节点{(9,6)(8,1)}。用同样的办法划分左子树的节点{(2,3),(5,4),(4,7)}和右子树的节点{(9,6)(8,1)}。最终得到KD树。
最后得到的KD树如下 KD树搜索最近邻
当我们生成KD树以后就可以去预测测试集里面的样本目标点了。对于一个目标点我们首先在KD树里面找到包含目标点的叶子节点。以目标点为圆心以目标点到叶子节点样本实例的距离为半径得到一个超球体最近邻的点一定在这个超球体内部。然后返回叶子节点的父节点检查另一个子节点包含的超矩形体是否和超球体相交如果相交就到这个子节点寻找是否有更加近的近邻,有的话就更新最近邻。如果不相交那就简单了我们直接返回父节点的父节点在另一个子树继续搜索最近邻。当回溯到根节点时算法结束此时保存的最近邻节点就是最终的最近邻。
从上面的描述可以看出KD树划分后可以大大减少无效的最近邻搜索很多样本点由于所在的超矩形体和超球体不相交根本不需要计算距离。大大节省了计算时间。
我们用建立的KD树来看对点(2,4.5)找最近邻的过程。
先进行二叉查找先从7,2查找到5,4节点在进行查找时是由y 4为分割超平面的由于查找点为y值为4.5因此进入右子空间查找到4,7形成搜索路径(7,2)(5,4)(4,7)但 4,7与目标查找点的距离为3.202而5,4与查找点之间的距离为3.041所以5,4为查询点的最近点 以24.5为圆心以3.041为半径作圆如下图所示。可见该圆和y 4超平面交割所以需要进入5,4左子空间进行查找也就是将2,3节点加入搜索路径中得(7,2)(2,3)于是接着搜索至2,3叶子节点2,3距离2,4.5比5,4要近所以最近邻点更新为23最近距离更新为1.5回溯查找至5,4直到最后回溯到根结点7,2的时候以2,4.5为圆心1.5为半径作圆并不和x 7分割超平面交割如下图所示。至此搜索路径回溯完返回最近邻点2,3最近距离1.5。
对应的图如下 KD树预测
有了KD树搜索最近邻的办法KD树的预测就很简单了在KD树搜索最近邻的基础上我们选择到了第一个最近邻样本就把它置为已选。在第二轮中我们忽略置为已选的样本重新选择最近邻这样跑k次就得到了目标的K个最近邻然后根据多数表决法如果是KNN分类预测为K个最近邻里面有最多类别数的类别。如果是KNN回归用K个最近邻样本输出的平均值作为回归预测值。
KNN算法之球树实现原理
KD树算法虽然提高了KNN搜索的效率但是在某些时候效率并不高比如当处理不均匀分布的数据集时,不管是近似方形还是矩形甚至正方形都不是最好的使用形状因为他们都有角。一个例子如下图 如果黑色的实例点离目标点星点再远一点那么虚线圆会如红线所示那样扩大导致与左上方矩形的右下角相交既然相 交了那么就要检查这个左上方矩形而实际上最近的点离星点的距离很近检查左上方矩形区域已是多余。于此我们看见KD树把二维平面划分成一个一个矩形但矩形区域的角却是个难以处理的问题。
为了优化超矩形体导致的搜索效率的问题牛人们引入了球树这种结构可以优化上面的这种问题。
我们现在来看看球树建树和搜索最近邻的算法。
球树的建立
球树顾名思义就是每个分割块都是超球体而不是KD树里面的超矩形体。 我们看看具体的建树流程
先构建一个超球体这个超球体是可以包含所有样本的最小球体。从球中选择一个离球的中心最远的点然后选择第二个点离第一个点最远将球中所有的点分配到离这两个聚类中心最近的一个上然后计算每个聚类的中心以及聚类能够包含它所有数据点所需的最小半径。这样我们得到了两个子超球体和KD树里面的左右子树对应。对于这两个子超球体递归执行步骤2). 最终得到了一个球树。
可以看出KD树和球树类似主要区别在于球树得到的是节点样本组成的最小超球体而KD得到的是节点样本组成的超矩形体这个超球体要与对应的KD树的超矩形体小这样在做最近邻搜索的时候可以避免一些无谓的搜索。
球树搜索最近邻
使用球树找出给定目标点的最近邻方法是首先自上而下贯穿整棵树找出包含目标点所在的叶子并在这个球里找出与目标点最邻近的点这将确定出目标点距离它的最近邻点的一个上限值然后跟KD树查找一样检查兄弟结点如果目标点到兄弟结点中心的距离超过兄弟结点的半径与当前的上限值之和那么兄弟结点里不可能存在一个更近的点否则的话必须进一步检查位于兄弟结点以下的子树。
检查完兄弟节点后我们向父节点回溯继续搜索最小邻近值。当回溯到根节点时此时的最小邻近值就是最终的搜索结果。
从上面的描述可以看出KD树在搜索路径优化时使用的是两点之间的距离来判断而球树使用的是两边之和大于第三边来判断相对来说球树的判断更加复杂但是却避免了更多的搜索这是一个权衡。
KNN算法的扩展
这里我们再讨论下KNN算法的扩展限定半径最近邻算法。
有时候我们会遇到这样的问题即样本中某系类别的样本非常的少甚至少于K这导致稀有类别样本在找K个最近邻的时候会把距离其实较远的其他样本考虑进来而导致预测不准确。为了解决这个问题我们限定最近邻的一个最大距离也就是说我们只在一个距离范围内搜索所有的最近邻这避免了上述问题。这个距离我们一般称为限定半径。
接着我们再讨论下另一种扩展最近质心算法。这个算法比KNN还简单。它首先把样本按输出类别归类。对于第 L类的个样本。它会对这个样本的n维特征中每一维特征求平均值最终该类别所有维度的n个平均值形成所谓的质心点。对于样本中的所有出现的类别每个类别会最终得到一个质心点。当我们做预测时仅仅需要比较预测样本和这些质心的距离最小的距离对于的质心类别即为预测的类别。这个算法通常用在文本分类处理上。
KNN算法小结
KNN算法是很基本的机器学习算法了它非常容易学习在维度很高的时候也有很好的分类效率因此运用也很广泛\
KNN的主要优点有
理论成熟思想简单既可以用来做分类也可以用来做回归可用于非线性分类训练时间复杂度比支持向量机之类的算法低仅为O(n)和朴素贝叶斯之类的算法比对数据没有假设准确度高对异常点不敏感由于KNN方法主要靠周围有限的邻近的样本而不是靠判别类域的方法来确定所属类别的因此对于类域的交叉或重叠较多的待分样本集来说KNN方法较其他方法更为适合该算法比较适用于样本容量比较大的类域的自动分类而那些样本容量较小的类域采用这种算法比较容易产生误分
KNN的主要缺点有
计算量大尤其是特征数非常多的时候样本不平衡的时候对稀有类别的预测准确率低KD树球树之类的模型建立需要大量的内存使用懒散学习方法基本上不学习导致预测时速度比起逻辑回归之类的算法慢相比决策树模型KNN模型可解释性不强
