一种改进的KNN文本分类算法

2009，45（11）数据挖掘是用于大规模数据处理的一种新的思维方法和技术手段，它是在现实生活中数据量呈指数级不断增长，和以数据库技术为核心的信息技术逐渐成熟的背景下应运产生的一种技术。

数据挖掘可以帮助用户发现隐藏在大型数据库中的知识和有用信息。

它融合了人工智能（artificial in－telligence）、统计（statistics）、机器学习（machine learning）、模式识别（pattern recognition）和数据库等多种学科的理论、方法与技术，已经在商业、企业、政府、科研及体育等多种不同类型的组织机构和领域中获得了非常广泛地应用。

几种典型的数据挖掘方法的研究是关联规则、分类、聚类、预测、Web 挖掘等[1]。

聚类（clustering）是一种无监督的学习，是指在没有训练数据样本的情况下，依据数据对象自身的相似性将一组对象划分成一系列有意义的子集的描述性任务[2]。

通过制定数据对象的相似性度量标准，使得同一组内的数据有较高的相似度，不同组中的相似度较低。

一般不同的相似度量标准就有不同的聚类结果。

常用的聚类方法一般有基于模型的、密度的、划分的、层次的、网格的及混合的方法等[1]。

分类（classification）是一种有监督的学习，是指从一组已知类别的数据中发现分类规则，以此预测新的数据类别[3]。

常用的分类方法主要有决策树、神经网络、遗传算法、支持向量机等。

本文综合考虑了聚类和分类方法的特点，提出了改进的k-近邻快速分类算法，可达到快速分类的目的。

1K-均值聚类算法K-均值算法建立在误差平方和准则基础之上[4]，为了得到最优结果，首先要先选定一些代表点作为初始聚类中心，然后再用K-均值算法将其余的点化分到各类别中去。

假设样本集R={x1，x2，…，x N}含K（K<N）个类型，即R=S1∪S2∪…∪S K。

算法步骤[5]：（1）选取K个初始聚类中心：z11，z12，…，z1K，（右上脚码为寻找聚类中心的迭代次数）；（2）将其余的数据归类：取样本xi，若有|xi-z ml|<|xi-z ml|（其中i=1，2，…，N，l=1，2，…，K，l≠j，m是迭代次数），则xi∈S mj，S mj是聚类中心为z mj的样本集合；（3）计算新的聚类中心：z m+1j=1nj x∈SΣx（其中j=1，2，…，K），nj为该类S mj所含的样本数；（4）如果z mj=z m+1j，其中j=1，2，…，K，则程序结束，否则令m=m+1转到步骤（2）。

浅谈KNN算法在文本分类中的应用K-最邻近算法在文本分类中的应用目录:一、引言二、算法简介三、ＫＮＮ的实现过程四、总结分析摘要：随着现在Internet以惊人的速度发展起来，人们已经进入信息大爆炸的时代，网络上的各种信息让我们眼花缭乱，如何在这海量的信息中给各种信息进行分类，从中提取出对我们有用的信息点，已日愈成为众多企业家、IT认识关注的焦点，在众多算法中，可以对信息进行的分类的有很多，包括k-Nearest Neighbor(kNN)、支持向量机(Support VectorMachines, SVM)、简单贝叶斯(Na?ve Bayes，NB)、Linear Least Squares Fits(LLSF)、NeuralNetwork(NNet)，而以下则是本人对k-Nearest Neighbor(kNN)算法在文本分类中的见解。

关键字：K-最邻近算法文本分类网页分类经过的简短的16节的数据挖掘课程后,对数据挖掘这一专业方向,从一无所知到,到有所了解,课上简单的了解几个数据挖掘的算法,其中一个印象比较深刻的就K-最邻近算法，但却不知道可以具体运用到什么地方去。

后来,经过课后上网学习研究得知,K-最邻近算法可以运用到分类问题中去,例如:对短信分类、过滤垃圾短信、网络页面分类等。

在网上经过了一番简单的研究,更具体的了解了ＫＮＮ算法，并得知了在文本分类中的简单运用．一、引言信息时代的发展,离不开Internet的飞速发展,这是一个信息爆炸的时代,人类每天产生的信息量都在急剧增长,而信息量的海量增加离不开网页,为了有效地组织和处理这海量的Web信息，需要对网页进行有效的分类．从文档分类得角度来看，文档分类可以分为人工分类和自动分类．人工分类是根据人的判断来进行分类，其特点是更准确，但是随之来的是确实需要投入大量的人力，这无疑给网络作业带来的高昂的代价，而且人工分类的效率很低，根本赶不上信息增长的速度．面对着每日剧增的信息量，人工分类显得那么的低效和昂贵，因此我们需要对网页实现自动分类，这一技术的实现则可以用到K-最邻近算法（KNN）。

KNN算法不足与改进学号：班级：姓名：专业：指导教师：摘要：KNN算法的核心思想是，通过计算每个训练样本到待分类数据的距离，取和待分类数据距离最近的K个训练样本，K个样本中哪个类别的训练样本占多数，则待分类数据就属于哪个类别。

本文首先说明了KNN算法的应用及优点，继而基于KNN算法的不足以及改进方法进行详细论述，最后结束语总结全文。

一前言KNN算法是对NN（nearest neighbor）算法即近邻算法的改进，最初的近邻算法是由T.M. Cover,在其文章”Rates of Convergence for Nearest Neighbor Procedures,”中提出的，是以全部训练样本作为带标点，计算测试样本与所有样本的距离并以最近邻者的类别作为决策，后学者们对近邻算法进行了各方面的改进。

1.1 KNN应用场景文本分类：文本分类主要应用于信息检索，机器翻译，自动文摘，信息过滤，邮件分类等任务。

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

回归：通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。

更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。

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

1.2 KNN有如下优点- 算法易于理解且易于实现- 几乎没有训练过程(只是需要确定K值和必要的预处理)- 可以在线更新- 非线性分类器，鲁棒性强二 KNN算法不足该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K 个邻居中大容量类的样本占多数。

基于K-Medoids聚类的改进KNN文本分类算法
罗贤锋;祝胜林;陈泽健;袁玉强
【期刊名称】《计算机工程与设计》
【年(卷),期】2014(035)011
【摘要】为有效提高传统KNN算法(K最近邻算法)在海量数据的分类效率,分析传统KNN算法的分类过程,提出基于K-Medoids聚类的改进KNN算法.利用K-Medoids算法对文本训练集进行聚类,把文本训练集分成相似度较高的簇;根据待分类文本与簇的相对位置,对文本训练集进行裁剪,解决传统KNN算法在文本训练集过大时速度慢的问题.分析与实验结果表明,该裁剪方法能够合理有效地裁剪文本训练集,提高了KNN算法的运行效率和分类能力.
【总页数】5页(P3864-3867,3937)
【作者】罗贤锋;祝胜林;陈泽健;袁玉强
【作者单位】华南农业大学信息学院,广东广州510642;华南农业大学信息学院,广东广州510642;华南农业大学信息学院,广东广州510642;华南农业大学信息学院,广东广州510642
【正文语种】中文
【中图分类】TP391.1
【相关文献】
1.基于类别特征改进的KNN短文本分类算法 [J], 黄贤英;熊李媛;刘英涛;李沁东
2.基于聚类算法的KNN文本分类算法研究 [J], 江涛;陈小莉;张玉芳;熊忠阳
3.基于DBSCAN聚类的改进KNN文本分类算法 [J], 苟和平;景永霞;冯百明;李勇
4.基于聚类改进的Fisher与KNN判别分类算法对比研究 [J], 朱景福;李芳;鹿保鑫
5.基于改进K-modes聚类的KNN分类算法 [J], 王志华; 刘绍廷; 罗齐
因版权原因，仅展示原文概要，查看原文内容请购买。

应用于中文文本分类的改进KNN算法
刘慧;杨宏光
【期刊名称】《今日科苑》
【年(卷),期】2010(000)008
【摘要】本文介绍了文本分类的基本流程及涉及到的相关技术,详细介绍了传统KNN方法并分析了它存在的不足之处,在此基础上提出了一种改进的KNN方法,该方法在相似度计算上进行了改进,通过实验证明了改进的KNN方法在宏召回率、宏准确率、宏F1值以及微F1上都有所提高。

【总页数】2页(P54-55)
【作者】刘慧;杨宏光
【作者单位】
【正文语种】中文
【中图分类】TP393
【相关文献】
1.一种新的中文文本分类算法——One Class SVM-KNN算法 [J], 刘文;吴陈
2.应用特征聚合进行中文文本分类的改进KNN算法 [J], 张晓辉;李莹;王华勇;赵宏
3.基于改进KNN算法的中文文本分类方法 [J], 王爱平;徐晓艳;国玮玮;李仿华
4.基于改进ML-KNN算法的文本分类研究 [J], 邢娟韬; 白金牛
5.使用KNN算法的中文Web文本分类技术研究 [J], 曹勇;吴顺祥
因版权原因，仅展示原文概要，查看原文内容请购买。

学习文档 仅供参考 KNN算法缺乏与改进 学号： 班级： ： 专业： 指导教师： 学习文档 仅供参考

摘要：KNN算法的核心思想是，通过计算每个训练样本到待分类数

据的距离，取和待分类数据距离最近的K个训练样本，K个样本中哪个类别的训练样本占多数，那么待分类数据就属于哪个类别。本文首先说明了KNN算法的应用及优点，继而基于KNN算法的缺乏以及改进方法进行详细论述，最后结束语总结全文。

一 前言 KNN算法是对NN〔nearest neighbor〕算法即近邻算法的改进，最初的近邻算法是由T.M. Cover,在其文章〞Rates of Convergence for Nearest Neighbor Procedures,〞中提出的，是以全部训练样本作为带标点，计算测试样本与所有样本的距离并以最近邻者的类别作为决策，后学者们对近邻算法进行了各方面的改进。 1.1 KNN应用场景 文本分类：文本分类主要应用于信息检索，机器翻译，自动文摘，信息过滤，邮件分类等任务。文本分类在搜索引擎中也有着大量的使用，网页分类/分层技术是检索系统的一项关键技术，搜索引擎需要研究如何对网页进行分类、分层，对不同类别的网页采用差异化的存储和处理，以保证在有限的硬件资源下，提供给用户一个高效的检索系统，同时提供给用户相关、丰富的检索结果。 回归：通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。 可以使用knn算法做到比较通用的现有用户产品推荐，基于用户的最近邻(长得最像的用户)买了什么产品来推荐是种介于电子商务网站和sns网站之间的精确营销。

1.2 KNN有如下优点 学习文档 仅供参考

- 算法易于理解且易于实现 - 几乎没有训练过程(只是需要确定K值和必要的预处理) - 可以在线更新 - 非线性分类器，鲁棒性强

作者： 邢娟韬[1];白金牛[2]
作者机构： [1]内蒙古科技大学信息工程学院,内蒙古包头014010;[2]内蒙古科技大学包头医学院,内蒙古包头014040
出版物刊名： 科技创新与应用
页码： 25-26页
年卷期： 2020年 第9期
主题词： 多标记学习;ML-KNN;最近邻;聚类;距离权重
摘要：由于传统ML-KNN算法数据集中每个特征具有相同权重,与事实上的不同特征具有不同权重相违背,故提出对ML-KNN算法的改进,用ML-KNN来构建分类模型进行分类。

为验证该算法的分类效果,选取算法常用的衡量标准与其他两种算法比较,结果表明由改进ML-KNN算法构造的模型要优于其他两种算法,能有效表达多领域数据集分类问题,算法效果更好。