Диссертация (1137276), страница 2
Текст из файла (страница 2)
. . – множеством всех подстрок . . . , где >= 1, <= , <= . Длякаждой пары строка – текст несложно найти все возможные общие подстроки, иначе говоря, совпадения. Максимальным совпадением назовем такое совпадение, при добавлении символа в начало или в конец которого, перестаетбыть совпадением. Допустим, существует совпадение строки с текстом .
. . .Определим его вероятность, как условную частоту последнего символа : ( . . . ) = ( | . . . −1 ) (УВС). Вероятностью максимального совпадениятогда является средняя сумма совпадений, в него входящих (СУВС), а полнойрелевантностью строки тексту – сумма вероятностей максимальных совпадений данному тексту (СУВСС). Для эффективной реализации вычисления оценок релевантности следует использовать аппарат аннотированного суффиксно7го дерева – структуры данных, которая позволяет вычислять все частоты всехподстрок.Объект исследования – вычислительные задачи анализа текстовых документов, написанных на естественном языке.Предмет исследования – вычислительное моделирование текстов какстрок символов и задачи их анализа, решаемые путем наложения разных строкдруг на друга.Цель данного диссертационного исследования – разработка оригинальных моделей, методов, алгоритмов и программных комплексов, предназначенных для решения некоторых задач анализа текстовых документов на естественном языке на уровне последовательностей символов.К задачам исследования относятся:1.
Разработка модели представления коллекции текстовых документовстроками и ассоциированной с ней функции релевантности;2. Верификация разработанной модели на реальных задачах анализа коллекций текстовых документов:a) Рубрикация текстовых документов в соответствии с заданнойсистемой рубрик;b) Пополнение таксономии с использованием внешней коллекциитекстов;c) Фильтрация коллекции текстовых документов от обсценнойлексики.3.
Реализация разработанных моделей и методов в виде комплекса программ.К методам, использованным в исследовании, относятся:1. Метод Укконена для построения аннотированного суффиксного дереваза линейное время;2. Метод вычисления релевантности строки тексту с помощью наложениястроки на аннотированное суффиксное дерево его представляющее;3.
Методы вычисления релевантности строки тексту, основанные на представлении текстов векторными пространствами и вероятностными моделями.Научная новизна. В диссертации получен ряд новых научных результатов, которые выносятся на защиту:81. Разработана теоретико-множественная модель совокупности «строкатекст» с методом оценки релевантности строк тексту, основанном нааннотированных суффиксных деревьев. Предложен новый метод вычисления оценок релевантности строки тексту СУВСС, апробированный в работе;2. Предложен метод рубрикации научных статей с использованием критерия релевантности СУВСС, более точного, чем популярные методы,традиционно используемые в международных публикациях;3.
Разработан метод использования справочных материалов интернета, сучетом наличия в них шумовой компоненты, для пополнения предметных таксономий. Методика апробирована в задачах пополнения таксономий чистой и прикладной математики с использованием русскоязычной Википедии;4. Показана эффективность использование критерия релевантностиСУВСС в классе задач поиска по однословному ключу, в которомполнота важнее, чем точность;5.
Разработаны комплексы программ, реализующие предложенную теоретико-множественную модель совокупности «строка – текст» с использованием критерия релевантности СУВСС, применительно к решениюзадач в пунктах 2, 3 и 4.Теоретическая значимость работы заключается в разработке принципиально новых моделей и методов: теоретико-множественной модели совокупности «строка – текст», модели нормированного аннотированного суффиксногодерева с критерием релевантности СУВСС, а также метода построения таблицрелевантности «строка – текст» (РСТ) для применения в конкретных задачах.Практическая ценность подтверждена экспериментами по сравнительной оценке использования мер релевантности для рубрикации научных статей,результатами расчетов по пополнению таксономий с использованием материалов интернета и результатами решения задач поиска, ориентированных на егополноту.
Все разработанные методы реализованы в виде программных комплексов, предназначенных для решения исследовательских и прикладных задач.Разработанные методы и алгоритмы были успешно применены в реальных проектах компании ООО «ФОРС-Центр разработки» (метод фильтрации обсценной лексики использован для анализа и определения тональности текстов всоциальных сетях в системе FORSMedia) и «ЕС-Лизинг» (метод рубрикации9использован для категоризации проектной документации) и проектах, выполнявшихся по грантам ВШЭ в 2010 – 2015 гг., а также в преподавательскойдеятельности Департамента анализа данных и искусственного интеллекта Факультета компьютерных наук НИУ ВШЭ.Достоверность полученных результатов подтверждена строгостьюиспользованных математических моделей и методов, экспериментами по сравнению результатов применения разработанных традиционных методов на конкретных задачах, а также алгоритмической эффективностью программных реализаций.Апробация результатов работы.
Основные результаты работы обсуждались и докладывались на следующих научных конференциях и семинарах:– 1-ой, 2-ой всероссийских научных конференция “Анализ изображений,сетей и текстов” (АИСТ-2012, АИСТ-2013), Екатеринбург, Россия; темыдокладов – “Автоматизация использования таксономий для аннотирования текстовых документов”, “Использование ресурсов интернета дляпостроения таксономии”– 1-ом семинаре по кластерам, деревьям и порядкам (COT-2013), Москва,Россия; тема доклада – “An AST method for scoring string-to-textsimiliarity in semantic text analysis”– 8-ой международной конференции “Диалог” (Диалог-2013), Бекасово,Россия; тема доклада – “Computational refining of Russian-languagetaxonomy using Wikipedia”– 3-ей международной научной конференции “Анализ изображений, сетей и текстов” (АИСТ-2014), Екатеринбург, Россия; тема доклада –“Conceptual maps: construction over a text collection and analysis”– 2-ой международной конференции “Информационные технологии и количественный менеджмент” (ITQM-2014), Москва, Россия; тема доклада – “A method for refining a taxonomy by using annotated suffix trees andWikipedia recourses”– 3-ей всероссийской конференции “Искусственный интеллект и естественный язык” (AINL-2014), Москва, Россия; тема доклада – “Создание ивизуализация газетного интернет-корпуса”– 8-ой международной конференции “Веб-поиск и майнинг данных”(WSDM-2015), Шанхай, КНР тема доклада – “An approach to theproblem of annotation of research publication”;10– 2-ом международном семинаре по майнингу данных и автоматическойобработке текстов (DMNLP-2015) тема доклада – “Some thoughts onusing annotated suffix trees for NLP tasks”Публикация результатов.
Основные результаты работы изложены в13 научных статьях. 7 статей опубликованы в рецензируемых сборниках трудов международных и всероссийских конференций, 3 статьи опубликованы вжурналах из списка ВАК.Основные результаты работы1. Экспериментально показана целесообразность использования теоретико-множественной модели совокупности «строка-текст» и нормированного аннотированного суффиксного дерева (АСД) в качестве численного метода оценки параметров модели и ассоциированной с ниммеры релевантности для решения задач анализа коллекций текстовыхдокументов;2. В рамках теоретико-множественной модели совокупности «строкатекст» предложена и обоснована естественная мера релевантностиСУВСС, вычисляемая на основе нормированного АСД;3.
Показана эффективность использования меры релевантности, основанной на АСД, в задаче рубрикации коллекций текстовых документов безучителя – использование данной примеры приводит к лучшему ранжированию;4. Предложен и применен к двум таксономиям прикладной математикиметод пополнения таксономии, использующий Википедию в качествевнешнего источника;5. Показана эффективность использования меры релевантности, основанной на АСД, в задаче фильтрации обсценной лексики – использованиеданной меры приводит к лучшим показателям полноты и вычислительной сложности по времени;6.
Предложена адаптация алгоритма Укконена для построения АСД;7. Разработаны программные комплексы для извлечения данных из Википедии, для построения АСД, вычисления оценок релевантности ипостроения таблиц релевантности «строка – текст».Во введении раскрывается актуальность темы диссертации, формулируются проблемы и задачи исследования, предмет исследования, определяютсяцели работы, описываются методы исследования, излагаются основные научные11результаты, обосновывается теоретическая и практическая значимость работы,даётся общая характеристика исследования.В первой главе приводится обзор четырех подходов к машинному представлению коллекций текстовых документов: векторная модель представленияколлекций текстовых документов, языковая модель представления коллекцийтекстовых документов, представление коллекции текстовых документов на основе модели скрытых тем, представление коллекции текстовых документов наоснове модели суффиксных деревьев.
Рассматриваются задачи обработки и анализа коллекций текстовых документов, в которых применяются те или иныемодели представления, возможные преимущества и ограничения. Приводятсяосновные определения, связанные с предварительной обработкой текстовых документов, моделями представления текстовых документов, различными задачами обработки и анализа коллекций текстовых документов.Во второй главе рассматривается проблематика определения релевантности строки текстовому документу, принадлежащему некоторой коллекции.Утверждается, что построение функции релевантности тесно связано с выбранным формальным представлением коллекции текстовых документов. В связи сэтим рассматриваются различные функции релевантности, порождаемые различными формальными представлениями коллекций текстовых документов.Вводится понятие нормированного аннотированного суффиксного дерева и связанной с ним естественно интерпретируемой функции релевантности СУВСС.Описывается метод построения таблиц релевантности «строка – текст» (РСТ),используемых в дальнейшем для анализа коллекций текстовых документов, атакже оптимальные по памяти и времени алгоритмы построения нормированного аннотированного суффиксного дерева.В третьей главе рассматривается задача рубрикации аннотаций научныхпубликаций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
