Размещено на http://www.allbest.ru/

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

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

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

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

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

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

соискателя на степень магистра филологии

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

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

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

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

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

руководитель группы инструментов оценки качества, «Яндекс»

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



Содержание

Введение

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

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

1.2 Кластеризация как нечеткая классификация

2. Алгоритмы кластерного анализа

2.1 Оценка качества кластеризации

2.2 Кластеризация в лингвистике

3. Лингвистические основания автоматической кластеризации текстов по ключевым словам и конструкциям

3.1 Лингвистика конструкций и оценка связей в конструкциях

3.2 Автоматическое выделение ключевых слов в документах

4. Автоматическая кластеризация текстов в новостном корпусе с назначением ключевых слов - меток кластеров

4.1 Общие положения

4.2 Кластеризация

4.3 Выделение ключевых слов

4.4 Выделение конструкций

4.5 Выделение тематических меток в кластере новостных документов

Заключение

Список литературы



Введение

автоматический кластеризация метка биграммный

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

1.2 Кластеризация как нечеткая классификация

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

Чтобы сформулировать и другие параметры процедуры кластерного анализа, нам следует в первую очередь определить самое базовое понятие - классификацию.

Ограничения, определяющие классификацию

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

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

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

Формальное описание классификации

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

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

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

Нечеткая и зависимость параметра от выборки

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

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

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

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

Метрическое пространство объектов

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

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

В задаче разделения группы людей на дружественные компании удобнее использовать графовое представление пространства, объекты считая вершинами, а ребра устанавливая в случае выполнения условия (дружбы), возможно, с некоторым «весом». Тогда естественное расстояние между двумя объектами - длина кратчайшего пути между соответствующими вершинами графа.

Кластерный анализ как поиск оптимальной классификации

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

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

Особенности кластеризации

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

Кластеризация существенно зависит от заданной метрики и критерия качества . Но структура этой зависимости непредсказуема и универсальных параметров нет.

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



2. Алгоритмы кластерного анализа

Неявное задание критериев качества в алгоритме кластеризации

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

Выделяется как минимум три цели кластеризации [Воронцов 2015]:

5. описать структуру пространства объектов, разбивая его на классы похожих объектов и исследуя области сгущения (выделить темы),

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

7. выделить специфические объекты, не относящиеся ни к одному из кластеров.

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

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

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

Алгоритм выделения связных компонент

Выделение связанных компонент [Лагутин 2003] - один из простейших методов кластеризации. Пространство представляется в виде графа: вершинами являются объекты, а каждому ребру соответствует число - длина пути между соответствующими объектами. Фиксируется некоторый параметр и перекрываются все те ребра, длина которых больше параметра . Граф распадается на компоненты связности (между вершинами различных компонент не может быть пути, проходящего по ребрам графа). Каждая компонента и будет искомым кластером.

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

Алгоритм кратчайшего пути

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

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

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

Алгоритм ФОРЭЛ (Формальный элемент)

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

Этот алгоритм имеет множество вариаций и модификаций [Загоруйко 1999], которые отличаются способом объединения окрестностей формальных элементов в кластеры, способами изменения параметра , способами выбора начального положения формальных элементов, однако построены на одном и том же принципе. Значительно усложняется процедура кластеризации, если пространство нелинейно. Доказано, что он сходится за конечное число шагов.

Минимизация функционала качества

Мы уже описали, что задача алгоритма кластеризации - минимизировать некоторый критерий (функционал) качества, то есть подобрать оптимальную классификацию. Есть множество функционалов качества, среди которых нельзя назвать один «правильный». Отметим несколько естественных критериев.

Во-первых, среднее внутрикластерное расстояние должно быть как можно меньше:

С другой стороны, среднее межкластерное расстояние должно быть как можно больше:

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

Для поиска минимума функционала можно использовать один из оптимизационных алгоритмов, например, EM-алгоритм и др.

Разделение смеси распределений

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

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

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

Метод k-средних

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

Более формально, если - выборка пространства объектов, подбирается такой классификатор , что если - центры масс кластеров, то величина

достигает минимума.

Среднеквадратический разброс характеризует, насколько элементы одного кластера согласованы друг с другом. Однако такая метрика имеет ряд недостатков.

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

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

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

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

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

Метод k-средних по сути представляет собой упрощенную версию EM-алгоритма при разделении смеси: в первом случае каждому объекту однозначно соответствует единственный кластер, тогда как во втором случае каждому объекту соответствует некоторое вероятностное распределение на всем множестве кластеров.

Этот метод - один из самых используемых в прикладных задачах, существует немало модификаций, позволяющих учесть тонкие настройки оптимизации или формы кластеров. Он крайне чувствителен к начальным приближениям центров кластеров вплоть до того, что разные стартовые позиции могут привести к разным локальным минимумам функционала качества. С этой проблемой есть разные способы борьбы, один из которых - параллельный запуск нескольких случайных приближений. Иной метод, предназначенный для решения проблемы поиска глобального минимума, называют схемой инициализации k-means++. В качестве априорного приближения выбираются наиболее удаленные друг от друга точки. Доказано, что таким путем получается заведомо лучшая кластеризация, чем при генерации случайных центров.

Метод сигнала родства (Affinity Propagation)

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

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

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

Итак, вернемся к описанию самого алгоритма. Сигнал, передаваемый между элементами и , бывает двух типов: выразительность (responsibility) и характерность (availability). Выразительность определяет насколько по сравнению с другими элементами элемент , будучи представителем, выражает признаки элемента . Характерность , наоборот, отражает, насколько элемент характерен для элемента как для представителя класса. В результате алгоритма представители класса выбираются в том случае, если элементы с одной стороны имеют достаточно много близких элементов, с другой - не описывают друг друга.

Формально выразительность элемента как представителя элемента задается следующим образом:

где - степень близости, а характерность, в свою очередь:

Начальные значения , считаются нулями, параметры пересчитываются до сходимости.

Сдвиг среднего (Mean Shift)

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

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

Новое приближение центроида есть сдвиг прежней величины на функцию :

Спектральная кластеризация (Spectral clustering)

Еще один алгоритм, который работает на графовой структуре данных, которая, между прочим, часто используется в лингвистике. Матрица данных (попарных расстояний между объектами) при этом должна быть разрежена. Спектральный метод требует задания количества кластеров. Стоит заметить, что с увеличением их числа качество кластеризации заметно понижается.

В основе спектрального метода лежит алгоритм нормализованного разделения (normalized cuts), основанного на вычислении собственного вектора симметричного нормализованного лапласиана, которому соответствует второй с конца по величине собственное число. При разделении объектов максимизируется вес кластеров.

Спектральный метод особенно распространен при обработке изображений.

Иерархическая кластеризация

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

Иерархические алгоритмы бывают двух видов - нисходящие и восходящие. Первые делят пространство на всё более мелкие части.

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

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

где , , и - числовые параметры. Через это представление выражаются почти все разумные метрики пространства кластеров.

Чаще всего используются следующие способы вычисления расстояний :

(1) Расстояние ближнего соседа:

(2) Расстояние дальнего соседа:

(3) Среднее расстояние:

(4) Расстояние между центрами:

(5) Расстояние Уорда:

DBSCAN

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

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

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

2.1 Оценка качества кластеризации

На первый взгляд, оценка качества кластеризации - задача почти тривиальная - достаточно сосчитать количество ошибочно классифицированных объектов. Но это не вполне верно.

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

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

Рассмотрим ряд таких метрик первого типа.

Индекс Ранда

Итак, пусть имеется эталонная классификация объектов , с которой требуется сравнить прогнозную кластеризацию . Дополнительно определим:

· - число пар объектов, попавших в один класс и в один кластер,

· - число пар объектов, попавших в различные классы и различные кластеры,

· - общее число элементов.

Стандартный (смещенный) индекс Ранда (Rand index) задается по следующей формуле:

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

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

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

Этому условию отвечает несмещенный индекс Ранда (Adjusted Rand index), задаваемый следующим образом:

Он требует неоднократного запуска процесса кластеризации.

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

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

Взаимная информация

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

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

Как стандартная взаимная информация, так и ее нормированная модификация являются смещенными оценками.

Обозначим два разбиения пространства объектов U и V. Тогда энтропия неравномерности для каждого разбиения задается по формуле:

где - вероятность того, что случайный элемент попадет в класс . Аналогичная величина определяется и для :

при этом вероятность попадания случайного элемента в класс обозначается величиной .

Взаимная информация определяется формулой:

где - вероятность того, что случайный объект попадет в оба класса и .

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

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

Статистический метод усреднения был предложен в статье [Vinh, Epps & Bailey, 2009]. Нам понадобиться обозначить , . Тогда верна следующая оценка:



Используя эту величину, можно вычислить усредненную взаимную информацию:

Точность, полнота и V-мера

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

В статье [Rosenberg and Hirschberg, 2007] описываются два интуитивно понятных требования для оценки качества кластеризации.

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

Для эталонной классификации и прогнозной кластеризация обозначим величину, называемую условной энтропией разбиения:

а - энтропию класса, определенную по формуле:

где - общее число элементов, и - число элементов соответственно в классе и кластере . Аналогично зададим и .

Точность (homogeneity), характеризующая величину ошибки первого рода, т.е. количество элементов разных классов, попавших в один кластер, определяется по формуле:

Аналогично полнота (completeness), характеризующая, в свою очередь, величину ошибки второго рода - количество элементов разных классов, оказавшихся в одном кластере, - задается по формуле:

Их комбинация (-мера), учитывающая и величину полноты, и точности, является средним гармоническим:

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

С другой стороны, V-мера чувствительна по отношению к шуму (т.е. смещена). Случайное разбиение, таким образом, не всегда имеет нулевую метрику. Кроме того, все три метрики зависит от размера выборки, числа кластеров и структуры классификации.

Этой проблемой можно пренебречь, когда объем выборки более тысячи, а число кластеров менее 10.

Коэффициент силуэта

Как мы уже замечали, если эталонная классификация неизвестна, следует использовать один из коэффициентов качества, описанных ранее. Такие метрики, естественно, весьма условны. Во-первых, даже эталонная классификация не всегда им удовлетворяет. Во-вторых, всякий алгоритм кластеризации минимизирует тот или иной функционал качества и, являясь эталонным для одного, может и не являться таковым для другого.

Как бы то ни было, критерии качества весьма показательны - они позволяют понять, насколько полученное разбиение однозначно. Среди прочих используется и коэффициент силуэта.

Задается две величины:

a - среднее расстояние между данным элементом и всеми точками соответствующего кластера.

b - среднее расстояние между данным элементом и всеми точками другого ближайшего к нему кластера.

Сам коэффициент определяется по формуле:

Чаще всего его значение оказывается в пределах отрезка , однако это выполнено не всегда. Он характеризует, насколько кластеры отделены друг от друга, иными словами, насколько кластеризация однозначна.

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

Мы достаточно исследовали алгоритмы кластеризации, осталось сказать, как этот чисто математический метод нашел свое применение в лингвистике и позволил решить ранее, казалось бы, неподъемные задачи.

2.2 Кластеризация в лингвистике

Электронные корпусы текстов позволили широко использовать методы кластеризации для решения самых разных лингвистических задач. Классический пример применения кластеризации - статья [Schьtze, 1998], в которой комбинация аггломеративного и EM-алгоритма использовалась для снятия лексической неоднозначности. Основное положение подобных методов заключается в том, что схожесть контекста дает основание считать одинаковым значения обеих лексем. Подобные подходы использовались в работах [Lin, 1998, 2002] и по-прежнему актуальны [McCarthy и др., 2016]. Обзор работ по применению методов кластеризации в задачах снятия лексической неоднозначности можно найти в статье [Navigli, 2009].

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

Нашел свое применение кластерный анализ и в задаче построения тонального словаря [Четверкин, 2013] по корпусу текстов.

Как и в нашей работе, нередко методы кластеризации используются в задачах тематического моделирования [Basu, Murphy, 2013]. В частности, их используют для классификации научных текстов, насыщенных специальной терминологией [Savova и др., 2005].

Особую роль методы кластерного анализа играют в компьютерной текстологии. В рамках исследований по определению силы связей между списками рукописей на основе данных об узлах разночтений, проводимых А.А. Алексеевым, Е.Л. Алексеевой (Кузнецовой) и Д.М. Мироновой, используется вариант аггломеративного кластерного анализа, в процессе которого близкие тексты объединяются в стемму [Миронова 2016].

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



3. Лингвистические основания автоматической кластеризации текстов по ключевым словам и конструкциям

3.1 Лингвистика конструкций и оценка связей в конструкциях

Основные идеи лингвистики конструкций

Лингвистика конструкций - молодая отрасль науки, возникшая как альтернатива модульному, или атомарному подходу к явлениям языка и речи, опирающемуся на понятия основных единиц и отношений в рамках того или иного уровня языка. Ранее именно элементарные единицы и отношения привлекали внимание ученых, многим казалось, что именно в них кроются загадки естественного языка. Однако в языке и в текстах существуют конструкции - сложным образом организованные объекты, функционирующие как единое целое, возникающие в ходе взаимодействия и взаимопроникновения явлений морфологического, синтаксического, семантического и других уровней языка. В фокусе внимания лингвистики конструкций находятся воспроизводимые единицы текста, большие, чем слово: словосочетания разной степени устойчивости, фразеологизмы, идиомы, обороты, неоднословные целостности, явления «малого синтаксиса» и т.д. С одной стороны, этот класс явлений, наблюдаемых в корпусе, привлекает интерес компьютерных лингвистов, однако до сих пор представляет большую проблему в автоматической обработке корпусов текстов. Одна из причин заключается в том, что их природа и особенности функционирования не до конца изучены. Лингвистика конструкций предназначена как раз для того, чтобы отчасти восполнить возникший пробел.

Развитие лингвистики конструкций идет непростыми путями. Существует ряд отечественных и зарубежных теорий, среди которых обращают на себя внимание грамматика конструкций Ч. Филлмора [Fillmore 1988, Goldberg 1995, 2006, Tomasello 2003], теория лексических функций в рамках модели «Смысл <=> Текст» [Мельчук 1974/1999; ТКС 1984], конструктивный синтаксис Н.Ю.Шведовой [АК 1980], описание классов ядерных глагольных конструкций русского языка (моделей управления) и их трансформационных преобразований Ю.Д.Апресяна [Апресян 1967] и т.д. Есть немало последователей этого направления в современной российской лингвистике [Кузнецова 2007; Рахилина 2010; Овсянникова, Сай 2010; Оскольская, Овсянникова, Сай 2011].

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

Признанным основоположником зарубежной школы исследователей конструкций является Ч. Филлмор, разработчик теории падежной грамматики [Филлмор 1981] и глава разработчиков первой в мире базы данных лексических конструкций FrameNet [Fillmore 1982]. В своих работах Ч. Филлмор и его коллеги опирались на очень общее определение конструкции: это языковое выражение, в котором наличествуют формальные или содержательные аспекты, которые невозможно вывести из значения или формы составных частей. Простейшим примером такой конструкции может служить выражение железная дорога, общее значение которой, подобно паззлу, хоть и состоит из отдельных частей, в сочетании воспринимается как неделимое. Лексические конструкции, согласно теории Филлмора, представляют собой единство формы и содержания. Форма конструкции фиксируется, во-первых, уже заданными элементами, а во-вторых, грамматическими, семантическими и пропозициональными ограничениями, которые естественным образом накладываются на переменные ячейки конструкции. Как правило, значение лексической конструкции не выводится из составляющих, хотя возможна, как более широкая, так и более узкая трактовка понятия: от свободных сочетаний лексических единиц до фразеологизированных структур.

Конструкциями по Ч. Филлмору могут являться языковые единицы любого уровня, если они обладают формой и содержанием: их элементами могут быть и морфемы, и слова, и целые предложения [Рахилина 2010]. В классической работе Ч. Филлмора и коллег [Fillmore et al. 1988] обсуждается многоуровневый анализ лексической конструкции let alone («не говоря уже о…») и продемонстрировано, как следует анализировать конструкции в качестве единицы грамматического описания на синтаксическом, семантическом и прагматическом уровне. С точки зрения синтаксиса в конструкции есть два обязательных компонента (A) let alone (B), требующие восполнения за счет обязательного третьего компонента (С), без которого конструкция не является законченной: например, I doubt (C) he made colonel (A) let alone general (B). На семантическом уровне данная лексическая конструкция может быть описана шкалой, или иерархией пропозиций (от более сильной (to make colonel) к более слабой (to make general). Прагматическая интерпретация конструкции связана с выразительностью отрицания, носителем которого является компонент (С).

Грамматика конструкций позволяет по-новому объяснить целый класс языковых выражений. Так, в своей пионерской работе [Goldberg, 1995] А.Голдберг предложила отказаться от традиционного взгляда на рамки глагольных валентностей: вместо того, чтобы приписывать именным группам, заполняющим позиции в рамке глагольных валентностей, статус глагольных актантов, исследовательница призывает их рассматривать наравне с самим глаголом как компоненты глагольных конструкций. Тем самым, в семантическом анализе глагольных контекстов появляется принципиально новое решение проблемы неоднозначности и разграничения глагольных значений. Например, следуя этой точке зрения, мы признаем, что в глагольных конструкциях бросать камни и бросаться камнями реализуются два разных значения, но они ассоциируются не с глаголом (что заставило бы нас в словаре представить два разных глагола с разными рамками валентностей), а с глагольной конструкцией (точнее, с двумя разными конструкциями для одного и того же глагола, отличающимися лишь оформлением актантов) [Рахилина 2010]. Не менее успешным оказывается данный подход при оценке степень приемлемости различных сочетаний слов в рамках конструкций. Всё это позволяет говорить о том, что лексические конструкции более гибки в описании нюансов языка, чем традиционная глаголоцентрическая модель. [Рахилина 2010].

Статистический анализ структурной организации конструкций

В русле лингвистики конструкций существует течение, появившееся как ответ на запросы специалистов, работающих с корпусами текстов. Речь идет о так называемом коллострукционном анализе, исследовательской процедуре, разработанной А.Стефановичем и Ст. Грисом [Stefanowitsch, Gries, 2003] в качестве алгоритмической надстройки к теории. Коллострукционный анализ -- это многоступенчатая процедура статистического анализа структурной организации конструкций. Основными этапами коллострукционного анализа являются колексемный анализ, различительный колексемный анализ и ковариация колексем.

Колексемный анализ имеет целью количественно оценить степень тяготения лексемы к тому или иному слоту конструкции. Колексемный анализ позволяет оценить силу взаимодействия пары факторов в конструкции. В качестве факторов можно рассматривать, например, лексему и некий грамматический признак конструкции, а силу взаимодействия данных факторов оценить с помощью точного критерия Фишера. Например, таким образом можно определить тенденции в употреблении глагольных конструкций с формами прошедшего времени того или иного глагола: в случае с русским глаголом сказать можно вычислить общую частоту его встречаемости в корпусе, частоту употребления в форме прошедшего времени, а также частоту всех глагольных лексем в корпусе и частоту всех их форм прошедшего времени. Частота употребления глагола сказать в форме прошедшего времени оказывается выше, чем «среднестатистическая», что свидетельствует о тяготении данного глагола к конструкциям прошедшего времени (прежде всего, к конструкциям, вводящим прямую и косвенную речь) [Рахилина 2010].

Различительный колексемный анализ предназначен для того, чтобы сравнивать схожие конструкции и выяснять степень тяготения лексемы к той или иной конструкции из набора. В работе [Gries, Stefanowitch 2004] проводится сопоставительный анализ дитранзитивной конструкции и конструкции с to: (John sent Mary the book. John sent the book to Mary.). Семантический характер различий между двумя конструкциями подтверждается тем фактом, что они притягивают к себе разные наборы лексем. В рассматриваемом случае глагол give проявляет тенденцию к употреблению в дитранзитивной конструкции.

И наконец, ковариация колексем определяется для того, чтобы оценить, силу связи между лексемами - кандидатами на заполнение разных слотов одной и той же конструкции. А.Стефанович и Ст. Грис в качестве иллюстрации приводят анализ каузативной конструкции с into в английском языке [Stefanowitch, Gries 2005], где есть один фискированный компонент и два свободных: например, Newley had been tricked into revealing his hiding place. Оказывается, что семантика конструкции накладывает ограничения на комбинацию пар глаголов, которые могут заполнить слоты конструкции. В частности, в первом слоте конструкции могут быть глаголы со значением оказания давления или уловки. Во втором слоте следует ожидать глаголы, обозначающие неприятное или нежелательное действие.

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

...