文档介绍：K近邻分类算法
1 算法的提出与发展
最初的近邻法是由Cover和Hart与1968年提出的,随后得到理论上深入的分析与研究,是非参数法中最重要的方法之一。
2 算法原理
基本原理
最近邻方法(k-nearest neighbor,简称kNN)是一种简洁而有效的非参数分类方法,是最简单的机器学习算法之一,该算法最初由Cover和Hart提出的,用于解决文本的分类问题。 K 近邻算法是最近邻算法的一个推广。该规则将是一个测试数据点x分类为与它最接近的 K 个近邻中出现最多的那个类别。K 近邻算法从测试样本点x开始生长,不断的扩大区域,直到包含进 K 个训练样本点为止,并且把测试样本点x归为这最近的 K 个训练样本点中出现频率最大的类别。其中测试样本与训练样本的相似度一般使用欧式距离测量。如果 K 值固定,并且允许训练样本个数趋向于无穷大,那么,所有的这 K 个近邻都将收敛于x。如同最近邻规则一样,K 个近邻的标记都是随机变量,概率P(wi|x),i=1,2,…,K都是相互独立的。假设P(wm|x)是较大的那个后验概率,那么根据贝叶斯分类规则,则选取类别wm。而最近邻规则以概率P(wm|x)选取类别。而根据K近邻规则,只有当K个最近邻中的大多数的标记记为wm,才判定为类别wm。做出这样断定的概率为
通常K值越大,选择类别wm概率也越大。
K值的选择
K近邻规则可以被看作是另一种从样本中估计后验概率P(wi|x)的方法。为了得到可高的估计必须是的K值越大越好。另一方面,又希望又希望x的 K 个近邻x 距离x1 越近越好,因为这样才能保证P(wi|x1)尽可能逼近P(wi|x)。在选取 K 值的时候,就不得不做出某种折衷。只有当n趋近于无穷大时,才能保证 K 近邻规则几乎是最优的分类规则。 K值的选择:需要消除K值过低,预测目标容易产生变动性,同时高k值时,预测目标有过平滑现象。推定k值的有益途径是通过有效参数的数目这个概念。有效参数的数目是和k值相关的,大致等于n/k,其中,n是这个训练数据集中实例的数目。
确定K的值:通过实验确定。进行若干次实验,取分类误差率最小的k值。算法步骤
1) 依公式计算 Item 与 D1、D2 ……、Dj 之相似度。得到Sim(Item, D1)、Sim(Item, D2)
……、Sim(Item, Dj)。
2) 将Sim(Item, D1)、Sim(Item, D2)……、Sim(Item, Dj)排序,若是超过相似度门槛t则放入邻居案例集合NN。
3) 自邻居案例集合NN中取出前k名,依多数决,得到Item可能类别。
3 KNN优缺点
优点:1)原理简单,实现起来比较方便;
2)支持增量学习;
3)能对超多边形的复杂决策空间建模。
缺点:1)样本的不均衡可能造成结果错误:如果一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数。
2)计算量较大,需要有效的存储技术和并行硬件的支撑:因为对每一个待分类的文本都要计算它到全体已知样本的距离,才能求得它的K个最近邻点。
4 KNN的改进
针对上述KNN算法的几个主要缺陷,主要有以下三类改进方法:
1)为