26.06.2024 00:32
interesting-cs-math 0 751 Источник

Введение

В данной статье рассмотрим вывод формулы разделительной линии «наивного» байесовского классификатора для случая, когда все объекты выборки имеют один вес (одинаковый штраф за ошибку классификации).

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

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

Рассмотрим вывод формулы. Запишем формулу разделительной линии в общем виде.

{X}_{y} {\hat{P}}_{y} {\hat{p}}_{y}(x) = {X}_{s} {\hat{P}}_{s} {\hat{p}}_{s}(x){\hat{P}}_{y} = \frac{l_y}{l}; {\hat{P}}_{s} = \frac{l_s}{l}\frac{l_y}{l} {\hat{p}}_y(x) = \frac{l_s}{l} {\hat{p}}_s(x); l_y {\hat{p}}_y(x) = l_s {\hat{p}}_s(x)

Логарифмируем:

ln(l_y) + ln({\hat{p}}_y(x)) = ln(l_s) + ln({\hat{p}}_s(x))\hat{p}_y (x) = \hat{p}_{y_1} (x) \cdot \hat{p}_{y_2} (x) \dotsm \hat{p}_{y_n} (x)\hat{p}_{y_j} (x_j) = \frac{1}{\sigma_{y_j} \cdot \sqrt{2\pi}} exp \left( - \frac{(x_j -\mu_{y_j})^2}{2 \sigma_{yj}^{2}} \right)ln(l_y) + \sum_{j=1}^{n} ln \left( \frac{1}{\sigma_{yj} \sqrt{2\pi}} - \frac{(x_j-\mu_{yj})^2}{2 \sigma_{yj}^{2}} \right) = =ln(l_s) + \sum_{j=1}^{n} ln \left( \frac{1}{\sigma_{sj} \sqrt{2\pi}} - \frac{(x_j-\mu_{sj})^2}{2 \sigma_{sj}^{2}} \right)ln(l_y) - ln(l_s) - \sum_{j=1}^{n} ln(\sigma_{yj}) - \sum_{j=1}^{n} ln(\sqrt{2\pi}) - \frac{1}{2} \sum_{j=1}^{n} \frac{(x_j - \mu_{yj})^2}{\sigma_{yj}^{2}} ++\sum_{j=1}^{n} ln (\sigma_{sj}) + \sum_{j=1}^{n}ln(\sqrt{2\pi})+ \frac{1}{2} \sum_{j=1}^{n} \frac{(x_j - \mu_{sj})^2}{\sigma_{sj}^{2}} =0\text{Пусть } M = ln(l_y) - ln(l_s) - \sum_{j=1}^{n} ln (\sigma_{yj}) + \sum_{j=1}^{n} ln(\sigma_{sj})-\frac{1}{2} \sum_{j=1}^{n} \frac{(x_j - \mu_{yj})^2}{\sigma_{yj}^{2}} + \frac{1}{2} \sum_{j=1}^{n} \frac{(x_j - \mu_{sj})^2}{\sigma_{sj}^{2}} + M = 0-\sum_{j=1}^{n} \frac{(x_j - \mu_{yj})^2}{\sigma_{yj}^{2}} + \sum_{j=1}^{n} \frac{(x_j - \mu_{sj})^2}{\sigma_{sj}^{2}} + 2M = 0-\sum_{j=1}^{n} \frac{x_j^2 - 2\mu_{yj} x_j + \mu_{yj}^2}{\sigma_{yj}^{2}} + \sum_{j=1}^{n} \frac{x_j^2 - 2\mu_{sj} x_j + \mu_{sj}^2}{\sigma_{sj}^{2}} + 2M = 0-\sum_{j=1}^n \frac{x_j^2}{\sigma_{yj}^2} + 2 \sum_{j=1}^n \frac{\mu_{yj}}{\sigma_{yj}^2} x_j - \sum_{j=1}^n \frac{\mu_{yj}^2}{\sigma_{yj}^2} ++\sum_{j=1}^n \frac{x_j^2}{\sigma_{sj}^2} - 2 \sum_{j=1}^n \frac{\mu_{sj}}{\sigma_{sj}^2} x_j + \sum_{j=1}^n \frac{\mu_{sj}^2}{\sigma_{sj}^2} + 2M = 0\text{Пусть } С = \sum_{j=1}^n \frac{\mu_{yj}^2}{\sigma_{yj}^2} + \sum_{j=1}^n \frac{\mu_{sj}^2}{\sigma_{sj}^2} + 2M\sum_{j=1}^n \left( -\frac{1}{\sigma_{yj}^2} + \frac{1}{\sigma_{sj}^2} \right) x_j^2 + 2 \sum_{j=1}^n \left( \frac{\mu_{yj}}{\sigma_{yj}^2} - \frac{\mu_{sj}}{\sigma_{sj}^2} \right) x_j + C = 0\sum_{j=1}^n a_j x_j^2 + 2 \sum_{j=1}^n b_j x_j + C = 0

Полученная формула позволяет не перебирать всё пространство возможных объектов. Нет необходимости строить карту классификации. Достаточно построить разделительную линию.

Для построения разделительной линии достаточно перебрать значения лишь одного из признаков (когда всего 2 признака). В общем случае, если признаков m, то асимптотическая сложность алгоритма построения разделительной линии O(X^{m-1}), где X – диапазон значений признаков (для простоты изложения будем считать, что диапазонX значений признаков одинаковый).

Комментарии (0)