Байесовский классификатор - это классификатор, использующий теорему Байеса для определения вероятности принадлежности наблюдения (элемента выборки) к одному из классов C при условии того, что зависимые переменные принимают заданные значения: P(C|F₁ ,...,F_n ). То есть, если на основе значений переменных можно однозначно определить, какому классу относится наблюдение, байесовский классификатор сообщит, что вероятность принадлежности к этому классу равна 1. В промежуточных же случаях, когда наблюдение может с разной вероятностью принадлежать к различным классам, результатом работы классификатора будет вектор, компоненты которого являются вероятностями принадлежности к тому или иному классу.

Можно видеть, что идеальный байесовский классификатор в каком-то смысле является оптимальным. Его результат не может быть улучшен, т.к. во всех случаях, когда возможен однозначный ответ, он его даст - а в тех случаях, когда ответ неоднозначен, результат количественно характеризует меру этой неоднозначности. Вместе с тем, в оптимальности кроется и основной недостаток идеального байесовского классификатора: для его построения требуется выборка, содержащая все возможные комбинации переменных - а размер такой выборки экспоненциально растет с ростом числа переменных (т.н. "проклятие размерности").

Для преодоления описанной выше проблемы на практике используют т.н. наивный байесовский классификатор - классификатор, построенный на основе предположения о независимости переменных, т.е. предположения о том, что

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

Преимуществом этого подхода является то, что требования к размеру выборки сокращаются от экспоненциальных до линейных. Недостаток - то, что модель точна лишь в случае, когда выполняется предположение о независимости. В противном случае, строго говоря, вычисленные вероятности уже не являются точными (и даже более того, их сумма может не равняться единице, из-за чего требуется нормировать результат). Однако на практике незначительные отклонения от независимости приводят лишь к незначительному снижению точности, и даже в случае существенной зависимости между переменными результат работы классификатора продолжает коррелировать с истинной принадлежностью образа к классам. При этом достоинства классификатора (высокая скорость работы, простота и масштабируемость, умеренные требования к памяти) часто перевешивают недостатки.

Пропущенные значения

Важной особенностью байесовского классификатора является то, что он может быть построен на основе выборки с пропущенными значениями. Следует отметить, что классификатор исходит из предположения о том, что наличие или отсутствие значений переменных носит абсолютно случайный характер (MCAR, Missing Completely At Random). В случае, если наблюдения с пропущенными значениями систематически отличаются от других наблюдений, возможна некорректная работа классификатора. В этом случае рекомендуется выделить специальное значение, обозначающее пропуск.

Пример 1: данные представляют собой результаты переписи населения, проведенной в 1873 году. Часть записей выцвела из-за длительного хранения и в ходе оцифровки пришлось пропустить значения, которые невозможно прочитать. Очевидно, что здесь пропущенные значения распределены случайно.

Пример 2: данные представляют собой результаты измерения длины, ширины и высоты контейнеров на складе. Длина и ширина указаны всегда, часть значений высоты пропущена, т.к. измерявший не доставал до верхнего края контейнера. В данном случае имеется систематичное отсутствие значений выше определенного уровня, что может исказить результаты. Правильным будет ввести ещё одно значение для переменной "высота" - "не удалось измерить".

Непрерывные переменные

В случае дискретной независимой переменной условные вероятности, использующиеся в ходе работы классификатора, легко вычислить. Однако если независимая переменная непрерывна, то рассчитать на основе выборки вероятность того, что она примет указанное значение, уже не так просто. Существует два подхода к обработке непрерывных переменных: дискретизация и использование методов оценки плотности (например, KDE). Классификатор, входящий в пакет ALGLIB, использует автоматическую дискретизацию.

Дискретизация осуществляется прозрачно для пользователя, следует только выбрать алгоритм дискретизации. Пакет ALGLIB содержит два алгоритма: неоптимальный, обладающий трудоемкостью O(NPoints ^1.33), и оптимальный, трудоемкость которого равна O(NPoints ^2.33). Оптимальный алгоритм находит разбиение диапазона значений вещественной переменной на интервалы, при котором минимизируется ошибка классификации с использованием только этой переменной. Неоптимальный алгоритм также ищет минимум, но только среди разбиений на интервалы, содержащие одинаковое число значений переменной. Оптимальный алгоритм лучше адаптируется к особенностям распределения, размещая границы интервалов как можно ближе к границам классов. Однако с ростом размера выборки это преимущество становится менее значительным, т.к. возрастает исло интервалов, на которые можно разбить диапазон значений, а значит, и неоптимальный алгоритм становится достаточно гибок. Выбор алгоритма главным образом определяется соображениями быстродействия - если вы можете позволить себе использовать оптимальный алгоритм, почему бы не использовать его? Если нет (например, размер выборки измеряется десятками тысяч элементов), то остается только неоптимальный алгоритм.

Описание модуля bayes

Подпрограммы модуля можно разделить на три группы: построение классификатора, использование классификатора, вспомогательные подпрограммы. Ниже приведена краткая информация о подпрограммах и их параметрах; более детальная информация доступна в комментариях к подпрограммам.

Наиболее общей из подпрограмм, обучающих классификатор, является подпрограмма NBCBuildM. Эта подпрограмма обучает байесовский классификатор на основе выборки, которая может содержать пропущенные значения (задаются массивом-маской). Выборка имеет стандартный для пакета ALGLIB формат - двухмерный массив, каждая строка которого соответствует одному наблюдению. В начале строки располагаются независимые переменные, номинальные переменные принимают целые значения от 0 до F_j -1 (где F_j  - максимальное число значений j-ой переменной), а в конце строки располагается номер класса, принимающий значения от 0 до NClasses-1. Результатом работы является вещественный массив C, содержащий построенную модель во внутреннем формате ALGLIB. Кроме подпрограммы NBCBuildM доступны также подпрограмма NBCBuild (отличающаяся тем, что не принимает маску пропущенных значений - на случай, если пропущенные значения отсутствуют) и NBCBuildI, работающая только с дискретными переменными (эта подпрограмма является основой для других подпрограмм модуля).

Для получения вектора вероятностей принадлежности наблюдения ко всем возможным классам служат подпрограммы NBCProcess и NBCProcessM. Они принимают вектор независимых переменных и возвращают вектор вероятностей. Первая подпрограмма работает с наблюдениями, у которых присутствуют все независимые переменные, вторая может обрабатывать векторы переменных с пропущенными значениями. Следует отметить, что подпрограммы не выделяют память под массив, в котором хранится их результат. Это должна сделать вызывающая программа.

Следущая группа подпрограмм служит для получения ошибки классификатора на тестовом множестве. Подпрограммы NBCAvgCE и NBCClsError возвращают среднюю кросс-энтропию (в битах на наблюдение) и ошибку классификации (число неверно классифицированных случаев) на тестовом множестве, не содержащем пропущенных значений независимых переменных. В случае, если часть значений пропущена, можно использовать подпрограммы NBCAvgCEM и NBCClsErrorM (в качестве одного из параметров передается маска пропущенных значений).