KNN原理
训练元组用n个属性描述,每个元组代表n维空间中的一个点,所有的训练元组存放在n维的模式空间。当给定一个未知元组时,搜索该模式空间,找出最接近未知元组的k个训练元组。未知元组指派到它的k个最近邻中的多数类。“邻近性”用距离度量,如欧几里德距离。
KNN算法中的细节处理
•数值属性规范化:将数值属性规范到0-1区间以便于计算,也可防止大数值型属性对分类的主导作用。
可选的方法有:v'= (v - vmin)/ (vmax - vmin),当然也可以采用其它的规范化方法
•比较的属性是分类类型而不是数值类型的:同则差为0,异则差为1.
有时候可以作更为精确的处理,比如黑色与白色的差肯定要大于灰色与白色的差。
•缺失值的处理:取最大的可能差,对于分类属性,如果属性A的一个或两个对应值丢失,则取差值为1;
如果A是数值属性,若两个比较的元组A属性值均缺失,则取差值为1,若只有一个缺失,另一个值为v,则取差值为|1-v|和|0-v|中的最大值
•确定K的值:通过实验确定。进行若干次实验,取分类误差率最小的k值。
•对噪声数据或不相关属性的处理:对属性赋予相关性权重w,w越大说明属性对分类的影响越相关。对噪声数据可以将所在的元组直接cut掉。
KNN算法流程
•准备数据,对数据进行预处理
•选用合适的数据结构存储训练数据和测试元组
•设定参数,如k
•维护一个大小为k的的按距离由大到小的优先级队列,用于存储最近邻训练元组
•随机从训练元组中选取k个元组作为初始的最近邻元组,分别计算测试元组到这k个元组的距离,将训练元组标号和距离存入优先级列
•遍历训练元组集,计算当前训练元组与测试元组的距离,将所得距离L与优先级队列中的最大距离Lmax进行比较。若L>=Lmax,则舍弃该元组,遍历下一个元组。若L< Lmax,删除优先级队列中最大距离的元组,将当前训练元组存入优先级队列。
•遍历完毕,计算优先级队列中k个元组的多数类,并将其作为测试元组的类别。
•测试元组集测试完毕后计算误差率,继续设定不同的k值重新进行训练,最后取误差率最小的k值。
KNN的优缺点
优点:原理简单,实现起来比较方便。支持增量学习。能对超多边形的复杂决策空间建模。
缺点:计算开销大,需要有效的存储技术和并行硬件的支撑。
KNN算法的改进策略
•将存储的训练元组预先排序并安排在搜索树中(如何排序有待研究)
•并行实现
•部分距离计算,取n个属性的“子集”计算出部分距离,若超过设定的阈值则停止对当前元组作进一步计算。转向下一个元组。
•剪枝或精简:删除证明是“无用的”元组。
该算法比较适用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用这种算法比较容易产生误分
分享到:
相关推荐
K最近的NEIGHBOUR-KNN算法KNN表示K最近邻算法。 KNN是最简单的监督式机器学习算法,主要用于数据分类。 在继续学习KNN之前,让我们简单地看一下机器学习和KNN所属的类别。 机器学习(ML)是对计算机算法的研究,该...
kNN算法:K最近邻(kNN,k-NearestNeighbor)分类算法。 KNN算法1、算法概述2、举例3、加深理解4、算法原理5、算法超参数5.1 K值5.2 关于K的取值5.3 距离度量方式5.4 权重计算方式6、算法步骤7、使用KNN实现分类7.1 ...
基于KNN 算法的分类器matlab实现,简单操作,可出图,可根据自身需求修改代码
该代码实现了一个简单的 k 最近邻(kNN)分类器,用于对 MNIST 手写数字数据集进行分类。 使用方法: 1. 将代码压缩包解压,该项目已包含所有代码和MNIST数据集 2. 直接在 MATLAB 中运行 MNIST_classification_accuracy...
在机器学习领域,K最近邻(K-Nearest Neighbors,KNN)是一种常用的算法,用于解决分类和回归问题。在这个教程中,我们将学习如何使用R编程语言中的caret和kknn库来实现K最近邻回归模型,以预测白葡萄酒的质量评分。
k最近邻算法:分类和回归。通过对训练集分类训练模型,验证集用于验证数据的准确性。
传统k最近邻算法(k-Nearest Neighbor,kNN)作为一种非参数化分类技术在数据分析中具有广泛的应用,但该算法具有较多的冗余计算,致使处理数据时需要花费较多的计算时间。目前大量的研究都集中在数据的预处理阶段,...
:trophy: 使用K-NN,多类感知器... 由于这是一项比较研究,因此我们首先将K最近邻分类器描述为基准方法,然后将其与Multiclass Perceptron分类器和SVM分类器进行比较。 1)K最近邻分类器-我们的基准方法 k最近邻居(k-
在Apache Spark上实现的k最近邻居算法(k-NN)。 这使用混合溢出树方法来实现高精度和搜索效率。 k-NN的简单性和调整参数的缺乏使k-NN成为许多机器学习问题的有用基线模型。 如何使用 该软件包使用,链接信息可在...
在此示例中,将K最近邻分类方法(有监督的机器学习)应用于有关汽车类型和购买者特征的一些样本数据,以便用可能的汽车模型对购买者进行分类。 用法: hadoop jar KnnPattern.jar KnnPattern /home/mhi/knn/Car...
其基本思想是对于一个待分类的样本,找到其在训练数据集中K个最近邻的样本,然后根据这K个最近邻样本的标签进行投票,将待分类样本归为票数最多的那一类。KNN算法简单易懂,不需要事先对数据进行假设和模型的拟合,...
机器学习模型能够处理大量数据,并在相对短的时间内产生可行且效果良好的结果。 它能够同时处理标称型和数值型数据,并可以处理具有缺失属性的样本。 机器学习算法如决策树,易于理解和解释,可以可视化分析,容易...
分类时,对新的实例,根据其k个最近邻的训练实例类别,通过多数表决等方式进行预测。 决策树 一种基于树结构来进行决策的分类算法,我们希望从给定的训练数据集学得一个模型(即决策树),用该模型对新样本分类。...
KNN算法的核心思想是通过测量不同数据点之间的距离,将新的数据点分类到与其最近邻的训练数据点所属的类别。在葡萄酒质量分类中,算法会计算待分类葡萄酒样本与训练集中各个样本之间的距离,并找出距离最近的K个样本...
k最近邻法的实现是线性扫描(以穷举搜索的方式进行距离测算,加权分类),即要计算输入实例与每一个训练实例的距离。计算并存储好以后,再查找K近邻。 当训练集很大时,计算效率非常的低下。 为了提高KNN最近邻搜索...
本来这篇文章是5月份写的,今天修改了一下内容,就成今天发表的了,CSDN这是出BUG了...1.K最近邻分类器原理 首先给出一张图,根据这张图来理解最近邻分类器,如下: 根据上图所示,有两类不同的样本数据,分别用蓝色
knnAUC : k-最近邻 AUC 测试。 在knnAUC框架中,我们首先基于k-nearest neighbor分类器计算AUC估计量,然后评估基于AUC的统计量的显着性(备择假设:AUC > 0.5,即X对Y有预测能力) .
K邻近算法采用测量不同特征值之间的距离方法来进行分类。
分类时,对新的实例,根据其 k 个最近邻的训练实例的类别,通过多数表决等方式进行预测。因此,KNN算法不具有显式的学习过程。 KNN算法实际上利用训练数据集对特征向量空间进行划分,并作为其分类的“模型”。 k值的...
提出一种最近邻分类的改良模型,综合考虑待分类数据的k近邻、所属的簇和整个训练数据集的类分布,充分利用局部、部分和全局三种类分布信息,从而具有抗噪声的性能。实验表明,提出的最近邻分类改良模型具有较好的抗...