上圖使用 plot.ly 所畫。

上次我們用JavaScript實(shí)現(xiàn)了 線性規(guī)劃 ，這次我們來聊聊KNN算法。

KNN是 k-Nearest-Neighbours 的縮寫，它是一種監(jiān)督學(xué)習(xí)算法。KNN算法可以用來做分類，也可以用來解決回歸問題。

GitHub倉庫： machine-learning-with-js

KNN算法簡介

簡單地說， KNN算法由那離自己最近的K個點(diǎn)來投票決定待分類數(shù)據(jù)歸為哪一類 。

如果待分類的數(shù)據(jù)有這些鄰近數(shù)據(jù)， NY : 7 , NJ : 0 , IN : 4 ，即它有7個 NY 鄰居，0個 NJ 鄰居，4個 IN 鄰居，則這個數(shù)據(jù)應(yīng)該歸類為 NY 。

假設(shè)你在郵局工作，你的任務(wù)是為郵遞員分配信件，目標(biāo)是最小化到各個社區(qū)的投遞旅程。不妨假設(shè)一共有7個街區(qū)。這就是一個實(shí)際的分類問題。你需要將這些信件分類，決定它屬于哪個社區(qū)，比如 上東城 、 曼哈頓下城 等。

最壞的方案是隨意分配信件分配給郵遞員，這樣每個郵遞員會拿到各個社區(qū)的信件。

最佳的方案是根據(jù)信件地址進(jìn)行分類，這樣每個郵遞員只需要負(fù)責(zé)鄰近社區(qū)的信件。

也許你是這樣想的：”將鄰近3個街區(qū)的信件分配給同一個郵遞員”。這時，鄰近街區(qū)的個數(shù)就是 k 。你可以不斷增加 k ，直到獲得最佳的分配方案。這個 k 就是分類問題的最佳值。

KNN代碼實(shí)現(xiàn)

像 上次 一樣，我們將使用 mljs 的 KNN 模塊 ml-knn 來實(shí)現(xiàn)。

每一個機(jī)器學(xué)習(xí)算法都需要數(shù)據(jù)，這次我將使用 IRIS數(shù)據(jù)集 。其數(shù)據(jù)集包含了150個樣本，都屬于 鳶尾屬 下的三個亞屬，分別是 山鳶尾 、 變色鳶尾 和 維吉尼亞鳶尾 。四個特征被用作樣本的定量分析，它們分別是 花萼 和 花瓣 的長度和寬度。

1. 安裝模塊

$npm install ml-knn@2.0.0 csvtojson prompt

ml-knn : k-Nearest-Neighbours 模塊，不同版本的接口可能不同，這篇博客使用了2.0.0

csvtojson : 用于將CSV數(shù)據(jù)轉(zhuǎn)換為JSON

prompt : 在控制臺輸入輸出數(shù)據(jù)

2. 初始化并導(dǎo)入數(shù)據(jù)

IRIS數(shù)據(jù)集 由加州大學(xué)歐文分校提供。

curl https://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data > iris.csv

假設(shè)你已經(jīng)初始化了一個NPM項(xiàng)目，請?jiān)?index.js 中輸入以下內(nèi)容：

const KNN = require(’ml-knn’);const csv = require(’csvtojson’);const prompt = require(’prompt’);var knn;const csvFilePath = ’iris.csv’; // 數(shù)據(jù)集const names = [’sepalLength’, ’sepalWidth’, ’petalLength’, ’petalWidth’, ’type’];let seperationSize; // 分割訓(xùn)練和測試數(shù)據(jù)let data = [], X = [], y = [];let trainingSetX = [], trainingSetY = [], testSetX = [], testSetY = []; seperationSize 用于分割數(shù)據(jù)和測試數(shù)據(jù)

使用csvtojson模塊的fromFile方法加載數(shù)據(jù)：

csv( { noheader: true, headers: names }) .fromFile(csvFilePath) .on(’json’, (jsonObj) => { data.push(jsonObj); // 將數(shù)據(jù)集轉(zhuǎn)換為JS對象數(shù)組 }) .on(’done’, (error) => { seperationSize = 0.7 * data.length; data = shuffleArray(data); dressData(); });

我們將 seperationSize 設(shè)為樣本數(shù)目的0.7倍。注意，如果訓(xùn)練數(shù)據(jù)集太小的話，分類效果將變差。

由于數(shù)據(jù)集是根據(jù)種類排序的，所以需要使用 shuffleArray 函數(shù)對數(shù)據(jù)進(jìn)行混淆，這樣才能方便分割出訓(xùn)練數(shù)據(jù)。這個函數(shù)的定義請參考StackOverflow的提問 How to randomize (shuffle) a JavaScript array? :

function shuffleArray(array){ for (var i = array.length - 1; i > 0; i--) { var j = Math.floor(Math.random() * (i + 1)); var temp = array[i]; array[i] = array[j]; array[j] = temp; } return array;} 3. 轉(zhuǎn)換數(shù)據(jù)

數(shù)據(jù)集中每一條數(shù)據(jù)可以轉(zhuǎn)換為一個JS對象：

{sepalLength: ‘5.1’,sepalWidth: ‘3.5’,petalLength: ‘1.4’,petalWidth: ‘0.2’,type: ‘Iris-setosa’ }

在使用 KNN 算法訓(xùn)練數(shù)據(jù)之前，需要對數(shù)據(jù)進(jìn)行這些處理：

將屬性(sepalLength, sepalWidth,petalLength,petalWidth)由字符串轉(zhuǎn)換為浮點(diǎn)數(shù). ( parseFloat ) 將分類 (type)用數(shù)字表示

function dressData(){ let types = new Set(); data.forEach((row) => { types.add(row.type); }); let typesArray = [...types]; data.forEach((row) => { let rowArray, typeNumber; rowArray = Object.keys(row).map(key => parseFloat(row[key])).slice(0, 4); typeNumber = typesArray.indexOf(row.type); // Convert type(String) to type(Number) X.push(rowArray); y.push(typeNumber); }); trainingSetX = X.slice(0, seperationSize); trainingSetY = y.slice(0, seperationSize); testSetX = X.slice(seperationSize); testSetY = y.slice(seperationSize); train();} 4. 訓(xùn)練數(shù)據(jù)并測試

function train(){ knn = new KNN(trainingSetX, trainingSetY, { k: 7 }); test();}

train方法需要2個必須的參數(shù): 輸入數(shù)據(jù)，即 花萼 和 花瓣 的長度和寬度；實(shí)際分類，即 山鳶尾 、 變色鳶尾 和 維吉尼亞鳶尾 。另外，第三個參數(shù)是可選的，用于提供調(diào)整 KNN 算法的內(nèi)部參數(shù)。我將 k 參數(shù)設(shè)為7，其默認(rèn)值為5。

訓(xùn)練好模型之后，就可以使用測試數(shù)據(jù)來檢查準(zhǔn)確性了。我們主要對預(yù)測出錯的個數(shù)比較感興趣。

function test(){ const result = knn.predict(testSetX); const testSetLength = testSetX.length; const predictionError = error(result, testSetY); console.log(`Test Set Size = ${testSetLength} and number of Misclassifications = ${predictionError}`); predict();}

比較預(yù)測值與真實(shí)值，就可以得到出錯個數(shù)：

function error(predicted, expected){ let misclassifications = 0; for (var index = 0; index < predicted.length; index++) { if (predicted[index] !== expected[index]) { misclassifications++; } } return misclassifications;} 5. 進(jìn)行預(yù)測(可選)

任意輸入屬性值，就可以得到預(yù)測值

function predict(){ let temp = []; prompt.start(); prompt.get([’Sepal Length’, ’Sepal Width’, ’Petal Length’, ’Petal Width’], function(err, result) { if (!err) { for (var key in result) { temp.push(parseFloat(result[key])); } console.log(`With ${temp} -- type = ${knn.predict(temp)}`); } });} 6. 完整程序

完整的程序 index.js 是這樣的：

const KNN = require(’ml-knn’);const csv = require(’csvtojson’);const prompt = require(’prompt’);var knn;const csvFilePath = ’iris.csv’; // 數(shù)據(jù)集const names = [’sepalLength’, ’sepalWidth’, ’petalLength’, ’petalWidth’, ’type’];let seperationSize; // 分割訓(xùn)練和測試數(shù)據(jù)let data = [], X = [], y = [];let trainingSetX = [], trainingSetY = [], testSetX = [], testSetY = [];csv( { noheader: true, headers: names }) .fromFile(csvFilePath) .on(’json’, (jsonObj) => { data.push(jsonObj); // 將數(shù)據(jù)集轉(zhuǎn)換為JS對象數(shù)組 }) .on(’done’, (error) => { seperationSize = 0.7 * data.length; data = shuffleArray(data); dressData(); });function dressData(){ let types = new Set(); data.forEach((row) => { types.add(row.type); }); let typesArray = [...types]; data.forEach((row) => { let rowArray, typeNumber; rowArray = Object.keys(row).map(key => parseFloat(row[key])).slice(0, 4); typeNumber = typesArray.indexOf(row.type); // Convert type(String) to type(Number) X.push(rowArray); y.push(typeNumber); }); trainingSetX = X.slice(0, seperationSize); trainingSetY = y.slice(0, seperationSize); testSetX = X.slice(seperationSize); testSetY = y.slice(seperationSize); train();}// 使用KNN算法訓(xùn)練數(shù)據(jù)function train(){ knn = new KNN(trainingSetX, trainingSetY, { k: 7 }); test();}// 測試訓(xùn)練的模型function test(){ const result = knn.predict(testSetX); const testSetLength = testSetX.length; const predictionError = error(result, testSetY); console.log(`Test Set Size = ${testSetLength} and number of Misclassifications = ${predictionError}`); predict();}// 計(jì)算出錯個數(shù)function error(predicted, expected){ let misclassifications = 0; for (var index = 0; index < predicted.length; index++) { if (predicted[index] !== expected[index]) { misclassifications++; } } return misclassifications;}// 根據(jù)輸入預(yù)測結(jié)果function predict(){ let temp = []; prompt.start(); prompt.get([’Sepal Length’, ’Sepal Width’, ’Petal Length’, ’Petal Width’], function(err, result) { if (!err) { for (var key in result) { temp.push(parseFloat(result[key])); } console.log(`With ${temp} -- type = ${knn.predict(temp)}`); } });}// 混淆數(shù)據(jù)集的順序function shuffleArray(array){ for (var i = array.length - 1; i > 0; i--) { var j = Math.floor(Math.random() * (i + 1)); var temp = array[i]; array[i] = array[j]; array[j] = temp; } return array;}

在控制臺執(zhí)行 node index.js

$ node index.js

輸出如下：

Test Set Size = 45 and number of Misclassifications = 2prompt: Sepal Length: 1.7prompt: Sepal Width: 2.5prompt: Petal Length: 0.5prompt: Petal Width: 3.4With 1.7,2.5,0.5,3.4 -- type = 2 參考鏈接 K NEAREST NEIGHBOR 算法 安德森鳶尾花卉數(shù)據(jù)集

歡迎加入 我們Fundebug 的 全棧BUG監(jiān)控交流群: 622902485 。

來自：https://kiwenlau.com/2017/07/10/javascript-machine-learning-knn/