kNN算法综述.docx

kNN算法综述王宇(北京交通大学计算机与信息技术学院，北京，100044)摘要：kNN算法是著名的模式识别统计学方法，是最好的文本分类算法之一，在机器学习分类算法中占有相当大的地位，是最简单的机器学习算法之一。本文对kNN算法及相关文献做一份总结，详细介绍kNN算法的思想、原理、实现步骤以及具体实现代码，并分析了算法的优缺点及其各种改进方案。本文还介绍了kNN算法的发展历程、重要的发表的论文。本文在最后介绍了kNN算法的应用领域，并重点说明其在文本分类中的实现。关键字：kNN算法；k近邻算法；机器学习；文本分类Abstract: KNN algorithm, a famous statistical method of pattern recognition, which is one of the best algorithms for dealing with text categorization, is playing an important role in machine learning classification algorithm, and it is one of the simplest algorithms in machine learning. This paper mainly summaries the kNN algorithm and its related literature, and detailed introduces its main idea, principle, implementation steps and specific implementation code, as well as analyzes the advantages and disadvantages of the algorithm and its various improvement schemes. This paper also introduces the development course of kNN algorithm, its important published paper. In the final, this paper introduces the application field of kNN algorithm, and especially in text categorization.Keywords: KNN algorithm, K neighbor algorithm, Machine learning, Text classification引言分类是数据挖掘中的核心和基础技术，在经营、决策、管理、科学研究等多个领域都有着广泛的应用。目前主要的分类技术包括决策树、贝叶斯分类、kNN分类、人工神经网络等。在这些方法中，kNN分类是一种简单、有效、非参数的方法，现已经广泛应用于文本分类、模式识别、图像及空间分类等领域。本文从各个角度对kNN算法进行较为全面的总结。本文的结构如下：在第二部分，主要介绍kNN算法的基本原理、思想、实现步骤、Java实现代码以及发展历程和经典论文。第三部分是对kNN算法的诸多不足之处进行的讨论，并给出一些改进的方案。第四部分介绍的是kNN算法如何处理多标签数据。第五部分介绍了kNN算法目前的主要应用领域，并着重说明了其在文本分类中的出色表现。kNN算法简介算法引入KNN算法是机器学习里面比较简单的一个分类算法，整体思想比较简单：计算一个点A与其他所有点之间的距离，取出与该点最近的k个点，然后统计这k个点里面所属分类比例最大的，则点A属于该分类。下面用一个例子来说明一下：电影名称打斗次数接吻次数电影类型California Man3104RomanceHe’s Not Really into Dudes2100RomanceBeautiful Woman181RomanceKevin Longblade10110ActionRobo Slayer 3000995ActionAmped II982Action简单说一下这个数据的意思：这里用打斗次数和接吻次数来界定电影类型，如上，接吻多的是Romance类型的，而打斗多的是动作电影。还有一部名字未知（这里名字未知是为了防止能从名字中猜出电影类型），打斗次数为18次，接吻次数为90次的电影，它到底属于哪种类型的电影呢？KNN算法要做的，就是先用打斗次数和接吻次数作为电影的坐标，然后计算其他六部电影与未知电影之间的距离，取得前K个距离最近的电影，然后统计这k个距离最近的电影里，属于哪种类型的电影最多，比如Action最多，则说明未知的这部电影属于动作片类型。在实际使