K近邻算法（MATLAB）
4星 · 超过85%的资源 需积分: 50 105 浏览量
2014-06-24
16:10:35
上传
评论 6
收藏 119KB PDF 举报 
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 实现(应要求)，把代码帖在下面，以备将来查用或者需要
的朋友可以参考.
VecDist.m
function y = VecDist(a, b)
%%返回两向量距离的平方
assert(length(a) == length(b));
y = sum((a-b).^2);
end
下面是 HKNN 的代码
Node.m
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
%samples 是个列向量，它里面的元素是 SAMPLES 的行的下标,而不是 SAMPLES
资源评论
想念_呐殇2016-01-04不错，K近邻算法正在用- c_x_g2017-01-26K近邻算法简单而实用，其实推荐系统中的协同过滤算法就是基于K近邻思想的。 本资源给出了K按住的matlab实现，适合初学者学习。
