【教学课件】第6讲机器学习.ppt

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