Использование новостных кластеров для улучшения извлечения информации из текстов


НазваниеИспользование новостных кластеров для улучшения извлечения информации из текстов
Дата02.11.2012
Размер113 Kb.
ТипДокументы
Использование новостных кластеров для улучшения извлечения информации из текстов


© Котельников Д.

МГУ

info@dmitriu.com


Аннотация

Новостные кластеры содержат разнообразные описания одного и того же события, изложенные разными авторами [9]. В работе описывается метод обогащения шаблонов, извлекающих информацию из текста, за счет нахождение в новостном кластере нескольких близких по содержанию предложений, в которых хотя бы в одном удалось обнаружить извлекаемое событие. Полученные таким образом примеры могут быть использованы для машинного обучения.

  1. Введение

Существующие методы извлечения информации из текста, можно разделить на два принципиально различных класса: методы, основанные на знаниях и методы машинного обучения [12].

При использовании методов, основанных на знаниях, шаблоны или правила выделения событий задаются экспертами на основе анализа текстов подлежащих обработки. Основным препятствием использования машинного обучения является высокая трудоемкость создания системы и невозможность её адаптации для извлечения новых событий [5, 10]. Да и человек зачастую не может предусмотреть всевозможные ситуации описания извлекаемого события или применения правила, что приводит к снижению полноты и точности выделения событий.

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

Одним из методов, позволяющих снизить проблему получения размеченных данных для обучения, является кластеризация похожих фрагментов текста для улучшения качества извлечения закономерностей [8].

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

В данной работе исследуется вопрос о наращивании обучающего множества для извлечения информации из потока новостей за счет двойной кластеризации. Сначала новостные сообщения близкой тематики объединяются в новостные кластеры, затем предложения, в которых обнаружены шаблоны извлекаемой информации, служат центрами для кластеров схожих предложений, в которых такие шаблоны не обнаружены.

В качестве базового инструмента извлечения информации используется программа RCO Fact Extractor [11], кластеризация документов производится новостным кластеризатором НИВЦ МГУ [14].

2. Обзор работ по исследуемой тематике

Одним из первых исследований в области наращивания обучающего множества, используя неразмеченные примеры, является работа Blum A. и Mitchell T. [3]. Алгоритм «совместного» обучения применяется, когда обучающее множество можно описать двумя различными наборами признаков, причем каждого достаточно для успешной классификации объектов. Машинное обучение производится на обоих наборах одновременно, после чего построенная процедура классификации применяется на неразмеченном корпусе и все примеры, результаты которых для обоих признаковых пространств совпадают, становятся обучающими.

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

В системе Snowball [1] размеченная коллекция предложений используется для формирования шаблонов и получения фактов наличия связи между двумя словами. Шаблоны определяются тремя векторами соответствующими левому, правому и среднему контекстам, на которые разбивают предложение два слова. Элементами векторов являются значения функции от частоты каждого слова во фрагменте предложения, умноженные на некоторый вес. В неразмеченном тексте производится поиск слов, наличие связи между которыми установлено и найденные предложения используются для формирования новых шаблонов. На каждой итерации производится проверка получившихся правил на извлечение фактов, противоречащих уже установленным из более ранних шаблонов или обучающей выборки.

В публикациях [2,7] дается описание методов, применяющих кластеризацию, для автоматического извлечения информации из частично структурированных HTML документов. Система обрабатывает предварительно размеченную коллекцию HTML документов, кластеризует их по содержанию одинаковой структуры. Получившиеся кластеры используются для формирования правил извлечения информации, на основе сопоставления положения извлекаемых элементов в документах кластера.

3. Исходные данные

В качестве исходных данных используются результаты работы демонстрационной версии программы извлечения информации ― RCO Fact Extractor, работа которой основана на инженерном методе составления шаблонов для извлечения информации из текстов [13].

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

Так, фрейм Получение кредита (Кредитор, Получатель, Сумма) извлекается из предложения (*) и не извлекается из предложения (**):

(*) Краткосрочный государственный кредит в размере $4 миллиарда получит компания Chrysler.

(**) Chrysler получил от Минфина США кредит в 4 млрд. долларов.


Е

сли рассмотреть новостной кластер, объединяющий несколько тематически близких сообщений, то в нем часто оказывается достаточное количество близких по смыслу предложений, включающих как предложения, в которых некоторый фрейм распознан вполне успешно, так и предложения, в которых этот же фрейм не распознан совсем или распознан частично. Именно эту вторую группу предложений можно использовать для наращивания шаблонов для распознавания данного фрейма.

4. Описание методов и алгоритмов

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

При своей работе системы извлечения информации не только определяют наличие в текстовом фрагменте некоторого события (фрейма), но и выделяют связанную с этим событием информацию (слоты фрейма).

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

4.1 Метод «количество слотов»

В методе отбираются предложения, в которых количество найденных слотов больше некоторого порога.

Исследования показали, что даже для предложений, в которых найдено около 3-4 слотов, может не описываться ситуации получения кредита, поэтому нужно было разработать дополнительные меры близости содержания предложений.

4.2 Метод «косинуса угла»

В данном алгоритме для каждого предложения кластера вычислялся косинус угла между вектором слов данного предложения и вектором слов предложения, в котором анализатор обнаружил наличие некоторого события по формуле:

4.3 Метод «TF*IDF»

В этом алгоритме также для оценки близости двух предложений используется мера косинуса, но вместо слов в векторе предложения используется значение меры TF*IDF слова [6], вычисляемое по формуле: , где

N — количество кластеров;

tf — частота слова в кластере;

df — количество кластеров, содержащих данное слово;

dl — количество слов в кластере

dlavg — средняя число слов в кластере.

4.4 Объединение методов

Так же была произведена проверка работы объединенных алгоритмов, в которых при отборе предложений учитывались несколько факторов близости предложений.

5. Эксперименты

Для проведения экспериментальных исследований была выбрана тематика извлечения информации о выдаче кредитов. В проверке работы использовалась коллекция новостных кластеров НИВЦ МГУ им. Ломоносова. Обработка текстов и извлечение информации производилась с помощью библиотеки RCO Fact Extractor [11], которая выделяет предложения, слова с различными атрибутами и связи между ними, а также выявляет наличие фактов различного типа.

В RCO Fact Extractor уже имелся шаблон для выделения фрейма кредита, созданный экспертами RCO. Шаблон обладал высокой точность извлечения информации, но был неустойчив к любым изменениям в позиции слов в предложении, из-за чего обладал низкой полнотой. Из новостных документов выделялись следующие данные о кредите (слоты фрейма): получатель, кредитор, сумма, дата получения, цель, место получения, описание события получения кредита.

Первоначально была произведена обработка текста новостных кластеров библиотекой RCO FX, и из всех кластеров были отобраны только те, в которых хотя бы в одном из документов был выделен фрейм кредита. Для каждого кластера анализатор обнаружил в среднем 5-6 ситуаций получения кредита.


Среднее отношение количества слотов, которые получились после объединения всей извлеченной информации из разных документов кластера, с максимальным количеством слотов найденных в каждом документе по отдельности составило 86.56 процентов. Это говорит о том, что кластер помогает обогатить информацию о событии, склеивая её из разных кусочков, описанных в различных документах кластера.

Для каждого предложения кластера было получено количество слотов, содержащихся в этом предложении.

Экспериментальным путем для каждого алгоритма подбиралось значение порога для меры близости двух предложение и количества слотов, содержащихся в предложении, так чтобы точность на тестовой выборке была выше 90%.

Так как в кластере выделялось несколько предложений, содержащих фрейм кредита, то из всех значений меры, выбиралось наибольшее.

В результате были подобраны минимальные значения порогов для следующих алгоритмов: «количество слотов» ― 4; «косинус угла» ― 0.75; «TF*IDF» ― 0.95; «TF*IDF и количество слотов» ― 0.75 и 3 соответственно; «количество слотов и косинус угла» ― 3 слота и 0.4 или 2 слота и 0.8.

Таким образом, было получено множество предложений, с указанием для каждого из них набора слотов фрейма кредита, которые содержатся в предложении.

Результаты работы алгоритмов проверялись на коллекции из 120 новостных кластеров содержащих ~ 1100 текстовых документов, из которых вручную были отобраны предложения, содержащие информацию о кредите.

Таблица 1

Эффективность алгоритмов нахождения обучающих примеров с точностью больше 90% (результаты упорядочены по убыванию F-меры)


Имя

Точность

Полнота

F-мера

Косинус угла и количество слотов

0,901575

0,275240

0,421731

TF*IDF и количество слотов

0,901840

0,176683

0,295477

Количество слотов

0,932203

0,132212

0,231579

Косинус угла

0,966667

0,034856

0,067285

TF*IDF

0,900000

0,013221

0,025761

5. Выводы и обсуждение результатов

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

Литература

  1. Agichtein E., Gravano L., Snowball: Extracting Relations from Large Plain-Text Collections. Proceedings of the Fifth ACM International Conference on Digital Libraries, 2000.

  2. Ashraf F., Ozyer T., Alhajj R. Employing Clustering Techniques for Automatic Information Extraction From HTML Documents, IEEE, 2008.

  3. Blum A., Mitchell T. Combining Labeled and Unlabeled Data with Co-Training. Proceedings of the eleventh annual conference on Computational learning theory, 1998.

  4. Cheng N., Wei L., Jihong D. A Bootstrapping Approach to Named Entity Classification Using Successive Learners. Proceedings of the 41st Annual Meeting on Association for Computational Linguistics, 2003.

  5. Greenwood M., Stevenson M. Improving Semi-Supervised Acquisition of Relation Extraction Patterns. Workshop On Information Extraction Beyond The Document, 2006.

  6. Hatzivassiloglou V., Klavans J., Holcombe L.,

Barzilay R., Min-Yen Kan, McKeown R. SIMFINDER: A Flexible Clustering Tool for Summarization. Proceedings of the NAACL Workshop on Automatic Summarization, 2001.

  1. Le Phong Bao Vuong L., Xiaoying Gao. Using Clustering for Web Information Extraction. Advances in Artificial Intelligence, 2007.

  2. Moens M. Information extraction: Algorithms and Prospects in a Retrieval Context. Springer, 2006.

  3. Naughton M., Kushmerick N., Carthy J. Clustering sentences for discovering events in news articles. ECIR, 2006.

  4. Patwardhan S., RiloffLearning E. Domain-Specific Information Extraction Patterns from the Web. Workshop On Information Extraction Beyond The Document, 2006.

  5. RCO Fact Extractor. http://rco.ru/product.asp?ob_no=1131

  6. S. Sarawagi. Information Extraction. Foundations and Trends in Databases, 2008.

  7. Киселев С.Л., Ермаков А.Е., Плешко В.В. Поиск фактов в тексте естественного языка на основе сетевых описаний.
    Компьютерная лингвистика и интеллектуальные технологии: труды Международной конференции Диалог’2004. – Москва, Наука, 2004.

  8. Лукашевич Н.В., Добров Б.В. Автоматическое аннотирование новостных кластеров на основе тематического представления. Компьютерная лингвистика и интеллектуальные технологии. По материалам ежегодной международной конференции «Диалог» Периодическое издание Выпуск 8 (15) 2009, в печати.

Using News Clustering to Improve Information Extraction


Kotelnikov D.


News clusters contain various descriptions of the same event stated by different authors. This article is dedicated to the improvement of the information extraction technique. This method is based on searching of several relevant sentences in the news clusters. These sentences are selected by indicator of presence of extracted events. The examples which were received by this method can be used for machine learning.


Добавить документ в свой блог или на сайт

Похожие:

Разместите кнопку на своём сайте:
cat.convdocs.org


База данных защищена авторским правом ©cat.convdocs.org 2012
обратиться к администрации
cat.convdocs.org
Главная страница