最近邻法和k-近邻法
一.基本概念：
最近邻法：对于未知样本x，比较x与N个已知类别的样本之间的欧式距离，并决策x 与距离它最近的样本同类。
K近邻法：取未知样本x的k个近邻，看这k个近邻中多数属于哪一类，就把x归为哪一类。K取奇数，为了是避免k1=k2的情况。
二.问题分析：
要判别x属于哪一类，关键要求得与x最近的k个样本（当k=1时，即是最近邻法），然后判别这k个样本的多数属于哪一类。
可采用欧式距离公式求得两个样本间的距离s=sqrt（（x1-x2）^2+(y1-y2)^2）
三.算法分析：
该算法中任取每类样本的一半作为训练样本，其余作为测试样本。例如iris中取每类样本的25组作为训练样本，剩余25组作为测试样本，依次求得与一测试样本x距离最近的k 个样本，并判断k个样本多数属于哪一类，则x就属于哪类。测试10次，取10次分类正确率的平均值来检验算法的性能。
四.MATLAB代码：
最近邻算实现对Iris分类
clc;
totalsum=0;
for ii=1:10
data=load('iris.txt');
data1=data(1:50,1:4);%任取Iris-setosa数据的25组
rbow1=randperm(50);
trainsample1=data1(rbow1(:,1:25),1:4);
rbow1(:,26:50)=sort(rbow1(:,26:50));%剩余的25组按行下标大小顺序排列
testsample1=data1(rbow1(:,26:50),1:4);
data2=data(51:100,1:4);%任取Iris-versicolor数据的25组 rbow2=randperm(50); trainsample2=data2(rbow2(:,1:25),1:4);
rbow2(:,26:50)=sort(rbow2(:,26:50));
testsample2=data2(rbow2(:,26:50),1:4);
data3=data(101:150,1:4);%任取Iris-virginica数据的25组
rbow3=randperm(50);
trainsample3=data3(rbow3(:,1:25),1:4);
rbow3(:,26:50)=sort(rbow3(:,26:50));
testsample3=data3(rbow3(:,26:50),1:4);
trainsample=cat(1,trainsample1,trainsample2,trainsample3);%包含75组数据的样本集testsample=cat(1,testsample1,testsample2,testsample3);
newchar=zeros(1,75);sum=0;
[i,j]=size(trainsample);%i=60,j=4
[u,v]=size(testsample);%u=90,v=4
for x=1:u
for y=1:i
result=sqrt((testsample(x,1)-trainsample(y,1))^2+(testsample(x,2)-trainsample(y,2))^2+(testsampl e(x,3)-trainsample(y,3))^2+(testsample(x,4)-trainsample(y,4))^2); %欧式距离
newchar(1,y)=result;
end;
[new,Ind]=sort(newchar);
class1=0;
class2=0;
class3=0;
if Ind(1,1)<=25
class1=class1+1;
elseif Ind(1,1)>25&&Ind(1,1)<=50
class2=class2+1;
else
class3=class3+1;
end
if class1>class2&&class1>class3
m=1;
ty='Iris-setosa';
elseif class2>class1&&class2>class3
m=2;
ty='Iris-versicolor';
elseif class3>class1&&class3>class2
m=3;
ty='Iris-virginica';
else
m=0;
ty='none';
end
if x<=25&&m>0
disp(sprintf('第%d组数据分类后为%s类',rbow1(:,x+25),ty));
elseif x<=25&&m==0
disp(sprintf('第%d组数据分类后为%s类',rbow1(:,x+25),'none'));
end
if x>25&&x<=50&&m>0
disp(sprintf('第%d组数据分类后为%s类',50+rbow2(:,x),ty));
elseif x>25&&x<=50&&m==0
disp(sprintf('第%d组数据分类后为%s类',50+rbow2(:,x),'none'));
end
if x>50&&x<=75&&m>0
disp(sprintf('第%d组数据分类后为%s类',100+rbow3(:,x-25),ty));
elseif x>50&&x<=75&&m==0
disp(sprintf('第%d组数据分类后为%s类',100+rbow3(:,x-25),'none'));
end
if (x<=25&&m==1)||(x>25&&x<=50&&m==2)||(x>50&&x<=75&&m==3)
sum=sum+1;
end
end
disp(sprintf('第%d次分类识别率为%4.2f',ii,sum/75)); totalsum=totalsum+(sum/75);
end
disp(sprintf('10次分类平均识别率为%4.2f',totalsum/10));
测试结果：
第3组数据分类后为Iris-setosa类
第5组数据分类后为Iris-setosa类
第6组数据分类后为Iris-setosa类
第7组数据分类后为Iris-setosa类
第10组数据分类后为Iris-setosa类
第11组数据分类后为Iris-setosa类
第12组数据分类后为Iris-setosa类
第14组数据分类后为Iris-setosa类
第16组数据分类后为Iris-setosa类
第18组数据分类后为Iris-setosa类
第19组数据分类后为Iris-setosa类
第20组数据分类后为Iris-setosa类
第23组数据分类后为Iris-setosa类
第24组数据分类后为Iris-setosa类
第26组数据分类后为Iris-setosa类
第28组数据分类后为Iris-setosa类
第30组数据分类后为Iris-setosa类
第31组数据分类后为Iris-setosa类
第34组数据分类后为Iris-setosa类
第37组数据分类后为Iris-setosa类
第39组数据分类后为Iris-setosa类
第41组数据分类后为Iris-setosa类
第44组数据分类后为Iris-setosa类
第45组数据分类后为Iris-setosa类
第49组数据分类后为Iris-setosa类
第51组数据分类后为Iris-versicolor类
第53组数据分类后为Iris-versicolor类
第54组数据分类后为Iris-versicolor类
第55组数据分类后为Iris-versicolor类
第57组数据分类后为Iris-versicolor类
第58组数据分类后为Iris-versicolor类
第59组数据分类后为Iris-versicolor类
第60组数据分类后为Iris-versicolor类
第61组数据分类后为Iris-versicolor类
第62组数据分类后为Iris-versicolor类
第68组数据分类后为Iris-versicolor类第70组数据分类后为Iris-versicolor类第71组数据分类后为Iris-virginica类第74组数据分类后为Iris-versicolor类第75组数据分类后为Iris-versicolor类第77组数据分类后为Iris-versicolor类第79组数据分类后为Iris-versicolor类第80组数据分类后为Iris-versicolor类第84组数据分类后为Iris-virginica类第85组数据分类后为Iris-versicolor类第92组数据分类后为Iris-versicolor类第95组数据分类后为Iris-versicolor类第97组数据分类后为Iris-versicolor类第98组数据分类后为Iris-versicolor类第99组数据分类后为Iris-versicolor类第102组数据分类后为Iris-virginica类第103组数据分类后为Iris-virginica类第105组数据分类后为Iris-virginica类第106组数据分类后为Iris-virginica类第107组数据分类后为Iris-versicolor类第108组数据分类后为Iris-virginica类第114组数据分类后为Iris-virginica类第118组数据分类后为Iris-virginica类第119组数据分类后为Iris-virginica类第124组数据分类后为Iris-virginica类第125组数据分类后为Iris-virginica类第126组数据分类后为Iris-virginica类第127组数据分类后为Iris-virginica类第128组数据分类后为Iris-virginica类第129组数据分类后为Iris-virginica类第130组数据分类后为Iris-virginica类第133组数据分类后为Iris-virginica类第135组数据分类后为Iris-virginica类第137组数据分类后为Iris-virginica类第138组数据分类后为Iris-virginica类第142组数据分类后为Iris-virginica类第144组数据分类后为Iris-virginica类第148组数据分类后为Iris-virginica类第149组数据分类后为Iris-virginica类第150组数据分类后为Iris-virginica类
k近邻法对wine分类：
clc;
otalsum=0;
for ii=1:10 %循环测试10次
data=load('wine.txt');%导入wine数据
data1=data(1:59,1:13);%任取第一类数据的30组
rbow1=randperm(59);
trainsample1=data1(sort(rbow1(:,1:30)),1:13);
rbow1(:,31:59)=sort(rbow1(:,31:59)); %剩余的29组按行下标大小顺序排列
testsample1=data1(rbow1(:,31:59),1:13);
data2=data(60:130,1:13);%任取第二类数据的35组
rbow2=randperm(71);
trainsample2=data2(sort(rbow2(:,1:35)),1:13);
rbow2(:,36:71)=sort(rbow2(:,36:71));
testsample2=data2(rbow2(:,36:71),1:13);
data3=data(131:178,1:13);%任取第三类数据的24组
rbow3=randperm(48);
trainsample3=data3(sort(rbow3(:,1:24)),1:13);
rbow3(:,25:48)=sort(rbow3(:,25:48));
testsample3=data3(rbow3(:,25:48),1:13);
train_sample=cat(1,trainsample1,trainsample2,trainsample3);%包含89组数据的样本集
test_sample=cat(1,testsample1,testsample2,testsample3); k=19;%19近邻法
newchar=zeros(1,89);
sum=0;
[i,j]=size(train_sample);%i=89,j=13
[u,v]=size(test_sample);%u=89,v=13
for x=1:u
for y=1:i
result=sqrt((test_sample(x,1)-train_sample(y,1))^2+(test_sample(x,2)-train_sample(y,2))^2+(test_ sample(x,3)-train_sample(y,3))^2+(test_sample(x,4)-train_sample(y,4))^2+(test_sample(x,5)-train _sample(y,5))^2+(test_sample(x,6)-train_sample(y,6))^2+(test_sample(x,7)-train_sample(y,7))^2+ (test_sample(x,8)-train_sample(y,8))^2+(test_sample(x,9)-train_sample(y,9))^2+(test_sample(x,1
0)-train_sample(y,10))^2+(test_sample(x,11)-train_sample(y,11))^2+(test_sample(x,12)-train_sa mple(y,12))^2+(test_sample(x,13)-train_sample(y,13))^2); %欧式距离
newchar(1,y)=result;
end;
[new,Ind]=sort(newchar); class1=0; class 2=0; class 3=0;
for n=1:k
if Ind(1,n)<=30
class 1= class 1+1;
elseif Ind(1,n)>30&&Ind(1,n)<=65
class 2= class 2+1;
else
class 3= class3+1;
end
end
if class 1>= class 2&& class1>= class3
m=1;
elseif class2>= class1&& class2>= class3
m=2;
elseif class3>= class1&& class3>= class2
m=3;
end
if x<=29
disp(sprintf('第%d组数据分类后为第%d类',rbow1(:,30+x),m));
elseif x>29&&x<=65
disp(sprintf('第%d组数据分类后为第%d类',59+rbow2(:,x+6),m));
elseif x>65&&x<=89
disp(sprintf('第%d组数据分类后为第%d类',130+rbow3(:,x-41),m));
end
if (x<=29&&m==1)||(x>29&&x<=65&&m==2)||(x>65&&x<=89&&m==3)
sum=sum+1;
end
end
disp(sprintf('第%d次分类识别率为%4.2f',ii,sum/89));
totalsum=totalsum+(sum/89);
end
disp(sprintf('10次分类平均识别率为%4.2f',totalsum/10));
第2组数据分类后为第1类
第4组数据分类后为第1类
第5组数据分类后为第3类
第6组数据分类后为第1类
第8组数据分类后为第1类
第10组数据分类后为第1类
第11组数据分类后为第1类
第14组数据分类后为第1类
第19组数据分类后为第1类第20组数据分类后为第3类第21组数据分类后为第3类第22组数据分类后为第3类第26组数据分类后为第3类第27组数据分类后为第1类第28组数据分类后为第1类第30组数据分类后为第1类第33组数据分类后为第1类第36组数据分类后为第1类第37组数据分类后为第1类第43组数据分类后为第1类第44组数据分类后为第3类第45组数据分类后为第1类第46组数据分类后为第1类第49组数据分类后为第1类第52组数据分类后为第1类第54组数据分类后为第1类第56组数据分类后为第1类第57组数据分类后为第1类第60组数据分类后为第2类第61组数据分类后为第3类第63组数据分类后为第3类第65组数据分类后为第2类第66组数据分类后为第3类第67组数据分类后为第2类第71组数据分类后为第1类第72组数据分类后为第2类第74组数据分类后为第1类第76组数据分类后为第2类第77组数据分类后为第2类第79组数据分类后为第3类第81组数据分类后为第2类第82组数据分类后为第3类第83组数据分类后为第3类第84组数据分类后为第2类第86组数据分类后为第2类第87组数据分类后为第2类第88组数据分类后为第2类第93组数据分类后为第2类第96组数据分类后为第1类第98组数据分类后为第2类第99组数据分类后为第3类
第104组数据分类后为第2类第105组数据分类后为第3类第106组数据分类后为第2类第110组数据分类后为第3类第113组数据分类后为第3类第114组数据分类后为第2类第115组数据分类后为第2类第116组数据分类后为第2类第118组数据分类后为第2类第122组数据分类后为第2类第123组数据分类后为第2类第124组数据分类后为第2类第133组数据分类后为第3类第134组数据分类后为第3类第135组数据分类后为第2类第136组数据分类后为第3类第139组数据分类后为第3类第140组数据分类后为第3类第142组数据分类后为第3类第144组数据分类后为第2类第145组数据分类后为第1类第146组数据分类后为第3类第148组数据分类后为第3类第149组数据分类后为第2类第152组数据分类后为第2类第157组数据分类后为第2类第159组数据分类后为第3类第161组数据分类后为第2类第162组数据分类后为第3类第163组数据分类后为第3类第164组数据分类后为第3类第165组数据分类后为第3类第167组数据分类后为第3类第168组数据分类后为第3类第173组数据分类后为第3类第174组数据分类后为第3类
五：问题和收获：
该算法的优缺点总结为：
优点：算法简单且识别率较高；
缺点：算法需要计算未知样本x与周围每个样本的距离，然后排序选择最近的k个近邻，计算量和时间复杂度高。
书本上有好多优化的k近邻法，比如，快速搜索近邻法、剪切近邻法、压缩近邻法等，但就个人能力而言，上述优化的算法不太容易编程实现。在日后的学习中，自己也要加强优化算法的能力。
第2章k-近邻算法(kNN) 引言 本章介绍kNN算法的基本理论以及如何使用距离测量的方法分类物品。其次，将使用python从文本文件中导入并解析数据，然后，当存在许多数据来源时，如何避免计算距离时可能碰到的一些常见的错识。 2.1 k-近邻算法概述 k-近邻(k Nearest Neighbors)算法采用测量不同特征之间的距离方法进行分类。它的工作原理是：存在一个样本数据集合，并且样本集中每个数据都存在标签，即我们知道样本每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据的分类标签。一般来说，我们只选择样本数据集中前k 个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。 k-近邻算法的优点是精度高，对异常值不敏感，无数据输入假定；缺点是计算复杂度高、空间复杂度高。适用于数值和离散型数据。 2.1.1 准备知识：使用python导入数据 首先，创建名为kNN.py的python模块，然后添加下面代码： from numpy import * #引入科学计算包 import operator #经典python函数库。运算符模块。
#创建数据集 def createDataSet(): group=array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]]) labels=['A','A','B','B'] return group,labels 测试：>>> import kNN >>> group,labels=kNN.createDataSet() 注意：要将kNN.py文件放到Python27文件夹下，否则提示找不到文件。 2.2.2 实施kNN算法 使用k-近邻算法将每组数据划分到某个类中，其伪代码如下： 对未知类别属性的数据集中的每个点依次执行以下操作： 1.计算已知类别数据集中的点与当前点之间的距离； 2.按照距离递增交序排序； 3.选取与当前点距离最小的k个点； 4.确定前k个点所在类别的出现频率； 5.返回前k个点出现频率最高的类别作为当前点的预测分类。 用欧氏距离公式，计算两个向量点xA和xB之间的距离： 例如，点(0, 0)与(1, 2)之间的距离计算为: python函数classify()程序如下所示：
球面上的K 最近邻查询算法 张丽平a ，李 松a ，郝晓红b (哈尔滨理工大学a. 计算机科学与技术学院；b. 计算中心，哈尔滨 150080) 摘 要：针对球面上数据对象点集的特征和K 最近邻查询的需求，提出2种处理球面上K 最近邻查询的算法：基于查询轴的K 最近邻查询算法(PAM 方法)和基于查询圆面的K 最近邻查询算法(PCM 方法)。对2种算法进行实验比较，结果表明，PAM 方法和PCM 方法都适合处理球面上的最近邻查询问题，PAM 方法在存储量和查询复杂度方面相对于PCM 方法具有一定优势，但PAM 方法的可扩展性远低于 PCM 方法，尤其不适合处理受限查询和带方向的查询。 关键词：最近邻；球面；查询轴；查询圆面；索引结构 Algorithms for K-Nearest Neighbor Query on Sphere ZHANG Li-ping a , LI Song a , HAO Xiao-hong b (a. School of Computer Science and Technology; b. Computation Center, Harbin University of Science and Technology, Harbin 150080, China) 【Abstract 】According to the characteristics of the datasets on the sphere, the algorithm of the K -Nearest Neighbor query based on the query axis (PAM) and the algorithm of the K-Nearest Neighbor query based on the query circular planar(PCM) are presented. Theoretical research and experimental results show that both the two methods can handle the problem of the K -Nearest Neighbor query on the sphere, compared with the PCM, PAM has advantages on the memory capacitance and the query efficiency, but the expansibility of PAM is poor and PCM has high scalability. 【Key words 】nearest neighbor; sphere; query axis; query circular planar; index structure DOI: 10.3969/j.issn.1000-3428.2011.02.018 计 算 机 工 程 Computer Engineering 第37卷 第2期 V ol.37 No.2 2011年1月 January 2011 ·软件技术与数据库· 文章编号：1000—3428(2011)02—0052—02文献标识码：A 中图分类号：TP391 1 概述 随着空间定位技术、地理信息系统和智能查询技术的发展， 对空间对象的近邻查询及其变种的研究成为空间数据库领域研究的热点和难点。近年来，国内外对空间对象的近邻关系查询问题进行了大量的工作，取得了一定的研究成 果[1-5]，但其主要是对二维平面中的近邻查询问题进行分析，没有进一步给出球面上的数据对象集的最近邻查询的算法，研究成果在具体应用中具有一定的局限性。本文着重对球面上数据对象点的K 最近邻查询算法进行研究。 2 球面上的K 最近邻查询算法 根据球面上数据对象点的特征和K 最近邻查询的要求，本节给出基于查询轴的K 最近邻查询算法(PAM 方法)和基于查询圆面的K 最近邻查询算法(PCM 方法)。 2.1 基于查询轴的K 最近邻查询算法(PAM 方法) 定义1 设P ={p 1, p 2,…, p n }(2≤n ≤∞)为球面S 2上的对象点集，X i 和X j 分别为点p i ∈S 和p j ∈S 的位置矢量，点p i 和p j 之间的最短距离定义为通过点p i 和p j 的大圆(其中心点即为球的中心)中较小弧段的长度。这个距离用公式表达为： d (p i , p j )=arcos(T i j X X )≤π 称此距离为点p i 和p j 之间的球面距离。 定义2 过查询点q 和球心o 的直线称之为q 的查询轴， q 的查询轴具有唯一性。q 的查询轴与球面相交的另一点q ’称为q 的球面对称点。以查询轴作为一维刻度轴，查询轴上的数据点到查询点q 的距离称为轴查询距离。球面上的数据点在查询轴上的投影称之为轴投影点。 查询轴及查询圆面如图1所示，直线qq ’是查询轴，查询轴上的点o 3是球面上的点p 12的轴投影点。由球的性质可知，判断球面上点集之间的弧的长短可以转化为判断欧式空间内的直线段的大小。且球面上的数据对象点到查询点 q 之间的球面距离大小关系在q 的查询轴上投影后保持不变。 若查询点q 的位置固定，球面上其他数据点在球面上移动，移动点到查询点q 的距离关系在查询轴上因数据点的移动而做相应变化，其变化情况与球面上的一致。球面上数据点到q 的距离大小关系及其动态距离关系的变化在q 的查询轴上可得到较好的保持。由此，可将查询点q 在球面数据集中的K 最近邻问题降维到q 的查询轴上进行处理，从而降低了查询的难度。基于查询轴的方法主要适用于球面上的数据对象点是静态或动态、查询点q 的更新频率较低的情况。 图1 查询轴及查询圆面 若球面S 2上数据集中的数据点是静态的，数据集的动态变化主要限于增加或删除数据点，此时可用二叉树或B 树来处理一维查询轴空间内的查询点q 的K 最近邻查询问题。当球面数据集中增加点或删除点时，相应的树索引结构可进行局部的插入或删除更新。具体算法如算法1所示。 基金项目：黑龙江省教育厅科学技术研究基金资助项目(11551084) 作者简介：张丽平(1976－)，女，讲师、硕士，主研方向：数据结构，数据库理论；李 松，讲师、博士；郝晓红，高级实验师 收稿日期：2010-07-02 E-mail ：zhanglptg@https://www.doczj.com/doc/4d2570245.html,
K近邻算法 算法介绍： K最近邻(k-Nearest neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。 KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法（和该样本距离小的邻居权值大）来改进。 该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
最近邻法和k-近邻法 学号：02105120姓名：吴林一.基本概念： 最近邻法：对于未知样本x，比较x与N个已知类别的样本之间的欧式距离，并决策x与距离它最近的样本同类。 K近邻法：取未知样本x的k个近邻，看这k个近邻中多数属于哪一类，就把x归为哪一类。K取奇数，为了是避免k1=k2的情况。 二.问题分析： 要判别x属于哪一类，关键要求得与x最近的k个样本（当k=1时，即是最近邻法），然后判别这k个样本的多数属于哪一类。 可采用欧式距离公式求得两个样本间的距离s=sqrt（（x1-x2）^2+(y1-y2)^2） 三.算法分析： 该算法中任取每类样本的一半作为训练样本，其余作为测试样本。例如iris中取每类样本的25组作为训练样本，剩余25组作为测试样本，依次求得与一测试样本x距离最近的k 个样本，并判断k个样本多数属于哪一类，则x就属于哪类。测试10次，取10次分类正确率的平均值来检验算法的性能。 四.MATLAB代码： 最近邻算实现对Iris分类 clc; totalsum=0; for ii=1:10 data=load('iris.txt'); data1=data(1:50,1:4);%任取Iris-setosa数据的25组 rbow1=randperm(50); trainsample1=data1(rbow1(:,1:25),1:4); rbow1(:,26:50)=sort(rbow1(:,26:50));%剩余的25组按行下标大小顺序排列testsample1=data1(rbow1(:,26:50),1:4); data2=data(51:100,1:4);%任取Iris-versicolor数据的25组 rbow2=randperm(50); trainsample2=data2(rbow2(:,1:25),1:4); rbow2(:,26:50)=sort(rbow2(:,26:50)); testsample2=data2(rbow2(:,26:50),1:4); data3=data(101:150,1:4);%任取Iris-virginica数据的25组 rbow3=randperm(50); trainsample3=data3(rbow3(:,1:25),1:4); rbow3(:,26:50)=sort(rbow3(:,26:50)); testsample3=data3(rbow3(:,26:50),1:4);
学号：02105120 姓名：吴林一.基本概念： 最近邻法：对于未知样本x，比较x与N个已知类别的样本之间的欧式距离，并决策x与距离它最近的样本同类。 K近邻法：取未知样本x的k个近邻，看这k个近邻中多数属于哪一类，就把x归为哪一类。K取奇数，为了是避免k1=k2的情况。 二.问题分析： 要判别x属于哪一类，关键要求得与x最近的k个样本（当k=1时，即是最近邻法），然后判别这k个样本的多数属于哪一类。 可采用欧式距离公式求得两个样本间的距离s=sqrt（（x1-x2）^2+(y1-y2)^2） 三.算法分析： 该算法中任取每类样本的一半作为训练样本，其余作为测试样本。例如iris中取每类样本的25组作为训练样本，剩余25组作为测试样本，依次求得与一测试样本x距离最近的k 个样本，并判断k个样本多数属于哪一类，则x就属于哪类。测试10次，取10次分类正确率的平均值来检验算法的性能。 四.MATLAB代码： 最近邻算实现对Iris分类 clc; totalsum=0; for ii=1:10 data=load(''); data1=data(1:50,1:4);%任取Iris-setosa数据的25组 rbow1=randperm(50); trainsample1=data1(rbow1(:,1:25),1:4); rbow1(:,26:50)=sort(rbow1(:,26:50));%剩余的25组按行下标大小顺序排列 testsample1=data1(rbow1(:,26:50),1:4); data2=data(51:100,1:4);%任取Iris-versicolor数据的25组 rbow2=randperm(50); trainsample2=data2(rbow2(:,1:25),1:4); rbow2(:,26:50)=sort(rbow2(:,26:50)); testsample2=data2(rbow2(:,26:50),1:4); data3=data(101:150,1:4);%任取Iris-virginica数据的25组 rbow3=randperm(50); trainsample3=data3(rbow3(:,1:25),1:4); rbow3(:,26:50)=sort(rbow3(:,26:50)); testsample3=data3(rbow3(:,26:50),1:4); trainsample=cat(1,trainsample1,trainsample2,trainsample3);%包含75组数据的样本集 testsample=cat(1,testsample1,testsample2,testsample3); newchar=zeros(1,75);sum=0; [i,j]=size(trainsample);%i=60,j=4 [u,v]=size(testsample);%u=90,v=4 for x=1:u
k近邻算法(knn, k nearest neighbor) 前两天受朋友之托，帮忙与两个k近邻算法，k近邻的非正式描述，就是给定一个样本集exset，样本数为M，每个样本点是N维向量，对于给定目标点d，d也为N维向量，要从exset中找出与d距离最近的k个点(k<=N)，当k=1时，knn问题就变成了最近邻问题。最naive的方法就是求出exset中所有样本与d的距离，进行按出小到大排序，取前k个即为所求，但这样的复杂度为O(N)，当样本数大时，效率非常低下. 我实现了层次knn(HKNN)和kdtree knn，它们都是通过对树进行剪枝达到提高搜索效率的目的，hknn的剪枝原理是(以最近邻问题为例)，如果目标点d与当前最近邻点x的距离，小于d与某结点Kp中心的距离加上Kp的半径，那么结点Kp中的任何一点到目标点的距离都会大于d 与当前最近邻点的距离，从而它们不可能是最近邻点(K近邻问题类似于它)，这个结点可以被排除掉。 kdtree对样本集所在超平面进行划分成子超平面，剪枝原理是，如果某个子超平面与目标点的最近距离大于d与当前最近点x的距离，则该超平面上的点到d的距离都大于当前最近邻点，从而被剪掉。两个算法均用matlab实现(应要求)，把代码帖在下面，以备将来查用或者需要的朋友可以参考. function y = VecDist(a, b) %%返回两向量距离的平方 assert(length(a) == length(b)); y = sum((a-b).^2); end 下面是HKNN的代码
classdef Node < handle %UNTITLED2 Summary of this class goes here % Detailed explanation goes here % Node 层次树中的一个结点，对应一个样本子集Kp properties Np; %Kp的样本数 Mp; %Kp的样本均值，即中心 Rp; %Kp中样本到Mp的最大距离 Leafs; %生成的子节点的叶子,C * k矩阵,C为中心数量，k是样本维数。如果不是叶结点，则为空 SubNode; %子节点, 行向量 end methods function obj = Node(samples, maxLeaf) global SAMPLES
最近邻法和k-近邻法 一.基本概念： 最近邻法：对于未知样本x，比较x与N个已知类别的样本之间的欧式距离，并决策x 与距离它最近的样本同类。 K近邻法：取未知样本x的k个近邻，看这k个近邻中多数属于哪一类，就把x归为哪一类。K取奇数，为了是避免k1=k2的情况。 二.问题分析： 要判别x属于哪一类，关键要求得与x最近的k个样本（当k=1时，即是最近邻法），然后判别这k个样本的多数属于哪一类。 可采用欧式距离公式求得两个样本间的距离s=sqrt（（x1-x2）^2+(y1-y2)^2） 三.算法分析： 该算法中任取每类样本的一半作为训练样本，其余作为测试样本。例如iris中取每类样本的25组作为训练样本，剩余25组作为测试样本，依次求得与一测试样本x距离最近的k 个样本，并判断k个样本多数属于哪一类，则x就属于哪类。测试10次，取10次分类正确率的平均值来检验算法的性能。 四.MATLAB代码： 最近邻算实现对Iris分类 clc; totalsum=0; for ii=1:10 data=load('iris.txt'); data1=data(1:50,1:4);%任取Iris-setosa数据的25组 rbow1=randperm(50); trainsample1=data1(rbow1(:,1:25),1:4); rbow1(:,26:50)=sort(rbow1(:,26:50));%剩余的25组按行下标大小顺序排列 testsample1=data1(rbow1(:,26:50),1:4); data2=data(51:100,1:4);%任取Iris-versicolor数据的25组 rbow2=randperm(50); trainsample2=data2(rbow2(:,1:25),1:4); rbow2(:,26:50)=sort(rbow2(:,26:50)); testsample2=data2(rbow2(:,26:50),1:4); data3=data(101:150,1:4);%任取Iris-virginica数据的25组 rbow3=randperm(50); trainsample3=data3(rbow3(:,1:25),1:4); rbow3(:,26:50)=sort(rbow3(:,26:50)); testsample3=data3(rbow3(:,26:50),1:4); trainsample=cat(1,trainsample1,trainsample2,trainsample3);%包含75组数据的样本集testsample=cat(1,testsample1,testsample2,testsample3); newchar=zeros(1,75);sum=0; [i,j]=size(trainsample);%i=60,j=4 [u,v]=size(testsample);%u=90,v=4 for x=1:u for y=1:i
k 近邻模型和算法 2.1 K 近邻模型 K 近邻法使用的模型实际上对应于对特征空间的划分。模型由三个基本要素 —-距离度量、k 值得选择和分类规则决定。 2.1.1 模型 K 近邻法中，当训练集、距离度量（如欧式距离）、k 值及分类决策规则（如多数表决）确定后，对于任何一个新的输入实例，它所属的类唯一确定。这相当于根据上述要素将特征空间划分为一些子空间，确定子空间里的每个点所述的类。这一事实从最近邻算法中可以看得很清楚。 特征空间中，对每个实例点i x ,距离该点比其他店更近的所有点组成一个区域，叫做单元。每个训练实例点拥有一个单元，所有训练实例点的单元构成对特 征空间的一个划分。最近邻法将实例i x 的类i y 作为其单元中所有点的类标记。这样，每个单元的实例点的类别时确定的。下图是二维特征空间划分的一个例子。 2.1.2 距离度量
特征空间中两个实例点的距离是两个点相似程度的反映。K 近邻模型的特征空间一般是n 维实数向量空间Rn 。使用的距离是欧式距离，但也可以是其他距离，如更一般的Lp 或闽科夫斯基距离。 设特征空间χ是n 维实数向量空间n R ，i x ，,),,,(,) ()2()1(T n i i i i j x x x x x =∈χ ,),,,() ()2()1(T n j j j j x x x x =j i x x ,的距离定义为P L p n l p l j l i j i p x x x x L 11),(? ?? ??-=∑= 这里1≥p 。当2=p 时，称为欧式距离，即 2 1 122,??? ??-=∑=n l l j l i j i x x x x L ） （ 当 时，称为曼哈顿距离，即 ∑=-=n l l j l i j i x x x x L 1 1,） （ 当∞=p 时，它是各个距离坐标的最大值，即 l j l i l j i x x x x L -=∞max ),( 2.1.3 K 值的选择 k 值的选择会对k 近邻法的结果产生重大影响。 如果选择较小的k 值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差会减小，只有与输入实例较近的（相似的）训练实例才会对预测结果起作用。但缺点是“学习”的估计误差会增大，预测结果会对近邻的实例点非常敏感。如果近邻的实例点恰巧是噪声，预测就会出错。换句话说，k 值得减小就意味着整体模型变得复杂，容易发生过拟合。 如果选择较大的k 值，就相当于用较大邻域中的训练实例进行预测。其优点是可以减少学习的估计误差。但缺点是学习的近似误差会增大。这时与输入实例较远的（不相似的）训练实例也会对预测起作用，是预测发生错误。K 值得增大就意味着整体的模型变得简单。 如果k=N ，那么无论输入实例是什么，都将简单的预测它属于在训练实例中最多的类。这时，模型过于简单，完全忽略训练实例中的大量有用信息，是不可取的。 2.1.4 分类决策规则 1 =p
K近邻分类的算法实现 K近邻（KNN）法的输入为实例的特征向量，对应于特征空间的点；输入为实例的类别，可以取多类。K近邻法假设给定一个训练数据集，其中的实例类别已定。分类时，对新的实例，根据其k个最近邻的训练实例的类别,通过多数表决等方式进行预测。因此K近邻不具有显式的学习过程。K近邻法实际上是利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。 1.1 选题背景 现如今，数据的爆炸式增长、广泛可用和巨大数量使得我们的时代成为真正的数据时代。急需功能强大和通用的工具，以便从这些海量数据中发现有价值的信息，把这些数据转化成有组织的知识。这种需求导致了数据挖掘的诞生。这个领域是年轻的、动态变化的、生机勃勃的。数据挖掘已经并且将继续在我们从数据时代大步跨入信息时代的历程中作出贡献。 K近邻方法是20世纪50年代早期首次引进的。当给定大量数据集时，该方法是计算密集的，直到20世纪60年代计算能力大大增强之后才流行起来。此后它广泛用于模式识别领域。 K近邻分类法是基于类比学习，即通过将给定的检验元组与它相似的训练元组进行比较来学习。训练元组用n个属性描述。每个元组代表n维空间的一个点。这样，所有的训练元组都存放在n维模式空间中。当给定一个未知元组时，k近邻分类法搜索模式空间，找出最接近元组的k个训练元组。这k个训练元组即为该元组的k个“最近邻”。 1.2 研究现状 国内外学者为此算法在实际生活中更好地应用做出了许多努力。例如对k近邻方法的不足做出的一些改进如文献[2]，[7]，[8]，[9]，[10]等等。在其他领域的应用如文献[5]将K近邻算法改进为非线性分类算法，以达到分类动态心电图波形的目的。文献[6]在KNN算法的基础上提出了图像自动分类模型。在生物学上，K近邻方法也得到了广泛地应用，有文献利用蛋白质相互作用网络,提出
题目k-最近邻算法实现学生姓名 学生学号 专业班级 指导教师 2015-1-2
实验二 k-最近邻算法实现 一、实验目的 1.加强对k-最近邻算法的理解； 2.锻炼分析问题、解决问题并动手实践的能力。 二、实验要求 使用一种你熟悉的程序设计语言，如C++或Java，给定最近邻数k和描述每个元组的属性数n，实现k-最近邻分类算法，至少在两种不同的数据集上比较算法的性能。 三、实验环境 Win7 旗舰版 + Visual Studio 2010 语言：C++ 四、算法描述 KNN(k Nearest Neighbors)算法又叫k最临近方法。假设每一个类包含多个样本数据，而且每个数据都有一个唯一的类标记表示这些样本是属于哪一个分类， KNN就是计算每个样本数据到待分类数据的距离。如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。因此，采用这种方法可以较好地避免样本的不平衡问题。另外，由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待
分样本集来说，KNN 方法较其他方法更为适合。该方法的不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K 个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。 1、 算法思路 K-最临近分类方法存放所有的训练样本，在接受待分类的新样本之前不需构造模型，并且直到新的（未标记的）样本需要分类时才建立分类。K-最临近分类基于类比学习，其训练样本由N 维数值属性描述，每个样本代表N 维空间的一个点。这样，所有训练样本都存放在N 维模式空间中。给定一个未知样本，k-最临近分类法搜索模式空间，找出最接近未知样本的K 个训练样本。这K 个训练样本是未知样本的K 个“近邻”。“临近性”又称为相异度（Dissimilarity ），由欧几里德距离定义，其中两个点 X （x1,x2,…,xn ）和Y （y1,y2,…,yn ）的欧几里德距离是： 2 222211)()()(),(n n y x y x y x y x D -+?+-+-= 未知样本被分配到K 个最临近者中最公共的类。在最简单的情况下，也就是当K=1时，未知样本被指定到模式空间中与之最临近的训练样本的类。 2、 算法步骤 初始化距离为最大值； 计算未知样本和每个训练样本的距离dist ； 得到目前K 个最临近样本中的最大距离maxdist ； 如果dist 小于maxdist ，则将该训练样本作为K-最近邻样本； 重复步骤2、3、4，直到未知样本和所有训练样本的距离都算完； 统计K-最近邻样本中每个类标号出现的次数； 选择出现频率最大的类标号作为未知样本的类标号。
题目k-最近邻算法实现学生 学生学号 专业班级 指导教师 2015-1-2
实验二k-最近邻算法实现 一、实验目的 1.加强对k-最近邻算法的理解； 2.锻炼分析问题、解决问题并动手实践的能力。 二、实验要求 使用一种你熟悉的程序设计语言，如C++或Java，给定最近邻数k和描述每个元组的属性数n，实现k-最近邻分类算法，至少在两种不同的数据集上比较算法的性能。 三、实验环境 Win7 旗舰版+ Visual Studio 2010 语言：C++ 四、算法描述 KNN(k Nearest Neighbors)算法又叫k最临近方法。假设每一个类包含多个样本数据，而且每个数据都有一个唯一的类标记表示这些样本是属于哪一个分类，KNN就是计算每个样本数据到待分类数据的距离。如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本
的类别来决定待分样本所属的类别。KNN 方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。因此，采用这种方法可以较好地避免样本的不平衡问题。另外，由于KNN 方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN 方法较其他方法更为适合。该方法的不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K 个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。 1、 算法思路 K-最临近分类方法存放所有的训练样本，在接受待分类的新样本之前不需构造模型，并且直到新的（未标记的）样本需要分类时才建立分类。K-最临近分类基于类比学习，其训练样本由N 维数值属性描述，每个样本代表N 维空间的一个点。这样，所有训练样本都存放在N 维模式空间中。给定一个未知样本，k-最临近分类法搜索模式空间，找出最接近未知样本的K 个训练样本。这K 个训练样本是未知样本的K 个“近邻”。“临近性”又称为相异度（Dissimilarity ），由欧几里德距离定义，其中两个点 X （x1,x2,…,xn ）和Y （y1,y2,…,yn ）的欧几里德距离是： 2 222211)()()(),(n n y x y x y x y x D -+?+-+-= 未知样本被分配到K 个最临近者中最公共的类。在最简单的情况下，也就是当K=1时，未知样本被指定到模式空间中与之最临近的训练样本的类。
模式识别作业 K近邻算法 姓名： 班级： 学号： 二零一一年十二月
K近邻算法 一、K近邻基本描述： K近邻就是在N个样本中，找出x 的K个近邻。设这N个样本中，来自Wc类的样本有Nc个，若K1，K2，…Kc分别是K个近邻中属于W1，W2，…，Wc类的样本数，则我们可以定义判别函数为： g i x=k i，i=1，2，3，…，c 决策规则为：若 g j x=max k i i 则决策x∈w j。这就是K近邻的基本规则。 二、基本算法流程如下： （1）取A[1]~A[k]作为x的初始临近，计算与测试样本x间的欧氏距离d（x，A[ i ]），i=1~k； （2）按d（x，A[ i ]）升序排序，计算最远样本与x间的距离D←max{ d （x，A[ j ]）}，j=1~k； （3）for（i=k+1；i<=n; i++） （4）计算A[ i ]与x间的距离d（x，A[ i ]）; （5）if d（x，A[ i ]） 三、实验结果： 导入iris训练样本之后得到的结果 由图可以得知我们算得的结果为第一类的聚类准确率为1.0000，第二类聚类的准确率为0.93333，第三类聚类的准确率为0.93333。总体准确率为0.93333。 四、程序源代码 #include KNN算法详解 一、算法概述 1、kNN算法又称为k近邻分类(k-nearest neighbor classification)算法。 最简单平凡的分类器也许是那种死记硬背式的分类器，记住所有的训练数据，对于新的数据则直接和训练数据匹配，如果存在相同属性的训练数据，则直接用它的分类来作为新数据的分类。这种方式有一个明显的缺点，那就是很可能无法找到完全匹配的训练记录。 kNN算法则是从训练集中找到和新数据最接近的k条记录，然后根据他们的主要分类来决定新数据的类别。该算法涉及3个主要因素：训练集、距离或相似的衡量、k的大小。 2、代表论文 Discriminant Adaptive Nearest Neighbor Classification Trevor Hastie and Rolbert Tibshirani 3、行业应用 客户流失预测、欺诈侦测等（更适合于稀有事件的分类问题） 二、算法要点 1、指导思想 kNN算法的指导思想是“近朱者赤，近墨者黑”，由你的邻居来推断出你的类别。 计算步骤如下： ?1）算距离：给定测试对象，计算它与训练集中的每个对象的距离?2）找邻居：圈定距离最近的k个训练对象，作为测试对象的近邻?3）做分类：根据这k个近邻归属的主要类别，来对测试对象分类 2、距离或相似度的衡量 什么是合适的距离衡量？距离越近应该意味着这两个点属于一个分类的可能性越大。 觉的距离衡量包括欧式距离、夹角余弦等。 对于文本分类来说，使用余弦(cosine)来计算相似度就比欧式(Euclidean)距离更合适。 3、类别的判定 投票决定：少数服从多数，近邻中哪个类别的点最多就分为该类。 加权投票法：根据距离的远近，对近邻的投票进行加权，距离越近则权重越大（权重为距离平方的倒数） 三、优缺点 简单，易于理解，易于实现，无需估计参数，无需训练 适合对稀有事件进行分类（例如当流失率很低时，比如低于0.5%，构造流失预测模型） 特别适合于多分类问题(multi-modal,对象具有多个类别标签)，例如根据基因特征来判断其功能分类，kNN比SVM的表现要好 懒惰算法，对测试样本分类时的计算量大，内存开销大，评分慢 可解释性较差，无法给出决策树那样的规则。 四、常见问题 ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 ２００７，４３（７）１引言 孤立点检测是数据挖掘中的一个重要方向。在ＫＤＤ应用 中研究孤立点有时比研究聚类、更重要。因为在某些应用领域中研究孤立点的异常行为能发现隐藏在数据集中更有价值的知识。诸如，在欺诈探测中，孤立点可能预示着欺诈行为；在市场分析中，可用于确定极低或极高的收入的消费行为；在医疗分析中，用于发现对多种治疗方式的不寻常的反映；此外孤立点检测还可应用于金融欺诈、网络监控、数据清洗、电子商务、职业运动员的成绩分析、故障检测、天气预报、医药研究、信贷信用等众多领域。孤立点检测可以描述如下：给定一个ｎ个数据点或对象的集合，及预期的孤立点的数目ｎ，发现与剩余的数据相比显著相异的、异常的或不一致的头ｎ个对象［１］。因此孤立点检测的对象是数据集中与其他数据有明显不同特征的一小部分数据。现有的孤立点检测算法大体上可分为以下几类：统计学方法，基于距离的方法，基于偏离的方法和基于密度的方法。 传统的孤立点检测方法将每个对象要么看成是属于簇中的点，要么是孤立点／噪声。基于密度的孤立点检测方法给每个对象赋予一个度来反映它的偏离程度。ＬＯＦ［２］是一种典型的基于密度的孤立点检测方法，它通过计算每个对象的局部孤立因子ＬＯＦ（ｐ）来反映该点的偏离程度，并将前ｎ个具有最大ＬＯＦ值的对象作为孤立点。局部孤立因子的计算是基于局部的密度即每个点的孤立程度只与它周围的对象有关，而与数据集中其 他的对象没有任何关系，因此如果数据集中含有不同密度的簇，各簇周围的孤立点也能很好地区分开。 Ｋｏｒｎ和Ｍｕｔｈｕｋｒｉｓｈｎａｎ最早在参考文献［６］提出了反向近 邻（ＲＮＮ）的概念，后来又将反向近邻的概念延伸到反向Ｋ近邻（ＲＫＮＮ），一个点ｐ的反向Ｋ近邻［３］（ＲＫＮＮ）是那些Ｋ个最近邻中包含ｐ的点的集合。最近在参考文献［６］中的研究表明了反向近邻在决策支持系统、移动设备管理、连续的推荐系统和文档存储等诸多领域中的应用。点ｐ的反向Ｋ近邻个数越小，说明它的偏离程度越大，点ｐ越有可能是一个孤立点，于是利用反向Ｋ近邻的这个性质提出一个孤立点检测算法Ｏ－ ＤＲＫＮＮ，在综合数据集和真实数据集上的实验结果表明，该算 法能有效地检测出孤立点，且算法的效率高于典型的基于密度的孤立点检测算法ＬＯＦ和ＬＳＣ的效率。 ２ＯＤＲＫＮＮ算法 ２．１相关概念 定义１［３］对任意的正整数Ｋ和数据集Ｄ，计算点ｐ与所有点之间的距离，并选取前Ｋ个（除点ｐ外）最近的点作为它的Ｋ近邻。对象ｐ的Ｋ近邻记作ＫＮＮＫ（Ｐ）。 定义２［３］对任意的正整数Ｋ和数据集Ｄ，对象ｐ的反向Ｋ近邻（记作ＲＫＮＮＫ（Ｐ））是那些Ｋ最近邻中包含ｐ的点的集合，即ＲＫＮＮＫ（Ｐ）＝｛ｐｉ｜ｐｉ∈Ｄ∩ｐ∈ＫＮＮＫ（Ｐｉ）｝。 点ｐ的反向Ｋ近邻的定义是基于全局的角度（而不是从点 作者简介：岳峰（１９８０－），男，硕士研究生，主要研究方向为数据挖掘；邱保志（１９６４－），男，副教授，硕士生导师，主要研究方向为数据挖掘。 基于反向Ｋ近邻的孤立点检测算法 岳 峰，邱保志 ＹＵＥＦｅｎｇ，ＱＩＵＢａｏ－ｚｈｉ 郑州大学信息工程学院，郑州４５００５２ ＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｏｎ＆Ｅｎｇｉｎｅｅｒｉｎｇ，ＺｈｅｎｇｚｈｏｕＵｎｉｖｅｒｓｉｔｙ，Ｚｈｅｎｇｚｈｏｕ４５００５２，ＣｈｉｎａＥ－ｍａｉｌ：ｙｕｅｆｅｎｇ２００５＠ｔｏｍ．ｃｏｍ ＹＵＥＦｅｎｇ，ＱＩＵＢａｏ－ｚｈｉ．ＯｕｔｌｉｅｒｄｅｔｅｃｔｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎＲｅｖｅｒｓｅＫＮｅａｒｅｓｔＮｅｉｇｈｂｏｒｓ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２００７，４３（７）：１８２－１８４． Ａｂｓｔｒａｃｔ：ＴｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｓａｎｅｗｏｕｔｌｉｅｒｄｅｔｅｃｔｉｏｎａｌｇｏｒｉｔｈｍＯＤＲＫＮＮｂａｓｅｄｏｎｒｅｖｅｒｓｅＫｎｅａｒｅｓｔｎｅｉｇｈｂｏｒｓ．ＯＤＲＫＮＮｃｏｕｎｔｓｔｈｅｎｕｍｂｅｒｏｆｅａｃｈｐｏｉｎｔ’ｓｒｅｖｅｒｓｅＫｎｅａｒｅｓｔｎｅｉｇｈｂｏｒｓｔｏｒｅｆｌｅｃｔｉｔｓｉｓｏｌａｔｉｏｎｄｅｇｒｅｅ，ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｏｎｓｙｎｔｈｅｓｉｚｅｄａｎｄｒｅａｌｗｏｒｌｄｄａｔａｓｅｔｓｈｏｗｔｈａｔＯＤＲＫＮＮｃａｎｅｆｆｉｃｉｅｎｔｌｙｄｅｔｅｃｔｏｕｔｌｉｅｒｓａｎｄｈａｓｈｉｇｈｅｒｅｆｆｉｃｉｅｎｃｙｔｈａｎｏｕｔｌｉｅｒｓｄｅｔｅｃｔｉｏｎａｌｇｏ－ｒｉｔｈｍＬＯＦａｎｄＬＳＣ． Ｋｅｙｗｏｒｄｓ：ｏｕｔｌｉｅｒｓ；ＫＮｅａｒｅｓｔＮｅｉｇｈｂｏｒｓ；ＲｅｖｅｒｓｅＫＮｅａｒｅｓｔＮｅｉｇｈｂｏｒｓ（ＲＫＮＮ） 摘 要：提出了基于反向Ｋ近邻（ＲＫＮＮ）的孤立点检测算法ＯＤＲＫＮＮ。ＯＤＲＫＮＮ算法用每个数据点的反向Ｋ近邻个数来衡量该 数据点的偏离程度，在综合数据集和真实数据集上的实验结果表明，该算法能有效地检测出孤立点，且算法的效率高于算法ＬＯＦ和ＬＳＣ的效率。 关键词：孤立点；Ｋ近邻；反向Ｋ近邻文章编号：１００２－８３３１（２００７）０７－０１８２－０３ 文献标识码：Ａ 中图分类号：ＴＰ３１１ １８２ 第一部分、K近邻算法 1.1、什么是K近邻算法 何谓K近邻算法，即K-Nearest Neighbor algorithm，简称KNN算法，单从名字来猜想，可以简单粗暴的认为是：K个最近的邻居，当K=1时，算法便成了最近邻算法，即寻找最近的那个邻居。为何要找邻居？打个比方来说，假设你来到一个陌生的村庄，现在你要找到与你有着相似特征的人群融入他们，所谓入伙。 用官方的话来说，所谓K近邻算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例（也就是上面所说的K个邻居），这K个实例的多数属于某个类，就把该输入实例分类到这个类中。根据这个说法，咱们来看下引自维基百科上的一幅图： 如上图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。也就是说，现在，我们不知道中间那个绿色的数据是从属于哪一类（蓝色小正方形or红色小三角形），下面，我们就要解决这个问题：给这个绿色的圆分类。 我们常说，物以类聚，人以群分，判别一个人是一个什么样品质特征的人，常常可以从他/她身边的朋友入手，所谓观其友，而识其人。我们不是要判别上图中那个绿色的圆是属于哪一类数据么，好说，从它的邻居下手。但一次性看多少个邻居呢？从上图中，你还能看到： ?如果K=3，绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一 类。 ?如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形 一类。 于此我们看到，当无法判定当前待分类点是从属于已知分类中的哪一类时，我们可以依据统计学的理论看它所处的位置特征，衡量它周围邻居的权重，而把它归为(或分配)到权重更大的那一类。这就是K近邻算法的核心思想。 1.2、近邻的距离度量表示法 上文第一节，我们看到，K近邻算法的核心在于找到实例点的邻居，这个时候，问题就接踵而至了，如何找到邻居，邻居的判定标准是什么，用什么来度量。这一系列问题便是下面要讲的距离度量表示法。但有的读者可能就有疑问了，我是要找邻居，找相似性，怎么又跟距离扯上关系了？ 这是因为特征空间中两个实例点的距离和反应出两个实例点之间的相似性程度。K近邻模型的特征空间一般是n维实数向量空间，使用的距离可以使欧式距离，也是可以是其它距离，既然扯到了距离，下面就来具体阐述下都有哪些距离度量的表示法，权当扩展。 ? 1. 欧氏距离，最常见的两点之间或多点之间的距离表示法，又称之为欧几里得度量，它定义于欧几里得空间中，如点x = (x1,...,xn) 和y = (y1,...,yn) 之间的距离为： (1)二维平面上两点a(x1,y1)与b(x2,y2)间的欧氏距离： (2)三维空间两点a(x1,y1,z1)与b(x2,y2,z2)间的欧氏距离： (3)两个n维向量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的欧氏距离：K N N ( k 近 邻 ) 机 器 学 习 算 法 详 解
基于反向K近邻的孤立点检测算法
K近邻算法
相关主题
文本预览