one-class(单分类) kNN(K-Nearest Neighbor)算法Matlab实现

one-class(单分类) kNN(K-Nearest Neighbor)算法Matlab实现

本文的核心是给出了一个基于kNN的单分类（one-class）分类器实现代码，并给出了数据以及运行实例，让读者能更好地理解并使用。代码基于MATLAB平台实现。而多分类的KNN代码已经比较多了，比如https://blog.csdn.net/queyuze/article/details/70195087博客中就给出了其实现。

1.首先是单分类分类器的介绍

1.1二分类问题

首先，学过机器学习的人都应该比较了解二分类SVM，这里引用网上一个比较糊的图，但是能看出这里是针对两种label的数据进行了SVM边界构建。而多分类可以由多个二分类构建，这里非本文重点就不详细介绍了。

1.2单分类问题（one-class）

单分类问题（one-class）不像常见的二分类或多分类问题，其目的并不是将有不同label的数据区分开来，而更像是对单个类别的特征生成一个轮廓与描述（description）。这里感觉轮廓更好理解一点，可以理解为是样本空间中的一个区域，当某个样本落在这个区域外，我们就认为该样本不属于这个类别。单分类方法常用于异常检测，或者类别极度不平衡的分类任务中。

算法层面：当我们假设数据服从一个概率分布，我们就可以对这个分布中的参数进行估计了。对于一个新样本，如果这个样本在给定类别的概率分布中的概率小于阈值，就会被判定为异常样本。

2.常用单分类SVM的缺点

2.1 SVDD简介

其基本思想是通过在映射到高维的特征空间中找出一个包围目标样本点的超球体（在如上特征降维可视化的二维图片，就是一个包围目标样本点的圆形），并通过最小化该超球体所包围的体积让目标样本点尽 能地被包围在超球体中，而非目标样本点尽可能地排除在超球体中，从而达到正常类以非正常类之间划分的目的。

其训练过程如下：

1.基于合法用户的数据进行训练（通常是多个特征向量）
2.获得SVDD单分类分类器
3.基于此分类器对于一个未知样本进行分类，结果为正常类（可以理解为在上图的黑色边界内）或者异常类（可以理解为在上图的黑色边界外）。

基本所有的单分类分类认证都是这个过程，比如在一些感知认证工作中，由于实际的场景往往只有正样本，所以选择单分类分类器作为其模型。

2.2 SVDD缺点

但是在实际使用中SVDD有一定的缺点，就是这个边界的松紧不能细粒度的调整，以使得我们实验中没法获得全面的分析数据。以第二张图为例，这个边界如果变大了，就是变松一点，那么误拒绝合法用户的概率就会低，因为模型正例的空间域变大了。反之如果边界变小，就是变紧，那么模型正例的空间域变小。这个松紧调整的意义在于我们可以细粒度地对我们的算法性能进行分析。

曾经在我的论文实验中，我十分希望如下以细粒度地调整模型的松紧，如下表所示。

来观察设计的算法性能，比如FAR和FRR的变化，SVDD试了多次发现是不能满足如下这样细粒度要求的，其粒度会比较粗，使得我们无法全方位评估我们算法性能。MATLAB自带的fitsvm函数选下实现SVDD，这个OutlierFraction代表了假设 7% 的观测值是离群值，对预测变量进行标准化。而实际上，当我们的样本数不足100而只有十几个的时候，往往以样本的离群值为代表，就只有较少的粒度。比如可能7%和10%都是代表固定个数样本的离群值。

SVMModel = fitcsvm(traindataout,labeltrain,'KernelFunction','RBF',
'KernelScale','auto','Standardize',true,'OutlierFraction',0.07);

本文核心想法：所以我换了思路，不以训练样本中的离群数代表模型松紧，我们将这个松紧粒度放在分类时进行调整。简单来说，我们利用KNN是基于距离度量的特性，我们获得测试样本与训练样本的距离与训练样本之间的距离，基于这两个值的比值是否小于一个阈值来判断，而我们可以对这个阈值实现细粒度的调整，实现模型松紧的细粒度调整。具体实现如下：

3.基于KNN的单分类分类器实现

3.1训练阶段

给定N个训练样本的特征数据，每一个特征数据向量记为di,i在1-N，其中dij表示第i个特征向量和第j个特征向量之间的曼哈顿距离或者欧式距离。基于M我们可以衡量这个训练样本的簇密度，代表了训练样本数据的特性。
M = ∑ i = 1 N − 1 ∑ j = i + 1 N d i j C N 2 M=\frac{\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}d_{ij}}{C_{N}^{2}} M=CN2​∑i=1N−1​∑j=i+1N​dij​​

function [M] = oneclass_KNN_train(traindata,distype)
% training process
% this function returns the threshold(M)  of traindata.
% It takes 2 input arguments
% which are traindata,distype.
% distype is the cityblock distance(1) or the euclidean distance(2)
    [n,~]=size(traindata);
    M=0;
    for i=1:n%此处计算平均距离
        temp=traindata(i,:);
        for j=i+1:n         % 计算其到所有traindata的距离，并排序
            a=[temp;traindata(j,:)];
            if distype==1
                dis=pdist(a,'cityblock');
            else
               dis=pdist(a,'euclidean');
            end
            M=M+dis;
        end
    end
    M=2*M/((n-1)*n);
end

3.2分类阶段

给定一个测试样本f，我们将其特征数据向量与所有的di进行距离计算，选出其中最小的k个距离值，并求该k个距离值的平均值记为m。

那么基于m与M的比较，我们可以判断测试样本的分类结果。其中我们基于基于λ进行模型松紧的细粒度调整。
T e s t r e s u l t = { l e g i t i m a t e   u s e r , m ≤ λ × M a t t a c k e r , m > λ × M Testresult = \begin{cases} legitimate \ user, & m \leq \lambda \times M \\ attacker, & m > \lambda \times M \end{cases} Testresult={legitimate user,attacker,​m≤λ×Mm>λ×M​

function [ positive_num ] = oneclass_KNN_test( traindata,testdata,k,M,ratio,distype)
% testing process
% this function returns the positive number of testdata.
% It takes 6 input arguments
% which are traindata,testdata,k,threshold,ratio,distype.
% k means the parameter of kNN, threshold means the Denisty calculated from
% training process, ratio is the tradeoff between FNR and FPR
% distype is the cityblock distance(1) or the euclidean distance(2)
    [n,~]=size(traindata);
    [n2,~]=size(testdata);
    dis=ones(1,n); %用于计算每一次的距离
    accnum=0;
    for i=1:n2 %对于n2个testdata数据行进行认证测试
        temp=testdata(i,:);
        for j=1:n         % 计算其到所有traindata的距离，并排序
            a=[temp;traindata(j,:)];
            if distype==1
                    dis(j)=pdist(a,'cityblock');
            else
                    dis(j)=pdist(a,'euclidean');
            end
        end
        dis=sort(dis);
        ithreshold=0;
        for p=1:k           % 对于p个距离计算其均值
            ithreshold=ithreshold+dis(p);
        end
        ithreshold=ithreshold/p;
        if(ithreshold<M*ratio)% 如果K均值小于阈值，则认为是合法值
            accnum=accnum+1;
        end
    end
    positive_num = accnum;
end

这里traindata和testdata的数据格式如下

M = d 12 + d 23 + d 13 C 3 2 M=\frac{d12+d23+d13}{C_{3}^{2}} M=C32​d12+d23+d13​

基于M以及给定的模型松紧参数λ（比如λ = 1.1），以及计算的测试样本距离m，我们可以对一个测试样本向量进行分类

4.总结

我们基于MATLAB实现了one-class kNN分类器，解决了现有单分类分类器比如SVDD模型松紧不能细粒度调整的问题，并给出了实现代码。

博客系本人原创，如果有转载，请注明出处，如有错误欢迎评论指正，谢谢！