Las siglas kNN significa k-Nearest-Neighbours, que es un algoritmo de aprendizaje supervisado. Se puede utilizar para la clasificación, así como para problemas de regresión.
¿Cómo funciona el algoritmo kNN?
kNN decide la clase del nuevo punto de datos basándose en el número máximo de vecinos que tiene el punto de datos que pertenecen a la misma clase.
Si los vecinos de un nuevo punto de datos son los siguientes, NY: 7, NJ: 0, IN: 4, entonces la clase del nuevo punto de datos será NY.
Digamos que trabajas en una oficina de correos y tu trabajo es organizar y distribuir cartas entre los carteros para minimizar el número de viajes a los diferentes barrios. Y como sólo estamos imaginando cosas, podemos asumir que sólo hay siete vecindarios diferentes. Este es un tipo de problema de clasificación. Necesitas dividir las letras en clases, donde las clases aquí se refieren al Upper East Side, Downtown Manhattan, y así sucesivamente.
Si te gusta perder tiempo y recursos, puedes dar una carta de cada vecindario a cada cartero, y esperar que se conozcan en el mismo vecindario y descubran tu plan corrupto. Ese es el peor tipo de distribución que se puede lograr.
Por otro lado, puedes organizar las cartas en función de qué direcciones están más cerca unas de otras.
Podrías empezar con «Si está dentro de un rango de tres manzanas, dáselo al mismo cartero». Ese número de bloques más cercanos es de donde viene K. Puedes seguir aumentando el número de bloques hasta que llegues a una distribución eficiente. Ese es el valor más eficiente de k para tu problema de clasificación.
kNN en la práctica – Código
Como hicimos en el último tutorial, vamos a usar el módulo KNN de ml.js para entrenar a nuestro clasificador kNearestNeighbors. Cada problema de Aprendizaje de Máquina necesita datos, y vamos a usar el conjunto de datos IRIS en este tutorial.
El conjunto de datos del iris consiste en 3 tipos diferentes de longitud de pétalos y sépalos de iris (Setosa, Versicolor y Virginica), junto con un campo que indica su tipo respectivo.
Instalar las bibliotecas
$ yarn add ml-knn csvtojson prompt
O si prefieres npm:
npm install ml-knn csvtojson prompt
- ml-knn: k Vecinos más cercanos
- csvtojson: Datos de análisis
- en el momento oportuno: Para permitir que el usuario solicite predicciones
Inicializar la biblioteca y cargar los datos
El conjunto de datos Iris es proporcionado por la Universidad de California, Irvine y está disponible aquí. Sin embargo, debido a la forma en que está organizado, tendrás que copiar el contenido en el navegador (Seleccionar todo, Copiar) y pegarlo en un archivo llamado iris.csv. Puedes nombrarlo como quieras, excepto que la extensión debe ser .csv.
Ahora, inicializa la biblioteca y carga los datos.
const KNN = require('ml-knn');
const csv = require('csvtojson');
const prompt = require('prompt');
let knn;
const csvFilePath = 'iris.csv'; // Data
const names = ['sepalLength', 'sepalWidth', 'petalLength', 'petalWidth', 'type']; // para el header
let seperationSize; // Para separar los datos de entrenamiento y de prueba
let data = [],
X = [],
y = [];
let trainingSetX = [],
trainingSetY = [],
testSetX = [],
testSetY = [];
Los nombres de los encabezados se utilizan para la visualización y la comprensión. Se quitarán más adelante.
Además, seperationSize se utiliza para dividir los datos en conjuntos de datos de formación y de prueba.
Hemos importado el paquete csvto.json, y ahora vamos a usar su método fromFile para cargar los datos. (Ya que nuestros datos no tienen una fila de encabezado, estamos proporcionando nuestros propios nombres de encabezado.)
csv({noheader: true, headers: names})
.fromFile(csvFilePath)
.on('json', (jsonObj) => {
data.push(jsonObj); // Push each object to data Array
})
.on('done', (error) => {
seperationSize = 0.7 * data.length;
data = shuffleArray(data);
dressData();
});
Estamos empujando cada fila a la variable de dates, y cuando el proceso ha terminado, estamos ajustando el seperationSize a 0.7 veces el número de muestras en nuestro conjunto de datos. Ten en cuenta que, si el tamaño de las muestras de capacitación es demasiado pequeño, es posible que el clasificador no funcione tan bien como lo haría con un conjunto más grande.
Dado que nuestro conjunto de datos está ordenado con respecto a los tipos (console.log para confirmar), la función shuffleArray se utiliza para, barajar el conjunto de datos para permitir la división. (Si no barajas, puedes terminar con un modelo que funcione bien para las dos primeras clases, pero que falle con la tercera.)
Así es como se define.
/**
* https://stackoverflow.com/a/12646864
* Ordenar al azar los elementos de la matriz en el lugar.
* Usando el algoritmo de barajar de Durstenfeld.
*/
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;
}
Datos del Vestido (una vez más)
Nuestros datos están organizados de la siguiente manera:
{
sepalLength: ‘5.1’,
sepalWidth: ‘3.5’,
petalLength: ‘1.4’,
petalWidth: ‘0.2’,
type: ‘Iris-setosa’
}
Hay dos cosas que necesitamos hacer con nuestros datos antes de entregarlos al clasificador kNN:
- Gira los valores de la cadena a flotantes. (parseFloat)
- Convierte el tipo en clases numeradas.
function dressData() {
/**
* Hay tres tipos diferentes de flores de Iris que este conjunto
*de datos clasificados:
*
* 1. Iris Setosa (Iris-setosa)
* 2. Iris Versicolor (Iris-versicolor)
* 3. Iris Virginica (Iris-virginica)
*
* Vamos a cambiar estas clases de Strings a números.
* Tal que, un valor de tipo igual a
* 0 significaría setosa,
* 1 significaría versicolor, y
* 3 significaría virginica
*/
let types = new Set(); // Para reunir clases ÚNICAS
data.forEach((row) => {
types.add(row.type);
});
typesArray = [...types]; // Para grabar los diferentes tipos de clases.
data.forEach((row) => {
let rowArray, typeNumber;
rowArray = Object.keys(row).map(key => parseFloat(row[key])).slice(0, 4);
typeNumber = typesArray.indexOf(row.type); // Convertir tipo (String) a tipo (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();
}
Si no estás familiarizado con los Sets, son como sus contrapartes matemáticas, ya que no pueden tener elementos duplicados, y sus elementos no tienen un índice. (A diferencia de los Arrays.)
Y pueden ser fácilmente convertidos a Arrays usando el operador de spread o usando el constructor de Set.
Entrena a tu modelo y luego pruébalo
function train() {
knn = new KNN(trainingSetX, trainingSetY, {k: 7});
test();
}
El método de entrenamiento toma dos argumentos obligatorios, los datos de entrada, como la longitud del pétalo, la anchura del pétalo, y su clase real, como el Iris-setosa, y así sucesivamente. También toma un parámetro opcional de opciones, que es sólo un objeto JS que se puede pasar para ajustar los parámetros internos del algoritmo. Estamos pasando el valor de k como una opción. El valor por defecto de k es 5.
Ahora que nuestro modelo ha sido entrenado, veamos cómo funciona en el equipo de pruebas. Principalmente, estamos interesados en el número de errores de clasificación que se producen. (Es decir, el número de veces que predice que la entrada es algo, aunque en realidad sea otra cosa.)
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();
}
El error se calcula de la siguiente manera. Usamos el humilde bucle for para hacer un bucle sobre el conjunto de datos, y ver si la salida pronosticada no es igual a la salida real. Es una clasificación errónea.
function error(predicted, expected) {
let misclassifications = 0;
for (var index = 0; index < predicted.length; index++) {
if (predicted[index] !== expected[index]) {
misclassifications++;
}
}
return misclassifications;
}
(Opcional) Comenzar a predecir
Es hora de tener algunas indicaciones y predicciones.
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)}`);
}
});
}
Siéntete libre de omitir este paso, si no desea probar el modelo en una nueva entrada.
¡Todo terminado!
Si tú seguiste todos los pasos, así es como debería verse tu index.js:
const KNN = require('ml-knn');
const csv = require('csvtojson');
const prompt = require('prompt');
let knn;
const csvFilePath = 'iris.csv'; // Datos
const names = ['sepalLength', 'sepalWidth', 'petalLength', 'petalWidth', 'type']; // para el header
let seperationSize; // Para separar los datos de entrenamiento y de prueba
let data = [], X = [], y = [];
let trainingSetX = [], trainingSetY = [], testSetX = [], testSetY = [];
csv({noheader: true, headers: names})
.fromFile(csvFilePath)
.on('json', (jsonObj) => {
data.push(jsonObj); // Empujar cada objeto a la matriz de datos
})
.on('done', (error) => {
seperationSize = 0.7 * data.length;
data = shuffleArray(data);
dressData();
});
function dressData() {
let types = new Set(); // Para reunir clases ÚNICAS
data.forEach((row) => {
types.add(row.type);
});
typesArray = [...types]; // Para grabar los diferentes tipos de clases.
data.forEach((row) => {
let rowArray, typeNumber;
rowArray = Object.keys(row).map(key => parseFloat(row[key])).slice(0, 4);
typeNumber = typesArray.indexOf(row.type); // Para grabar los diferentes tipos de clases.
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();
}
function train() {
knn = new KNN(trainingSetX, trainingSetY, {k: 7});
test();
}
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();
}
function error(predicted, expected) {
let misclassifications = 0;
for (var index = 0; index < predicted.length; index++) { if (predicted[index] !== expected[index]) { misclassifications++; } } return misclassifications; } 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)}`); } }); } /** * https://stackoverflow.com/a/12646864 * Randomize array element order in-place. * Using Durstenfeld shuffle algorithm. */ 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;
}
Ejecuta el nodo index.js. Debería mostrarte esto en pantalla:
$ node index.js Test Set Size = 45 and number of Misclassifications = 2 prompt: Sepal Length: 1.7 prompt: Sepal Width: 2.5 prompt: Petal Length: 0.5 prompt: Petal Width: 3.4 With 1.7,2.5,0.5,3.4 -- type = 2
Bien hecho. Ese es tu algoritmo kNN en el trabajo.
Un aspecto enorme del algoritmo kNN es el valor de k, y se le llama hiperparámetro. Los hiperparámetros son un, «tipo de parámetros que no pueden ser aprendidos directamente del proceso de entrenamiento regular». Estos parámetros expresan propiedades de «nivel superior» del modelo, como su complejidad o la rapidez con la que debe aprenderse. Se llaman «hiperparámetros».
