Привет, друзья!
В этой серии статей мы разбираем структуры данных и алгоритмы, представленные в этом замечательном репозитории. Это одиннадцатая часть серии.
Сегодня мы рассмотрим несколько простых, но интересных алгоритмов машинного обучения, а также один весьма любопытный статистический алгоритм.
Код, представленный в этой и других статьях серии, можно найти в этом репозитории.
Интересно? Тогда прошу под кат.
- Первая часть
- Вторая часть
- Третья часть
- Четвертая часть
- Пятая часть
- Шестая часть
- Седьмая часть
- Восьмая часть
- Девятая часть
- Десятая часть
❯ Машинное обучение
❯ NanoNeuron
NanoNeuron (далее — нейрончик) — это очень упрощенная версия концепции нейронов из нейронных сетей. Нейрончик умеет конвертировать значения температуры из градусов Цельсия в градусы Фаренгейта.
Код примера содержит 7 простых функций (затрагивающих предсказание модели, вычисление стоимости, прямое/обратное распространение и обучение), позволяющих понять, как машины на самом деле "обучаются". В коде нет сторонних библиотек, внешних зависимостей или наборов данных, только чистые и простые функции.
Эти функции не являются руководством по машинному обучению. Многие концепции машинного обучения отсутствуют и упрощены! Упрощение преследует цель дать читателю самое базовое понимание того, как учатся машины, а также того, что машинное обучение — это не магия, а математика.
Чему NanoNeuron будет учиться?
Вероятно, вы слышали о нейронах в контексте нейронных сетей. Нейрончик — это как раз такой нейрон, только проще. Мы реализуем его с нуля. Для простоты мы даже не будем создавать сеть из нейрончиков. Он будет работать сам по себе, делая некоторые "магические" предсказания для нас. Мы научим его конвертировать (предсказывать) температуру в градусах Фаренгейта на основе температуры в градусах Цельсия.
Кстати, формула для такого преобразования следующая:
f = c * 1.8 + 32Но пока наш нейрончик о ней не знает.
Модель NanoNeuron
Определим функцию моделирования нейрончика. Она реализует базовую линейную зависимость между x и y, которая выглядит как y = w * x + b. Проще говоря, наш нейрончик — это "ребенок" в "школе", который учится рисовать прямую линию в системе координат XY.
Переменные w и b — это параметры модели. Нейрончику известны только эти параметры линейной функции. Он "выучит" значения этих параметров в процессе обучения.
Единственная вещь, которую умеет делать нейрончик, — это имитация линейной зависимости. В методе predict() он принимает некоторый x и предсказывает y. Никакой магии:
function NanoNeuron(w, b) {
this.w = w;
this.b = b;
this.predict = (x) => {
return x * this.w + this.b;
}
}Линейная регрессия — это ты?🧐
Преобразование градусов
function celsiusToFahrenheit(c) {
const w = 1.8;
const b = 32;
const f = c * w + b;
return f;
};Мы хотим научить нейрончика имитировать эту функцию, т.е. научить, что w = 1.8, а b = 32 без предоставления этих значений.
Графически эту функцию можно представить следующим образом:
Генерация наборов данных
Перед обучением модели нужно сгенерировать наборы тренировочных и тестовых данных на основе функции celsiusToFahrenheit(). Наборы состоят из пар входных значений и правильно размеченных результатов.
В реальной жизни данные, как правило, собираются, а не генерируются. Например, у нас может быть набор изображений с рукописными цифрами и набор соответствующих цифр.
Для обучения нейрончика используется тренировочный набор. Перед тем, как нейрончик вырастет и сможет принимать решения самостоятельно, мы должны объяснить ему, что такое хорошо и что такое плохо с помощью тренировочных примеров.
Тестовый набор используется для проверки того, насколько хорошо нейрончик обрабатывает данные, которых он не видел в процессе обучения. Это та точка, когда мы видим, что наш "ребенок" вырос и может принимать самостоятельные решения:
function generateDataSets() {
// xTrain -> [0, 1, 2, ...],
// yTrain -> [32, 33.8, 35.6, ...]
const xTrain = [];
const yTrain = [];
for (let x = 0; x < 100; x += 1) {
const y = celsiusToFahrenheit(x);
xTrain.push(x);
yTrain.push(y);
}
// xTest -> [0.5, 1.5, 2.5, ...]
// yTest -> [32.9, 34.7, 36.5, ...]
const xTest = [];
const yTest = [];
// Начиная с 0.5 и используя такой же шаг 1,
// который мы использовали для тренировочного набора,
// мы обеспечиваем уникальность данных
for (let x = 0.5; x < 100; x += 1) {
const y = celsiusToFahrenheit(x);
xTest.push(x);
yTest.push(y);
}
return [xTrain, yTrain, xTest, yTest];
}Стоимость (ошибка) предсказания
Нам нужен какой-то критерий верности предсказания. Вычисление стоимости (ошибки) между правильным значением y и prediction (предсказанием), сделанным нейрончиком, производится по следующей формуле:
predictionCost = (y - prediction) ** 2 * 0.5Это просто разница между двумя значениями. Чем ближе значения друг к другу, тем меньше разница. Мы используем степень 2 для избавления от отрицательных чисел, поэтому (1 - 2) ** 2 = (2 - 1) ** 2. Деление на 2 выполняется для упрощения дальнейшей формулы обратного распространения (см. ниже):
function predictionCost(y, prediction) {
return (y - prediction) ** 2 / 2;
}Прямое распространение
Прямое распространение (forward propagation) означает выполнение предсказаний для всех тренировочных примеров из наборов xTrain и yTrain и вычисление средней стоимости этих предсказаний.
Мы позволяет нейрончику играть в "угадайку". Он может сильно ошибаться. Средняя стоимость покажет нам, насколько некорректной является наша модель. Эта стоимость очень важна, поскольку влияет на параметры w и b, которыми оперирует нейрончик. Повторное выполнение прямого распространения показывает, стал ли нейрончик умнее после соответствующих изменений.
Средняя стоимость вычисляется по такой формуле:
Где m — это количество тренировочных примеров (100 в нашем случае).
function forwardPropagation(model, xTrain, yTrain) {
const m = xTrain.length;
const predictions = [];
let cost = 0;
for (let i = 0; i < m; i += 1) {
const prediction = nanoNeuron.predict(xTrain[i]);
cost += predictionCost(yTrain[i], prediction);
predictions.push(prediction);
}
// Нас интересует средняя стоимость
cost /= m;
return [predictions, cost];
}Обратное распространение
После того, как мы узнали, насколько верными являются предсказания модели (на основе средней стоимости), как нам сделать их более точными?
Ответ — обратное распространение (backward propagation). Обратное распространение — это процесс оценки стоимости предсказания и модификации параметров w и b таким образом, чтобы будущие предсказания были более точными.
В этом месте машинное обучение выглядит как магия. Ключевой концепцией здесь является производная (derivative), которая показывает, какой шаг необходимо предпринять, чтобы подобраться к минимальной функции стоимости (minimum cost function).
Помните, что нахождение минимальной функции стоимости — это конечная цель обучения. Если мы нашли значения w и b, которые делают среднюю стоимость маленькой, значит, модель будет делать хорошие и точные предсказания.
Производные — это большая и отдельная тема, выходящая за рамки нашей беседы. MathIsFun — отличный ресурс для начала погружения в эту тему.
Производная, по сути, является касательной к кривой функции, которая указывает в направлении минимума функции:
Из приведенного графика следует, что если мы находимся в точке (x=2, y=4), то кривая "говорит" нам двигаться влево и вниз для достижения минимума функции.
Производные функции averageCost() для параметров w и b выглядят так:
Где m — количество тренировочных примеров (100 в нашем случае).
function backwardPropagation(predictions, xTrain, yTrain) {
const m = xTrain.length;
// В начале мы не знаем, как менять параметры 'w' и 'b'.
// Поэтому устанавливаем шаг изменения для каждого параметра в 0
let dW = 0;
let dB = 0;
for (let i = 0; i < m; i += 1) {
dW += (yTrain[i] - predictions[i]) * xTrain[i];
dB += yTrain[i] - predictions[i];
}
// Нас интересует средняя дельта каждого параметра
dW /= m;
dB /= m;
return [dW, dB];
}Обучение модели
Теперь мы знаем, как оценивать корректность модели для всех тренировочных примеров (прямое распространение). Мы также знаем, как применять небольшие модификации параметров w и b модели (обратное распространение). Но проблема состоит в том, что однократного запуска прямого и обратного распространений недостаточно для того, чтобы наша модель извлекла какие-то уроки из тренировочных данных. Это можно сравнить с одним днем обучения ребенка в школе. Ребенок ходит в школу не однажды, а день за днем и год за годом, чтобы чему-нибудь научиться.
Поэтому распространения следует повторять много раз. Это как раз то, что делает функция trainModel(). Это как учитель для нашего нейрончика:
- он проводит некоторое время (
epochs) с нашим глупым нейрончиком и пытается его чему-то научить - он использует специальные "книги" (наборы данных
xTrainиyTrain) для обучения - он заставляет нейрончика учиться усерднее (быстрее) с помощью параметра оценки обучения
alpha
Несколько слов об alpha. Это просто произведение dW и dB, вычисленных в процессе обратного распространения. Производная указывает нам направление, в котором мы должны двигаться для достижения минимума функции стоимости (положительные/отрицательные знаки dW и dB), а также скорость, с которой мы должны двигаться в этом направлении (абсолютные значения dW и dB). Нам нужно умножить эти шаги на alpha, чтобы ускорить или замедлить наше движение к минимуму. При использовании больших значений для alpha можно просто перепрыгнуть минимум и никогда его не найти.
Если использовать аналогию с учителем, то можно сказать, что чем сильнее учитель будет давить на ребенка, тем быстрее он будет учиться, но если учитель будет давить слишком сильно, то у ребенка случится нервный срыв и больше учиться он не сможет 🤯
Параметры w и b будут обновляться следующим образом:
w = w + alpha * dW
b = b + alpha * dBФункция обучения:
function trainModel({model, epochs, alpha, xTrain, yTrain}) {
// История обучения
const costHistory = [];
// Перебираем эпохи
for (let epoch = 0; epoch < epochs; epoch += 1) {
// Прямое распространение
const [predictions, cost] = forwardPropagation(model, xTrain, yTrain);
costHistory.push(cost);
// Обратное распространение
const [dW, dB] = backwardPropagation(predictions, xTrain, yTrain);
// Модифицируем параметры модели для повышения точности предсказаний
nanoNeuron.w += alpha * dW;
nanoNeuron.b += alpha * dB;
}
return costHistory;
}Вместе веселее
Применим созданные функции.
Создаем экземпляр NanoNeuron. В данный момент нейрончику неизвестны значения w и b. Устанавливаем их произвольно:
const w = Math.random(); // например -> 0.9492
const b = Math.random(); // например -> 0.4570
const nanoNeuron = new NanoNeuron(w, b);Генерируем наборы данных:
const [xTrain, yTrain, xTest, yTest] = generateDataSets();Обучаем модель небольшими шагами (0.0005) на протяжении 7000 эпох. Эти значения были определены эмпирическим путем, не стесняйтесь их менять:
const epochs = 70000;
const alpha = 0.0005;
const trainingCostHistory = trainModel({ model: nanoNeuron, epochs, alpha, xTrain, yTrain });Проверяем функцию стоимости в процессе обучения. Мы ожидаем, что стоимость после обучения будет значительно ниже, чем до него. Это будет означать, что нейрончик стал умнее. Противоположное также возможно:
console.log('Стоимость до обучения:', trainingCostHistory[0]); // например, 4694.3335043
console.log('Стоимость после обучения:', trainingCostHistory[epochs - 1]); // например, 0.0000024Графически снижение стоимости выглядит так (ось x — количество эпох):
Взглянем на параметры модели. Мы ожидаем, что w и b нейрончика будут близки к истинным (w = 1.8 и b = 32):
console.log('Параметры нейрончика:', { w: nanoNeuron.w, b: nanoNeuron.b }); // например -> { w: 1.8, b: 31.99 }Оцениваем точность модели на тестовых данных, чтобы увидеть, как хорошо нейрончик справляется с обработкой неизвестных данных. Мы ожидаем, что стоимость тестовых предсказаний будет близка к стоимости тренировочных предсказаний:
[testPredictions, testCost] = forwardPropagation(nanoNeuron, xTest, yTest);
console.log('Стоимость тестовых предсказаний:', testCost); // например -> 0.0000023Теперь, поскольку наш "ребенок" хорошо показал себя при обучении в "школе" и научился правильно обрабатывать данные, которых он не видел, мы можем назвать его "умным" и задать ему парочку вопросов. В этом и заключалась цель обучения:
const tempInCelsius = 70;
const customPrediction = nanoNeuron.predict(tempInCelsius);
console.log(`Нейрончик "думает", что ${tempInCelsius}°C в градусах Фаренгейта:`, customPrediction); // -> 158.0002
console.log('Правильный ответ:', celsiusToFahrenheit(tempInCelsius)); // -> 158Очень близко! Наш нейрончик хорош, но не идеален, как все люди :)
// Модель NanoNeuron (нейрончика).
// Она реализует базовую линейную зависимость между 'x' и 'y': y = w * x + b.
// Проще говоря, наш нейрончик - это "ребенок", умеющий рисовать прямую линию в системе координат XY.
// w, b - параметры модели
class NanoNeuron {
constructor(w, b) {
// Нейрончику известны только эти два параметра линейной функции.
// Значения этих параметров будут определяться нейрончиком в процессе обучения
this.w = w
this.b = b
}
// Все, что умеет нейрончик, - имитировать линейную зависимость.
// Он принимает некоторый 'x' и предсказывает 'y'. Никакой магии
predict(x) {
return x * this.w + this.b
}
}
// Конвертирует градусы Цельсия в градусы Фаренгейта по формуле: f = 1.8 * c + 32.
// Мы хотим научить нейрончика имитировать эту функцию, т.е.
// научить, что W = 1.8, а B = 32 без предоставления этих значений.
// c - температура в градусах Цельсия
// f - вычисленная температура в градусах Фаренгейта
const W = 1.8
const B = 32
function celsiusToFahrenheit(c) {
const f = c * W + B
return f
}
// Генерирует обучающий и тестовый наборы данных с помощью функции celsiusToFahrenheit().
// Наборы состоят из пар входных значений и правильно размеченных результатов.
// В реальной жизни в большинстве случаев эти данные будут собраны, а не сгенерированы.
// Например, у нас может быть набор изображений рукописных цифр и
// набор соответствующих цифр
function generateDataSets() {
// Генерируем ТРЕНИРОВОЧНЫЕ данные.
// Эти данные будут использоваться для обучения модели.
// Перед тем, как нейрончик вырастет и сможет принимать решения самостоятельно,
// мы должны объяснить ему, что такое хорошо и что такое плохо с помощью
// тренировочных примеров.
// xTrain -> [0, 1, 2, ...],
// yTrain -> [32, 33.8, 35.6, ...]
const xTrain = []
const yTrain = []
for (let x = 0; x < 100; x += 1) {
const y = celsiusToFahrenheit(x)
xTrain.push(x)
yTrain.push(y)
}
// Генерируем ТЕСТОВЫЕ данные.
// Эти данные будут использоваться для оценки того, насколько хорошо модель работает с данными,
// которых она не видела в процессе обучения. Здесь мы можем увидеть,
// что наш "ребенок" вырос и может принимать решения самостоятельно.
// xTest -> [0.5, 1.5, 2.5, ...]
// yTest -> [32.9, 34.7, 36.5, ...]
const xTest = []
const yTest = []
// Начиная с 0.5 и используя такой же шаг 1,
// который мы использовали для тренировочного набора,
// мы обеспечиваем уникальность данных
for (let x = 0.5; x < 100; x += 1) {
const y = celsiusToFahrenheit(x)
xTest.push(x)
yTest.push(y)
}
return [xTrain, yTrain, xTest, yTest]
}
// Вычисляем стоимость (ошибку) между правильным значением 'y' и
// 'prediction' (предсказанием), сделанным нейрончиком
function predictionCost(y, prediction) {
// Это просто разница между двумя значениями.
// Чем ближе значения друг к другу, тем меньше разница.
// Мы используем здесь степень 2 только для того, чтобы избавиться от отрицательных чисел,
// поэтому (1 - 2) ^ 2 = (2 - 1) ^ 2.
// Результат делится на 2 просто для упрощения дальнейшей формулы обратного распространения (см. ниже)
return (y - prediction) ** 2 / 2 // например -> 235.6
}
// Прямое распространение.
// Эта функция берет все примеры из тренировочных наборов xTrain и yTrain
// и вычисляет предсказания модели для каждого примера из xTrain.
// По пути она также вычисляет среднюю стоимость предсказаний
function forwardPropagation(model, xTrain, yTrain) {
const m = xTrain.length
const predictions = []
let cost = 0
for (let i = 0; i < m; i += 1) {
const prediction = model.predict(xTrain[i])
cost += predictionCost(yTrain[i], prediction)
predictions.push(prediction)
}
// Нас интересует средняя стоимость
cost /= m
return [predictions, cost]
}
// Обратное распространение.
// В этом месте машинное обучение выглядит как магия.
// Ключевой концепцией здесь является производная (derivative), которая показывает, какой шаг нужно предпринять, чтобы
// приблизиться к минимуму функции стоимости. Помните, нахождение минимальной функции стоимости -
// конечная цель процесса обучения. Функция стоимости выглядит следующим образом:
// (y - prediction) ^ 2 * 1/2, где prediction = x * w + b.
function backwardPropagation(predictions, xTrain, yTrain) {
const m = xTrain.length
// В начале мы не знаем, как менять параметры 'w' и 'b'.
// Поэтому устанавливаем шаг изменения для каждого параметра в значение 0
let dW = 0
let dB = 0
for (let i = 0; i < m; i += 1) {
// Это производная функции стоимости параметра 'w'.
// Она показывает, в каком направлении (положительный/отрицательный знак 'dW') и
// на сколько (абсолютное значение 'dW') параметр 'w' должен быть изменен
dW += (yTrain[i] - predictions[i]) * xTrain[i]
// Это производная функции стоимости параметра 'b'.
// Она показывает, в каком направлении (знак 'dB') и
// на сколько (абсолютное значение 'dB') параметр 'b' должен быть изменен
dB += yTrain[i] - predictions[i]
}
// Нас интересуют средняя дельта каждого параметра
dW /= m
dB /= m
return [dW, dB]
}
// Обучает модель.
// Это "учитель" нашего нейрончика:
// - он проводит некоторое время (epochs) с нашим глупым нейрончиком и пытается его чему-то научить,
// - он использует специальные "книги" (наборы данных xTrain и yTrain) для обучения,
// - он заставляет ребенка учиться усерднее (быстрее) с помощью параметра оценки обучения 'alpha'
// (чем сильнее стимул, тем быстрее модель учится, но если учитель будет давить слишком сильно
// у "ребенка" может случиться нервный срыв, и больше он не сможет учиться)
function trainModel(model, epochs, alpha, xTrain, yTrain) {
// История обучения модели.
// Она может содержать хорошие или плохие "оценки" (стоимость),
// полученные в процессе обучения
const costHistory = []
// Перебираем эпохи
for (let i = 0; i < epochs; i += 1) {
// Прямое распространение для всех тренировочных примеров.
// Сохраняем стоимость текущей итерации.
// Это поможет анализировать обучение модели
const [predictions, cost] = forwardPropagation(model, xTrain, yTrain)
costHistory.push(cost)
// Обратное распространение. Учимся на ошибках.
// Эта функция возвращает небольшие модификации, которые нужно применить к параметрам 'w' и 'b',
// чтобы сделать предсказания более точными
const [dW, dB] = backwardPropagation(predictions, xTrain, yTrain)
// Модифицируем параметры нейрончика для повышения точности его предсказаний
nanoNeuron.w += alpha * dW
nanoNeuron.b += alpha * dB
}
// Возвращаем историю обучения для анализа и визуализации
return costHistory
}
// ===
// Создаем экземпляр модели.
// В данный момент нейрончику неизвестны значения параметров 'w' и 'b'.
// Устанавливаем их произвольно
const w = Math.random() // например -> 0.9492
const b = Math.random() // например -> 0.4570
const nanoNeuron = new NanoNeuron(w, b)
// Генерируем тренировочные и тестовые наборы данных
const [xTrain, yTrain, xTest, yTest] = generateDataSets()
// Обучаем модель небольшими шагами (0.0005) в течение 70000 эпох.
// Можете попробовать другие значения, они определены эмпирическим путем
const epochs = 70000
const alpha = 0.0005
const trainingCostHistory = trainModel(
nanoNeuron,
epochs,
alpha,
xTrain,
yTrain,
)
// Проверим, как менялась стоимость в процессе обучения.
// Мы ожидаем, что стоимость после обучения будет значительно ниже, чем до него.
// Это будет означать, что наш нейрончик стал умнее. Но возможно и обратное
console.log('Стоимость до обучения:', trainingCostHistory[0]) // например -> 4694.3335043
console.log('Стоимость после обучения:', trainingCostHistory[epochs - 1]) // например -> 0.0000024
// Взглянем на параметры нейрончика, чтобы увидеть, чему он научился.
// Мы ожидаем, что значения параметров 'w' и 'b' модели будут близки к истинным значениям,
// которые используются в функции celsiusToFahrenheit() (w = 1.8 и b = 32)
console.log(
'Параметры нейрончика:',
JSON.stringify({ w: nanoNeuron.w, b: nanoNeuron.b }, null, 2),
) // например -> { w: 1.8, b: 31.99 }
// Оцениваем точность модели на тестовых данных, чтобы увидеть, насколько хорошо она обрабатывает неизвестные данные.
// Мы ожидаем, что стоимость тестовых предсказаний будет близкой к стоимости тренировочных предсказаний.
// Это будет означать, что нейрончик хорошо справляется как с тренировочными, так и с тестовыми данными
const [testPredictions, testCost] = forwardPropagation(nanoNeuron, xTest, yTest)
console.log('Стоимость тестовых предсказаний:', testCost) // например -> 0.0000023
// После того, как "ребенок" хорошо показал себя в "школе" в процессе обучения и хорошо справился с тестовыми данными,
// мы можем назвать его "умным" и задать ему парочку вопросов
const tempInCelsius = 70
const customPrediction = nanoNeuron.predict(tempInCelsius)
console.log(
`Нейрончик "думает", что ${tempInCelsius}°C в градусах Фаренгейта:`,
customPrediction,
) // -> 158.0002
console.log('Правильный ответ:', celsiusToFahrenheit(tempInCelsius)) // -> 158
// Очень близко! Нейрончик хорош, но не идеален, как все люди :)Пропущенные концепции машинного обучения
Следующие концепции машинного обучения были пропущены или упрощены.
Разделение данных
Обычно, у нас имеется один большой набор данных. Часто он разделяется в пропорции 70/30 для тренировочного/тестового набора (это зависит от количества примеров). Данные должны произвольно перемешиваться перед разделением. Если примеров много (например, миллионы), то пропорция может быть ближе к 90/10 или даже к 95/5.
Сеть
Как правило, нейроны не используются по отдельности. Настоящая сила заключается в нейронных сетях. Сеть можно научить гораздо более сложным вещам. Наш нейрончик больше похож на линейную регрессию, чем на нейронную сеть.
Нормализация
Перед обучением входные данные лучше нормализовать.
Векторная реализация
Для сетей векторные (матричные) вычисления работают намного быстрее, чем циклы for.
Минимум функции стоимости
Используемая нами функция стоимости очень упрощена. Она должна содержать логарифмические компоненты. Обратите внимание, что изменение функции стоимости повлечет изменение ее производных, поэтому в обратном распространении также надо будет использовать другие формулы.
Функция активации
Обычно, результат нейрона пропускается через функцию активации, такую как сигмоида, ReLU или аналоги.
❯ Метод k ближайших соседей
Описание
Метод k ближайших соседей (k-nearest neighbors algorithm, k-NN) — метрический алгоритм для автоматической классификации объектов или регрессии. Он относится к методам машинного обучения с учителем (supervised).
В случае использования метода для классификации объект присваивается тому классу, который является наиболее распространённым среди k соседей данного элемента, классы которых уже известны. В случае использования метода для регрессии, объекту присваивается среднее значение по k ближайшим к нему объектам, значения которых уже известны. Мы будем говорить в основном о классификации.
Алгоритм может быть применим к выборкам с большим количеством атрибутов (многомерным). Для этого перед применением нужно определить функцию расстояния; классический вариант такой функции — евклидова метрика.
Использование теоремы Пифагора для вычисления евклидова расстояния на плоскости
Принцип работы
- проверяется валидность данных и меток
- вычисляется евклидово расстояние между тестовым (целевым) и всеми обучающими образцами
- расстояния вместе с классами сортируются в возрастающем порядке
- выбирается
kближайших образцов (соседей), где числоkзадается заранее (как правило, выбирается нечетное число — 3, 5 и т.д.) - итоговым прогнозом среди выбранных
kближайших соседей будет мода в случае классификации и среднее арифметическое в случае регрессии - возвращается наиболее похожий класс (для классификации) или среднее значение (для регрессии)
Визуализация k-NN для лучшего понимания:
Пример классификации методом k-NN: тестовый образец (зеленый круг) должен быть классифицирован как синий квадрат (класс 1) или как красный треугольник (класс 2); если k=3, то он классифицируется как 2-й класс, потому что внутри меньшего круга 2 треугольника и только 1 квадрат; если k=5, то он будет классифицирован как 1-й класс (3 квадрата против 2 треугольников внутри большего круга)
Еще одна визуализация:
Здесь k = 7, поэтому тестовый образец классифицируется как зеленый треугольник
И еще одна:
Звездочкой обозначен целевой образец
k=3
k=10
k=20
Как видим, во всех трех случаях целевой образец классифицируется как синий круг.
Реализация
// algorithms/machine-learning/k-nn.js
// Функция для вычисления евклидова расстояния
import euclideanDistance from '../math/euclidean-distance'
/** Функция принимает:
* data - данные
* labels - метки
* target - тестовый/целевой образец
* k - количество ближайших соседей
*/
export default function kNN(data, labels, target, k = 3) {
if (!data || !labels || !target) {
throw new Error('Отсутствует обязательный параметр')
}
// Вычисляем расстояние от `target` до каждой точки `data`.
// Сохраняем расстояние и метку точки в списке
const distances = []
for (let i = 0; i < data.length; i++) {
distances.push({
distance: euclideanDistance([data[i]], [target]),
label: labels[i],
})
}
// Сортируем расстояния по возрастанию (от ближайшего к дальнему).
// Берем `k` значений
const kn = distances
.sort((a, b) => {
if (a.distance === b.distance) {
return 0
}
return a.distance < b.distance ? -1 : 1
})
.slice(0, k)
// Считаем количество экземпляров каждого класса
const _labels = {}
let topClass = 0
let topClassCount = 0
for (let i = 0; i < kn.length; i++) {
if (kn[i].label in _labels) {
_labels[kn[i].label] += 1
} else {
_labels[kn[i].label] = 1
}
if (_labels[kn[i].label] > topClassCount) {
topClassCount = _labels[kn[i].label]
topClass = kn[i].label
}
}
// Возвращает класс с наибольшим количеством экземпляров
return topClass
}// algorithms/machine-learning/__tests__/k-nn.test.js
import kNN from '../k-nn'
describe('kNN', () => {
it('при неправильных данных должно выбрасываться исключение', () => {
expect(() => {
kNN()
}).toThrowError('Отсутствует обязательный параметр')
})
it('при неправильных метках должно выбрасываться исключение', () => {
const noLabels = () => {
kNN([[1, 1]])
}
expect(noLabels).toThrowError('Отсутствует обязательный параметр')
})
it('при отсутствии целевого образца должно выбрасываться исключение #1', () => {
const noClassification = () => {
kNN([[1, 1]], [1])
}
expect(noClassification).toThrowError('Отсутствует обязательный параметр')
})
it('при отсутствии целевого образца должно выбрасываться исключение #2', () => {
const inconsistent = () => {
kNN([[1, 1]], [1], [1])
}
expect(inconsistent).toThrowError('Матрицы имеют разную форму')
})
it('должен выполнить классификацию целевых образцов', () => {
let dataSet
let labels
let toClassify
let expectedClass
dataSet = [
[1, 1],
[2, 2],
]
labels = [1, 2]
toClassify = [1, 1]
expectedClass = 1
expect(kNN(dataSet, labels, toClassify)).toBe(expectedClass)
dataSet = [
[1, 1],
[6, 2],
[3, 3],
[4, 5],
[9, 2],
[2, 4],
[8, 7],
]
labels = [1, 2, 1, 2, 1, 2, 1]
toClassify = [1.25, 1.25]
expectedClass = 1
expect(kNN(dataSet, labels, toClassify)).toBe(expectedClass)
dataSet = [
[1, 1],
[6, 2],
[3, 3],
[4, 5],
[9, 2],
[2, 4],
[8, 7],
]
labels = [1, 2, 1, 2, 1, 2, 1]
toClassify = [1.25, 1.25]
expectedClass = 2
expect(kNN(dataSet, labels, toClassify, 5)).toBe(expectedClass)
})
it('должен выполнить классификацию целевого образца с соседями на одинаковых расстояниях', () => {
const dataSet = [
[0, 0],
[1, 1],
[0, 2],
]
const labels = [1, 3, 3]
const toClassify = [0, 1]
const expectedClass = 3
expect(kNN(dataSet, labels, toClassify)).toBe(expectedClass)
})
it('должен выполнить классификацию целевого образца с соседями в трехмерном пространстве', () => {
const dataSet = [
[0, 0, 0],
[0, 1, 1],
[0, 0, 2],
]
const labels = [1, 3, 3]
const toClassify = [0, 0, 1]
const expectedClass = 3
expect(kNN(dataSet, labels, toClassify)).toBe(expectedClass)
})
})Запускаем тесты:
npm run test ./algorithms/machine-learning/__tests__/k-nn
❯ Метод k-средних
Описание
Метод k-средних (k-means) — наиболее популярный метод кластеризации. Он относится к методам машинного обучения без учителя (unsupervised).
Действие алгоритма таково, что он стремится минимизировать суммарное квадратичное отклонение точек кластеров от центров этих кластеров:
где k — число кластеров, Si — полученные кластеры, i = 1, 2, ..., k, а μi — центры масс (центроиды) всех векторов x из кластера Si.
Принцип работы
Алгоритм разбивает множество элементов векторного пространства на заранее известное число кластеров k.
Основная идея заключается в том, что на каждой итерации перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем векторы разбиваются на кластеры вновь в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике. Для вычисления схожести между центром масс и векторами данных часто используется евклидова метрика.
Использование теоремы Пифагора для вычисления евклидова расстояния на плоскости
Алгоритм завершается, когда на какой-то итерации не происходит изменения внутрикластерного расстояния. Это происходит за конечное число итераций, так как количество возможных разбиений конечного множества конечно, а на каждом шаге суммарное квадратичное отклонение V уменьшается, поэтому зацикливание невозможно.
Действие алгоритма в двумерном случае. Начальные точки выбраны случайно
Последовательность шагов:
- проверяется валидность/согласованность данных
- инициализируется
kцентроидов с начальными/произвольнымиkточками - вычисляется расстояние каждой точки до каждого центроида
- каждой точке присваивается значение метки ближайшего кластера
- вычисляется центроид каждого кластера на основе содержащихся в нем точек
- цикл повторяется до тех пор, пока положение центроидов не перестанет меняться
Визуализация для лучшего понимания:
Проблемы k-средних
- не гарантируется достижение глобального минимума суммарного квадратичного отклонения
V, а только одного из локальных минимумов
Типичный пример сходимости метода k-средних к локальному минимуму. В этом примере результат кластеризации указанным методом противоречит очевидной кластерной структуре множества данных. Маленькими кружками обозначены точки данных, четырехлучевые звезды — центроиды. Принадлежащие им точки данных окрашены в тот же цвет
- результат зависит от выбора исходных центров кластеров, их оптимальный выбор неизвестен
Результат кластеризации методом k-средних для ирисов Фишера и реальные виды ирисов, визуализированные с помощью ELKI. Центры кластеров отмечены с помощью крупных, полупрозрачных маркеров
- число кластеров надо знать заранее
Применение
В алгоритмах глубокого обучения метод k-средних иногда применяют не по прямому назначению (классификация разбивкой на кластеры), а для создания так называемых фильтров (ядер свертки, словарей). Например, для распознавания изображений в алгоритм k-средних подают небольшие случайные кусочки изображений обучающей выборки, допустим, размером 16х16 в виде линейного вектора, каждый элемент которого кодирует яркость своей точки. Количество кластеров k задается большим, например 256. Обученный метод k-средних при определенных условиях вырабатывает при этом центры кластеров (центроиды), которые представляют собой удобные базисы, на которые можно разложить любое входное изображение. Такие "обученные" центроиды в дальнейшем используют в качестве фильтров, например для сверточной нейронной сети в качестве ядер свертки или других аналогичных систем машинного зрения.
Реализация
// algorithms/machine-learning/k-means.js
// Утилиты для матричных вычислений
import * as matrix from '../math/matrix'
// Функция для вычисления евклидова расстояния
import euclideanDistance from '../math/euclidean-distance'
/** Функция принимает:
* data - данные
* k - количество кластеров
*/
export default function kMeans(data, k = 1) {
if (!data) {
throw new Error('Отсутствуют данные для классификации')
}
// Количество измерений
const dimension = data[0].length
// Центроиды
const centroids = data.slice(0, k)
// Матрица расстояний от каждой точки до каждого центроида
const distances = matrix.zeros([data.length, k])
// Классы векторных точек данных.
// - 1 означает, что класс еще не назначен
const classes = new Array(data.length).fill(-1)
// Индикатор итерации
let iterate = true
while (iterate) {
iterate = false
// Вычисляем и сохраняем расстояние каждой точки от каждого центроида
for (let i = 0; i < data.length; i++) {
for (let j = 0; j < k; j++) {
distances[i][j] = euclideanDistance([centroids[j]], [data[i]])
}
// Присваиваем метку ближайшего кластера каждой точке
const closestClusterIndex = distances[i].indexOf(
Math.min(...distances[i]),
)
// Проверяем, был ли класс точки изменен
// и нужно ли повторить итерацию
if (classes[i] !== closestClusterIndex) {
iterate = true
}
classes[i] = closestClusterIndex
}
// Пересчитываем положение центроида кластера
// на основе содержащихся в нем точек
for (let i = 0; i < k; i++) {
// Сбрасываем координаты центроида, поскольку нам нужно их пересчитать
centroids[i] = new Array(dimension).fill(0)
let clusterSize = 0
for (let j = 0; j < data.length; j++) {
if (classes[j] === i) {
// Регистрируем еще одну точку текущего кластера
clusterSize += 1
for (let l = 0; l < dimension; l++) {
centroids[i][l] += data[j][l]
}
}
}
// Вычисляем среднее значение каждой координаты центроида
for (let j = 0; j < dimension; j++) {
centroids[i][j] = parseFloat(
Number(centroids[i][j] / clusterSize).toFixed(2),
)
}
}
}
return classes
}// algorithms/machine-learning/__tests__/k-means.test.js
import KMeans from '../k-means'
describe('kMeans', () => {
it('при невалидных данных должно выбрасываться исключение', () => {
expect(() => {
KMeans()
}).toThrowError('Отсутствуют данные для классификации')
})
it('при несогласованных данных должно выбрасываться исключение', () => {
expect(() => {
KMeans([[1, 2], [1]], 2)
}).toThrowError('Матрицы имеют разную форму')
})
it('должен выполнить кластеризацию', () => {
const data = [
[1, 1],
[6, 2],
[3, 3],
[4, 5],
[9, 2],
[2, 4],
[8, 7],
]
const k = 2
const expectedClusters = [0, 1, 0, 1, 1, 0, 1]
expect(KMeans(data, k)).toEqual(expectedClusters)
expect(
KMeans(
[
[0, 0],
[0, 1],
[10, 10],
],
2,
),
).toEqual([0, 0, 1])
})
it('должен выполнить кластеризацию точек на одинаковых расстояниях', () => {
const dataSet = [
[0, 0],
[1, 1],
[2, 2],
]
const k = 3
const expectedCluster = [0, 1, 2]
expect(KMeans(dataSet, k)).toEqual(expectedCluster)
})
it('должен выполнить кластеризацию точек в трехмерном пространстве', () => {
const dataSet = [
[0, 0, 0],
[0, 1, 0],
[2, 0, 2],
]
const k = 2
const expectedCluster = [1, 1, 0]
expect(KMeans(dataSet, k)).toEqual(expectedCluster)
})
})Запускаем тесты:
npm run test ./algorithms/machine-learning/__tests__/k-means
❯ Статистика
❯ Взвешенная произвольная выборка
Описание
Допустим, у нас есть список элементов. Элемент может быть чем угодно. Например, у нас может быть список фруктов и овощей, которые мы любим кушать: [ '🍌', '🍎', '🥕' ].
Список весов представляет вес (вероятность выбора, важность) каждого элемента. Веса — это числа. Например, веса [3, 7, 1] означают следующее:
- мы выбираем яблоко чаще всего (
7из3+7+1=11раз) - банан мы выбираем менее часто (
3из11раз) - морковку мы не любим, поэтому выбираем ее редко (
1из11раз)
Если говорить в терминах вероятности, то веса должны быть представлены числами с плавающей запятой, сумма которых дает1(например,[0.1, 0.5, 0.2, 0.2]).
Взвешенная произвольная выборка (weighted random) — это функция, которая возвращает произвольный элемент списка с учетом его веса, поэтому элементы с большим весом выбирается чаще.
Пример интерфейса функции:
const items = [ '🍌', '🍎', '🥕' ];
const weights = [ 3, 7, 1 ];
function weightedRandom(items, weights) {
// Реализация...
}
const nextSnackToEat = weightedRandom(items, weights); // вероятнее всего будет '🍎'Применение
- в генетической алгоритме взвешенная произвольная выборка используется на стадии выборки, когда нам нужно выбрать наиболее приспособленных/сильных особей на основе оценки их приспособленности для спаривания и создания следующего более сильного поколения. См. Самопаркующийся авто за 500 строк кода
- в рекуррентных нейронных сетях (RNN) при принятии решения о выборе следующей буквы (для формирования предложения) на основе вероятности следующей буквы. См. Jupyter Notebook Recipe Generation using Recurrent Neural Network (RNN)
- в балансировщике нагрузки Nginx для более частой отправки запросов на сервер с более высоким весом
- во многих других областях
Алгоритм
Самый простой подход состоит в следующем:
- Дублируем каждый элемент в соответствии с его весом.
- Выбираем произвольный элемент.
Например, для наших фруктов и овощей можно сгенерировать следующий список:
const items = [ '🍌', '🍎', '🥕' ];
const weights = [ 3, 7, 1 ];
// Дублируем элементы на основе их весов
const weightedItems = [
'🍌', '🍌', '🍌',
'🍎', '🍎', '🍎', '🍎', '🍎', '🍎', '🍎',
'🥕',
];
// Теперь просто извлекаем произвольный элемент из `weightedItems`Однако, как вы можете видеть, такой подход требует большого количества памяти в случае, когда у нас много элементов для повторения. Например, повторение строки "some-random-string" 10 млн раз потребует выделения около 180 Мб памяти только для массива weightedItems.
Более эффективный подход состоит в следующем:
- Готовим список совокупных весов для каждого элемента (список
cumulativeWeightsбудет иметь такую же длину, как исходный списокweights). В нашем случае он будет выглядеть так:cumulativeWeights = [3, 3 + 7, 3 + 7 + 1] = [3, 10, 11]. - Выбираем произвольное число в диапазоне от
0до наибольшего совокупного веса. В нашем случае таким диапазоном будет[0...11]. Допустим, мы получилиrandomNumber = 8. - Перебираем
cumulativeWeightsслева направо и берем первый элемент, который больше или равенrandomNumber. Индекс такого элемента используется для выбора элемента из спискаitems.
Основная идея данного подхода состоит в том, что более высокие веса будут "занимать" больше числового пространства. Таким образом, более высока вероятность выбора произвольного числа из "числовой группы более высокого веса".
const weights = [3, 7, 1 ];
const cumulativeWeights = [3, 10, 11];
// `cumulativeWeights` можно представить так
const pseudoCumulativeWeights = [
1, 2, 3, // <-- 3 числа
4, 5, 6, 7, 8, 9, 10, // <-- 7 чисел
11, // <-- 1 число
];Реализация
// algorithms/statistics/weighted-random.js
/**
* Возвращает произвольный элемент на основе его веса.
* Элементы с более высоким весом выбираются чаще (с большей вероятностью).
*
* Например:
* - items = ['banana', 'orange', 'apple']
* - weights = [0, 0.2, 0.8]
* - weightedRandom(items, weights) в 80% случаев будет возвращать 'apple',
* в 20% случаев - 'orange' и никогда - 'banana' (поскольку вероятность его выбора равна 0%)
*
* @param {any[]} items
* @param {number[]} weights
* @returns {{item: any, index: number}}
*/
export default function weightedRandom(items, weights) {
if (!items.length || !weights.length) {
throw new Error('Элементы/веса не должны быть пустыми')
}
if (items.length !== weights.length) {
throw new Error('Массивы элементов и весов должны иметь одинаковую длину')
}
// Готовим массив совокупных весов.
// Например:
// - weights = [1, 4, 3]
// - cumulativeWeights = [1, 5, 8]
const cumulativeWeights = []
for (let i = 0; i < weights.length; i++) {
cumulativeWeights[i] = weights[i] + (cumulativeWeights[i - 1] || 0)
}
// Получаем произвольное число в диапазоне [0...sum(weights)].
// Например:
// - weights = [1, 4, 3]
// - maxCumulativeWeight = 8
// - диапазон произвольного числа - [0...8]
const maxCumulativeWeight = cumulativeWeights.at(-1)
const random = Math.random() * maxCumulativeWeight
// Извлекаем произвольный элемент на основе его веса.
// Элементы с более высоким весом выбираются чаще
const index = cumulativeWeights.findIndex((cumulativeWeight) => {
return cumulativeWeight >= random
})
const item = items[index]
return {
item,
index,
}
}import weightedRandom from '../weighted-random'
describe('weightedRandom', () => {
it('при передаче пустого массива элементов или весов должно выбрасываться исключение', () => {
const getWeightedRandomWithInvalidInputs = () => {
weightedRandom([], [])
}
expect(getWeightedRandomWithInvalidInputs).toThrow(
'Элементы/веса не должны быть пустыми',
)
})
it('при несовпадении количества элементов и весов должно выбрасываться исключение', () => {
const getWeightedRandomWithInvalidInputs = () => {
weightedRandom(['a', 'b', 'c'], [10, 0])
}
expect(getWeightedRandomWithInvalidInputs).toThrow(
'Массивы элементов и весов должны иметь одинаковую длину',
)
})
it('должен правильно выполнять взвешенную произвольную выборку в простых случаях', () => {
expect(weightedRandom(['a', 'b', 'c'], [1, 0, 0])).toEqual({
index: 0,
item: 'a',
})
expect(weightedRandom(['a', 'b', 'c'], [0, 1, 0])).toEqual({
index: 1,
item: 'b',
})
expect(weightedRandom(['a', 'b', 'c'], [0, 0, 1])).toEqual({
index: 2,
item: 'c',
})
expect(weightedRandom(['a', 'b', 'c'], [0, 1, 1])).not.toEqual({
index: 0,
item: 'a',
})
expect(weightedRandom(['a', 'b', 'c'], [1, 0, 1])).not.toEqual({
index: 1,
item: 'b',
})
expect(weightedRandom(['a', 'b', 'c'], [1, 1, 0])).not.toEqual({
index: 2,
item: 'c',
})
})
it('должен правильно выполнять взвешенную произвольную выборку', () => {
// Количество выборок
const ATTEMPTS_NUM = 1000
// Погрешность количества выборок элемента.
// Например, если мы хотим, чтобы элемент 'a' выбирался 300 раз из 1000 (30%),
// тогда 267 раз является приемлемым, поскольку это больше 250 (300 - 50)
// и меньше 350 (300 + 50)
const THRESHOLD = 50
const items = ['a', 'b', 'c'] // значения элементов неважны
const weights = [0.1, 0.3, 0.6]
const counter = []
for (let i = 0; i < ATTEMPTS_NUM; i += 1) {
const randomItem = weightedRandom(items, weights)
if (!counter[randomItem.index]) {
counter[randomItem.index] = 1
} else {
counter[randomItem.index] += 1
}
}
for (let itemIndex = 0; itemIndex < items.length; itemIndex += 1) {
/*
Элемент под индексом 0 должен выбираться 100 раз (в идеале)
или, учитывая порог, [100 - 50, 100 + 50] раз.
Элемент под индексом 1 должен выбираться 300 раз (в идеале)
или, учитывая порог, [300 - 50, 300 + 50] раз.
Элемент под индексом 2 должен выбираться 600 раз (в идеале)
или, учитывая порог, [600 - 50, 600 + 50] раз
*/
expect(counter[itemIndex]).toBeGreaterThan(
ATTEMPTS_NUM * weights[itemIndex] - THRESHOLD,
)
expect(counter[itemIndex]).toBeLessThan(
ATTEMPTS_NUM * weights[itemIndex] + THRESHOLD,
)
}
})
})Запускаем тесты:
npm run test ./algorithms/statistics
На сегодня это все, друзья. Увидимся в следующей части.
Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩
