Агрегированное представление текстов для задач поиска в коллекциях текстовых документов тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Фролов Дмитрий Сергеевич

• Фролов Дмитрий Сергеевич
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Фролов Дмитрий Сергеевич

0.8 Структура работы

1 Обзор литературы и существующих решений

1.1 Задача информационного поиска

1.1.1 Введение в задачу информационного поиска

1.1.2 Модели информационного поиска

1.1.3 Применение индексирования и ранжирования

1.1.4 Безындексные алгоритмы информационного поиска

1.2 Представление текста в задачах информационного поиска

1.2.1 Основные подходы

1.2.2 Признаковое описание документов

1.2.3 Агрегированное представление текстов с помощью аннотированных суффиксных деревьев (АСД) и других подходов

1.2.4 Вероятностное тематическое моделирование в коллекциях документов

1.2.5 Векторные представления слов и документов

1.3 Задача нечеткого поиска и методы ее решения

1.3.1 Признаковые подходы, алгоритмы Soundex, фрагментные подходы

1.3.2 Методы хэширования по сигнатуре

1.3.3 Метрические деревья, деревья Букхарда-Келлера и другие специализированные методы

1.4 Разведочный информационный поиск и анализ коллекций

1.4.1 Задача разведочного информационного поиска

1.4.2 Базовые методы разведочного поиска

1.4.3 Структуризация коллекций

1.4.4 Использование таксономий и понятие обобщения в разведочном поиске

1.4.5 Анализ коллекций научных публикаций

1.5 Популярные программные системы для информационного поиска

1.5.1 Lemur

1.5.2 ElasticSearch

1.5.3 Библиотека gensim

1.5.4 Другие популярные программные системы для информационного поиска

2 Разработка метода информационного поиска на основе

аннотированных суффиксных деревьев

2.1 Метод поиска АСДП и его оптимизация с помощью фрагментного индексирования

2.2 Экспериментальное сравнение АСДП с классическими методами информационного поиска

2.2.1 Сравнение качественных метрик

2.2.2 Сравнение производительности

2.3 Экспериментальное сравнение АСДП со специализированными методами нечеткого поиска

2.3.1 Сравниваемые методы и тестовые коллекции

2.3.2 Сравнение качества поиска

2.3.3 Сравнение скорости поиска

2.3.4 Результаты сравнения

2.3.5 Зависимость скорости поиска от длины строк для построения АСД в методе АСДП

2.4 Выводы на основе результатов экспериментов

2.5 Программная реализация распределенной поисковой системы, основанной на методе АСДП

3 Алгоритм оптимального обобщения нечеткого множества (ПарГеНМ) и его применение в задаче разведочного поиска

67

3.1 Описание задачи

3.2 Оптимальный подъем нечеткого тематического кластера в таксономии

3.2.1 Постановка задачи

3.2.2 Алгоритм ПарГеНМ

для поиска оптимального обобщения

3.2.3 Иллюстративные примеры

3.3 Применение алгоритма ПарГеНМ в задаче разведочного поиска

3.3.1 Структурирование коллекции научных публикаций с помощью таксономии предметной области

3.3.2 Подготовка коллекции научных публикаций

3.3.3 Таксономия DST

3.3.4 Вычисление степени релевантности между текстами

и темами таксономии

3.3.5 Определение и вычисление нечетких кластеров тем таксономии

3.3.6 Результаты подъема кластеров L, R, и C в таксономии DST

3.3.7 Выводы

3.4 Алгоритм ПарГеНМ как механизм анализа текстовых коллекций

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

3.5.1 Латентное размещение Дирихле

3.5.2 Иерархический кластер-анализ

4 Применение алгоритма ПарГеНМ для задачи расширения аудитории в рекламном таргетинге (Programmatic)

4.1 Модель интернет-рекламы Programmatic

4.2 Рекламный таргетинг в модели Programmatic

4.3 Применение алгоритма ПарГеНМ для обобщения пользовательских сегментов в интернет-рекламе

4.4 Оценка эффективности алгоритма обобщения пользовательских

сегментов

Заключение

Библиографический список использованной литературы

Список иллюстраций

Список таблиц

Приложение 1: Таксономия Науки о данных

согласно ЛСМ-СС8

Приложение 2: Темы, полученные с использованием

реализации ЬЮА из пакета gensim

Приложение 3: Тематические кластеры, полученные

с помощью метода ЦРОМЛ

Приложение 4: Программная реализация АСД с возможностью

вычисления степени вхождения строки в документ

Приложение 5: Программная реализация алгоритма ПарГеНМ

Приложение 6: Программная реализация отображения дерева

подъема нечеткого множества в таксономии

Введение

Введение диссертации (часть автореферата) на тему «Агрегированное представление текстов для задач поиска в коллекциях текстовых документов»

0.1 Актуальность исследования

Задачи автоматизации анализа текстов и, прежде всего, задачи их поиска получают всё большую актуальность в связи с современными процессами глобализации и дигитализации общества. Задачи поиска и извлечения текстовых документов широко освещены в современной литературе, в частности, в [14, 80, 50, 101, 112].

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

1) повышение скорости поиска документов;

2) повышение качества поиска документов;

3) обеспечение возможности распределенного хранения документов коллекции;

4) обеспечение возможности параллельной и неодновременной обработки данных;

5) автоматизация анализа текстовой информации, включая ее структурирование и интерпретацию.

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

переменных или ограничений, дающую иное описание изучаемого процесса или объекта. В частности, в последнее время получили популярность такие способы агрегированного представления коллекций документов как вероятностное латентно-семантическое индексирование [68] и скрытое размещение Дирихле [39]. Эти подходы были с успехом применены в задачах поиска (наряду с задачами рубрикации и кластеризации документов), что описано, например, в обзоре [12]).

Методы вероятностного латентно-семантического индексирования и скрытого размещения Дирихле используют признаковое описание документов, невозможное без существенной предобработки. Существует и другой подход к агрегированию, не требующий предобработки, в котором кодируются не признаки, а произвольные фрагменты текста - так называемый метод аннотированного суффиксного дерева (АСД) [25, 16]. Этот подход разрабатывался для решения задач анализа текстовых коллекций, в частности, рубрикации [48]. Методы поиска, использующие АСД, могут иметь определенные преимущества, например, при выполнении поиска документов по неточным запросам (возможно, содержащих неточности написания, ошибки). Методы на основе признакового описания крайне сложно адаптируемы к таким ситуациям.

0.2 Цель и задачи исследования

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

1) Разработать эффективный алгоритм поиска и извлечения текстов на основе их представления аннотированными суффиксными деревьями;

2) Разработать варианты этого алгоритма для параллельных и распределенных вычислений, а также неодновременной обработки данных;

3) Адаптировать разработанные алгоритмы для работы с динамически изменяющимися коллекциями документов (случаи вставки, удаления, изменения текста документов);

4) Разработать методику интерпретации результатов информационного поиска с использованием кластерного анализа и таксономического представления предметной области;

5) Разработать математическое обеспечение и провести вычислительные эксперименты по обоснованию эффективности разработанных программ;

6) Провести вычислительные эксперименты по сравнению разработок диссертации с существующими методами;

7) Применить разработанную технологию в задачах реального поиска и извлечения информации.

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

0.3 Методы исследования, достоверность результатов

К методам, использованным в исследовании, относятся:

1) Метод представления текста в виде аннотированного суффиксного дерева (АСД), а также метод вычисления релевантности строки тексту на основе АСД;

2) Методы индексирования и ранжирования для задач информационного поиска;

3) Метод нечеткой кластеризации РАБОК;

4) Таксономическое представление предметных областей, в особенности, Науки о данных.

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

0.4 Результаты, выносимые на защиту

В ходе работы над диссертацией были получены следующие основные результаты:

1) Разработан новый метод информационного поиска АСДП. Выполнена программная реализация поисковой системы, основанной на данном методе. Эффективность метода доказана вычислительными экспериментами по сравнению АСДП с популярными современными методами поиска, в том числе, и специализированными для задач нечеткого поиска. Сравнение показало качественное преимущество разработанного метода в задачах нечеткого поиска и хороший баланс его качественных характеристик и производительности.

2) Разработан метод интерпретации результатов информационного поиска с помощью формирования и оптимального обобщения нечетких кластеров в таксономии предметной области (ПарГеНМ). Сделана программная реализация разработанного метода. Экспериментальная апробация метода ПарГеНМ проведена на коллекции публикаций издательства Springer в области Науки о данных.

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

0.5 Научная новизна исследования

Впервые разработана методика информационного поиска для коллекций документов, представленных в виде аннотированных суффиксных деревьев (АСД). Разработан новый метод информационного поиска АСДП. Выполнена программная реализация поисковой системы, основанной на данном методе. Эффективность метода доказана вычислительными экспериментами по сравнению АСДП с популярными современными методами поиска, в том числе, и специализированными для задач нечеткого поиска. Сравнение показало качественное преимущество разработанного метода в задачах нечеткого поиска и хороший баланс его качественных характеристик и производительности.

Разработан и программно реализован метод интерпретации результатов поиска с помощью оптимального обобщения нечетких кластеров в таксономии предметной области (ПарГеНМ). Проведена его экспериментальная апробация и валидация, в том числе, при структурировании и интерпретации научных публикаций в области Науки о данных.

Разработан и программно реализован метод расширения аудитории интернет-рекламы на основе оптимального обобщения сегментов пользователя в таксономии предметной области (ОПС). Произведена программная реализация и апробация разработанного метода расширения аудитории ОПС с использованием реальных рекламных кампаний в Интернете. Новый метод расширения аудитории рекламных кампаний успешно внедрен на практике в коммерческой организации.

0.6 Теоретическая значимость и практическая ценность

Теоретическая значимость диссертации заключается в том, что в работе предложен метод информационного поиска АСДП и его модификации для параллельных, распределенных и динамических вычислений, а также алгоритм поиска оптимального обобщения нечетких кластеров в таксономии - ПарГеНМ. Кроме того, разработаны методики использования алгоритма оптимального обобщения в таксономиях ПарГеНМ для задач:

1) Структурирования и интерпретации текстовых коллекций;

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

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

1) Экспериментально обоснована эффективность метода АСДП в задачах информационного поиска, в том числе, и для нечеткого;

2) Проведен анализ тенденций развития области Науки о данных по массиву научных статей, опубликованных в журналах издательства Springer в 1998-2017 годах;

3) Предложена и внедрена методика для эффективного расширения аудитории интернет-рекламы.

0.7 Апробация и публикация результатов работы

Результаты работы представлены на следующих конференциях:

1) RuSSIR 2015 (Young Scientists Conference), участие в постер-сессии с докладом «Aggregate Text Representation for Information Retrieval in Collections of Text Documents», 24-28 августа 2015, г. Санкт-Петербург.

2) Летняя школа Факультета компьютерных наук НИУ ВШЭ, участие в постер-сессии с докладом «Using Annotated Suffix Trees for Fuzzy Full Text Search», 27-29 мая 2016, п. Вороново Московской обл.

3) RuSSIR-2016 (Young Scientists Conference), участие в постер-сессии с докладом «Using Annotated Suffix Trees for Fuzzy Full Text Search», 22-26 августа 2016, г. Саратов.

4) 3-й Колмогоровский семинар по компьютерной лингвистике и наукам о языке, участие в постер-сессии с докладом «Annotation of a Document Collection by Finding Thematic Fuzzy Clusters and Parsimoniously Lifting Them in a Domain Taxonomy», 25 апреля 2018, ФКН НИУ ВШЭ, г. Москва.

5) Общемосковский научный семинар «Математические методы анализа решений в экономике, бизнесе и политике», доклад на тему «Рубрикация коллекции документов с помощью формирования тематических нечетких

кластеров и их оптимального подъема в таксономии предметной области», 16 мая 2018, НИУ ВШЭ, Москва.

6) Общемосковский научный семинар «Математические методы анализа решений в экономике, бизнесе и политике», доклад на тему «Обобщение в таксономиях: модель, метод, приложения», 15 мая 2019, НИУ ВШЭ, Москва.

7) IARIA Content 2019, доклад на тему «Method for Generalization of Fuzzy Sets», 5-9 мая 2019, г. Венеция, Италия.

8) ICAISC-2019, участие в постер-сессии с докладом «Method for Generalization of Fuzzy Sets», 16-20 июня 2019, г. Закопане, Польша.

9) IEEE 2019 International Conference on Fuzzy Systems, доклад на тему «Using Taxonomy Tree to Generalize a Fuzzy Thematic Clusters», 23-26 июня 2019, г. Нью-Орлеан, США.

10) World Congress on Global Optimization - 2019, доклад на тему «Globally Optimal Parsimoniously Lifting a Fuzzy Query Set Over a Taxonomy Tree», 8-10 июля 2019, г. Мец, Франция.

11) IHIET-2019, участие в постер-сессии с докладом «A Method for Audience Extending in Programmatic Advertising by Using Parsimonious Generalization of User Segments», 22-24 августа 2019, г. Ницца, Франция.

По теме диссертации опубликованы статьи, перечисленные ниже.

Публикации повышенного уровня:

1) Frolov D., Mirkin B., Nascimento S., Fenner T. Using Taxonomy Tree to Generalize a Fuzzy Thematic Cluster // IEEE 2019 International Conference on Fuzzy Systems Proceedings, 2019. (CORE level A)

2) Frolov D., Mirkin B., Nascimento S., Fenner T. Method for Generalization of Fuzzy Sets // Rutkowski L., Scherer R., Korytkowski M., Pedrycz W., Tadeusiewicz R., Zurada J. Artificial Intelligence and Soft Computing. ICAISC 2019. Lecture Notes in Computer Science, vol 11508. Springer. С. 273-286. (Web of Science Q4, Scopus Q2)

Публикации стандартного уровня:

3) Frolov D., Mirkin B., Nascimento S., Fenner T. Globally Optimal Parsimoniously Lifting a Fuzzy Query Set Over a Taxonomy Tree //Le Thi H., Le H., Pham Dinh T. Optimization of Complex Systems: Theory, Models, Algorithms and Applications (WCGO). 2019. Advances in Intelligent Systems and Computing, vol 991. Springer, Cham. C. 779-789. (Scopus Q3)

4) Frolov D., Taran Z., Mirkin B. A Method for Audience Extending in Programmatic Advertising by Using Parsimonious Generalization of User Segments // Human Interaction and Emerging Technologies (IHIET) 2019. (Scopus Q3)

5) Frolov D. Using Annotated Suffix Trees for Fuzzy Full Text Search // Communications in Computer and Information Science. Information Retrieval. 10th Russian Summer School, RuSSIR 2016. Revised Selected Papers. Springer. (Scopus Q3)

6) Frolov D., Mirkin B., Nascimento S., Fenner T. Using Domain Taxonomy to Model Generalization of Thematic Fuzzy Clusters // IARIA Content 2019 Proceedings, C. 20-25. (Web of Science)

7) Frolov D.S. Annotated suffix tree as a way of text representation for information retrieval in text collections // Business Informatics. 2015. No. 4 (34). P. 63-70. (Фролов Д.С. Применение метода аннотированного суффиксного дерева в задачах поиска в коллекциях текстовых документов // Бизнес-Информатика. 2015. №4 (34). C. 63-70.) (Web of Science)

Другие публикации:

8) Frolov D., Mirkin B., Nascimento S., Fenner T. Finding an appropriate generalization for a fuzzy thematic set in taxonomy // Working paper WP7/2018/04, Moscow, Higher School of Economics Publ. House, 2018, 60 C.

0.8 Структура работы

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

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

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

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

Глава 3 описывает задачу оптимального обобщения нечетких кластеров в таксономии предметной области: модель и метод (ПарГеНМ). Приводятся иллюстративные примеры применения метода на модельных и реальных данных, описываются различные случаи работы метода, описывается моделирование подбора параметров метода. Приводится подробный практический пример применения метода ПарГеНМ в задаче разведочного поиска на примере коллекции научных публикаций журналов издательства Springer в области Науки о данных. Показывается, как с использованием таксономии Науки о данных, созданной на основе Таксономии компьютерных наук Всемирной ассоциации вычислительной техники ACM-CCS 2012, решается задача выявления новых тенденций научных исследований.

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

В заключении описываются результаты, достигнутые в ходе работы над

диссертацией и выносимые на защиту.

Объем работы. Диссертация состоит из введения, четырех глав, заключения и четырех приложений. Полный объём диссертации составляет 189 страниц, включая 26 иллюстраций и 30 таблиц. Список использованных источников содержит 163 наименования.

Благодарности

Автор диссертации благодарит своего научного руководителя, Ординарного профессора НИУ ВШЭ Бориса Григорьевича Миркина, за ценные советы и внимание во время всех этапов проведенного исследования, неоценимо повлиявшие на становление и формирование автора как специалиста в области анализа данных, а также искреннюю и заинтересованную поддержку во всех его начинаниях.

Кроме того, автор выражает благодарность за поддержку Научному фонду НИУ ВШЭ в рамках Исследовательского проекта НУГ «Концепт» («Разработка методов структуризации и концептуализации текстовых данных на основе таксономии предметной области», грант 19-04-019, 2018-2019) и Международной научно-учебной лаборатории анализа и выбора решений, в рамках субсидии, предоставленной НИУ ВШЭ Правительством Российской Федерации для внедрения проекта «5-100».

Глава 1

Обзор литературы и существующих решений

1.1 Задача информационного поиска 1.1.1 Введение в задачу информационного поиска

Информационным поиском называется совокупность процессов поиска неструктурированной информации, удовлетворяющей задаваемым запросам [14]. Если задано множество документов D = di и поисковый запрос Q, выражающий информационную потребность, то релевантностью (он английского relevance - уместность) документа di Е D поисковому запросу Q (будем обозначать релевантность как score(di,Q)) называется мера соответствия документа этому запросу, то есть степень удовлетворения информационного интереса, заданного запросом Q, документом di. В базовой постановке информационным поиском будет являться процесс извлечения списка документов из коллекции D, обладающих наибольшей релевантностью, в порядке убывания релевантности запросу Q. Практически всегда понятие «релевантность» сложно формализуется. Часто для создания коллекций (для тестов, обучения алгоритмов информационного поиска и др.) приходится прибегать к помощи асессоров-экспертов, вручную определяющих значения релевантности [14, 50].

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

переизданную и переведенную на русский язык, которая может являться базовым пособием при изучении задач информационного поиска. В работе [80], имеющей, скорее, научно-популярный характер, описываются многие методы и техники, применяемые в крупнейшей в мире поисковой системе Google. В [50] рассматриваются средства поиска, в том числе, и для таких специфических документов, как страницы интернет-форумов, где основная доля информации создается пользователями.

В простейшем случае задачу поиска документов по запросу можно рассматривать как задачу полнотекстового поиска или даже элементарную задачу о поиске подстроки в строке. Здесь существует множество методик, о которых говорится, например, в работах [101, 108]. Применяемые техники направлены, в основном, на соблюдение разумного баланса между качеством результатов, найденных по поисковому запросу, и временем выполнения запроса.

Объединение коллекций веб-сайтов приводит к очень масштабной задаче поиска страниц, которую решают поисковые системы. Здесь отметим обзорную работу [20], по праву считающуюся своего рода «классикой» среди подобных обзоров. Среди набора технологий, рассмотренных в ней, отметим методы поисковых индексов, применяющиеся для работы с большими коллекциями документов, а также прекрасное описание процедур индексирования и ранжирования.

1.1.2 Модели информационного поиска

Цель задач поиска информации состоит в том, чтобы предоставить пользователям множество документов, которые удовлетворят их информационные потребности. При этом такие потребности должны быть сформулированы в форме, «понятной» для механизма поиска. С другой стороны, все множество данных, по которому производится поиск, также должно быть представлено в формате, который позволит механизму поиска быстро идентифицировать потенциально релевантные документы. Очевидно, что в обоих случаях часть информации может быть потеряна в процессе преобразований. Поэтому для разработки моделей поиска важны как организация алгоритмов поискового механизма, так и задача представления информации.

Булев поиск

Одной из исторически первых групп моделей информационного поиска было семейство моделей Булева поиска [14]. Кратко поясним их основную идею.

Модель требует предварительной обработки коллекции документов и выявления из них всех возможных термов (в качестве которых могут выступать предобработанные признаки документов: Т = {¿1 , ¿2,...,£«}. Тогда представлением документа йг будет подмножество этого множества, такое, которое включает все встречающиеся в нем термы. Обозначим за О множество представлений всех документов коллекции.

Запросом в Булевой модели, выраженным в конъюнктивной нормальной форме, будет являться выражение

где Хг истинно для документа ф тогда и только тогда, когда Е . Тогда задачей является поиск всех таких документов из О, которые удовлетворяют Q. Этот процесс удобно выполнить в два этапа.

1) Для каждого х^ в Q найти множество документов Б^-, каждый из которых удовлетворяет .

2) Получить множество документов, удовлетворяющих Q, по формуле

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

Q = (Х1 V Х2 V ... ) Л ... Л (Хг V Хг+1 V ... ),

(1.1)

Бд = (Б1 и Б2 и ■ ■ ■ ) П ■ ■ ■ П (Бг и Бг+1 У ■ ■ ■ ).

(1.2)

Статистические модели

Двумя главными группами статистических моделей являются модели векторных пространств [109] и вероятностные модели [78]. Обе группы используют статистическую информацию (например, в частотной форме) для определения релевантности документов запросу. Отличия заключаются в способах ее применения.

Модели векторных пространств представляют и документы, и запросы в виде векторов в многомерном пространстве, размерностью которого является количество текстовых признаков, используемых для представления документов [37, 38]. Для осуществления процедуры поиска могут применяться индекс термов и ранжирующая функция (или несколько). Данные понятия будут рассмотрены ниже отдельно. Отметим, что модели данной группы имеют колоссальное распространение.

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

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

1.1.3 Применение индексирования и ранжирования

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

Метод обратного индекса

Метод обратного индекса (inverted index) [14] был введен для улучшения производительности алгоритмов обработки коллекций документов, информационного поиска, быстрого получения данных из коллекции.

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

/

fl ^ [nil, . . . ,nimi];

f2 ^ [n2i, . . . , n2m2]; . .

fК ^ [nKl,.. .

,пКтк].

Здесь fi - признаки, nij - номера содержащих их документов. K - общее количество признаков. Часто вместе с номерами документов хранят и так называемый вес его вхождения в конкретный документ [14].

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

Ранжирование

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

Одной из широко распространенных ранжирующих функций является Okapi Best Matching 25 (BM25) [115]. Вид функции основан на вероятностной структуре поиска, разработанной в 1970-х и 1980-х годах. Поисковая система Okapi, разработанная в Лондонском университете в 1980-х и 1990-х годах, была первой крупной поисковой системой, реализовавшей эту функцию. BM25 имеет массу

Список литературы диссертационного исследования кандидат наук Фролов Дмитрий Сергеевич, 2019 год

Библиографический список использованной литературы

[1] Агеев М.С. Методы автоматической рубрикации текстов, основанных на машинном обучении и знаниях экспертов / Диссертация на соискание ученой степени к.ф.-м.н. - М.: МГУ, 2004

[2] Агеев М., Кураленок И., Некрестьянов И. Официальные метрики РОМИП-2004 // Труды второго российского семинара по оценке методов информационного поиска. Под ред. И.С. Некрестьянова - Санкт-Петербург: НИИ Химии СПбГУ. - 2004. - С. 142-150.

[3] Бойцов Л. М. Классификация и экспериментальное исследование современных алгоритмов нечеткого словарного поиска // Труды Yandex. -2004. - Т. 6.

[4] Велихов П. Е. Использование открытых баз данных как семантических словарей для автоматической обработки текстов: система Texterra // Информационные процессы. - 2012. - Т. 12. - №. 3. - С. 320-329.

[5] Воронцов К. В., Потапенко А. А. Модификации EM-алгоритма для вероятностного тематического моделирования // Машинное обучение и анализ данных. - 2013. - T. 1, № 6. - С. 657-686.

[6] Воронцов К. В., Фрей А. И., Апишев М. А., Ромов П. А., Янина А. О., Суворова М. А. BigARTM: библиотека с открытым кодом для тематического моделирования больших текстовых коллекций // Аналитика и управление данными в областях с интенсивным использованием данных. XVII

Международная конференция ВАМБГО/КСВЬ'2015, Обнинск, 13-16 октября 2015.

[7] Гиляревский Р. С., Шапкин А. В., Белоозеров В. Н. Рубрикатор как инструмент информационной навигации / СПб.: Профессия, 2008. - 352 с.

[8] Горяинова, Е. Р., Панков А. Р., Платонов Е. Н. Прикладные методы анализа статистических данных / Е. Р. Горяинова., А. Р. Панков, Е. Н. Платонов -М.: Издательский дом Высшей школы экономики, 2012. - 310 с.

[9] Дубов М. С., Черняк Е. Л. Аннотированные суффиксные деревья: особенности реализации // В кн.: Доклады всероссийской научной конференции АИСТ-2013 / Отв. ред.: Е. Л. Черняк; науч. ред.: Д. И. Игнатов, М. Ю. Хачай, О. Баринова. М.: Национальный открытый университет «ИНТУИТ», 2013. С. 49-57.

[10] Иванов М. Н., Воронцов К. В. Применение монотонного классификатора ближайшего соседа в задаче категоризации текстов // Интеллектуализация обработки информации (ИОИ-2012): Докл.- Москва: Торус Пресс, 2012. С. 621-624.

[11] Кобзарь, А. И. Прикладная математическая статистика для инженеров и научных работников / А. И. Кобзарь. - М.: Физматлит, 2006. - 816 с.

[12] Коршунов А, Гомзин А. Тематическое моделирование текстов на естественном языке // Труды ИСП РАН. 2012. №1. С.215-244.

[13] Ломакин А. А. Совершенствование методов идентификации персональных данных в автоматизированной информационной системе «Электронный социальный регистр населения» Санкт-Петербурга //Электронный научный журнал «Исследовано в России» -С. - 2011. - Т. 156. - С. 163.

[14] Маннинг К. Д., Рагхаван П., Шютце Х. Введение в информационный поиск / Маннинг К. Д., Рагхаван П., Шютце Х. - М.: Вильямс, 2011. - 680 с.

[15] Миркин, Б. Г. Методы кластер-анализа для поддержки принятия решений: обзор / Б. Г. Миркин. - М.: Издательский дом Национального исследовательского университета «Высшая школа экономики», 2011 - 84 с.

[16] Миркин Б. Г., Черняк Е. Л., Чугунова О. Н. Метод аннотированного суффиксного дерева для оценки степени вхождения строк в текстовые документы // Бизнес-информатика. 2012. Т. 3. № 21. С. 31-41.

[17] Муравьев Н. А., Панченко А. И., Объедков С. А. Неологизмы в социальной сети Фейсбук // Компьютерная лингвистика и интеллектуальные технологии.

2014. №13, C. 440-454.

[18] Осминин П. Г. Современные подходы к автоматическому реферированию и аннотированию // Вестник ЮУрГУ. Серия: Лингвистика. 2012. 25. (дата обращения: 06.05.2019).

[19] Пономаренко А. Организация быстрого поиска без индекса //Автоматизация и современные технологии. - 2010. - №. 3. - С. 25-32.

[20] Сегалович И. Как работают поисковые системы // Мир Internet. - 2002. - Т. 10.

[21] Тодорико О. А., Добровольский Г. А. Оценка сигнатурных алгоритмов поиска по сходству в словаре //Вестник ХНТУ. - 2011. - №. 2. - С. 41.

[22] Турдаков Д. и др. Texterra: инфраструктура для анализа текстов // Труды Института системного программирования РАН. - 2014. - Т. 26. - №. 1.

[23] Фролов Д.С. Применение метода аннотированного суффиксного дерева для задач поиска в коллекциях текстовых документов // Бизнес-Информатика.

2015. №. 4 (34). С. 63-70.

[24] Фролов Д. С. Распределенная система хранения и рубрикации документов: магистерская диссертация. НИУ ВШЭ, Москва, 2014. https://www.hse.ru/ data/2014/06/06/1323476304/graduate_work.pdf

[25] Черняк Е. Л., Миркин Б. Г. Использование ресурсов Интернета для построения таксономии // В кн.: Доклады всероссийской научной конференции АИСТ 2013 / Отв. ред.: Е. Л. Черняк; науч. ред.: Д. И. Игнатов, М. Ю. Хачай, О. Баринова. М. : Национальный открытый университет «ИНТУИТ», 2013. С. 36-48.

[26] Шурыгин, А. М. Математические методы прогнозирования / А. М. Шурыгин. - М.: Телеком, 2009. - 180 с.

[27] OZON.ru - Каталог в XML [Электронный ресурс]. 2009 -. - Режим доступа: http://www.ozon.ru/context/partner_xml/ , свободный. - Загл. с экрана.

[28] Ресурсы сайта machinelearning.ru [Электронный ресурс]. 2012 -. - Режим доступа: http://www.maichinelearning.ru/, свободный. - Загл. с экрана.

[29] Фролов Д.С. Современные аспекты представления текстов при анализе естественного языка: классические и альтернативные подходы, сайт habrahabr.com [Электронный ресурс]. 2014 -. - Режим доступа: https://habr.com/ru/post/227199/, свободный. - Загл. с экрана.

[30] Altevogt P., Nitzsche R. Method of generating a distributed text index for parallel query processing: пат. 7966332 США. - 2011.

[31] Amancio D.R., Oliveira Jr. O.N., Costa L.F. Three-feature model to reproduce the topology of citation networks and the effects from authors' visibility on their h-index // Journal of Informetrics, 6, C. 427-434, 2012.

[32] Amancio D.R. Comparing the topological properties of real and artificially generated scientific manuscripts // Scientometrics, 105, С. 1763-1779, 2015.

[33] Ashraf J., Chang E., Hussain O. K., Hussain F. K. Ontology usage analysis in the ontology lifecycle: A state-of-the-art review // Knowledge-Based Systems, vol. 80, C. 34-47, 2015.

[34] Baeza-Yates R. et al. Proximity matching using fixed-queries trees // Annual Symposium on Combinatorial Pattern Matching. - Springer, Berlin, Heidelberg, 1994. - С. 198-212.

[35] Beneventano D., Dahlem N., El Haoum S., Hahn A., Montanari D., Reinelt M. Ontology-driven semantic mapping // Enterprise Interoperability III, Part IV, Springer, C. 329-341, 2008.

[36] Bezdek J.C., Hathaway R.J., Windham M.P. Numerical comparisons of the RFCM and AP algorithms for clustering relational data // Pattern Recognition, 24, C. 783-791, 1991.

[37] Bird S. NLTK: the natural language toolkit // Proceedings of the COLING/ACL on Interactive presentation sessions. - Association for Computational Linguistics, 2006. - С. 69-72.

[38] Bird S., Klein E., Loper E. Natural Language Processing with Python / Steven Bird, Ewan Klein, Edward Loper - OReilly Media, 2009 -. - 504 c.

[39] Blei D., Ng A., Jordan M. Latent Dirichlet allocation // Journal of Machine Learning Research, 3: 993-1022, January 2003

[40] Blei D. Probabilistic topic models // Communications of the ACM, 55 (4), C. 77-84, 2012.

[41] Brouwer R.K. A method of relational fuzzy clustering based on producing feature vectors using FastMap // Information Sciences, 179, C. 3561-3582, 2009.

[42] Buche P., Dibie-Barthelemy J., Ibanescu L. Ontology mapping using fuzzy conceptual graphs and rules // ICCS Supplement, C. 17-24, 2008.

[43] Buckley C., Voorhees E. Evaluating evaluation measure stability. //In Proc. of the SIGIR'00, C. 33-40, 2000.

[44] Burges C. et al. Learning to rank using gradient descent // Proceedings of the 22nd International Conference on Machine learning (ICML-05). - 2005. - C. 89-96.

[45] Chao P., Bin W., Chao D. Design and Implementation of Parallel Term Contribution Algorithm Based on Mapreduce Model // Open Cirrus Summit (OCS), 2012 Seventh. - IEEE, 2012. - C. 43-47.

[46] Chen C. Science mapping: A systematic review of the literature // Journal of Data and Information Science, vol. 2, no. 2, C. 1-40, 2017.

[47] Chen C., Ibekwe-SanJuan F., Hou J. The structure and dynamics of co-citation clusters: A multiple-perspective co-citation analysis // Journal of the American Society for information Science and Technology, vol 61, no. 7, 1386-1409, 2010.

[48] Chernyak E. An approach to the problem of annotation of research publications // Proceedings of the eighth ACM international conference on web search and data mining, ACM, 429-434, 2015.

[49] Chernyak E., Mirkin B. Refining a Taxonomy by Using Annotated Suffix Trees and Wikipedia Resources // Annals of Data Science, 2(1), C. 61-82, 2015.

[50] Croft W. B., Metzler D., Strohman T. Search engines: Information retrieval in practice - Reading: Addison-Wesley, 2010. - C. 283.

[51] Cutting D., Pedersen J. Optimization for dynamic inverted index maintenance // Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval. - ACM, 1989. - C. 405-411.

[52] Dietz L. et al. TREC complex answer retrieval overview // Proceedings of TREC. - 2017.

[53] Ding F. Click Prediction with Machine Learning Tools : gnc. - UCLA, 2018.

[54] Ducange P. et al. A novel approach for internet traffic classification based on multi-objective evolutionary fuzzy classifiers // 2017 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE). - IEEE, 2017. - C. 1-6.

[55] Elmasri R., Navathe S. Fundamentals of database systems. - Addison-Wesley Publishing Company, 2010.

[56] Frolov D.S. Annotated suffix tree as a way of text representation for information retrieval in text collections //Business Informatics. 2015. No. 4 (34). C. 63-70. DOI: 10.17323/1998-0663.2015.4.63.70.

[57] Frolov D. Using Annotated Suffix Trees for Fuzzy Full Text Search, in: Communications in Computer and Information Science. Information Retrieval. 10th Russian Summer School, RuSSIR 2016, Saratov, Russia, August 22-26, 2016, Revised Selected Papers. Springer, 2016.

[58] Fortunato S., Bergstrom C.T., Borner K., Evans J.A., Helbing D., Milojevic S., Petersen A.M., Radicchi F., Sinatra R., Uzzi B., Vespignani A., Waltman L., Wang D., Barabasi A.-L. Science of science // Science, 359 (6379), 2018.

[59] Frolov D., Mirkin B., Nascimento S., Fenner T. Finding an appropriate generalization for a fuzzy thematic set in taxonomy / Working paper WP7/2018/04, Moscow, Higher School of Economics Publ. House, 2018, 58 c.

[60] Gacto M.J., Alcalá R., Herrera F. Interpretability of linguistic fuzzy rule-based systems: An overview of interpretability measures // Information Sciences, vol. 181, C. 4340-4360, 2011.

[61] Galitsky, B. Machine learning of syntactic parse trees for search and classification of text // Engineering Applications of Artificial Intelligence. 26(3), C. 1072-1091, 2013.

[62] Gene Ontology Consortium Gene ontology consortium: going forward // Nucleic Acids Research, vol. 43 D1049-D1056, 2015.

[63] Goldberg Y., Levy O. word2vec Explained: deriving Mikolov et al.'s negative-sampling word-embedding method //arXiv preprint arXiv:1402.3722. -2014.

[64] Gormley C., Tong Z. Elasticsearch: The Definitive Guide: A Distributed Real-Time Search and Analytics Engine. - O'Reilly Media, Inc., 2015.

[65] Grossi R., Vitter J.S. Compressed suffix arrays and suffix trees with applications to text indexing and string matching // SIAM Journal on Computing, 35, 2 C. 378-407, 2005.

[66] Guru D. S., Harish B. S., Manjunath S. Symbolic representation of text documents // Proceedings of the Third Annual ACM Bangalore Conference. - ACM, 2010. -C. 18.

[67] Heinrich G. Parameter estimation for text analysis // Technical report, Fraunhofer IGD, 2005

[68] Hofmann T. Probabilistic Latent Semantic Analysis // UAI 1999: 289-296.

[69] Holmes D., McCabe M. C. Improving precision and recall for soundex retrieval //Proceedings. International Conference on Information Technology: Coding and Computing. - IEEE, 2002. - C. 22-26.

[70] Hou J., Yang X., Chen C. Emerging trends and new developments in information science: A document co-citation analysis (2009-2016) // Scientometrics, 115, 2, C. 869-892, 2018.

[71] Hwang K., Dongarra J., Fox G. C. Distributed and cloud computing: From parallel processing to the internet of things. - Morgan Kaufmann, 2013.

[72] Ianina A., Golitsyn L., Vorontsov K. Multi-objective topic modeling for exploratory search in tech news //Conference on Artificial Intelligence and Natural Language. - Springer, Cham, 2017. - C. 181-193.

[73] Jauvion G. et al. Optimization of a SSP's Header Bidding Strategy using Thompson Sampling // Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. - ACM, 2018. - C. 425-432.

[74] Kapur S., Ayman O. F., Chatwin R. E. Method and apparatus for representing text using search engine, document collection, and hierarchal taxonomy. / U.S. Patent No. 7,580,926. 2009.

[75] Kawamura T., Watanabe K., Matsumoto N., Egami S., Jibu M. Funding map using paragraph embedding based on semantic diversity / Scientometrics, vol. 116, no. 2, C. 941-958, 2018.

[76] Klavans R., Boyack K. W. Which type of citation analysis generates the most accurate taxonomy of scientific and technical knowledge? // Journal of the Association for Information Science and Technology, 68(4), C. 984-998, 2017.

[77] Krasnov F., Ushmaev O. Exploration of Hidden Research Directions in Oil and Gas Industry via Full Text Analysis of OnePetro Digital Library // International Journal of Open Information Technologies. - 2018. - T. 6. - №. 5. - C. 7-14.

[78] Kuehlmann A., McMillan K. L., Brayton R. K. Probabilistic state space search //Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design. - IEEE Press, 1999. - C. 574-579.

[79] Kunchukuttan A., Bhattacharyya P. Learning variable length units for SMT between related languages via Byte Pair Encoding // arXiv preprint arXiv:1610.06510. - 2016.

[80] Langville A. N., Meyer C. D. Google PageRank and beyond: The science of search engine rankings // Princeton University Press, 2011.

[81] Lau J. H., Baldwin T. An empirical evaluation of doc2vec with practical insights into document embedding generation // arXiv preprint arXiv:1607.05368. - 2016.

[82] Lee D, Cornet R, Lau F, De Keizer N. A survey of SNOMED CT implementations // Journal of Biomedical Informatics, vol. 46, no. 1, C. 87-96, 2013.

[83] Li T., Chen Y. Web Page Clustering Based on Searching Keywords // Intelligent Computation Technology and Automation (ICICTA), 2010 International Conference on. - IEEE, 2010. - T. 3. - C. 1163-1166.

[84] Li X., Guan D. Programmatic buying bidding strategies with win rate and winning price estimation in real time mobile advertising // Pacific-Asia Conference on Knowledge Discovery and Data Mining. - Springer, Cham, 2014. - C. 447-460.

[85] Lin J., Dyer C. Data-intensive text processing with MapReduce // Synthesis Lectures on Human Language Technologies. - 2010. - T. 3. - №. 1. - C. 1-177.

[86] LloretE., Boldrini E., Vodolazova T., MartAnez-Barco P., MunozR., Palomar M. A novel concept-level approach for ultra-concise opinion summarization // Expert Systems with Applications, 42(20), C. 7148-7156, 2015.

[87] Luxburg van U. A tutorial on spectral clustering // Statistics and Computing, vol. 17, C. 395-416, 2007.

[88] Marchionini G. Exploratory Search: from finding to understanding. Communications of the ACM. 2006, 49(4), C. 41-46.

[89] Mei J.P., Wang Y., Chen L., Miao C. Large scale document categorization with fuzzy clustering // IEEE Transactions on Fuzzy Systems, 25(5), 1239-1251, 2017.

[90] Mirkin B. Clustering: A Data Recovery Approach / Chapman and Hall/CRC Press, 2012.

[91] Mirkin B. G. Core Concepts of Data Analysis / B. G. Mirkin. - Springer, 2012. -416 C.

[92] Nanni F. et al. Benchmark for complex answer retrieval //Proceedings of the ACM SIGIR international conference on theory of information retrieval. - ACM, 2017. - C. 293-296.

[93] Mirkin B., Nascimento S. Analysis of Community Structure, Affinity Data and Research Activities using Additive Fuzzy Spectral Clustering, Technical Report 6, School of Computer Science, Birkbeck University of London, 2009.

[94] B. Mirkin, S. Nascimento, T. Fenner, L.M. Pereira Building fuzzy thematic clusters and mapping them to higher ranks in a taxonomy, Int. Journal of Software Informatics, vol. 4, no. 3, C. 257-275, 2010.

[95] Mirkin B., Nascimento S. Additive spectral method for fuzzy cluster analysis of similarity data including community structure and affinity matrices, Information Sciences, vol. 183, no. 1, C. 16-34, 2012.

[96] Mirkin B., Orlov M. Three aspects of the research impact by a scientist: measurement methods and an empirical evaluation // Optimization, Control, and Applications in the Information Age. Springer. C. 233-259.

[97] Murtagh F, Orlov M., Mirkin B. Qualitative judgement of research impact: Domain taxonomy as a fundamental framework for judgement of the quality of research // Journal of Classification, 35(1), C. 5-28, 2018.

[98] Moon. T.K. The expectation-maximization algorithm // IEEE Signal Processing Mag., vol. 13, C. 47-60, Nov. 1996

[99] Mueller G., Bergmann R. Generalization of Workflows in Process-Oriented Case-Based Reasoning // FLAIRS Conference, C. 391-396, 2015.

[100] Nallaperuma D, De Silva D. A participatory model for multi-document health information summarisation // Australasian Journal of Information Systems, 21.

[101] Natarajan J. et al. Full-Text Search // Pro T-SQL 2012 Programmer's Guide. -Apress, 2012. - C. 287-315.

[102] Nascimento S., Fenner T., Mirkin B. Representing research activities in a hierarchical ontology // Procs. of 3rd International Workshop on Combinations of Intelligent Methods and Applications (CIMA 2012), Montpellier, France, August, 28, C. 23-29, 2012.

[103] Ogilvie P., Callan J. P. Experiments Using the Lemur Toolkit // TREC. - 2001. - T. 10. - C. 103-108.

[104] Osborne F., Salatino A., Birukou A., Motta E. Automatic Classification of Springer Nature Proceedings with Smart Topic Miner // Groth P. et al. (Eds) The Semantic Web - ISWC 2016. Lecture Notes in Computer Science, vol 9982, C. 383-399. Springer, Cham, 2016.

[105] Pampapathi R., Mirkin B., Levene M. A suffix tree approach to anti-spam email filtering // Machine Learning, 65(1), C. 309-338, 2006.

[106] Page L. et al. The PageRank citation ranking: Bringing order to the web. -Stanford InfoLab, 1999.

[107] Pennington J., Socher R., Manning C. Glove: Global vectors for word representation //Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP). - 2014. - С. 1532-1543.

[108] Pitts W. M. Full text search capabilities integrated into distributed file systems-Incrementally Indexing Files : заяв. пат. 13/959,534 США. - 2013.

[109] Platzer C., Dustdar S. A vector space search engine for web services //Third European Conference on Web Services (EC0WS'05). - IEEE, 2005. - С. 9

[110] Popov A., Iakovleva D. Adaptive look-alike targeting in social networks advertising // Procedia Computer Science. - 2018. - Т. 136. - С. 255-264.

[111] Punjabi S., Bhatt P. Robust Factorization Machines for User Response Prediction // Proceedings of the 2018 World Wide Web Conference on World Wide Web. - International World Wide Web Conferences Steering Committee, 2018. - С. 669-678.

[112] Rijsbergen van C. J. Information Retrieval / Butterworth's and Co., London, U.K., 2 edition, 1979.

[113] Rinaldi A. M. An ontology-driven approach for semantic information retrieval on the Web // ACM Trans. on Internet Technologies, vol. 9, no.3, article 10, 2009.

[114] Ristad E. S., Yianilos P. N. Learning string-edit distance //IEEE Transactions on Pattern Analysis and Machine Intelligence. - 1998. - Т. 20 - С. 522-532.

[115] Robertson S. et al. The probabilistic relevance framework: BM25 and beyond //Foundations and Trends in Information Retrieval. - 2009. - Т. 3.(4). - С. 333-389.

[116] Robinson P., Bauer S. Introduction to Bio-Ontologies / Chapman and Hall/CRC Press, 2011.

[117] Rodgers S., Thorson E. Digital advertising: Theory and research. - Taylor & Francis, 2017.

[118] Ruotsalo T., Peltonen J., Eugster M., Glowacka D., Floreen P., Myllymaki P., Jacucci G., Kaski S. Interactive Intent Modeling for Exploratory Search // ACM Transactions on Information Systems, 2018, 36 (4): 1-46.

[119] Salatino A.A., Osborne F., Motta E. How are topics born? Understanding the research dynamics preceding the emergence of new areas / Peer J Computer Science, 3, 2017.

[120] Salton G., Buckley C. Term-weighting approaches in automatic text retrieval // Information Processing and Management, vol. 25, no 5, C. 513-523, 1998.

[121] Santos A.P., Rodrigues F. Multi-Label Hierarchical Text Classification Using the ACM Taxonomy // Proceedings of 14th Portuguese Conference on Artificial Intelligence, (Aveiro, Portugal, October 12-15), C. 553-564, 2010.

[122] Sayedi A. Real-Time Bidding in Online Display Advertising, 2017.

[123] Sebastiani F. Machine learning in automated text categorization // Journal of ACM Computing Surveys, 1, 34, C. 1-42, 2002.

[124] She X., Wang S. Research on Advertising Click-Through Rate Prediction Based on CNN-FM Hybrid Model // 2018 10th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC). - IEEE, 2018. - T. 2. - C. 56-59.

[125] Shepard R.N., Arabie P. Additive clustering: representation of similarities as combinations of discrete overlapping properties // Psychological Review, vol. 86, C. 87- 123, 1979.

[126] Silva F.N., Amancio D.R., Bardosova M., Costa L.F., Oliveira Jr. O.N. Using network science and text analytics to produce surveys in a scientific topic // Journal of Informetrics, 10, C. 487-502, 2016.

[127] Snow R., Jurafsky D., Ng A.Y. Semantic taxonomy induction from heterogenous evidence // Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics, Association for Computational Linguistics, C. 801-808, 2006.

[128] Song, Y., Liu, S., Wang, H., Wang, Z., Li, H. Automatic taxonomy construction from keywords / U.S. Patent No. 9,501,569. Washington, DC: U.S. Patent and Trademark Office, 2016.

[129] Soto de A.R. A hierarchical model of a linguistic variable // Information Sciences, vol. 181, C. 4394-4408, 2011.

[130] Sokal R, Michener C. A statistical method for evaluating systematic relationships // University of Kansas Science Bulletin. vol. 38. C. 1409-1438. 1958.

[131] Strehl A., Ghosh J., Mooney R. Impact of similarity measures on web-page clustering // Workshop on Artificial Intelligence for Web Search (AAAI 2000). - 2000. - C. 58-64.

[132] Suchal J., Navrat P. Full text search engine as scalable k-nearest neighbor recommendation system //IFIP International Conference on Artificial Intelligence in Theory and Practice. - Springer, Berlin, Heidelberg, 2010. - C. 165-173.

[133] Usman M., Britto R., Boerstler J., Mendes E. Taxonomies in software engineering: A Systematic mapping study and a revised taxonomy development method // Information and Software Technology, 85, C. 43-59, 2017.

[134] Vedula N., Nicholson P.K., Ajwani D., Dutta S., Sala A., Parthasarathy S. Enriching Taxonomies With Functional Domain Knowledge // The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval, ACM, C. 745-754, 2018.

[135] Vorontsov K. V., Potapenko A. A. Tutorial on Probabilistic Topic Modeling: Additive Regularization for Stochastic Matrix Factorization // AIST'2014, Analysis of Images, Social networks and Texts. - Lecture Notes in Computer Science (LNCS), Springer Verlag-Germany, 2014

[136] Vulic I., Moens M. F. Monolingual and cross-lingual information retrieval models based on (bilingual) word embeddings //Proceedings of the 38th international ACM SIGIR conference on research and development in information retrieval. -ACM, 2015. - C. 363-372.

[137] Waitelonis J., Exeler C., Sack H. Linked data enabled generalized vector space model to improve document retrieval // Proceedings of NLP & DBpedia

2015 workshop in conjunction with 14th International Semantic Web Conference (ISWC), CEUR-WS, vol. 1486, 2015.

[138] Wang C., Blei D. Collaborative topic modeling for recommending scientific articles // Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, C. 448-456, 2011.

[139] Wang Y., Kitsuregawa M. Evaluating contents-link coupled web page clustering for web search results // Proceedings of the eleventh international conference on Information and knowledge management. - ACM, 2002. - C. 499-506.

[140] Wang, C., He, X., Zhou, A. A Short Survey on Taxonomy Learning from Text Corpora: Issues, Resources and Recent Advances, // Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, C. 1190-1203, 2017.

[141] Wang J., Yuan S., Zhang W. Real-time bidding based display advertising: mechanisms and algorithms //European Conference on Information Retrieval. -Springer, Cham, 2016. - C. 897-901.

[142] Wei X., Croft W. B. LDA-based document models for ad-hoc retrieval // Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval. - ACM, 2006. - C. 178-185.

[143] Weinberger K. Q., Saul L. K. Distance metric learning for large margin nearest neighbor classification //Journal of Machine Learning Research. - 2009. - T. 10. - C. 207-244.

[144] Wess S., Althoff K. D., Derwand G. Using k-d trees to improve the retrieval step in case-based reasoning //European Workshop on Case-Based Reasoning. -Springer, Berlin, Heidelberg, 1993. - C. 167-181.

[145] White R., Roth R. Exploratory Search: beyond the Query-Response paradigm. San Rafael, CA: Morgan and Claypool, 2009.

[146] Williams M. et al. Applications with asyncio and Twisted // Expert Twisted. -Apress, Berkeley, CA, 2019. - C. 305-316.

[147] Wong B., Vigfusson Y., Sirer E. G. Hyperspaces for object clustering and approximate matching in peer-to-peer overlays // Proceedings of the 11th USENIX workshop on Hot topics in operating systems. - USENIX Association, 2007. - С. 8.

[148] Yang R. et al. An Empirical Analysis on Research of Small World Based on Bibliometrics and HIST Algorithm. - 2010.

[149] Yuan, Y., Wang, F., Li, J., Qin, R. A survey on real time bidding advertising. In Service Operations and Logistics, and Informatics (SOLI) // 2014 IEEE International Conference. IEEE. C. 418-423.

[150] Zhou B. et al. A distributed text mining system for online web textual data analysis // Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC), 2010 International Conference on. - IEEE, 2010. - С. 1-4.

[151] The 2012 ACM Computing Classification System [Electronic resource]. 2019 -. -Режим доступа: http://www.acm.org /about/class/2012 , свободный. - Загл. с экрана.

[152] Celery: Distributed Task Queue [Electronic resource]. 2019 -. - Режим доступа: http://www.celeryproject.org/ , свободный. - Загл. с экрана.

[153] Gensim: Topic modelling for humans [Electronic resource]. 2018 -. - Режим доступа: http://radimrehurek.com/gensim/ , свободный. - Загл. с экрана.

[154] IAB Tech Lab Content Taxonomy [Electronic resource]. 2019 -. - Режим доступа: https://www.iab.com/guidelines/iab-quality-assurance-guidelines-qag-taxonomy/, свободный. - Загл. с экрана.

[155] Interactive Advertising Bureau (IAB) [Electronic resource]. 2019 -. - Режим доступа: https://www.iab.com/ , свободный. - Загл. с экрана.

[156] Merriam-Webster website. [Electronic resource]. 2019 -. - Режим доступа: https://www.m,erriam,-webster.com,/dictionary/generalize , свободный. - Загл. с экрана.

[157] MongoDB [Electronic resource]. 2015 -. - Режим доступа: http://www.mongodb.org/ , свободный. - Загл. с экрана.

[158] OpenRTB Protocol [Electronic resource]. 2019 -. - Режим доступа: https://www.iab.com/guidelines/real-time-bidding-rtb-project/ , свободный. -Загл. с экрана.

[159] Python 3 library for reading and manipulating the TREC Complex Answer Retrieval (CAR) dataset [Electronic resource]. 2019 -. - Режим доступа: https://trec-car-tools.readthedocs.io/en/latest/ , свободный. - Загл. с экрана.

[160] Reuters-21578 Test Collection [Electronic resource]. 2015 -. - Режим доступа: http://www.daviddlewis.com/resources/ testcollections/reuters21578/ , свободный. - Загл. с экрана.

[161] SciPy scientific library [Electronic resource]. 2019 -. - Режим доступа: https://scipy.org/ , свободный. - Загл. с экрана.

[162] USPTO patent full-text databases [Electronic resource]. 2015 -. - Режим доступа: http://patft.uspto.gov/ , свободный. - Загл. с экрана.

[163] Wikipedia Lists of common misspellings [Electronic resource]. 2019 -. - Режим доступа: https://en.wikipedia.org/wiki/Wikipedia:Lists_of_common_misspellings, свободный. - Загл. с экрана.

Список иллюстраций

1.1 Аннотированное суффиксное дерево для строки «mining»....... 26

1.2 АСД для строки

'inference': шаг 1............................... 29

1.3 АСД для строки

'inference': шаг 2............................... 29

1.4 Итоговое АСД для строки 'inference'................... 30

2.1 Графики зависимости полноты и точности для рассматриваемых методов, коллекция №1........................... 61

2.2 Графики зависимости полноты и точности для рассматриваемых методов, коллекция №2........................... 61

2.3 Пример функционирования поисковой системы, использующей метод АСДП, на четком запросе..................... 65

2.4 Пример функционирования поисковой системы, использующей метод АСДП, на нечетком запросе.................... 66

3.1 Фрагмент таксономии, черные прямоугольники соответствуют элементам, принадлежащим множеству: простой случай (a) и более сложный (b)................................. 68

3.2 Обобщение нечеткого множества запроса, показанного на рисунке 3.1 (b) с помощью его отображения в корень дерева. Цена этого обобщения - четыре пробела (gap).................... 72

3.3 Обобщение нечеткого множества запроса, показанного на рисунке 3.1 (b) с помощью его отображения в корень левого поддерева. Цена такого обобщения - один пробел (gap) и один выброс (offshoot). . . 72

3.4 Иллюстративная таксономия T и нечеткое множество запроса со значениями принадлежности, назначенными листьям, умноженным на 1000; (b) T после обрезания и аннотирования значениями принадлежности и значениями важности пробелов V(■)........ 79

3.5 Поднятие нечеткого субкластера Computer Vision. Вычислены значения принадлежности для всех узлов дерева............ 81

3.6 Поднятие нечеткого субкластера Computer Vision. Выполнен базовый шаг алгоритма ПарГеНМ.................... 82

3.7 Поднятие нечеткого субкластера Computer Vision. Применение рекурсивного шага алгоритма к корню левого поддерева....... 82

3.8 Поднятие нечеткого субкластера Computer Vision. Применение рекурсивного шага алгоритма к корню правого поддерева...... 83

3.9 Поднятие нечеткого субкластера Computer Vision. Узлы пронумерованы в соответствии с Таблицей 3.3............. 84

3.10 Фрагмент таксономии, демонстрирующий отсутствие подъема кластера................................... 86

3.11 Результаты подъема кластера L: Learning. Пробелы пронумерованы,

см. таблицу 3.11...............................100

3.12 Результаты подъема кластера R. Пробелы пронумерованы, см. таблицу 3.12. Обозначения к рисунку приведены в легенде рисунка

3.11......................................102

3.13 Фрагмент результатов подъема кластера C. Обозначения к рисунку приведены в легенде рисунка 3.11.....................104

3.14 Схематичный результат подъема кластера 3. Обозначения к рисунку приведены в легенде рисунка 3.11....................113

3.15 Схематичный результат подъема кластера 4. Обозначения к рисунку приведены в легенде рисунка 3.11.....................114

4.1 Общая схема взаимодействия в рекламной модели Programmatic. . . 117

4.2 Фрагмент таксономии IAB.........................120

4.3 Подъем пользовательских сегментов...................124

Список таблиц

1.1 Вычисление оценок релевантности для суффиксов строки 'fence'. . 31

1.2 Вычисление оценок релевантности для суффиксов строки 'since'. . . 31

1.3 Среднее время выполнения запроса из одного слова в системе gensim. 48

2.1 Сравнительная точность рассматриваемых методов поиска на уровне N = 5 документов, коллекция №1................ 55

2.2 Сравнительная точность рассматриваемых методов поиска на уровне N =10 документов, коллекция №1................ 56

2.3 Сравнение характеристики MAP рассматриваемых методов поиска

на коллекции №3 (TREC CAR)...................... 57

2.4 Среднее время обработки запроса для различных методов на коллекции №1 (время работы CPU, с).................. 57

2.5 Среднее время обработки запроса для различных методов на коллекции №2 (время работы CPU, с).................. 58

2.6 Среднее время обработки запроса для различных методов на коллекции №3 (время работы CPU, с).................. 58

2.7 Точность на уровнях N = 5 и N =10 документов........... 60

2.8 Среднее время обработки запроса для различных методов (время работы CPU, с)............................... 62

2.9 Результаты сравнения методов нечеткого поиска (место 1-2 приравнено рангу 1.5)........................... 62

2.10 Влияние длины строки в АСД на время обработки запроса, коллекция №2 (время работы CPU, с).................. 63

3.1 Результаты применения ПарГеНМ для узлов A и B в обрезанном дереве для нечеткого множества запроса и, показанного на рисунке 3.4; значения весов штрафа для пробелов и выбросов Л = 0.2 и y = 0.9. 80

3.2 Результаты вычислений в корне для нечеткого множества запроса u, показанного на рисунке 3.4, на основе вычислений, показанных в таблице 3.1; значения весов штрафа для пробелов и выбросов Л = 0.2

и y = 0.9................................... 80

3.3 Множества узлов и значения переменных, полученные в процессе подъема нечеткого субкластера Computer Vision............ 85

3.4 Различные значения принадлежностей и весов штрафа, приводящие ко всем возможным описаниям в строках с 1 по 5 для иллюстративной таксономии на рисунке 3.4 (а). В алгоритме использованы нормированные значения принадлежностей u, распространенные на остальные узлы дерева в соответствии с

квадратичным условием в (3.11)..................... 88

3.5 Список журналов Springer, связанных с Наукой о данных, которые использовались в качестве источников текстов для коллекции публикаций................................. 90

3.6 Подмножество таксономии Системы классификации компьютерных наук Всемирной ассоциации вычислительной техники ACM (ACM-CCS) 2012, касающееся Науки о данных; несколько тем самых высоких рангов........................... 92

3.7 Количества релевантных тем для документов рассматриваемой коллекции. .......................... 94

3.8 Кластер L "Learning": темы со значением принадлежности более 0.15. 98

3.9 Кластер R "Retrieval": темы со значением принадлежности более 0.15. 99

3.10 Кластер C "Clustering": темы со значением принадлежности более 0.15. 99

3.11 Пробелы, полученные в процессе подъема кластера

Ь. ....................101

3.12 Пробелы, полученные в процессе подъема кластера

И,. .....................103

4.1 Примеры результатов расширения пользовательских сегментов. . . 123

4.2 Показатели для рекламной кампании 1.................125

4.3 Показатели для рекламной кампании 2.................126

4.4 Показатели для рекламной кампании 3.................126

4.5 Эффективность метода ОПС.......................127

Приложение 1: Таксономия Науки о данных

согласно ACM-CCS 2012

Листья таксономии, добавленные авторами, помечены звездочкой «*».

Index Level 1 Level 2 Level 3 Level 4 Level 5 Level 6

1. Theory of computation

1.1. Theory and algorithms for application domains

1.1.1. Machine learning theory

1.1.1.1. Sample complexity and generalization bounds

1.1.1.2. Boolean function learning

1.1.1.3. Unsupervised learning and clustering

1.1.1.4. Kernel methods

1.1.1.4.1. Support vector machines

1.1.1.4.2. Gaussian processes

1.1.1.4.3.* Modelling

1.1.1.5. Boosting

1.1.1.6. Bayesian analysis

1.1.1.7. Inductive inference

1.1.1.8. Online learning theory

1.1.1.9. Multi-agent learning

1.1.1.10. Models of learning

1.1.1.11. Query learning

1.1.1.12. Structured prediction

1.1.1.13. Reinforcement learning

1.1.1.13.1. Sequential decision making

1.1.1.13.2. Inverse reinforcement learning

1.1.1.13.3. Apprenticeship learning

1.1.1.13.4. Multi-agent reinforcement learning

1.1.1.13.5. Adversarial learning

1.1.1.14. Active learning

1.1.1.15. Semi-supervised learning

1.1.1.16. Markov decision processes

1.1.1.17. Regret bounds

1.1.2. Database theory

1.1.2.1. Data exchange

1.1.2.2. Data provenance

1.1.2.3. Data modeling

1.1.2.4. Database query languages (principles)

1.1.2.5. Database constraints theory

1.1.2.6. 1.1.2.7.

1.1.2.8.

1.1.2.9.

1.1.2.10. 1.1.2.11.

1.1.2.12.

2.

2.1. 2.1.1.

2.1.1.1. 2.1.1.2.

2.1.1.3.

2.1.1.4.

2.1.1.5.

2.1.1.6.

2.1.1.7.

2.1.1.8.

2.1.1.8.1. 2.1.1.8.2. 2.1.1.8.3.

2.1.2.

2.1.2.2. 2.1.2.3.

2.1.2.5. 2.1.2.5.1.

2.1.2.6. 2.1.3.

2.1.3.1.

2.1.3.2.

2.1.3.3.

2.1.3.4.

2.1.3.5.

2.1.3.5.1.

2.1.3.5.2.

2.1.3.5.3.

2.1.3.5.4.

2.1.3.7.

2.1.3.7.1.*

2.1.3.8.

2.1.3.8.1.

2.1.3.8.2.

2.1.3.9.

2.1.4.

2.1.5.

2.1.5.1.

2.1.5.2.

2.1.5.3. 2.1.5.3.1.

2.1.5.4.

2.1.5.5.

2.1.5.6.

2.1.5.7.

2.1.5.8.

2.1.5.9.

Mathematics of

computing

Probability and statistics

Probabilistic representations

Probabilistic inference problems

Probabilistic reasoning algorithms

Probabilistic algorithms Statistical paradigms

Database interoperability Data structures and

algorithms for data

management

Database query processing and optimization (theory) Data integration Logic and databases Theory of database privacy and security

Incomplete, inconsistent, and uncertain databases

Bayesian networks

Markov networks

Factor graphs

Decision diagrams

Equational models

Causal networks

Stochastic differential

equations

Nonparametric

representations

Maximum likelihood

estimation

Bayesian computation Computing most probable explanation

Hypothesis testing and confidence interval

computation Density estimation

Max marginal computation

Variable elimination Loopy belief propagation Variational methods Expectation maximization Markov-chain Monte Carlo methods

Sequential Monte Carlo methods

Kalman filters and hidden Markov models

Resampling methods Random number generation

Queueing theory Contingency table analysis Regression analysis

Time series analysis Survival analysis Renewal theory Dimensionality reduction Cluster analysis Statistical graphics

Kernel density estimators Spline models Bayesian nonparametric models

Quantile regression

Gibbs sampling

Metropolis-Hastings

algorithm

Simulated annealing Markov-chain Monte

Carlo convergence

measures

Factorial HMM

Bootstrapping Jackknifing

Robust regression

2 1.5.10. Exploratory data analysis

2 1.6. Stochastic

processes

2 1.6.1. Markov processes

2 1.7. Nonpara-

metric

statistics

2 1.8. Distribu- tion

functions

2 1.9. Multiva- riate

statistics

3 Information

systems

3 1. Data

management

systems

3 1.1. Database

design and

models

3 1.1.1. Relational database model

3 1.1.2. Entity relationship models

3 1.1.3. Graph-based database

models

3 1.1.3.1. Hierarchical data models

3 1.1.3.2. Network data models

3 1.1.4. Physical data models

3 1.1.5. Data model extensions

3 1.1.5.1. Semi-structured data

3 1.1.5.2. Data streams

3 1.1.5.3. Data provenance

3 1.1.5.4. Incomplete data

3 1.1.5.5. Temporal data

3 1.1.5.6. Uncertainty

3 1.1.5.7. Inconsistent data

3 1.2. Data

structures

3 1.2.1. Data access methods