Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
Мы, избиратели ЗАТО Александровск, доверили Вам представлять наши интересы в Совете депутатов ЗАТО Александровск и наделили Вас большими полномочиями ...полностью>>
'Конкурс'
Цель: повышение у обучающихся ЦДТ правовой культуры и информированности о главном Законе страны – Конституции Российской Федерации, формирование у под...полностью>>
'Документ'
о стоимости строительства квартиры в текущих ценах и размере внесенных средств для оплаты стоимости строительства квартиры участником долевого строите...полностью>>
'Программа'
В. .Кубасова 10 3 4- О.В.Кубасова Литературное чтение «Любимые страницы» « Планета Знаний» «Литературное чтение» Автор Э....полностью>>

Главная > Документ

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

Санкт-Петербургский государственный университет

Кафедра математической лингвистики

Направление: «Лингвистика»

Образовательная программа: «Прикладная и экспериментальная лингвистика»

Профиль: «Компьютерная лингвистика и интеллектуальные технологии»

Кластеризация языковых выражений в корпусе текстов на основе стохастического ранжирования

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

Букия Григория Теймуразовича

Научный руководитель

к.ф.н., доц. Митрофанова О.А.

Рецензент: Тарелкин А.В.,

руководитель группы инструментов

оценки качества, «Яндекс»

Санкт-Петербург

2016

Введение

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

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

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

Работа состоит из трех глав в соответствии с решаемыми задачами.

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

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

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

Для кластеризации документов используются методы, реализованные в библиотеке Scikit-learn языка Python. В ходе работы была написана программа, реализующая описанные эксперименты. Мы использовали наиболее популярные статистические критерии, необходимые для выделения ключевых слов и конструкций, описанные в монографии А.И. Кобзаря «Прикладная и математическая статистика».

Результаты, полученные в ходе выполнения данной работы, могут найти свое применение при разработке новостных порталов. Главная идея и отличительная особенность данной работы – двухэтапная кластеризация для выделения ключевых слов – основывается на идее условного разделения документов на два класса: «серьезные» и «несерьезные», лексика которых существенно отличается. Такое условие характерно именно для новостных корпусов.

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

  1. Основные идеи и методы
    кластерного анализа

    1. История кластерного анализа

Классификация была издревле известна человечеству. Прообраз этого понятия можно найти в первых строках книги Бытия (Быт. 1:21). Известны классические примеры классификации у Платона и Аристотеля [Новая философская энциклопедия, 2001], однако систематизация процесса классификации долгое время не проводилась. В начале XIX века французский ботаник Огюстен Декандоль [Брокгауз, Ефрон 1907] предложил свою теорию классификации и систематизации, названную впоследствии таксономией. Декантоль стремился классифицировать все существующие растения, объединяя их в однородные группы разных уровней, образующих иерархическую структуру (вид, род, семейство, класс, отдел). Данный метод вскоре получил широкое распространение и за пределами биологии. Теперь он положен в основу иерархических методов кластеризации.

Немецким биологом Ф. Гейнке был предложен метод группировки объектов по нескольким признакам. Всякий новый объект принадлежал той группе, к центру которой он ближе всего – идея, легшая в основу метода k средних.

Пионером применения базовых принципов кластеризации считается польский антрополог К. Чекановский. В 1913 году он предложил идею «структурной классификации» [Плюта 1980]: выделять компактные группы объектов. Для этого он разработал и оригинальный метод, применяемый при диагонализации признаковой матрицы.

В 1925 году советским гидробиологом П.В. Терентьевым был разработан метод корреляционных плеяд [Терентьев 1959] – это по-видимому первый алгоритм, направленный на выявление групп тесно коррелирующих признаков. Идеи этого алгоритма легли в основу многих пороговых алгоритмов на графах, например метода связных компонент.

Термин кластерный анализ впервые применил английский ученый Р. Трион [Trion 1939].

В 50-х годах ситуация стала развиваться значительно быстрее. Появились ЭВМ, способные обрабатывать данные гораздо быстрее человека. Алгоритмы усложнялись и совершенствовались, объемы данных росли и вскоре кластерный анализ завоевал прочное место в ряду прикладных дисциплин. Появилась возможность обрабатывать такое количество информации, которое прежде было человеку не под силу.

Следующие два десятилетия считаются золотым веком кластерного анализа. Тогда были получены основные результаты, изучен метод k-средних, иерархические процедуры, диагонализация и пр. Важную роль в этом сыграли и советские ученые [Мандель 1988].

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



Похожие документы:

  1. «Компьютерная лингвистика и интеллектуальные технологии» (1)

    Документ
    ... Кафедра математической лингвистики Направление: «Лингвистика» Образовательная программа: «Прикладная и экспериментальная лингвистика» Профиль: «Компьютерная лингвистика и интеллектуальные технологии» Параллельный конкорданс ...
  2. «Компьютерная лингвистика и интеллектуальные технологии» (2)

    Документ
    ...   Кафедра математической лингвистики Направление: «Лингвистика» Образовательная программа: «Прикладная и экспериментальная лингвистика» Профиль: «Компьютерная лингвистика и интеллектуальные технологии» Выявление информации ...
  3. Как единица устной речи: общая характеристика и прагматический потенциал

    Документ
    ... результаты исследования // Компьютерная лингвистика и интеллектуальные технологии: по материалам ежегодной ... . И. Б. Пересказывательность в русском языке // Компьютерная лингвистика и интеллектуальные технологии: материалы Международной конференции «Диалог ...
  4. Сводные данные международных мероприятий в области образования, науки и инноваций на 20 1 3 – 2015 гг

    Документ
    ... . ноябрь 2013 612 Международная конференция «Компьютерная лингвистика и интеллектуальные технологии» – Диалог 2013 Ин-т проблем ... техни-ческий конгресс по интеллектуальным системам и информационным технологиям Таганрогский технологический ин-т Южного ...
  5. Материал из Semantic Future

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

Другие похожие документы..