最近邻分类器VIP免费

数据挖掘1第二十讲最近邻分类器主讲：王彦October21,2024数据挖掘导论2最近邻分类器•基本思想:–找出和测试样例的属性相对接近的所有训练样例。这些训练样例称为：最近邻训练记录待分类记录计算距离选择k个“最近”的记录October21,2024数据挖掘导论3最近邻分类器•要求–存放训练记录–计算记录间距离的度量–k值,最近邻数•对未知记录分类:–计算域各训练记录的距离–找出k个最近邻–使用最近邻的类标号决定未知记录的类标号(例如,多数表决)UnknownrecordOctober21,2024数据挖掘导论4最近邻定义XXX(a)1-nearestneighbor(b)2-nearestneighbor(c)3-nearestneighbor记录x的k-最近邻是与x之间距离最小的k个训练数据点数据挖掘5k-最近邻分类•K-近邻分类方法特点–不是事先通过数据来学好分类模型,再对未知样本分类，而存储带有标记的样本集，给一个没有标记的样本，用样本集中k个与之相近的样本对其进行即时分类。–由于没有事先学习出模型，所以把它称作基于要求或懒惰的学习方法。–这是一种基于示例的学习方法，一种基于类比的学习方法–K-近邻就是找出k个相似的实例来建立目标函数逼近。这种方法为局部逼近。复杂度低，不失为一个方法。数据挖掘6k-最近邻分类•相似实例：什么是相似？对于距离的计算方法有许多。样本为X=(x1,x2,…xn)•明考斯基距离:•曼哈坦距离:•欧氏距离：•距离近就相似qqppqqjxixjxixjxixjid)||...|||(|),(2211||...||||),(2211ppjxixjxixjxixjid)||...|||(|),(2222211ppjxixjxixjxixjidOctober21,2024数据挖掘导论7k-最近邻分类算法•k-最近邻分类算法1：令k是最近邻数目，D是训练样例的集合2：for每个测试样例z=(x',y')do3：计算z和每个样例(x,y)D之间的距离d(x',x)4：选择离z最近的k个训练样例的集合DzD5：6：endfor•距离加权表决(,)argmax()iiziivyDywIvyxOctober21,2024数据挖掘导论8k-最近邻•k值的选择:–如果k太小,则对噪声点敏感–如果k太大,邻域可能包含很多其他类的点•定标问题（规范化）–属性可能需要规范化，防止距离度量被具有很大值域的属性所左右X数据挖掘9K-NN算法例子•给样本数据集T={2,4,10,12,3,20,22,21,11,24}t={18},K=41.N={2,4,10,12},d1=16,d2=14,d3=8,d4=62.d={3},比较,N={4,10,12,3},d1=14,d2=8,d3=6,d4=153.d={20},比较,N={4,10,12,20},d1=14,d2=8,d3=6,d4=24.d={22},比较,N={10,12,20,22},d1=8,d2=6,d3=2,d4=45.d={21},比较,N={12,20,22,21},d1=6,d2=2,d3=4,d4=36.d={11},比较,N={12,20,22,21},d1=6,d2=2,d3=4,d4=37.d={24},比较,N={20,22,21,24},d1=2,d2=4,d3=3,d4=6t属于{20,22,21,24}所在的类.October21,2024数据挖掘导论10k-NN的特点•k-NN的特点–是一种基于实例的学习•需要一个邻近性度量来确定实例间的相似性或距离–不需要建立模型，但分类一个测试样例开销很大•需要计算域所有训练实例之间的距离–基于局部信息进行预测，对噪声非常敏感–最近邻分类器可以生成任意形状的决策边界•决策树和基于规则的分类器通常是直线决策边界–需要适当的邻近性度量和数据预处理•防止邻近性度量被某个属性左右数据挖掘11第二十讲结束