-6-Введение
С каждым годом увеличивается объем доступных пользователю массивов текстовой информации, и поэтому становится все более актуальной задача поиска необходимых пользователю документов в таких массивах. Для решения этой задачи часто применяются различные тематические классификаторы, рубрикаторы и т. д., которые позволяют искать (автоматически или вручную) документы в небольшом подмножестве документной базы, соответствующем интересующей пользователя тематике.
«Ручные классификаторы». Классификатор обычно представляет собой множество рубрик, объединенных в иерархию (рубрикатор). К каждой рубрике приписываются соответствующие ее тематике документы. Иерархия рубрик может являться деревом, однако возможны ситуации, когда некоторые рубрики являются дочерними сразу для нескольких родительских рубрик. Пример: «новости математики» может являться дочерней одновременно для рубрики «математика» и рубрики «новости науки».
[ .ориеаая рубрми
железнодорожный I I авиация и «имонавтика
транспорт
легковые
ишенной проходимости 1
J
специа/ъныв
J
Рис. В.1. Пример рубрикатора
У классификационного поиска имеется один существенный недостаток - документы, как правило, приходится классифицировать вручную. Другими словами, при добавлении в массив нового документа сначала нужно его проанализировать и определить, к каким рубрикам классификатора он относится (микропроцессорные системы, сотрудничество компьютерных фирм, изобразительное искусство средневековья и т.д.). И только после этого документ становится доступным для поиска по классификатору.
-7-Понятно, что при небольшом штате технических специалистов или
большом потоке входных документов применение ручной классификации становится нереальным. Более того, обеспечить высокую полноту ручной классификации большого объема документов оказывается очень сложно, даже при помощи большого количества специалистов. Дело в том, что при ручной классификации часто случается так, что документ, соответствующий сразу нескольким рубрикам, оказывается приписан только части из них. Обычно количество таких ошибок пропорционально размерности рубрикатора.
Множества рубрик при ручной классификации очень трудно менять, так как любое изменение (например, выделение в рубрике история России подрубрик история СССР, и история древней Руси) приводит к необходимости повторного анализа всех документов данной рубрики и «соседних» рубрик иерархии.
Также следует отметить, что ошибки ручной классификации непрерывно накапливаются, и со временем усиливается потребность в полном пересмотре распределения документов по рубрикам.
Автоматическая классификация. Для решения указанных проблем используют программы классификации, которые автоматически выполняют отнесение документов к рубрикам. Для каждой рубрики такие программы хранят множества признаков, используя которые они могут принять решение, соответствует анализируемый документ рубрике, или нет. Множества признаков рубрики в тематическом рубрикаторе еще называют семантическими образами.
Чаще всего семантические образы рубрик составляет пользователь-эксперт. Однако, современные программы могут решать задачу автоматического обучения (распознавания образов), при которой эксперт приписывает к каждой рубрике некоторое количество эталонных документов, а программа сама выполняет их анализ и строит семантические образы.
_ о_
Новые свойства. Использование программных средств автоматической классификации позволяет получать динамичные, легко изменяющиеся рубрикаторы любого объема. Действительно, если программа способна обработать десятки или сотни мегабайт текстовой информации за несколько часов, появляется возможность быстро вносить изменения в иерархию рубрик, а также строить системы, обрабатывающие большие потоки текстов в режиме реального времени.
Кроме того, использование автоматических классификаторов позволяет повысить количество рубрик до тысяч и даже десятков тысяч, и упростить отнесение документа сразу к нескольким рубрикам.
Использование развитых программных систем классификации позволяет не только качественно структурировать уже накопленную информацию, но и получать новые знания. Например, анализируя семантические образы рубрик, тематика которых связана с политикой, можно составить список всех фамилий, связанных с соответствующим рубрике политическим явлением.
На рисунке В.2 показана последовательность операций, которые необходимо выполнить для того, чтобы расклассифицировать массив документов.
Сначала эксперты составляют рубрикатор и заносят его в программу. Затем из массива документов выбирается некоторая часть, которая классифицируется вручную, в результате чего к рубрикам приписываются эталонные документы. Дерево рубрик вместе с приписанными к нему эталонными документами называется обучающей выборкой. Затем запускается процедура обучения классификатора, которая формирует внутреннюю информацию, необходимую для последующей автоматической классификации.
После этого программа классификации готова к работе, можно подавать на ее вход документы для автоматической классификации. Иногда в
-9-
процессе эксплуатации программы может потребоваться коррекция и тонкая
настройка рубрик, а также дополнительное обучение.
Текстовая база
Тематическая структура fc
Создание тематического дерева рубрик
Обучающие документы
Добавление обучающих документов
Обучение системы
Администратор системы
Тонкая настройка
Режим настройки классификатора
Основной поток документов
Автоматическая классификация
Работа автоматического классификатора
Рис. В.2. Сценарий использования классификатора
Автоматические классификаторы текстов могут быть полезны практически в любой системе, в которой для представления информации используются текстовые документы. Ниже перечислены несколько примеров использования классификатора.
Фильтрация и маршрутизация сообщений электронной почты
На адреса электронной почты больших компаний приходит несколько сотен или даже тысяч сообщений в сутки. Эти сообщения приходится сортировать, доставляя каждое из них в соответствующее подразделение. При этом необходимо гарантировать время ответа на письма, а также отсутствие потерь информации. Для решения этой задачи может использоваться автоматический классификатор, который настроен на дерево рубрик, отражающее иерархию подразделений в структуре компании. При получении очередного письма такая программа может самостоятельно
-10-
проанализировать тематику этого письма и направить его одно или
несколько соответствующих тематике подразделений. Разумеется, в случае, если расклассифицировать сообщение не удалось, оно попадает на ручную обработку.
Использование автоматического классификатора позволяет существенно уменьшить количество ручного труда, повысить оперативность обработки корреспонденции, а также обеспечить получение письма всеми заинтересованными лицами.
Уточнение результатов поиска в поисковой машине
Если все документы некоторого массива обработаны автоматическим классификатором и, следовательно, отнесены к рубрикам некоторого рубрикатора, то поисковый запрос может включать в себя не только список ключевых слов или фраз, которые должны содержаться в документах, но и имена рубрик. Так, например, пользователь может захотеть найти все документы, содержащие слово Волга в рубрике автомобили и ее подрубриках. При этом из результатов поиска будут удалены документы, в которых речь идет, например, о нересте осетровых в устье Волги.
Системы такого типа сейчас активно разрабатываются [42].
Автоматический учет интересов пользователей сети Интернет при показе рекламы (тематическое таргетирование)
Пользователи сети Интернет постепенно привыкают не обращать внимания на рекламные блоки, размещенные на страницах сайтов. Обусловлено это в первую очередь тем, что большая часть рекламных сообщений выдается «не по делу» - без учета того, действительно пользователь заинтересуется таким сообщением, или нет. Эффективность данного вида рекламы оказывается невысокой. Естественный путь повышения эффективности -показ пользователю только тех рекламных блоков, которые действительно могут его заинтересовать.
-11-
Если определить сферы интересов каждого из пользователей, отобразив их в иерархический рубрикатор, и расклассифицировать рекламные блоки по рубрикам этого же рубрикатора, то можно показывать пользователям только те блоки, которые входят в сферу их интересов. Для того чтобы это сделать, достаточно интегрировать автоматический классификатор со счетчиком Интернет (например, со счетчиком topi 00). Каждый раз, когда пользователь заходит на web-страницу, на которой помещен код такого счетчик, на специальном сервере запускается анализатор тематики этой страницы, который пополняет список тематик, составляющих сферу интересов этого пользователя. Такие списки регулярно передаются в систему показа рекламных блоков и используются там для проведения точных, адресных рекламных кампаний.
1. Постановка задачи
1.1. Формулировки задач классификации и распознавания образов
Задачу классификации сформулируем следующим образом [30]: Пусть существует известное множество С— {с/}, / = l..JVc, состоящее из Nc классов объектов. Каждый объект представляется набором результатов измерений, называемым его описанием. Одно изменение — это точка на некоторой шкале, а шкалы в свою очередь, определяют пространство описаний Ф. Отметим, что два разных объекта могут иметь одинаковые описания, но находиться в разных классах.
Процедурой классификации образов называется процедура, относящая объект к классу ct е С тогда и только тогда, когда его описание попадает в область Ф/ пространства Ф, соответствующую этому классу. Такая процедура классификации образов корректна, если объект и в самом деле относится к классу с,-. Процедурой распознавания образов называется процедура определения этих областей { Ф,-} путем исследования множества Tteach объектов, про которые известно, каким классам они на самом деле
-12-
принадлежат. Итак, Tteach будет обучающей выборкой, с которой работает процедура распознавания образов.
В задаче классификации текстовых документов объектами являются текстовые документы, а классами — рубрики (тематики), которым эти документы относятся. Можно различить следующие варианты множества рубрик:
• «плоские» рубрикаторы — все рубрики полностью независимы друг от друга, иерархия отсутствует; Это самый простой вариант, однако во многих задачах анализа текстов удается свести множество классов именно к нему.
• иерархические рубрикаторы — рубрики организованы в виде дерева, документы, относящиеся к рубрике, неявно относятся и ко всем ее родительским рубрикам. Пример: рубрика «автомобили» может содержать рубрики с документами более узкой тематики, такие, как «автомобили—легковые», «автомобили — грузовые». Глубина вложенности иерархии рубрик не ограничивается - у последней из перечисленных рубрик может быть подрубрика «автомобили — грузовые — повышенной проходимости».
• графовые рубрикаторы — рубрика может иметь несколько родительских. Пример: «новости математики» может являться дочерней одновременно для рубрики «математика» и рубрики «новости науки». Графовые рубрикаторы можно привести к иерархическим при помощи
использования комбинации из двух действий — введения перекрестных ссылок и копирования поддеревьев. Первое действие предполагает, что среди всех родительских рубрик текущей обрабатываемой рубрики делается (автоматически или вручную) выбор одной главной, а остальные связи родитель-ребенок исключаются из рассмотрения классифицирующей системы (остаются только в пользовательском интерфейсе). Второе действие заключается в копировании поддеревьев таким образом, чтобы каждая из родительских рубрик ссылалась на свою собственную копию подграфа,
-13-
начинающегося с текущей обрабатываемой рубрики. Необходимо отметить,
что далеко не все алгоритмы распознавания образов устойчивы к такому копированию.
Итак, в дальнейшем можно ограничиться рассмотрением иерархических рубрикаторов.
У задачи классификации текстовых документов на иерархическом множестве классов есть 3 особенности, отличающие ее от классических задач распознавания [43, 73]. Во первых, документы, принадлежащие рубрике ch косвенно принадлежат также и всей цепочке родительских рубрик иерархии Со* са, Сь, сс.
Во вторых, объекты (текстовые документы) могут быть одновременно отнесены к нескольким классам, расположенным в разных местах иерархии. Так, например, документ, описывающий особенности технологии сварки автомобильных кузовов может быть одновременно отнесен к рубрикам «автомобили - легковые» и «технологии машиностроения - сварка». У данной особенности есть следствие, продиктованное соображениями эргономики: если документ принадлежит большому количеству рубрик, дочерних по отношению к рубрике с,-, то его удобнее приписать к самой рубрике cL Действительно, если документ содержит сведения по легковым, грузовым и некоторым специальным автомобилям, значительно удобнее видеть одну ссылку на него из рубрики «автомобили», чем 3 ссылки из рубрик «автомобили—легковые», «автомобили — грузовые» и «автомобили — легковые», «автомобили — специальные». В предельном случае, если на вход процедуре классификации подать документ, полученный конкатенацией всех документов из обучающей выборки Tteach, то такой документ полагается отнести ко всем рубрикам. Разумеется, такое решение совсем неудобно для пользователя, поэтому такой документ стоит поместить в корневую рубрику.
Третья особенность задачи классификации текстов заключается в нестабильности рубрикатора — некоторые рубрики со временем «сливаются», а другие наоборот, приходится разбивать на несколько подрубрик. Пример:
-14-
пустъ в рубрикаторе были 2 рубрики: DOS и Unix. В каждую из них попадали
документы, относящиеся к соответствующей операционной системе. Как только в базу начнут попадать документы про операционную с систему Windows или Linux (как известно, название данной операционной системы расшифровывается как Linux Is Not UniX), рубрикатор должен быть перестроен.
Введем следующие обозначения:
С = - классификатор, где:
R = {г,}, / = \..Nr - множество рубрик (классов);
Н = {<г„ rj>}, i, j = l,..Nr — иерархия рубрик - рубрика г( является родительской по отношению к рубрике гу, причем тематика документов, которые должны попадать в рубрику г,- является более общей, по сравнению с тематикой рубрики г,, например, рубрика «автомобили» является родительской по отношению к рубрике «легковые автомобили».
Ориентированный граф рубрик Г = обязательно должен быть связным, не может иметь циклов и имеет единственную корневую рубрику г0, такую, что.
3!r0eR: Vr, eR => eH*, где Н* - транзитивное замыкание отношения Н.
Sub(rt) — множество, содержащее рубрику г{ и все ее подрубрики. Sub(ro) = R.
eR: е
Sem={Sem(r,)} i = \..Nr — множество признаков рубрик (семантические образы рубрик). Данное множество формируется автоматически в процессе обучения классификатора на основе множества TteaCh.
D = {dn} - множество документов, п =1.JV«/;
-15-
Tte.ch = { : dn eD,r, eR}- обучающая выборка, приписывающая
документы dn рубрикам г,. Обучающая выборка должна полностью покрывать множество рубрик:
Dteach ={dk:< dk,rt >g Tteach} - документы обучающей выборки.
Семантические образы рубрик строятся в процессе обучения на основе графа рубрик Г и обучающей выборки Tteach с документами из множества
Dteach''
= L(R,H,Tteach)
В результате обработки множества документов D при помощи классификатора С = формируется множество классификаций
где:
dn - документ, который удалось успешно расклассифицировать, D* = {dn,e X} - множество таких документов;
г,- — рубрика, к которой принадлежит документ dn.
fni — численная мера степени соответствия документа dn рубрике г„
0Отметим, что не все документы из D могут быть расклассифицированы, то есть множество D* может не совпадать с D.
1.2. Методы оценки эффективности системы классификации текстов
Каждый из ученых, занимавшихся разработкой систем классификации текстов, обязательно дает оценки качества работы своей системы. Так как ни одна современная математическая модель не может адекватно описать все явления естественного языка (синтаксис, семантику и т. д.), эффективность работы классифицирующей системы обычно определяют экспериментально,
-16-
путем обработки некоторых тестовых наборов и сопоставления результатов обработки с результатами работы экспертов.
Часто исследователи сравнивают эффективность работы своих программ и чужих, построенных на каких-либо других идеях и алгоритмах. При этом зачастую оказывается, что разработанная каждым из авторов система работает лучше, чем все остальные. Это может быть связано с несколькими причинами:
• Используются разные наборы документов и рубрик. Очевидно, что на одних наборах классификатор может работать лучше, чем на других.
• Для одних и тех же алгоритмов используются разные настроечные параметры. Так, например, многие алгоритмы позволяют задавать приоритет полноты над точностью или наоборот, точности над полнотой.
• Нет возможности вести обработку тестовых данных одинаково для всех методов. Например, метод kNN требует настолько большого количества вычислений, что необходимо прореживание терминов или даже сокращение объема обучающей выборки [78].
• Оценка результатов классификации зачастую субъективна - то, что одному эксперту кажется правильным, для другого может казаться спорным или даже неверным.
Различные меры эффективности их обоснование и сравнение даны в [26, 27, 46]. В работе [69] предложен универсальный подход к оценке эффективности и разработан соответствующий математический аппарат.
Существуют системы для автоматической оценки эффективности программ классификации, которые в пакетном режиме выполняют обработку одного и того же набора тестовых документов несколькими различными методами, сравнивают результаты с экспертными оценками и вычисляют показатели эффективности. При этом один и тот же метод классификации может быть протестирован многократно с разными значениями настроечных параметров. Одна из таких систем описана в [76].
-17-В работах [78, 95] приведены результаты экспериментов, в которых
сравниваются современные методы классификации на одних и тех же наборах документов.
1.2.1. Определение меры эффективности классификации
Перед исследователями систем обработки текстов стоит задача сравнения различных методов, выбора среди них лучшего для данных условий и его тонкой настройки. Говоря математическим языком, выполняется поиск оптимального решения задачи. Для того, чтобы вести такой поиск, нужна численная мера того, насколько эффективно работает система. Купер (Cooper) сформулировал следующий принцип (стратегию) оптимизации систем обработки информации [46]:
Принцип 1 (The Probability Ranking Principle, PRP): Если ответы системы упорядочены по убыванию вероятности полезности для пользователя, причем эти вероятности оценены настолько точно, насколько это возможно с использованием данных, доступных системе, то эффективность такой системы максимальна по сравнению со всеми другими, располагающими этой же информацией.
Понятно, что использовать его в «чистом виде» на практике не получается. Более того, не все используемые на практике меры эффективности согласуются с этим принципом.
Пусть мы имеем некоторую меру эффективности Н (S , Z*), где S* -результаты работы классифицирующей системы, a Z* - экспертные оценки, с которыми мы эти результаты будем сравнивать [68, 69]. Так как разные эксперты могут классифицировать документы по разному, причем среди всех документов, которые эксперты отнесли к рубрике, есть те, которые бесспорно ей соответствуют и те, которые соответствуют не вполне (например, лишь часть документа посвящена данной тематике), Z* можно представить в виде множества случайных величин Z}/ (вероятность соответствия документа dt рубрике rj), каждая из которых имеет некоторое

 Часть из работы     Получить работу