DM3-2K最近邻方法和Bayes方法QBai21-08-2006.ppt

K-近邻分类方法 Dr. Qingyuan Bai School of Computer Science Faculty of Mathematics and Computer Science, Fuzhou University Email: baiqy@fzu.edu.cn K- 近邻分类方法 简单概念 K-近邻基本思路 K-最近邻算法 K- 近邻分类方法也可作为预测方法 基于距离的分类方法 1.简单概念 1/3 K- 近邻分类方法特点 不是事先通过数据来学好分类模型, 再对未知样本分类，而存储带有标记的样本集，给一个没有标记的样本，用样本集中k个与之相近的样本对其进行即时分类。 由于没有事先学习出模型，所以把它称作基于要求或懒惰的学习方法。 这是一种基于示例的学习方法，一种基于类比的学习方法 1.简单概念 2/3 3. K-近邻就是找出k个相似的实例来建立目标函数逼近。这种方法为局部逼近。复杂度低，不失为一个方法。 1.简单概念--相似 3/3 4. 相似实例：什么是相似？距离近! 对于距离的计算方法有许多。 样本为 X=(x1,x2,…xn) 明考斯基距离: 曼哈坦距离: 欧氏距离： 在明考斯基距离公式中,q??,表示什么距离? 2.K-近邻基本思路 存储一些标记好的样本集 一个未知类的样本（要对其分类） 逐一取出样本集中的样本，与未知类样本比较，找到K-个与之相近的样本，就用这K-个样本的多数的类（或类分布）为未知样本定类。 在样本集为连续值时，就用K-个样本的平均值为未知样本定值。 3.K-最近邻算法 样本：用 n 维数值属性表示 每个样本为n维空间一个点 X=(x1,x2,……..xn) Y=(y1,y2,……..yn) 度量：点之间的距离（关系）表示 K-近邻算法 输入： T //训练数据( 带有类标记的样本） K //邻居的数目（给定k个近邻） t //将要被分类的元组 输出： c//元组t被分配的类别 算法://利用K-近邻（k-NN）算法对元组进行分类 N= ?; //对于元组t发现的邻居集合 for each d∈T do if |N|≤K, then N=N∪{d}; else if u∈N such that sim(t,u) ！≤sim(t, d), then begin N=N-{u};//去掉与 t 距离大的u; N=N∪{d};//加进与 t 距离小的d； end //发现分类的类别 c=class to which the most u∈N are classified;//N中的最多的类 c 赋给 t 4。K-近邻方法的优缺点 优点： （1）易于编程，且不需要优化和训练 （2）当样本增大到一定容量，k也增大到合适的程度，k-近邻的误差可与贝叶斯方法相比。 缺点： （1）在高维和数据质量较差时，k-近邻方法表现不好。 （2）当n个训练样本，n大时，计算时间太大。 如计算一个点要p次操作，每次查询都要np次计算，时间复杂度为O(np)。往往用户难以接受。 K-近邻方法对k的选择也是要靠经验，也取决于要处理的问题与背景。 5.基于距离的分类方法 1/4 近邻的含义？ 用什么方法来判断近邻也因问题不同而不同。 距离的计算? 用什么方法来判断距离，距离怎样计算，这些都是因问题而异。 基于距离的分类方法 2/4 数据样本都是用n维数值属性描述的向量。 X=(x1,x2，……xn) 每个样本代表n维空间的一个点。 这样所有的 训练样本都存放在n维模式空间中。 我们根据样本的m个类别，将同类样本计算出类 中心： Cj=(cj1,cj2, …… cjn)；j=1,2,…m 输入一个未知类别样本： Y=(y1,y2, …… yn) 判断Y的类别，将Y与Cj进行距离计算，与那个类 距离小，就是那类。计算距离方法因问题而异。 基于距离的分类方法 3/4 基于距离的分类方法 4/4 输入： C1,C2,…Cm //样本有m个类 t //未知样本 输出: C //t 属于的类