Диссертация (1149537), страница 7

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

Текст из файла (страница 7)

+ mn − nT = |X|:F : (X, D(x, y)) → (Rm , k · k).Каждому вектору-фрагменту xji сопоставим вектор F ∈ Rm по следующему правилу:D(xji , xT1 +1 ) D(xji , xT1 +2 ) (2.11)...jF (xi ) = 0....mn−1 jD(xi , xn )nD(xji , xmn )Таким образом, ∀j > T, i ∈ 1..n координаты вектора F (xji ) соответствуют расстояниям от вектора-фрагмента xji до всех векторов-фрагментовиз множества X.46Рассмотрим пример вложения. Пусть X = {xt11 , xt21 , xt31 } и• D(xt11 , xt21 ) = 0.5,• D(xt11 , xt31 ) = 1,• D(xt21 , xt31 ) = 0.2.Тогда соответствующие вектора F равны   00.51   t1t1t1F (x1 ) = 0.5, F (x2 ) =  0 , F (x3 ) = 0.2.10.20Обозначим F = {F (xji }xj ∈X . Будем кластеризовать элементы мноiжества F с помощью алгоритма кластеризации Cl, минимизирующегофункционал (1.5) из п.1.4.Алгоритм 3Вход:X — коллекция текстовT — параметр задержкиk — число группПроцедура:j m1: Построить X = {xi }j=T +1 .2: Для каждого x построить динамическую модель sx по (2.4).3: Вычислить F (x) для каждого x по (2.11).4: Разделить множество F на k кластеров с помощью алгоритма кластеризации Cl.Пусть в результате работы Алгоритма 3 вектора F (x) разделились наk кластеров L1 , .

. . , Lk . Тогда в пространстве фрагментов можно определить следующее правило классификации, относящее фрагмент к одномуиз классов l1 , . . . , lk :Правило классификации 2Два фрагмента xi и xj относятся к одному классу lk , если соответствующие им вектора F (xi ) и F (xj ) попали в один кластер k.47Теорема 2. Если r(x, y) — положительно определенное ядра и выполнено Предположение 1 кластеризация в пространстве F обеспечиваетоднозначность и корректность правила классификации.Доказательство.

Если r(x, y) — положительно определенное ядро, топри выполнении Предположения 1 функция D(x, y) является отрицательно определенным ядром, таким, что D(x, x) = 0 ∀x ∈ X.Тогда по теореме из п. 1.5.2 существует гильбертово пространство Hвещественнозначных функций на X и отображение φ : X → H такое, что||φ(x) − φ(y)||2 = D(x, y).Полагая φ(·) = F (·) и H = F имеем изометрическое вложение множествавекторов-фрагментов X в множество векторов из F. Следовательно, имеем соответствие между кластерами в пространстве векторов-фрагментовX и в пространстве векторов F.

Это и обуславливает корректность построенной процедуры классификации.48Глава 3ЭкспериментальныерезультатыВ главе приводятся результаты применения разработанных алгоритмов классификации фрагментов текстовых документов к задаче определения авторства текстов нескольких серий популярных книг. Полученные результаты указывают на то, что динамика изменений фрагментовтекстовых документов является их отличительной характеристикой. Результаты хорошо согласуются с известными фактами.3.1Определение авторства текстаЗадача определения авторства текста заключается в определение автора конкретного текста при помощи анализа текстовых документов,принадлежащим нескольким известным авторам. В этой сфере существует долгая история исследований.

Исчерпывающие обзоры подходов даныв [80] и [134].Для количественного определения различия двух текстов используют меры различия, которые является ключевой составляющей любогоалгоритма определения авторства. Burrows’s Delta [28] – одна из самыхраспространенных мер стилистического различия, была предложена в2002 году. Различные ее модификации были разработаны и протестированы в работах [18], [71], [136].49Нормализованное расстояние сжатия (англ.

Normalized CompressionDistance) также успешно применяется в задачах кластеризации текстови используется для оценки вычислительной сложности алгоритмов определения авторства (как, например, в [35], [113])Некоторые подходы используют признаки на основе слов. Такого рода подходы можно разделить на три класса.

В первом классе методовтекст рассматривается как совокупность слов – служебных частей речи(например, предлоги, местоимения, союзы). При этом самостоятельныечасти речи игнорируются, так как они склонны быть сильно связанными с темой текста [149]. Второй класс подходов использует традиционную модель “мешка слов”, выбирая в качестве признаков текста самостоятельные части речи [48]. Алгоритмы во втором классе основаны напредположении, что авторский стиль в большей степени определяетсяраспределением вероятности появления слов, фраз или других синтаксических структур [100].

Они применимы в случае, когда есть явная связьмежду автором и темой текста. Стоит упомянуть среди них алгоритмлокального дискриминативного тематического моделирования [144]. Последний класс методов рассматривает признаки на основе N -грамм —последовательностей N слов или символов [115].

Символьные N -граммыоказываются очень подходящими признаками для задачи определенияавторства текстов. Они нечувствительны к грамматическим ошибкам,вычислительно эффективны и подходят для любых языков, так как ихиспользование позволяет избежать сложной предобработки, например,токенизации для восточных языков. Ключевым аспектом этого подхода является правильный выбор длины N -граммы N . Большие значенияN позволяют учесть контекст и тему текста, но также ведут к увеличению размерности признакового пространства. Меньшие значения Nповышают чувствительность алгоритма к связям внутри слов, но не учитывают более широкий контекст. Для анализа синтаксической структуры, являющейся подходящей характеристикой авторского стиля, в работах [130], [131], [132] были представлены синтаксические N -граммы.Гибридные методы сочетают несколько видов признаков (например,50[44]), таким образом используя стилистические и тематические признаки одновременно.

Как было подчеркнуто в [123], не существует универсального признака, который позволит точно отличить разные авторскиестили. Таким образом, необходимо анализировать необычайно широкийнабор признаков с привлечением разных подходов [80] для того, чтобы получить подходящий результат. В задаче верификации авторства,авторский стиль становится самым важным признаком рассматриваемого текста [85], [134]. При верификации множество авторов-кандидатовсостоит из одного автора [99].

Так как любую задачу идентификацииавтора можно привести к последовательности из задач верификации,последнюю считают фундаментальной [90], [133].Существует два основных подхода к решению задачи верификации:внутренний и внешний. Внутренний подход работает только с предоставленными текстами (один известного авторства и один исследуемый,авторство которого под вопросом) и сводится к задаче одноклассовойклассификации [57], [65], [77].

Такая задача возникает и при выявленииплагиата (например, [86], [96], [135], [147]). Внешние подходы преобразуют задачу верификации в задачу бинарной классификации. Среди алгоритмов такого рода стоит упомянуть “метод самозванцев” (ImpostorsMethod) [89]. Решение об авторстве принимается на основании того, чтодокумент известного авторства более похож на исследуемый текст посравнению с текстами из множества “самозванцев”. Несмотря на то, чтометод эффективен в целом, ее применимость имеет ряд ограничений.Например, может быть проблематично классифицировать пары “одинавтор” и “разные авторы”, когда исследуемые тексты разного жанра итематики [90].513.2Классификация текстов на основеалгоритма кластеризации с помощьюспектрального представленияВ этом разделе приведены результаты применения Алгоритма 2 иПравила классификации 1 п.

2.2.1 к анализу авторского стиля в двухкнижных циклах: “Основание” А. Азимова и “Рама” А. Кларка (произведения на английском языке).Предобработка текстовых документов заключалась в удалении стопслов. Каждый документ делился на одинаковое количество отрывковm = 256. В качестве векторной модели была выбрана модель символьных 3-грамм.

По коллекции текстовых документов строился словарь всехвстречающихся в текстах 3-грамм, далее каждый фрагмент текста представлялся как распределение частот появления в нем 3-грамм из словаря.В качестве функции r(x, y) было выбрано dSpearman (x, y) (см. п. 1.5.1),параметр T = 10 — учитывались 10 предшествующих фрагментов. Разделение периодограмм на кластеры происходило агломеративном иерархическим алгоритмом кластеризации с методом одиночной связи (см.п.

1.4.1), выбор оптимального количества кластеров — с помощью индекса Silhouette [122]. Значение индекса измеряет, как точки в одномкластере ближе друг к другу, в отличие от точек, попавших в другиекластеры. Точки с большими положительными значениями индекса около +1 хорошо сгруппированы. Точки, у которых отрицательные значенияиндекса, находятся в неправильном кластере. Среднее значение индекса, вычисленное для всех точек, характеризует качество разбиения накластеры. Оптимальным считается разбиение с наибольшим значениеминдекса, так как оно обеспечивает с одной стороны, компактность кластеров, а другой — хорошо отделяет кластеры друг от друга.52Цикл “Основание” А.АзимоваКнижная серия “Основание” представляет собой цикл из 7 научнофантастических романов А.Азимова.

Первоначально цикл состоял изтрех романов, спустя тридцать лет были написаны еще четыре книги.Ниже представлен список книг согласно внутренней хронологии событий в произведениях:1. “Прелюдия к Основанию” (1988) (F1)2. “На пути к Основанию” (1993) (F2)3. “Основание” (1951) (F3)4. “Основание и Империя” (1952) (F4)5.

“Второе Основание” (1953) (F5)6. “Кризис Основания” (1982) (F6)7. “Основание и Земля” (1986) (F7)Рассмотрим две периодограммы, построенные для первой напечатанной книги “Основание” (красный) и последней напечатанной книгой “Напути к Основанию” Рис. 3.1.Нестрого говоря, эти кривые похожи, но спектр мощности краснойлинии больше сосредоточен в низких частотах. Она имеет больше пиков,в то время как синяя — более гладкая.

Характеристики

Список файлов диссертации