РАЗДЕЛ 2
РАЗРАБОТКА МЕТОДОВ КЛАССИФИКАЦИИ ИНФОРМАЦИИ ДЛЯ ИНФОРМАЦИОННО-ПОИСКОВОЙ СИСТЕМЫ
ТАМОЖЕННОЙ СЛУЖБЫ УКРАИНЫ
В этом разделе выполнена формализация задачи по классификации документов в
АИПС. Основной информацией для классификации является значение случайного
вектора характеризующего вхождение в текущий документ терминов из словаря
данных. Получены выражения для условных вероятностей случая, когда в документ
данного класса вводит определенный набор терминов из словаря данных. Указанные
выражения получены в предположениях о взаимной независимости появления
различных терминов в документе, а также взаимной независимости появления
всевозможных пар терминов, троек терминов и т.д. Для всех рассмотренных случаев
получены оценки указанных условных вероятностей на основе информации о
классификации предыдущих документов (информации об обучающей выборке
документов). На основе полученных оценок построены выражения для решающих
функций байесовского классификатора. Эти решающие функции являются основой
численных алгоритмов классификации [91-109].
2.1 Постановка задачи классификации текстовой документации для
информационно-поисковой системы
Для математической постановки задачи введем следующие основные понятия и
определения.
Под системой документооборота будем понимать совокупность тематических разделов
Ci, i=1,…,n, структурированных определенным образом, к которым могут относиться
поступающие документы. Принадлежность данного документа D к определенному
тематическому разделу (классу) Ci будем обозначать: DО Ci. Вообще говоря, один
и тот же документ может относиться к нескольким классам. Системой классификации
(классификатором) будем называть устройство, которое относит поступающий на
вход системы документ Dj (j=1, 2, …) к определенному классу (классам) Ci. Эта
система в своей работе должна, очевидно, использовать определенную информацию о
документе Dj, на основе которой она и принимает классификационное решение.
Такая информация в теории распознавания называется вектором признаков образа. В
качестве такой информации будем рассматривать, как наиболее важный, факт
вхождения (или не вхождения) в документ определенного термина (дескриптора) из
множества V={v1, v2, …, vm}, которое назовем тезаурусом или словарем данных.
Таким образом, под вектором признаков документа-образа будем понимать вектор
x(j)={x1, x2, …, xm}(j), где
xk=. (2.1)
Таким образом, задача состоит в построении системы классификации, которая будет
на основе этой информации, а также решений о распознавании предыдущих j-1
документов, принимать решение, к какому из классов Ci отнести заданный
документ.
В теории распознавания принято в качестве системы классификации рассматривать
систему решающих функций di, i=1,…,n. Для таких функций принимается решение об
отнесении образа x(j) к классу Ci, если di(x(j))іdl(x(j)) для любого l=1,…, n,
l № i.
При работе системы классификации возможны две ситуации. Первую ситуацию, когда
система относит образ x(j), действительно принадлежащий к классу Ci, к этому
классу, будем называть успехом (правильной классификацией). Противоположный
случай, когда документ с вектором признаков x(j), на самом деле принадлежащий к
классу Ci, относится системой к классу Cp, p№i, будем называть ошибкой
классификации (неуспехом). Очевидно, что среди множества всех классификаторов
нас интересуют именно те, которые «меньше ошибаются». Существует несколько
подходов к построению подобных критериев качества классификации. В
статистической теории распознавания наиболее известным является критерий,
называемый байесовским классификатором [91-109], основанный на минимизации
средних потерь при использовании системы классификации. Под потерей понимается
проигрыш игрока – системы классификации – в игре с нулевой суммой против
другого игрока – природы, которая «поставляет» образы на вход системы
классификации. Будем считать, что природа в этой игре выбирает стратегию Ci,
когда на вход системы распознавания выдается документ DОCi. Вероятность выбора
этой стратегии обозначим через P(Ci). Стратегией системы распознавания будет
указание класса Cl , к которому она относит данный документ. Указанная игра
будет характеризоваться матрицей потерь Lil. Предположим, что природа выдает
образы независимо один от другого, руководствуясь вероятностями P(Ci). Тогда
математическое ожидание потерь, связанных с отнесением системой образа x(j) к
классу Cl, определится формулой:
rl(x(j)) = . (2.2)
Здесь P(Ci|x(j)) – условная вероятность появления класса Ci, когда на вход
системы был подан образ x(j).
Байесовским называется классификационное правило, которое минимизирует величину
(2.2) [91, 92].
В большинстве случаев естественно предположить, что потери при правильной
классификации равны нулю, а в противном случае равны единице, т.е.
Lil = 1-dil , (2.3)
где dil – символы Кронекера.
Докажем следующую теорему.
Теорема 1.
Для матрицы потерь (2.3) байесовское классификационное правило будет
определяться набором решающих функций вида
di(x(j)) = P(x(j)|Ci)P(Ci). (2.4)
Здесь P(x(j)|Ci) – вероятность появления образа x(j), когда выпал класс
Ci. [91]
Доказательство.
Воспользовавшись формулой Байеса
P(Ci|x(j)) = , (2.5)
выражение (2.5) можно представить в следующем виде:
rl(x(j)) = , (2.6)
где P(x(j)|Ci) называют функцией правдоподобия для класса Ci.
Поскольку выражение входит во все формулы вычисления условных средних потерь
rl(x(j)), l=1,2,…,N в качестве общего множителя, его можно устранить из
соотношения (2.6). В таком случае выражение для средних потерь сводится к
следующему:
rl(x(j)) = . (2
- Київ+380960830922