Содержание к диссертации
Введение
ГЛАВА 1. Задача классификации многотемных документов 13
1.1 Постановка задачи и требования к решению 13
1.2 Обзор методов классификации многотемных документов 14
1.2.1 Критерии сравнения методов 14
1.2.2 Методы, основанные на оптимизационном подходе 16
1.2.2.1 Метод AdaBoost.MH 17
1.2.2.2 Метод ADTBoost.MII 18
1.2.2.3 Метод ML-kNN на основе алгоритма к-ближайших соседей и принципа максимизации апостериорных вероятностей 19
1.2.2.4 Метод на основе модели смешивания, обученной с помощью метода максимизации математического ожидания 21
1.2.3 Методы, основанные на декомпозиции в набор независимых бинарных проблем 22
1.2.4 Методы, основанные на подходе ранжирования с последующим отсечением нерелевантных классов 23
1.2.4.1 Метод Multiclass-Multilabel Perceptron 24
1.2.4.2 Метод k-ближайших соседей 26
1.2.4.3 Метод RankSVM 27
1.2.4.4 Методы отсечения нерелевантных классов 28
1.3 Выводы 29
ГЛАВА 2. Решение задачи классификации многотемных документов на основе подхода попарных сравнений 30
2.1 Структура предложенного решения 30
2.2 Традиционный подход на основе попарных сравнений для взаимно исключающих классов 33
2.3 Предложенный метод ранжирования на основе попарных сравнений для существенно пересекающихся классов 36
2.4 Предложенные методы отсечения нерелевантных классов 39
2.4.1 Метод, основанный на пороговой функции в пространстве релевантностей классов 40
2.4.2 Метод, основанный на предположении о существовании линейной зависимости функции классификации от функции ранжирования 41
2.5 Дообучение метода классификации 45
2.6 Экспериментальная оценка предложенного решения на эталонных наборах данных 48
2.6.1 Описание тестовых данных 48
2.6.2 Сравнение эффективности методов отсечения нерелевантных классов 49
2.6.3 Сравнение эффективности методов классификации многотемных документов 51
2.7 Выводы 53
ГЛАВА 3. Модель представления гипертекстовых документов 54
3.1 Постановка задачи и требования к решению 54
3.2 Обзор методов построения модели представления гипертекстовых документов 55
3.2.1 Критерии сравнения моделей представления 55
3.2.2 Выделение признаков в гипертекстовых документах 56
3.2.2.1 Метод ключевых слов 56
3.2.2.2 Метод N-грамм 58
3.2.2.3 Учёт окружения гипертекстовых документов 59
3.2.3 Меры сходства для документов 59
3.2.3.1 Частотная мера сходства 59
3.2.3.2 Мера сходства k-spectrum 61
3.2.4 Выводы 62
3.3 Модель представления гипертекстовых документов на основе частых комбинаций признаков с учетом гиперссылок 62
3.3.1 Предложенный метод учёта гиперссылок при представлении гипертекстовых документов 63
3.3.2 Предложенный метод построения модели представления на основе выделения частых эпизодов признаков 64
3.3.3 Дообучение метода построения модели представления документов 65
3.3.4 Экспериментальная оценка предложенного решения на эталонных наборах данных 66
3.3.4.1 Описание тестовых данных 67
3.3.4.2 Оценка эффективности предложенной модели представления 67
3.3.4.3 Сравнение эффективности методов выделения признаков 69
3.3.4.4 Оценка эффективности разработанного метода классификации с разработанной моделью представления документов 72
3.4 Выводы 74
ГЛАВА 4. Экспериментальный модуль классификации многотемных гипертекстовых документов 76
4.1 Требования к программным средствам классификации многотемных гипертекстовых документов 76
4.2 Архитектура экспериментального модуля 78
4.2.1 Компонент лексического анализа 79
4.2.2 Компонент вычисления меры сходства 82
4.2.3 Классификатор 83
4.2.4 Свойства разработанной архитектуры 85
4.3 Сценарии функционирования модуля 89
4.3.1 Обучение 90
4.3.2 Классификация 90
4.3.3 Дообучение и добавление темы 90
4.3.4 Удаление темы 91
4.4 Особенности программной реализации модуля классификации 91
4.5 Исследование производительности модуля и результаты экспериментов 94
4.6 Выводы 95
Заключение 96
Литература
- Метод ML-kNN на основе алгоритма к-ближайших соседей и принципа максимизации апостериорных вероятностей
- Традиционный подход на основе попарных сравнений для взаимно исключающих классов
- Сравнение эффективности методов отсечения нерелевантных классов
- Обзор методов построения модели представления гипертекстовых документов
Введение к работе
Настоящая работа посвящена исследованию и разработке алгоритмов и методов построения программных средств классификации многотемных гипертекстовых документов. Задача классификации многотемных документов (multi-label classification), заключается в определении принадлежности документа к одному или нескольким классам (из предопределённого набора классов) на основании анализа совокупности признаков, характеризующих данный документ [4,9]. Классы, к которым принадлежит документ, называются релевантными для данного документа (рис. 1). Классы в рассматриваемой задаче не являются взаимоисключающими (как в традиционной постановке задачи классификации), а могут пересекаться и быть вложенными (рис. 2).
П р едо пр сделен и ы й набор классов
Разработка подходов и алгоритмов решения задачи классификации многотемных документов - это относительно новое направление исследований, которое в настоящее время активно развивается за рубежом и в России. Большинство существующих подходов [4,6-9,11,12] является альтернативой непосредственного сведения задачи классификации многотемных документов к традиционной задаче классификации, характеризующейся тем, что классифицируемый объект может принадлежать только к одному классу (multi-class classification) [18].
Рисунок 2. Multi-class и multi-label классификация.
На сегодняшний день существует ряд актуальных прикладных задач, при решении которых возникает необходимость разработки программных средств классификации
многотемных документов. К числу таких задач относятся: категоризация электронной почты [60-62]; мониторинг документооборота пользователей и предотвращение утечек конфиденциальной информации [53]; анализ и фильтрация Интернет-трафика [54-56]; автоматизированное модерирование Интернет-ресурсов [58]; категоризация документов в электронных библиотеках [52] и другие. Остановимся подробнее на некоторых из перечисленных задач.
Объёмы электронной корреспонденции и время работы пользователей с ней ежегодно возрастают, в связи с этим возникает необходимость в средствах автоматизированной категоризации электронной почты. Почтовые папки пользователей могут иметь сложную структуру и не обязательно соответствуют семантическим тематикам или отдельным адресатам. Папки могут соответствовать текущим задачам, группам проектов, адресатам, группам адресатов и т.д. При этом электронные сообщения являются многотемными относительно заданного набора папок: например, одно и то же сообщение может относиться как к текущему проекту, которым занимается пользователь, так и к нескольким отдельным адресатам (рис. 3). Отметим, что при решении данной задачи предъявляются высокие требования к производительности программных средств классификации, поскольку автоматическая категоризация входящих электронных писем не должна приводить к задержкам при общении пользователей в интерактивном режиме.
.*$
Рисунок 3. Категоризация электронной почты.
В задаче анализа и фильтрации Интернет-трафика возникает необходимость определять тематики web-страниц для блокирования доступа учащихся и сотрудников
организаций к нелегальной информации, принадлежащей к определённым категориям ресурсов, а также для предотвращения нецелевого использования Интернет-ресурсов в рабочее время. Набор категорий фильтрации Интернет-ресурсов определяется, исходя из специфики организации и возможности задания гибких политик фильтрации трафика для различных пользователей и групп пользователей. Категории фильтрации могут пересекаться и иметь иерархическую структуру, при этом классифицируемый объект (web-страница) имеет многотемную природу относительно этого набора категорий. Например, некоторая новостная статья может одновременно принадлежать как к категории «новости», так и категориям «политика» и «терроризм» (рис. 1). В данной задаче время классификации запрашиваемых пользователями web-страниц является критичным и не должно вносить задержки в интерактивный режим работы конечных пользователей.
В задаче мониторинга документооборота пользователей и предотвращения утечек конфиденциальной информации необходимо определять категории документов, с которыми работают пользователи, и анализировать трафик пользователей с целью обнаружения и предотвращения доступа к конфиденциальным данным (таким как информация о корпоративных сетях, персональная информация пользователей и т.п.). Актуальность данной задачи обоснована тем, что порядка 45% внутренних угроз в организациях составляет нарушение конфиденциальности информации [57]. Набор конфиденциальных категорий определяется спецификой конкретной организации и политиками безопасности, а передаваемые документы являются многотемными относительно этих категорий (рис. 4). Производительность программных средств классификации при решении данной задачи также является критичной, поскольку конечные пользователи не должны замечать задержки, связанные с категоризацией и анализом передаваемых ими документов.
Набі
-1 О
эр категорий
Сообщение
секретный
особо секретный
кредиты
продажа оборудования
контракт
налоговый
данные о служащих
Рисунок 4. Задача предотвращения утечек конфиденциальной информации.
В задаче автоматизированного модерирования Интернет-ресурсов в качестве классифицируемых объектов выступают сообщения на дискуссионных форумах, досках объявлений, новостных порталах, редактируемых пользователями, и т.п. Каждое сообщение может одновременно затрагивать многие сферы интересов пользователей, и соответственно, может быть отнесено сразу к нескольким категориям. Определяя эти категории, можно, например, выявлять несоответствия сообщений определённым тематикам форума и перемещать сообщения в наиболее релевантные для них тематики, а также обнаруживать факты web-спама. Отметим, что требования к производительности средств классификации при решении данной задачи высоки, поскольку поступающие сообщения должны классифицироваться с такой скоростью, чтобы пользователи Интернет-ресурса при этом могли работать в интерактивном режиме.
Таким образом, во всех перечисленных задачах возникает необходимость решения задачи классификации, причем классифицируемый документ имеет многотемную природу, и для принятия решения необходимо знать набор всех классов, релевантных для документа. Существующие решения [43-50] для рассматриваемых приложений основаны на сведении их к совокупности задач традиционной (multi-class) классификации с последующим применением соответствующих методов. Настоящая работа посвящена исследованию использования методов классификации многотемных (multi-label) документов для решения обозначенных прикладных задач.
Для решения перечисленных прикладных задач требуется применение методов классификации на основе машинного обучения, поскольку состав и содержимое анализируемых документов постоянно изменяется, и одним из путей адаптации к этой динамике является использование таких методов. Цель методов машинного обучения для задачи классификации многотемных документов заключается в построении модели классификации на основе обучающего набора и применении построенной модели для предсказания набора классов, релевантных для нового документа [5] (рис. 5).
Рисунок 5. Классификация многотемных документов на основе машинного обучения.
Обучающий набор для рассматриваемой задачи классификации состоит из документов, каждому из которых сопоставлено множество релевантных классов (рис. 6). Под документами и классами в обозначенных приложениях будем подразумевать некоторые обобщённые понятия, которые различаются для разных прикладных задач. В качестве документов будут выступать web-страницы, электронные письма, сообщения на форумах, досках объявлений, новостных порталах и т.п.; в качестве классов - рубрики, тематики, категории.
Рисунок 6. Обучающий набор для задачи классификации многотемных документов. В рассматриваемых прикладных задачах обучающие наборы имеют достаточно большой размер, ввиду чего при решении этих задач необходимо применение методов классификации с возможностью дообучения без необходимости хранения обучающего набора {incremental learning, пошаговое обучение) [6,31,37]. При пошаговом обучении обучающие данные подаются алгоритму последовательно (по одному примеру на каждом шаге обучения), и на последующих шагах алгоритм использует только новые обучающие примеры. При традиционном пакетном обучении (batch learning), в отличие от
пошагового, для обучения алгоритма классификации весь обучающий набор должен быть задан целиком.
Возможность пошагового обучения может включать в себя различные сценарии функционирования, связанные как с уточнением модели классификации на новых обучающих примерах в рамках предопределённого набора тематик, так и с модификацией модели классификации при удалении существующих и добавлении новых тематик классификации с новыми обучающими примерами. Специфика перечисленных прикладных задач такова, что набор интересующих тематик классификации может динамически изменяться. Например, в задачах предотвращения утечек конфиденциальной информации и фильтрации Интрнет-трафика список запрещённых и разрешённых тематик может пополняться, в то время как некоторые из существующих тематик могут становиться неактуальными в процессе работы прикладной системы. В задаче категоризации электронной почты пользователь может создавать новые тематические папки и удалять существующие, и в этом случае необходимо, чтобы алгоритм классификации дообучался с учётом этих изменений. В задаче автоматизированного модерирования Интернет-ресурсов список категорий (форума, новостного портала и т.п.), как правило, изменяется со временем. Изменения набора категорий могут быть достаточно частыми и должны оперативно отражаться в модели классификации, чтобы анализ новых сообщений осуществлялся относительно наиболее актуального набора тематик. Поэтому важно, чтобы для учёта изменений набора тематик не приходилось заново обучать модель классификации.
Таким образом, актуальна разработка программных средств классификации многотемных документов, обеспечивающих следующие сценарии функционирования: обучение на основе обучающего набора, классификация документов, дообучение на новых документах без необходимости хранения предыдущего обучающего набора, добавление и удаление тематик классификации. Разрабатываемые программные средства должны удовлетворять требованиям к производительности, предъявляемым современными прикладными задачами. Качественной неформальной оценкой этих требований будем считать, что скорость классификация документов должна соответствовать интерактивному режиму работы пользователей. Следует отметить, что методы машинного обучения для классификации документов постоянно развиваются и совершенствуются, поэтому необходимо предусмотреть в архитектуре программных
средств классификации возможность расширяемости, т.е. возможность независимой замены отдельных компонентов и методов.
Ещё одной важной подзадачей при создании программных средств классификации является разработка модели представления электронных документов, поскольку для алгоритма классификации на основе машинного обучения выбор модели представления документов влияет на большинство важных критериев оценки алгоритма, таких как скорость обучения и классификации, точность, размер модели. Формальной моделью описания электронных документов, с которыми работают обозначенные прикладные задачи, является гипертекст. Гипертекстовая модель представления определяется ориентированным графом, в вершинах которого располагаются блоки содержательной информации [1-3]. Эти блоки имеют смысловую связь, фиксируемую дугами и ребрами графа. Благодаря этому гипертекст отличается от обычного линейного текста, который имеет последовательную структуру. Учёт гиперссылок в документе может позволить получить более точное (для классификации) представление, по сравнению с учётом только локального содержимого (контента) классифицируемого документа [16]. Однако при этом необходимо учитывать, что глубина выборки контента по гиперссылкам существенно влияет на скорость представления документов, а соответственно и на скорость классификации.
Итак, на сегодняшний день является актуальным проведение исследований и разработка программных средств, осуществляющих классификацию многотемных гипертекстовых документов на основе методов машинного обучения с возможностью дообучения и добавления (удаления) категорий классификации.
Постановка задачи: исследование и разработка методов и построение программных средств классификации многотемных гипертекстовых документов на основе методов машинного обучения с возможностью дообучения и добавления (удаления) категорий классификации.
Таким образом, разработанные программные средства классификации должны обеспечивать:
возможность пошагового дообучения и добавления (удаления) категорий классификации без необходимости хранения обучающего набора;
производительность классификации, не уступающую современному уровню разработок по данной проблеме.
Объектом исследования диссертационной работы является архитектура программных средств классификации многотемных гипертекстовых документов; алгоритмы классификации многотемных документов на основе машинного обучения; модели представления гипертекстовых документов.
Структура диссертации. Диссертация состоит из введения, четырёх глав, заключения и библиографии. Далее излагается краткое содержание работы.
Первая глава посвящена исследованию существующих методов классификации многотемных документов. В главе формализована постановка задачи классификации многотемных документов и содержится обзор существующих подходов и методов решения данной задачи. В обзоре показано, что обозначенным в постановке задачи требованиям удовлетворяет только подход на основе декомпозиции «каждый-против-оставльных» с применением дообучаемых нейросетевых алгоритмов для осуществления двуклассовой классификации, однако методы, основанные на таком подходе, как правило, обеспечивают невысокое качество классификации [6]. Показана актуальность задачи разработки методов классификации многотемных документов, с возможностью дообучения, возможностью динамического добавления и удаления тематик классификации и обеспечивающих высокое качество классификации, не уступающее современному уровню разработок по данной проблеме.
Вторая глава содержит описание предложенного решения задачи классификации многотемных документов на основе подхода попарных сравнений и результаты экспериментальной оценки характеристик предложенного решения. Предложенное решение включает, во-первых, новый алгоритм ранжирования, основанный на модифицированном для случая существенно пересекающихся классов методе попарных сравнений с помощью набора бинарных классификаторов и вычислении степеней принадлежности классам с использованием обобщенной модели Брэдли-Терри с «ничьей» [23]; во-вторых, новый алгоритм построения пороговой функции отсечения нерелевантных классов, строящий пороговую функцию не в исходном пространстве характеристик (как это делает большинство традиционных алгоритмов), а в пространстве релевантностей классов, что позволяет упростить вид пороговой функции, значительно сократить вычисления и в большинстве случаев увеличить точность.
Третья глава посвящена исследованию и разработке методов построения модели представления гипертекстовых документов. Глава состоит из обзора существующих
методов решения рассматриваемой задачи, описания предложенной модели представления гипертекстовых документов и результатов экспериментальной оценки характеристик предложенного решения. В обзоре показано, что существующие методы построения модели представления гипертекстовых документов имеют достаточно большую вычислительную сложность и не удовлетворяют требованиям интерактивного режима. Показана актуальность задача разработки более эффективной (по сравнению с существующими) модели представления гипертекстовых данных. Предложное решение для представления документов является расширением традиционной векторной модели представления. Разработанная модель учитывает базовые текстовые признаки (лексемы, если есть поддержка стемминга [13] для языка, или N-граммы [15] для морфологически сложных языков без стемминга), базовые нетекстовые признаки (идентификаторы классов гиперссылок) и составные признаки, являющиеся частыми комбинациями базовых. В главе также описан предложенный метод учёта ссылочной структуры гипертекстовых документов, основанный на использовании классификатора (при N-граммном представлении), применяемого для анализа самой структуры гиперссылки и не требующего загрузки содержимого документа, на который указывает гиперссылка.
Четвёртая глава посвящена описанию экспериментального программного модуля классификации многотемных гипертекстовых документов. Глава содержит описание архитектуры, сценариев функционирования и результаты экспериментального исследования производительности разработанного экспериментального программного модуля. Разработанная архитектура модуля состоит из трёх основных компонент: классификатор, компонент лексического анализа и компонент вычисления меры сходства. Модуль имеет четыре основных сценария функционирования: обучение, дообучение (с возможностью добавления новых тематик), классификация и удаление темы. Разработанное программное решение обладает свойствами масштабируемости и расширяемости.
Заключение содержит основные результаты диссертации.
Метод ML-kNN на основе алгоритма к-ближайших соседей и принципа максимизации апостериорных вероятностей
Метод Multi-Label-A:-NN (ML-kNN) [4] представляет собой подход multi-label-обучения, полученный на основе традиционного метода -ближайших соседей. А именно, для каждого примера сначала определяются его к ближайших соседей. После этого, в соответствии с наборами классов этих соседей, определяется набор релевантных для примера классов, используя принцип максимизации апостериорных вероятностей.
Введём обозначения. Зададим пример х и связанный с ним набор классов У сУ. Пусть у- -— вектор категорий для х, где его 1-я компонента д Д/) (/ є У ) имеет значение 1, если l Y-, и 0 — иначе. Кроме того, пусть N(x) — набор индексов к ближайших соседей документа х, определённых на обучающем наборе. Таким образом, основываясь на наборах классов этих соседей, вектор подсчёта членства может быть определён в следующем виде: аєЛГ(ї) где Сх (/) подсчитывает, как много соседей х принадлежат /-ому классу.
В методе ML-kNN для каждого тестового примера xtesl сначала определяются его к ближайших соседей N(xjest). Для этого для каждого примера х из обучающей выборки, находится расстояние до xlesl, которое выражается через косинус угла между векторами признаков: p(xtesl,x) = l-cos(xlest,x) . Далее из обучающей выборки выбираются к примеров, ближайших к xlesl.
Пусть Н[ — событие, что тестовый пример xlesl имеет метку /, а Н!0 — событие, что xlesl не имеет метки /. Кроме того, пусть Е (у Є {О,...,к}) обозначает событие, что среди к ближайших соседей примера xlest ровно у примеров имеют метку /. Поэтому, основываясь на векторе подсчёта членства С- , вектор категорий у-х определяется, используя принцип максимизации апостериорных вероятностей: у- (/) = argmaxР{Н[ \Е1-С ...), / є У . Х"«К іє{0,1} с:,аЛ! Используя формулу Байеса, связывающую апостериорную вероятность с априорной вероятностью, последнее соотношение может быть записано в следующем виде: Р(Н Ь)Р(Е 5_ \Н[) у, (/) = argmax = argmaxР(НІ)Р(ЕІ ІП\НІ). Заметим, что априорные вероятности Р{Н1Ь) (/ є У,be {0,1}) и апостериорные вероятности Р(Е1 Н1Ь) (J є {0,...,к}) могут быть оценены, используя обучающий набор Z.
Таким образом, в методе ML-kNN [4] для определения набора категорий, релевантных для тестового примера, используется принцип максимизации апостериорных вероятностей принадлежности примера к категориям. Этот метод имеет недостатки, свойственные методам, основанным на методе -ближайших соседей, - это большие вычислительные затраты на этапе классификации и большой объём памяти, необходимый для хранения и работы сразу со всем набором обучающих данных. Следовательно, для метода ML-kNN характерно долгое время классификации, он не имеет возможности дообучения и динамического добавления (удаления) категорий.
Метод, основанный на модели смешивания, обученной с помощью метода максимизации математического ожидания [9], для классификации многотемных документов основан на байесовском подходе, в котором определяется порождающая вероятностная модель, отражающая природу многотемного документа.
Порождающую вероятностную модель можно определить следующим образом. Пусть С = {с1,с2,...,сп} - набор классов. Каждый документ связывается с некоторым подмножеством этих классов, которое можно рассматривать как двоичный вектор с , задающий, какие классы принадлежат подмножеству. Совокупность всех подмножеств множества всех возможных классов обозначается С . С каждым конкретным классом с, связывается распределение слов P(wk\Cj) для всех слов из словаря V = {wl,w2,...,wN} . Задавая набор классов, каждый документ формируется, смешивая эти распределения слов с весами смешивания А (причём компоненты А , связанные с классами не из с , устанавливаются в ноль). Сами веса смешивания выбираются из распределения над весами смешивания, записанньми как Р(А с). Помеченные обучающие данные состоят из набора документов 2? = {dvd2,...,dm}. Вектор меток классов, связанный с документом dt, обозначается /..
Порождающий процесс для многотемного документа следующий. Сначала выбирается набор классов из распределения Р(с), которые будут метками для документа. Затем выбираются веса смешивания для выбранных классов в соответствии с Р(А \ с). Затем начинается формирование слов в документе. Сначала выбирается класс с в соответствии с весами смешивания в А (компоненты которого записываются как Ас и могут рассматриваться как Р(с А) ). Затем пусть этот класс формирует одно слово в соответствии с многомерным нормальным распределением слов P(wk\c) . Таким образом, вероятность документа определяется следующим образом: P(d) = ]dXP{l 15)П Z lp(w Ic)
Традиционный подход на основе попарных сравнений для взаимно исключающих классов
Данный раздел посвящен рассмотрению традиционного подхода попарных сравнений для решения задачи классификации, в которой каждый классифицируемый объект может принадлежать только к одному классу. Введём некоторые обозначения. Пусть задан обучающий набор z = {х,,у,}, є X у , который состоит из т классифицированных примеров , из некоторого множества X. Метки классов yt принадлежат некоторому множеству Y = {i,...,q], q 2. При детерминистической постановке задачи распознавания, алгоритм обучения использует обучающий набор Z для построения классификатора fz :Х -» . В вероятностной постановке цель алгоритма обучения - оценить распределение P(/z(x) = y\Z). Это означает, что для любого заданного х алгоритм вычисляет апостериорные вероятности классов: Жх) = {Ру(х)}%, Pj (х) = Р(у = j ] х), ffj (x) = l. (2 ,}
В традиционной multi-class проблеме сценарий применения подхода на основе попарных сравнений следующий. Сначала необходимо осуществить декомпозицию исходной задачи обучения с тренировочным набором Z в q(q-l)/2 бинарных подзадач - по одной подзадаче для каждой пары классов к и j. Каждая подзадача включает только примеры, помеченные к либо / Примеры, помеченные классом к, рассматриваются как "положительные" с меткой +1; примеры, помеченные классом j, - как "отрицательные" и помечаются -1. Цель состоит в том, чтобы для каждой подзадачи построить бинарный классификатор, разделяющий "отрицательные" и "положительные" примеры, то есть отделяющий класс к от класса j и игнорирующий все другие классы. Это идея иллюстрируется на рисунке 2.4.
Рисунок 2.4 Разделение взаимно исключающих классов. Примеры, лежащие на «неправильной» стороне разделяющей гиперплоскости, рассматриваются как исключения. При использовании вероятностного бинарного классификатора оцениваются отдельные вероятности: b(x)=P(fz&) k\xekKjfi (2.2) Так как классы j а к предполагаются взаимно исключающими, дополнительные вероятности определяются как: vw=i-%w 2-3
Таким образом, имеем q(q-l)/2 обученных классификаторов, которые оценивают вероятности (2.2) и (2.3) для любого заданного примера jr. Чтобы классифицировать новый пример х, используя подход попарных сравнений, необходимо применить все обученные классификаторы, оценить вероятности (2.2) и (2.3) и затем объединить их, чтобы получить результирующее предсказание. Для реализации этого было предложено много стратегий, включая четкие и нечёткие схемы голосования [19], теоретические игровые модели [20] и статистические модели [21]. Рассмотрим простейшую схему четкого голосования и статистический метод для оценки вероятностей классов (2.1), использующий модель Брэдли-Терри [21]. Схема четкого голосования работает следующим образом. Для заданного х и для всех к классов вычисляется функция голосования: vote, (x) = { j I j Ф к A rkJ (x) 0.5} (2-4)
Класс, получивший максимальное число голосов (2.4), присваивается примеру х. Хотя эта схема вычислительно эффективна, она имеет несколько существенных недостатков: она не является точной; она допускает неопределённости, когда несколько классов получают максимальное количество голосов; она не позволяет оценить вероятности классов (2.1).
Схема для оценки вероятностей в случае взаимоисключающих классов, основанная на модели Брэдли-Терри [9], не имеет таких недостатков. Модель Бредли-Терри для попарных сравнений позволяет оценивать «силу» отдельных команд на основе вероятностей исходов попарных соревнований команд. Эта модель применяется в спорте, машинном обучении, статистике. В рассматриваемой задаче ранжирования классов модель Бредли-Терри может быть использована для оценки вероятностей принадлежности документа классам. Эта оценка основывается на результатах попарных сравнений классов, которые выражаются через результаты бинарных классификаторов, и некотором предположении о взаимосвязи принадлежности документа классам и исходами попарных сравнений. Для базовой модели Бредли-Терри это предположение заключается в том, что вероятность того, что к-ая команда победиту -ую равна отношению «силы» к-ой команды к сумме «силы» Аг-ой и «силы»у -ой команд.
Таким образом, модель Бредли-Терри позволяет получить результирующие вероятности (2.1) на основе подхода попарных сравнений: P(kbeatsj) = pt/(pt+Pj), (2.5) где приближённые значения рк могут быть найдены как решение следующей оптимизационной задачи: ( Y -Z vg——+ Iog—— Д Pk+Pj Pk+Pj) я при условии Pj = l,Pj 0. mm р (2.6)
Для решения задачи (2.6) было разработано много эффективных итерационных алгоритмов [21,22,23].
Предложенный метод ранжирования на основе попарных сравнений для существенно пересекающихся классов
Рассмотрим теперь задачу ранжирования на основе попарных сравнений для случая существенно перекрывающихся классов. Следует отметить, что ранее подход попарных сравнений не давал позитивных результатов для задач многотемной классификации, поскольку не удавалось решить проблему декомпозиции - построить точный классификатор, разделяющий два существенно перекрывающихся (не взаимоисключающих) класса. «Наивный» подход сделать это заключается в прямом сведении этой задачи к случаю взаимоисключающих классов. Один из способов - просто исключить из рассмотрения (убрать из тренировочного набора) примеры из перекрывающейся области. Другой способ - рассмотрение примеров из перекрывающейся области как исключений (т.е. такие примеры остаются в тренировочном наборе как положительные примеры для всех классов, к которым они относятся). Однако оба способа не являются корректными и не показывают приемлемых результатов. Причина этого заключается в том, что перекрывающаяся область может быть наиболее важной областью одного или обоих классов. И если примеры из этой области рассматривать как исключения или игнорировать, структура классов, важная для алгоритма multi-label обучения, может быть потеряна.
Ввиду выше изложенного, в настоящей работе предлагается каждую пару возможно перекрывающихся (и даже вложенных) классов у и k разделять с помощью двух бинарных классификаторов, которые отделяют пересекающиеся и непересекающиеся области [70]. Используя эти классификаторы, можно выделить четыре области: область «только классами; область «только класса Ь ; «перекрывающаяся область» (/ и А); область, не принадлежащую «ни классу/ ни классу А» (рис.2.5).
Сравнение эффективности методов отсечения нерелевантных классов
Сравнение разработанного метода многотемной классификации проводилось с ведущими существующими методами, применимыми для решения задач текстовой классификации: Multi-class Multi-label Perceptron (ММР) [6] - метод ранжирования классов multi-label документов, основанный на алгоритме персептрона и пошаговой модификации весов для каждого обучающего документа; с пороговой функцией в пространстве релевантностей классов; AdaBoost.MH [7] - метод multi-label классификации, основанный на boosting-методах минимизации Hamming Loss; ML-KNN [4] - метод multi-label классификации, основанный на методе к ближайших соседей и принципе максимизации апостериорных вероятностей принадлежности объекта к классам; 1-vs-all-SVM [5] - метод multi-label классификации, основанный на декомпозиции multi-label проблемы в набор независимых бинарных проблем, в котором в качестве метода бинарной классификации применяется метод опорных векторов.
Результаты экспериментов приведены ниже в таблице 2.2. Для оценки достоверности результатов тестирования применялся k-раздельный парный t-тест перекрёстной проверки [27,35].
Значение, следующее за «±», показывает стандартное отклонение; наилучшие результаты по каждому критерию выделены жирным шрифтом. Для наглядности сравнения точности моделей представления вводится частичный порядок « » на множестве всех сравниваемых алгоритмов для каждого критерия оценки. То есть А1 А2 означает, что алгоритм А1 статистически лучше, чем алгоритм А2 для конкретного критерия (основываясь на к-раздельном парном t-тесте перекрёстной проверки). Частичный порядок для всех сравниваемых методов в терминах каждого критерия приведён в таблице 2.3.
Частичный порядок « » показывает только относительную разницу между алгоритмами А1 и А2 для конкретного критерия оценки. Однако, при этом возможна ситуация, что А1 показывает лучшие результаты, чем А2, по одному критерию, но худшие по другому. В этом случае трудно оценить, какой алгоритм действительно лучше. Поэтому для общей оценки производительности с каждым алгоритмом связывается значение, которое учитывает его относительную производительность по всем метрикам. А именно, для каждого критерия оценки, для каждой возможной пары алгоритмов А1 и А2, если выполнено А1 А2, то А1 получает положительную оценку «+1», а А2 получает «-1». Основываясь на совокупных результирующих значениях каждого алгоритма по всем критериям, определяется общий порядок «»» на наборе всех моделей, что показано в последней строке таблицы 2.3.
Как видно из таблиц 2.2 и 2.3, разработанный метод превосходит существующие по всем основным характеристикам точности, особенно по качеству ранжирования классов (Coverage и Ranking Loss).
Разработан новый метод решения задачи классификации многотемных документов на основе подхода попарных сравнений. Разработанный метод включает, во-первых, новый алгоритм ранжирования, основанный на модифицированном для случая существенно пересекающихся классов методе попарных сравнений с помощью набора бинарных классификаторов и вычисления степеней принадлежности классам с использованием обобщенной модели Брэдли-Терри с «ничьей»; во-вторых, новый алгоритм построения пороговой функции отсечения нерелевантных классов, строящий пороговую функцию не в исходном пространстве характеристик (как это делает большинство традиционных алгоритмов), а в пространстве релевантностей классов, что позволяет упростить вид пороговой функции, значительно сократить вычисления и в большинстве случаев увеличить точность. Как показали результаты экспериментальной оценки, на эталонном наборе тестовых данных Reuters-2000 разработанный метод классификации многотемных документов показал лучшее качество классификации, по сравнению с существующими методами, применимыми для решения задач текстовой классификации.
Глава посвящена исследованию и разработке методов построения модели представления гипертекстовых документов. Глава состоит из обзора существующих методов решения рассматриваемой задачи, описания предложенной модели представления гипертекстовых документов и результатов экспериментальной оценки характеристик предложенного решения. Разработанная модель представления гипертекстовых документов является расширением традиционного векторного представления документов. Она учитывает базовые текстовые признаки (лексемы, если есть поддержка стемминга для языка, или N-граммы для морфологически сложных языков без стемминга), базовые нетекстовые признаки (идентификаторы классов гиперссылок) и составные признаки, являющиеся частыми комбинациями базовых.
Второй ключевой подзадачей при разработке программных средств классификации многотемных гипертекстовых документов является разработка эффективной формальной модели представления гипертекстовой информации. Для алгоритма классификации на основе машинного обучения выбор модели представления документов является одной из наиболее важных задач. Это влияет на большинство важных критериев оценки алгоритма: скорость обучения и классификации, точность, размер модели.
Объекты классификации — гипертекстовые документы и их фрагменты — являются слабо структурированными разнородными данными. Большинство алгоритмов классификации работают с формальным описанием объектов, используя векторную модель представления документа. Для реализации этой модели необходимо, во-первых, выбрать пространство признаков, во-вторых, определить алгоритм вычисления весов. Алгоритм классификации определяет, каким темам из предопределённого набора тем принадлежит каждый документ на основе «сравнения» его содержания с содержанием документов, классификация которых известна. Решение этой задачи требует оценивать сходство содержания гипертекстовых документов.
Обзор методов построения модели представления гипертекстовых документов
Программные средства классификации многотемных гипертекстовых документов должны удовлетворять ряду специфических требований, предъявляемых как к алгоритму классификации и модели представления документов, так и к архитектуре и программной реализации выбранных алгоритмов.
Требования к алгоритму классификации и модели представления документов, главным образом, связаны с тем, что программные средства классификации должны обеспечивать определённые сценарии функционирования: обучение на основе обучающего набора, дообучение с возможностью добавления новых тематик, классификация и удаление темы. Все эти требования были достигнуты при разработке алгоритма классификации многотемных гипертекстовых документов.
Требования к архитектуре и программной реализации модуля связаны преимущественно с тем, что методы классификации многотемных документов достаточно ресурсоёмки, и одна из традиционных проблем применения этих методов на практике -это скорость классификации. Поэтому одним из требований к архитектуре разрабатываемого модуля является масштабируемость и возможность распараллеливания вычислений. Кроме того, методы классификации документов постоянно развиваются и совершенствуются, поэтому архитектура модуля должна обладать свойством расширяемости.
Как было сказано во введении, одним из наиболее критичных требований к реализации программных средств классификации является скорость классификации документов, удовлетворяющая интерактивному режиму работы пользователей. Для задачи анализа web-документов интерактивный режим работы можно определить следующей статистикой. По данным аналитических исследований приемлемым с точки зрения обычного пользователя временем загрузки страниц с web-сайта является интервал в 1.5-2 секунды [41]; по данным Keynote Systems 2008 (Keynote Business 40 Internet Performance Index) среднее время загрузки web-страниц составляет 2.33 секунды [42]. При этом необходимо учитывать, что запросы от пользователей могут приходить одновременно, и предусмотреть эффективную обработку параллельных запросов на классификацию.
Следующим требованием к разрабатываемым программным средствам классификации многотемных гипертекстовых документов является эффективное встраивание таких средств классификации в различные практические приложения. Для удовлетворения этому требованию необходимо обеспечить сценарии функционирования разрабатываемых средств, учитывая нацеленность на применение для широкого спектра прикладных задач. Важно отметить, что существующие программные решения рассматриваемой проблемы, главным образом, ориентированы на конкретные прикладные задачи [43-50] и не удовлетворяют обозначенным выше требованиям.
Следующие два требования к программной реализации связаны с необходимостью обеспечения сценария дообучения и добавления тематик классификации: во-первых, это возможность осуществления классификации новых документов параллельно с дообучением (добавлением темы), а во-вторых, оперативность выполнения самого дообучения и добавления новой тематики. Первое из этих требований связано с тем, что процесс дообучения или добавления темы может занимать достаточно много времени, а время ожидания запросов на классификацию критично, поэтому необходимо, чтобы во время дообучения поступающие запросы классифицировались на основе существующей модели, а как только дообученная модель будет готова, новые запросы уже работали с ней. Второе требование следует из необходимости классификации документов на основе наиболее актуальной версии модели классификации.
Разработан экспериментальный программный модуль классификации, отвечающий потребностям современных прикладных проблем и удовлетворяющий перечисленным выше требованиям к программной реализации. Разработанный модуль основывается на результатах проведённого исследования методов классификации многотемных документов и методов построения модели представления гипертекстовых данных. В качестве метода классификации многотемных гипертекстовых документов используется разработанный метод на основе попарных сравнений с помощью набора бинарных классификаторов, поскольку в проведённых экспериментах на эталонных наборах данных этот метод показал лучшие результаты по точности классификации. Разработанное алгоритмическое решение обеспечивает: классификацию многотемных гипертекстовых документов на основе обучающего набора; возможность дообучения - уточнения модели классификации на новых обучающих примерах в рамках существующего набора тематик (без необходимости хранения всего обучающего набора); возможность удаления существующих и добавления новых тематик классификации.
На рисунке 4.1 представлена архитектура разработанного модуля. Модуль классификации состоит из трёх основных компонент: компонент лексического анализа (парсер) — осуществляет разбор, выделение признаков и преобразование гипертекстовых документов во внутреннее представление; компонент вычисления меры сходства — определяет значения близости между документами (значения функции ядра) на основе выданного парсером представления и осуществляет кэширование этих значений; классификатор - строит дообучаемую модель классификации и на её основе осуществляет классификацию многотемных гипертекстовых документов.
