Содержание к диссертации
Введение
Глава 1. Обзор методов категоризации текстовых документов 10
1.1. Формализация задачи 10
1.2. Автоматическая категоризация 11
1.3. Индексирование документов 12
1.4. Уменьшение размерности пространства признаков 14
1.5. Методы построения классификаторов 17
1.6. Оценка эффективности 26
1.7. Ансамбли классификаторов 29
1.8. Выводы 31
Глава 2. Разработка классификатора 32
2.1. Лексическая база WordNet 32
2.2. Методы разрешения лексической многозначности 37
2.3. Алгоритм разрешения лексической многозначности 47
2.4. Построение классификатора 53
2.5. Категоризация документов 61
2.6. Выводы 64
Глава 3. Программная реализация и экспериментальные исследования 66
3.1. Программная реализация 66
3.2. Эксперименты на коллекции «Reuters-21578» 72
3.3. Эксперименты на коллекции «Reuters Corpus Volume 1» 83
3.4. Анализ результатов и рекомендации 96
3.5. Выводы 99
Заключение 100
Литература
- Индексирование документов
- Алгоритм разрешения лексической многозначности
- Эксперименты на коллекции «Reuters-21578»
- Анализ результатов и рекомендации
Введение к работе
Актуальность работы. Объем накапливаемой и обрабатываемой информации постоянно увеличивается, что приводит к сложности ориентирования в информационных ресурсах, и делает задачу категоризации текстовых документов все более актуальной. Использование классификаторов позволяет ограничить поиск необходимой информации относительно небольшим подмножеством документов. Так, например, в «автоматизированной системе тематического анализа информации» (Васенин В. А. и др., 2009) классификатор используется для фильтрации результатов поиска, что повышает релевантность поисковой выдачи. Помимо сужения области поиска в поисковых системах, задача категоризации имеет практическое применение в следующих областях: фильтрация спама, составление тематических каталогов, контекстная реклама, системы электронного документооборота, снятие омонимии в автоматическом переводе текстов.
Категоризация текстовых документов является задачей автоматического отнесения документа к одной или нескольким категориям на основании содержания документа. Существуют различные модели и методы категоризации текстов — деревья решений, метод наименьших квадратов, адаптивные линейные классификаторы, метод ближайших соседей, метод опорных векторов и другие (Sebastiani F., 2002).
В последнее время активно разрабатываются способы интеграции различных баз знаний и ресурсов в методы категоризации текстовых документов с целью получения высоких результатов категоризации. Большой интерес представляет использование семантических ресурсов, таких как WordNet или Wikipedia.
WordNet — это семантический словарь английского языка, базовой словарной единицей которого является синонимический ряд, так называемый
«синеет», объединяющий слова со схожим значением. Синсеты связаны между собой различными семантическими отношениями. Также существуют реализации для других язьжов, ведутся разработки WordNet для русского язьжа.
Большинство методов категоризации основывается на использовании простой векторной модели описания документов, в которой признаками документов являются базовые формы слов. Использование слов в качестве признаков имеет ряд недостатков: словосочетания, такие как «European Union», разделяются на отдельные слова и обрабатываются независимо; слова, являющиеся синонимами, используются как самостоятельные признаки; многозначные слова рассматриваются как обычные признаки, в то время как они могут иметь несколько различных значений. В работе (Gonzalo J. et al., 1998) отмечается, что использование в качестве признаков документов значений слов, представленных синсетами, может приводить к улучшению качества категоризации на 28%. Такие результаты были получены на коллекции документов, где устранение лексической многозначности слов было выполнено вручную. Согласно результатам исследования, эффективность категоризации при использовании методов автоматического разрешения лексической многозначности, доля ошибок которых составляет менее 10%, сопоставима с эффективностью категоризации для размеченного вручную текста. Увеличение доли ошибок разрешения лексической многозначности с 10% до 30% приводит к резкому спаду эффективности категоризации, а для методов с ошибкой 30-60% использование в качестве признаков синсетов не приводит к заметному приросту эффективности категоризации.
Существует несколько публикаций, в которых сравниваются эффективности категоризации с использованием слов и синсетов WordNet, полученных с помощью различных методов автоматического разрешения лексической многозначности. В системе автоматической категоризации документов на базе метода ^-ближайших соседей (Ferretti Е. et al., 2003) использование син-
сетов в качестве признаков, полученных с помощью метода, базирующегося на использовании скрытой модели Маркова, приводит к росту эффективности категоризации на 2%. В работе (Bloehdorn S. et al, 2004) проводилось сравнение алгоритма категоризации «AdaBoost» на нескольких коллекциях документов, а для устранения лексической многозначности слов применялся метод, суть которого заключается в выборе того синсета, слова которого в документе встречаются чаще остальных. Использование данного метода позволяет повысить эффективность категоризации на 1%.
В работе (Patwardhan S. et al, 2006) описывается метод оценки семантической близости синсетов с помощью контекстных векторов, использующий информацию о совместной встречаемости слов в тексте. Оценка эффективности этого метода проводилась на нескольких наборах слов. Данный метод показывает лучшие результаты среди других методов оценки семантической близости слов на базе ресурса WordNet. Однако, практическое применение данного метода для устранения лексической многозначности не исследовалось.
Актуальность исследования обуславливается практической значимостью систем автоматической категоризации текстовых документов, в которых в качестве признаков используются значения слов, представленные синсетами WordNet.
Цели диссертационной работы:
Разработать и реализовать алгоритм разрешения лексической многозначности слов с помощью контекстных векторов на базе ресурса WordNet.
Реализовать программный комплекс автоматической категоризации текстовых документов с использованием синсетов WordNet в качестве признаков документов.
Исследовать применимость разработанного алгоритма разрешения лек-
сической многозначности к различным коллекциям документов с помощью оценки его влияния на эффективность категоризации.
Научная новизна исследования состоит в следующем:
Разработан алгоритм разрешения лексической многозначности слов, в котором используются контекстные векторы для оценки семантической близости синсетов с контекстом.
Реализован программный комплекс автоматической категоризации текстовых документов, в котором используются синсеты WordNet в качестве признаков документов и контекстные векторы для разрешения лексической многозначности.
Практическая значимость заключается в формировании нового инструмента, позволяющего повысить эффективность категоризации текстовых документов.
Полученные в диссертации результаты могут быть использованы в существующих информационных системах для повышения релевантности результатов поиска, в системах электронного документооборота для тематической категоризации документов, и представляют научный интерес для специалистов в области информационного поиска и машинного обучения.
Основные положения, выносимые на защиту:
Алгоритм разрешения лексической многозначности слов, в котором используются контекстные векторы для оценки семантической близости синсетов с контекстом.
Алгоритм обработки текстовых документов, позволяющий выделять в тексте словосочетания произвольной длины, для которых существуют синсеты WordNet.
Повышение качества категоризации неспециализированных текстов при использовании в качестве признаков документов синсетов WordNet, полученных с помощью разработанного алгоритма разрешения лексической многозначности.
Влияние на качество категоризации тематики корпуса для построения пространства слов, в котором представляются контекстные векторы.
Апробация работы. Основные результаты диссертации докладывались на следующих конференциях и семинарах: XVIII всероссийский семинар «Ней-роинформатика, ее приложения и анализ данных», г. Красноярск, Академгородок, 2010; II международная научно-практическая конференция «Прогрессивные технологии и перспективы развития», г. Тамбов, 2010; II международная заочная научно-практическая конференция «Современные направления научных исследований», 2010; межвузовская научно-практическая конференция «Информационные технологии и автоматизация управления», г. Омск, 2009; научный семинар кафедры информационной безопасности факультета компьютерных наук ОмГУ им. Ф. М. Достоевского, г. Омск, 2010.
Публикации. Материалы диссертации опубликованы в 10 печатных работах, из них 2 статьи в журналах из списка, рекомендованного ВАК.
Личный вклад автора. Содержание диссертации и основные положения, выносимые на защиту, отражают персональный вклад автора в опубликованные работы. Все представленные в диссертации результаты получены лично автором.
Структура и объем диссертации. Диссертация состоит из введения, трех основных глав, заключения и библиографии. Общий объем диссертации 118 страниц, содержит 16 рисунков и 18 таблиц. Библиография включает 112 наименований.
Индексирование документов
При решении задач автоматической категоризации текстовых документов используются методы информационного поиска (Information Retrieval, IR) [35, 73] и машинного обучения (Machine Learning, ML) [35, 82, 104].
Документы на естественном языке преобразовываются в удобную для машинной обработки форму — индексируются. В процессе индексирования происходит выделение признаков из документа.
Классификатор для категории с автоматически создается в процессе обучения, при котором просматривается множество документов с заранее определенными категориями С{ или СІ и подбираются такие характеристики классификатора, чтобы новый (ранее не просмотренный) документ, отнесенный к категории С{, соответствовал им. Чтобы построить классификатор С, необходимо множество документов D, для которых значения функции $(dj, СІ) известны для каждой пары (dj,Ci) Є D х С. В экспериментах обычно все множество документов D разделяется на два не пересекающихся подмножества [98]: — набор для обучения (обучающее множество) ; — набор для проверки (тестирующее множество) Т На обучающем множестве L строится классификатор и определяются значения его параметров, при которых классификатор выдает лучший результат. На тестирующем множестве Т происходит вычисление эффективности построенного классификатора. Индексирование документов, построение классификатора и вычисление его эффективности являются темами следующих разделов.
Индексирование документов в задачах категоризации текстов не представлено разнообразием методов и подходов. Обычно документ после индексирования представляется как вектор в некотором пространстве (пространстве признаков), в котором каждому признаку (терму) ставится в соответствие его вес (значимость): где Т — словарь, т.е. множество признаков, которые встречаются в \\ обучающих классификатор документах, и 0 шщ 1 определяет значимость признака tk в документе dj.
Подходы к индексированию различаются в методе определения признаков и способе вычисления весов.
Обычно признаками являются слова, встречающиеся в документе (за исключением так называемых стоп-слов, т.е. нейтральных слов, таких как союзы, предлоги, местоимения и т.п.). Слова, как правило, подвергаются морфологическому разбору или стеммингу (специальный алгоритм для определения морфологического корня слова [50]). Иногда в задачах категоризации текстов встречается подход с использованием не отдельных слов в качестве признаков, а словосочетаний, которые выделяются при помо щи синтаксического разбора предложений или статистически, что придает таким признакам семантически большую значимость [46, 71].
Вес u kj может просто определять наличие признака в документе, в таком случае wjy Є {0,1}. Но обычно в качестве весовых значений используются вещественные числа из диапазона 0 LUJ J 1. Такие веса имеют статистическую или вероятностную природу и зависят от метода построения классификатора.
Для определения веса признака можно привлекать дополнительную информацию. Например, если признак находится в заголовке документа, то его вес можно увеличить на несколько процентов. Документы в наборе, как правило, имеют разную длину, поэтому полученные веса принято нор-мализовыватъ. С обзором подходов к вычислению весов признаков можно ознакомиться в статье [93].
При индексировании сверхкоротких текстов документам обычно не удается набрать нужный для определения категории вес, поэтому в таких случаях применяются другие методики [6].
Наиболее популярным классом статистических весовых функций является «t/ idf», в котором определены два интуитивных правила: чем чаще признак tk встречается в документе dj, тем более значим он в нем (term frequency); чем в большем количестве документов признак tk встречается, тем менее отличительным он является (inverse document frequency). Существует множество вариантов «tf idf». Вот один из них: где u ij — вес г-го признака в документе dj, tfy — частота встречаемости г-го признака в рассматриваемом документе (term frequency), idfi = log N/n — логарифм отношения количества документов в коллекции к количеству документов, в которых встречается г-ый признак (inverse document frequency). Веса, вычисленные по этой формуле, нормализованы таким образом, что сумма квадратов весов каждого документа равна единице. Эмпирический закон Хипса [57] связывает рост количества обрабатываемых документов с ростом словаря Т. Вычислительная сложность различных методов категоризации напрямую зависит от размерности пространства признаков. Поэтому в задачах категоризации часто прибегают к сокращению числа используемых признаков, т. е. к уменьшению значения \Т\ до \Т\ « Г. Побочным эффектом уменьшения размерности пространства признаков является переобучение (overfitting), когда классификатор слишком хорошо работает на документах из обучающего набора и достаточно плохо на документах, не участвующих в обучении. Для уменьшения размерности можно прибегнуть к выбору признаков из существующих (feature selection) или к созданию искусственных (feature extraction). Существуют различные методы выбора признаков: оставлять наиболее встречающиеся признаки в документах или выбирать наиболее значимые, используя различные функции полезности.
Наиболее простой подход к уменьшению размерности пространства признаков заключается в нахождении значений df(tk) (document frequency — количество документов из ,, в которых встречается признак tk) и выборе наиболее встречающихся. В работе [111] автор показывает возможность уменьшения размерности пространства признаков в 10 раз без потери эффективности и отмечает, что уменьшение в 100 раз приводит к незначительному ухудшению работы классификатора.
Рассмотрим теперь некоторые функции полезности f(tk,Ci), характеризующие значимость признака tk в некотором документе для категории Cj. Чтобы вычислить значимость признака для всей коллекции С можно, например, найти среднее значение
Алгоритм разрешения лексической многозначности
Большинство методов категоризации основывается на использовании простой векторной модели описания документов, в которой признаками документов являются базовые формы слов. Использование слов в качестве признаков имеет ряд недостатков: словосочетания, такие как «European Union», разделяются на отдельные слова и обрабатываются независимо; слова, являющиеся синонимами, используются как самостоятельные признаки: многозначные слова рассматриваются как обычные признаки, в то время как они могут иметь несколько различных значений.
В работе [55] отмечается, что использование в качестве признаков документов значений слов, представленных синсетами, может приводить к улучшению качества категоризации на 28%. Такие результаты были получены на коллекции документов, где устранение лексической многозначности слов было выполнено вручную. Согласно результатам исследования, эффективность категоризации при использовании методов автоматического разрешения лексической многозначности, доля ошибок которых составляет менее 10%, сопоставима с эффективностью категоризации для вручную размеченного текста. Увеличение доли ошибок разрешения лексической многозначности с 10% до 30% приводит к резкому спаду эффективности категоризации, а для методов с ошибкой 30-60% использование в качестве признаков синсетов не приводит к заметному приросту эффективности категоризации.
В следующих публикациях сравниваются эффективности категоризации текстовых документов с использованием слов и синсетов WordNet, полученных с помощью различных методов автоматического разрешения лексической многозначности.
В работе [36] проводилось сравнение алгоритма «AdaBoost» на нескольких коллекциях документов с использованием автоматического разрешения лексической многозначности, суть которого заключается в выборе того синсета, чьи слова из дефиниции встречаются в документе чаще остальных. В экспериментах на коллекции «Reuters-21578» с использованием разбиения «ModApte» использование синсетов, полученных таким способом, в качестве признаков документов позволяет повысить эффективность категоризации на 1% (с 84.21% до 85% для микроусредненной i \, и с 72.75% до 73.79% — макро).
В работе [49] представлена система автоматической категоризации текстовых документов на базе метода А;-ближайших соседей, в котором признаками документов являются синсеты, полученные с помощью метода автоматического разрешения лексической многозначности на базе скрытой модели Маркова. Эксперименты проводились с коллекцией документов «20 Newsgroups». Использование представленного в работе алгоритма разрешения лексической многозначности приводит к росту эффективности категоризации на 2%.
Однако это далеко не все методы автоматического разрешения лексической многозначности слова на базе ресурса WordNct.
Разрешение лексической многозначности (Word Sense Disambiguation, WSD) — это задача выбора значения (концепта) многозначного слова или фразы из множества их значений (концептов) в зависимости от контекста, в котором данное слово или словосочетание находятся. Задача разрешения лексической многозначности оказывает влияние на такие области как информационный поиск, машинный перевод, категоризация текстов, извлечение информации и другие. Например, если в некоторой информационной системе при поиске по запросу исключить документы, в которых слова встречаются в значениях отличных от тех, что используются пользователем в запросе, то можно добиться увеличения релевантности результатов поиска.
С различными подходами к решению данной задачи можно ознакомится в [17, 21, 26, 52, 79, 107]. Рассмотрим методы разрешения лексической многозначности слов с использованием информации, полученной из ресурса WordNet.
Задачу разрешения лексической многозначности молено представить следующим образом. Возьмем для примера предложение «pine cones hanging in a tree» («сосновые шишки, висящие на дереве»). Необходимо для каждого слова определить, в каком из нескольких своих значений оно употреб ляется в данном предложении. У слова «pine» есть два значения: «kinds of evergreen tree with needle-shaped leaves» («вид вечнозеленых деревьев с игольчатыми листьями») и «waste away through sorrow or illness» («чахнуть от печали или недомогания»). Для человека очевидно, что в данном примере слово «pine» употреблено в первом значении.
Если построить все возможные пересечения предложения с дефинициями синсетов обрабатываемого слова, то в качестве искомого значения можно выбрать синеет с наибольшим количеством слов в пересечении. В данном примере пересечение первого значения слова «pine» с предложением даст одно слово «tree» в пересечении, а второе — ничего. На этом предположении основан алгоритм разрешения лексической многозначности Леска, который в работе [30] был адаптирован для работы с WordNet.
Рассмотрим метод разрешения лексической многозначности, основанный на попарной оценке семантической близости синсетов [31, 39]. Идея заключается в том, что слова, которые в тексте встречаются вместе, как правило, употребляются в одних и тех же значениях. Например, если слово «pine» стоит рядом со словом «сопе», то «pine» употребляется в значении «сосновый», в то же время, если рядом находится слово «away», то используется уже значение, обозначающее действие «изнывать».
Для обрабатываемого слова определяется контекст — множество слов в предложении, которые находятся по обе стороны от обрабатываемого слова, включая его самого. Предположим, что контекст состоит из In + 1 слов. Если обозначить слова за Wi, где —п і + п, то WQ будет являться обрабатываемым словом. Чтобы определить значение слова WQ В ЭТОМ контексте, необходимо для каждого синсета SQA; слова WQ ВЫЧИСЛИТЬ значение следующей функции: где \u i\ — количество синсетов слова Wi, Sij обозначает j-ът синеет слова Wi, sim(x,y) — некоторая функция оценки семантической близости пары синсетов х и у. В качестве значения слова WQ выбирается синеет SOA,- с наибольшим значением score(sok) Синсеты WordNet связаны между собой различными семантическими отношениями, образуя иерархическую структуру. Использование этой иерархии лежит в основе следующих методов оценки семантической близости синсетов.
Кратчайший путь. Суть метода заключается в вычислении кратчайшего расстояния между двумя синсетами в иерархии. Очевидно, что чем короче путь от одного концепта к другому, тем более семантически близкими они являются. Чем глубже в иерархии находятся узлы, тем короче должны быть расстояния между ними, так как более специфичными они являются. Поэтому ребра необходимо взвешивать. В общем виде формула ДЛЯ ОЦеНКИ СемаНТИЧеСКОЙ блИЗОСТИ Двух СИНСеТОВ Si И S2 выглядит
Эксперименты на коллекции «Reuters-21578»
Программный комплекс автоматической категоризации текстовых документов реализован на языке программирования Erlang с использованием открытой платформы ОТР [28].
Erlang — функциональный язык программирования с динамической типизацией, предназначенный для создания распределенных вычислительных систем. Программы, на языке Erlang транслируются в байт-код, исполняемый виртуальной машиной, что обеспечивает переносимость. Работа с Erlang, как правило, подразумевает использование ОТР (Open Telecom Platform) — большой коллекции библиотек для Erlang.
Разработанный программный комплекс автоматической категоризации состоит из следующих модулей: 1. wnc — модуль компиляции ресурсов WordNet. Отвечает за обработку файлов базы WordNet. WordNet работает с десятком файлов, и для увеличения производительности этот модуль компилирует все необходимые данные во внутреннее представление Erlang. 2. wn — модуль библиотеки WordNet. Содержит реализацию всех необходимых функций для работы с WordNet на Erlang. В частности, функции получения списка синсетов для слова и части речи, получение расширенной дефиниции для синсета, создание пространства слов и вычисление векторов дефиниций. 3. wnm — модуль морфологического разбора. Производит морфологический разбор слов и словосочетаний. 4. wnmc — модуль компиляции словарей исключений WordNet. Преобразовывает файлы со словами исключениями во внутреннее представление Erlang для более удобной и эффективной работы. 5. wnp — модуль обработки (парсиига) текстовых документов. Отвечает за разбиение документа на предложения и фрагменты, поиск слов и словосочетаний с использованием модуля wnm. Модуль wn используется для разрешения лексической многозначности. 6. кпп - модуль, в котором реализован fc-NN классификатор. Является главным, управляющим модулем, который отвечает за построение классификатора и последующую категоризацию документов. 7. Не — модуль для работы с документами коллекции «Reuters-21578». Поддерживает работу в двух режимах: синхронном и асинхронном. В случае использования синхронного режима, документы индексируются по очереди и передаются в модуль кпп. Обработка следующего документа начинается только после обработки предыдущего. В асинхронном режиме для каждого документа создается отдельный легковесный процесс Erlang, что позволяет вести категоризацию в параллельном режиме. 8. rtc2 — модуль для работы с документами коллекции «Reuters Corpus Volume 1». Работает, как и модуль rtc, в двух режимах: синхронном и асинхронном.
Модульная организация позволяет вносить изменения в реализацию отдельно взятого модуля без необходимости модификации остальных модулей. Центральным модулем является кпп, который взаимодействует с модулем wnp при индексировании документов. Модуль wnp получает на входе текст документа и отдает на выходе список признаков. Модуль кпп спроектирован таким образом, что в качестве признаков документов могут выступать любые типы данных. Например, для разработанного классификатора признаками являются идентификаторы синсетов. Но не составит большого труда изменить реализацию модуля wnp, чтобы на после индексирования документа получался список базовых форм слов. Что и было сделано в ходе экспериментов для исследования применимости разработанного метода разрешения лексической многозначности в категоризации текстов, когда эффективность разработанного классификатора сравнивалась с эффективностью базовой реализацией метода ближайших соседей.
Программный комплекс полностью выполнен на Erlang/OTP, что позволяет запускать его на любой платформе, для которой существует реализация виртуальный машины Erlang. Работа комплекса была проверена на ОС Windows 7, Ubuntu Linux 10.10 и Mac OS 10.6.
Erlang предоставляет высокоуровневые структуры хранения и представления данных, такие как кортежи, списки, хеш-таблицы. Кортеж — это набор данных фиксированного размера. Erlang предоставляет два типа хеш-таблиц: ETS и DETS. Отличие заключается в том, что первый тип таблиц полностью размещается в памяти, а второй тип таблиц хранится в дисковом пространстве и частично в памяти. Для хранения элементов, определяющих пространство слов W, используется ETS таблица ws, элементами которой являются кортежи вида {word, count}, где word — слово, a count — количество раз, которое слово word встретилось в корпусе. Контекстные векторы первого порядка для слов из W представлены бинарными массивами данных и хранятся в DETS таблице dws, элементами которой являются кортежи {word, id, cx_vector}, где id — идентификатор слова word в пространстве слов, a cx_vector — контекстный вектор первого порядка слова word.
Вектора дефиниций синсетов из-за их огромных размеров (порядка 7 гигабайт) хранятся в файле с произвольным доступом. Каждый синеет имеет внутренний идентификатор, который используется для вычисления смещения в файле векторов дефиниций.
Данные синсетов хранятся в ETS таблице data. Ключом таблицы является пара {pos, offset}, где pos — часть речи синсета, a offset — внутренний идентификатор WordNet, представляющий смещение в файле с данными. Несмотря на то, что файлы WordNet не используются после компиляции, идентификаторы было решено оставить для удобства отладки. Элементами этой таблицы являются кортежи {key, words, gloss}, где words — список слов синсета, a gloss — дефиниция синсета, представляющая собой список слов. Данные из индексных файлов WordNet хранятся в ETS таблице index, элементами которой являются кортежи {key, synset}, где key — {pos, word}, pos — часть речи слова word, a synset — список смещений offset синсетов, каждый из которых вместе epos идентифицирует синеет в таблице данных синсетов. Таким образом, чтобы получить для некоторого слова список синсетов дефинициями, необходимо произвести поиск записи с ключом {pos, word} в таблице index, затем для каждого значения offset из synset этой записи получить запись с ключом {pos, offset} из таблицы data.
Анализ результатов и рекомендации
Модульная организация позволяет вносить изменения в реализацию отдельно взятого модуля без необходимости модификации остальных модулей. Центральным модулем является кпп, который взаимодействует с модулем wnp при индексировании документов. Модуль wnp получает на входе текст документа и отдает на выходе список признаков. Модуль кпп спроектирован таким образом, что в качестве признаков документов могут выступать любые типы данных. Например, для разработанного классификатора признаками являются идентификаторы синсетов. Но не составит большого труда изменить реализацию модуля wnp, чтобы на после индексирования документа получался список базовых форм слов. Что и было сделано в ходе экспериментов для исследования применимости разработанного метода разрешения лексической многозначности в категоризации текстов, когда эффективность разработанного классификатора сравнивалась с эффективностью базовой реализацией метода ближайших соседей.
Программный комплекс полностью выполнен на Erlang/OTP, что позволяет запускать его на любой платформе, для которой существует реализация виртуальный машины Erlang. Работа комплекса была проверена на ОС Windows 7, Ubuntu Linux 10.10 и Mac OS 10.6.
Erlang предоставляет высокоуровневые структуры хранения и представления данных, такие как кортежи, списки, хеш-таблицы. Кортеж — это набор данных фиксированного размера. Erlang предоставляет два типа хеш-таблиц: ETS и DETS. Отличие заключается в том, что первый тип таблиц полностью размещается в памяти, а второй тип таблиц хранится в дисковом пространстве и частично в памяти. Для хранения элементов, определяющих пространство слов W, используется ETS таблица ws, элементами которой являются кортежи вида {word, count}, где word — слово, a count — количество раз, которое слово word встретилось в корпусе. Контекстные векторы первого порядка для слов из W представлены бинарными массивами данных и хранятся в DETS таблице dws, элементами которой являются кортежи {word, id, cx_vector}, где id — идентификатор слова word в пространстве слов, a cx_vector — контекстный вектор первого порядка слова word.
Вектора дефиниций синсетов из-за их огромных размеров (порядка 7 гигабайт) хранятся в файле с произвольным доступом. Каждый синеет имеет внутренний идентификатор, который используется для вычисления смещения в файле векторов дефиниций.
Данные синсетов хранятся в ETS таблице data. Ключом таблицы является пара {pos, offset}, где pos — часть речи синсета, a offset — внутренний идентификатор WordNet, представляющий смещение в файле с данными. Несмотря на то, что файлы WordNet не используются после компиляции, идентификаторы было решено оставить для удобства отладки. Элементами этой таблицы являются кортежи {key, words, gloss}, где words — список слов синсета, a gloss — дефиниция синсета, представляющая собой список слов. Данные из индексных файлов WordNet хранятся в ETS таблице index, элементами которой являются кортежи {key, synset}, где key — {pos, word}, pos — часть речи слова word, a synset — список смещений offset синсетов, каждый из которых вместе epos идентифицирует синеет в таблице данных синсетов. Таким образом, чтобы получить для некоторого слова список синсетов дефинициями, необходимо произвести поиск записи с ключом {pos, word} в таблице index, затем для каждого значения offset из synset этой записи получить запись с ключом {pos, offset} из таблицы data. Модуль кпп отвечает за хранение различных статистических данных, полученных во время построения классификатора.
Пространство признаков реализовано как ETS таблица features, элементами которой являются кортежи {id,df,idf}, где id — идентификатор признака, df — встречаемость признака id в обучающем множестве документов, idf — логарифм отношения общего числа документов к количеству документов, в которых встречается признак id. В зависимости от реализации модуля wnp классификатора, в качестве id могут выступать базовые формы слов (бинарные данные) или синсеты, представленные кортежами вида {pos,offset}.
Документы обучающего множества хранятся в ETS таблице documents, элементами которой являются кортежи {id,tf,topics,weights}, где tf — встречаемость признаков в документе, topics — список категорий документа и weights — список взвешенных признаков документа.
Хранение категорий организовано в ETS таблице topics, элементами которой являются кортежи вида {name, documents}, где пате — название категории, a documents — список идентификаторов документов категории.
Для исследования влияния разработанного алгоритма разрешения лексической многозначности (WSD) на эффективность категоризации текстовых документов были проведены эксперименты с разработанным &HMN классификатором и классификатором SVMh9ht [62]. Для каждой коллекции документов сначала проводилось вычисление эффективности категоризации, когда в качестве признаков документов выступали базовые формы слов (т. е. без использования WSD), а затем — синсеты (и использованием WSD). Таблица 3.1. Усреднение точности р и полноты г
Для этого в модуле гипр в дополнение к разработанному методу обработки документов был реализован метод без привлечения механизма разрешения лексической многозначности, что позволило получать для документа на выходе набор базовых форм слов, встретившихся в документе.
Вычисление эффективности реализовано в модуле кпп. Для вычисления микро- и макроусредненных значений точности и полноты используются формулы из таблицы 1.1 на стр. 27. Если за N взять общее количество категорий, А\ — количество документов, которые должно были быть отнесены к категории С{ при категоризации, В{ — количество документов, которые были классификатором отнесены к категории с,-, а С, — количество документов, которые были верно отнесены к категории СІ, тогда формулы для вычисления эффективности принимают вид из таблицы 3.1. 3.2. Эксперименты на коллекции «Reuters—21578»
Чтобы провести сравнение различных классификаторов, необходимо выполнить их построение и вычисление эффективности на одинаковых наборах документов для обучения и тестирования. Широкое распространение получил корпус текстов «Reuters-21578» [69], для которого существуют фиксированные разбиения на обучающее и тестирующее множества. Коллекция состоит из 21578 документов — финансовые новости, проходившие через новостное агентство Рейтере в 1987 году.
Построение классификаторов и оценка их эффективности проводилась с использованием разбиения «ModApte». Это разбиение задает 90 категорий, 9603 документа содержатся в обучающем наборе и 3299 документов — в тестирующем. В таблице 3.2 представлено разбиение документов по обучающему и тестирующему множествам для десяти самых больших категорий «Reuters-21578». Из таблицы хорошо видно, что эта коллекция является несбалансированной.
На этом корпусе текстов для разработанного &-NN классификатора (без использования механизма разрешения лексической многозначности) было исследовано влияние значения параметра к на качество категоризации.
В таблице 3.3 приведены результаты экспериментов с fc-NN классификатором для различных значений к. На рисунках 3.1 и 3.2 показаны графики зависимости от параметра к микро- и макроусредненных значений точности р, полноты г и меры F\. Из таблицы и графиков видно, что с ростом значения к микроусредненные значения точности и полноты уменьшаются, а макроусредненная точность повышается, но значения меры Fi для обоих
