1. 簡(jiǎn)介
源于數(shù)據(jù)挖掘的一個(gè)作業(yè)， 這里用Node.js來(lái)實(shí)現(xiàn)一下這個(gè)機(jī)器學(xué)習(xí)中最簡(jiǎn)單的算法之一k-nearest-neighbor算法(k最近鄰分類法)。
k-nearest-neighbor-classifier
還是先嚴(yán)謹(jǐn)?shù)慕榻B下。急切學(xué)習(xí)法（eager learner）是在接受待分類的新元組之前就構(gòu)造了分類模型，學(xué)習(xí)后的模型已經(jīng)就緒，急著對(duì)未知的元組進(jìn)行分類，所以稱為急切學(xué)習(xí)法，諸如決策樹歸納，貝葉斯分類等都是急切學(xué)習(xí)法的例子。惰性學(xué)習(xí)法（lazy learner）正好與其相反，直到給定一個(gè)待接受分類的新元組之后，才開始根據(jù)訓(xùn)練元組構(gòu)建分類模型，在此之前只是存儲(chǔ)著訓(xùn)練元組，所以稱為惰性學(xué)習(xí)法，惰性學(xué)習(xí)法在分類進(jìn)行時(shí)做更多的工作。
本文的knn算法就是一種惰性學(xué)習(xí)法，它被廣泛應(yīng)用于模式識(shí)別。knn基于類比學(xué)習(xí)，將未知的新元組與訓(xùn)練元組進(jìn)行對(duì)比，搜索模式空間，找出最接近未知元組的k個(gè)訓(xùn)練元組，這里的k即是knn中的k。這k個(gè)訓(xùn)練元祖就是待預(yù)測(cè)元組的k個(gè)最近鄰。
balabala了這么多，是不是某些同學(xué)想大喊一聲..speak Chinese! 還是來(lái)通俗的解釋下，然后再來(lái)看上面的理論應(yīng)該會(huì)明白很多。小時(shí)候媽媽會(huì)指著各種各樣的東西教我們，這是小鴨子，這個(gè)紅的是蘋果等等，那我們哼哧哼哧的看著應(yīng)答著，多次被教后再看到的時(shí)候我們自己就能認(rèn)出來(lái)這些事物了。主要是因?yàn)槲覀冊(cè)谀X海像給這個(gè)蘋果貼了很多標(biāo)簽一樣，不只是顏色這一個(gè)標(biāo)簽，可能還有蘋果的形狀大小等等。這些標(biāo)簽讓我們看到蘋果的時(shí)候不會(huì)誤認(rèn)為是橘子。其實(shí)這些標(biāo)簽就對(duì)應(yīng)于機(jī)器學(xué)習(xí)中的特征這一重要概念，而訓(xùn)練我們識(shí)別的過(guò)程就對(duì)應(yīng)于泛化這一概念。一臺(tái)iphone戴了一個(gè)殼或者屏幕上有一道劃痕，我們還是能認(rèn)得出來(lái)它，這對(duì)于我們?nèi)藖?lái)說(shuō)非常簡(jiǎn)單，但蠢計(jì)算機(jī)就不知道怎么做了，需要我們好好調(diào)教它，當(dāng)然也不能過(guò)度調(diào)教2333，過(guò)度調(diào)教它要把其他手機(jī)也認(rèn)成iphone那就不好了，其實(shí)這就叫過(guò)度泛化。
所以特征就是提取對(duì)象的信息，泛化就是學(xué)習(xí)到隱含在這些特征背后的規(guī)律，并對(duì)新的輸入給出合理的判斷。
我們可以看上圖，綠色的圓代表未知樣本，我們選取距離其最近的k個(gè)幾何圖形，這k個(gè)幾何圖形就是未知類型樣本的鄰居，如果k=3，我們可以看到有兩個(gè)紅色的三角形，有一個(gè)藍(lán)色的三正方形，由于紅色三角形所占比例高，所以我們可以判斷未知樣本類型為紅色三角形。擴(kuò)展到一般情況時(shí)，這里的距離就是我們根據(jù)樣本的特征所計(jì)算出來(lái)的數(shù)值，再找出距離未知類型樣本最近的K個(gè)樣本，即可預(yù)測(cè)樣本類型。那么求距離其實(shí)不同情況適合不同的方法，我們這里采用歐式距離。
綜上所述knn分類的關(guān)鍵點(diǎn)就是k的選取和距離的計(jì)算。
2. 實(shí)現(xiàn)
我的數(shù)據(jù)是一個(gè)xls文件，那么我去npm搜了一下選了一個(gè)叫node-xlrd的包直接拿來(lái)用。
// node.js用來(lái)讀取xls文件的包 var xls = require('node-xlrd'); 然后直接看文檔copy實(shí)例即可，把數(shù)據(jù)解析后插入到自己的數(shù)據(jù)結(jié)構(gòu)里。
var data = http://www.netofthings.cn/JieJueFangAn/2016-11/[];'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í)行測(cè)試 run();});然后定義一個(gè)構(gòu)造函數(shù)Sample表示一個(gè)樣本，這里是把剛生成的數(shù)據(jù)結(jié)構(gòu)里的對(duì)象傳入，生成一個(gè)新的樣本。
// Sample表示一個(gè)樣本 var Sample = function (object) { // 把傳過(guò)來(lái)的對(duì)象上的屬性克隆到新創(chuàng)建的樣本上 for (var key in object) { // 檢驗(yàn)屬性是否屬于對(duì)象自身 if (object.hasOwnProperty(key)) { this[key] = object[key]; } } }再定義一個(gè)樣本集的構(gòu)造函數(shù)
// SampleSet管理所有樣本 參數(shù)k表示KNN中的kvar SampleSet = function(k) { this.samples = []; this.k = k;};// 將樣本加入樣本數(shù)組SampleSet.prototype.add = function(sample) { this.samples.push(sample);}