当前位置:文档之家› 一种考虑风力作用的KNN城市AQI预测算法

一种考虑风力作用的KNN城市AQI预测算法

一种考虑风力作用的KNN城市AQI预测算法
一种考虑风力作用的KNN城市AQI预测算法

kNN算法综述

kNN算法综述 王宇航13120476 (北京交通大学计算机与信息技术学院,北京,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 1引言 分类是数据挖掘中的核心和基础技术,在经营、决策、管理、科学研究等多个领域都有着广泛的应用。目前主要的分类技术包括决策树、贝叶斯分类、kNN分类、人工神经网络等。在这些方法中,kNN分类是一种简单、有效、非参数的方法,现已经广泛应用于文本分类、模式识别、图像及空间分类等领域。本文从各个角度对kNN算法进行较为全面的总结。 本文的结构如下: 在第二部分,主要介绍kNN算法的基本原理、思想、实现步骤、Java实现代码以及发展历程和经典论文。 第三部分是对kNN算法的诸多不足之处进行的讨论,并给出一些改进的方案。 第四部分介绍的是kNN算法如何处理多标签数据。 第五部分介绍了kNN算法目前的主要应用领域,并着重说明了其在文本分类中的出色表现。

KNN算法应用

应用场景 (1)文本分类:文本分类主要应用于信息检索,机器翻译,自动文摘,信息过滤,邮件分类等任务。文本分类在搜索引擎中也有着大量的使用,网页分类/分层技术是检索系统的一项关键技术,搜索引擎需要研究如何对网页进行分类、分层,对不同类别的网页采用差异化的存储和处理,以保证在有限的硬件资源下,提供给用户一个高效的检索系统,同时提供给用户相关、丰富的检索结果。在搜索引擎中,文本分类主要有这些用途:相关性排序会根据不同的网页类型做相应的排序规则;根据网页是索引页面还是信息页面,下载调度时会做不同的调度策略;在做页面信息抽取时,会根据页面分类的结果做不同的抽取策略;在做检索意图识别的时候,会根据用户所点击的url所属的类别来推断检索串的类别。 (2)回归:通过找出一个样本的k个最近邻居,将这些邻居的属性的平均值赋给该样本,就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight),如权值与距离成正比。 (3)可以使用knn算法做到比较通用的现有用户产品推荐,基于用户的最近邻(长得最像的用户)买了什么产品来推荐是种介于电子商务网站和sns网站之间的精确营销。只需要定期(例如每月)维护更新最近邻表就可以,基于最近邻表做搜索推荐可以很实时。 文本分类 1.KNN 算法最初由Cover 和Hart 于1968 年提出,该算法的基本思想是:根据传统的向量空间模型,文本内容被形式化为特征空间中的加权特征向量,即 D = D (T1,W1;T2,W2;…;Tn,Wn)。对于一个测试文本,计算它与训练样本集中每个文本的相似度,找出K 个最相似的文本,根据加权距离和判断测试文本所属的类别。 具体算法步骤如下: (1) 对于一个测试文本,根据特征词形成测试文本向量。 (2) 计算该测试文本与训练集中每个文本的文本相似度,计算公式为: 式中: x 为测试文本的特征向量;Sim(x,di)为相似度计算公式;b 为阈值,有待于优化选择;而y(di,Cj)的取值为1 或0,如果di属于Cj,则函数值为1,否则为0 。 (5)比较类的权重,将文本分到权重最大的那个类别中。 2.传统KNN 分类系统 传统的KNN 分类过程如图5-1:

机器学习十大算法8:kNN

Chapter8 k NN:k-Nearest Neighbors Michael Steinbach and Pang-Ning Tan Contents 8.1Introduction (151 8.2Description of the Algorithm (152 8.2.1High-Level Description (152 8.2.2Issues (153 8.2.3Software Implementations (155 8.3Examples (155 8.4Advanced Topics (157 8.5Exercises (158 Acknowledgments (159 References (159 8.1Introduction One of the simplest and rather trivial classi?ers is the Rote classi?er,which memorizes the entire training data and performs classi?cation only if the attributes of the test object exactly match the attributes of one of the training objects.An obvious problem with this approach is that many test records will not be classi?ed because they do not

exactly match any of the training records.Another issue arises when two or more training records have the same attributes but different class labels. A more sophisticated approach,k-nearest neighbor(k NNclassi?cation[10,11,21],?nds a group of k objects in the training set that are closest to the test object,and bases the assignment of a label on the predominance of a particular class in this neighborhood.This addresses the issue that,in many data sets,it is unlikely that one object will exactly match another,as well as the fact that con?icting information about the class of an object may be provided by the objects closest to it.There are several key elements of this approach:(ithe set of labeled objects to be used for evaluating a test object’s class,1(iia distance or similarity metric that can be used to compute This need not be the entire training set. 151 152kNN:k-Nearest Neighbors the closeness of objects,(iiithe value of k,the number of nearest neighbors,and(iv the method used to determine the class of the target object based on the classes and distances of the k nearest neighbors.In its simplest form,k NN can involve assigning an object the class of its nearest neighbor or of the majority of its nearest neighbors, but a variety of enhancements are possible and are discussed below. More generally,k NN is a special case of instance-based learning[1].This includes case-based reasoning[3],which deals with symbolic data.The k NN approach is also an example of a lazy learning technique,that is,a technique that waits until the query arrives to generalize beyond the training data. Although k NN cl assi?cation is a classi?cation technique that is easy to understand and implement,it performs well in many situations.In particular,a well-known result by Cover and Hart[6]shows that the classi?cation error2of the nearest neighbor rule is

KNN算法实验报告

KNN算法实验报告 一试验原理 K最近邻(k-NearestNeighbor,KNN)分类算法,是一个理论上比较成熟的方法,也是最简单的机器学习算法之一。 该方法的思路是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。KNN算法中,所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决 定待分样本所属的类别。KNN方法虽然从原理上也依赖于极限定理,但在类别决策时,只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合。 KNN算法不仅可以用于分类,还可以用于回归。通过找出一个样本的k个最近邻居,将这些邻居的属性的平均值赋给该样本,就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight),如权值与距离成正比。 该算法在分类时有个主要的不足是,当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本,某一类的样本数量很大,那么或者这类样本并不接近目标样本,或者这类样本很靠近目标样本。无论怎样,数量

并不能影响运行结果。可以采用权值的方法(和该样本距离小的邻居权值大)来改进。该方法的另一个不足之处是计算量较大,因为对每一个待分类的文本都要计算它到全体已知样本的距离,才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑,事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用这种算法比较容易产生误分。 二试验步骤 那么根据以上的描述,我把结合使用反余弦匹配和kNN结合的过程分成以下几个步骤: 1.计算出样本数据和待分类数据的距离 2.为待分类数据选择k个与其距离最小的样本 3.统计出k个样本中大多数样本所属的分类 4.这个分类就是待分类数据所属的分类 数学表达:目标函数值可以是离散值(分类问题),也可以是连续值(回归问题).函数形势为f:n维空间R—〉一维空间R。 第一步:将数据集分为训练集(DTrn)和测试集(DTES)。 第二步:在测试集给定一个实例Xq;在训练集(DTrn)中找到与这个实例Xq的K-最近邻子集{X1、、、、XK},即:DKNN。 第三步:计算这K-最近邻子集得目标值,经过加权平均: ^f(Xq)=(f(X1)+...+f(XK))/k作为f(Xq)的近似估计。改进的地方:对

knn算法

knn算法(K-Nearest Neighbor ) 这是一个小而有效的程序来执行的K -近邻搜索算法,此算法利用JIT 理论加速循环,比向量化有效解决了大量数据的精度问题。甚至比kd-tree效果要佳。K-nearest neighbor search已经广泛应用在科学与工程上,比如模式识别,数据挖掘和信号处理。 此程序小而简单,非常适合对K -近邻搜索算法的入学者。 用法: IDX = knnsearch(Q,R,K) 搜索参考数据集合R(n*d矩阵,代表d维空间中的n个点)中搜索k-近邻中个查询点代表Q(m x d)中的行.返回m x k的索引值IDX。 IDX = knnsearch(Q,R) 默认值为K=1. IDX = knnsearch(Q) or IDX = knnsearch(Q,[],K) 搜索当R = Q. 举例: 例1: R=randn(100,2); Q=randn(3,2); idx=knnsearch(Q,R); plot(R(:,1),R(:,2),'b.',Q(:,1),Q(:,2),'ro',R(idx,1),R(idx,2),'gx'); 结果: 例2: R=rand(100,2); Q=[0 0]; K=10; idx=knnsearch(Q,R,10); r=max(sqrt(sum(R(idx,:).^2,2))); theta=0:0.01:pi/2; x=r*cos(theta); y=r*sin(theta); plot(R(:,1),R(:,2),'b.',Q(:,1),Q(:,2),'co',R(idx,1),R(idx,2),'gx',x,y ,'r-','linewidth',2); 结果: 例3: R=randn(10000,4); Q=randn(500,4); t0=cputime; idx=knnsearch(Q,R); t1=cputime; T=delaunayn(R); idx1=dsearchn(R,T,Q); t2=cputime; fprintf('Are both indices the same? %d\n',isequal(idx,idx1));

KNN算法原理及应用

KNN分类算法(理论)

目录 1.KNN算法 (1) 2.KNN算法描述 (1) 3.KNN主要的应用领域 (2) 4.KNN算法的优、缺点 (2)

1.KNN算法 KNN算法,右又叫K最邻近分类算法,是数据挖掘分类技术中最简单的方法之一。所谓K最近邻,就是k个最近的邻居的意思,说的是每个样本都可以用它最接近的k个邻居来代表。 KNN算法概括来说,就是已知一个样本空间里的部分样本分成几个类,然后,给定一个待分类的数据,通过计算找出与自己最接近的K个样本,由这K个样本投票决定待分类数据归为哪一类。kNN算法在类别决策时,只与极少量的相邻样本有关。由于kNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,kNN方法较其他方法更为适合。 2.KNN算法描述 一个比较经典的KNN图如下: 从上图中我们可以看到,图中的有两个类型的样本数据,一类是蓝色的正方形,另一类是红色的三角形。而那个绿色的圆形是我们待分类的数据。 如果K=3,那么离绿色点最近的有2个红色三角形和1个蓝色的正方形,这3个点投票,于是绿色的这个待分类点属于红色的三角形。

如果K=5,那么离绿色点最近的有2个红色三角形和3个蓝色的正方形,这5个点投票,于是绿色的这个待分类点属于蓝色的正方形。 3.KNN主要的应用领域 文本分类、聚类分析、预测分析、模式识别、图像处理。 KNN算法不仅可以用于分类,还可以用于预测。通过找出一个样本的k个最近邻居,将这些邻居的属性的平均值赋给该样本,就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight),如权值与距离成反比。 4.KNN算法的优、缺点 优点 (1) 简单,易于理解,易于实现,无需估计参数,无需训练; (2) 适合对稀有事件进行分类; (3) 特别适合于多分类问题(multi-modal,对象具有多个类别标签),kNN比SVM的表现要好。 缺点 (1) 当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数。 (2) 计算量较大,因为对每一个待分类的文本都要计算它到全体已知样本的距离,才能求得它的K个最近邻点。

(总结452类)kNN算法综述

算法综述 王宇航 (北京交通大学计算机与信息技术学院,北京,) 摘要:算法是著名的模式识别统计学方法,是最好的文本分类算法之一,在机器学习分类算法中占有相当大的地位,是最简单的机器学习算法之一。本文对算法及相关文献做一份汇总报告,详细介绍算法的思想、原理、实现步骤以及具体实现代码,并分析了算法的优缺点及其各种改进技术指导文件。本文还介绍了算法的发展历程、重要的发表的论文。本文在最后介绍了算法的应用领域,并重点说明其在文本分类中的实现。 关键字:算法。近邻算法。机器学习。文本分类 :, , , , . , , , , . , . , , . : , , , 1引言 分类是数据挖掘中的核心和基础技术,在经营、决策、管理、科学研究等多个领域都有着广泛的应用。目前主要的分类技术包括决策树、贝叶斯分类、分类、人工神经网络等。在这些方法中,分类是一种简单、有效、非参数的方法,现已经广泛应用于文本分类、模式识别、图像及空间分类等领域。本文从各个角度对算法进行较为全面的汇总报告。 本文的结构如下: 在第二部分,主要介绍算法的基本原理、思想、实现步骤、实现代码以及发展历程和经典论文。 第三部分是对算法的诸多不足之处进行的讨论,并给出一些改进的技术指导文件。 第四部分介绍的是算法如何处理多标签数据。 第五部分介绍了算法目前的主要应用领域,并着重说明了其在文本分类中的出色表现。 2算法简介 2.1算法引入 算法是机器学习里面比较简单的一个分类算法,整体思想比较简单:计算一个点与其他所有点之间的距离,取出与该点最近的个点,然后统计这个点里面所属分类比例最大的,则点属于该分类。下面用一个例子来说明一下:

对KNN算法的优化

百度文库 中国地质大学课程报告 课程名称:数据挖掘 指导老师:蒋良孝 学生学号:20131003701 学生班级:086131 学生姓名:刘卫

对KNN算法的优化 k-近邻算法概述 k-近邻(k Nearest Neighbors)算法采用测量不同特征之间的距离方法进行分类。它的工作原理是:存在一个样本数据集合,并且样本集中每个数据都存在标签,即我们知道样本每一数据与所属分类的对应关系。输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较,然后算法提取样本集中特征最相似数据的分类标签。一般来说,我们只选择样本数据集中前k个最相似的数据,这就是k-近邻算法中k的出处,通常k是不大于20的奇数。最后,选择k个最相似数据中出现次数最多的分类,作为新数据的分类。 k-近邻算法的优点是精度高,对异常值不敏感,无数据输入假定;缺点是计算复杂度高、空间复杂度高。适用于数值和标称型数据。 使用k-近邻算法将每组数据划分到某个类中,其伪代码如下: 对未知类别属性的数据集中的每个点依次执行以下操作: 计算已知类别数据集中的点与当前点之间的距离; 按照距离递增交序排序; 选取与当前点距离最小的k个点; 确定前k个点所在类别的出现频率; 返回前k个点出现频率最高的类别作为当前点的预测分 类。 提出问题: 1.我在上机用KNN算法做实验时,发现k值只能凭经验 选取,而且不同的k值所产生的测试结果正确率相差很 大。如右图所示,当k值取3的时候待测元组就属于三 角形而当k值取5的时候待测元组属于正方形,最极端 的情况k取值为所有训练样本的元组数n时,那就是正方形和三角形哪个多取哪个了。 2.对于所要预测的值为离散类型数据时,是将这k个训练数据中哪个类别的训练数据占多数,待测分类元祖就属于哪个类别;对于预测值为连续型时,结果取k个训练数据的平均值。但这里明显k个点到待测元组的距离是不同的,距离近的肯定更有参考价值,而这里却把这k个点的价值等同看待,不合情理。

Matlab学习系列22.-KNN算法

21. KNN算法 KNN算法又称为k近邻分类(k-nearest neighbor classification)算法,是从训练集中找到和新数据最接近的k条记录,然后根据他们的主要分类来决定新数据的类别。该算法涉及3个主要因素:训练集、距离或相似的衡量、k的大小。 一、算法要点 1. 指导思想 其指导思想是“近朱者赤,近墨者黑”,由你的邻居来推断出你的类别。 2. 算法步骤: 1)算距离:计算已知类别数据集合汇总的点与当前点的距离,按照距离递增次序排序; 2)找邻居:选取与当前点距离最近的K个点; 3)做分类:确定距离最近的前K个点所在类别的出现频率,返回距离最近的前K个点中频率最高的类别作为当前点的预测分类。 3. k值设定为多大? k太小,分类结果易受噪声点影响;k太大,近邻中又可能包含太多的其它类别的点。(对距离加权,可以降低k值设定的影响)k值通常是采用交叉检验来确定(以k=1为基准) 经验规则:k一般低于训练样本数的平方根 2.距离或相似度的衡量

什么是合适的距离衡量?距离越近应该意味着这两个点属于一个分类的可能性越大。常用的距离衡量包括欧氏距离、夹角余弦等。 对于文本分类来说,使用余弦(cosine)来计算相似度就比欧式(Euclidean)距离更合适。高维度对距离衡量的影响:众所周知当变量数越多,欧氏距离的区分能力就越差。 变量值域对距离的影响:值域越大的变量常常会在距离计算中占据主导作用,因此应先对变量进行标准化。 3.类别的判定 投票决定:少数服从多数,近邻中哪个类别的点最多就分为该类。 加权投票法:根据距离的远近,对近邻的投票进行加权,距离越近则权重越大(权重为距离平方的倒数)。 投票法没有考虑近邻的距离的远近,距离更近的近邻也许更应该决定最终的分类,所以加权投票法更恰当一些。 4. 优缺点 1)优点 简单,易于理解,易于实现,无需估计参数,无需训练。适合对稀有事件进行分类(例如当流失率很低时,比如低于0.5%,构造流失预测模型)。特别适合于多分类问题(multi-modal, 对象具有多个类别标签),例如根据基因特征来判断其功能分类,kNN比SVM(支持向量机)的表现要好。 2)缺点

KNN算法总结

KNN算法总结 1 KNN分类算法 1.1KNN简述 K最近邻(k-Nearest Neighbor,KNN)分类算法,是一个理论上比较成熟的方法,也是最简单的机器学习算法之一。该方法的思路是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。KNN算法中,所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别[1]。KNN方法虽然从原理上也依赖于极限定理,但在类别决策时,只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合。 KNN最邻近规则,主要应用领域是对未知事物的识别,即判断未知事物属于哪一类,判断思想是,基于欧几里得定理,判断未知事物的特征和哪一类已知事物的的特征最接近。 1.2 KNN原理 最近邻方法(k-nearest neighbor,简称kNN)是一种简洁而有效的非参数分类方法,是最简单的机器学习算法之一,该算法最初由Cover和Hart提出的,用于解决文本的分类问题。 K近邻算法是最近邻算法的一个推广。该规则将是一个测试数据点x分类为与它最接近的K个近邻中出现最多的那个类别。K近邻算法从测试样本点x开始生长,不断的扩大区域,直到包含进K个训练样本点为止,并且把测试样本点x 归为这最近的K个训练样本点中出现频率最大的类别。其中测试样本与训练样本的相似度一般使用欧式距离测量。 如果K值固定,并且允许训练样本个数趋向于无穷大,那么,所有的这K个

knn算法

教 育 技 术 前 沿 讲 座 计算机科学学院 教育技术学01 41109020105 刘泽成

KNN - 简介 是K最邻近结点算法(k-Nearest Neighbor algorithm)的缩写形式,是电子信息分类器算法的一种。KNN方法对包容型数据的特征变量筛选尤其有效。 KNN - 算法描述 该算法的基本思路是:在给定新文本后,考虑在训练文本集中与该新文本距离最近(最相似)的 K 篇文本,根据这 K 篇文本所属的类别判定新文本所属的类别,具体的算法步骤如下: 一、:根据特征项集合重新描述训练文本向量 二、:在新文本到达后,根据特征词分词新文本,确定新文本的向量表示 三、:在训练文本集中选出与新文本最相似的 K 个文本,计算公式为: 【图】公式(1)-KNN 其中,K 值的确定目前没有很好的方法,一般采用先定一个初始值,然后根据实验测试的结果调整 K 值,一般初始值定为几百到几千之间。 四、:在新文本的 K 个邻居中,依次计算每类的权重,计算公式如下:【图】】公式(2)-KNN 其中, x为新文本的特征向量, Sim(x,di)为相似度计算公式,与上一步骤的计算公式相同,而y(di,Cj)为类别属性函数,即如果di 属于类Cj ,那么函数值为 1,否则为 0。 五、:比较类的权重,将文本分到权重最大的那个类别中。 除此以外,支持向量机和神经网络算法在文本分类系统中应用得也较为广泛,支持向量机的基本思想是使用简单的线形分类器划分样本空间。对于在当前特征空

间中线形不可分的模式,则使用一个核函数把样本映射到一个高维空间中,使得样本能够线形可分。 而神经网络算法采用感知算法进行分类。在这种模型中,分类知识被隐式地存储在连接的权值上,使用迭代算法来确定权值向量。当网络输出判别正确时,权值向量保持不变,否则进行增加或降低的调整,因此也称为奖惩法。 KNN - 不足 该算法在分类时有个主要的不足是,当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数。因此可以采用权值的方法(和该样本距离小的邻居权值大)来改进。该方法的另一个不足之处是计算量较大,因为对每一个待分类的文本都要计算它到全体已知样本的距离,才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑,事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用这种算法比较容易产生误分。 KNN - 图示 图示-KNN 右图中,绿色圆要被决定赋予哪个类,是红色三角形还是蓝色四方形?如果K=3,由于红色三角形所占比例为2/3,绿色圆将被赋予红色三角形那个类,如果K=5,由于蓝色四方形比例为3/5,因此绿色圆被赋予蓝色四方形类。 KNN - 主要应用领域

关于KNN算法的理解及应用

关于KNN算法的理解及应用 K最近邻即KNN(k-Nearest Neighbor)分类算法是数据聚类中一种较为简单方便的方法。所谓K最近邻,假设每一类包含多个样本数据,而且没个数据有一个唯一的类标记表示这些样本是属于那一个分类,计算没个样本数据到待分类数据的距离,取和待分类数据最近的K个数据样本,那么这K个样本数据中哪个类别的样本数据占多数,则待分类数据就属于该类别。由此可见,KNN算法的核心思想是如果一个样本在特征空间中的K个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。由于kNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较为适合。 我们可以看两个简单的例子来了解一下KNN算法,如图附录1。列表中给出了七部曾经的风靡电影,可以看到该表统计了每部电影中的打斗次数及接吻次

数,并在最后一列对该电影进行了分类:动作电影抑或是爱情电影。通过观察可以发现,打斗次数多而接吻次数少的电影即被判别为动作电影,反之即为爱情电影,这符合正常的逻辑。对于第七部电影,电影名未知,但已知其中接吻及打斗次数,通过简单比较我们就可以判断出该电影属于动作电影。再看图附录2,图中的圆被决定属于哪个类,是三角形还是四方形?根据定义我们可以做简单的判断:当K=3时,由于三角形所占比例为2/3,故圆将被赋予三角形所在的类。当然我们也可以取K=5,此时四方形所占比例为3/5,故圆将被赋予四方形所在的类。 通过上述的两个例子我们可以总结下KNN算法的算法流程:1. 准备数据,对数据进行预处理;2. 选用合适的数据结构存储训练数据和测试元组;3. 设定参数,如K(K 值的确定目前没有很好的方法,一般采用先定一个初始值,然后根据实验测试的结果调整K 值};4.维护一个大小为k的的按距离由大到小的优先级队列,用于存储最近邻训练元组。随机从训练元组中选取k个元组作为初始的最近邻元组,分别计算测试元组到这k个元组的距离,将训练元组标号和距离存入优先级队列;5. 遍历训练元组集,计算当前训练元组与测试元组的距离,将所得距离L 与优先级队列

KNN算法综述

2018年10月 KNN算法综述 窦小凡(吉林高新区万信培训学校,吉林省吉林市132000) 【摘要】KNN算法是非常有效和容易完成的,是最好的文本分类算法之一,在机器学习分类算法中占有相当大的位置,是最简略的机器学习算法之一。它用于分类、回归和模式识别等。 【关键词】机器学习;人工智能;KNN算法;K近邻算法 【中图分类号】TP301.6【文献标识码】A【文章编号】1006-4222(2018)10-0273-02 1引言 计算机分类在生活中已经运用广泛,在商业经营中,政府 决策管理中,科学研究中和工业中等多个领域都有运用。我对 计算机、手机之类的设备感兴趣,比如手机中的人脸、图片识 别,模式识别,扫码,计算机中的空间分类,文本分类,决策树 分类(kd-tree),贝叶斯分类,KNN分类,人工神经网络等技 术。从计算机的KNN分类中,我发现了这种算法的一些优点 及缺点。本文的结构如下: 第二部分主要介绍KNN算法及其基本原理。 第三部分是对KNN算法的一些优点及不足之处进行了 概括。 第四部分是针对KNN算法的不足之处提出了一些简单的建议。 2KNN算法 (1)KNN(K-nearestneighbor),即K-邻近算法是由Cover 和Hart于1968年提出。所谓K最近邻,就是K附近的邻居的意思,说的是每个样本都可以用它最接近的K个邻居来代表。比如将20万张猫的图片和20万张狗的图片,输入到计算机让它学习,每一张都不要重复。训练成功后,你就可以随意选一张图片,让它识别,它就会在它储存40万张照片中,判断与它储存的形状最接近的一个,最后显示出结果,如图1所示。 圆圈就像20万张猫的图片,方块就像20万张狗的图片,以此类推。X就相当于你想识别的对象,这时计算机就会将与它距离最近的对象识别出来,给出最终的结果。再打个比方,我们都说物以类聚,人以群分,判别一个人有什么样的品质特征,常常可以通过他身边的朋友来入手。KNN算法也类似,如果我们想判断圆圈属于哪一类数据(如图2所示)。 若以圆圈为圆心,半径为3画圆,圆圈圈中的三个样本,三角形样本数量最多,那么就将圆圈视为三角形一类。 (2)KNN算法流程: T=(x1,y1),(x2,y2),…,(x N,y N)(1)其中x是每个样本的特征向量,特征向量意思就是一个矩阵作用在一个向量上,数字就是特征值,这个向量就是特征向量。y为实例的类别,i就是常数、序号1,2,3…N。根据测完的距离,在T(样本)中找出与待分类对象最邻近的k个点,包 含了所有k点的区域记作Nk(x)。在Nk(x)中根据分类决策(少数跟随多数的原则来表决)决定x的类别: y=arg max cj∑xi∈Nk(x)I(y i=c j),i=1,2,…,N(2)式中,I为指示函数,即当y i=c j时I=1,不然I=0。k近邻法的特殊状况时k=1的情景,成为最近邻算法。关于输入的实例 点x,最近邻法将数据集中与x最邻近点的类作为x的类。3KNN算法的优点/缺点 KNN算法自身操作简略、有效,易于了解,易于完成,无需预计参数,也无需训练。它适宜对时间进行分类,尤其适合于多分类问题(multi-modal,即此对象具备多个类别)。它是一种lazy-learning,也就是惰性学习。这种分类器不需要应用训练及进行训练,也就是训练时间复杂度为0,你只需要输入大量样本,计算机就会进行分类,再输入一个新的样本,它就会识别出来。KNN分类的计算复杂度和训练集中的文档数目成正比,打个比方,假如你输入了一些关于手机的照片,你输入的图片数量越少,它识别的速度也随之变快。但这个算法有不足之处,就是计算量较大。因为计算机需要计算出每一个已知的样本与待分类对象之间的距离,才能得出它的近邻。KNN算法还可以回归,或者说成预测。通过找出待识别对象的几个近邻,求出这些近邻的平均值,将这个平均值赋给待分类对象,就可以知道这个对象的属性。还有另外一种方法,就是将不同距离的近邻对该对象所产生的影响给予不同的权值(权值,就是加权平均数中每个数的频数),权值与距离成反比。这种算法仍有不足之处,当样本数量不平衡时,即一种样本容量很大,而其他几种容量很小时,有可能会导致输入一个新样本时,该样本的近邻中容量大的样本所占多数,就会产生误差。4KNN算法的改进策略 KNN算法提出时间较早,再加上其它技术的不断更新和完善,这种算法的许多不足之处也逐一浮现出来。对此,一些科研人员也研究出的改进算法也应运而生。针对3中的不足点,科研人员将改进算法分为两类:分类效率和分类效果。提高效率的方法主要是事先对样本属性进行约简,删除一些对分类结果影响较小的样本属性,就能快速得出待分类样本的 图1KNN 分类示意图 图2KNN分类示意图 论述273

相关主题
相关文档 最新文档