Диссертация (1137276), страница 17
Текст из файла (страница 17)
Стемминг стоп-листа частотного словаря, составленного по коллекции,с помощью алгоритма Портера [74] в реализации NLTK [75], поиск совпадающих стемов, вычисление показателей качества;8. Разбиение слов из частотного словаря, составленного по коллекции, на-граммы ( = 3,4,5,6), разбиение стоп-слов на -граммы ( = 3,4,5,6),вычисление меры Жаккара по множествам -грамм, определение обсценных слов по порогу, составляющему 0.8, вычисление показателейкачества;9. Вычисление редакционного расстояния Левенштейна между словам изчастотного словаря, составленного по коллекции, и стоп-словами, определение обсценных слов по порогу, составляющему 5, 8, вычислениепоказателей качества;10. Построение АСД по стоп-листу, вычисление оценок сходства слов изчастотного словаря, составленного по коллекции, с АСД, определениеобсценных слов по порогу, составляющему 0.2, вычисление показателейкачества.99Таблица 32 — Сравнение фильтров обсценной лексики по точности, полноте,аккуратности и 2 -мереточность полнота аккуратность 2 -мерасовпадения0.72880.13630.98100.2297лемматизацияpymorphy20.64920.24660.98150.3574mystem30.68070.31950.98270.4349стемминг0.61130.40280.98220.4856АСД, порог = 0.2 0.15780.6201 0.92330.2516коэффициент Жаккара3-граммы0.67990.16330.98100.26344-граммы0.71260.14750.98100.24305-граммы0.71680.12840.98080.21796-граммы0.69890.09750.98030.1711расстояние Левенштейна<80.02340.9127 0.80860.0456<50.02090.9825 0.96290.04095.2.3Результаты экспериментаРезультаты эксперимента приведены в Таблице 32.По точности лучшим методом фильтрации является поиск совпадения,что очевидно: если слово входит в стоп-лист, то оно является безусловно обсценным.
Худшими фильтрами по точности оказываются фильтры, основанныена расстоянии Левенштейна: среди тех слов, которые эти фильтры определяюткак обсценные, на самом деле обсценными являются 2%. Эти же фильтры являются лучшими по полноте: с их использованием получается обнаружить до98% обсценных слов. Второе место по полноте занимает фильтр, основанный наАСД: этот фильтр обнаруживает порядка 60% обсценной лексики. Остальныефильтры существенно проигрывают по полноте, но выигрывают по точности.Среди двух использованных лемматизаторов, лучшие результаты достигаютсяпри использовании Mystem. Стемминг позволяет достичь выигрыша порядка10% по полноте сравнению с лемматизацией при относительно несущественном100падении точности.
Вычисление меры Жаккара на -граммах при сравнительновысокой точности приводит к низким значением полноты.Важным параметром для сравнения фильтров является их вычислительная сложность. Приведем оценки вычислительной сложности каждого фильтра.Допустим, что – это максимум из всех возможных длин слов, – максимумиз длины частотного слова и стоп-листа, ≪ . Тогда:– Сложность поиска по совпадению (лемме, стему) составляет () –слово (лемма, стем) проверяется на совпадение со словами (стемами)из стоп-листа;– Сложность попарного вычисления коэффициента Жаккара на множествах -грамм для слов из частотного словаря и стоп-листа и расстояния Левенштейна составляет (2 · 2 ), сложность проверки одногослова – (2 · );– Сложность построения АСД с помощью алгоритма Укконена для стоплиста составляет ( · ), сложность проверки одного слово – ().Таким образом, мы видим, что по общим мерам качества (аккуратности и2 -мере), выигрывают фильтры, использующие поиск совпадения по леммам.Однако, с учетом приведенного выше утверждения о важности именно полноты, а не общего качества фильтра, целесообразным представляется использование фильтров, вычисляющих расстояние Левенштейна или СУВВС.
Остановимся подробнее на сравнение этих двух фильтров. Фильтры, использующиерасстояние Левенштейна, имеют показатели точности близкие к нулю, а полноты – к 1, за счет чего достигают высоких оценок аккуратности и мизерныхоценок 2 -меры. Фильтры, использующие СУВВС, более сбалансированы поточности и полноте, имеют аккуратность, сопоставимую с другими рассматриваемыми фильтрами, но и невысокое значение 2 -меры, благодаря низкой точности. В итоге, с учетом того, что при уже построенном заранее по стоп-листуАСД, проверка одного слова имеет линейную сложность по времени, разумнойпредставляется следующая схема фильтрации.
Заранее строится АСД по стоплисту, которое занимает небольшое место и хранится в оперативной памяти.При необходимости проверки текста на наличие обсценной лексики находятсявсе словоупотребления, после чего для каждого находится оценка по СУВСС.Если найденная оценка превосходит некий порог, слово признается обсценными срабатывают следующие процедуры фильтрации.101Глава 6.
Комплексы программВ [100; 101] описывается современный подход к разработке современныхсистем автоматической обработки текстов в форме pipeline. Примерами систем,разработанных в рамках этого подхода, могут выступить Stanford CoreNLP [102]Стэндфордского университета, свободная библиотека для машинного обученияSciKit-Learn [103], Google SyntaxNet [104], DKPro Технического университетаДармштадта [105]. Идея pipeline заключается в том, что одна система отвечаетза все необходимые этап обработки текстов и, если такая необходимость возникает, обращается к внешним инструментам без участия пользователя. Стандартный pipeline включает в себя предобработку текстов (удаление лишних символов и разметки), токенизацию, морфологический анализ (приведение слов кнормальной форме и/или лемматизацию и/или стемминг) и синтаксическийанализ (выделение именных и/или глагольных групп и/или построение деревьев зависимостей или составляющих).
Пользователю при этом достаточно задать входные файлы и параметры конфигурации и не нужно вызывать отдельные модули последовательно.В духе pipeline реализована описанная ниже библиотека EAST, выполняющая все необходимые шаги для построения АСД таблицы. Заметим, что pipelineбиблиотеки EAST существенно меньше, чем pipeline библиотеки SciKit-Learnили индустриальных CoreNLP или DKPro, хотя бы потому, что использованиеметода АСД не требует существенной обработки текстов. При необходимостиподключить к библиотеке EAST возможности морфологического или синтаксического анализа не составит особого труда.6.1Программная реализация построения таблиц РСТ и методаАСДВ статье [60] приведено описание реализации наивного и линейного алгоритмов построения АСД и таблиц рСТ.
Программная реализация обоих алгоритмов находится в свободном доступе по следующей ссылке: https://github.com/mikhaildubov/AST-text-analysis. Программа, разработанная совместно102Рисунок 6.1 — Схема pipeline библиотеки EASTс М. С. Дубовым, может работать в двух режимах: как из командной строки,так и в качестве библиотеки на языке Python 2.7.На Рис.
6.1 представлена схема pipeline библиотеки EAST: на вход системе поступает коллекция текстовых документов и список ключевых слов исловосочетаний. Коллекция текстовых документов подвергается предобработке: токенизации и разбиению на строки, по которым в последствии строитсяаннотированное суффиксное дерево (АСД). После чего вычисляется сходствоключевых слов и словосочетаний с построенным АСД и на выход подается готовая таблица релевантности. Все последующие аналитические алгоритмы используют построенную таблицу либо для определения максимальных значениймеры релевантности, либо для ранжирования по убыванию меры релевантности.6.1.1Использование программы EAST из командной строкиДля вызова из командной строки следует задать следующую последовательность команд:$ east [-s] [-d] [-f <table_format>] [-a <ast_algorithm>] keyphrases table<keyphrases_file> <directory_with_txt_files>103На вход программе подается адрес текстового файла, в котором записанысловосочетания и адрес директории, в которой хранится коллекция текстов.Каждый текст должен быть сохранен в отдельном текстовом формате.
Такжепрограмме на вход подается несколько параметров:– s: возможность учета синонимов (в стадии разработки).– d: расчет оценки релевантности без нормализация. По умолчанию используется оценка релевантности с нормализаций, если указан параметр d, то используется оценка релевантности без нормализации.– f: формат выдачи РСТ таблицы: либо XML, либо .csv файл.– a: алгоритм построения АСД. По умолчанию используется линейныйалгоритм построения АСД, однако, при желании, пользователь можетиспользовать наивный алгоритм.Если программа запушена из командной строки, то существа два варианта выдачи результатов: либо выдача результатов непосредственно в консоль,либо перенаправление выдачи в текстовый файл.
Первый вариант предлагается исключительно для ознакомления с функциональностью программы. Дляперенаправления выдачи следует использовать инструкцию > filename.txt.6.1.2Использование программы EAST как библиотеки языкаPython 2.7Для вызова из среду Python строки следует задать следующую последовательность команд. Приведенный ниже фрагмент кода показывает, как построить АСД для коллекции из двух строк и посчитать релевантность других двухстрок построенному АСД.From east.asts import base #импорт библиотекиast = base.AST.get_ast([“XABXAC”, “HI”]) #построение АСДprint ast.score(“ABCI”) # 0.1875 (подсчет оценки релевантности)print ast.score(“NOPE”) # 0 (подсчет оценки релевантности)1046.1.3Структура программы EASTПрограмма EAST написана языке Python 2.7 и состоит из 24 модулей,большая часть из которых носит вспомогательный характер: модули для инициализации, тестирования, хранения списка исключений, форматирования выдачи.
Перечислим модули, в которых реализован метод АСД и метод построенияРСТ таблиц:– east/asts/ast.py – в этом модуле хранится класс AST (Annotated SuffixTree, АСД) и его методы: добавить узел в дерево, убрать узел из дерева,обойти дерево в глубину, обойти дерево в ширину и вычислить оценкурелевантности строки дереву.– east/asts/ast_naive.py – наивный алгоритм построения АСД.– east/asts/ast_linear.py – линейный алгоритм построения АСД– east/asts/utils.py – некоторые полезные утилиты: токенизатор, функциядля разбиения текста на строки, функция, которая добавляет уникальные терминальные символы к строкам.Общая схема работы программы: на вход программе поступает коллекция текстов и коллекция строк-словосочетаний.
Программа по очереди обрабатываетвсе тексты. Каждый текст программа разбивает сначала на токены, потом токены объединяет в строки, добавляет к ним уникальные терминальные символы иполучает набор строк для построения АСД по данному тексту. Затем программа инициализирует пустой объект класса AST, назовем его, например, tree,и вызывает один из алгоритмов построения АСД, передавая ему на вход коллекцию строк. Алгоритм строит АСД и сохраняет его в существующий объекткласса АСД tree.
После этого программа передает коллекцию словосочетанийстрок tree. У класса tree есть метод для вычисления оценок релевантности сколлекцией строк, который возвращает вектор оценок релевантности. Полученный вектор программа записывает как столбец в РСТ таблицу. После того, какпрограмма обработает все тексты, она окончательно формирует РСТ таблицуи выдает ее в командную строку или записывает в выходной файл.1056.2Утилита WikiDPСовместно с Н. Левицким и Е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
