kNN算法综述.doc

《kNN算法综述.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、19kNN算法综述kNN算法综述王宇航13120476(北京交通大学计算机与信息技术学院，北京，100044)摘要：kNN算法是著名的模式识别统计学方法，是最好的文本分类算法之一，在机器学习分类算法中占有相当大的地位，是最简单的机器学习算法之一。本文对kNN算法及相关文献做一份总结，详细介绍kNN算法的思想、原理、实现步骤以及具体实现代码，并分析了算法的优缺点及其各种改进方案。本文还介绍了kNN算法的发展历程、重要的发表的论文。本文在最后介绍了kNN算法的应用领域，并重点说明其在文本分类中的实现。关键字：kNN算法；k近

2、邻算法；机器学习；文本分类Abstract:KNNalgorithm,afamousstatisticalmethodofpatternrecognition,whichisoneofthebestalgorithmsfordealingwithtextcategorization,isplayinganimportantroleinmachinelearningclassificationalgorithm,anditisoneofthesimplestalgorithmsinmachinelearning.Thisp

3、apermainlysummariesthekNNalgorithmanditsrelatedliterature,anddetailedintroducesitsmainidea,principle,implementationstepsandspecificimplementationcode,aswellasanalyzestheadvantagesanddisadvantagesofthealgorithmanditsvariousimprovementschemes.Thispaperalsointroduce

4、sthedevelopmentcourseofkNNalgorithm,itsimportantpublishedpaper.Inthefinal,thispaperintroducestheapplicationfieldofkNNalgorithm,andespeciallyintextcategorization.Keywords:KNNalgorithm,Kneighboralgorithm,Machinelearning,Textclassification1引言分类是数据挖掘中的核心和基础技术，在经营、决策、

5、管理、科学研究等多个领域都有着广泛的应用。目前主要的分类技术包括决策树、贝叶斯分类、kNN分类、人工神经网络等。在这些方法中，kNN分类是一种简单、有效、非参数的方法，现已经广泛应用于文本分类、模式识别、图像及空间分类等领域。本文从各个角度对kNN算法进行较为全面的总结。本文的结构如下：在第二部分，主要介绍kNN算法的基本原理、思想、实现步骤、Java实现代码以及发展历程和经典论文。第三部分是对kNN算法的诸多不足之处进行的讨论，并给出一些改进的方案。19kNN算法综述第四部分介绍的是kNN算法如何处理多标签数据。第五部

6、分介绍了kNN算法目前的主要应用领域，并着重说明了其在文本分类中的出色表现。1kNN算法简介1.1算法引入KNN算法是机器学习里面比较简单的一个分类算法，整体思想比较简单：计算一个点A与其他所有点之间的距离，取出与该点最近的k个点，然后统计这k个点里面所属分类比例最大的，则点A属于该分类。下面用一个例子来说明一下：电影名称打斗次数接吻次数电影类型CaliforniaMan3104RomanceHe’sNotReallyintoDudes2100RomanceBeautifulWoman181RomanceKevinLon

7、gblade10110ActionRoboSlayer3000995ActionAmpedII982Action简单说一下这个数据的意思：这里用打斗次数和接吻次数来界定电影类型，如上，接吻多的是Romance类型的，而打斗多的是动作电影。还有一部名字未知（这里名字未知是为了防止能从名字中猜出电影类型），打斗次数为18次，接吻次数为90次的电影，它到底属于哪种类型的电影呢？KNN算法要做的，就是先用打斗次数和接吻次数作为电影的坐标，然后计算其他六部电影与未知电影之间的距离，取得前K个距离最近的电影，然后统计这k个距离最近的

8、电影里，属于哪种类型的电影最多，比如Action最多，则说明未知的这部电影属于动作片类型。在实际使用中，有几个问题是值得注意的：K值的选取，选多大合适呢？计算两者间距离，用哪种距离会更好呢？计算量太大怎么办？假设样本中，类型分布非常不均，比如Action的电影有200部，但是Romance的电影只有20部，这样计算起