??鄰近算法，或者說(shuō)K最近鄰(kNN，k-NearestNeighbor)分類算法是數(shù)據(jù)挖掘分類技術(shù)中最簡(jiǎn)單的方法之一。所謂K最近鄰，就是k個(gè)最近的鄰居的意思，說(shuō)的是每個(gè)樣本都可以用它最接近的k個(gè)鄰居來(lái)代表。
??舉個(gè)例子：下圖中，綠色圓要被決定賦予哪個(gè)類，是紅色三角形還是藍(lán)色四方形？如果K=3，由于紅色三角形所占比例為2/3，綠色圓將被賦予紅色三角形那個(gè)類，如果K=5，由于藍(lán)色四方形比例為3/5，因此綠色圓被賦予藍(lán)色四方形類。

knn.png

??kNN算法的核心思想是如果一個(gè)樣本在特征空間中的k個(gè)最相鄰的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別，并具有這個(gè)類別上樣本的特性。該方法在確定分類決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類別來(lái)決定待分樣本所屬的類別。 kNN方法在類別決策時(shí)，只與極少量的相鄰樣本有關(guān)。由于kNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來(lái)確定所屬類別的，因此對(duì)于類域的交叉或重疊較多的待分樣本集來(lái)說(shuō)，kNN方法較其他方法更為適合。
??KNN算法不僅可以用于分類，還可以用于回歸。通過(guò)找出一個(gè)樣本的k個(gè)最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對(duì)該樣本產(chǎn)生的影響給予不同的權(quán)值(weight)，如權(quán)值與距離成反比。
簡(jiǎn)單的kNN源碼實(shí)現(xiàn)：

import java.util.LinkedList;
import java.util.List;

/**
 * kNN算法思想：
 * 找出與當(dāng)前節(jié)點(diǎn)距離（這里用最簡(jiǎn)單的歐式距離）最近的k個(gè)節(jié)點(diǎn)，然后通過(guò)這k的節(jié)點(diǎn)的所屬類型進(jìn)行投票分類。少數(shù)服從多數(shù)。
 * 約定原始數(shù)據(jù)為等長(zhǎng)度的double類型數(shù)組，最后一位表示數(shù)據(jù)的class類別屬性（默認(rèn)二分類0，1）
 * @author zhaoshiquan 2018年1月24日 下午2:25:12
 *
 */
public class Algorithm_kNN {
    public static double pos = 1.0;
    public static double neg = 0.0;

    public List<Res_Node> kNN(List<double[]> train, List<double[]> sample, int k){
        LinkedList<Res_Node> list = new LinkedList<Res_Node>();
        sample.forEach(s->{
            list.add(kNN(train, s, k));
        });
        return null;
    }
    
    public Res_Node kNN(List<double[]> train, double[] sample, int k){
        LinkedList<KNN_Node> list = new LinkedList<KNN_Node>();
        train.forEach(t->{
            insertNode(list, new KNN_Node(euclideanDistance(t, sample),t[t.length - 1]),k);
        });
        return getResult(list);
    }
    

    //歐式距離的計(jì)算
    private double euclideanDistance(double[] train, double[] sample){
        double sum = 0;
        for(int i = 0; i <sample.length; i++){
            sum += (sample[i] - train[i]) * (sample[i] - train[i]);
        }
        return sum;
    }

    //維護(hù)一個(gè)大小為k的有序的中間節(jié)點(diǎn)鏈表（根據(jù)distance排序）
    private void insertNode(LinkedList<KNN_Node> list, KNN_Node node, int k){

        //插入排序，并移除最后一個(gè)節(jié)點(diǎn)
        int orig = list.size();
        for(int i = 0; i< list.size(); i++){
            if(list.get(i).dist >= node.dist){
                list.add(i, node);
                break;
            }
        }

        //判斷當(dāng)前節(jié)點(diǎn)是否加入list中
        if(orig == list.size())
            list.addLast(node);

        //判斷l(xiāng)ist是否超過(guò)長(zhǎng)度k
        if(list.size() > k){
            list.removeLast();
        }
    }

    //獲取分類結(jié)果
    private Res_Node getResult(LinkedList<KNN_Node> list){
        int count_pos = 0;
        for(KNN_Node n:list){
            if(n.label > 0.5)
                count_pos++;
        }
        double conf = 1.0 * count_pos / list.size();
        return conf>=0.5 ? new Res_Node(pos,conf) : new Res_Node(neg, 1 - conf); 
    }


    class KNN_Node{
        double dist = Double.MAX_VALUE;
        double label;
        public KNN_Node(double dist, double label){
            this.dist = dist;
            this.label = label;
        }
    }

    class Res_Node{

        public double label = neg;

        /**
         * confidence表示當(dāng)前樣本分類為label的置信度
         */
        public double confidence = pos;

        public Res_Node(double label, double confidence){
            this.label = label;
            this.confidence = confidence;
        }

        @Override
        public String toString() {
            return "Res_Node [label=" + label + ", confidence=" + confidence + "]";
        }
    }

}

測(cè)試數(shù)據(jù)及分類結(jié)果：

public static void main(String[] args) {
        //測(cè)試數(shù)據(jù)
        List<double[]> train = new ArrayList<>();
        double[] t1 = {1,1,1,1,1};
        double[] t2 = {1,2,1,0,0};
        double[] t3 = {1,3,1,3,1};
        double[] t4 = {1,2,4,1,0};
        double[] t5 = {1,0,5,1,0};
        double[] t6 = {1,0,9,1,0};
        double[] t7 = {1,1,2,1,1};
        double[] t8 = {1,4,1,1,0};
        double[] t9 = {1,5,0,1,1};
        double[] t10 = {1,8,4.5,1,1};
        train.add(t1);
        train.add(t2);
        train.add(t3);
        train.add(t4);
        train.add(t5);
        train.add(t6);
        train.add(t7);
        train.add(t8);
        
        double[] s1 = {0.0,0.0,0.0,1};
        double[] s2 = {2,6,3,1};
        double[] s3 = {1,1,2,0};
        
        Algorithm_kNN knn = new Algorithm_kNN();
        System.out.println(knn.kNN(train,s1,5));
        System.out.println(knn.kNN(train,s2,7));
        System.out.println(knn.kNN(train,s3,10));
        
    }


分類結(jié)果：
Res_Node [label=1.0, confidence=0.6]
Res_Node [label=0.0, confidence=0.5714285714285714]
Res_Node [label=0.0, confidence=0.625]

kNN三要素

??kNN模型由三要素——距離度量方式、k值選定和分類決策規(guī)則來(lái)確定。

距離度量

??特征空間中兩個(gè)點(diǎn)實(shí)例之間的距離是兩個(gè)實(shí)例相似程度的反應(yīng)。kNN一般使用的距離是歐式距離，但也可以是其他距離，如更一般的距離。
??這里的。當(dāng)時(shí)，稱為曼哈頓距離，即：
??當(dāng)時(shí)，稱為歐氏距離，即：

k值選擇

??k值得選擇會(huì)之間對(duì)kNN模型的結(jié)果產(chǎn)生影響。k值較小時(shí)，只選擇較小的領(lǐng)域內(nèi)的訓(xùn)練實(shí)例進(jìn)行預(yù)測(cè)，學(xué)習(xí)的近似誤差會(huì)比較小，但是學(xué)習(xí)的估計(jì)誤差會(huì)比價(jià)大，因?yàn)轭A(yù)測(cè)的結(jié)果會(huì)對(duì)鄰近的點(diǎn)比較敏感，k值越小意味著整體模型的復(fù)雜度較高，容易發(fā)生過(guò)擬合。
??如果選擇的k值較大，相當(dāng)于用較大領(lǐng)域的數(shù)據(jù)進(jìn)行預(yù)測(cè)。優(yōu)點(diǎn)是可以減少估計(jì)誤差，但是近似誤差會(huì)增大。k值越大意味著模型的復(fù)雜度越低，模型相對(duì)越簡(jiǎn)單。在實(shí)際應(yīng)用中，k值一般是一個(gè)比較小的值，通?？梢酝ㄟ^(guò)交叉驗(yàn)證大來(lái)選擇最優(yōu)的k值

分類決策規(guī)則

??kNN的分類決策規(guī)則一般是少數(shù)服從多數(shù)，即多數(shù)表決規(guī)則。多數(shù)表決規(guī)則等價(jià)于經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化。
??以上就是kNN的全部?jī)?nèi)容，在實(shí)際實(shí)施過(guò)程中，kNN需要考慮如何針對(duì)訓(xùn)練數(shù)據(jù)快速地進(jìn)行kNN檢索。最簡(jiǎn)單的方法是線性掃描，但是這種方法在數(shù)據(jù)量特別大的時(shí)候，計(jì)算非常耗時(shí)。一種較快的kNN檢索的方式稱為k-d Tree，可以使用k-d樹(shù)對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行存儲(chǔ)，并在k-d樹(shù)的基礎(chǔ)上進(jìn)行kNN檢索。