K_近邻分类算法的研究及实现.pdf

科 技 论 坛 K- 近邻分类算法的研究及实现 1 2 王建伟 张 璞 （1、华北水利水电学院信息工程学院，河南 郑州 450046 2 、河南职业技术学院，河南 郑州 450000） 摘 要： k- 近邻（KNN）算法是一种基本的基于实例的学习分类算法，被广泛用于数据挖掘中。它分为学习过程和训练过程两个阶段。在学习 阶段，该算法除进行已知数据的简单存储之外不进行其它的操作，而在学习阶段进行绝大多数的计算。每当遇到新的查询实例时，一系列的相似的 实例就从存储器中取出，并用来分类新的查询实例。 关键词： k- 近邻；KNN ；分类；数据挖掘 1 概述 分类问题是数据挖掘邻域研究的一个基 表 1 本的问题，给定一批具有类标记的训练实例，分 类器被构造并被用于预测待分类实例的类标 记。通常，一个实例X 用一个m 维的属性向量 x ,x , ···,x 来表示，其中x 表示实例X 的第i 1 85 377% 14623% 1 2 m i 个属性值。令C 表示实例的类标记，则实例X 2 77 83% 22 17% 的类标记可表示为C(x)。KNN 算法作为一种基 3 82 547% 17453% 本的基于实例的分类算法，由于它的有效、简 单、高鲁棒性而被广泛的应用于数据挖掘领域 4 73 585% 26415% 来解决分类问题。 5 98 585% 1 4151% 2 KNN 算法 KNN 算法假定所有的实例对应于m 维的 6 1 0 欧氏空间Rm 中的点，实例间的距离是根据标准 7 90 094% 9 9057% 的欧氏距离来度量的，假设有欧氏空间中的两 个实例a 和b ，则a、b 之间的欧氏距离可以表 8 91038% 8 9623% 示为如下： 。若对实例X 9 89 623% 10377% 进行分类时，KNN 将距离实例X 最近，即：欧氏 10 78774% 21226% 距离最小的k 个实例的最普遍的类标记作为预 86 745% 13255% 测值赋给实例X，用公式表示如下： ，其中，y （i=1,2 ···k）为X 的k 个近 当K 增大时，分类效果可能会相对较好，但并 间复杂度为O(nlogn)，所以整个训