Содержание к диссертации
Введение
1. Постановка задачи 11
1.1. Формулировки задач классификации и распознавания образов 11
1.2. Методы оценки эффективности системы классификации текстов... 15
1.2.1. Определение меры эффективности классификации 17
1.2.2. Возможные виды меры эффективности классификации 19
1.2.3. Тестовые наборы 22
1.3. Анализ требований, предъявляемых к обучающим выборкам 23
1.4. Жизненный цикл системы автоматической классификации 25
2. Обзор методов распознавания образов и классификации 29
2.1. Основные группы методов распознавания и классификации 29
2.1.1. Предъявление обучающего множества 30
2.1.2. Варианты описаний объектов 31
2.1.3. Правила классификации 34
2.2. Математические модели для одноуровневых рубрикаторов 36
2.2.1. Классификаторы, основанные на правиле Байеса 37
2.2.2. Сжатие словаря терминов байесовского классификатора 41
2.2.3. Метод максимизации энтропии 42
2.2.4. Классификация методом поиска К-ближайших соседей (kNN) 48
2.2.5. Метод центроид 51
2.2.6. Нейронные сети 52
2.2.7. Ассоциативные сети 56
2.3. Математические модели для иерархических рубрикаторов 59
2.3.1. Метод вложенных классификаторов 59
2.3.2. Метод стягивания параметров классификатора 60
2.4. Учет гиперссылок 63
2.5. Сравнение методов классификации 69
3. Математическая модель автоматического классификатора текстовых документов 74
3.1. Математическая модель представления текстового документа 74
3.1.1. Выбор вида терминов 74
3.1.2. Выбор методы сопоставления терминов 76
3.1.3. Критерии выбора вида терминов и функции нормализации... 78
3.1.4. Алгоритм приближенного выделения словосочетаний 81
3.2. Математические модели для оценки значимости терминов 88
3.2.1. Собственная (морфологическая) значимость терминов 89
3.2.2. Контекстная значимость терминов 92
3.2.3. Статистическая значимость терминов 98
3.2.4. Вычисление значимости выделенных из текста дат, денежных сумм и т. д 101
3.3. Математическая модель документов и рубрик, метод классификации 102
3.3.1. Модель семантического образа рубрики 104
3.3.2. Модель классифицируемого документа 105
3.3.3. Метод классификации, основанный на полнотекстовом поиске 107
3.4. Математическая модель документов обучающей выборки, метод обучения 112
3.4.1. Формирование семантических образов рубрик одного уровня иерархии 116
3.4.2. Вычисление пороговых весов терминов и рубрик 119
3.5. Детальное описание алгоритма обучения классификатора 122
3.5.1. Структура базы данных системы автоматической классификации 122
3.5.2. Алгоритм обучения классификатора 126
3.5.3. Вычисление весов терминов 135
3.5.4. Формирование оптимального покрытия 136
3.5.5. Формирование семантических образов рубрик 138
3.6. Структура программного комплекса 145
4. Автоматическое выявление ассоциативных связей между словами и словосочетаниями 149
4.1. Метод построения ассоциативных связей 149
4.1.1. Виды ассоциаций 150
4.1.2. Автоматический показ ассоциативных запросов 150
4.1.3. Алгоритм формирования ассоциативных связей 151
4.2. Расширение семантических образов рубрик ассоциативными терминами 153
4.3. Дальнейшее развитие метода 157
5. Автоматическое распознавание текстовых метаконструкции 158
5.1. Структура системы распознавания 160
5.2. Алгоритм работы системы распознавания 163
5.2.1. Этапы обработки текста 163
5.2.2. Разбиение входного текста на фрагменты 166
5.2.3. Операции над распознанными конструкциями 166
5.2.4. Параметры, передаваемые процедурам обработки шаблонов 167
5.3. Алгоритм модификации очереди фрагментов шаблонами 168
5.4. Язык описания шаблонов 169
6. Результаты экспериментов 186
6.1. Описания тестовых наборов 189
6.2. Описание тестов и результаты 190
6.2.1. Влияние вида выделяемых из документа терминов на эффективность классификации 190
6.2.2. Вклад алгоритма сопоставления, использующего полнотекстовый поиск 193
6. 2.3. Вклад алгоритма расчета контекстной значимости 195
6.2.4. Эффективность классификации при увеличении объема обучающей выборки и ручной настройке 196
6.2.5. Использование ассоциативных связей для повышения качества классификации 198
6.2.6. Использование объектов для повышения качества классификации 199
6.2.7. Скорость обучения и классификации 200
6.3. Выводы 201
Заключение 202
Основные результаты 202
Направления дальнейшей работы 203
Литература 204
Приложения 215
- Возможные виды меры эффективности классификации
- Классификация методом поиска К-ближайших соседей (kNN)
- Математическая модель документов обучающей выборки, метод обучения
- Расширение семантических образов рубрик ассоциативными терминами
Введение к работе
С каждым годом увеличивается объем доступных пользователю массивов текстовой информации, и поэтому становится все более актуальной задача поиска необходимых пользователю документов в таких массивах. Для решения этой задачи часто применяются различные тематические классификаторы, рубрикаторы и т. д., которые позволяют искать (автоматически или вручную) документы в небольшом подмножестве документной базы, соответствующем интересующей пользователя тематике.
«Ручные классификаторы». Классификатор обычно представляет собой множество рубрик, объединенных в иерархию (рубрикатор). К каждой рубрике приписываются соответствующие ее тематике документы. Иерархия рубрик может являться деревом, однако возможны ситуации, когда некоторые рубрики являются дочерними сразу для нескольких родительских рубрик. Пример: «новости математики» может являться дочерней одновременно для рубрики «математика» и рубрики «новости науки».
Рис. В.1. Пример рубрикатора
У классификационного поиска имеется один существенный недостаток - документы, как правило, приходится классифицировать вручную. Другими словами, при добавлении в массив нового документа сначала нужно его проанализировать и определить, к каким рубрикам классификатора он относится (микропроцессорные системы, сотрудничество компьютерных фирм, изобразительное искусство средневековья и т.д.). И только после этого документ становится доступным для поиска по классификатору.
-7-Понятно, что при небольшом штате технических специалистов или
большом потоке входных документов применение ручной классификации
становится нереальным. Более того, обеспечить высокую полноту ручной
классификации большого объема документов оказывается очень сложно,
даже при помощи большого количества специалистов. Дело в том, что при
ручной классификации часто случается так, что документ, соответствующий
сразу нескольким рубрикам, оказывается приписан только части из них.
Обычно количество таких ошибок пропорционально размерности
рубрикатора.
Множества рубрик при ручной классификации очень трудно менять, так как любое изменение (например, выделение в рубрике история России подрубрик история СССР, и история древней Руси) приводит к необходимости повторного анализа всех документов данной рубрики и «соседних» рубрик иерархии.
Также следует отметить, что ошибки ручной классификации непрерывно накапливаются, и со временем усиливается потребность в полном пересмотре распределения документов по рубрикам.
Автоматическая классификация. Для решения указанных проблем используют программы классификации, которые автоматически выполняют отнесение документов к рубрикам. Для каждой рубрики такие программы хранят множества признаков, используя которые они могут принять решение, соответствует анализируемый документ рубрике, или нет. Множества признаков рубрики в тематическом рубрикаторе еще называют семантическими образами.
Чаще всего семантические образы рубрик составляет пользователь-эксперт. Однако, современные программы могут решать задачу автоматического обучения (распознавания образов), при которой эксперт приписывает к каждой рубрике некоторое количество эталонных документов, а программа сама выполняет их анализ и строит семантические образы.
Новые свойства. Использование программных средств автоматической
классификации позволяет получать динамичные, легко изменяющиеся рубрикаторы любого объема. Действительно, если программа способна обработать десятки или сотни мегабайт текстовой информации за несколько часов, появляется возможность быстро вносить изменения в иерархию рубрик, а также строить системы, обрабатывающие большие потоки текстов в режиме реального времени.
Кроме того, использование автоматических классификаторов позволяет повысить количество рубрик до тысяч и даже десятков тысяч, и упростить отнесение документа сразу к нескольким рубрикам.
Использование развитых программных систем классификации позволяет не только качественно структурировать уже накопленную информацию, но и получать новые знания. Например, анализируя семантические образы рубрик, тематика которых связана с политикой, можно составить список всех фамилий, связанных с соответствующим рубрике политическим явлением.
На рисунке В.2 показана последовательность операций, которые необходимо выполнить для того, чтобы расклассифицировать массив документов.
Сначала эксперты составляют рубрикатор и заносят его в программу. Затем из массива документов выбирается некоторая часть, которая классифицируется вручную, в результате чего к рубрикам приписываются эталонные документы. Дерево рубрик вместе с приписанными к нему эталонными документами называется обучающей выборкой. Затем запускается процедура обучения классификатора, которая формирует внутреннюю информацию, необходимую для последующей автоматической классификации.
После этого программа классификации готова к работе, можно подавать на ее вход документы для автоматической классификации. Иногда в
процессе эксплуатации программы может потребоваться коррекция и тонкая
настройка рубрик, а также дополнительное обучение.
Текстовая база
^
Тематическая
Обучение системы
Тонкая настройка
Администратор системы
Режим настройки классификатора
Основной поток документов
Автоматическая классификация
Работа автоматического классификатора
Рис. В.2. Сценарий использования классификатора
Автоматические классификаторы текстов могут быть полезны практически в любой системе, в которой для представления информации используются текстовые документы. Ниже перечислены несколько примеров использования классификатора.
Фильтрация и маршрутизация сообщений электронной почты
На адреса электронной почты больших компаний приходит несколько сотен или даже тысяч сообщений в сутки. Эти сообщения приходится сортировать, доставляя каждое из них в соответствующее подразделение. При этом необходимо гарантировать время ответа на письма, а также отсутствие потерь информации. Для решения этой задачи может использоваться автоматический классификатор, который настроен на дерево рубрик, отражающее иерархию подразделений в структуре компании. При получении очередного письма такая программа может самостоятельно
проанализировать тематику этого письма и направить его одно или
несколько соответствующих тематике подразделений. Разумеется, в случае, если расклассифицировать сообщение не удалось, оно попадает на ручную обработку.
Использование автоматического классификатора позволяет существенно уменьшить количество ручного труда, повысить оперативность обработки корреспонденции, а также обеспечить получение письма всеми заинтересованными лицами.
Уточнение результатов поиска в поисковой машине
Если все документы некоторого массива обработаны автоматическим классификатором и, следовательно, отнесены к рубрикам некоторого рубрикатора, то поисковый запрос может включать в себя не только список ключевых слов или фраз, которые должны содержаться в документах, но и имена рубрик. Так, например, пользователь может захотеть найти все документы, содержащие слово Волга в рубрике автомобили и ее подрубриках. При этом из результатов поиска будут удалены документы, в которых речь идет, например, о нересте осетровых в устье Волги.
Системы такого типа сейчас активно разрабатываются [42].
Автоматический учет интересов пользователей сети Интернет при показе рекламы (тематическое таргетирование)
Пользователи сети Интернет постепенно привыкают не обращать внимания на рекламные блоки, размещенные на страницах сайтов. Обусловлено это в первую очередь тем, что большая часть рекламных сообщений выдается «не по делу» - без учета того, действительно пользователь заинтересуется таким сообщением, или нет. Эффективность данного вида рекламы оказывается невысокой. Естественный путь повышения эффективности -показ пользователю только тех рекламных блоков, которые действительно могут его заинтересовать.
Если определить сферы интересов каждого из пользователей, отобразив их в иерархический рубрикатор, и расклассифицировать рекламные блоки по рубрикам этого же рубрикатора, то можно показывать пользователям только те блоки, которые входят в сферу их интересов. Для того чтобы это сделать, достаточно интегрировать автоматический классификатор со счетчиком Интернет (например, со счетчиком topi 00). Каждый раз, когда пользователь заходит на web-страницу, на которой помещен код такого счетчик, на специальном сервере запускается анализатор тематики этой страницы, который пополняет список тематик, составляющих сферу интересов этого пользователя. Такие списки регулярно передаются в систему показа рекламных блоков и используются там для проведения точных, адресных рекламных кампаний.
Возможные виды меры эффективности классификации
Каждый из ученых, занимавшихся разработкой систем классификации текстов, обязательно дает оценки качества работы своей системы. Так как ни одна современная математическая модель не может адекватно описать все явления естественного языка (синтаксис, семантику и т. д.), эффективность работы классифицирующей системы обычно определяют экспериментально, путем обработки некоторых тестовых наборов и сопоставления результатов обработки с результатами работы экспертов.
Часто исследователи сравнивают эффективность работы своих программ и чужих, построенных на каких-либо других идеях и алгоритмах. При этом зачастую оказывается, что разработанная каждым из авторов система работает лучше, чем все остальные. Это может быть связано с несколькими причинами: Используются разные наборы документов и рубрик. Очевидно, что на одних наборах классификатор может работать лучше, чем на других. Для одних и тех же алгоритмов используются разные настроечные параметры. Так, например, многие алгоритмы позволяют задавать приоритет полноты над точностью или наоборот, точности над полнотой. Нет возможности вести обработку тестовых данных одинаково для всех методов. Например, метод kNN требует настолько большого количества вычислений, что необходимо прореживание терминов или даже сокращение объема обучающей выборки [78]. Оценка результатов классификации зачастую субъективна - то, что одному эксперту кажется правильным, для другого может казаться спорным или даже неверным. Различные меры эффективности их обоснование и сравнение даны в [26, 27, 46]. В работе [69] предложен универсальный подход к оценке эффективности и разработан соответствующий математический аппарат. Существуют системы для автоматической оценки эффективности программ классификации, которые в пакетном режиме выполняют обработку одного и того же набора тестовых документов несколькими различными методами, сравнивают результаты с экспертными оценками и вычисляют показатели эффективности. При этом один и тот же метод классификации может быть протестирован многократно с разными значениями настроечных параметров. Одна из таких систем описана в [76]. В работах [78, 95] приведены результаты экспериментов, в которых сравниваются современные методы классификации на одних и тех же наборах документов. Перед исследователями систем обработки текстов стоит задача сравнения различных методов, выбора среди них лучшего для данных условий и его тонкой настройки. Говоря математическим языком, выполняется поиск оптимального решения задачи. Для того, чтобы вести такой поиск, нужна численная мера того, насколько эффективно работает система. Купер (Cooper) сформулировал следующий принцип (стратегию) оптимизации систем обработки информации [46]: Принцип 1 (The Probability Ranking Principle, PRP): Если ответы системы упорядочены по убыванию вероятности полезности для пользователя, причем эти вероятности оценены настолько точно, насколько это возможно с использованием данных, доступных системе, то эффективность такой системы максимальна по сравнению со всеми другими, располагающими этой же информацией. Понятно, что использовать его в «чистом виде» на практике не получается. Более того, не все используемые на практике меры эффективности согласуются с этим принципом. Пусть мы имеем некоторую меру эффективности #(S\Z )f где S -результаты работы классифицирующей системы, a Z - экспертные оценки, с которыми мы эти результаты будем сравнивать [68, 69]. Так как разные эксперты могут классифицировать документы по разному, причем среди всех документов, которые эксперты отнесли к рубрике, есть те, которые бесспорно ей соответствуют и те, которые соответствуют не вполне (например, лишь часть документа посвящена данной тематике), Z можно представить в виде множества случайных величин Z,7 (вероятность соответствия документа dt рубрике гу), каждая из которых имеет некоторое распределение /7,,. А вот результаты работы классифицирующей системы наоборот, определяются исключительно алгоритмом, обучающими выборками, текстами документов и настроечными параметрами, и поэтому случайными величинами не являются1.
Таким образом, перед нами стоят следующие задачи: выбор меры эффективности и нахождение эффективных способов ее вычисления для заданных Z. Затем, имея меру эффективности, мы можем выбрать оптимальный метод классификации или настроить параметры имеющегося метода так, чтобы значение меры было максимальным.
В общем виде решать такую задачу очень сложно, поэтому рассмотрим частный случай - бинарный классификатор. В этом случае Zjt принимают значения 1 (документ соответствует рубрике) с вероятностью р и значение Zji = О (документ не соответствует рубрике) с вероятностью 1 - Pj(. Предположим также, что величины 2},- независимы. S представляет собой множество {Sji}, где Sji = 1, если система классификации решила, что документ dt соответствует рубрике г,, и Sji = 0 в противном случае.
Классификация методом поиска К-ближайших соседей (kNN)
Вторым параметром, определяющим возможные задачи распознавания образов, являются способы описаний самих объектов. В большинстве задач классификации объект можно считать набором результатов измерений. Какова природа этих измерений и что значит их природа для процедур классификации и распознавания? Эти вопросы не совсем тривиальны.
Например, в большинстве изучаемых случаев (особенно в статистике) считается, что измерения определяют евклидово пространство описаний. И каждый объект представляется точкой в этом пространстве. Это позволяет комбинировать измерения, чтобы определить для каждого класса местоположение «типичной» точки в пространстве описаний. Такая процедура хорошо работает для задач измерения и группирования физических объектов. В других случаях нет разумной интерпретации расстояния. Например, так было бы в случае, если бы основными измерениями были определяющие признаки, выражаемые такими величинами, как пол, место рождения и раса. Иными словами, описание объекта — это список признаков, а не набор измерений. В любом случае объект можно представить в виде вектора описания; правда, имеющие смысл математические операции с такими векторами будут совершенно другими.
Структурные описания дают другой интересный способ описания объектов. Грубо говоря, структурное описание выделяет взаимоотношения между компонентами объекта, а не характеристики объекта, получаемые в серии измерений [30,27]. Примером структурного описания может быть синтаксическое дерево предложения на естественном языке.
Для обработки текстовой информации обычно применяют 2 последних варианта описаний, причем каждый из них обладает своими достоинствами и недостатками. Использование первого способа описаний - векторов евклидовою пространства предполагает наличие некоторой симметричной меры смысловой близости между двумя документами, которая бы не только задавала отношение порядка (документ dt ближе по смыслу к документу dj, чем документ dk), но и могла быть использована как абсолютная мера расстояния, удовлетворяющая требованиям аксиомы треугольника. Действительно, при получении такой меры можно применить к задаче классификации тестов развитый математический аппарат, позволяющий получить алгоритмы с известными (или предсказуемыми) характеристиками.
Однако трудность построения метрик, адекватно отражающих смысловую близость в условиях реальных массивов текстовой информации, сводит на нет все преимущества способа. Хороших результатов классификации документов, представленных данным способом, удалось достичь при помощи метода SVM.
Второй вариант (списки признаков) обычно оперирует векторами терминов (чаще всего - слов), выделенных из текста документов [15, 28, 92, 97]. Документ в таком случае представляется точкой в N-мерном лексическом пространстве, где N —общее число всех терминов в документной базе (размерность словаря). В простейшем случае информационный вектор документа содержит 1 по всем координатам, соответствующим терминам, которые в нем присутствуют, и 0 — по всем остальным координатам. Достоинством таких моделей является простота вычислений, недостатком - малая точность. В более сложных моделях в качестве величины координаты используется число, характеризующее смысловую значимость термина в документе.
Структурные модели документов, в которых документы представлены описаниями своей синтаксической, или даже семантической структуры [28] позволяют достичь исключительно высоких показателей точности распознавания образов и классификации. Так, например, выделение в тексте понятий позволяет почти безошибочно определять его тематику. Однако в условиях реальных текстов, с присущей им многозначностью, использовании структурных моделей возникают серьезные проблемы, уже начиная с синтаксического анализа, требующего применения запредельно сложных, громоздких структур данных, таких как таблицы глагольного управления, матрицы инцидентности слов и т. п.
Одним из шагов в сторону перехода от пространств описаний к структурным моделям заключается в учете ссылочной составляющей текстов (гиперссылок, цитат, списков литературы и т. д.) [43,44, 62, 65].
Сравнение, проведенное в [43, 58, 72] показывает, что среди универсальных не требующих сложных семантических структур, представлений наиболее эффективны гибридные структуры описания документов, при которых используются взвешенные векторы терминов в лексическом пространстве. При этом для повышения качества классификации необходимо учитывать как можно больше разных явлений в тестах - частоту встречаемости терминов, их взаимосвязь и правила изменения, а также использовать составные термины (словосочетания или даже фразы). Настоящая диссертационная работа главным образом посвящена именно построению простой модели представления текстов, хорошо отражающей их семантику.
В качестве терминов в разработанной автором модели используются словосочетания, извлеченные из текста при помощи процедур приблизительного, упрощенного синтаксического и/или статистического анализа, что позволяет выделять из текста устойчивые словосочетания, которые являются более точными носителями тематики по сравнению с отдельными словами. Выделение словосочетаний обеспечивает более высокие показатели точности процедуры классификации. Пример: наличие в документе словосочетания «условная вероятность» позволяет с большей степенью уверенности делать заключение о принадлежности данного документа рубрике «теория вероятности», чем наличие в том же документе отдельных слов «условный» и «вероятность».
Математическая модель документов обучающей выборки, метод обучения
На рисунке изображена трехслойная сеть, в которой нейроны располагаются во втором (скрытом) и третьем (выходном) слое. Первый слой только передает сигналы всем нейронам второго слоя. Каждый из четырех нейронов второго слоя имеет п=Ъ входов, которым приписаны веса wn...win (для нейрона с номером і). Получив входные сигналы, нейрон суммирует их с соответствующими весами, затем применяет к этой сумме некоторую передаточную функцию и пересылает результат на один из входов нейрона третьего слоя. В свою очередь, нейрон выходного слоя суммирует полученные от нейронов второго слоя сигналы с некоторыми весами V/.
Таким образом, данная сеть эквивалентна системе нелинейных уравнений. В [9] исследованы различные виды нейронов, их передаточных функций и конфигурации нейронных сетей, а также обучения таких сетей. Фактически обучение сети сводится к подаче на ее входы специально подобранных сигналов, для которых заранее известен результат работы сети, и корректировке коэффициентов каждого из нейронов сети таким образом, чтобы сеть выдавала именно это значение.
Нейронные сети могут применяться для классификации текстов [53, 98]. В простейшем случае документы обучающей выборки трансформируются в лексические вектора (при этом формируется словарь), затем каждому слову словаря присваивается порядковый номер и строится сеть с количеством входов, равным размерности словаря и выходов, равным количеству рубрик (в другом варианте строится по одной нейронной сети на каждую из рубрик). Далее документы обучающей выборки последовательно поступают на вход сети, и выполняется ее обучение.
Классификация выполняется аналогично — документы преобразуются в лексические вектора с использованием словаря, построенного на этапе обучения (таким образом, все термины, которых не было в обучающей выборке, из рассмотрения удаляются), а затем эти вектора поступают на вход сети. На выходе сети выдаются номера рубрик, которым соответствует документ. Нейросетевые классификаторы обладают следующими достоинствами: Учет терминов произвольной природы (слов, словосочетаний, метаконструкций, гиперссылок и т. д.). Неявный учет взаимосвязи терминов (например, ассоциативных связей, отношения род/вид и. т. д.). Потенциально высокая эффективность сети — если взять сеть с большим количеством нейронов и слоев, потратить вычислительные ресурсы на ее обучение, то можно ожидать высоких показателей эффективности. В частности, на большинстве тестов в [95] нейросетевые классификаторы были в числе лидеров по эффективности. Однако данному классу алгоритмов присущи и недостатки: Высокая вычислительная сложность — обучение и использование большой нейросети требует большого количества памяти и вычислений. Низкая устойчивость к шуму в обучающей выборке и неспособность нейросетевых алгоритмов работать «в чистом виде» с большими иерархиями рубрик (несколько тысяч рубрик, сотни тысяч документов в обучающей выборке). В работах [53, 95,98] показано, что при увеличении размерности задачи получение приемлемых по качеству результатов возможно только после предварительной фильтрации лексических векторов, уменьшающей их размерность. Для преодоления этих недостатков в работах [53, 91] предлагается применить латентное семантическое индексирование (LSI), при котором лексическое пространство документов сжимается до некоторой приемлемой с точки зрения размерности нейронной сети размерности. Метод LSI заключается в построении прямоугольной сингулярной матрицы, умножение которой на лексический вектор приводит к сокращению его размерности с небольшими потерями в способности нового вектора отражать семантику документа. Данное преобразование «склеивает» размерности лексического пространства, соответствующие словам, которые часто встречаются совместно (и редко порознь). В работе [98] предлагается другой метод предварительной обработки представлений документов, основанный на фильтрации с использованием элементов теории информации и метода различительных сил [27]. Во время обучения классификатора из всех терминов, присутствующих хотя бы в одном документе обучающей выборки, удаляются стоп-слова, а также термины, имеющие малые значения различительной силы. В результате такой фильтрации происходит сжатие пространства лексических векторов до размерностей, пригодных для обработки нейронными сетями.
Одним из близких по применяемому математическому аппарату методов является SOM {Self-Organizing Map) - метод кластеризации объектов, представленных в виде векторов, с последующим представлением в пространстве меньшей размерности (обычно 2, т.е. на плоскости). Применяется для наглядного представления любых данных, описываемых в виде векторов, в том числе для представления документов. На документы накладывается ограничение по размеру (они не должны быть слишком большими). Большие документы рекомендуется разбивать на несколько частей и рассматривать их в качестве отдельных документов.
Метод SOM разработан Кохоненом (Teuvo Kohonen) в начале 80-х годов [63]. Первоначально использовался для анализа числовых данных, но затем был применен и для обработки документов. Этот достаточно универсальный метод. Помимо автоматической классификации он применяется для решения следующих задач текстовой обработки [61]: поиск информации; автоматическое построение синонимических отношений между словами по сходству их контекстного окружения; автоматическое различение значений многозначных слов. Например, для слова ключ определяются 3 группы ассоциативных слов, уточняющих смысл этого слова: источник воды; устройство для открытия замка; что-то, обеспечившее успех решения некоторой задачи.
Расширение семантических образов рубрик ассоциативными терминами
Алгоритм формирования ассоциаций построен на следующем предположении: запросы, поданные одним и тем же пользователем в течение короткого промежутка времени, скорее всего, имеют одну и ту же тематику. Поэтому если большое количество пользователей, дав запрос х, сразу после этого дает еще и запрос у, можно сделать вывод о том, что запросы л: и у между собой связаны.
Для формирования ассоциаций используются протоколы работы web-сервера поисковой машины. В протоколах есть данные о времени обращения, сетевом адресе пользователя (IP), уникальном идентификаторе пользователя и, конечно же, информация о самом запросе к поисковой машине. Уникальный идентификатор пользователя — строка, которая хранится на компьютере этого пользователя в области так называемых cookie. Строка формируется в момент, когда пользователь впервые попадает на любую web-страницу Рамблера и с этого момента меняется очень редко.
На первом этапе построения ассоциаций протоколы работы web-сервера обрабатываются специальной программой, которая строит списки запросов, поданные каждым пользователем. Для каждого запроса запоминается время, в которое он был подан и количество найденной информации. Запросы, поданные одним и тем же пользователем с интервалом не более 1.5 часа, объединяются в группы. Все пары запросов из таких групп считаются кандидатами на ассоциации. Затем выполняется объединение групп и подсчет частот употребления пар запросов. При этом пара запросов, поданная одним пользователем, учитывается только один раз (не важно, как часто этот пользователь подавал эти запросы). Программа группировки получает на входе множество троек вида: (х, у, fxy), где х и у — запросы, э./ — количество пользователей, подавших данную пару запросов (частота совместной встречаемости). В процессе группировки для каждого запроса , все тройки вида (х,уъ/xyi), (х г,/ превращаются в список ассоциаций запроса де: assoc(Ar) = {(y,,f,)}. Для каждой ассоциации сохраняется ее частота. Полученные списки ассоциаций могут быть использованы для различного рода исследований аудитории Интернет. Однако, они непригодны для показа пользователям поисковой машины или для классификации. Дело в том, что очень большое количество пользователей дает запросы sex, porno, рефераты, Москва, знакомства. Получается, что в списке ассоциаций практически любого запроса в большом количестве присутствуют эти слова. Для того чтобы их подавить, выполняется специальное ранжирование ассоциаций. Делается это следующим образом: Для каждого запроса х, имеющего список из п ассоциаций {(у,,/,)}, i=\...n, гдеУІ — ассоциативный запрос, - количество пользователей, которые искали одновременно дси в течение 1.5 часов, вычислим ранги элементов списка ассоциаций и отсортируем элементы по убыванию веса. Ранги определяются следующим образом: мера похожести списков ассоциаций запроса х и списка ассоциаций запроса уі (косинусообразный коэффициент корреляции); W{yi) - функция от числа слов в запросе yh дающая небольшой приоритет запросам из двух или трех слов и уменьшающая ранг длинных запросов; Z(x, уі) - функция, повышающая вес ассоциациям, текст которых целиком включает в себя запрос JC; а,р - постоянные коэффициенты. Мера похожести между списками ассоциаций {а/ , /1} и {bj , ft } определяется следующим образом: Благодаря учету степени похожести в каждом списке ассоциаций вверху оказываются те запросы, в списке ассоциаций которых присутствует много запросов анализируемого списка. Это означает, что слова реферат, Москва и др. получают высокий вес только в списках ассоциаций подобных слов. 4.2. Расширение семантических образов рубрик ассоциативными терминами В системе классификации, основанной на механизмах полнотекстового поиска, внедрить учет ассоциаций оказывается достаточно просто. В самом деле, если признаками рубрик являются списки поисковых запросов с вычисленными алгоритмом CalculateBounds (см. главу III, стр. 119) значениями поискового веса, то достаточно выбрать «правильные» ассоциативно связанные термины, добавить их в семантические образы рубрик и пересчитать пороговые значения весов. При этом полнота классификации увеличивается за счет увеличения количества терминов, а точность - за счет учета в вычислении меры подобия документа рубрике количества терминов, которые нашлись в тексте документа. Дообучение классификатора с учетом ассоциативных связей выполняется в три этапа: 1) расширение семантических образов рубрик ассоциативно связанными терминами; 2) вычисление различительных сил для всех добавленных терминов, фильтрация терминов с низкой различительной силой. 3) повторный запуск модуля обучения классификатора, вычисление пороговых значений поискового веса терминов, порогового значения меры подобия документа рубрике. Пусть мы имеем для каждого термина (поискового запроса) tk є V множество ассоциативно связанных с ним запросов: Расширим словарь V ассоциативными терминами: где A — некоторая константа — пороговое значение веса связи. Теперь мы можем построить списки терминов, которыми предполагается расширить семантические образы рубрик: Vrt є R = Bassoon) = {ti є V : 3 tk є в(г,) : tt,rank(tk,t,) eassoc( ) л Ц «Ё в(г,)} Использование в качестве семантического образа рубрики множества вігі) U Oassodr,) вместо множества 0(г,) не всегда приводит к повышению качества классификации из-за наличия в списках assoc неточных ассоциаций и многозначности терминов. Пусть, например, в списке признаков рубрики металлообработка есть термин пресс. Список ассоциаций термина (поискового запроса) пресс содержит слова грудь, бицепс, трицепс. Очевидно, что если мы добавим эти слова в семантический образ рубрики металлообработка, точность классификации сильно уменьшится. Для того, чтобы этого избежать, необходимо провести дополнительную фильтрацию МНОЖеСТВ 0assoc(rt) Использовать для фильтрации метод различительных сил затруднительно, поскольку термины из 0asSoc(f"d отсутствуют во внутреннем представлении документов обучающей выборки. Поэтому применять выражения 3.32 или 3.34 (см. главу III, стр. 117) напрямую невозможно. Модифицируем выражение 3.34 с использованием полнотекстового поиска по документам обучающей выборки. Построим для этого инвертированный индекс по всем документам обучающей выборки:
Похожие диссертации на Модели и методы автоматической классификации текстовых документов
