Цель

Создать классификатор с нуля на C++ на основе теоремы Байеса об условной вероятности без использования внешних сторонних библиотек, таких как Eigen! Просто чистое и веселое программирование с нуля.

Введение

Gaussian Naive Bayes (GNB) — это вероятностный метод определения результата с использованием условной вероятности. Как следует из названия, это Наивный, потому что он делает сильное предположение, что все признаки независимы друг от друга и имеют вероятность, определенную заданным классом с и распределением Гаусса для признака х.

Алгоритм

В этом разделе сначала рассматривается теория условной вероятности, а затем ее реализация.

Теория

Поскольку GNB основан на модели условной вероятности, довольно просто выразить проблему сначала простыми словами, а затем в математических обозначениях.

В основном,

Определим некоторые переменные.

Ck — каждый из K возможных классов
n — количество признаков
x — признак

используя это, мы можем определить проблему, которую необходимо классифицировать, а именно:

где каждый x - независимые функции. Это основное предположение наивной теоремы Байеса об условной вероятности. Используя это, основное уравнение можно записать в математических обозначениях.[1]

Числитель дроби имеет значение, так как знаменатель является только нормирующим членом. следовательно, это можно записать как:

с помощью цепного правила его можно расширить до:

Наивное предположение об условной независимости приводит к:

Следовательно, совместная вероятностная модель упрощается следующим образом:

где N - нормирующий коэффициент

Классификация

Чтобы построить классификатор, максимальное значение вычисленных вероятностей используется для определения прогнозируемого класса.

Обучение

Когда данные обучения доступны с непрерывным атрибутом «x» в качестве функций, делается предположение, что распределение является нормальным. Следовательно, следующим шагом является вычисление дисперсии (σ²_k) и среднего значения (μ_k) x в каждом классе. где;

вычисленное значение даст априорные вероятности для каждого класса.[1]

Выполнение

Реализацию можно найти в этом Репозитории.

Примечания: в репозитории можно найти источники с объявленным GNB, определенным в «classifier.h» и «classifier.cpp» соответственно. С точки зрения приложения потребуются только GNB::Train(…) и GNB::Predict(…), но это не является целью. Цель состоит в том, чтобы понять, что было сделано для реализации классификатора GNB.

из которых функция

void CalcStatistics(const vector<vector<double>>& data,                               const vector<string>& labels);

отвечает за расчет априорных вероятностей. путем сохранения стандартного отклонения (σ_k) и среднего значения (μ_k) каждого класса (т.е. метки) C_k.

Функция GNB::predict(…) принимает тестовую выборку и прогнозирует метку.

Это позволит вычислить вероятности тестовой выборки по всем меткам.

Все это, конечно, требует вычисления вероятностей с использованием гауссового, то есть нормального распределения, которое обсуждалось ранее.

double GNB::gaussian(double x, double mu, double sigma) const                       {                           double expr1 = 1.0 / sqrt(2 * M_PI);                             double expr2 = pow((x - mu) / sigma, 2)*-0.5;
return (expr1 / sigma) * exp(expr2);   
}

Следующим важным шагом является получение файла argmax. это завершит реализацию классификатора

Данные

GNB полезен против непрерывных вводов функций. Поэтому он использовался для экспериментов по обнаружению намерений целевого транспортного средства сменить полосу движения на дороге с использованием данных о траектории транспортного средства на разных полосах движения. Есть три возможных метки, как показано на рисунке.

«держать» — сохранять полосу, т. е. не менять полосу (черный)
«право» — менять полосу вправо (красный)
«лево» — менять полосу налево (синий)

Эти данные были разбиты на два файла, как вы видите в Repository/data:

// load the train and test data
vector<vector<double> > X_train = Load_State("../data/train_states.txt");                         
vector<vector<double> > X_test  = Load_State("../data/test_states.txt");                         
vector<string> Y_train = Load_Label("../data/train_labels.txt");                         vector<string> Y_test  = Load_Label("../data/test_labels.txt");
//Training
GNB gnb = GNB();                                                  gnb.train(X_train, Y_train);
//Predictions
int score = 0;                         
for (int i = 0; i < X_test.size(); ++i) {
vector<double> coords = X_test[i];
string predicted = gnb.predict(coords);
//find accuracy.
if (predicted.compare(Y_test[i]) == 0) 
{
score += 1; 
}                         
}                                                 
float fraction_correct = float(score) / Y_test.size();

fraction_correct дает точность классификатора.

после построения и запуска проекта следует увидеть производительность классификатора с точки зрения его точности.

Резюме

Таким образом, был подробно описан дизайн и реализация простого гауссовского наивного байесовского классификатора, а также кратко обсуждено его применение для выявления намерений сменить полосу движения.

использованная литература

  1. МУРТИ, М. Нарасимха; ДЭВИ, В. Сушила. Распознавание образов: алгоритмический подход. Springer Science & Business Media, 2011.
  2. МАККАЛУМ, Эндрю и др. Сравнение моделей событий для наивной байесовской классификации текстов. В: Семинар AAAI-98 по обучению категоризации текста. 1998. С. 41–48.
  3. Данные предоставлены в курсе https://www.udacity.com/course/self-driving-car-engineer-nanodegree--nd013