然后我們會(huì)在樣本的原型上定義很多方法，這樣每個(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ù)測(cè)樣本間距離排序Sample.prototype.sortByDistance = function() { this.neighbors.sort(function (a, b) { return a.distance - b.distance; });};// 判斷被預(yù)測(cè)樣本類別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來(lái)預(yù)測(cè)樣本類型和對(duì)比判斷是否分類成功。
最后是樣本集的原型上定義一個(gè)方法，該方法可以在整個(gè)樣本集里尋找未知類型的樣本，并生成他們的鄰居集，調(diào)用未知樣本原型上的方法來(lái)計(jì)算鄰居到它的距離，把所有鄰居按距離排序，最后猜測(cè)類型。
// 構(gòu)建總樣本數(shù)組，包含未知類型樣本SampleSet.prototype.determineUnknown = function() { /* * 一旦發(fā)現(xiàn)某個(gè)未知類型樣本，就把所有已知的樣本 * 克隆出來(lái)作為該未知樣本的鄰居序列。 * 之所以這樣做是因?yàn)槲覀冃枰?jì)算該未知樣本和所有已知樣本的距離。 */ for (var i in this.samples) { // 如果發(fā)現(xiàn)沒(méi)有類型的樣本 if ( ! this.samples[i].type) { // 初始化未知樣本的鄰居 this.samples[i].neighbors = []; // 生成鄰居集 for (var j in this.samples) { // 如果碰到未知樣本 跳過(guò) if ( ! this.samples[j].type) continue; this.samples[i].neighbors.push( new Sample(this.samples[j]) ); } // 計(jì)算所有鄰居與預(yù)測(cè)樣本的距離 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(); // 猜測(cè)預(yù)測(cè)樣本類型 this.samples[i].guessType(this.k); } }};最后分別計(jì)算10倍交叉驗(yàn)證和留一法交叉驗(yàn)證的精度。
留一法就是每次只留下一個(gè)樣本做測(cè)試集，其它樣本做訓(xùn)練集。
K倍交叉驗(yàn)證將所有樣本分成K份，一般均分。取一份作為測(cè)試樣本，剩余K-1份作為訓(xùn)練樣本。這個(gè)過(guò)程重復(fù)K次，最后的平均測(cè)試結(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; }) }剩余測(cè)試代碼好寫，這里就不貼了。
測(cè)試結(jié)果為
用余弦距離等計(jì)算方式可能精度會(huì)更高。
3. 總結(jié)
knn算法非常簡(jiǎn)單，但卻能在很多關(guān)鍵的地方發(fā)揮作用并且效果非常好。缺點(diǎn)就是進(jìn)行分類時(shí)要掃描所有訓(xùn)練樣本得到距離，訓(xùn)練集大的話會(huì)很慢。
可以用這個(gè)最簡(jiǎn)單的分類算法來(lái)入高大上的ML的門，會(huì)有點(diǎn)小小的成就感。
完整代碼和文件在: https://github.com/Lunaticf/D…
參考: http://burakkanber.com/blog/m…