最近邻分类算法

1、数据挖掘算法,K,最近邻分类,(KNN),?,K,最近邻分类（,KNN,）,?,该方法的思路是：如果一个样本在特征空间中的,k,个最相近,(,即特征,空间中最邻近,),的样本中的大多数属于某一个类别，则该样本也属于,这个类别。即,“近朱者赤，近墨者黑”，由你的邻居来推断出你,的类别。,?,用下面的谚语最能说明：,“,如果走像鸭子，叫像鸭子，看起来还像鸭,子，那么它很可能就是一只鸭子。,”,?,K,值选取,?,?,k,值通常是采用交叉检验来确定（以,k=1,为基准）,交叉验证的概念：将数据样本的一部分作为训练样本，一部分作为测试样本，比如选择,95%,作为,训练样本，剩下的用作测试样本。通过训练

2、数据训练一个模型，然后利用测试数据测试其误差率。,cross-validate,（交叉验证）误差统计选择法就是比较不同,K,值时的交叉验证平均误差率，选择误,差率最小的那个,K,值。例如选择,K=1,2,3,.,，,对每个,K=i,做,100,次交叉验证，计算出平均误差，,然后比较、选出最小的那个。,?,?,经验规则：,k,一般低于训练样本数的平方根。,需要指出的是：取,k=1,常常会得到比其他值好的结果，特别是在小,数据集中。,?,不过仍然要注意：在样本充足的情况下，选择较大的,K,值能提高抗,躁能力。,?,欧氏距离,?,计算距离有许多种不同的方法，如欧氏距离、余弦距离、,汉明距离、曼哈顿距

3、离等等，传统上，,kNN,算法采用的,是欧式距离。,?,也称欧几里得距离，它是一个采用的距离定义，他是在,维空间中两个点之间的真实距离。,?,d,?,(,x,1,?,x,2,),?,(,y,1,?,y,2,),二维的公式：,2,2,?,计算步骤如下：,?,?,1.,计算未知样本和每个训练样本的距离,dist,2.,得到目前,K,个最临近样本中的最大距离,maxdist,?,3.,如果,dist,小于,maxdist,，则将该训练样本作为,K-,最近邻,样本,?,4.,重复步骤,2,、,3,、,4,，直到未知样本和所有训练样本的,距离都算完,?,5.,统计,K,个最近邻样本中每个类别出现的次数,

4、?,注意：,?,该算法不需要花费时间做模型的构建。其他大多数分类,算法，如决策树等都需要构建模型的阶段，而且该阶段,非常耗时，但是它们在分类的时候非常省时。,?,类别的判定,?,投票决定,：,少数服从多数，近邻中哪个类别的点最多就,分为该类。,?,如果训练数据大部分都属于某一类，投票算法就有很大问题了。这,时候就需要考虑设计每个投票者票的权重了。,?,加权投票法：,根据距离的远近，对近邻的投票进行加权，,距离越近则权重越大（权重为距离平方的倒数）,?,若样本到测试点距离为,d,，则选,1/d,为该邻居的权重（也就是得到了,该邻居所属类的权重），接下来统计统计,k,个邻居所有类标签的权,重和，值

5、最大的那个就是新数据点的预测类标签。,?,示例：,?,?,?,如图，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？,如果,K=3,，由于红色三角形所占比例为,2/3,，绿色圆将被赋予红色三,角形那个类，如果,K=5,，由于蓝色四方形比例为,3/5,，因此绿色圆被,赋予蓝色四方形类。,?,优缺点,?,1,、优点,?,?,简单，易于理解，易于实现，无需估计参数，无需训练,适合对稀有事件进行分类（例如当流失率很低时，比如低于,0.5%,，,构造流失预测模型）,?,特别适合于多分类问题,(multi-modal,对象具有多个类别标签,),，例如,根据基因特征来判断其功能分类，,kNN,比,SV

6、M,的表现要好,?,对于类域的交叉或重叠较多的待分样本集来说，,KNN,方法较其他方,法更为适合。,?,优缺点,?,2,、缺点,?,?,懒惰算法，就是说直到预测阶段采取处理训练数据。,对测试样本分类时的计算量大，内存开销大，评分慢。,?,?,可解释性较差，无法给出决策树那样的规则。,由于没有涉及抽象过程，,kNN,实际上并没有创建一个模型，预测时,间较长。,?,该算法在分类时有个主要的不足是，当样本不平衡时，,如一个类的样本容量很大，而其他类样本容量很小时，,有可能导致当输入一个新样本时，该样本的,K,个邻居中,大容量类的样本占多数。,?,改进,?,分组快速搜索近邻法,?,其基本思想是：将样本集按近邻关系分解成组，给出每组质心的位,置，以质心作为代表点，和未知样本计算距离，选出距离最近的一,个或若干个组，再在组的范围内应用一般的,knn,算法。由于并不是,将未知样本与所有样本计算距离，故该改进算法可以减少计算量，,但并不能减少存储量,?,行业应用,?,客户流失预测、欺诈侦测等（更适合于稀有事件的分类,问题）