Кибернетики




Скачать 100.42 Kb.
PDF просмотр
НазваниеКибернетики
Студент  курса
Дата конвертации03.10.2012
Размер100.42 Kb.
ТипИсследование
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ИМ. М.В. ЛОМОНОСОВА
ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И
КИБЕРНЕТИКИ
Курсовая работа
Исследование и разработка методов извлечения отношений из текста
Выполнил:
Студент 4 курса
Федоренко Денис Глебович
Научный руководитель:
Турдаков Денис Юрьевич
Москва
2012

Оглавление
Вв
  едение                                                                                                                                
 ............................................................................................................................... . . . . . . . . . . . . . . .4  
1 П
 
остановка задачи                                                                                                               
 .............................................................................................................. . . . . . . . . . . . . .5  
2 О
 
бзор существующих методов                                                                                                   
 .................................................................................................. . . . . .6  
2.1 О
 
бучение с учителем (Supervised learning)                                              
 ............................................. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6  
2.2 Ча
 
стичное обучение с учителем (Semi-supervised learning)                    
 ................... . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6  
2.3 О
 
писание систем DIPRE и Snowball                                                                       
 ...................................................................... . . . . . . . . . . . . . . . .6  
2.4 Вы
 
вод                                                                                                                  
 ................................................................................................................. . . . . . . . . . . . . . . . . . . . . . . .7  
3 И
 
сследование и построение решения задачи                                                                                 
 
 
................................................................................
 
9  
3.1 Ба
 
зовая архитектура алгоритма                                                                                
 ............................................................................... . . . . . . . . . . . . . . .9  
3.2 Н
 
ачальные данные                                                                                                  
 ................................................................................................. . . . . . . . . . . . . . . . . . .9  
3.3 К
 
оллекция документов                                                                                      
 ..................................................................................... . . . . . . . . . . . . . . . . . . . . . . .9  
3.4 Г
 
енерация шаблонов                                                                                                
 ............................................................................................... . . . . . . . . . . . . . . .10
   
3.4.1 И
 
звлечение признаков                                                                       
 ...................................................................... . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10
   
3.4.2 И
 
звлечение шаблонов                                                                                     
 .................................................................................... . . . . . . . . . . . . . . . .10
   
А
  лгоритм Single-pass Clustering                                                                         
 ........................................................................ . . . . . . . . . . . . . . . .10
   
О
  пределение частей речи                                                                                               
 .............................................................................................. . . . . .1 1 
3.5 И
 
звлечение новых кортежей                                                                              
 ............................................................................. . . . . . . . . . . . . . . . . . . . .1 1 
3.6 О
 
ценка шаблонов и кортежей                                                                            
 ........................................................................... . . . . . . . . . . . . . . . . . . . .1 1 
3.6.1 О
 
ценка шаблонов                                                                                     
 .................................................................................... . . . . . . . . . . . . . . . . . . . . . . .12
   
3.6.2 О
 
ценка кортежей                                                                                       
 ...................................................................................... . . . . . . . . . . . . . . . . . . . . . .12
   
3.7 Во
 
сстановление неполных кортежей                                                                    
 ................................................................... . . . . . . . . . . . . . . . .13
   
4 О
 
писание практической части                                                                                                    
 ................................................................................................... . . .14
   
4.1 О
 
пределение частей речи                                                                                         
 ........................................................................................ . . . . . . . . . . . . . .14
   
4.2 Вы
 
бор поискового веб-сервиса                                                                                            
 ........................................................................................... . .14
   
4.3 Вз
 
аимодействие с поисковым веб-сервисом                                                         
 ........................................................ . . . . . . . . . . . . . . .15
   
4.3.1 П
 
оиск веб-страниц                                                                                      
 ..................................................................................... . . . . . . . . . . . . . . . . . . . .15
   
4.4 А
 
рхитектура системы                                                                                            
 ........................................................................................... . . . . . . . . . . . . . . . . .16
   
4.4.1 Ди
 
аграммы активности                                                                                                  
 ................................................................................................. .16
   
А
  лгоритм кластеризации                                                                               
 .............................................................................. . . . . . . . . . . . . . . . . . . . . .16
   
А
  лгоритм извлечения кортежей                                                                      
 ..................................................................... . . . . . . . . . . . . . . . . . . .17
   
А
  лгоритм оценки шаблонов                                                                           
 .......................................................................... . . . . . . . . . . . . . . . . . . . .18
   
А
  лгоритм оценки кортежей                                                                             
 ............................................................................ . . . . . . . . . . . . . . . . . . .19
   
4.4.2 Ди
 
аграммы классов                                                                                                  
 ................................................................................................. . . . . . . .20
   
Вн
  утреннее представление шаблонов                                                               
 .............................................................. . . . . . . . . . . . . . . . .20
   
П
  одсистема генерации шаблонов                                                            
 ........................................................... . . . . . . . . . . . . . . . . . . . . . . . . . .21
   
П
  одсистема извлечения контекстов                                                                      
 ..................................................................... . . . . . . . . . . . . .22
   
П
  одсистема извлечения шаблонов                                                                               
 .............................................................................. . . . . . .23
   
П
  одсистема поиска документов в текстовой коллекции                   
 .................. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .24
   
П
  одсистема форматирования результатов поиска документов                            
 ........................... . . . . . . . . . . .25
   
И
  терация базового алгоритма                                                                  
 ................................................................. . . . . . . . . . . . . . . . . . . . . . . . . . .26
   
Ф
  асад системы                                                                                                       
 ...................................................................................................... . . . . . . . . . . . . . .27
   
4.5 Т
 
естирование                                                                                                               
 .............................................................................................................. . . . . . . . . . . . .28
   
За
  ключение                                                                                                                                  
 ................................................................................................................................. . . . . . . .30
   
2

Аннотация
Курсовая работа посвящена задаче извлечения отношений из текста с целью восстановления 
значений атрибутов в частично заполненных отношениях (кортежах). Задача восстановления 
заключается в том, чтобы найти значения для таких атрибутов, удовлетворяющие исходному 
отношению. Поиск значений атрибутов осуществляется в текстовой коллекции на основе 
связей, полученных с помощью обучающих данных – кортежей, удовлетворяющих 
исходному отношению, в которых известны все значения атрибутов.
В курсовой работе рассматриваются существующие системы извлечения отношений из 
текста (DIPRE, Snowball), а также собственная реализация системы, ориентированная на 
восстановление строк с пропущенными атрибутами.
3

Введение
Задача извлечения отношений - одна из задач обработки естественного языка. Данная задача 
заключается в поиске взаимосвязанных сущностей внутри коллекции документов. 
Примерами отношений могут являться:

(автор, книга)

(организация, адрес)

(личность, дата рождения, дата смерти)
Системы извлечения отношений могут быть полезны для организации автоматического 
заполнения и ведения баз данных, восстановления неполных данных, а также для 
информационного поиска в целом.
Все алгоритмы извлечения отношений основаны на машинном обучении и состоят из двух 
основных этапов: обучение и поиск новых данных. На этапе обучения берется некоторое 
множество заранее известных данных (кортежей), которое затем используется для извлечения 
признаков заданного отношения из коллекции документов. Затем на основе полученных 
признаков строится модель, позволяющая извлекать новые, ранее неизвестные кортежи. 
Извлечение новых кортежей происходит засчет классификации данных как либо 
удовлетворяющих, либо не удовлетворяющих исходному отношений.
Методы машинного обучения делятся на три основных типа: обучение без учителя, обучение 
с частичным привлечением учителя и обучение с учителем. Основным отличием методов 
является специфика обучения. В случае обучения с учителем требуется много обучающих 
данных, содержащих как удовлетворяющие, так и не удовлетворяющие отношению кортежи. 
Однако, в случае обучения с частичным привлечением учителя достаточно лишь небольшого 
количества исходных кортежей и неразмеченных данных.
В данной работе рассмотрена задача восстановления неполных кортежей данных на основе 
методов извлечения отношений. Данная задача заключается в восстановлении пропущенных 
значений атрибутов строк в заданной таблице. В качестве примера может быть рассмотрена 
задача восстановить пропущенное значение в кортеже “Google – ?” отношения 
(ORGANIZATION, LOCATION) на основе кортежей “Microsoft – Redmond”, “IBM – Armonk”.
Для решения поставленной задачи был выбран метод обучения с частичным привлечением 
учителя, так как он:

не требует участия человека в процессе обучения

требует мало обучающих данных, в качестве которых могут быть взяты полные 
кортежи исходной таблицы
Далее в работе подробно рассмотрен алгоритм извлечения отношений и его применение для 
восстановления неполных данных. Также приведена реализация системы, 
восстанавливающей таблицы с неполными данными. В конце работы представлены 
эксперементальные результаты и основные выводы.
4

1 Постановка задачи
Целью данной работы является:
1. Исследование существующих алгоритмов извлечения отношений
2. Разработка алгоритма восстановления неполных кортежей данных в частично 
заполненных отношениях любой размерности на основе методов извлечения 
отношений
3. Реализация разработанных алгоритмов в виде программной системы, которая:

Предоставляет возможность работать с различными источниками данных (веб-
страницы, коллекции документов)

Требует в процессе работы минимального участия человека

Имеет встроенные средства оценки качества результатов
5

2 Обзор существующих методов
На данный момент существуют различные подходы к решению задачи извлечения 
отношений. Эти подходы делятся на два типа: подходы, основанные на обучении с учителем, 
и подходы, основанные на обучении с частичным привлечением учителя.
2.1 Обучение с учителем (Supervised learning)
В качестве обучающих данных используются кортежи из двух классов: удовлетворяющие и 
не удовлетворяющие исходному отношению. Такие кортежи обычно выбираются вручную. 
Затем происходит поиск исходных кортежей в текстовой коллекции и извлечение признаков: 
частей речи, именованных сущностей, множеств слов между атрибутами и другие [4].
Извлеченные признаки используются для обучения некоторого алгоритма: SVM, Decision 
Trees, Naive Bayes, Maximum Entropy. Полученный классификатор в дальнейшем 
применяется для извлечения новых кортежей, удовлетворяющих отношению.
Преимущества метода:

Достаточно формален и хорошо изучен

Высокие показатели точности и полноты (значения достигают 90%)
Недостатки метода

Требует большого количества обучающих данных из обоих классов

Требует непосредственного участия человека в процессе обучения (необходимо 
вручную составить обучающие кортежи, среди которых есть как соответствующие, 
так и не соответствующие исходному отношению)
2.2 Частичное обучение с учителем (Semi-supervised learning)
В отличие от метода обучения с учителем, данный подход требует минимального набора 
обучающих данных. Подход основан на итеративном алгоритме: используя минимальный 
набор исходных данных, извлекаются новые данные, которые затем используются в качестве 
обучающих данных. Таким образом, после нескольких итераций алгоритма получается набор 
новых данных, которые с некоторой точностью удовлетворяют исходному отношению.
Примерами систем, реализующих описанный метод, являются: DIPRE, Snowball, KnowItAll, 
TextRunner [1]. Описание двух из них (DIPRE, Snowball) будет дано далее.
Преимущества метода

Практически не требует обучающих данных

Минимальное участие человека в процессе обучения
Недостатки метода

Нужно реализовывать "с нуля"

Средние показатели точности и полноты (значения достигают 60-75%)
2.3 Описание систем DIPRE и Snowball
Один из наиболее общих и эффективных методов извлечения отношений на основе 
6

частичного обучения был реализован в системах DIPRE и Snowball [2], [3].
Главная идея метода заключается в использовании специальных шаблонов, которые 
позволяют извлекать отношения из текстовой коллекции. Шаблоны создаются на основе 
текстового корпуса и заранее известных кортежей, соответствующих исходному отношению. 
Внутри текстовой коллекции исследуются зависимости между атрибутами отношения, 
которые выражаются в виде последовательностей слов (между атрибутами, слева и справа от 
первого и последнего атрибута соответственно). Комбинация таких последовательностей 
называется шаблоном.
К примеру, для отношения (ORGANIZATION, LOCATION) может быть найден шаблон 
" is located in ", где ,  - обозначения атрибутов отношения 
(слоты). С помощью такого шаблона можно найти новые кортежи, удовлетворяющие 
исходному отношению.
Таким образом, основными шагами метода являются:
1. Создание шаблонов на основе обучающего корпуса
2. Использование шаблонов для поиска новых кортежей
Новые кортежи (извлеченные на втором шаге алгоритма) затем используются в качестве 
обучающих данных для поиска новых шаблонов. В этом заключается итеративность метода.
Описанный метод также включает в себя различные техники оценки качества шаблонов и 
кортежей, поскольку на каждой итерации алгоритма неизбежно возникают некорректные 
данные. К примеру, шаблон ", " соответствует всем подстрокам, в которых 
слова разделены запятой. Понятно, что среди таких подстрок только их малая часть будет 
соответствовать исходному отношению. Фильтрация некорректных шаблонов и кортежей 
является необходимой составляющей метода.
Система DIPRE реализует описанный выше подход, однако обладает рядом недостатков. К 
примеру, в системе оцениваются только шаблоны, причем мера качества рассчитывается на 
основе количества слов в данном шаблоне (что является довольно слабой эвристикой). Также 
система никак не учитывает смысл атрибутов, то есть слоты шаблона соответствуют любым 
словам. Из-за этого извлекается много некорректных кортежей.
Другая система, Snowball, является улучшением системы DIPRE, устраняющим ее главные 
недостатки. В Snowball используются более формальные и обоснованные методы оценки 
качества шаблонов и кортежей, а также учитывается смысл атрибутов исходного отношения 
(в случае шаблона ", ",  будет соответствовать только названиям 
организаций). Эти улучшения позволяют системе получать более качественные результаты - 
по результатам тестирования, Snowball показывает точность и полноту на 10-15% выше, чем 
у DIPRE.
Также важной особенностью обеих систем является то, что они могут извлекать только 
отношения, состоящие из двух атрибутов. Одной из целей данной работы является 
разработка системы, позволяющей извлекать отношения с любым количеством атрибутов.
2.4 Вывод
Наиболее точно поставленным требованиям удовлетворяет метод частичного обучения с 
учителем, поскольку требует минимального участия человека. Фактически, для успешной 
работы алгоритма достаточно подать ему на вход таблицу, содержащую как полные, так и 
неполные кортежи, тогда полные кортежи будут использованы в качестве обучающих данных 
на первой итерации алгоритма.
7

Далее в работе приводится подробное описание алгоритма восстановления отношений и его 
реализация.
8


3 Исследование и построение решения задачи
Для решения поставленной задачи был разработан алгоритм, который может быть выражен 
как последовательность двух этапов:
1. Сгенерировать шаблоны на основе полных кортежей и текстовой коллекции
2. Для каждого неполного кортежа подставить его известные значения атрибутов внутрь 
шаблонов и найти в тексте значения оставшихся (неизвестных) атрибутов. К примеру, 
из шаблона " is located in " и неполного кортежа ("Microsoft", LOC) 
будет получен новый шаблон "Microsoft is located in ", который затем будет 
использован для поиска недостающего значения атрибута LOC.
3.1 Базовая архитектура алгоритма
Базовая архитектура алгоритма представлена на Рисунке 1. Алгоритм является итеративным. 
Результатом каждой итерации является набор кортежей, который затем, на последующей 
итерации, используется в качестве обучающих данных для поиска новых шаблонов. Также на 
каждой итерации происходит оценка шаблонов и кортежей: только качественные данные 
проходят на следующие итерации алгоритма. Таким образом, после нескольких итераций 
результатом являются преимущественно качественные шаблоны, которые позволяют 
извлекать релевантные исходному отношению данные.
Детальное описание каждого шага представлено далее.
Рисунок 1: архитектура алгоритма
3.2 Начальные данные
В качестве начальных данных системе подается отношение (например, файл в формате CSV), 
в котором присутствуют как полные, так и неполные кортежи. Полные кортежи используются 
в качестве обучающих данных первой итерации алгоритма, а неполные - в качестве данных 
для тестирования.
На начальные данные не накладываются какие-либо ограничения: атрибуты таблицы могут 
иметь любое значение, количество атрибутов не фиксировано.
3.3 Коллекция документов
Поскольку природа начальных данных неизвестна, то заранее подготовить текстовую 
9

коллекцию не представляется возможным. Поэтому в качестве основного источника данных 
было решено использовать поисковые веб-сервисы, позволяющие получать нужную 
информацию "на лету".
3.4 Генерация шаблонов
На данном шаге из текста извлекаются признаки с целью создания шаблонов, 
соответствующих отношению и позволяющих извлекать новые кортежи данных.
3.4.1 Извлечение признаков
Алгоритму подается на вход набор полных кортежей (то есть кортежей без пустых значений 
атрибутов). Для каждого такого кортежа система ищет в коллекции документов части текста, 
в которых содержатся атрибуты данного кортежа. Среди таких частей текста выбираются 
только те, в которых атрибуты расположены достаточно близко  друг к другу (т.е. любые два 
атрибута отстоят друг от друга не более, чем на N слов), после чего извлекаются контексты - 
последовательности слов, которые "соединяют" атрибуты друг с другом. Каждое слово 
контекста обладает весом - функцией частоты слова внутри этого контекста.
Таким образом, результатом шага алгоритма является набор признаков - структур вида 
, где contexti - i-ый контекст, sloti - i-ый слот.
Рассмотрим пример. Пусть исходным отношением является отношение (AUTHOR, BOOK). 
Тогда для кортежа  и текста "War and Peace is a novel by the 
Russian author Leo Tolstoy, first published in 1869" будет извлечен признак вида <"", BOOK, "is 
a novel by the Russian author", AUTHOR, "first published in 1869">.
3.4.2 Извлечение шаблонов
На предыдущем шаге алгоритма получается набор признаков, соответствующих исходным 
кортежам. Далее признаки группируются с целью нахождения шаблонов - наиболее общих 
последовательностей контекстов, характеризующих связи между атрибутами в исходном 
отношении. В качестве алгоритма кластеризации используется алгоритм Single-pass 
Clustering [6].
Алгоритм Single-pass Clustering
Данный алгоритм является простым однопроходным алгоритмом кластеризации.
Основные шаги алгоритма:
1. Инициализация начального кластера.
Из признаков, поданых на вход алгоритму, некоторым образом выбирается признак, 
который будет использован в качестве начального кластера. Обычно в качестве такого 
признака берется первый признак, либо случайный признак из кластеризуемой 
последовательности.
2. Для каждого последующего признака t:
1. Найти такой кластер с центроидом centroid, что значение m = Match(centroid, t) - 
максимально. Центроидом группы признаков является некий общий признак, в 
котором каждый контекст является результатом пересечения соответствующих 
контекстов элементов кластера. Функция Match - функция близости признаков 
(определена далее).
Если значение m меньше некоторого заранее определенного значения threshold, то 
10


создать новый кластер из признака t, иначе поместить t в кластер с максимальным 
значением m. Значение threshold определяется эмпирически и в рассматриваемой 
задаче имеет достаточно высокое значение (не менее 0.8).
Функция близости Match
Данная функция применяется для подсчета близости между структурами вида
.
Пусть имеются два признака вида p1 = , p2 = . Тогда функция Match 
определена как
В результате кластеризации получается набор групп похожих признаков. Центроидами таких 
групп являются шаблоны, которые затем используются для извлечения новых кортежей, 
удовлетворяющих отношению. Так, для группы признаков {<"", BOOK, "is a novel by the 
Russian author", AUTHOR, "first published in 1869">, <"", BOOK, "is a novel by the English 
author", AUTHOR, "published in 1905">} шаблоном может являться <"", BOOK, "is a novel by 
author", AUTHOR, "published in">.
Определение частей речи
Для каждого атрибута исходного отношения также определяется часть речи. Это необходимо, 
поскольку слоты в шаблонах не несут никакой дополнительной информации о сущностях 
отношения и, тем самым, могут соответствовать любому слову в тексте. Из-за этого шаблоны 
могут извлекать множество некорректных кортежей. Дополнительная информация - часть 
речи - позволяет отсечь часть некорректных данных, путем сравнения части речи атрибута 
шаблона с фактической частью речи некоторого слова.
3.5 Извлечение новых кортежей
На данном этапе происходит поиск новых кортежей путем сопоставления шаблонов с 
коллекцией документов.
На первом шаге извлекаются части текста, содержащие слова, части речи которых совпадают 
с частями речи атрибутов шаблонов. Далее для этих слов извлекается контекст. Полученный 
текст представляется в виде t = , после чего сопоставляется 
с некоторым шаблоном p с помощью функции Match. Если значение Match(t,p) больше, чем 
некоторое пороговое значение sim  (определяется эмпирически, обычно не менее 0.6), то 
сохраняется новый кортеж вида , где attri - значения атрибутов кортежа.
Например, шаблон <"", BOOK, "is a novel by author", AUTHOR, "published in"> может извлечь 
кортеж  из предложения "Eugene Onegin is a novel by Pushkin is 
published in 1833".
3.6 Оценка шаблонов и кортежей
Оценка качества извлекаемой информации является важной составляющей алгоритма, так 
как на каждой его итерации неизбежно появляются как "плохие" шаблоны так и, как 
следствие, "плохие" кортежи. К примеру, шаблон ", " не является 
удовлетворительным, так как совпадает с любой подстрокой, содержащей запятую. Понятно, 
11




что такой шаблон извлечет множество кортежей, несоответствующих отношению. Если 
"плохие" кортежи будут допущены на следующую итерацию алгоритма, то качество 
информации будет постепенно ухудшаться.
3.6.1 Оценка шаблонов
Предположим, для некоторого отношения R=(r1, ..., rN) был сгенерирован шаблон P. Для 
оценки данного шаблона генерируются все возможные подмножества S исходного отношения 
R мощности N-1, т.е. Subsets = { S : S = (r1, ..., ri-1, ri+1, ..., rN), 1 <= i <= N }. Затем для каждого 
такого подмножества Si берется каждый обучающий кортеж, и его значения атрибутов из 
подмножества Si подставляются в шаблон P. В итоге получается набор шаблонов, в котором 
неизвестен лишь один, i-ый атрибут исходного отношения. К примеру, для отношения 
(ORGANIZATION, LOCATION) и шаблона " is located in " система 
сгенерирует набор шаблонов вида {"%T1% is located in ", " is located in 
%T2%"}, где %T1% и %T2% - некоторые значения атрибутов ORGANIZATION и LOCATION 
соответственно. Затем каждый такой шаблон сопоставляется с текстовой коллекцией с целью 
поиска недостающего атрибута. Полученные результаты сравниваются с реальными 
значениями атрибутов и итоговая оценка вычисляется по формуле
Шаблон считается "хорошим", если значение оценочной функции больше, чем некоторое 
значение conf. определяемое по результатам тестирования.
3.6.2 Оценка кортежей
Имея значения оценок для шаблонов, можно оценить кортежи, извлеченные данными 
шаблонами. Заметим, что каждый кортеж может быть извлечен несколько раз разными 
шаблонами.
Рассмотрим кортеж T и набор шаблонов P = {Pi}, которые извлекли данный кортеж. 
Предположим, что известна вероятность, с которой каждый шаблон Pi извлекает кортежи, 
удовлетворяющие отношению. Если события извлечения кортежей независимы, то 
вероятность того, что кортеж T является корректным, может быть вычислена по формуле
В качестве оценки величины Prob(Pi) может быть использована метрика Conf(Pi), поэтому 
формула оценки качества кортежа выглядит как
Напомним, что алгоритм является итеративным, поэтому необходимо также учитывать 
результаты оценок предыдущих итераций. Оценка качества шаблона с учетом предыдущих 
итераций может быть вычислена по формуле
12


Если параметр Wupdt меньше 0.5, тогда алгоритм доверяет новым результатам меньше, чем 
результатам, полученным на предыдущих итерациях.
Аналогичным образом вычисляет и оценка кортежей.
Таким образом, после вычисления оценок шаблонов и кортежей, алгоритм отсекает часть 
кортежей с низкой оценкой conf. Такие кортежи не переходят на следующую итерацию 
алгоритма и, тем самым, далее не участвуют в процессе создания новых шаблонов.
3.7 Восстановление неполных кортежей
Результатом N итераций базового алгоритма является набор шаблонов {P}. Теперь в каждый 
из этих шаблонов можно подставить известные значения атрибутов неполных кортежей и, 
получив таким образом новые шаблоны, найти в текстовой коллекции недостающие значения 
атрибутов. В качестве итоговых выбираются наиболее часто встречаемые значения.
13

4 Описание практической части
4.1 Определение частей речи
Для определения частей речи атрибутов отношения используется библиотека Stanford POS 
Tagger.
Из отношения берется полный кортеж, затем каждый из его атрибутов подается на вход 
библиотеке. Определенные таким образом части речи являются частями речи атрибутов всего 
отношения.
При определении частей речи атрибутов внутри текста также учитывается контекст 
атрибутов [7].
4.2 Выбор поискового веб-сервиса
Были рассмотрены следующие сервисы:

Яндекс
Недостатки: не имеет API для взаимодействия, сильное ограничение на количество 
запросов

Google
Преимущества: удобный API
Недостатки: ограничение на количество запросов в день

Bing
Преимущества: удобный API, ограничение на количество запросов в секунду
Опираясь на преимущества и недостатки рассмотренных систем, в качестве основного 
поискового сервиса был выбран Bing.
14

4.3 Взаимодействие с поисковым веб-сервисом
Взаимодействие с сервисом Bing осуществляется по протоколу REST. Возвращаемым 
значением сервиса является документ в формате XML, узлы которого содержат аннотации и 
URL найденных веб-страниц.
Для разбора веб-страниц (которые представляют собой документы в формате HTML) 
использовалась библиотека Jsoup.
4.3.1 Поиск веб-страниц
Поскольку поисковый сервис Bing поддерживает только текстовые запросы, то для поиска 
документов, содержащих кортежи, необходимо предварительно преобразовать исходные 
данные в строковый вид:
 → "attr1" ... "attrN"
Атрибуты заключаются в кавычки для того, чтобы поисковый сервис не применял 
лексические преобразования и искал строки в исходном виде.
Аналогично, для поиска документов, удовлетворяющих шаблонам, применяется 
преобразование:
 → "context1" ... "contextN+1"
При таком преобразовании теряется информация об атрибутах шаблона, так как современные 
поисковые сервисы пока что не предоставляют возможность поиска текста вместе с его мета-
информацией, такой как части речи, именованные сущности, регулярные выражения. К 
сожалению, из-за этого качество извлекаемых документов сильно ухудшается.
15


4.4 Архитектура системы
4.4.1 Диаграммы активности
Алгоритм кластеризации
16


Алгоритм извлечения кортежей
17


Алгоритм оценки шаблонов
18


Алгоритм оценки кортежей
19


4.4.2 Диаграммы классов
Внутреннее представление шаблонов
token.FeaturedTokenList - базовый класс, представляющий структуру шаблонов и кортежей
token.FeaturedToken - абстрактный элемент FeaturedTokenList, имеющий различные 
признаки, такие как текстовое представление, вес
20


Подсистема генерации шаблонов
token.pattern.ClustersOfPatternsFromWorkpieceGenerator - генерирует кластеры 
признаков. Использует алгоритм кластеризации Single-pass Clustering
token.pattern.PatternFromClusterGenerator - генерирует шаблон по кластеру, то есть 
извлекает центроид кластера
token.ContextExtractor - извлекает контексты шаблонов
token.pattern.PatternFromPatternWorkpieceGenerator - генерирует шаблоны из 
"заготовок". Главное отличие "заготовки" от шаблона в том, что шаблон содержит слоты и 
взвешанные контексты, а "заготовка" содержит реальные значения атрибутов (вместо слотов) 
и контексты без весовых значений
21


Подсистема извлечения контекстов
token.ContextExtractor - извлекает контексты шаблонов (последовательности слов, 
разделенных слотами)
22


Подсистема извлечения шаблонов
PatternsExtractor извлекает шаблоны с помощью известных кортежей и текстовой 
коллекции. Не оценивает извлекаемые шаблоны
docs.DocumentSearcher ищет документы в текстовой коллекции
23


Подсистема поиска документов в текстовой коллекции
docs.DocumentSearcher - абстрактный класс для поиска документов в текстовой коллекции
docs.WebDocumentSearcher - реализация DocumentSearcher для поиска документов с 
помощью поисковых веб-сервисов (Bing, Google)
docs.IQueryString - интерфейс преобразования шаблонов и кортежей в вид, понятный для 
подсистемы поиска документов в текстовой коллекции
24


Подсистема форматирования результатов поиска документов
docs.formatter.IFormatter - интерфейс форматирования результатов поиска в некоторый 
канонический вид
25


Итерация базового алгоритма
EvaluatedDataExtractor возвращает только "хорошие" данные после итерации алгоритма
PatternEvaluator подсистема оценки извлекаемых шаблонов
TupleEvaluator подсистема оценки качества извлекаемых кортежей
EvaluatedPattern - шаблон и его значения оценки
EvaluatedTuple – кортеж и его значения оценки
26


Фасад системы
RelationExtractionFacade – точка входа в систему
RelationExtractionBootstrapper осуществляет итерации базового алгоритма 
TupleFiller восстанавливает неполные кортежи с помощью шаблонов 
27


4.5 Тестирование
Для тестирования системы использовалось отношение (ORGANIZATION, LOCATION) со 
следующим набором обучающих данных:
Для каждого кортежа с помощью системы Bing извлекался набор документов (порядка 30), 
содержащих данный кортеж. Далее на этих документах запускался алгоритм извлечения 
шаблонов. Пороговое значение функции Match при кластеризации полагалось равным 0.8.
На первой итерации алгоритма было получено порядка 50 различных шаблонов, 
большинство из которых было неудовлетворительным. Далее запускался алгоритм 
оценивания: шаблон считался "хорошим", если значение conf по каждому из его атрибутов 
было не ниже 0.1. В результате оценивания остались следующие шаблоны:












На следующем этапе алгоритма с помощью полученных шаблонов извлекались новые 
кортежи. Для этого каждый из шаблонов преобразовывался в строку, после чего извлекались 
соответствующие наборы веб-страниц. Далее запускался алгоритм извлечения кортежей. 
Пороговое значение функции Match полагалось равным 0.7.
По результатам эксперимента, лишь малая часть полученных кортежей соответствовала 
исходному отношению:

,  (2 из 16)

:
 * 3,
 * 2,
,
 (7 из 24)

 * 2 (2 из 20)

 (0 из 13)
Причиной таких результатов во многом являлось то, что извлеченный набор документов 
содержал много страниц, не удовлетворяющих шаблонам. К примеру, у запроса " 's 
headquarters in" поисковый сервис проигнорировал подстроки " 's " и "in", которые являлись 
важными составляющими шаблона. Поэтому из всех кортежей не нашлось ни одного 
28

удовлетворительного.
Понятно, что при таком наборе данных система будет сильно деградировать и не сможет 
извлекать шаблоны нужного качества.
29

Заключение
Была разработана система восстановления неполных кортежей данных с помощью метода 
извлечения отношений, основанного на итеративном алгоритме поиска шаблонов и кортежей. 
Система позволяет работать с отношениями любой размерности. В качестве основного 
источника данных система использует поисковые веб-сервисы.
Разработанной системе не удалось в полной мере решить задачу восстановления отношений, 
поскольку современные поисковые сервисы не предоставляют возможностей поиска текста с 
учетом его мета-информации. Также поисковые системы игнорируют символы пунктуации, 
которые являются важной составляющей шаблонов. Из-за этого извлечение документов, 
соответствующих шаблонам, не представляется возможным. Однако, первый шаг алгоритма 
(генерация шаблонов по кортежам) показал вполне удовлетворительные результаты. Также 
показал свою эффективность разработанный метод оценки шаблонов.
30

Список литературы
1. Nguyen Bach, Sameer Badaskar. A Survey on relation extraction 
(http://www.cs.cmu.edu/~nbach/papers/A-survey-on-Relation-Extraction-Slides.pdf)
2. Sergey Brin. Extracting Patterns and Relations from the World Wide Web 
(http://ilpubs.stanford.edu:8090/421/1/1999-65.pdf)
3. Eugene Agichtein, Luis Gravano. Snowball: Extracting Relations from Large Plain-Text 
Collections (http://www.mathcs.emory.edu/~eugene/papers/dl00.pdf) 
4. Dmitry Zelenko, Chinatsu Aone. Kernel Methods for Relation Extraction 
(http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.76.3487&rep=rep1&type=pdf)
5. Ryan McDonald, Fernando Pereira. Seth Kulick2Simple Algorithms for Complex Relation 
Extraction with Applications to Biomedical IE 
(http://www.seas.upenn.edu/~strctlrn/bib/PDF/relationACL2005.pdf)
6. Example of Single Pass Clustering Technique 
(http://maya.cs.depaul.edu/classes/ds575/single-pass.html)
7. Johan Hall. Probabilistic Part-of-Speech Tagger with Suffix Probabilities 
(http://www.hall.maltparser.org/cv/pub/msireport03015.pdf)
31

Document Outline

  • Аннотация
  • Введение
  • 1 Постановка задачи
  • 2 Обзор существующих методов
    • 2.1 Обучение с учителем (Supervised learning)
    • 2.2 Частичное обучение с учителем (Semi-supervised learning)
    • 2.3 Описание систем DIPRE и Snowball
    • 2.4 Вывод
  • 3 Исследование и построение решения задачи
    • 3.1 Базовая архитектура алгоритма
    • 3.2 Начальные данные
    • 3.3 Коллекция документов
    • 3.4 Генерация шаблонов
      • 3.4.1 Извлечение признаков
      • 3.4.2 Извлечение шаблонов
        • Алгоритм Single-pass Clustering
        • Определение частей речи
    • 3.5 Извлечение новых кортежей
    • 3.6 Оценка шаблонов и кортежей
      • 3.6.1 Оценка шаблонов
      • 3.6.2 Оценка кортежей
    • 3.7 Восстановление неполных кортежей
  • 4 Описание практической части
    • 4.1 Определение частей речи
    • 4.2 Выбор поискового веб-сервиса
    • 4.3 Взаимодействие с поисковым веб-сервисом
      • 4.3.1 Поиск веб-страниц
    • 4.4 Архитектура системы
      • 4.4.1 Диаграммы активности
        • Алгоритм кластеризации
        • Алгоритм извлечения кортежей
        • Алгоритм оценки шаблонов
        • Алгоритм оценки кортежей
      • 4.4.2 Диаграммы классов
        • Внутреннее представление шаблонов
        • Подсистема генерации шаблонов
        • Подсистема извлечения контекстов
        • Подсистема извлечения шаблонов
        • Подсистема поиска документов в текстовой коллекции
        • Подсистема форматирования результатов поиска документов
        • Итерация базового алгоритма
        • Фасад системы
    • 4.5 Тестирование
  • Заключение
  • Список литературы


Похожие:

Кибернетики iconНн и цифровых систем коммут
Кибернетики анан, д т н., академик                                                                 
Кибернетики iconВычислительной математики и кибернетики
Московского университета, ведущий учебный  и научный центр России в области фундаментальных ис
Кибернетики iconФакультет вычислительной математики И кибернетики 
Фгоувпо «Национальный исследовательский  технологический университет - Московский  институт стали и сплавов» 
Кибернетики iconФакультет вычислительной математики и кибернетики 
М. В. Ломоносова, расположенном  по  адресу:  119991,  Российская  Федерация,  Москва,  гсп-1,  Ленинские 
Кибернетики iconПоложение о факультете вычислительной математики И  кибернетики московского государственного университета имени М. В. Ломоносова
Факультет   в   установленном   порядке   в   соответствии   с   законодательством 
Кибернетики iconАвтореферат разослан  
...
Кибернетики iconИстория информатики и кибернетики в Санкт-Петер бурге 
В  течение  первых  двух  столетий  столичный  статус  города,  высокий  уровень 
Кибернетики iconРабочая программа по курсу «Экономическая кибернетика» Всего 155 часов в т ч. лекции 34 часа
Учебно-методическая помощь к процессу изучения основных разделов «экономической кибернетики»
Кибернетики iconИскусственный интеллект” и проблема субъективного в философии
Кибернетика имеет необычный, синтетический характер. В связи с этим до сих пор существуют различия в трактовке некоторых ее проблем...
Разместите кнопку на своём сайте:
TopReferat


База данных защищена авторским правом ©topreferat.znate.ru 2012
обратиться к администрации
ТопРеферат
Главная страница