3.KNN不足与改进

第一篇：

3.knn不足与改进北京理工大学软件学院商务智能

knn算法不足与改进

学号：班级：姓名：专业：指导教师：

1

北京理工大学软件学院商务智能

摘要。knn算法的核心思想是，通过计算每个训练样本到待分类数据的距离，取和待分类数据距离最近的k个训练样本，k个样本中哪个类别的训练样本占多数，则待分类数据就属于哪个类别。本文首先说明了knn算法的应用及优点，继而基于knn算法的不足以及改进方法进行详细论述，最后结束语总结全文。

一前言

knn算法是对nn（nearestneighbor）算法即近邻算法的改进，最初的近邻算法是由t.m.cover，在其文章”ratesofconvergencefornearestneighborprocedures，”中提出的，是以全部训练样本作为带标点，计算测试样本与所有样本的距离并以最近邻者的类别作为决策，后学者们对近邻算法进行了各方面的改进。

1.1knn应用场景

文本分类。文本分类主要应用于信息检索，机器翻译，自动文摘，信息过滤，邮件分类等任务。文本分类在搜索引擎中也有着大量的使用，网页分类/分层技术是检索系统的一项关键技术，搜索引擎需要研究如何对网页进行分类、分层，对不同类别的网页采用差异化的存储和处理，以保证在有限的硬件资源下，提供给用户一个高效的检索系统，同时提供给用户相关、丰富的检索结果。

回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值（weight），如权值与距离成正比。

可以使用knn算法做到比较通用的现有用户产品推荐，基于用户的最近邻（长得最像的用户）买了什么产品来推荐是种介于电子商务网站和sns网站之间的精确营销。

1.2knn有如下优点

2

北京理工大学软件学院商务智能

-算法易于理解且易于实现

-几乎没有训练过程（只是需要确定k值和必要的预处理）k值难以确定

·目前没有很好的方法，一般采用先定一个初始值，然后根据实验测试的结果调整k值。

·可解释性较差，无法给出决策树那样的规则。-对于不平衡样本集比较敏感

·采用权值的方法（增大距离小的邻居样本的权值）当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的k个邻居中大容量类的样本占多数。

3

北京理工大学软件学院商务智能

三knn算法改进

3.1基于聚类的knn算法改进

3.1.1传统的knn算法

对于测试集中每一个测试文本，都需要计算它与训练集中每个文本的距离，然后把距离排序找到离该测试文本最近的k个文本，根据测试文本与训练文本的距离来给该测试文档的候选类别按公式（1）评分。如果有属于同一个类别的，就将该类别中的文本的打

分求和作为该类别的得分。最后，将得分排序，测试文本将被分配给得分最高的那个类别。

score（c|x）=Σsim（x，d）i（d，c）x是一个测试集文本，c是训练集的类别，d是距离x最近的k个文本之一；sim（x，d）是文本x与文本d的相似度，这里指的是距离；

i（d，c）是表示d是否属于类c，如果属于类c则为1，否则为0。

3.1.2改进的iknn算法

首先对训练集文本进行聚类，采用dbscan算法。算法过程如下：

第一步：如果文本对象p未被归入某个簇或标记为噪声，就检查它的指定半径邻域r，如果指定半径邻域内包含的对象数目大于等于给定的值m，就建立新簇c，将p的指定半径领域r中所有点加入该簇c；