Методы обнаружения и противодействия автоматизированному сбору информации с веб-ресурсов тема диссертации и автореферата по ВАК РФ 05.13.19, кандидат наук Менщиков Александр Алексеевич

• Менщиков Александр Алексеевич
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Менщиков Александр Алексеевич

СОДЕРЖАНИЕ

РЕФЕРАТ

SYNOPSIS

ВВЕДЕНИЕ

ГЛАВА 1. СОВРЕМЕННОЕ СОСТОЯНИЕ ПРОБЛЕМЫ АВТОМАТИЗИРОВАННЫХ УГРОЗ БЕЗОПАСНОСТИ ВЕБ-РЕСУРСОВ

1.1. Угрозы и атаки на веб-ресурсы

1.1.1 Атаки на процессы аутентификации и авторизации

1.1.2 Атаки на клиентов

1.1.3 Исполнение кода на веб-сервере

1.1.4 Логические атаки

1.1.5 Атаки на отказ в обслуживании

1.1.6 Спам

1.1.7 Разглашение информации

1.1.8 Автоматизированные атаки

1.2 Автоматизированные угрозы

1.3. Автоматизированный сбор информации с веб-ресурсов

1.4. Классификация веб-роботов

1.4.1 Структура запроса

1.4.2 Назначение веб-роботов

1.4.3 Политика повторного посещения

1.4.4 Мотивация веб-роботов

1.5. Проблемы автоматизированного сбора информации

1.6. Классификация методов обнаружения веб-роботов

1.7. Проблемы обнаружения автоматизированного сбора информации

1.7.1 Идентификация сессий

1.7.2 Изменяющийся User-Agent

1.8. Базовые принципы обнаружения веб-роботов

1.9. Правовое регулирование веб-роботов

1.10. Выводы

ГЛАВА 2. МЕТОДЫ ОБНАРУЖЕНИЯ ВЕБ-РОБОТОВ

2.1. Задача обнаружения веб-роботов

2.2 Анализ поведения пользователей и автоматизированных средств

2.3 Анализ методов обнаружения веб-роботов

2.4 Анализ структуры веб-ресурса

2.4.1 Создание графа связности веб-ресурса

2.5 Анализ структуры веб-роботов

2.5.1 Обобщённая архитектура веб-роботов

2.5.2 Распределённые веб-роботы

2.6. Методы обнаружения веб-роботов на основе структурных характеристик

2.6.1 Использование Марковского алгоритма кластеризации

2.6.2 Исследование шаблонных запросов файлов разных типов

2.6.3 Анализ графа запросов сессии

2.6.4 Байесовский подход к обнаружению

2.6.5 Способ онлайн обнаружения

2.6.6 Предсказание поведения веб-роботов

2.6.7 Использование наивного Байесовского классификатора

2.6.8 Использование деревьев решений

2.6.9 Использование нейронных сетей

2.7. Характеристики, используемые для обнаружения автоматизированных угроз

2.7.1 Метод на основе выделения функциональных признаков страниц

2.7.2 Метод на основе содержимого файлов

2.7.3 Метод на основе типа ресурса

2.8. Задача извлечения информации с веб-ресурса

2.9. Методы обнаружения веб-роботов

2.9.1. Синтаксический анализ логов

2.9.2. Поведенческий анализ

2.9.3. Аналитические методы

2.10. Программные методы обнаружения и противодействия

2.10.1. Блокировка источника запросов

2.10.2. Использование учётных записей

2.10.3. Использование CAPTCHA

2.10.4. Использование сложной JavaScript логики

2.10.5. Динамическое изменение структуры страницы

2.10.6. Ограничение частоты запросов и объема загружаемых данных

2.10.7. Защита отображения данных

2.11 Характеристики обнаружения

2.11.1 Характеристики HTTP запроса

2.11.2 Временные характеристики

2.11.3 Поведенческие характеристики

2.12 Метод обнаружения веб-роботов на основе семантического анализа

посещённых страниц

2.13 Метод обнаружения веб-роботов на основе анализа графа пользовательского поведения

2.13.1 Построение графа веб-ресурса

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

2.14. Выводы

ГЛАВА 3. РАЗРАБОТКА СИСТЕМЫ ОБНАРУЖЕНИЯ И ПРОТИВОДЕЙСТВИЯ АВТОМАТИЗИРОВАННОМУ СБОРУ ИНФОРМАЦИИ С ВЕБ-РЕСУРСОВ

3.1. Алгоритм обнаружения и противодействия веб-роботам

3.1.1. Этап инициализации

3.1.2. Этап обучения

3.1.3. Этап обнаружения

3.1.4. Этап реагирования

3.2. Методика подготовки данных для обучения системы обнаружения веб-роботов

3.3. Меры по противодействию автоматизированным угрозам

3.4. Вопрос онлайн обнаружения

3.5. Архитектура системы обнаружения и противодействия веб-роботам

3.6. Выводы

ГЛАВА 4. ПРАКТИЧЕСКИЕ АСПЕКТЫ РЕАЛИЗАЦИИ КОМПЛЕКСНОЙ СИСТЕМЫ ОБНАРУЖЕНИЯ И ПРОТИВОДЕЙСТВИЯ

АВТОМАТИЗИРОВАННОМУ СБОРУ ИНФОРМАЦИИ С ВЕБ-РЕСУРСОВ

4.1 Сравнение облачных веб-роботов

4.2 Сравнение промышленных веб-роботов

4.3 Используемые наборы данных

4.4 Архитектура экспериментального стенда

4.5 Архитектура системы реагирования

4.6 Архитектура подсистемы хранения и обработки информации

4.7 Оценка результатов обнаружения веб-роботов

4.8. Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК РИСУНКОВ

СПИСОК ТАБЛИЦ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЯ

Приложение А. Акты о внедрении

Приложение В. Результаты интеллектуальной деятельности

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

РЕФЕРАТ

Введение диссертации (часть автореферата) на тему «Методы обнаружения и противодействия автоматизированному сбору информации с веб-ресурсов»

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

Степень разработанности темы. Разработка и совершенствование алгоритмов и методов обнаружения и противодействия веб-роботам является перспективным направлением исследований в области безопасности веб-ресурсов. Об этом свидетельствуют исследования таких зарубежных учёных как Derek Doran, Aijun An, Swapna S. Gokhale, Ning Xie, Kyle Brown, Nathan Rude и Natalija Vlajic, а также большое количество посвященных данной тематике докладов на ведущих международных конференциях, таких как OWASP AppSec, ICMLA, ASONAM, ICCCAS и др.

В то же время, выделение направления защиты от автоматизированного сбора

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

Содержание диссертации соответствует пунктам 3, 5, 6 паспорта специальности 05.13.19 - «Методы и системы защиты информации, информационная безопасность»:

- Методы, модели и средства выявления, идентификации и классификации угроз нарушения информационной безопасности объектов различного вида и класса;

- Методы и средства (комплексы средств) информационного противодействия угрозам нарушения информационной безопасности в открытых компьютерных сетях, включая Интернет;

- Модели и методы формирования комплексов средств противодействия угрозам хищения (разрушения, модификации) информации и нарушения информационной безопасности для различного вида объектов защиты вне зависимости от области их функционирования.

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

Для достижения поставленной цели были сформулированы и решены следующие задачи:

1. Исследование современных подходов к решению проблемы обнаружения и противодействия автоматизированным атакам на веб-ресурсы;

2. Разработка методов обнаружения и противодействия автоматизированному сбору информации с веб-ресурсов;

3. Разработка алгоритма обнаружения и противодействия автоматизированному сбору информации с веб-ресурсов;

4. Разработка комплекса программных средств для обнаружения и противодействия автоматизированным атакам на веб-ресурсы;

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

Объектом исследования является веб-ресурс, среда его функционирования и запросы к нему из сети Интернет.

Предметом исследования являются закономерности работы алгоритмов, методов и средств обнаружения и противодействия автоматизированным атакам на веб-ресурсы.

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

Научная новизна результатов диссертации:

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

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

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

4. Предложена методика сбора и расчёта необходимых характеристик и построения графа связности страниц веб-ресурса, а также определения тематики страниц для обеспечения функционирования алгоритма обнаружения и противодействия автоматизированному сбору информации с веб-ресурсов.

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

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

Основные положения, выносимые на защиту:

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

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

3. Алгоритм обнаружения и противодействия автоматизированному сбору информации с веб-ресурсов, использующий комбинацию методов

обнаружения с использованием анализа графа пользовательского поведения и семантического анализа посещённых страниц;

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

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

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

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

1. Ist International Scientific and Technical Conference «Fundamental and practical aspects of computer technology» (FPACT'2018);

2. Международный конгресс по интеллектуальным системам и информационным технологиям (IS&IT-2018);

3. 10th International Conference On Security of Information and Networks (SIN'17);

4. Second International Scientific Conference «Intelligent Information Technologies for Industry» (IITI'17);

5. XX Международная научная конференция «The 20th Conference of Open Innovations Association FRUCT and ISPIT 2017 seminar»;

6. XX, XXI Международная объединенная научная конференция «Интернет и современное общество» (2017г., 2018г.);

7. VII, VIII Международная научно-техническая и научно-методическая конференция «Актуальные проблемы инфокоммуникаций в науке и образовании» (2018г., 2019г.);

8. VII, VIII Научно-практическая конференция молодых ученых «Вычислительные системы и сети (Майоровские чтения)» (2015 г., 2016г.);

9. IV, V, VI, VII, VIII Всероссийский конгресс молодых ученых (20152019гг.);

10. I, II Всероссийский студенческий форум «Инженерные кадры - будущее инновационной экономики России» (2015г., 2016г.);

11.XLV, XLVI, XLVII, XLVIII, Научная и учебно-методическая конференция Университета ИТМО (2016-2019гг.);

Результаты исследования были представлены на конкурсе грантов Правительства Санкт-Петербурга в 2019 году («Система обнаружения веб-роботов»), где автор был удостоен звания победителя конкурса грантов для студентов вузов, расположенных на территории Санкт-Петербурга, аспирантов вузов, отраслевых и академических институтов, расположенных на территории Санкт-Петербурга.

Внедрение результатов

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

- В федеральном государственном автономном образовательном учреждении высшего образования «Национальный исследовательский университет ИТМО»;

- НИР №619296 «Разработка методов создания и внедрения киберфизических систем»;

- НИР №617026 «Разработка методов интеллектуального управления

киберфизическими системами с использованием квантовых технологий»;

- НИР №615878 «Проектирование методов создания безопасных технологических и информационных систем»;

- СПб ГБУК «ГМП «Исаакиевский собор»;

- ООО «Технокон».

Система обнаружения автоматизированного сбора информации с веб-ресурсов зарегистрирована в Федеральной службе по интеллектуальной собственности (№2017661508 от 16.10.2017).

Публикации по теме диссертации. Результаты диссертационной работы отражены в 14 публикациях, в том числе 6 публикациях в рецензируемых журналах из перечня ВАК и 3 публикациях в рецензируемых журналах из перечня Scopus. Получено 1 свидетельство государственной регистрации на программу для ЭВМ.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 170 наименований, 3 приложений. Общий объем работы составляет 223 страницы, в том числе 27 рисунков и 9 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава посвящена современным тенденциям в области обеспечения безопасности веб-ресурсов и противодействия автоматизированным угрозам. В данной главе приводится анализ состояния проблемы обнаружения и противодействия автоматизированным угрозам безопасности веб-ресурсов. Особое внимание уделяется онтологии автоматизированных угроз из проекта OWASP Automated Threats и их влияния на веб-ресурсы. Приводится механизм идентификации классов таких угроз, онтология, признаки возникновения и возможные схемы противодействия. Фиксируется конкретное подмножество угроз,

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

В разделе 1.1 описаны существующие угрозы и атаки на веб-ресурсы, а также фиксируется область автоматизированных угроз. Раздел 1.2 целиком посвящен подробному разбору термина «автоматизированные угрозы» и классификации данных угроз. В разделе 1.3 разбираются существующие области применения, сценарии и этапы процессов обнаружения, противодействия и восстановления после реализации угроз. Раздел 1.4 содержит классификацию веб-роботов. Проблемы и ограничения средств автоматизированного сбора информации с веб-ресурсов приведены в разделе 1.5. Раздел 1.6 посвящен классификации методов обнаружения веб-роботов. Основные сложности обнаружения рассматриваемых угроз приводятся в разделе 1.7. Раздел 1.8 описывает базовые принципы, на которых строится обнаружение веб-роботов. В разделе 1.9 описываются современные принципы регулирования действий веб-роботов.

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

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

В разделе 2.2 приводится многоаспектный анализ поведения веб-роботов и легитимных пользователей на сайте. Исследуются виды веб-ресурсов, их схемы реализации, протоколы взаимодействия с ними и алгоритмы действий веб-роботов. Изучаются проблемы и ограничения, с которыми сталкиваются веб-роботы. В разделе 2.3 приводится всесторонний анализ существующих методов обнаружения и противодействия веб-роботам. Вводится классификация таких методов, а также основные характеристики и особенности каждого из них, влияющие на сценарии использования, ограничения и преимущества в различных условиях реализации. Раздел 2.4 посвящен анализу структуры веб-ресурса. Предлагаемые в данной работе методы опираются на знание о структуре и содержании защищаемого веб-ресурса, что предполагает построение графа связности страниц. Разбираются разные подходы к оптимальному решению данной задачи. Описывается процедура составления карты веб-ресурса (рисунок 1). В разделе 2.5 анализируется структура веб-роботов, приводится обобщенная архитектура типичного веб-робота, описывается принцип функционирования распределенных веб-роботов и сценарии их работы с точки зрения практики.

Получение ссылки на страницу из очереди

Извлечение документа по ;сьпке

Выполнение скриптов нг странице

Сохранение содержимого страницы

Парсинг содержимого

И ¿в." ече кие с: ылок

г V

Проверка никальности

Добавление ссылки в очередь

Рисунок 1. Процедура составления карты связности веб-ресурса

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

поведения веб-робота и использование Байесовского классификатора для обнаружения. Рассматриваются методы с применением решающих деревьев и нейронных сетей. В разделе 2.7 предлагаются дополнительные возможные характеристики, используемые для обнаружения автоматизированных угроз: основанные на выделении функциональных признаков страниц и типа загружаемого ресурса. Раздел 2.8 описывает задачу извлечения информации с веб-ресурсов, решаемую веб-роботами. В разделе 2.9 описываются классические подходы к обнаружению веб-роботов: синтаксический анализ логов, поведенческий анализ, аналитические методы. Программные методы обнаружения (такие как блокировка источника запроса, использование учетных записей, CAPTCHA, сложная JavaScript логика, динамическое изменение структуры страницы, ограничение частоты запросов и защита отображения данных) отдельно разбираются в разделе 2.10. В разделе 2.11 описываются классические временные и структурные характеристики, участвующие в процессе обнаружения. В разделе 2.12 описывается метод обнаружения веб-роботов на основе семантического анализа посещённых страниц. Описываются характеристики обнаружения, особенности применения данного метода и результаты его использования, демонстрирующие увеличение точности и полноты обнаружения за счёт введения семантических признаков. Приводятся результаты работы данного метода для различных алгоритмов классификации на наборе данных веб-сервера (таблица 1).

Таблица 1. Результаты сравнения различных классификаторов

Классификатор Точность Полнота Fi-мера Время

RandomForestClassifier 0.93 0.94 0.93 19.4с

GradientBoostingClassifier 0.97 0.97 0.97 48.8с

XGBClassifier 0.97 0.96 0.96 11.6с

KNeighborsClassifier 0.94 0.92 0.93 4.77с

МЬРС^йег 0.94 0.93 0.93 21.3с

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

Рассматривается матрица переходов веб-роботов и легитимных пользователей между тематиками страниц (рисунок 2), показана возможность применения данного подхода к обнаружению в реальном времени по мере поступления новых запросов.

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

На основе семантического содержания, страницы веб-ресурса группируются в несколько объединенных по смыслу тематик при помощи автоматической кластеризации [37, 133, 137]. Подбор оптимального количества тематик рассчитывается автоматически [138]. Распределение переходов между различными тематиками в рамках сессии определяет шаблон поведения. На рисунке 2 представлены наиболее частотные переходы между парами тематик для веб-роботов и легитимных пользователей. Видно, насколько для пользователей более характерно совершать переходы внутри одной тематики, а для веб-роботов переходить из кластеров, определяющих страницы-каталоги (№5, №28), на обычные страницы сайта с различным содержимым.

8 -> 8 ■ 16 16

■ 5 -> 8

■ 5 5

■ 8 5

■ 2 8 ■ 8 -> 1 ■ 8^2 ■ 8 ^ 16 ■ 16 8

Рисунок 2. Переходы пользователей (слева) и веб-роботов (справа) между

тематиками

Распределение частот переходов между тематиками используется как одна из характеристик, влияющих на итоговое решение об обнаружении. Так итоговую вероятность появления шаблона переходов между тематиками удобно высчитывать по образу, описанному в [91], как произведение вероятности входа sA и вероятностей соответствующих переходов PA,B и PB,C между тематиками (формула 2).

Ра,в,с = sA х РА,В х РВ,С (2)

Полученная вероятность для каждой сессии S = (х1,... ,хп) высчитывается по формуле 2 и классифицирует сессию как пользовательскую или роботизированную на основе порогового значения if log PrS|R < log Рг5|И , где R -матрица и вектор вероятностей входа для роботизированных сессий, а Ш - матрица и вектор для сессий обычных пользователей. Для упрощения вычислений значения логарифмируются и результат высчитывается по формуле 3 [91-92].

п

log PrS| (s,P) = log SX1 + ^ log Pxi-ixi (3)

i=2

Производится сравнение с существующими методами обнаружения веб-роботов. Отдельное внимание уделяется методике обучения системы, формированию кластеризации тематик страниц (рисунок 3) и подбору гиперпараметров для максимизации ROC AUC (рисунок 4).

1.0

0.4

✓ S

✓ y'

у ✓ s *

- ROC curve (area 0.98)

0.4

0.6

Falsi Positive Rate

Рисунок 4. ROC кривая и значение AUC

Раздел 2.13 посвящен методу обнаружения веб-роботов на основе анализа графа пользовательского поведения (рисунок 5). Подробно приводится отличие существующих методов поведенческого анализа и предложенной схемы.

Рисунок 5. Граф связности страниц веб-ресурса

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

-О.Ов 0.00 005 О.Ю 0.15 020 0.25 0.30 -0.025 0.000 0.025 0.050 0075 0.100 0.125 0.150 0.175

Рисунок 6. Сравнение распределений значений графовых характеристик (closenesscentrality и betweennesscentrality) для людей и веб-роботов

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

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

Рисунок 7. Схема обнаружения и противодействия веб-роботам

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

Список литературы диссертационного исследования кандидат наук Менщиков Александр Алексеевич, 2019 год

Литература

1. Menshchikov A. et al. A study of different web-crawler behaviour //2017 20th Conference of Open Innovations Association (FRUCT). - IEEE, 2017. - Pp. 268-274.

2. OWASP Automated threat Handbook 2018. URL: https://www.owasp.org/images/3/33/Automated-threat-handbook.pdf (дата обращения: 03.06.2019).

3. Zabihimayvan M. et al. A soft computing approach for benign and malicious web robot detection // Expert Systems with Applications. - 2017. - Vol. 87. - Pp. 129-140.

4. Doran D., Morillo K., Gokhale S. S. A comparison of web robot and human requests //Proceedings of the 2013 IEEE/ACM international conference on advances in social networks analysis and mining. - ACM, 2013. - Pp. 1374-1380.

5. Hamidzadeh J., Zabihimayvan M., Sadeghi R. Detection of Web site visitors based on fuzzy rough sets //Soft Computing. - 2018. - Vol. 22. - №. 7. - Pp. 2175-2188.

6. Bursztein E., Martin M., Mitchell J. Text-based CAPTCHA strengths and weaknesses //Proceedings of the 18th ACM conference on Computer and communications security. - ACM, 2011. - Pp. 125-138.

7. UC Irvine Machine Learning Repository. URL: https://archive.ics.uci.edu/ml/index.php (дата обращения: 03.06.2019).

References

1. Menshchikov A. et al. A study of different web-crawler behaviour //2017 20th Conference of Open Innovations Association (FRUCT). - IEEE, 2017. - Pp. 268-274.

2. OWASP Automated threat Handbook 2018. Available at: https://www.owasp.org/images/3Z33/ Automated-threat-handbook.pdf (accessed: 03 June 2019).

3. Zabihimayvan M. et al. A soft computing approach for benign and malicious web robot detection // Expert Systems with Applications. - 2017. - Vol. 87. - Pp. 129-140.

4. Doran D., Morillo K., Gokhale S. S. A comparison of web robot and human requests //Proceedings of the 2013 IEEE/ACM international conference on advances in social networks analysis and mining. - ACM, 2013. - Pp. 1374-1380.

5. Hamidzadeh J., Zabihimayvan M., Sadeghi R. Detection of Web site visitors based on fuzzy rough sets //Soft Computing. - 2018. - Vol. 22. - №. 7. - Pp. 2175-2188.

6. Bursztein E., Martin M., Mitchell J. Text-based CAPTCHA strengths and weaknesses //Proceedings of the 18th ACM conference on Computer and communications security. - ACM, 2011. - Pp. 125-138.

7. UC Irvine Machine Learning Repository. Available at: https://archive.ics.uci.edu/ml/index.php (accessed: 03 June 2019).

МЕНЩИКОВ Александр Алексеевич, аспирант, Университет ИТМО. 197101, г. Санкт-Петербург, Кронверкский пр., 49. E-mail: [e-mail]

ГАТЧИН Юрий Арменакович, доктор технических наук, профессор, Университет ИТМО. 197101, г. Санкт-Петербург, Кронверкский пр., 49. E-mail: [e-mail]

КОРОБЕЙНИКОВ Анатолий Григорьевич, доктор технических наук, профессор, заместитель директора по науке, Санкт-Петербургский филиал Федерального государственного бюджетного учреждения науки Института земного магнетизма, ионосферы и распространения радиоволн им. Н.В.Пушкова Российской академии наук. 199034, г. Санкт-Петербург, Менделеевская линия, 3. E-mail: [e-mail]

MENSHCHIKOV Alexander, postgraduate student, St. Petersburg National Research University of Information Technologies, Mechanics and Optics. 197101, St. Petersburg, Russia. Kronverksky pr., 49. E-mail: [e-mail]

GATCHIN Yurij, Dr.Sc., Professor, St. Petersburg National Research University of Information Technologies, Mechanics and Optics. 197101, St. Petersburg, Russia. Kronverksky pr., 49. E-mail: [e-mail]

KOROBEYNIKOV Anatoly, Dr.Sc., Professor, Deputy Director for Science, Pushkov Institute of Terrestrial Magnetism, Ionosphere and Radio Wave Propagation of the Russian Academy of Sciences (IZMIRAN). 199034, St. Petersburg, Russia. Mendeleevskaya liniya, 3. E-mail: [e-mail]

05.13.19

А.А. Менщиков, Ю.А. Гатчин д-р техн. наук

Федеральное государственное автономное образовательное учреждение высшего образования «Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики», факультет информационной безопасности и компьютерных технологий, кафедра проектирования и безопасности компьютерных систем, Санкт-Петербург, [e-mail]

АЛГОРИТМ И МЕТОДИКА ОБНАРУЖЕНИЯ И ПРОТИВОДЕЙСТВИЯ

ВЕБ-РОБОТАМ

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

Ключевые слова: веб-роботы, информационная безопасность, защита веб-ресурсов, краулеры, обнаружение веб-роботов.

В настоящее время, согласно отчётам компаний, занимающихся мониторингом сети Интернет, автоматизированные угрозы являются актуальными для веб-ресурсов [1]. Трафик, принадлежащий роботизированным средствам, не уступает пользовательскому. Специальные средства автоматизации действий на веб-ресурсе называются веб-роботами [2]. Такие средства несут множество автоматизированных угроз и угрожают приватности персональных данных и авторскому праву. Открытый проект обеспечения безопасности веб-приложений OWASP выпустил новый документ «Automated Threats to Web Applications» подробно описывающий актуальность данного рода угроз и причины их возникновения [3]. Всё это свидетельствует о масштабе проблемы и заинтересованности владельцев веб -ресурсов в её решении. Необходимо разрабатывать алгоритмы и методики обнаружения и противодействия таким средствам.

Сегодня существуют исследования поведения веб-роботов на веб-ресурсе и попытки использовать различные синтаксические и поведенческие особенности для составления механизма обнаружения автоматизированных средств [4, 5]. Данные методы преимущественно используют информацию о действиях пользователей на веб-ресурсе из логов веб-сервера. Такой информации не всегда достаточно, чтобы сформировать значимые отличительные признаки веб-роботов. Такие методы могут хорошо работать для одного веб-ресурса и не работать на другом за счёт отсутствия учёта специфики и структуры каждого конкретного веб-ресурса [6]. Также, определённым недостатком существующих методов является недостаточная проработанность алгоритмов реализации процессов обучения, обнаружения и противодействия.

Можно разделить существующие сегодня способы обнаружения веб-роботов на четыре категории: синтаксический анализ логов, статистический анализ трафика, аналитические методы и технические методы [7, 8].

Одной из важных отличительных особенностей предлагаемого алгоритма является использование метода обнаружения веб-роботов на основе анализа графа пользовательского поведения с привязкой к структуре и карте связности страниц защищаемого веб-ресурса, а также метода обнаружения веб-роботов на основе семантического анализа посещённых страниц с учётом переходов между различными тематиками [9, 10].

Алгоритм состоит из следующих четырёх этапов:

1. Этап инициализации, включающий в себя получение и расчёт характеристик обучения;

2. Этап обучения, включающий расчёт выбранных моделей и структур на основе полученной обучающей выборки;

3. Этап обнаружения, осуществляющий алгоритм отложенного или онлайн обнаружения;

4. Этап реагирования.

На этапе инициализации выполняются следующие шаги:

1. Задаётся множество используемых характеристик обнаружения (из логов веб-сервера или имеющихся средств мониторинга);

2. Построение карты связности страниц веб-ресурса;

3. Формирование множества тематик страниц веб-ресурса при помощи алгоритма кластеризации и подбор оптимального числа тематик;

4. Расчёт графовых и семантических характеристик узлов веб-ресурса;

5. Построение матриц переходных вероятностей между тематиками для пользователей и веб-роботов;

6. Конфигурирование порога срабатывания и сценария реагирования.

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

На этапе обнаружения выполняются следующие шаги:

1. Обновление характеристик сессии при появлении нового запроса;

2. Классификация сессии S с помощью обученной классификационной модели.

3. Вычисление вероятности того, что сессия принадлежит веб-роботу и сравнение с пороговым значением.

Финальный этап реагирования заключается в применении заранее сконфигурированного сценария реагирования (показ CAPTCHA, блокирование источника запроса, блокирование сессии и учётной записи пользователя, создание инцидента в системе мониторинга).

Методика обнаружения и противодействия веб-роботам включает в себя следующие группы процессов:

• Определение состава окружения веб-ресурса и уровня взаимодействия с ним;

• Определение структуры взаимодействия пользователя с сайтом (API, HTTP запросы, WebSocket);

• Взаимодействие с ресурсом для составления графа связности страниц и расчёта семантических характеристик;

• Выбор множества признаков для обучения классификационной модели;

• Ввод системы в эксплуатацию;

• Обнаружение и противодействие веб-роботов;

• Контроль и мониторинг, периодическое обновление информации о ресурсе и корректировка классификационной модели.

Был произведён эксперимент по обнаружению веб-роботов. В соответствии с разработанными алгоритмом и методикой были рассчитаны характеристики для каждой сессии в рамках рассматриваемого набора данных, построены карты связности страниц и тематик веб-ресурсов. В результате использования предлагаемого алгоритма точности и полнота обнаружения увеличились (Fi мера достигла значения 0.97), что превышает результаты классических методов как по точности, так и по полноте обнаружения. Количество ошибок первого и второго рода уменьшилось.

Список литературы

1. Bad bot report [Электронный ресурс]. - Режим доступа: https://resources.distilnetworks.com/travel/2018-bad-bot-report - Загл. с экрана, свободный, Яз. англ. (дата обращения 01.06.2019)

2. Менщиков А.А., Комарова А.В., Гатчин Ю.А. Изучение поведения средств автоматизированного сбора информации с веб-ресурсов // Вопросы кибербезопасности. -

2017. - №. 3 (21)

3. OWASP Automated Threats to Web Applications [Электронный ресурс]. - Режим доступа: https://www.owasp.org/index.php/File:Automated-threat-handbook.pdf - Загл. с экрана, свободный, Яз. англ. (дата обращения 01.06.2019)

4. D. Derek, S. Gokhale A Classification Framework for Web Robots // Journal of American Society of Information Science and Technology. - 2012. - V. 63. - P. 2549-2554.

5. Derek Doran, S. Gokhale Web robot detection techniques: overview and limitations. Data Mining and Knowledge Discovery. - 2011. - С. 183-210.

6. Wang W. et al. Using combinatorial testing to build navigation graphs for dynamic web applications // Software Testing, Verification and Reliability. - 2016. - Т. 26. - №. 4. - С. 318-346.

7. Zabihimayvan M. et al. A soft computing approach for benign and malicious web robot detection // Expert Systems with Applications. - 2017. - Т. 87. - С. 129-140.

8. Sisodia D.S., Verma S., Vyas O.P. Agglomerative approach for identification and elimination of web robots from web server logs to extract knowledge about actual visitors //Journal of Data Analysis and Information Processing. - 2015. - Т. 3. - №. 01. - С. 1.

9. Hamidzadeh J., Zabihimayvan M., Sadeghi R. Detection of Web site visitors based on fuzzy rough sets //Soft Computing. - 2018. - Т. 22. - №. 7. - С. 2175-2188.

10. Lagopoulos A., Tsoumakas G., Papadopoulos G. Web Robot Detection: A Semantic Approach //2018 IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI). - IEEE,

2018. - С.968-974.

Метод автоматизированного извлечения адресов из неструктурированных текстов

А.В. Комарова, А.А. Менщиков, А.В. Полев, Ю.А. Гатчин

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

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

I. Введение

На сегодняшний день данные, которые представлены в сети Интернет, очень слабо структурированы. Фактически отсутствует какая-либо стандартизация, либо иной принцип упорядочивания данных в сети. Каждая организация решает данную проблему удобным ей способом, что приводит к появлению большого числа противоречащих друг другу стандартов. Помимо этого, мало кто задумывается не только о структуре, но и о пригодности данных к автоматизированной обработке программными средствами [1].

Сегодня вопросы автоматизированной обработки больших объемов информации и структурирования представления данных в сети возникают повсеместно. Это связано как с развитием информационных ресурсов,

Менщиков Александр Алексеевич. Университет ИТМО. Факультет информационной безопасности и компьютерных технологий, кафедра проектирования и безопасности компьютерных систем, аспирант. e-mail: [e-mail].

Комарова Антонина Владиславовна. Университет ИТМО. Факультет информационной безопасности и компьютерных технологий, кафедра проектирования и безопасности компьютерных систем, аспирант. e-mail: [e-mail].

Полев Александр Васильевич. ИП Полев Александр Васильевич e-mail: [e-mail].

Гатчин Юрий Арменакович. Университет ИТМО. Факультет информационной безопасности и компьютерных технологий, кафедра проектирования и безопасности компьютерных систем, профессор. e-mail: [e-mail].

так и с появлением совершенно новых инструментов в общественной сфере. Одним из основных потребителей данной информации являются информационные сервисы, представляющие инициативы открытых данных и «Умных городов» [2]. Именно Город сегодня становится основой общественного развития, точкой роста современной экономики. Ни для кого не секрет, что тематика «Умных городов» с каждым годом набирает все большую и большую популярность. Многие исследователи высказываются о том, что «Smart City» или «Умный город» - это город будущего, и такие масштабные проекты требуют совершенно иного подхода к организации хранения и обработки информации в Интернете [3].

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

1. Разработка и внедрение новых принципов представления информации;

2. Модификация существующей информации в вид, пригодный для автоматизированной обработки.

Задача информационного поиска включает в себя процессы сбора, обработки и передачи полученной информации лицам, в ней заинтересованным [5]. В более точном смысле, данный процесс можно определить как совокупность следующих этапов: определение и формулировка информационного запроса, выявление информационных источников, извлечение релевантной информации, оценка полученных результатов поиска [6].

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

II. Актуальность

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

Согласно программе «Цифровая экономика РФ» к 2025 году в России планируется создать 50 «Умных городов» [8]. Программа развития предполагает несколько направлений. Среди них есть такие, как информационная безопасность и «Умный город». Проект данной программы был создан Минкомсвязью России и одобрен президентом Владимиром Путиным. Все созданные государственными органами документы и данные планируется перенести в единое централизованное облачное хранилище, а доли услуг, предоставляемых органами государственной власти, в электронном виде составит 80%.

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

Технологии обработки больших данных (Big Data), а также автоматизированного поиска информации будут иметь большое значение для «Умных городов»: для осуществления прозрачности в расчётах ЖКХ, для анализа количества трафика на дорогах, для поиска информации о свободных парковочных местах, для поиска своевременной информации о движении общественного транспорта, для получения данных с датчиков наполнения мусорных баков, для оптимизации полива парков и освещения улиц и дорог, для контроля уровня загрязнения в городе, а также уровня радиации, для быстрого получения медицинской помощи и т.д. [9]

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

III. Извлечение адресов

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

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

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

Комбинация данных подходов с учетом постоянного итерационного исправления алгоритма и ручной верификации исключительных случаев позволила авторам минимизировать ошибки и повысить точность обнаружения адресов для произвольных текстов [10-12].

Статистические подходы зависят не только от обучающей выборки и программной реализации, но и от используемого языка. Существующие исследования преимущественно касаются английского языка. Так, зарубежные исследователи предлагают использовать извлечение информации на основе статистики с выделением ключевых слов из текста и тегирования с помощью условных случайных полей. Ручное обучение на базе корпуса из 400 сайтов дало результаты точности порядка 0,89 и F-меры 0,74 [13]. Подход на основе шаблонов и пороговых значений совпадения с шаблоном позволил получить точность порядка 0,745 и F-меру 0,734 при извлечении адресов из досок объявлений сайта Yahoo [14, 15]. Использование всеобъемлющих справочников позволило

исследователям из Германии достичь полноты 0,95 [16], однако, точность распознавания в статье не приводится. К тому же, появление подобного справочника относительно затруднено применительно к России. Использование гибридного подхода позволяет получить значения F-меры порядка 0,73 и 0,93 в зависимости от того, учитывать ли полноту распознаваемости адреса [17]. Исследователи из Китая смогли добиться точности распознавания адресов в 0,90, используя статистический подход и учитывая особенности языка [18].

IV. Источники данных

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

Данные с известными параметрами использовались

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

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

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

Для оценки результатов использовались численные оценки качества.

р = Т (1)

Т„ + Е„

Я = _Т^_ (2)

Т + F

1 Р N

Точность определения адреса Р вычисляется как отношение числа верных классификаций к общему числу классификаций является ли слово заданным элементом адреса (правильных и ошибочных).

Полнота определения адреса Я вычисляется как доля верных классификаций элемента адреса относительно общего количества элементов данного класса.

Одновременно изучались точность и полнота как в среднем по разным типам элементов (улица, дом, ориентир), так и внутри данных групп.

На основе данных метрик вычислялась объединённая метрика Б, задаваемая следующим образом.

F = 2*Р^Я (3)

Р + Я

V. Процесс извлечения адресов

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

VI. Процесс очистки текста

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

Разбиение на слова

Текст после предварительной очистки разбивается на слова (токены) в соответствии с регулярным выражением [!,?;\S]+. Дополнительно фильтруются излишние токены из черного списка. Это помогает максимизировать скорость работы системы за счёт перебора только наиболее релевантных вариантов. Каждому токену сопоставляется тип (числовой, строковый). Также, каждый токен проверяется на то, является ли он географическим ориентиром, названием улицы или специальным якорем. Якорь - это слово, которое отсылает к появлению в пределах нескольких следующих слов искомой информации. Например, якорями являются слова «ул.», «Д.», «корп» и прочие.

Система позволяет варьировать размер окна, который указывает на количество слов в сегменте поиска.

В таблице представлены несколько наиболее эффективных якорей и их типы.

Таб. 1. Типы «якорей»

Тип якоря Якорь

Улица «Ул», «г.», «район»

Ориентир «Площадь», «метро», «станция», «проспект»

Номер дома «д.», «дом»

Дополнительный модификатор «этаж», «кв.», «стр», «строение», «корп»

Каждый якорь дополнительно модифицируется при поиске с учётом регистронезависимости, падежа, рода, и числа.

Помимо текстовых модификаторов, существуют шаблонные модификаторы, которые учитывают варианты сокращённого последовательного написания адреса: например, «д. 24A/5».

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

Рисунок 1. Схема используемых методов

VII. Реализация

Была написана программа на языке Python, которая состоит из трёх модулей. Модуль формирования словарей включает в себя функционал добавления новых текстовых якорей, ключевых слов, регулярных выражений и географических ориентиров, а также связей между ними. Его задачей является обновление базы данных и пересчёт моделей после внесения изменений и обновлений. Модуль классификации получает на вход неструктурированный текст и извлекает из него адреса и географические ориентиры. Модуль предполагает настройку уровня чувствительности, при необходимости можно отключить любые эвристические методы и оставить только поиск с использованием регулярных выражений и якорных слов. Модуль тестирования отвечает за сбор информации и поочерёдную проверку каждого текста из массива данных. В модуль встроен краулер, осуществляющий сбор данных с сайтов объявлений, а также генератор отчёта по результатам анализа, который позволяет обнаруживать ошибки и трудные случаи классификации для внесения их в словарь.

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

Для определения относится ли текстовый элемент к тому или иному классу использовался метод «один против всех». Были построены несколько классификаторов по числу возможных компонент адреса и оценена принадлежность слова или группы слов к каждому из них.

Для обучения классификатора были выбраны следующие основные признаки:

- количество распознанных якорей и расстояние до них от опорного слова;

- количество числовых элементов и расстояние до них от опорного слова;

- количество слов в блоке;

- соотношение типов якорей в блоке (например, улицы, дома, ориентиры);

- количество слов в предложении;

- порядок распознанных слов (например, улица после дома или номер дома после улицы);

- расстояния Левенштейна опорного слова до каждого из якорей выше определённого порога;

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

Рисунок 2. Схема системы сбора данных

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

Рис. 3. Схема извлечения информации

VIII. Результаты

Авторами был загружен набор текстов пользователей сайтов объявлений, связанных с недвижимостью. Многопоточным парсером в автоматизированном режиме было собрано 20 тысяч сообщений. Набор из 960 постов был размечен вручную для обучения дерева классификаций и составления фильтров. Данные также были разделены на две части - для тех сайтов, где объявления формировались в виде обычного неформатированного текста и для тех, где помимо неформатированного текста были представлены отдельные поля для ввода адреса: город, улица, номер дома, номер корпуса и строения. Данные с известными параметрами использовались для обучения и верификации модели, а также дополнительно были просмотрены вручную и очищены от испорченных записей. Изучались исключительные и типовые форматы. Система была протестирована на нескольких выборках для проверки ошибок и итерационного уточнения модели. В результате из полного набора было извлечено 880 валидных адресов. Также, осуществлялись контрольные проверки на случайных выборках из корпуса текстов.

\ адрес Улица Дом Модифик

Рис. 4. Точность классификации компонент адреса

Полный адрес Улица Дом Модификатор Ориентир

Рис. 5. Б-мера классификации компонент адреса

В итоге была зафиксирована средняя точность классификации на уровне 92%, а F1 мера на контрольной выборке составила порядка 0,95. Результаты сильно зависят от используемых словарей адресов и ориентиров, поскольку многие адреса на большом числе сайтов используют валидацию адресов и семантическую разметку страницы. Для исключения таких упрощённых вариантов было решено взять большую часть информации с сайтов и форумов, предоставляющих обычный неструктурированный текст, а также проанализировать объявления в социальных сетях. Также, на результаты влияют географические и языковые особенности региона и структура аудитории веб-ресурса.

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

IX. ВЫВОДЫ

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

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

Библиография

[1] Хорошевский В. Ф. Пространства знаний в сети Интернет и Semantic Web (Часть 1) // Искусственный интеллект и принятие решений. - 2008. - №1. - С. 80-97.

[2] Долгих Е. И., Антонов Е. В., Ерлич В. А. Умные города: перспективы развития в России // Урбанистика и рынок недвижимости. - 2015. - № 1. - С. 50-61.

[3] Hollands, R. G. Will the real smart city please stand up? Intelligent, progressive or entrepreneurial? // City. - 2008. - .№12(3). - P. 303320.

[4] Schmidt, Sebastian, et al. Extraction of address data from unstructured text using free knowledge resources. - Proceedings of the 13 th International Conference on Knowledge Management and Knowledge Technologies. - ACM. - 2013. - Article №7. URL: http://dl.acm.org/citation.cfm?doid=2494188.2494193 (дата обращения: 19.10.2017).

[5] Алексеев С. С., Морозов В. В., Симаков К. В. Методы машинного обучения в задачах извлечения информации из текстов по эталону // Труды 11й Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции». - 2009. - С. 237-246. - URL: http://rcdl.ru/doc/2009/237_246_Section07-1.pdf (дата обращения 19.10.2017).

[6] Chang, Chia-Hui, Chia-Yi Huang and Yueng-Sheng Su. On Chinese Postal Address and Associated Information Extraction // The 26th Annual Conference of the Japanese Society for Artificial Intelligence. - 2012. - Pp. 1-7. - URL: https://www.researchgate.net/publication/267422107_0n_Chinese_ Postal_Address_and_Associated_Information_Extraction (дата обращения 19.10.2017).

[7] Nesi, Paolo, Gianni Pantaleo, and Marco Tenti. Geographical localization of web domains and organization addresses recognition by employing natural language processing, Pattern Matching and clustering // Engineering Applications of Artificial Intelligence 51. -

2016. - Рр. 202-211. - URL: http://dl.acm.org/citation.cfm?id=2910172 (дата обращения 19.10.2017).

[8] Распоряжение Правительства РФ от 28.07.2017 N 1632-р Об утверждении программы "Цифровая экономика Российской Федерации". - URL: http://static.government.ru/media/files/9gFM4FHj4PsB79I5v7yLVu Pgu4bvR7M0.pdf (дата обращения: 19.10.2017).

[9] Добрынин А. П, Черных К. Ю., Куприяновский В. П., Куприяновский П. В., Синягов С. А. Цифровая экономика -различные пути к эффективному применению технологий (BIM, PLM, CAD, IOT, Smart City, BIG DATA и другие) // International Journal of Open Information Technologies. - 2016. - №1. - URL: http://cyberleninka.ru/article/n/tsifrovaya-ekonomika-razlichnye-puti-k-effektivnomu-primeneniyu-tehnologiy-bim-plm-cad-iot-smart-city-big-data-i-drugie (дата обращения: 19.10.2017).

[10] Zheyuan Yu. High accuracy postal address extraction from web pages // Masters Abstracts International. - 2007. - Vol. 45. - No. 05.

[11] Asadi S., Yang G., Zhou X., Shi Y., Zhai B., Jiang W. Pattern-Based Extraction of Addresses from Web Page Content // APWeb. -2008. - Pp. 407-418. - URL: https://link.springer.com/chapter/10.1007/978-3-540-78849-2_41 (дата обращения 19.10.2017).

[12] Pasternack J. and Roth D. Extracting Article Text from The Web With Maximum Subsequence Segmentation // WWW. - 2009. - Pp. 971-980. - URL:

[14]

[15]

http://www.academia.edu/2661588/Extracting_article_text_from_th e_web_with_maximum_subsequence_segmentation (дата

обращения 19.10.2017).

B. Loos and C. Biemann. Supporting Web-based Address Extraction with Unsupervised Tagging. In C. Preisach, H. Burkhardt, L. Schmidt-Thieme, and R. Decker // Data Analysis, Machine Learning and Applications, Studies in Classification, Data Analysis, and Knowledge Organization. - 2008. - Pp. 577-584. S. Asadi, G. Yang, X. Zhou, Y. Shi, B. Zhai, and W.-R. Jiang. Pattern-Based Extraction of Addresses from Web Page Content. In Y. Zhang, G. Yu, E. Bertino, and G. Xu // Progress in WWW Research and Development. - 2008. - Vol. 4976 of Lecture Notes in Computer Science. - Pp. 407-418.

D. Ahlers and S. Boll. Retrieving Address-based Locations from the Web // Proceedings of the 2nd international workshop on Geographic information retrieval, ACM . - 2008. - Pp. 27-34.

[16] Schmidt, S., Manschitz, S., Rensing, C., and Steinmetz, R. Extraction of address data from unstructured text using free knowledge resources // Proceedings of the 13th International Conference on Knowledge Management and Knowledge Technologies. - P. 7.

[17] W. Cai, S. Wang, and Q. Jiang. Address extraction: Extraction of location-based information from the web // Web Technologies Research and Development. - 2005. - Vol. 3399 of Lecture Notes in Computer Science. - Pp. 925-937.

[18] Chang, Chia-Hui, Chia-Yi Huang, and Yueng-Sheng Su. On chinese postal address and associated information extraction. // The 26th Annual Conference of the Japanese Society for Artificial Intelligence. - 2012.

Method of Automated Address Data Extraction

from Unstructured Text

A.A. Menshchikov, A.V. Komarova, A.V. Polev, Y.A. Gatchin

Abstract - This article presents a method of automated address data extraction from unstructured text on the Internet. The authors focus on the issue of extracting information from the text containing postal addresses and geographical landmarks. The emphasis is on two main techniques: template analysis and statistical analysis with the use of machine learning. The paper describes the advantages of using automated search technologies for Smart Cities and for open data initiatives that are becoming very popular today. In addition, the authors developed software for collecting and retrieving information from the text. The method can be used as a basis for information analysis system on real estate web resources, as well as in semantic web resources and knowledge management systems building.

Key words: Text analysis, information search, geoparsing, information gathering, natural language processing, Smart City, data processing.

СИСТЕМНЫЙ АНАЛИЗ, ПОИСК, АНАЛИЗ И ФИЛЬТРАЦИЯ ИНФОРМАЦИИ

Менщиков А.А., Комарова А.В., Гатчин Ю.А., Полев А.В.

КАТЕГОРИРОВАНИЯ ТЕМАТИКИ СТРАНИЦ ВЕБ-РЕСУРСА

о

0

-й

и

1 а л Й

РАЗРАБОТКА СИСТЕМЫ АВТОМАТИЧЕСКОГО

£

S <Ц

ш

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

со

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

а

на веб-ресурсе. Новизна исследования заключается в использовании нового подхода к

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

Ключевые слова: парсинг, анализ текста, категоризация веб-сайтов, система классификации, сбор информации, веб-роботы, машинное обучение, обработка информации, краулинг, большие данные

Abstract: This article reviews the problems of automatic processing of web content. Since the speed of obsolescence of information in the global network is very high, the problem of prompt

extraction of the necessary data from the Internet becomes more urgent. The research focuses on the web resources that contain text, unadapted to the automated processing. The subject of the research is a set of software and methods. A particular attention is paid to the categorization of ads placed on specialized websites. The authors also review practical aspects of the development of a universal architecture of information-gathering systems. The following methods were used during this study: analytical review of the main principles of development of systems of automated information gathering and analysis of natural languages. For obtaining practice-oriented methods of synthesis and analysis results were used. A special contribution of the authors of the study is in developing an automated system for collecting, processing and classification of the information contained on the web-site. The novelty of the research is to use a new approach to solve this problem by taking into account the semantics and structure characteristic for specific sites. The

>

main conclusions of the study are the applicability and effectiveness of the classification method for solving this problem.

Keywords: machine learning, web robots, information collection, classification system, web-sites

m

-§

ta X

categorization, text analisis, parsing, data processing, crawling, big data

Введение

о

Веб-краулер (веб-робот или парсер) - это специальная автоматизированная компьютерная программа, которая исследует веб-ресурсы на предмет интересующей ее владельцев информации, собирает данные и анализирует их в соответствии с внутренними правилами [1, 2]. В настоящее время информация в интернете имеет очень высокую скорость устаревания, а новый контент на веб-ресурсах появляется чуть-ли не ежечасно [3]. В современном мире скорость реакции на события имеет первостепенное значение. В таких условиях актуальной является задача своевременного и автоматизированного сбора информации. Однако, зачастую при сборе контента, имеющего неструктурированный формат (например, данные, генерируемые пользователями ресурса), возникает задача адаптивного анализа текста. Одной из важных ее составляющих является автоматизированное категорирование и классифицирование содержимого веб-страницы [4, 5].

Классификация текстов является одной из задач информационного поиска и состоит в отнесении текста (в нашем случае содержимого веб-страницы) к одной из нескольких категорий. Данная классификация может быть автоматической, ручной или полуавтоматической [6]. В контексте данного исследования наибольший интерес представляют автоматические и полуавтоматические методы. Существует множество методов решения задачи классификации, таких, как Naive Bayes, TWCNB, k-nearest-neighbour, Support Vector Machine, N-Gram based classification и др. Данные алгоритмы имеют свои сильные и слабые стороны, различаются по быстродействию и точности классификации [7].

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

Большинство исследовательских работ по тематике классификации и категорирова-нию веб-ресурсов опираются на методы классификации текстов и не учитывают семанти-

384 DOI: 10.7256/2305-6061.2016.4.21438

При цитировании этой статьи сноска на DOI обязательна

ческие особенности присущие веб-страницам [8, 9]. Так, на веб-странице часть текста не имеет отношение к категории основного его содержания (общие навигационные блоки, рекламные блоки, блоки рекомендаций и т.д.). Отсюда встает дополнительная задача учета структуры веб-ресурса при парсинге его содержания, один из подходов к решению которой описан в [8]. В решаемой нами задаче, мы рассматривали категорирование сайтов каталогов и объявлений для классификации конкретного продукта по тематике. Нас интересовало адаптивное извлечение характеристик товара, что невозможно без предварительного определения его типа. Сайты данной категории имеют похожую структуру, что позволяет сфокусировать краулера на тех блоках контента, которые с наибольшей вероятностью содержат релевантные описания содержания страницы. Данный подход широко используется при парсинге тематических сайтов, поскольку помогает избежать проблем характерных для алгоритмов, учитывающих лишь содержательные характеристики [10-12].

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

Описание алгоритма работы системы

о о

и

1 Л Л Й

£ £

£

К <Ц

ta I

О О О

W §

м

£

о

Z

Опорное слово - это лексическая единица на веб-странице, которая имеет значение при формировании категории. В рамках текущего исследования мы рассматривали в качестве таковых слова из полей meta-keywords и meta-description, а также заголовки внутри content полей веб-страницы.

Процесс категорирования мы разделили на несколько этапов в соответствии с функциональным наполнением (Рис. 1.).

Рис. 1. Задачи подсистемы анализа

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

и ь о

л

Ц

<Ц

S3

к

S3 *

<Ц

и

к

S

й 3

а с

о о PQ

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

На этапе обучения происходит выборка рассматриваемых опорных слов из тренировочного набора и обновление векторов классификации для каждого опорного слова.

for keyword in total words:

test keyword = self.db.keywords.find one({'word': keyword}) total = test keyword['total'] + 1 cats = test keyword['categories'] found = False for cat in cats:

if cat['name'] == category name: ^ cat['count'] += 1

found = True 5 break

и

О

W

if not found:

cats.append({'name': category name, 'weight':

cat['weight'] = float(cat['count']) / float(total)

О 0.0, 'count': 1}

О

W

for cat in cats:

Й £

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

о

¡3

match cats = {} is _

<3

for keyword in total words:

test keyword = self.db.keywords.find one

total words = self. get key words(html page)

({'word': keyword})

if test keyword:

cats = test keyword['categories'] м —

for cat in cats:

cat name = catf'name'l ^ _ L J

pq match cats[cat name] += cat['weight']

if len(match cats) > 0:max cat = max(match cats.iteritems(),

key=operator.itemgetter(1))[0]

return {url, max cat} На этапе классификации происходит постраничный парсинг веб-ресурса из рабочей

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

Функциональная схема работы системы

Рис. 2. Общая структура системы парсинга

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

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

Её работа сводится к последовательному ответу на следующие вопросы:

- является ли данная страница страницей с объявлением. Ответ да - продолжить анализ; нет - пропустить;

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

- определить местоположение объекта объявления; определить ключевые параметры. Важным является определения «рамок» параметра, например, адекватной цены;

определить дату публикации. Самые «свежие» данные будут обладать наибольшей ценностью;

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

о о

Л

т

23

Л ■ё

Описание результатов классификации

о о

и

1 Л Л Й

£ £

£

S <Ц

ta I

CD О CD

W §

pq

£ О

z

и h О Л

ц <u

¡3

S

¡3 %

<D

К S

§

Л С

<D О

pq

Разработанная система может работать в двух режимах: обучение и рабочий режим классификации. В обоих случаях, необходимо знать, какую веб-страницу считать объявлением, а какую - лишь набором дополнительных ссылок. В настоящее время, это делается в ручном режиме - для каждого сайта указывается, какого формата ссылка будет считаться объявлением. В будущем этот вопрос будет также решён в общем виде. То есть, нужно просто переходить по всем возможным ссылкам в рамках данного домена и как только была обнаружена «интересующая» страница, необходимо организовать её обработку.

Для обучения за основу был взят региональный веб-сайт с каталогом объявлений и аукционом «24au.ru», так как категории данного сайта достаточно полно охватывают все возможные направления сбора информации, к тому же, они располагаются в определённой иерархии. За 10 часов многопоточным краулером, работающим в 3 потока, было обработано более 149 тысяч страниц, выделено 8115 ключевых слов по 1382 различным категориям.

Далее производилось тестирование обученной системы. Для проверки работы системы, ей на вход подавались реальные объявления с трех подобных веб-сайтов объявлений («irr.ru», «24auto.ru», «avito.ru») и оценивалась корректность классификации. В большинстве случаев, система верно определяла категорию (важно отметить, что не только базовую, а полную иерархию нескольких категорий) в случае с наиболее часто продаваемой электроникой (ноутбуки, смартфоны). В ситуации с автомобилями, базовая категория определялась всегда верно, а далее система часто относила объявление к запчастям, нежели чем к продаже авто.

Для оценки качества автоматической классификации использовалась метрика F1, вычисляемая по формуле

Fi = 2 *

р*г р+г

(1)

г - это отношение R/Q,р - это отношение Я/Ь. В свою очередь, Я - количество правильно отнесенных к категории объявлений, Q - общее количество объявлений, которые должны быть отнесены к данной категории, Ь - общее количество объявлений, отнесенных системой парсинга к данной категории.

В таблице 1 приведены количество собранных объявлений по каждому из рассматриваемых сайтов и результирующая Г1 метрика. Стоит отметить, что на некоторых сайтах мы столкнулись с использованием систем противодействия автоматизированному сбору информации [14], что сказалась как на количестве собранных объявлений, так и на результатах классификации.

Таблица 1. Количественные показатели парсинга

Веб-ресурс Количество страниц F1 метрика

24au.ru 149 тыс. - (обучение)

24auto.ru 168 тыс. 0.82

avito.ru 3 тыс. 0.73

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

Выводы

£

£

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

о

£

Библиография:

£

1. Liu H. and Milios E. (2012), PROBABILISTIC MODELS FOR FOCUSED WEB CRAWLING. Computational Intelligence, 28: 289-328.

2. Менщиков А.А., Гатчин Ю.А. Методы обнаружения автоматизированного сбора информации с веб-ресурсов

о

// Кибернетика и программирование. - 2015. - № 5. - С.136-157. ¡3

<Ц

3. Razniewski Simon, and Werner Nutt. Long-term Optimization of Update Frequencies for Decaying Information // Proceedings of the 18th International Workshop on Web and Databases. ACM. - 2015.

H

4. Pant Gautam, and Padmini Srinivasan Learning to crawl: Comparing classification schemes // ACM Transactions on Information Systems (TOIS) 23.4 (2005): 430-462.

5. Kim Jin Young, et al. Characterizing web content, user interests, and search behavior by reading level and topic // Proceedings of the fifth ACM international conference on Web search and data mining. ACM, 2012.

6. Паутов К. Г., Попов Ф. А. Информационная система анализа и тематической классификации веб-страниц на основе методов машинного обучения // Современные проблемы науки и образования. 2012. №6.

о

7. Aggarwal Charu C., and ChengXiang Zhai. "A survey of text classification algorithms." Mining text data. Springer US, 2012. 163-222.

8. Chen Yu, Wei-Ying Ma, and Hong-Jiang Zhang. "Detecting web page structure for adaptive viewing on small form factor devices." Proceedings of the 12th international conference on World Wide Web. ACM, 2003.

9. Агеев Михаил Сергеевич, Добров Борис Викторович, Лукашевич Наталья Валентиновна Автоматическая рубрикация текстов: методы и проблемы // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. 2008. №4.

0

-й

и

1 а л Й

£

10. Eswaran Dhivya, Paul N. Bennett, and Joseph J. Pfeiffer III. "Modeling Website Topic Cohesion at Scale to Improve Webpage Classification." Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 2015.

11. Martinez-Alvarez Miguel et al. "Document Difficulty Framework for Semi-automatic Text Classification" DAWAK (2013).

12. Tripathi Nandita, Michael Oakes, and Stefan Wermter. "A Scalable Meta-Classifier Combining Search and Classification Techniques for Multi-Level Text Categorization." International Journal of Computational Intelligence and Applications 14.04 (2015).

13. Морфологический анализатор pymorphy [Электронный ресурс]. - Режим доступа: https://pythonhosted.org/ pymorphy/, свободный (дата обращения: 30.09.2016).

14. Менщиков А.А. Методы обнаружения автоматизированного сбора информации с веб-ресурсов // Альманах научных работ молодых ученых Университета ИТМ0-2016. - Т. 3. - С. 230-232.

к

References:

S

1. Liu H. and Milios E. (2012), PROBABILISTIC MODELS FOR FOCUSED WEB CRAWLING. Computational Intelligence, 28: 289-328

О

2. Menshchikov A.A., Gatchin Yu.A. Metody obnaruzheniya avtomatizirovannogo sbora informatsii s veb-resursov // Kibernetika i programmirovanie. - 2015. - № 5. - S.136-157.

3. Razniewski Simon, and Werner Nutt. Long-term Optimization of Update Frequencies for Decaying Information // Proceedings of the 18th International Workshop on Web and Databases. ACM. - 2015.

о

4. Pant Gautam, and Padmini Srinivasan Learning to crawl: Comparing classification schemes // ACM Transactions on Information Systems (TOIS) 23.4 (2005): 430-462.

5. Kim Jin Young, et al. Characterizing web content, user interests, and search behavior by reading level and topic // Proceedings of the fifth ACM international conference on Web search and data mining. ACM, 2012.

H

6. Pautov K. G., Popov F. A. Informatsionnaya sistema analiza i tematicheskoi klassifikatsii veb-stranits na osnove

s