Классификация документов - Обучающие методы

Интернет магазин китайских планшетных компьютеров

Компьютеры - Классификация документов - Обучающие методы

23 января 2011

Оглавление:
1. Классификация документов
2. Постановка задачи
3. Обучающие методы
4. Применение

Наивная байесовская модель

Наивная байесовская модель является вероятностным методом обучения. Вероятность того, что документ d попадёт в класс c записывается как P. Поскольку цель классификации - найти самый подходящий класс для данного документа, то в наивной байесовской классификации задача состоит в нахождении наиболее вероятного класса c_m

$c_m = \underset{c \in C}{\operatorname{argmax}} \, P$

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

$c_m = \underset{c \in C}{\operatorname{argmax}} \, \frac{PP}{P} = \underset{c \in C}{\operatorname{argmax}} \, PP$

где знаменатель P опущен, так как не зависит от c и, следовательно, не влияет на нахождение максимума; P - вероятность того, что встретится класс c, независимо от рассматриваемого документа; P - вероятность встретить документ d среди документов класса c.

Используя обучающее множество, вероятность P можно оценить как

$\hat{P} = \frac{N_c}{N}$

где N_c - количество документов в классе c, N - общее количество документов в обучающем множестве. Здесь использован другой знак для вероятности, поскольку с помощью обучающего множества можно лишь оценить вероятность, но не найти её точное значение.

Чтобы оценить вероятность $P = P$ , где t_k - терм из документа d, n_d - общее количество термов в документе, необходимо ввести упрощающие предположения о условной независимости термов и о независимости позиций термов. Другими словами, мы пренебрегаем, во-первых, тем фактом, что в тексте на естественном языке появление одного слова часто тесно связано с появлением других слов, и, во-вторых, что вероятность встретить одно и то же слово различна для разных позиций в тексте. Именно из-за этих грубых упрощений рассматриваемая модель естественного языка называется наивной. Итак, в свете сделанных предположений, используя правило умножения вероятностей независимых событий, можно записать

$P = P = PP...P = \prod_{k=1}^{n_d} P$

Оценка вероятнотей P с помощью обучающего множества будет

$\hat{P} = \frac{T_{ct}}{T_c}$

где T_ct - количество вхождений терма t во всех документах класса c; T_c - общее количество термов в документах класса c. При подсчёте учитываются все повторные вхождения.

После того, как классификатор "обучен", то есть найдены величины $\hat{P}$ и $\hat{P}$ , можно отыскать класс документа

$c_m = \underset{c \in C}{\operatorname{argmax}} \, \hat{P}\hat{P} = \underset{c \in C}{\operatorname{argmax}} \hat{P} \prod_{k=1}^{n_d} \hat{P}$

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

$c_m = \underset{c \in C}{\operatorname{argmax}}$

Эта формула имеет простую интерпретацию. Шансы классифицировать документ часто встречающимся классом выше, и слагаемое $\log\hat{P}$ вносит в общую сумму соответствующий вклад. Величины же $\log\hat{P}$ тем больше, чем важнее терм t для идентификации класса c, и, соответственно, тем весомее их вклад в общую сумму.

<<< Задача классификации

Компьютерное аппаратное обеспечение
Вычислительные комплексы
Компьютерные данные
Компьютерные журналы
Классы компьютеров
Компьютеры

Программное обеспечение
Производители компьютеров
Профессии в ИТ
Системное администрирование
Компьютерный сленг
Списки компьютерных терминов

Человеко-компьютерное взаимодействие