基于留一法的快速KNN代码

本是古典何须时尚 2023-02-18 12:57 9阅读 0赞

本文共885个字，预计阅读时间需要3分钟。

## 留一法交叉验证（LOOCV） ##

留一法即Leave-One-Out Cross Validation。这种方法比较简单易懂，就是把一个大的数据集分为k个小数据集，其中k-1个作为训练集，剩下的一个作为测试集，然后选择下一个作为测试集，剩下的k-1个作为训练集，以此类推。其主要目的是为了防止过拟合，评估模型的泛化能力。计算时间较长。

**适用场景**：

数据集少，如果像正常一样划分训练集和验证集进行训练，那么可以用于训练的数据本来就少，还被划分出去一部分，这样可以用来训练的数据就更少了。loocv可以充分的利用数据。

KNN算法简介与MATLAB实现：[https://www.omegaxyz.com/2018/03/24/knn\_matlab/][https_www.omegaxyz.com_2018_03_24_knn_matlab]

## 快速留一法KNN ##

因为LOOCV需要划分N次，产生N批数据，所以在一轮训练中，要训练出N个模型，这样训练时间就大大增加。为了解决这样的问题，根据留一法的特性，我们可以提前计算出不同样本之间的距离（或者距离的中间值），存储起来。使用LOOCV时直接从索引中取出即可。下面的代码以特征选择为Demo，验证快速KNN留一法。

其中FSKNN1是普通KNN，FSKNN2是快速KNN

**主函数main.m**

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

**数据集划分divide\_dlbcl.m**

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

简单KNN

FSKNN1.m

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

KNN1.m

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

**快速KNN**

preKNN.m

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

FSKNN2.m

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

KNN2.m

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

数据集：[https://github.com/xyjigsaw/Dataset][https_github.com_xyjigsaw_Dataset] 下载DLBCL.mat即可。

## 结果 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h5aXN2_size_16_color_FFFFFF_t_70_pic_center]  
可以看到FSKNN2+preKNN的时间比FSKNN1要少很多。

[https_www.omegaxyz.com_2018_03_24_knn_matlab]: https://www.omegaxyz.com/2018/03/24/knn_matlab/
[https_github.com_xyjigsaw_Dataset]: https://github.com/xyjigsaw/Dataset
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h5aXN2_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200617222637575.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h5aXN2,size_16,color_FFFFFF,t_70#pic_center
[omegaxyz.com]: https://www.omegaxyz.com/