Содержание к диссертации
Введение
1. Обзор методов и программ количественного анализа текстов и постановка задач исследований и разработок 10
1.1. Проверка текстов на близость стилей или однородность по стилю 10
1.2. Кластеризация текстов 14
1.3. Классификация текстов 18
1.4. Программные продукты 27
1.5. Постановка задач исследований и разработок 32
2. Методы и алгоритмы сравнения стилей текстов по частотным признакам 35
2.1. Сравнение стилей текстов по частотам появления признаков на основе статистических критериев 35
2.1.1. Гипергеометрический критерий (двусторонний точный критерий Фишера) 35
2.1.2. Критерий хи-квадрат 37
2.1.3. Сравнение распределений по критерию хи-квадрат 39
2.1.4. Метод кластеризации текстов по частотным признакам 39
2.1.5. Примеры анализа текстов 42
2.2. Классификация текстов с помощью деревьев решений 45
2.2.1. Алгоритм построения дерева решений 46
2.2.2. Оверфиттинг и отсечение 48
2.2.3. Классификация по авторству. Влияние объемов фрагментов 50
2.2.4. Классификация по авторству. Влияние порога отсечения 59
2.2.5. Классификация по жанровым типам 62
2.2.6. Классификация по источникам газет 66
2.2.7. Оценка информативности признаков 68
2.3. Классификация текстов с помощью метода Хмелева и его модификаций 72
2.3.1. Проверка марковости текстов 73
2.3.2. Мера Хмелева и альтернативные ей меры 80
2.3.3. Классификация по авторству. Влияние объема фрагментов 82
2.3.4. Классификация по жанровым типам 92
2.3.5. Классификация по источникам газет 96
2.4. Классификация текстов с помощью нейронных сетей прямого распространения 100
2.4.1. Нормализация данных 101
2.4.2. Алгоритм обучения 102
2.4.3. Классификация по авторству. Вычислительные эксперименты 104
2.5. Сравнение рассмотренных методов классификации 112
2.6. Выводы 116
3. Инструментарий анализа стилей текстов «СтилеАнализатор» 120
3.1. Язык задания частотных признаков 120
3.1.1. Схема извлечения частотных признаков текстов 121
3.1.2. Формат запроса. Язык задания частотных признаков 124
3.1.3. Устройство интерпретатора языка 128
3.2. Общая схема количественного анализа текстов в программе «СтилеАнализатор» 135
3.3. Работа с вертикальным текстом 137
3.4. Предварительная обработка текстов 140
3.5. Извлечение частотных признаков текстов 140
3.5.1. Пользовательский интерфейс 141
3.5.2. Привязка количественных данных к фрагментам текстов 143
3.6. Предварительная обработка количественных данных 144
3.7. Анализ частотных данных 146
3.8. Выводы 150
Заключение 151
Список использованной литературы
- Кластеризация текстов
- Гипергеометрический критерий (двусторонний точный критерий Фишера)
- Классификация текстов с помощью метода Хмелева и его модификаций
- Формат запроса. Язык задания частотных признаков
Введение к работе
Текст, как и многие другие виды представления информации, поддается анализу. Одной из возможных форм анализа текста является анализ его стиля.
Проблема анализа и сравнения стилей текстовых произведений является актуальной в филологических дисциплинах, изучающих стилистические особенности как текстов вообще, так и языка литературных произведений различных жанров, различных авторов, языковых диалектов и т.д., а также в психологии и теории искусственного интеллекта при изучении и моделировании мыслительной деятельности. Многие практические задачи сравнения стилей текстовых документов возникают в судебной практике и криминалистике.
Сравнивать стили текстов приходится в исторических исследованиях, чтобы определить время написания того или иного исторического документа, установить личность его автора. Наиболее известные среди этих исследований - атрибуция писем и эпиграмм Платона, анализ двенадцати спорных статей из «Бумаг республиканцев» (Federalist papers), автором которых может быть как Дж. Мэдисон, так и А. Гамильтон.
В литературоведческой практике сравнение стилей также необходимо для установления спорного авторства литературных произведений. Широко известен, например, спор об авторстве «Тихого Дона», произведений Шекспира. Не установлено точно авторство некоторых анонимных и псевдонимных публицистических статей, автором которых предположительно является Ф.М. Достоевский, ставится под сомнение авторство некоторых текстов М. Е. Салтыкова-Щедрина и т.д.
Алгоритмы сравнения стилей текстов важны также для информатики, поскольку с их помощью можно улучшить качество классификации и упорядочивания текстовых коллекций, что чрезвычайно актуально для постоянно расширяющейся сети Интернет.
Сравнение стилей текстов проводится, как правило, на основе совокупности ряда признаков («авторских инвариантов» и т.п.), отражающих свойства стилей текстов. Некоторые из этих признаков носят качественный характер и плохо поддаются формализации, хотя могут и обладать мощной разделительной способностью. Такие признаки условно назовем вербальными. Многие другие признаки (например, частоты появления определенных слов, знаков препинания, различных буквосочетаний) могут быть формализованы, что позволяет производить с их помощью количественный (частотный) анализ текстов.
АКТУАЛЬНОСТЬ РАБОТЫ
На базе сравнения стилей текстовых произведений решаются задачи проверки текстов на близость стилей или однородность по стилю, задача классификации и задача кластеризации текстов.
Проверкой текстов на близость стилей, в частности, занимались Mendenhall Т.С. [109], Морозов Н.А. [21], Фоменко Т.Г. и Фоменко В.П. [48]. Исследования по проверке однородности текстов проводили Morton A.Q. [112], Ashford Т. [68], Farringdon J.M. [86], Ковалевский А.П. [12] и др.
В рамках задачи кластеризации текстов в существующих публикациях рассмотрены различные известные методы кластеризации (метод k-средних, метод ближайшего соседа, метод центроидов, нейронные сети SOM и др.), а также их модификации. Иерархические методы кластеризации, в частности, использовали в своих работах Leouski A.V., Croft W.B. [105], Beil F., Ester M., Xu X. [71], Cutting D. R., Karger D. R., Pedersen J. 0., Tukey J. W. [79], Tantrum J., Muraa A., Stuetzle W. [125]. Неиерархические методы кластеризации текстов исследовали в своих работах Zhong S., Gosh J. [135], Choudhary, В., Bhattacharyya, P. [77], Steinbach M., Karypis G., Kumar V. [124] и др.
Наибольшее число работ в области сравнения стилей текстов посвящено задаче классификации текстов. В имеющихся публикациях рассматриваются различные методы классификации текстов. Среди них нейронные сети (Matthews R., Merriam Т. [107, ПО], Kjell В. [100, 101,102], Tweedie F.J., Singh S., Holmes D.I. [131], Lowe D., Matthews R. [106]), метод опорных векторов (de Vel О. [81], Joachims Т. [97], Diederich J. J. [82]), дискриминантный анализ (Baayen H., Tweedie F. [69], Patton J.M., Can F.A [116], Peng R.D., Hengartner N.W. [117]), метод сжатия данных (Frank E., Chui C, Witten I.H. [88], Teahan W.J. [126, 127], Хмелев Д. [49], Benedetto D. [73]), метод Хмелева Д. [18, 50], методы, основанные на извлечении правил (Apte С, Damerau F., Weiss S. [66, 67], Oakes M. [114], Holden N., Freitas A.A. [92]), и др.
Существует ряд программных систем, позволяющих производить разнообразные виды анализа текстов. Наиболее известными среди таких систем являются «Лингвоана-лизатор» Д.Хмелева [50], информационная система «СМАЛТ» [35, 37, 38], система «ВААЛ» 9.0 [34], PolyAnalyst 4.6 [39] (с модулем для работы с текстом TextAnalyst [40]), система DICTUM [103].
Несмотря на множество работ по сравнению стилей текстов, имеется ряд областей исследований, которые не затрагивались в других публикациях.
В сфере проверки текстов на близость стилей и кластеризации текстов неисследованным остается применение мер близости, основанных на точных статистических критериях сравнения частот появления признаков стилей.
В сфере классификации текстов остаются недостаточно исследованными зависимости качества классификации различными методами от объемов фрагментов, от числа классов. Нет исследований по сравнению качества классификации по различным сложным (в том числе грамматическим) признакам на размеченном и выверенном текстовом материале, исключающем ошибки разметки.
Несмотря на то, что в ряде работ говорится об использовании свойств марковости текста, никем не проводилось исследование того, является ли последовательность символов текста действительно реализацией простой цепи Маркова.
Все существующие программные реализации методов анализа текстов используют встроенный набор признаков стилей текстов, что не позволяет гибко менять признаки в ходе исследований и исключает возможность задания признаков пользователем, а не разработчиком. В частности, это относится и к одной из лучших программных реализаций систем классификации текстов - «Лингвоанализатора» Хмелева. Поэтому актуальным является создание механизма (лучше всего специализированного языка), обеспечивающего возможность задания пользователем любых желаемых признаков стилей текстов из достаточно широкого класса признаков.
Наконец, имеющиеся программные реализации систем анализа текстов не ориентированы на комплексное исследование и сравнение стилей текстов (для разных задач анализа текстов, с использованием различных методов их решения, различных частотных признаков, различного текстового материала). Поэтому актуальным является создание программной системы, позволяющей проводить подобные исследования.
ЦЕЛЬ РАБОТЫ
Целью работы является разработка алгоритмов и инструментария для сравнения стилей текстовых произведений. В рамках указанной цели поставлены и решены следующие задачи:
1) исследование качества работы ряда существующих методов математической статистики и искусственного интеллекта для сравнения стилей текстовых произведений по частотным признакам, задаваемым пользователем;
2) модификация известных и разработка новых мер сравнения частот для задач кластеризации и классификации текстов;
3) создание языка задания частотных признаков стилей текстовых произведений и его интерпретатора;
4) разработка и реализация программного комплекса для сквозного количественного анализа текстов от их первичной обработки до получения решений.
МЕТОДИКА ИССЛЕДОВАНИЙ
Для решения задач, обеспечивающих достижение поставленной цели, использовались методы математической статистики, искусственного интеллекта, а также методы объектно-ориентированного программирования.
НАУЧНАЯ НОВИЗНА РАБОТЫ
1. Предложены новые подходы для сравнения стилей текстов с использованием гипергеометрического критерия (двустороннего точного критерия Фишера) и критерия хи-квадрат по отдельным частотным признакам текстов, совокупности признаков, а также по их распределению.
2. Предложен новый подход к кластеризации текстов с использованием ранее не применявшихся в области обработки текстов таких мер сходства, как «частота рассогласования» (сложный признак) и интегральная мера рассогласования (совокупность признаков), получаемых на основе проверки гипотез о сходстве стилей текстов по частотным признакам.
3. Предложены модификации известного метода Хмелева классификации текстов по авторскому стилю с использованием для оценки расхождения частот мер Кульбака и хи-квадрат, а также модульных мер. Показано, что мера Хмелева является частным случаем меры Кульбака.
4. Доказана несостоятельность гипотезы о том, что последовательность символов текста обладает свойствами простой цепи Маркова.
5. Разработан оригинальный язык задания частотных признаков, позволяющий декларировать признаки и представлять их в виде шаблонов, пригодных для автоматического преобразования текстов к набору частот.
ПРАКТИЧЕСКАЯ ЦЕННОСТЬ РАБОТЫ
Разработанный программный комплекс «СтилеАнализатор» для анализа стилей текстов, обеспечивающий полный цикл проведения количественного анализа текстов, включающий предварительную обработку текстов, извлечение частотных признаков, их обработку и представление результатов в наглядном для человека виде, может быть ши роко использован специалистами в различных областях знаний (лингвистами, филологами, криминалистами, историками).
ПОЛОЖЕНИЯ, ВЫНОСИМЫЕ НА ЗАЩИТУ
1. Новые подходы для сравнения стилей текстов с использованием гипергеометрического критерия и критерия хи-квадрат по отдельным частотным признакам текстов, совокупности признаков, а также по их распределению.
2. Новый подход к кластеризации текстов на основе проверки гипотез о равенстве частотных признаков стилей текстов с использованием таких мер сходства, как «частота рассогласования» и интегральная мера рассогласования.
3. Модификации известного метода Хмелева с использованием для оценки расхождения частот мер Кульбака и хи-квадрат, а также модульных мер.
4. Доказательство несостоятельности гипотезы о том, что последовательность символов текста обладает свойствами простой цепи Маркова.
5. Язык задания частотных признаков стилей текстов.
6. Программный комплекс «СтилеАнализатор» для анализа стилей текстов.
ВНЕДРЕНИЕ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ
Реализованный программный комплекс внедрен в лаборатории общей и компьютерной лексикологии и лексикографии филологического факультета МГУ.
ПУБЛИКАЦИИ ПО РАБОТЕ
Основное содержание работы отражено в 16 публикациях, в т.ч. в 11 статьях [25, 29-31,45,54-55, 57-60] и в 5 докладах на конференциях [26-28, 44,56].
АПРОБАЦИЯ РАБОТЫ
Результаты работы докладывались и обсуждались на следующих конференциях:
1. IV Межвузовская конференция студентов аспирантов и молодых ученых «Наука и образование», Томск, 2000.
2. V Общероссийская межвузовская конференция студентов, аспирантов и молодых ученных «Наука и образование», Томск, апрель 2001 г.
3. Нейроинформатика и ее приложения: XII Всероссийской семинар, Красноярск, октябрь 2004 г.
4. Информационные технологии и математическое моделирование: III Всероссийская научно-практическая конференция, Анжеро-Судженск, декабрь 2004 г.
5. XLIII Международная научная студенческая конференция «Студент и научно-технический прогресс»: Информационные технологии, Новосибирск, апрель 2005 г.
6. XI Международная научно-практическая конференция студентов и молодых ученых «Современные техника и технологии СТТ 2005», Томск, марта - апрель 2005 г.
7. IX Международная конференция студентов, аспирантов и молодых ученых «Наука и образование», Томск, апрель 2005 г.
8. Всероссийская научная конференция Квантитативная лингвистика: исследования и модели (КЛИМ - 2005), Новосибирск, июнь 2005 г.
9. Информационные технологии и математическое моделирование: IV Всероссийская научно-практическая конференция, Анжеро-Судженск, ноябрь 2005 г.
БЛАГОДАРНОСТИ
Автор выражает глубокую благодарность научному руководителю Поддубному В.В. за сотрудничество, помощь и поддержку в работе, Тютереву В.В. за сотрудничество на ранних этапах работы, Поликарпову А.А., Кукушкиной О.В., Макарову А.Г. за обсуждение результатов работы и предоставление грамматически размеченного газетного корпуса, Сущенко СП., Фукс И.Л. за поддержку, СкворцоваА.В. за помощь и ценные советы, ФедякинаМ.В. за предоставление набора газетных текстов и обсуждение результатов.
Кластеризация текстов
Задача кластеризации текстов состоит в следующем. Имеется некоторый набор текстов. Необходимо сгруппировать эти тексты в соответствии с их схожестью (например, по стилям). Группировка может быть одноуровневой («плоской», с выделением кластеров, каждый из которых включает только тексты), либо иерархической, когда кластеры, объединяющие наиболее похожие тексты, сами объединены в кластеры, а кластеры кластеров - в другие кластеры и т.д. Принадлежность текста к кластеру на определенном уровне иерархии может быть однозначной (hard clustering - каждый текст принадлежит только одному кластеру), или неоднозначной (soft clustering - текст может принадлежать нескольким кластерам).
Тексты для кластеризации представляются, как правило, в виде векторов значений признаков [11, 71, 77, 79, 105, 115, 124, 125], но встречаются и другие представления текстов [11, 39, 78, 133, 132]. Имеются подходы, в которых исходными данными для кластеризации являются не векторы текстов, а векторы признаков (например, слов), где каждый компонент вектора соответствует одному тексту (например, Word-base soft clustering - WBSC [104]). В рамках данной работы нас интересуют подходы, использующие векторы значений признаков.
В качестве значений признаков, включенных в векторы, чаще всего выступают частоты появления определенных слов (или их нормальных форм) в текстах. Альтернативой частотам слов могут быть индикаторы появления слов (0 и 1) или значения, учитывающие среднюю встречаемость слова во всех текстах. В качестве меры близости текстов, представленных векторами значений признаков, обычно используется скалярное произведение векторов.
Для кластеризации текстов по векторам значений признаков в основном используются известные методы кластерного анализа [4, 80, 96] и искусственного интеллекта [47]: иерархические (метод ближайшего соседа, метод дальнего соседа, метод средней связи, центроидный метод и др.) и неиерархические ( -средних, ЕМ-метод - Expectation maximization, SOM-сети и др.), а также их модификации.
Суть иерархических методов кластеризации заключается в многократном сравнении близости в многомерном признаковом пространстве всех пар текстов и построении на основе этих сравнений иерархического описания (например, дерева кластеризации - дендрограммы). Существуют варианты методов, строящие иерархию сверху вниз (divisive - начальным кластером являются все тексты) и снизу вверх (agglomerative -первоначально каждый текст является отдельным кластером). Различие методов заключается также в способе измерении расстояния между кластерами. Достоинством этой группы методов является богатое представление результатов кластеризации: уровни иерархии дендрограммы позволяют видеть многие закономерности объединения данных, что особенно удобно при анализе таких сложных объектов как тексты. Недостатком иерархических методов является большая трудоемкость (0(N2) или 0(N2) в зависимости от метода, где N - число текстов), что затрудняет их использование при кластеризации большого числа текстов.
Методы иерархической кластеризации рассматриваются, например, в работе Леу-ски и Крофт (Leouski A.V., Croft W.B.) [105]. В частности, в ней применяется метод ближайшего соседа, методы CLASSIT [88], AGGLOM [87], InClass для кластеризации статей из "Wall Street Journal" за 1987 год.
В работе Beil F., Ester М., Xu X. [71], например, предлагается два метода кластеризации - FTC (Frequent Term-based text Clustering) для «плоской» кластеризации и HFTC (Hierarchical FTC) для иерархической кластеризации - и приводится их сравнение с двумя известными модификациями метода -средних. Сравнение проводится на различных корпусах текстов (базы веб-документов, статей новостного агентства Рейтер, газет из медицинских журналов и др.).
Другим примером кластеризации документов на основе иерархических методов является работа Cutting D. R., Karger D. R., Pedersen J. 0., Tukey J. W. [79], в которой рассматривается новый подход к извлечению текстовой информации на основе кластеризации текстов. Авторы предлагают в качестве альтернативы стандартному поиску подход пролистывания (browsing) текстов, так называемое рассеивание/сбор (scatter/gathering). Подход состоит в следующем. Первоначально проводится кластеризация всех имеющихся текстов. Затем пользователь выбирает отдельные кластеры текстов, которые ему наиболее интересны, и проводится повторная кластеризация выбранных групп. И т.д. до нужной степени детализации. В работе рассматривается кластеризация с помощью двух методов: метода «расслоения» (fractionation) и метода «картечи» (buckshot). Суть данных методов состоит в том, чтобы не производить кластеризацию всех текстов сразу, а прежде разбить их на подмножества и производить кластеризацию подмножеств. За счет такого разбиения достигается большая скорость обработки. Различие методов состоит в способе разбиения на подмножества (детерминированном или случайном). Кластеризация подмножеств производится по известному методу средней связи. В качестве меры сравнения векторов признаков текстов используется их скалярное произведение.
Суть неиерархических методов кластеризации заключается в соотнесении положений текстов с положениями центров кластеров в многомерном признаковом пространстве и постепенной корректировке этих центров. В базовых алгоритмах начальные центры и число кластеров, как правило, задается пользователем, в модифицированных, более сложных (например, MDL [76]), некоторые из этих параметров могут определяться автоматически.
Неиерархические методы, в отличие от иерархических, допускают неоднозначное отнесение текстов к кластерам. По такому принципу, например, работает ЕМ-метод [80]. Каждый вектор наблюдаемых значений признаков текста в данном методе рассматривается как реализация многомерной случайной величины, «сгенерированной» каким-то кластером и распределенной по нормальному закону. Если параметры распределений известны, можно вычислить условную вероятность принадлежности вектора значений признаков (т.е. текста) к тому или иному «генератору» (кластеру).
Достоинствами неиерархических методов является линейная трудоемкость (0(N), где TV- число текстов) и возможность вероятностного соотнесения текстов к кластерам. Недостатком - более бедное, по сравнению с иерархическими методами, представление результата.
Методы неиерархической кластеризации текстов рассматриваются, например, в работе [135], в которой производится сравнение 12-и различных подходов к кластеризации (4 стратегии объединения по отношению к 3-м моделям текста). В качестве материала для кластеризации используется набор из 20 электронных конференций UseNet [64].
Гипергеометрический критерий (двусторонний точный критерий Фишера)
Для применения данного критерия представим информацию о текстах в виде таблицы, содержащей частотные данные. Строки таблицы соответствуют фрагментам текстов (или разным текстам), столбцы — признакам стиля текстов. Каждая ячейка этой таблицы содержит числа т, выражающие количество событий в тексте, благоприятствующих выбранному признаку (число появления данного признака в данном фрагменте текста). Например, это может быть число появления предложений с определенным чис лом слов, число появления определенных слов в исследуемом тексте и т.п. Помимо чисел появления признаков, находящихся в таблице, необходимо также зафиксировать общее число п событий (предложений, слов и т.п.), определяющее объем выборки (объем фрагмента текста в числах предложений, числах слов и т.п.).
Рассмотрим задачу сравнения двух текстовых фрагментов по одному какому-либо частотному признаку стиля. Такое сравнение можно произвести с помощью гипергеометрического критерия, называемого обычно двусторонним точным критерием Фишера. Рассмотрим этот случай подробнее. Как известно [42], при проверке гипотезы о равенстве параметров рх и р2 двух независимых биномиальных распределений (частот появления признаков в рассматриваемых текстах) ФІІП Р С РЇІІ-РІУ - , X, =0,/1,, /=1,2 , где С = —г- - число сочетаний из п по х, приходится иметь дело с нулевой гипоте-х\(п-х). зой Н0 : рх = р2 при разных в общем случае объемах испытаний щ и п2. В задаче сравнения стилей текстов данная гипотеза говорит о том, что тексты имеют одинаковый стиль по данному признаку, альтернатива - напротив, указывает на то, что тексты значимо различаются по стилю. Оптимальные оценки параметров рх и р2 выражаются эмпирическими частотами р1 = т1/п1, р2 = т2/п2, где т1 и т2 - наблюдаемые в эксперименте значения хх и х2 при объемах испытаний пх и п2. Совместная вероятность встретить в эксперименте значения тх и т2 при реализовавшихся значениях щ и п2 и верной нулевой гипотезе #0, когда р1 = р2 (обозначим это общее значение через р), выражается произведением биномиальных распределений
Р(щ,щ nx,n2,p)= с%С%Р +т (\-р) - \ так что величина s = m1+m2 является достаточной статистикой для оптимальной оценки р: р = s/(nx +п2). Условная вероятность получить в эксперименте значения тх и т2 при фиксированном значении 8 = щ+т2 и верной Н0 есть на самом деле условная вероятность получить значение тх, так как m2=s-mx. Эта вероятность выражается значением при х = щ свободного от параметра р гипергеометрического распределения [42, с. 236]: h(xs,nun2) = С С Х/С +П2, х = maxfas-n min s). (2.1)
Таким образом, величина т1 является статистикой, распределение которой при верной нулевой гипотезе не зависит от неизвестного параметра р. Следовательно, при заданном уровне значимости а критерия проверки нулевой гипотезы Н0 : р1 = р2, о равенстве стилей текстов, против альтернативы Н1:р1Фр2, об их различии, решение в пользу альтернативы принимается при шх \ j2 или при ml hsn (1_а/2, где K,ru,rh,a.i2 и К,п,,пг,\-аі2 квантили соответственно уровней а/2 и 1-а/2 гипергеометрического распределения (2.1). При hs„n а/2 щ hs,n,,rh,\-a.i2 оснований отвергнуть нулевую гипотезу нет. Реализовавшемуся в эксперименте значению щ соответствует достигнутый уровень значимости min(«],5) Р0= Yj{Kx\s n\ n2) Km\\s n\ n2)} x=mdL\(Q,s-n2)
Решение в пользу альтернативы принимается при р0 а. При р0 а оснований отвергнуть нулевую гипотезу нет.
Рассмотренный критерий теоретически работает при любых значениях объемов фрагментов текстов (испытаний) щ и п2. На практике, однако, его применимость ограничивается возможностями вычислений факториалов больших чисел, так как уже 170! = 7.2574е+306, т.е. является числом, близким к машинной бесконечности. Фрагменты же в 170 или более букв, слов или предложений нельзя назвать большими, и встречаются они довольно часто. Поэтому для больших значений п требуется асимптотическое представление критерия. Для этих целей предлагается аппроксимировать гипергеометрическое распределение нормальным с вероятностями целочисленных значений х PN (х) = (і/VW ) ехр(- (х - ц)2/(2а2 )), где \i = s(nxln), a2 = 5(«1/wX«2/n)(w-iS )/(w-l) - математическое ожидание и дисперсия гипергеометрического распределения [10, с. 190], п = п1+п2. Вопрос о точности такой аппроксимации подробно исследован в работе [24].
Классификация текстов с помощью метода Хмелева и его модификаций
Условность отсылки на марковость текста в работах Хмелева тем не менее не ме шает проверить, образует ли последовательность символов текста простую цепь Марко ва. Ранее такие исследования не проводились. Вместе с тем соответствие текста данной модели может дать толчок к новым исследованиям, а несоответствие - окончатель но устранить путаницу в терминологии.
Проверку гипотезы о марковости последовательности символов текста проведем по критерию х2 [7] сравнения матриц частот, являющихся левой и правой частями матричного уравнения Колмогорова-Чепмена.
Пусть Р(Хп = j ХпЛ = /) есть вероятность того, что на п-м месте в последовательности символов текста стоит J-VL символ алфавита, содержащего L символов, при условии, что на предыдущем, (и-1)-м месте стоит /-й символ алфавита. Если эта вероятность для любых символов cij, cij алфавита не зависит от п, цепь символов называется однородной. Обозначим эту вероятность ру, так что PiJ=P(Xn=j\Xn_,=i) 0, -=1, /=1 - і2-6) Будем называть ру переходной вероятностью. Матрица П = р,у) переходных вероятностей образует стохастическую матрицу.
Введем переходную вероятность из состояния / в состояние/ за т шагов: Pij{m) = P(Xn+m=j\Xn=i), (2.7) так что Pjj = ру(\). Для однородной цепи Маркова вероятность Ру{т) удовлетворяет уравнению Колмогорова-Чепмена [33]: L PiJ(m1+m2)=YtPtkM-Py(m2) iJ = 1 L. (2.8)
Это уравнение эквивалентно определению однородной цепи Маркова. Вероятности Pi/(m) образуют стохастическую матрицу П(т)={ру(т)], удовлетворяющую матричному уравнению Колмогорова-Чепмена [33]: Yl(m1+m2)=U(m1)-U(m2), (2.9) откуда следует удобная для вычислений форма матричного уравнения Колмогорова-Чепмена: П(т) = Пт, /и = 1,2,.... (2.10)
Таким образом, все безусловные и условные распределения вероятностей появления символов в однородной марковской цепи полностью определяются матрицей П и начальным распределением {РкШ, рк(0)=Р(Х0=к), k = l,L.
Для проверки гипотезы о марковости цепи символов текста необходимо проверить гипотезы о равенстве левых и правых частей матричного уравнения Колмогорова-Чепмена (2.10) для т = 2,3,... и т.д. Если окажется, что нулевая гипотеза о равенстве левых и правых частей матричного уравнения Колмогорова-Чепмена (2.10) отвергается при заданном критическом уровне значимости pcrit (обычно pcrit = 0.05) уже для т = 2, нет необходимости проверять эту гипотезу для других т - гипотеза о марковости цепи символов текста уже отвергнута.
Рассмотрим матричное уравнение Колмогорова-Чепмена (2.10) для т = 2: П(2) = П П. В развернутом виде с учетом обозначения (2.6) оно принимает форму (2.8): L PiA2)=YjPik-Pkj i J = lL. (2.11)
В дальнейшем будем использовать следующие обозначения матриц переходных вероятностей: Рг = \ру\, Р2 = \руЩ, Р3=Р1-Р1.
Найдем эмпирические оценки Р\, Р2, Р3=Р1 Р1 этих матриц - матрицы частот переходов - по заданному тексту, представленному в виде одной длинной строки - последовательности символов текста. Приведем текст к нижнему регистру, т.е. заменим в тексте все прописные буквы строчными (не будем различать регистры букв). Выберем для анализа русских текстов следующую строку символов алфавита: абвгдежзийклмнопр-стуфхцчшщъыьэюя ;%,;.:!?-" (45 символов).
Символы текста, не вошедшие в эту строку, например, цифры, скобки и пр., будем при анализе текста игнорировать, полагая, что в текстах художественной прозы их ни чтожно мало. При желании, однако, строку символов алфавита можно расширить, добавив в нее указанные символы.
Пусть М ,к) - число пар символов dj и ак алфавита, следующих в тексте непосредственно друг за другом: djdk, так что символ dj непосредственно предшествует символу ак. Просуммировав элементы матрицы Мх вдоль строк (по второму индексу к), L получим вектор iVi с элементами Nl(j)= TiMx(j,k) - числом встречаемости в тексте к=\ символа а: на первом месте в паре символов безотносительно ко второму символу пары. Символы а;, для которых (/)=0, исключаются из алфавита (при этом L уменьшается). Тогда условная частота встречаемости символа ак на втором месте пары символов при условии, что первым в паре стоит символ dj, равна Р ,к) = Мх(],к)ІЩ(і). (2.12) Пусть M2(j,k) - число пар символов а: и ак алфавита, следующих в тексте через один символ: djdtdk, где ai - любой из L символов алфавита (/ = 1,2,...,1,). Другими словами, M2(j,k) - число троек подряд идущих символов, начинающихся символом а, и заканчивающихся символом ак, так что символ dj предшествует символу ак, но не непосредственно, а через одну позицию в тексте. Просуммировав элементы матрицы М2 вдоль строк (по второму индексу к), получим вектор N2 с элементами L 20)=Х 2(/ ) числом встречаемости в тексте символа aj на первом месте в к=\ тройке символов безотносительно к третьему символу тройки. Тогда условная частота встречаемости символа dk на третьем месте тройки символов при условии, что первым в тройке стоит символ dj, равна P2(j,k) = M2{j,k)lN2(j). (2.13) Матрица Р2 полученных таким образом частот - эмпирическая оценка левой части уравнения Колмогорова-Чепмена (2.11).
Формат запроса. Язык задания частотных признаков
Запрос пишется на языке задания частотных признаков, разработанном автором работы. Схематично запрос можно изобразить в следующем виде:
Запрос состоит из строк, каждая из которых задает один признак. Каждый признак задается набором однородных элементов. Например, если было решено подсчитывать предложения, то запрос будет состоять из признаков уровня предложения, если слова -из признаков уровня слов, если буквы - из признаков уровня букв. Смешение разнородных признаков в одном запросе не допускается.
Каждый элемент состоит из двух частей - содержимого и свойств элемента. Содержимое задает общий вид элемента, указывая, какие он должен содержать части (буквы, слова). Свойства определяют структуру элемента и его связь с другими элементам в строке признаков.
Элементы в запросах имеют следующие обозначения. Квадратные скобки обозначают предложение, круглые - слово, кавычки - буквосочетания. Знак "" (прямая черта) отделяет содержимое элемента от его свойств. Свойства располагаются во второй части описания элемента.
Набор возможных свойств зависит от типа элемента. У элементов типа «буквосочетание» могут быть следующие свойства (в скобках указаны их обозначения в языке): - позиция от начала слова (РВ), - позиция от конца слова (РЕ), - позиция относительно предыдущего буквосочетания (РР), - учет регистра букв (R).
Элементы «слово» можно описывать следующими свойствами: - длина слова в буквах (L), - позиция от начала предложения (РВ), - позиция от конца предложения (РЕ), - позиция по отношению к предыдущему слову (РР).
В грамматически размеченном («вертикальном», см. пункт 3.3) тексте можно задавать дополнительные свойства элементов «слово»:
- обладание или наоборот не обладание дополнительными характеристиками (АС-advanced characteristics), среди которых могут быть пометки о части речи, числе, роде, падеже, залоге, времени наклонении, виде, переходности, краткой и полной форме слова, семантическом типе слова (цифра, слово на другом языке, номер, имя, фамилия, отчество, географическое понятие, аббревиатура), принадлежности диалогу,
- являться нормальной формой слова (N) (то есть, содержимое данного элемента «слово» в ходе подсчета частоты признака, к которому данный элемент принадлежит, будет сопоставляться не со словом, каким оно встретилась в тексте, например «крокодиле», а с его нормальной формой - «крокодил»).
Элемент типа «предложение» имеет всего два свойства: - длина предложения в словах (L), - позиция относительно предыдущего предложения (РР).
Если элемент определяется несколькими свойствами, то они перечисляются через запятую. Каждому свойству с помощью знаков равно, неравно, больше, меньше и т.д. ставится в соответствие некоторое числовое или символьное (только для свойства АС) значение.
Содержимое элемента состоит из последовательности элементов более низкого уровня. Содержимым предложения является последовательность слов или буквосочетаний, содержимым слова - только последовательность буквосочетаний. Свойства и содержимое элемента могут быть не указаны. Если не указано ни то, ни другое, то значит, элемент может быть любым.
Пример 1. Для подсчета количества слов «он» в текстах необходимо написать следующий запрос: ("он Р=1" \ L=2). Первый символ в запросе - открывающая круглая скобка, по ней интерпретатор делает вывод о том, что подсчитываются слова. Далее, открывается кавычка - значит, в слове нужно проверить буквосочетания. Внутри кавычек указывается содержимое элемента типа «буквосочетание» (это содержимое - «он»), а после знака «» - свойство Р=\, обозначающее, что буквосочетание должно стоять в слове на первом месте. После закрывающей кавычки опять стоит символ «» и после него свойство L=2, уже относящееся к элементу типа «слово» и обозначающее, что длина слова должна быть равна двум (если не указать это свойство, будут подсчитаны также все слова, начинающиеся на буквосочетание «он»).
Пример 2. Для того чтобы, например, подсчитать предложения, в которых есть слово «он», достаточно заключить запрос в квадратные скобки: [("он / =1" 2,=2)].
Пример 3. Запрос, по которому будут подсчитаны все предложения, в которых «он» стоит на первом месте, выглядит следующим образом: [("он P=V \ L=2, Р=1)]. И т.д.
Запросы могут состоять из нескольких элементов, что позволяет задавать сложные признаки. Элементы, следующие один за другим (или через запятую), рассматриваются как выражения, соединенные по условию «И».
Пример 4. Запрос для подсчета слов, начинающихся на «у» и заканчивающихся на «ый», будет выглядеть следующим образом: ("у P=V\ "ый РЕ=Г).
Пример 5. Запрос для подсчета предложений, в которых на произвольных позициях стоят слова «он» и «пошел»: [("он P=V /,=2) ("пошел P=l" L=5)].
Для образования связанных последовательностей элементов текста в языке предусмотрено свойство «позиция по отношению к предыдущему» (РР).
Пример 6. Для подсчета числа предложений, в которых есть словосочетание «она внезапно замерла», можно составить следующий запрос: [("она I Р=Г I L=3), ("внезапно Р=Г 11=5, PP=\), ("замерла P=\"\ L=9, PP=1)].
Допускается также задание последовательностей элементов без включения этих последовательностей в элементы верхнего уровня. Так можно подсчитывать сами последовательности букв в тексте, а не слова, которые их содержат, сами последовательности слов, а не предложения, к которым эти слова относятся.
