数据挖掘导论--第5章-分类-5.2-KNN-2017

5.2最近邻分类器积极学习vs消极学习积极学习（急切学习）（EagerLearner）(1)归纳:由训练数据建立分类模型(2)演绎：把模型应用于测试样例比如，决策树和基于规则的分类器是消极学习（惰性学习）（lazylearner）把训练数据建模过程推迟到需要对样本分类时例子：Rote-learner（死记硬背）记住所有的训练数据，仅当记录的属性值与一个训练记录完全匹配才对它分类最近邻（Nearestneighbor）使用“最近”的k个点(最近邻)进行分类最近邻分类器基本思想:谚语“走路像鸭子，叫像鸭子，看起来还像鸭子，那么它很可能就是一只鸭子”Ifitwalkslikeaduck,quackslikeaduck,thenit’sprobablyaduck训练记录待分类记录计算距离选择k个“最近”的记录最近邻分类器最近邻（nearestneighbor）和测试样例的属性相对接近的所有训练记录，称为（测试样例的）的最近邻。利用最近邻可以对测试样例进行分类最近邻分类器把每个样例看做d维空间上的一个数据点，其中d是属性个数。给定一个测试样例，利用任意一种邻近性度量，计算该测试样例与训练集中其他数据点的邻近度。给定样例z的k-最近邻是指和z距离最近的k个数据点。最近邻分类器要求存放训练记录计算记录间距离的度量k值,最近邻数对未知记录分类:计算域各训练记录的距离找出k个最近邻使用最近邻的类标号决定未知记录的类标号(例如,多数表决)Unknownrecordk-最近邻分类算法k-最近邻分类算法1：令k是最近邻数目，D是训练样例的集合2：for每个测试样例z=(x',y')do3：计算z和每个样例(x,y)D之间的距离d(x',x)4：选择离z最近的k个训练样例的集合DzD5：6：endfor距离加权表决其中，I()为指示函数，期中参数为真，返回值为1，否则为0(,)argmax()iizivyDyIvyx(,)argmax()iiziivyDywIvyxk-最近邻XXX(a)1-nearestneighbor(b)2-nearestneighbor(c)3-nearestneighbor记录x的k-最近邻是与x之间距离最小的k个训练数据点---------------++++++++++++*---------------++++++++++++*---------------++++++++++++*k-最近邻k值的选择:如果k太小,则对噪声点敏感如果k太大,邻域可能包含很多其他类的点定标问题（规范化）属性可能需要规范化，防止距离度量被具有很大值域的属性所左右Xk-NN的特点k-NN的特点是一种基于实例的学习需要一个邻近性度量来确定实例间的相似性或距离不需要建立模型，但分类一个测试样例开销很大需要计算域所有训练实例之间的距离基于局部信息进行预测，对噪声非常敏感最近邻分类器可以生成任意形状的决策边界决策树和基于规则的分类器通常是直线决策边界需要适当的邻近性度量和数据预处理防止邻近性度量被某个属性左右