基于留一法的快速KNN代码

ubeautqq

留一法交叉验证（LOOCV）
留一法即Leave-One-Out Cross Validation。这种方法比较简单易懂，就是把一个大的数据集分为k个小数据集，其中k-1个作为训练集，剩下的一个作为测试集，然后选择下一个作为测试集，剩下的k-1个作为训练集，以此类推。其主要目的是为了防止过拟合，评估模型的泛化能力。计算时间较长。
: t5 w3 S8 K1 v! P
1 b. I: y! _# l" a适用场景：

: E6 F4 e- _# q) @& B4 n数据集少，如果像正常一样划分训练集和验证集进行训练，那么可以用于训练的数据本来就少，还被划分出去一部分，这样可以用来训练的数据就更少了。loocv可以充分的利用数据。
, b: P, b: ~. h1 X

# z# _$ o/ j/ R6 N快速留一法KNN

+ |' U/ ]9 W1 w! x因为LOOCV需要划分N次，产生N批数据，所以在一轮训练中，要训练出N个模型，这样训练时间就大大增加。为了解决这样的问题，根据留一法的特性，我们可以提前计算出不同样本之间的距离（或者距离的中间值），存储起来。使用LOOCV时直接从索引中取出即可。下面的代码以特征选择为Demo，验证快速KNN留一法。
0 M. V9 {5 d4 Z' \% @
其中FSKNN1是普通KNN，FSKNN2是快速KNN

主函数main.m
9 m2 n# s0 N5 E9 k7 W# Q

• clc
• [train_F,train_L,test_F,test_L] = divide_dlbcl();
• dim = size(train_F,2);
• individual = rand(1,dim);
• global choice
• choice = 0.5;
• global knnIndex
• [knnIndex] = preKNN(individual,train_F);
• for i = 1:100
•     [error,fs] = FSKNN1(individual,train_F,train_L);
•     [error2,fs2] = FSKNN2(individual,train_F,train_L);
• end
  1 U- {$ V) u! y/ g

7 y* _" j! O0 T( b: L9 S5 l' S
( B; ?0 t- t7 K0 @数据集划分divide_dlbcl.m
7 E7 D3 q  k& `5 M) ?
; ?" N, G7 {# T1 p2 o" P+ y

• function [train_F,train_L,test_F,test_L] = divide_dlbcl()
• load DLBCL.mat;
• dataMat=ins;
• len=size(dataMat,1);
• %归一化
• maxV = max(dataMat);
• minV = min(dataMat);
• range = maxV-minV;
• newdataMat = (dataMat-repmat(minV,[len,1]))./(repmat(range,[len,1]));
• Indices   =  crossvalind('Kfold', length(lab), 10);
• site = find(Indices==1|Indices==2|Indices==3);
• test_F = newdataMat(site,：);
• test_L = lab(site);
• site2 = find(Indices~=1&Indices~=2&Indices~=3);
• train_F = newdataMat(site2,：);
• train_L =lab(site2);
• end
  

6 f( _% r# P9 A, `, `9 S
" ?$ x! w% R+ L! D. Q4 ?简单KNN
- @5 g0 `, g' g& Q& {+ ~4 X
FSKNN1.m

. ^# Q4 m' L5 c. X+ r6 ~

• function [error,fs] = FSKNN1(x,train_F,train_L)
• global choice
• inmodel = x>choice;%%%%%设定恰当的阈值选择特征
• k=1;
• train_f=train_F(:,inmodel);
• train_length = size(train_F,1);
• flag = logical(ones(train_length,1));
• error=0;
• for j=1:train_length
•     flag(j) = 0;
•     CtrainF = train_f(flag,：);
•     CtrainL = train_L(flag);
•     CtestF = train_f(~flag,：);
•     CtestL = train_L(~flag);
•     classifyresult= KNN1(CtestF,CtrainF,CtrainL,k);
•     if (CtestL~=classifyresult)
•         error=error+1;
•     end
•     flag(j) = 1;
• end
•   error=error/train_length;
•   fs = sum(inmodel);
• end
  " g, e9 a* h: U  a

6 u- J8 E) ~, }2 [% t1 n
* n. V4 Q  e4 JKNN1.m

5 i& R, x0 `  x" o/ `/ a4 D

• function relustLabel = KNN1(inx,data,labels,k)
• %%
• %   inx 为 输入测试数据，data为样本数据，labels为样本标签 k值自定1~3
• %%
• [datarow , datacol] = size(data);
• diffMat = repmat(inx,[datarow,1]) - data ;
• distanceMat = sqrt(sum(diffMat.^2,2));
• [B , IX] = sort(distanceMat,'ascend');
• len = min(k,length(B));
• relustLabel = mode(labels(IX(1:len)));
• end
  

  G3 L( I/ [6 K. ~快速KNN

preKNN.m
- ]; {1 H7 K* J4 h9 {
0 o2 m* \) X. I6 e+ h. ~

• function [knnIndex] = preKNN(x,train_F)
•     inmodel = x > 0;
•     train_f=train_F(:,inmodel);
•     train_length = size(train_F,1);
•     flag = logical(ones(train_length,1));
•     knnIndex = cell(train_length,1);
•     for j=1:train_length
•         flag(j) = 0;
•         CtrainF = train_f(flag,：);
•         CtestF = train_f(~flag,：);
•         [datarow , ~] = size(CtrainF);
•         diffMat = repmat(CtestF,[datarow,1]) - CtrainF ;
•         diffMat = diffMat.^2;
•         knnIndex{j,1} = diffMat;
•         flag(j) = 1;
•     end
• end
  ! y- d. C9 O3 k5 x+ A! ^, v; A/ k9 G5 L

0 Z" ?: {, v' s4 Q+ P; v3 ?+ }
FSKNN2.m
( E; m% B& z/ @; T

• function [error,fs] = FSKNN2(x,train_F,train_L)
• global choice
• inmodel = x>choice;%%%%%设定恰当的阈值选择特征
• global knnIndex
• k=1;
• train_length = size(train_F,1);
• flag = logical(ones(train_length,1));
• error=0;
• for j=1:train_length
•     flag(j) = 0;
•     CtrainL = train_L(flag);
•     CtestL = train_L(~flag);
•     classifyresult= KNN2(CtrainL,k,knnIndex{j}(:,inmodel));
•     if(CtestL~=classifyresult)
•         error=error+1;
•     end
•     flag(j) = 1;
• end
•   error=error/train_length;
•   fs = sum(inmodel);
• end
  

* C9 U# @9 l, t: E1 a  C; Y' h9 R
0 P% k! }9 c. A/ dKNN2.m

  Q, t* F$ g$ l: i/ h) C- L+ ]0 M! e

• function relustLabel = KNN2(labels,k,diffMat)
• distanceMat = sqrt(sum(diffMat,2));
• [B , IX] = sort(distanceMat,'ascend');
• len = min(k,length(B));
• relustLabel = mode(labels(IX(1:len)));
• end
  * a' A9 V9 T+ C7 [  Q: E

7 c6 E0 K" i1 m9 A) H
( d0 f3 D* D" ]& z: q/ s4 w" b6 w结果

$ }- w1 x3 h, h4 R8 n  S/ W

( I% j* b$ R" c6 V1 V; Y% z可以看到FSKNN2+preKNN的时间比FSKNN1要少很多。

ExxNEN

基于留一法的快速KNN代码

smileqq

基于留一法的快速KNN代码

SsaaM7

基于留一法的快速KNN代码