摘要：簡介源于數(shù)據(jù)挖掘的一個(gè)作業(yè)，這里用來實(shí)現(xiàn)一下這個(gè)機(jī)器學(xué)習(xí)中最簡單的算法之一算法最近鄰分類法。其實(shí)這些標(biāo)簽就對應(yīng)于機(jī)器學(xué)習(xí)中的特征這一重要概念，而訓(xùn)練我們識別的過程就對應(yīng)于泛化這一概念。

源于數(shù)據(jù)挖掘的一個(gè)作業(yè)， 這里用Node.js來實(shí)現(xiàn)一下這個(gè)機(jī)器學(xué)習(xí)中最簡單的算法之一k-nearest-neighbor算法(k最近鄰分類法)。

還是先嚴(yán)謹(jǐn)?shù)慕榻B下。急切學(xué)習(xí)法（eager learner）是在接受待分類的新元組之前就構(gòu)造了分類模型，學(xué)習(xí)后的模型已經(jīng)就緒，急著對未知的元組進(jìn)行分類，所以稱為急切學(xué)習(xí)法，諸如決策樹歸納，貝葉斯分類等都是急切學(xué)習(xí)法的例子。惰性學(xué)習(xí)法（lazy learner）正好與其相反，直到給定一個(gè)待接受分類的新元組之后，才開始根據(jù)訓(xùn)練元組構(gòu)建分類模型，在此之前只是存儲著訓(xùn)練元組，所以稱為惰性學(xué)習(xí)法，惰性學(xué)習(xí)法在分類進(jìn)行時(shí)做更多的工作。

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

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

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

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

綜上所述knn分類的關(guān)鍵點(diǎn)就是k的選取和距離的計(jì)算。

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

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

然后直接看文檔copy實(shí)例即可，把數(shù)據(jù)解析后插入到自己的數(shù)據(jù)結(jié)構(gòu)里。

var data = [];
// 將文件中的數(shù)據(jù)映射到樣本的屬性
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);
        }
    }
    // 等文件讀取完畢后 執(zhí)行測試
    run();
});

然后定義一個(gè)構(gòu)造函數(shù)Sample表示一個(gè)樣本，這里是把剛生成的數(shù)據(jù)結(jié)構(gòu)里的對象傳入，生成一個(gè)新的樣本。

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

再定義一個(gè)樣本集的構(gòu)造函數(shù)

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

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

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

// 計(jì)算樣本間距離 采用歐式距離
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;
       
        // 計(jì)算歐式距離
        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);
    }
};

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

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

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

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

// 構(gòu)建總樣本數(shù)組，包含未知類型樣本
SampleSet.prototype.determineUnknown = function() {
    /*
     * 一旦發(fā)現(xiàn)某個(gè)未知類型樣本，就把所有已知的樣本 
     * 克隆出來作為該未知樣本的鄰居序列。
     * 之所以這樣做是因?yàn)槲覀冃枰?jì)算該未知樣本和所有已知樣本的距離。
     */
    for (var i in this.samples)
    {
        // 如果發(fā)現(xiàn)沒有類型的樣本
        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]) );
            }
            
            // 計(jì)算所有鄰居與預(yù)測樣本的距離
            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();

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

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

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

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

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

knn算法非常簡單，但卻能在很多關(guān)鍵的地方發(fā)揮作用并且效果非常好。缺點(diǎn)就是進(jìn)行分類時(shí)要掃描所有訓(xùn)練樣本得到距離，訓(xùn)練集大的話會很慢。
看似高大上的機(jī)器學(xué)習(xí)其實(shí)就是基于計(jì)算機(jī)科學(xué)，統(tǒng)計(jì)學(xué)，數(shù)學(xué)的一些實(shí)現(xiàn)，相信通過這個(gè)最簡單的入門算法能讓我們對機(jī)器學(xué)習(xí)有一點(diǎn)小小的感知和體會。

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

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