knn原理与实践

knn法是一种基本分类与回归方法

应用：knn算法不仅可以用于分类，还可以用于回归..

1、文本分类：文本分类主要应用于信息检索，机器翻译，自动文摘，信息过滤，邮件分类等任务.

2、可以使用knn算法做到比较通用的现有用户产品推荐，基于用户的最近邻(长得最像的用户)买了什么产品来推荐是种介于电子商务网站和sns网站之间的精确营销.只需要定期(例如每月)维护更新最近邻表就可以，基于最近邻表做搜索推荐可以很实时

优点：

1、简单，易于理解，易于实现，无需估计参数，无需训练，选择合适的k，对异常值不敏感；

2、适合于多分类问题(multi-modal,对象具有多个类别标签)

3、可拓展性强，添加新实例无需重新构造模型

缺点：

1、当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数.可以采用权值的方法（和该样本距离小的邻居权值大）来改进.

2、计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点.对于大数据分类，即需要大量的训练样本，计算复杂度高

3、可理解性差，无法给出像决策树那样的规则.

距离度量：

1、高维度对距离衡量的影响：众所周知当变量数越多，欧式距离的区分能力就越差.

2、变量值域对距离的影响：值域越大的变量常常会在距离计算中占据主导作用，因此应先对变量进行标准化.

K值选择：目前采用交叉验证方式，选出误差率最小的对应的K

构造：

1、随着树的深度增加，循环的选取坐标轴，作为分割超平面的法向量。对于3-d tree来说，根节点选取x轴，根节点的孩子选取y轴，根节点的孙子选取z轴，根节点的曾孙子选取x轴，这样循环下去。

2、每次均为所有对应实例的中位数的实例作为切分点，切分点作为父节点，左右两侧为划分的作为左右两子树。

对于n个实例的k维数据来说，建立kd-tree的时间复杂度为O(k*n*logn)。

搜索：

最近邻搜索如下（k最近邻，搜索k次，每次将上一次最近邻删除）

1、首先从根节点出发找到包含目标点的叶节点，目标点的最近邻一定在以目标点为中心，并通过当前叶节点的超球体内部，

2、然后从该叶节点出发，依次回退到父节点，

3、如果父节点的另一子节点的区域与超球体相交，则到该区域继续查找，不断的查找与目标点最近邻的节点，直到不能查找最近邻的节点为止。

############################R语言#########################

library(class)

knn(train,test,cl,k=1,l=0,prob=FALSE,use.all=TRUE)

################################案例###########################################

##############################案例#############################################

library(class)

library(nutshell) ######取数据集spambase做案例#########

library(sampling) ########用抽样函数strata做抽样###################

data(spambase)

spambase.strata<-strata(spambase,stratanames=c("is_spam"),size=c(1269,1951)

,method="srswor") ########变量ID_unit#描述了样本中的行号信息###########

spambase.training<-spambase[rownames(spambase)%in%spambase.strata$ID_unit,]

#####训练集#############

spambase.validation<-spambase[!(rownames(spambase)%in%spambase.strata$ID_unit),]

######验证集###############

spambase.knn<-knn(train=spambase.training,test=spambase.validation,

cl=spambase.training$is_spam)

##########cl:训练数据的响应变量(因子类型)######################

summary(spambase.knn)

table(predicted=spambase.knn,actual=spambase.validation$is_spam)

####################matlab代码:包含分类与回归#######################

functionrelustLabel=KNN(test,train,trainlabels,k,type) %% test 为一条输入测试数据，train为样本数据，trainlabels为样本标签,选取k个临近值 

    row = size(train,1);

    for j=1:row

        switch type 

            case 1  % 求test到每个样本的欧氏距离 

                distanceMat(j)=sum((test-train(j,:)).^2);

            case 2  %求test到每个样本的夹角余弦               

                distanceMat(j)=(train(j,:)*test')/(norm(train(j,:),2)*norm(test,2)); 

                if distanceMat(j)<0 

                    distanceMat(j)=(distanceMat(j)+1)/2;

                end

        end

    end

    distanceMat=distanceMat'; 

    [B, IX] = sort(distanceMat,'ascend');  %距离从小到大排序

    len = min(k,length(B));  %选k个邻近值，当然k不能超过训练样本个数 

    relustLabel = mode(trainlabels(IX(1:len))); % 取众数（即出现频率最高的label）作为返回结果

    %%%%%%%%%%%%%%%%%对于回归而言： relustLabel = avg(trainlabels(IX(1:len)))

end

 %主程序：

loaddata; 

dataMat = data(:,1:3);

labels = data(:,4);

len = size(dataMat,1);

k = 4; 

error = 0;

%观察可视化数据 

label1=find(data(:,4)==1);

label2=find(data(:,4)==2);

label3=find(data(:,4)==3); 

plot3(data(label1,1),data(label1,2),data(label1,3),'ro'); 

hold on 

plot3(data(label2,1),data(label2,2),data(label2,3),'go');

plot3(data(label3,1),data(label3,2),data(label3,3),'bo'); 

grid on  %归一化处理 

maxV = max(dataMat);

minV = min(dataMat);

range = maxV-minV;

newdataMat =  (dataMat-repmat(minV,[len,1]))./(repmat(range,[len,1])); 

%测试数据比例

Ratio = 0.1; 

numTest = Ratio * len; % 100条测试, 900条训练

%训练数据和测试数据 

TrainData=newdataMat(numTest+1:end,:);

TrainLabels=labels(numTest+1:end,:);

TestData=newdataMat(1:numTest,:);

TestLabels=labels(1:numTest,:); %测试，欧氏距离type=1, 夹角余弦type=2 

type=1; 

for i = 1:numTest

    classifyresult =  KNN(TestData(i,:),TrainData,TrainLabels,k,type);

    % fprintf('第 %d 条记录，测试结果为：%d  真实结果为：%d\n',[iclassifyresult(i) labels(i)])

    [classifyresult labels(i)])

        if(classifyresult~=labels(i))

            error = error+1;

        end

end

classifyresult=classifyresult';

fprintf('分类错误的记录标签为：') 

Index=find(classifyresult~=TestLabels)

fprintf('准确率为：%f\n',1-error/(numTest))