《【教学课件】第6讲机器学习.ppt》由会员分享,可在线阅读,更多相关《【教学课件】第6讲机器学习.ppt(15页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第6讲 机器学习1K-近邻学习概述不同于eager学习算法,K-近邻方法在训练阶段只是简单地把训练样例存储起来,把建模过程推迟到了要预测新实例的工作阶段。因此,K-近邻方法是一种典型的lazy学习算法。k-近邻方法既可以用于目标函数值是离散的情况,也可以用于是连续的情况。离散的情况就是分类,连续的情况就是回归。K-近邻方法的学习过程分两部:1)找到要预测新实例的K个邻居;2)根据这K个邻居来预测新实例的目标值。2k-近邻算法k-近邻算法假定所有的实例对应于n维空间Rn中的点,任意的实例表示为一个特征向量根据欧氏距离定义实例间的距离。两个实例xi和xj的距离d(xi,xj)定义为3伪代码(离散)
2、考虑离散目标函数f:RnV,V=v1,.,vs逼近离散值函数f:RnV的k-近邻算法训练算法将每个训练样例加入到列表training_examples分类算法给定一个要分类的查询实例xq在training_examples中选出最靠近xq的k个实例,并用x1.xk表示返回 其中4伪代码(连续)逼近连续值目标函数f:RnR的k-近邻算法训练算法将每个训练样例加入到列表training_examples分类算法给定一个要分类的查询实例xq在training_examples中选出最靠近xq的k个实例,并用x1.xk表示返回5距离加权的k-近邻算法(离散)对k-近邻算法的一个改进是对k个近邻的贡献加
3、权,越近的距离赋予越大的权值,比如:其中为了处理查询点xq恰好匹配某个训练样例xi,从而导致d(xq,xi)2为0的情况,令这种情况下的 等于f(xi),如果有多个这样的训练样例,我们使用它们占多数的分类。6距离加权的k-近邻算法(连续)对k-近邻算法的一个改进是对k个近邻的贡献加权,越近的距离赋予越大的权值,比如:其中 为了处理查询点xq恰好匹配某个训练样例xi,从而导致d(xq,xi)2为0的情况,令这种情况下的 等于f(xi),如果有多个这样的训练样例,则用它们的平均值来预测。7对k-近邻算法的的说明k-近邻算法的所有变体都只考虑k个近邻用以预测查询点,如果使用按距离加权,那么可以允许所
4、有的训练样例影响对xq的预测,因为非常远的实例的影响很小。唯一不足之处:使得预测的速度变得更慢。如果预测一个新实例时,考虑所有的训练样例,我们称为全局法;如果仅考虑靠近的训练样例,称为局部法。8k-近邻算法的优点K-近邻算法不是在整个实例空间上一次性地预测目标函数值,而是针对每个待预测的新实例,建立不同的目标函数逼近,作出局部的和相异的预测。这样做的好处是:有时目标函数很复杂,但具有不太复杂的局部逼近。距离加权的k-近邻算法对训练数据中的噪声有很好的健壮性,通过取k个近邻的加权平均,可以消除孤立的噪声样例的影响。9k-近邻算法的不足K-近邻方法的不足之处体现在:应用K-近邻算法来进行预测的时候
5、,经常会遇到很多现实问题。这些问题包括:维度灾害问题、近邻索引问题、近邻大小问题、计算效率问题、归纳偏置问题。10维度灾害问题k-近邻算法的一个实践问题:维度灾害许多学习方法,比如决策树方法,选择部分属性作出判断,而k-近邻方法中实例间的距离是根据实例的所有属性计算的。实例间距离会被大量的不相关属性所支配,可能导致相关属性的值很接近的实例相距很远。解决维度灾害问题的常用方法:1)属性加权;2)属性选择。11近邻索引问题k-近邻算法的所有计算几乎都花费在索引近邻问题上。因此,如何建立高效的索引是k-近邻算法的另外一个实践问题。目前,已经开发了很多对存储的训练样例进行索引的方法,以便能高效地确定最近邻。如kd-tree把实例存储在树的叶结点内,邻近的实例存储在同一个或附近的节点内,通过测试新查询xq的选定属性,树的内部节点把查询xq排列到相关的叶结点。12近邻大小问题k-近邻算法的预测结果与k的大小相关。同样的数据,K值不同可能导致不同的预测结果。13计算效率问题k-近邻算法推迟所有的计算处理,直到接收到一个新的查询,所以处理每个新查询可能需要大量的计算。14归纳偏置问题k-近邻算法的归纳偏置是:一个实例的分类xq与在欧氏空间中它附近的实例的分类相似。15
限制150内