Размещено на http://www.allbest.ru/

СОДЕРЖАНИЕ

• Введение
• 1 Аналитический обзор
• 1.1 Постановка задачи разработки интернет-сервиса подбора мероприятий
• 1.2 Анализ доступного API
• 1.2.1 Мероприятия АИС «Единое информационное пространство в сфере культуры»
• 1.2.2 Мероприятия сети «Вконтакте»
• 1.2.3 Сравнение объектов мероприятия «Вконтакте» и АИС ЕИПК
• 1.3 Постановка задачи классификации мероприятий по категории
• 1.4 Обзор некоторых методов машинного обучения для задачи классификации
• 1.4.1 Линейные модели
• 1.4.2 Решающие деревья
• 1.4.3 Байесовский классификатор
• 1.5 Обзор инструментов и готовых реализаций алгоритмов
• 1.5.1 Выбор языка
• 1.5.2 Обзор библиотек для анализа данных и машинного обучения
• 2 Проектирование автоматизированной системы
• 2.1 Проектирование архитектуры
• 2.2 Выбор средств разработки
• 2.3. Проектирование БД
• 2.4 Проектирование процесса поставки и серверного ландшафта
• 3 Реализация серверной части
• 3.1 Общие интерфейсы
• 3.1 Реализация и тестирование адаптера АИС ЕИПСК
• 3.2 Реализация и тестирование адаптера “Вконтакте”
• 3.3 Реализация и тестирование приложения API
• 4 Решение задачи классификация мероприятий по категориям
• 4.1 Выгрузка из базы данных
• 4.2 Подготовка данных для обучения
• 4.1.1 Предварительная подготовка
• 4.1.2 Выделение признаков
• 4.1.3 Анализ признаков
• 4.1.4 Подготовка обучающей и тестовой выборок
• 4.1.4 Векторизация признаков
• 4.2 Обучение линейного классификатора
• 4.3 Обучение решающего дерева
• 4.2 Обучение Байесовского классификатора
• 4.6 Выбор классификатора
• Заключение

Список использованных источников



Введение

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

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

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

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

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

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

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

Использование результатов работы. Результаты работы будут доступны в виде приложения на Android в Google Play, а также открытого API.

автоматизированный мероприятие машинный обучение



1. Аналитический обзор

1.1 Постановка задачи разработки интернет-сервиса подбора мероприятий

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

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

В таблице 1.1 представлена статистика поисковых запросов, похожих на “Куда пойти сегодня”, в Яндекс согласно сервису wordstat.yandex.ru за месяц.

Таблица 1.1 - Статистика поисковых запросов, похожих на “Куда пойти сегодня” за месяц.

Запрос	Количество показов в месяц
куда пойти сегодня	14 655
куда пойти +в москве сегодня	7 287
куда пойти +с ребенком сегодня	2 734
куда пойти сегодня бесплатно	1 431
куда пойти +с ребенком +в москве сегодня	1 363
куда пойти +в москве сегодня бесплатно	1 047
журнал выбор	1 599
казань куда пойти	5 950
куда пойти выходной	20 164
куда пойти завтра	1 507
город дп юа	763
куда пойти ночь	1 366
сайт днепропетровск	7 100
можно пойти	82 719
выходной куда сходить	50 685
куда пойти спб	12 546
афиша москва	250 521

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

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

После анализа рынка приложений были выделены 3 приложения, которые решают поставленную задачу. Анализ преимуществ и недостатков приведён в таблице 1.2.

Таблица 1.2 - анализ популярных сервисов-афиш.

Название	Преимущество	Недостататок
«KudaGo»	Ежедневно пополняемая база событий.	Ограниченный список городов (всего 16)
	Удобный UI.
«Афиша Rambler»	Возможность бронирования билетов на фильмы, концерты	Список мероприятий состоит в основном из фильмов, больше похоже на киноафишу
	Рецензии и отзывы других пользователей
	Простота использования
«Город Зовет»	Большой список городов	Недостаточный набор мероприятий, ограниченный одним источником



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

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

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

1.2 Анализ доступного API

Большое количество мероприятий публикует АИС «Единое информационное пространство в сфере культуры». Также большое количество мероприятий организуется с помощью событий социальной сети «Вконтакте».

Исследуем публичное API обеих систем на предмет возможности использования.



1.2.1 Мероприятия АИС «Единое информационное пространство в сфере культуры»

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

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

АИС ЕИПК реализует концепцию концепцию министерства культуры России. Открытые данные - это информация, размещенная в сети интернет в виде систематизированных данных, организованных в формате, обеспечивающем ее автоматическую обработку без предварительного изменения человеком, в целях неоднократного, свободного и бесплатного использования. [2]

Информацию о событиях в сфере культуры, находящихся в базе данных АИС «ЕИПСК», можно получать в формате JSON.
Для удобства инфопартнёров и представителей различных веб-сервисов и веб-сайтов подготовлено API, позволяющее свободно работать с доступной информацией. JSON выбран в качестве формата экспорта в связи со своей компактностью и высокой степенью распространения его использования для передачи данных в настоящее время. [3]

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

Для получения событий необходимо выполнить GET запрос вида https://all.culture.ru/api/2.2/events?[params], результат возвращается в формате JSON. [params] -- строка с параметрами.

Рассмотрим доступные параметры:

ids: numberArray -- список id событий через запятую (здесь и далее numberArray обозначает строку в формате 1,2,3).

Tags -- список id тегов, возвращаются все события, отмеченные этими тегами.

locales: numberArray -- список id локалей, возвращаются все события по этим локалям.

places: numberArray -- список id мест проведения. Возвращаются все события по этим местам.

subordinations: numberArray -- список id локалей. Возвращаются все события, которые отмечены локалями с рекурсивным (нестрогим) подчинением. Т.е при передаче в параметр id локали РФ, возвращаются все события РФ, и всех районов, регионов, городов, подчиненных этой локали. Если представить локали и их иерархию в виде дерева, то возвращаются события всех листьев этого дерева.

strictSubordinations: numberArray -- нерекурсивное подчинение, возвращаются события, непосредственно подчиненные переданным в параметре локалям. Т.е. только непосредственные потомки вершины РФ.

organizations: numberArray -- список id организаций. Возвращаются события, которые проводят эти организации.

nameQuery: string -- параметр используется для поиска события по имени или его части.

start: integer timestamp -- фильтр по дате начала события.

end: integer timestamp -- фильтр по дате окончания события.

createDateStart -- фильтр по дате создания события (публикации).

createDateEnd -- фильтр по дате снятия события с публикации.

status: {type: 'string', enum: [`accepted', `new', `rejected']} -- статус события. Для получения только подтвержденных событий используйте статус accepted.

offset: {type: 'integer', 'default': 0, minimum: 0} -- смещение для списка.

limit: {type: 'integer', minimum: 1, maximum: 100} -- лимит выборки.
fields: {type: 'string', filter: 'parseFields'} -- поля, которые пользователь желает видеть в ответе.

sort: {type: 'string', filter: 'parseSort', 'default': {_id: -1}} -- сортировка. Сортировать можно по любому параметру.
Поле sort подается в виде sort=createDate, _id. Знак «-» означает по убыванию.

Примеры запросов:

https://all.culture.ru/api/2.2/events?status=accepted&start=1426942292528&organizations=5&limit=6&offset=0 -- запрос вернет все подтвержденные события, которые не заканчиваются до даты 1426942292528, отмеченные организацией с_id = 5, начиная с нулевого и заканчивая 5-м по счету событием.

Для получения списка категорий используется следующий запрос:
https://all.culture.ru/api/2.2/categories[params]

Допустимые параметры:
type, offset, limit, fields, sort -- тип и значения полей те же, что и для events
Здесь важно поле type -- оно определяет тип категории (type=events)

Примеры запросов:
https://all.culture.ru/api/2.2/categories?type=events -- получение списка категорий, связанных с событиями.

API АИС ЕИПСК в текущем виде подходит для использовании в разрабатываемой системе.

1.2.2 Мероприятия сети «Вконтакте»

«Вконтакте» предоставляет открытое API для работы с различными объектами социальной сети, например: фотографии, сообщения, учётные записи пользователей, друзья, сообщества и так далее. Мероприятия в «Вконтакте» реализованы как подвид сообществ. Таким образом, для работы получения мероприятий из «Вконтакте» необходимо использовать метод search для группы объектов groups.

groups.search Осуществляет поиск сообществ по заданной подстроке.

Параметры запроса представлены в таблице 1.3. [4]

Таблица 1.3 - Параметры запроса «Вконтакте» для поиска сообщест

q	текст поискового запроса.  строка, обязательный параметр
type	тип сообщества. Возможные значения: group, page, event.  строка
country_id	идентификатор страны.  положительное число
city_id	идентификатор города. При передаче этого параметра поле country_idигнорируется.  положительное число
future	при передаче значения 1 будут выведены предстоящие события. Учитывается только при передаче в качестве type значения event.  флаг, может принимать значения 1 или 0
market	при передаче значения 1 будут выведены сообщества с включенными товарами.  флаг, может принимать значения 1 или 0
sort	0 -- сортировать по умолчанию (аналогично результатам поиска в полной версии сайта); 1 -- сортировать по скорости роста; 2 -- сортировать по отношению дневной посещаемости к количеству пользователей; 3 -- сортировать по отношению количества лайков к количеству пользователей; 4 -- сортировать по отношению количества комментариев к количеству пользователей; 5 -- сортировать по отношению количества записей в обсуждениях к количеству пользователей. целое число
offset	смещение, необходимое для выборки определённого подмножества результатов поиска. По умолчанию -- 0.  положительное число
count	количество результатов поиска, которое необходимо вернуть. Обратите внимание -- даже при использовании параметра offset для получения информации доступны только первые 1000 результатов.  положительное число, по умолчанию 20, максимальное значение 1000

Метод search возвращает краткое описание сообщества. Для получения подробной информации можно воспользоваться методом groups.getById. Возвращает информацию о заданном сообществе или о нескольких сообществах. Параметры запроса представлены в таблице 1.4.

Таблица 1.4 - Параметры запроса «Вконтакте» для подробного описания сообщества

group_ids	идентификаторы или короткие имена сообществ. Максимальное число идентификаторов -- 500.  список слов, разделенных через запятую
group_id	идентификатор или короткое имя сообщества.  строка
fields	список дополнительных полей, которые необходимо вернуть. Например: city, country, place, description, wiki_page, market, members_count, counters, start_date, finish_date, can_post, can_see_all_posts, activity, status, contacts, links, fixed_post, verified, site, ban_info, cover. Полный список полей доступен на этой странице.  Обратите внимание, для получения некоторых полей требуется право доступа groups. Подробнее см. описание полей объекта group список слов, разделенных через запятую

Комбинация двух вышеописанных методов позволит получить максимальное количество информации по мероприятиям. Для использования API «Вконтакте» необходимо пройти аутентификацию. Получение всех созданных мероприятий также не доступно через API, поскольку обязательным является параметр q, который должен быть не пустым.

При решении задачи аутентификации и заполнения паарметра q API «Вконтакте» пригодно для применения в разрабатываемой системе.

1.2.3 Сравнение объектов мероприятия «Вконтакте» и АИС ЕИПК

В таблице 1.5 приведены значимые для пользователя атрибуты объектов мероприятия из рассмотренных выше автоматизированных систем и произведено сопоставление



Таблица 1.5 - Сопоставление объектов в двух системах

Сообщество «Вконтакте»	Событие АИС ЕИПСК
Имя атрибута	Описание	Имя атрибута	Описание
id	идентификатор сообщества	_id	идентификатор мероприятия
name	название сообщества	name	название события
deactivated	сообщество удалено или заблокировано
type	тип сообщества
photo_200	URL главной фотографии в максимальном размере	image	постер события
age_limits	возрастное ограничение	ageRestriction	возрастное ограничение
city	город, указанный в информации о сообществе	locale	локаль события
contacts	информация из блока контактов публичной страницы
country	страна, указанная в информации о сообществе.	locale	локаль события
description	текст описания сообщества
place	место, указанное в информации о сообществе	places	массив, содержащий места, в которых проходит событие
start_date и finish_date	для встреч содержат время начала и окончания встречи в формате unixtime	Start, end	дата начала проведения и дата окончания мероприятия
		category	категория мероприятия
		createDate	дата создания мероприятия
		isFree	указывает, бесплатное ли мероприятие

Большинство атрибутов мероприятий содержат эквиваленты в обеих системах. Наиболее существенным отличием является наличие категории у события в АИС ЕИПСК.

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

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

Задача классификации -- формализованная задача, в которой имеется множество объектов (ситуаций), разделённых некоторым образом на классы. Задано конечное множество объектов, для которых известно, к каким классам они относятся. Это множество называется выборкой. Классовая принадлежность остальных объектов неизвестна. Требуется построить алгоритм, способный классифицировать (см. ниже) произвольный объект из исходного множества. [6]

1.4 Обзор некоторых методов машинного обучения для задачи классификации

Теория обучения машин (machine learning, машинное обучение) находится на стыке прикладной статистики, численных методов оптимизации, дискретного анализа, и за последние 50 лет оформилась в самостоятельную математическую дисциплину. Методы машинного обучения составляют основу ещё более молодой дисциплины -- интеллектуального анализа данных (data mining).

Классификация -- один из разделов машинного обучения, посвященный решению следующей задачи. Имеется множество объектов (ситуаций), разделённых некоторым образом на классы. Задано конечное множество объектов, для которых известно, к каким классам они относятся. Это множество называется обучающей выборкой. Классовая принадлежность остальных объектов не известна. Требуется построить алгоритм, способный классифицировать произвольный объект из исходного множества. [7]

Рассмотрим некоторые простые модели и методы, применимые для решения задачи классификации.

1.4.1 Линейные модели

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

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

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

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

На рис. 1.1 представлен геометрический смысл линейного классификатора.



Рисунок 1.1 - геометрический смысл линейного классификатора

Один из самых простых линейных классификаторов получается на основе регрессии путём взятия знака от ответа.

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

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

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

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

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

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

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

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

К особенностям линейных моделей относится следующее:

1. Линейные модели быстро учатся. В случае со среднеквадратичной ошибкой для вектора весов даже есть аналитическое решение. Также легко применять для линейных моделей градиентный спуск.

2. Линейные модели могут восстанавливать только простые зависимости из-за ограниченного количества параметров (степеней свободы).

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

4. Линейные модели не отражают особенности процесса принятия решений у людей.

1.4.2 Решающие деревья

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

Рисунок 1.2 - Пример принятия решения с помощью дерева

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

Рассмотренное дерево называется бинарным, поскольку листья имеют по два потомка. Решающее дерево в общем случае может иметь произвольную кратность.

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

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

Существует много различных вариантов критерия остановки:

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

2. Можно также останавливать разбиение, если глубина дерева достигла определенного значения.

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

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

1. сильно переобучается;

2. сильно меняется при небольшом изменении выборки.

1.4.3 Байесовский классификатор

Пусть некоторый объект имеет вектор признаков x. Необходимо определить, к какому классу y относится этот объект. Байесовский классификатор a(x) относит объект к такому классу, вероятность которого при условии, что реализовался данный объект, максимальна.

Непосредственное вычисление P(y|x) заключается в том, что необходимо рассмотреть множество объектов, которые имеют признаковое описание x, и найти долю класса y среди этого множества. Но возможных признаковых описаний огромное количество, а значит вряд ли в обучающей выборке будет достаточное количество объектов для всякого возможного x. Таким образом, не получится вычислять P(y|x) непосредственно и приходится применять теорему Байеса.

Теорема Байеса позволяет переходить к P(x|y), то есть фактически к плотности распределения x при условии класса y (в случае вещественных признаков). Последнюю величину уже можно оценивать по обучающей выборке.

Однако все еще стоит проблема нехватки данных. Пусть, например, обучающая выборка состоит из 100 000 объектов, а пространство признаков имеет размерность 10 000. В этом случае восстановить плотность как функцию от всех признаков достаточно затруднительно.

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

1.5 Обзор инструментов и готовых реализаций алгоритмов

1.5.1 Выбор языка

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

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

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

Исходя из этого, R может быть использован в основном для исследований в научных институтах, при проведении статистических анализов и визуализации данных. С другой стороны, Python используется для упрощения процесса совершенствования программ, обработке данных и т. д. [7]

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

1.5.2 Обзор библиотек для анализа данных и машинного обучения

Pandas - программная библиотека на языке Python для обработки и анализа данных. Работа pandas с данными строится поверх библиотеки NumPy, являющейся инструментом более низкого уровня.pandas предоставляет специальные структуры данных и операции для манипулирования числовыми таблицами и временными рядами.

Основные возможности библиотеки:

1. Объект DataFrame для манипулирования индексированными массивами двумерных данных

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

3. Встроенные средства совмещения данных и способы обработки отсутствующей информации

4. Переформатирование наборов данных, в том числе создание сводных таблиц

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

6. Вставка и удаление столбцов данных

7. Возможности группировки позволяют выполнять трёхэтапные операции типа «разделение, изменение, объединение» (англ. split-apply-combine).

8. Слияние и объединение наборов данных

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

10. Работа с временными рядами: формирование временных периодов и изменение интервалов и т. д.

Библиотека оптимизирована для высокой производительности, наиболее важные части кода написаны на Cython и C. [8]

Scikit-learn - это библиотека машинного обучения для языка программирования Python. Он реализует различные алгоритмы классификации, регрессии и кластеризации, включая векторные машины, случайные леса, градиентного бустинга, k-средства и DBSCAN и предназначен для взаимодействия с численными и научными библиотеками Python NumPy и SciPy.

Scikit-learn в значительной степени написана на Python. Некоторые основные алгоритмы для достижения производительности написанны на Cython. [9]

Кроме алгоритмов обучения реализованы вспомогательные: кросс-валидация, метрики качества, подбор параметров по сетке (grid_search) и другие.

pymorphy2 - морфологический анализатор для русского языка, написанный на языке Python и использующий словари из OpenCorpora. Он работает под Python 2.6, 2.7, 3.2 и 3.3 и распространяется по лицензии MIT.

Морфологический анализ - это определение характеристик слова на основе того, как это слово пишется. При морфологическом анализе не используется информация о соседних словах. [10]

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



2. Проектирование автоматизированной системы

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

2.1 Проектирование архитектуры

На первом этапе необходимо создать максимально простой сервис, имеющий реальную ценность для конечного пользователя, так называемый MVP. Минимально-жизнеспособный продукт (minimal viable product, MVP) в данном случае представляет собой мобильное или web-приложение, способное по некоторым фильтрам (город, время, возраст и категория) подобрать интересные пользователю мероприятия. При этом должен существовать механизм автоматического заполнения базы данных сервиса мероприятиями из внешних источников. Сервис в данном виде не имеет конкурентных преимуществ, но уже может быть использован потребителем.

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

Разрабатываемая система делится на несколько независимых групп функциональности: загрузка данных из внешних систем, предоставление доступа к данным потребителям (Rest API), обработчики имеющихся в БД данных. Каждая группа выделяется в одно или несколько отдельных приложений. Такой подход похож на микросервисную архитектуру. Микросервисная архитектура повышает гибкость и возможность масштабирования системы.

Концептуальная архитектура приведена на рисунке 2.1.



Рисунок 2.1 - Концептуальная архитектура

2.2 Выбор средств разработки

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

Java - сильно типизированный объектно-ориентированный язык программирования, разработанный компанией Sun Microsystems (в последующем приобретённой компанией Oracle). Приложения Java обычно транслируются в специальный байт-код, поэтому они могут работать на любой компьютерной архитектуре, с помощью виртуальной Java-машины.

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

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

Возможности:

1. Внедрение зависимости.

2. Аспектно-ориентированное программирование, включая декларативное управление транзакциями.

3. Создание Spring MVC web-приложений и RESTful web-сервисов.

4. Начальная поддержка JDBC, JPA, JMS. [11]

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

Возможности

1. Создание полноценных Spring приложений.

2. Встроенный Tomcat или Jetty (не требуется установки WAR файлов).

3. Обеспечивает 'начальные' POMs для упрощения Maven конфигурации.

4. Автоматическая конфигурирация Spring, когда это возможно.

5. Обеспечивает такими возможностями, как метрики, мониторинг состояниями и расширенная конфигурация.

Использование SpringBoot накладывает необходимость использовать средство управлением зависимостями. Наиболее популярными являются Gradle, Maven, Ant. Для решения задачи будем использовать Maven.

2.3. Проектирование БД

Для хранения информации о мероприятиях, параметров приложений и других объектов воспользуемся реляционной СУБД. Разрабатываемая система не накладывает высоких требований к производительности базы данных, поэтому можно воспользоваться любой популярной СУБД, например, MySQL.

MySQL -- свободная реляционная система управления базами данных. Разработку и поддержку MySQL осуществляет корпорация Oracle. Продукт распространяется как под GNU General Public License, так и под собственной коммерческой лицензией.

MySQL является решением для малых и средних приложений. Входит в состав серверов WAMP, AppServ, LAMP и в портативные сборки серверов Денвер, XAMPP, VertrigoServ. Обычно MySQL используется в качестве сервера, к которому обращаются локальные или удалённые клиенты, однако в дистрибутив входит библиотека внутреннего сервера, позволяющая включать MySQL в автономные программы.

Необходимы отдельные таблицы для хранения мероприятий, параметров, категорий, связки категорий и мероприятий, пользователей. Таблицы должны быть созданы в отдельной схеме. Доступ к схеме предоставлен с ограничением прав для отдельного пользователя. [13] Схема представлена на рисунке 2.2.

Рисунок 2.2 -- Схема базы данных

2.4 Проектирование процесса поставки и серверного ландшафта

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

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

Для хранения исходного кода используем систему хранения кода Git и репозиторий GitHub.

Оркестровщиком поставки будет являться Jenkins.

Jenkins -- проект для непрерывной интеграции с открытым исходным кодом, написанный на Java. Позволяет автоматизировать часть процесса разработки программного обеспечения, в котором не обязательно участие человека, обеспечивая функции непрерывной интеграции. Работает внутри в сервлет-контейнере, например, Apache Tomcat. Поддерживает инструменты системы управления версиями, включая AccuRev, CVS, Subversion, Git, Mercurial, Perforce, Clearcase и RTC. Может собирать проекты с использованием Apache Ant и Apache Maven, а также выполнять произвольные сценарии оболочки и пакетные файлы Windows. Сборка может быть запущена разными способами, например, по событию фиксации изменений в системе управления версиями, по расписанию, по запросу на определенный URL, после завершения другой сборки в очереди.

GitHub при каждом зафиксированном изменении кода отправляет web-hook в Jenkins. Jenkins при получении web-hook-а запускается соответствующую сборку.

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

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

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

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

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

Динамический DNS -- технология, позволяющая информации на DNS-сервере обновляться в реальном времени и по желанию в автоматическом режиме. Она применяется для назначения постоянного доменного имени устройству (компьютеру, сетевому накопителю) с динамическим IP-адресом. Это может быть IP-адрес, полученный по DHCP или по IPCP в PPP-соединениях, например при удалённом доступе через модем. Другие машины в Интернете могут устанавливать соединение с этой машиной по доменному имени и даже не знать, что IP-адрес изменился.

На рисунке 2.2 представлена схема поставки отдельного приложения.

Рис. 2.2 - Схема поставки приложения



3. Реализация серверной части

3.1 Общие интерфейсы

Для удобства разработки и повышения связности(cohesion) модулей выделим общие интерфейсы, описывающие основные объекты системы.

Мероприятие представлено интерфейсом Event:

public interface Event {

String getName();

String getDescription();

Calendar getStartDate();

Calenda getFinishDate();

String getImageUrl();

String getExtId();

String getSystemId();

int getMembersCount();

List<? extends Category> getCategories();

double getLatitude();

double getLongitude();

}

Категория мероприятия интерфейсом Category:

public interface Category {

String getName();

}

Источник мероприятий EventSource

public interface EventSource<T extends Event> {

Iterable<T> getNew();

}

Конфигурационный параметр Parameter:

public interface Parameter<T> {

T value();

void setValue(T value);

}

3.2 Реализация и тестирование адаптера АИС ЕИПСК

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

Рассмотрим основные сущности приложения.

За представление мероприятия из АИС ЕИПСК отвечает класс CultureEvent:

public class CultureEvent implements Event {

public static final String CULTURE_ID = "CULTURE";

private CultureDto source;

public CultureEvent(CultureDto material) {

this.source = material;

}

@Override

public String getName() {

return source.name;

}

@Override

public String getDescription() {

return Jsoup.parse(source.description).text();

}

@Override

public Calendar getStartDate() {

GregorianCalendar date = new GregorianCalendar();

date.setTimeInMillis(source.start);

return date;

}

@Override

public Calendar getFinishDate() {

GregorianCalendar date = new GregorianCalendar();

date.setTimeInMillis(source.end);

return date;

}

@Override

public String getImageUrl() {

return "https://all.culture.ru/uploads/" + source.image.name;

}

@Override

public String getExtId() {

return String.valueOf(source._id);

}

@Override

public String getSystemId() {

return CULTURE_ID;

}

@Override

public int getMembersCount() {

return source.visitorsCount != null ? source.visitorsCount : 0;

}

@Override

public List<Category> getCategories() {

return Collections.singletonList(new CategoryImpl(source.category.name));

}

}

Функциональность обращения к внешней системе сосредоточена в классе CultureEventSource. Обращение во внешнюю систему:

HttpRequest request = Unirest.get(CULTURE_URL)

.queryString("start", GregorianCalendar.getInstance().getTimeInMillis())

.queryString("limit", count)

.queryString("sort", "-_id")

.queryString("offset", offset);

HttpResponse<CultureResponse> response = request

.asObject(CultureResponse.class);

После оценки успешности статуса происходит попытка преобразования полученной коллекции Data Transfer Objects в коллекцию CultureEvents:

List<CultureDto> events = response.getBody().events;

return events.stream()

.map(CultureEvent::new)

.collect(Collectors.toList());

За запуск по расписанию и сохранение полученных событий отвечает класс EventScheduler с методом load.

@Scheduled(fixedDelay = 10000)

public void load() {

for (Event event : source.getNew()) {

new JpaStoredEvent(new JpaEvent(event), repository).save();

}

}

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

В качестве end-to-end тестирования сравним состояния БД до запуска приложения и спустя минуту.

SELECT count(*) from events WHERE events.events.system_id = 'CULTURE';

Результат:

0

Через минуту секунд выполним тот же запрос:

Результат:

1335

Новые события будут поступать в базу данных по мере обновления во внешней системе.

3.3 Реализация и тестирование адаптера “Вконтакте”

Для использования API “Вконтакте” необходимо выполнить подготовительную работу:

1. Создать приложение в социальной сети и занести параметры аутентифицируемого хоста.

2. Получить код доступа от пользвателя.

3. Получить аутентификационный токен по коду доступа.

4. Создать хранимые процедуры на стороне “Вконтакте”.

Через созданное приложение происходит представление разрабатываемой системы в “Вконтакте”, происходит учёт лимитов запросов и так далее. Процесс создания представлен на рисунке 3.1.



Рисунок 3.1 - Создание приложения “Вконтакте”

Для получение кода доступа пользователя необходимо любому зарегистрированному пользователю пройти по ссылке “https://oauth.vk.com/authorize?client_id=1&display=page&redirect_uri=http://spree.zapto.org/callback&scope=friends&response_type=code&v=5.80“ и разрешить доступ. В результате на url редиректа будет отправлен код доступа.

За обработку запроса на принятие кода доступа отвечает реализованный REST-сервис, реализованный контроллером InitVkAuthController:

@RequestMapping("/init")

public String index(@RequestParam("code") String code) {

authentication.init(code);

return "Success";

}

Происходит передача кода аутентификатору и возвращает код успешного завершения.

Аутентификатор представлен интервейсом VkAuthentication и реализацией VkUserActorAuthentication:

@Override

public void init(String code) {

LOG.info("user initializing with code " + code);

setupNewToken(code);

}

private void setupNewToken(String code) {

UserAuthResponse authResponse = getUserAuthResponse(code);

LOG.info("got authResponse: " + authResponse);

actor = new UserActor(authResponse.getUserId(), authResponse.getAccessToken());

saveParameters(authResponse);

}

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

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

Создадим процедуру getGroups, принимающую строку поиска и отдающую список групп с подробным описанием и дополнительными полями. Текст процедуры:

var searchJson = {"q":Args.text, "future":1, "type":"event",

"city_id":Args.cityId, "sort":1, "offset":0, "count":1000};

var ids = API.groups.search(searchJson).items@.id;

var response = {};

if (ids.length != 0) {

var getByIdJson = {"group_ids": ids, "fields":["description",

"start_date", "finish_date", "place", "members_count"]};

response = API.groups.getById(getByIdJson);

};

return response;

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

var photos = API.photos.get({"owner_id":-Args.ownerId, "album_id":"profile", "count":1, "rev":1});

if (photos.items[0].photo_807 != null) {

return photos.items[0].photo_807;

} else if (photos.items[0].photo_604 != null) {

return photos.items[0].photo_604;

} else {

return photos.items[0].photo_130;

}

Мероприятии из “Вконтакте” представлено классом VkEvent:

public class VkEvent implements Event {

private static final long MILLIS_IN_SECOND = 1000L;

public static final String VK_SYSTEM_ID = "VK";

public static final int DEFAULT_DURATION = 3 * 60 * 60 * 1000;

private GroupFull group;

public VkEvent(GroupFull group) {

this.group = group

@Override

public String getName() {

return group.getName();

}

@Override

public String getDescription() {

return group.getDescription();

}

@Override

public Calendar getStartDate() {

GregorianCalendar calendar = new GregorianCalendar();

calendar.setTimeInMillis(group.getStartDate() != null

? group.getStartDate() * MILLIS_IN_SECOND

: 0);

return calendar;

}

@Override

public Calendar getFinishDate() {

GregorianCalendar calendar = new GregorianCalendar();

calendar.setTimeInMillis(

group.getFinishDate() != null