摘要：簡介源于數據挖掘的一個作業，這里用來實現一下這個機器學習中最簡單的算法之一算法最近鄰分類法。其實這些標簽就對應于機器學習中的特征這一重要概念，而訓練我們識別的過程就對應于泛化這一概念。

源于數據挖掘的一個作業， 這里用Node.js來實現一下這個機器學習中最簡單的算法之一k-nearest-neighbor算法(k最近鄰分類法)。

還是先嚴謹的介紹下。急切學習法（eager learner）是在接受待分類的新元組之前就構造了分類模型，學習后的模型已經就緒，急著對未知的元組進行分類，所以稱為急切學習法，諸如決策樹歸納，貝葉斯分類等都是急切學習法的例子。惰性學習法（lazy learner）正好與其相反，直到給定一個待接受分類的新元組之后，才開始根據訓練元組構建分類模型，在此之前只是存儲著訓練元組，所以稱為惰性學習法，惰性學習法在分類進行時做更多的工作。

本文的knn算法就是一種惰性學習法，它被廣泛應用于模式識別。knn基于類比學習，將未知的新元組與訓練元組進行對比，搜索模式空間，找出最接近未知元組的k個訓練元組，這里的k即是knn中的k。這k個訓練元祖就是待預測元組的k個最近鄰。

balabala了這么多，是不是某些同學想大喊一聲..speak Chinese! 還是來通俗的解釋下，然后再來看上面的理論應該會明白很多。小時候媽媽會指著各種各樣的東西教我們，這是小鴨子，這個紅的是蘋果等等，那我們哼哧哼哧的看著應答著，多次被教后再看到的時候我們自己就能認出來這些事物了。主要是因為我們在腦海像給這個蘋果貼了很多標簽一樣，不只是顏色這一個標簽，可能還有蘋果的形狀大小等等。這些標簽讓我們看到蘋果的時候不會誤認為是橘子。其實這些標簽就對應于機器學習中的特征這一重要概念，而訓練我們識別的過程就對應于泛化這一概念。一臺iphone戴了一個殼或者屏幕上有一道劃痕，我們還是能認得出來它，這對于我們人來說非常簡單，但蠢計算機就不知道怎么做了，需要我們好好調教它，當然也不能過度調教2333，過度調教它要把其他手機也認成iphone那就不好了，其實這就叫過度泛化。

所以特征就是提取對象的信息，泛化就是學習到隱含在這些特征背后的規律，并對新的輸入給出合理的判斷。

我們可以看上圖，綠色的圓代表未知樣本，我們選取距離其最近的k個幾何圖形，這k個幾何圖形就是未知類型樣本的鄰居，如果k=3，我們可以看到有兩個紅色的三角形，有一個藍色的三正方形，由于紅色三角形所占比例高，所以我們可以判斷未知樣本類型為紅色三角形。擴展到一般情況時，這里的距離就是我們根據樣本的特征所計算出來的數值，再找出距離未知類型樣本最近的K個樣本，即可預測樣本類型。那么求距離其實不同情況適合不同的方法，我們這里采用歐式距離。

綜上所述knn分類的關鍵點就是k的選取和距離的計算。

我的數據是一個xls文件，那么我去npm搜了一下選了一個叫node-xlrd的包直接拿來用。

    // node.js用來讀取xls文件的包
    var xls = require("node-xlrd");
 

然后直接看文檔copy實例即可，把數據解析后插入到自己的數據結構里。

var data = [];
// 將文件中的數據映射到樣本的屬性
var map = ["a","b","c","d","e","f","g","h","i","j","k"];
// 讀取文件
xls.open("data.xls", function(err,bk){
    if(err) {console.log(err.name, err.message); return;}
    var shtCount = bk.sheet.count;
    for(var sIdx = 0; sIdx < shtCount; sIdx++ ){
        var sht = bk.sheets[sIdx],
            rCount = sht.row.count,
            cCount = sht.column.count;
        for(var rIdx = 0; rIdx < rCount; rIdx++){
            var item = {};
            for(var cIdx = 0; cIdx < cCount; cIdx++){
                item[map[cIdx]] = sht.cell(rIdx,cIdx);
            }
            data.push(item);
        }
    }
    // 等文件讀取完畢后 執行測試
    run();
});

然后定義一個構造函數Sample表示一個樣本，這里是把剛生成的數據結構里的對象傳入，生成一個新的樣本。

    // Sample表示一個樣本
    var Sample = function (object) {
        // 把傳過來的對象上的屬性克隆到新創建的樣本上
        for (var key in object)
        {
            // 檢驗屬性是否屬于對象自身
            if (object.hasOwnProperty(key)) {
                this[key] = object[key];
            }
        }
    }

再定義一個樣本集的構造函數

// SampleSet管理所有樣本 參數k表示KNN中的k
var SampleSet = function(k) { 
    this.samples = [];
    this.k = k;
};

// 將樣本加入樣本數組
SampleSet.prototype.add = function(sample) {
    this.samples.push(sample);
}

然后我們會在樣本的原型上定義很多方法，這樣每個樣本都可以用這些方法。

// 計算樣本間距離 采用歐式距離
Sample.prototype.measureDistances = function(a, b, c, d, e, f, g, h, i, j, k) { 
    for (var i in this.neighbors)
    {
        var neighbor = this.neighbors[i];
        var a = neighbor.a - this.a;
        var b = neighbor.b - this.b;
        var c = neighbor.c - this.c;
        var d = neighbor.d - this.d;
        var e = neighbor.e - this.e;
        var f = neighbor.f - this.f;
        var g = neighbor.g - this.g;
        var h = neighbor.h - this.h;
        var i = neighbor.i - this.i;
        var j = neighbor.j - this.j;
        var k = neighbor.k - this.k;
       
        // 計算歐式距離
        neighbor.distance = Math.sqrt(a*a + b*b + c*c + d*d + e*e + f*f + g*g + h*h + i*i + j*j + k*k);
    }
};

// 將鄰居樣本根據與預測樣本間距離排序
Sample.prototype.sortByDistance = function() {
    this.neighbors.sort(function (a, b) {
        return a.distance - b.distance;
    });
};

// 判斷被預測樣本類別
Sample.prototype.guessType = function(k) {
    // 有兩種類別 1和-1
    var types = { "1": 0, "-1": 0 };
    // 根據k值截取鄰居里面前k個
    for (var i in this.neighbors.slice(0, k))
    {
        var neighbor = this.neighbors[i];
        types[neighbor.trueType] += 1;
    }
    
    // 判斷鄰居里哪個樣本類型多
    if(types["1"]>types["-1"]){
        this.type = "1";
    } else {
        this.type = "-1";
    }
    }

注意到我這里的數據有a-k共11個屬性，樣本有1和-1兩種類型，使用truetype和type來預測樣本類型和對比判斷是否分類成功。

最后是樣本集的原型上定義一個方法，該方法可以在整個樣本集里尋找未知類型的樣本，并生成他們的鄰居集，調用未知樣本原型上的方法來計算鄰居到它的距離，把所有鄰居按距離排序，最后猜測類型。

// 構建總樣本數組，包含未知類型樣本
SampleSet.prototype.determineUnknown = function() {
    /*
     * 一旦發現某個未知類型樣本，就把所有已知的樣本 
     * 克隆出來作為該未知樣本的鄰居序列。
     * 之所以這樣做是因為我們需要計算該未知樣本和所有已知樣本的距離。
     */
    for (var i in this.samples)
    {
        // 如果發現沒有類型的樣本
        if ( ! this.samples[i].type)
        {
            // 初始化未知樣本的鄰居
            this.samples[i].neighbors = [];
            
            // 生成鄰居集
            for (var j in this.samples)
            {
                // 如果碰到未知樣本 跳過
                if ( ! this.samples[j].type)
                    continue;
                this.samples[i].neighbors.push( new Sample(this.samples[j]) );
            }
            
            // 計算所有鄰居與預測樣本的距離
            this.samples[i].measureDistances(this.a, this.b, this.c, this.d, this.e, this.f, this.g, this.h, this.k);

            // 把所有鄰居按距離排序
            this.samples[i].sortByDistance();

            // 猜測預測樣本類型
            this.samples[i].guessType(this.k);
        }
    }
};

最后分別計算10倍交叉驗證和留一法交叉驗證的精度。
留一法就是每次只留下一個樣本做測試集，其它樣本做訓練集。
K倍交叉驗證將所有樣本分成K份，一般均分。取一份作為測試樣本，剩余K-1份作為訓練樣本。這個過程重復K次，最后的平均測試結果可以衡量模型的性能。
k倍驗證時定義了個方法先把數組打亂隨機擺放。

// helper函數 將數組里的元素隨機擺放
    function ruffle(array) {
        array.sort(function (a, b) {
            return Math.random() - 0.5;
        })
    }

剩余測試代碼好寫，這里就不貼了。
測試結果為

計算鄰居到未知樣本的距離主要有歐氏距離、余弦距離、漢明距離、曼哈頓距離等方式，this case用余弦距離等計算方式可能精度會更高。

knn算法非常簡單，但卻能在很多關鍵的地方發揮作用并且效果非常好。缺點就是進行分類時要掃描所有訓練樣本得到距離，訓練集大的話會很慢。
看似高大上的機器學習其實就是基于計算機科學，統計學，數學的一些實現，相信通過這個最簡單的入門算法能讓我們對機器學習有一點小小的感知和體會。

完整代碼和文件在: https://github.com/Lunaticf/D...

參考: http://burakkanber.com/blog/m...