Главная Коллекция "Otherreferats" Программирование, компьютеры и кибернетика Разработка рекомендательной системы: реализация микросервисов для автоматической обработки и интеллектуального анализа данных

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

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

Рубрика Программирование, компьютеры и кибернетика
Вид дипломная работа
Язык русский
Дата добавления 01.08.2017
Размер файла 2,9 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Страница:

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

Проектирование системы

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

Проектирование архитектуры модуля анализа

В качестве архитектуры для модуля анализа выбрана микросервисная архитектура. Микросервисы - это архитектурный подход, при котором распределенная система состоит из нескольких небольших сервисов, которые являются отдельными приложениями, работающими в собственных процессах [36]. Каждый такой сервис разрабатывается для определенной цели и может коммуницировать с другими с помощью различных легких протоколов по сети (например, HTTP). Распределение функций между микросервисами происходит логически на основе бизнес-потребностей. Каждый сервис должен быть небольшим, так как выполняет только свою задачу. Эти микросервисы развертываются независимо и автоматизированным образом. Так как существует четкое разделение бизнес-логики между сервисами, каждый из них имеет доступ лишь к своим данным (управляет отдельной базой данных) [37].

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

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

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

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

Архитектура разрабатываемой системы представлена на рис.3.1.

Рисунок 3.1 Архитектура модуля анализа данных

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

В данном случае этот метод реализуется с помощью технологии gRPC от Google, одним из применений которой как раз таки является обеспечение связи между микросервисами. gRPC использует Protobuf в качестве инструмента описания типов данных и сериализации [38], отличительной особенностью которого является производительность даже при больших объемах данных. Данная технология поддерживает работу с большим количеством языков программирования, а также работает быстрее чем REST, так как в качестве протокола передачи структурированных данных использует Protobuf. Именно поэтому в качестве метода коммуникации между микросервисами выбрана технология gRPC.

Каждый микросервис управляет своей базой данных: сервис де-дупликации имеет доступ к базе данных Redis для хранения данных по подсчету tf_idf (необходим для сравнения строковых полей) и к базе данных де-дупликации, где хранятся результаты работы алгоритмов по поиску дубликатов; сервисы группировки, поиска ассоциативных правил также имеет свои базы данных, где хранятся результаты их работы и по запросу от клиента они выдают необходимую информацию, основываясь на этих данных. Микросервис для работы с данными имеет доступ лишь к общей базе данных, куда он заносит данные по запросу от клиента, либо забирает по запросу от микросервисов, выступающих в роли клиентов. В общей базе данных хранятся исходные данные клиента, которые тот поместил в систему для анализа. Таким образом, получаются соблюдены основные условия микросервисной архитектуры: каждый сервис выполняет свою задачу, является отдельным узлом, имеет собственное пространство данных.

Для обеспечения взаимодействия данных модулей с клиентами необходим API Gateway сервер, который будет перенаправлять запросы клиентов на необходимые микросервисы. Это позволяет создать единое API к микросервисам. Клиентам нельзя давать возможность знать адреса всех узлов микросервисов, так как это будет мешать масштабируемости. Для реализации этого прокси-сервера выбрана платформа nginx https: //nginx.org/ru/, которая позволяет также балансировать нагрузку между узлами. Прокси-сервер коммуницирует с микросервисами посредством REST API.

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

Проектирование логических компонент системы

Архитектура системы включает несколько видов взаимодействий между узлами. В зависимости от этого, каждый участник (клиент или сервер) имеет те или иные компоненты.

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

RPC подразумевает наличие в компонентах: приложения с бизнес-логикой, стаба, run_time библиотеки (подпрограмм для создания, отправки и получения сообщений RPC) и модуля коммуникаций (транспортировки) (см. рис.3.2).

Алгоритм работы:

1. Клиентское приложение делает запросы вызова локальной процедуры к стабу, содержащей параметры, которые будут переданы на сервер.

2. Стаб клиента сериализует параметры в процессе маршалинга, делает запрос к клиентской run-time библиотеке, которая в свою очередь отправляет запрос к серверу через коммуникационный модуль.

3. Run-time библиотека на сервере принимает запрос и вызывает процедуру стаба. Стаб проводит анмаршалинг и вызывает фактическую процедуру.

4. Стаб сервера отправляет ответ клиенту по аналогичному алгоритму.

Микросервисы для выполнения задач анализа и микросервис для управления данными имеют еще один поток, который отвечает за взаимодействие с базой данных. База данных для каждого микросервиса своя. Микросервис для поиска дубликатов имеет два модуля коммуникаций с базой данных, так как подключается к двум различным СУБД: Redis и MongoDB.

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

Рисунок 3.2 Компоненты микросервисов при взаимодействии с помощью RPC

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

Рисунок 3.3 Компоненты при взаимодействии REST

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

Обмен сообщениями между компонентами для задач группировки, де-дупликации и поиска ассоциативных правил показан на диаграммах последовательности (см. прил. G, H, J).

Проектирование баз данных

Разрабатываемая система должна работать с двумя СУБД: Redis (для хранения расчетов tf_idf строковых полей), MongoDB (содержит базы данных микросервисов).

Хранение данных микросервисов происходит в документно-ориентированной базах данных из-за отсутствия необходимости хранить отношения между сущностями и разработки универсальной схемы (поля и типы в базе данных зависят от данных пользователя). В MongoDB хранение данных осуществляется в виде json, что обеспечивает гибкость хранения данных.

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

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

Документы в этих коллекциях будут иметь поля загружаемых данных (рис.3.4).

Рисунок 3.4 Структура базы данных микросервиса по работе с данными ("Общая БД")

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

Рисунок 3.5 Структура базы данных группировки

База данных ассоциативных правил также имеет набор коллекций с результатами (правилами) и таблицу с параметрами (рис.3.6).

Рисунок 3.6 Структура базы данных ассоциативных правил

Документы правил имеют поля: условие и следствие (списки объектов), достоверность и поддержка правила. Параметры и свойства (часто встречающиеся наборы, минимальная поддержка, минимальная достоверность) каждой результирующей коллекции заносятся в таблицу params_collection.

База данных дубликатов (рис.3.7) имеет следующие коллекции: с исходными данными из БД группировки (intial_collections), с данными для обучения (train_datasets), с получившимися группами дубликатов без корректировки и с корректировкой пользователем (result_collections и results_after_correction), с обобщенными группами дубликатов (где выбран представитель группы) - results_after_uniting. Количество коллекций зависит от количества проведенных операций пользователя (например, можно сформировать сразу несколько обучающих выборок). Помимо этого требуются также коллекции, которые хранят системную информацию. Таблица параметров включает в себя документы с информацией о каждом запущенном процессе де-дупликации (название коллекции исходных данных, название процесса, список полей для сравнения объектов, база данных redis для tf_idf). Хранение информации о процессе необходимо для возобновления работы с ним. Для того, чтобы прикрепить модель (функцию сходства), обучающую выборку, матрицу сходства к определенному процессу, а также модель к матрице сходства, обучающую выборку к модели, необходимы следующие таблицы: datasets, models, matrices. Структуру их документов см. на рис.3.8.

Рисунок 3.7 Структура базы данных дубликатов

Рисунок 3.8 Структура документов БД дубликатов

Следующая база данных для проектирования - redis для хранения расчетов tf_idf меры слов. Idf мера считается достаточно долго (необходимо найти все документы, в которых встречаются слова строки), чтобы каждый раз высчитывать ее заново, поэтому принято решение хранить результаты в базе данных redis.

Redis - это хранилище данных в формате "ключ_значение". Redis хранит базу данных в оперативной памяти, что обеспечивает быстрый доступ к данным. Значения ключей могут иметь такие типы, как строки, списки, множества, хеш_таблицы, упорядоченные множества. Над этими структурами данных в redis можно выполнять атомарные операции (например, вставка в список).

Перечислим данные, которые необходимо хранить в таблице для каждого поля (field): общее количество документов (строк); для каждого слова количество документов, в которых оно встречается; мера idf для каждого слова, для каждого документа список слов с мерами idf, tf, tf_idf. В табл.3.1 приведены ключи и структуры хранимых данных.

Таблица 3.1 Структура базы данных для хранения мер tf-idf

Данные

Ключ

Тип

Пример

Общее количество документов

{field}: docs: count

Строка

20

Количество документов, в которых встречается слово

{field}: tokens: {token}: docs_count

Строка

45

Мера idf для каждого слова

{field}: tokens: {token}: idf

Строка

4

Список слов с мерами idf для документа

{field}: docs: {doc}: idf

Хеш-таблица

{“молоко”: 4, “цельное”: 1}

Список слов с мерами tf для документа

{field}: docs: {doc}: tf

Хеш-таблица

{“молоко”: 0.5, “цельное”: 0.5}

Список слов с мерами tf-idf для документа

{field}: docs: {doc}: tf-idf

Хеш-таблица

{“молоко”: 2, “цельное”: 0.5}

Таким образом, выполнено проектирование баз данных для модуля анализа.

Проектирование API для микросервисов

В данной части работы будут описаны принципы формирования API микросервисов.

Все микросервисы должны предоставлять REST API для доступа к их функциональности. HTTP-запросы к каждому микросервису представлены в приложении K.

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

Реализация модуля анализа объектов

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

Реализация методов коммуникаций

Все микросервисы написаны на языке python3, для реализации REST API используется фреймворк Flask, для организации метода коммуникации с помощью удаленных процедур - gRPC. Каждый запрос из приложения K в каждом микросервисе реализуется по одному принципу. Ниже представленный код является примером написания метода запроса при использовании Flask:

@app. route ('/processes/matrices/<matrix_name>',methods= ["GET"]) def show_matrix (matrix_name):

matrix = Функция обработки запроса () return Response (response=dumps (matrix), status=200, mimetype="application/json")

Для создания метода, обрабатывающего запрос, необходимо указать route ('/processes/matrices/<matrix>'), вид запроса (POST, GET и др.), сформировать и возвратить ответ (Response ()). Тело запроса и ответа представлено в виде json.

В качестве библиотеки для реализации RPC выбран фреймворк gRPC, который позволяет организовать взаимодействие клиентских и серверных приложений, базирующееся на применении протокола HTTP/2. Синхронизация форматов передаваемых сообщений и генерация кода происходит с помощью Protocol Buffers.

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

rpc GetData (stream DataName) returns (stream Object) {},

где DataName и Object - формат сообщений для передачи с определенными полями, например:

message Object {

string object_in_json = 1; }

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

Реализация микросервиса для группировки объектов

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

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

from sklearn. cluster import AffinityPropagation, KMeans

def kmeans (self, n_clusters):

clusterizer = KMeans (n_clusters=n_clusters, n_jobs=-1) return clusterizer. fit_predict (self. x)

Для определения примерного количества кластеров (чтобы избавиться от необходимости выбора вручную) использован метод affinity propagation этой же библиотеки:

def affinity_propagation (self, damping):

clusterizer = AffinityPropagation (damping=damping) return clusterizer. fit_predict (self. x)

На выборке из продуктов питания данное решение показало себя следующим образом: 7000 объектов были сгруппированы примерно в 60 групп по числовым характеристикам (белки, жиры, углеводы и т.д.). Анализ данных групп показал, что действительно в одном классе находятся продукты, схожие по показателям питания. Такая группировка позволила оптимизировать процесс де-дупликации, однако осталась вероятность того, что дубликаты могут попасть в разные кластеры, что может явиться причиной ошибок при поиске дубликатов.

Реализация микросервиса для поиска дубликатов

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

Определение разницы двух объектов

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

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

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

def get_difference (self, obj1, obj2, fields):

sim = {} for f in fields:

if f ["type"] =="string":

sim [f ["name"]] = self. tfidf. similarity_dq (self. token. extract_tokens (obj1 [f ["name"]],needs_stemming=True),

self. token. extract_tokens (obj2 [f ["name"]], needs_stemming=True), f ["name"]) if f ["type"] == "number":

sim [f ["name"]] = abs (obj1 [f ["name"]] - obj2 [f ["name"]]) // модуль разницы return sim

Поиск tf_idf меры требует на вход две строки, разбитые на слова. Для этого написан собственный упрощенный токенизатор, который разделяет предложения на слова, а также осуществляет поиск их основы (стемминг) с помощью фреймфорка snowballstemmer.

Расчет tf_idf для каждого документа (строки) проводится при помощи сохранения результатов в redis (чтобы при поиске разницы объектов на следующих этапах быстро осуществить перевод слов в вектора). База tf_idf мер заполняется при запуске процесса дедупликации (все строковые данные подвергаются подсчету мер и сохраняются под определенным ключом). Ключи для хранения мер отдельных слов (токенов) представляют собой строку этого слова, а для мер документов - перечисленные в строке токены документа. Запись в redis меры tf_idf документа:

self. redis. hset (self. process+": "+f+": docs: "+doc+": tf_idf", token, self. tf_idf (float (tf), idf))

Поиск меры документа:

tokens1 = self. redis. hgetall (self. process+": "+field+": docs: "+key1+": tf_idf")

Поиск косинусной близости:

for t,v_ in tokens1. items ():

v = float (v_) p = v*tokens2 [t] sum_p = sum_p + p sum1 = sum1 + math. pow (v,2) sum2 = sum2 + math. pow (tokens2 [t],2) try:

sim = sum_p/ (math. sqrt (sum1*sum2)) except:

sim = 0 return sim

Получение разницы между объектами протестировано на примере продуктов питания. Полученная разница между некоторыми объектами представлена ниже:

Таблица 4.1 Пример работы поиска разности между объектами

title

energy value

protein

carbs

fat

Пример 1

Продукт 1

Булки из Цельной Пшеницы

2.660

0.087

0.511

0.047

Продукт 2

Хлеб, из цельной пшеницы

2.780

0.084

0.450

0.054

Разница

0.38 (0.62 - близость)

0.120

0.003

0.057

0.007

Пример 2

Продукт 1

снэк, свиная шкурка с ароматом барбекю

5.380

0.579

0.016

0.318

Продукт 2

снэк, свиная шкурка

5.440

0.613

0.000

0.313

Разница

0.23 (0.77 - близость)

0.06

0.034

0.016

0.005

Пример 3

Продукт 1

Тофу, сушено-замороженный (Коядофу

4.800

0.480

0.070

0.300

Продукт 2

Свинина, бекон, приготовленный в микроволновке

5.050

0.390

0.0100

0.370

Разница

1 (0 - близость)

0.250

0.090

0.060

0.070

Модуль разметки

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

Получение пары объектов происходит следующим образом. Сравнение объектов происходит по единственному полю, которое выбирает пользователь. Сначала рандомным образом выбирается кластер, из которого будут взяты объекты. Затем также рандомно, но уже с заданными весами (0.2 для интервала [0,0.5), 0.8 [0.5,1]) выбирается граница вероятности сходства двух объектов sim_bound (вещественное число от 0 до 1), в случае, если сравниваемое поле имеет строковый тип:

c = random. randint (0, number_of_clusters) // выбор кластера

elements = [0, 1] weights = [0.2, 0.8] // веса if choice (elements, p=weights) == 0: // выбор 0 или 1 в зависимости от веса sim_bound = uniform (0,0.4) // выбор вещественного числа от 0 до 0.4 else: sim_bound = uniform (0.5,1) // выбор вещественного числа от 0.5 до 1

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

max_tags = max ([len (tags1), len (tags2)]) if (len (set (tags1) & set (tags2)) / max_tags >= p): return obj1, obj2

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

Понятие вероятности сходства в данном случае субъективно, так как нельзя судить об идентичности объектов лишь по одному полю и с точки зрения количества общих слов в строках. Являются объекты дубликатами или нет определяет пользователь. Так как обучающая выборка должна включать в большем количестве именно объекты-дубликаты, то веса для выбора границы сходства выбраны такие, что в 80% пользователю выдается пара объектов, имеющих вероятность сходства больше 0.5. Объекты для разметки должны предлагаться не однотипные, чтобы обученная модель имела более высокую точность предсказания. Это достигается с помощью сравнения по одному полю, а также рандомного выбора кластера и границы сходства при поиске очередной пары-кандидата.

Пример работы модуля разметки для поиска пары продуктов (сравнение по названию):

{"obj2": {

"title": "хот-дог, с чили",

"fiber": 0,"fat": 0.11,"energy_value": 2.6,"cluster": 28,"protein": 0.1185,"carbohydrates": 0.27

},

"obj1": {

"title": "Хот-Дог с Чили",

"fiber": 0,"fat": 0.118,"energy_value": 2.6,"cluster": 28,"protein": 0.1185,"carbohydrates": 0.27}}

{"obj2":

{"title": "Суши с Овощами, Завернутые в Водоросли",

"fiber": 0.005,"fat": 0.002,"energy_value": 1.17,"cluster": 16,"protein": 0.022,"carbohydrates": 0.25

},

"obj1": {

"title": "Суши",

"fiber": 0.008,"fat": 0.004,"energy_value": 1.43,"cluster": 16,"protein": 0.04,"carbohydrates": 0.299}}

{"obj2":

{"title": "Жаркое из Свинины (Постное)",

"fiber": 0,"fat": 0.09,"energy_value": 2.077,"cluster": 24,"protein": 0.28,"carbohydrates": 0

},

"obj1":

{"title": "Баранья Отбивная (Только Постное Мясо Съедено)",

"fiber": 0,"fat": 0.1,"energy_value": 2.15,"cluster": 24,"protein": 0.28,"carbohydrates": 0}}

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

Создание функции сходства

Функция сходства представляет собой обученную модель gradient boosted decision trees. Для построения такого вида решающих деревьев использован фреймворк XGBoost [27].

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

Обучение модели происходит следующим образом:

model = xgb. train (train, args) model. save_model (self. model_file_name)

Обучающая выборка загружается из базы данных в DataFrame (pandas), а далее превращается в DMatrix (xgboost) и подается на вход функциии train ().

В результате обучения модели на продуктах питания (обучающая выборка из 400 записей при 7000 продуктов всего) ошибка обучения составила 12%, а ошибка тестирования 13%. При определении сходства объектов точность 87% является достаточно высокой. Полученную модель можно визуализировать. На рис.4.1 представлен фргамент построенного дерева решений при обучении модели на продуктах питания. Полное дерево решений содержит шесть уровней, 35 вершин, 34 узла.

Рисунок 4.1 Фрагмент построенного дерева решений

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

def predict (self, object1, object2):

dif = self. pd. get_difference (object1, object2) prediction = self. model. predict (xgb. DMatrix (dif)) return prediction

Результаты прогнозирования для некоторых пар продуктов (приведено название продукта без остальных характеристик) см. в табл.4.2.

Таблица 4.2 Значения функции сходства для некоторых объектов

Продукт 1

Продукт 2

Результат

Мультизерновой Хлеб

Хлеб Зерновой

0.625

Мультизерновой Хлеб

Хлеб из Мультизерна

0.625

Мультизерновой Хлеб

Мультизерновой Хлеб

0.625

Поджаренный Мультизерновой Хлеб

Поджаренный Хлеб Мультизерна

0.625

Пшеничный Хлеб

Хлеб, из овсяной муки, поджаренный

0.582

Хлеб Воронецкий с Подсолнечником

Хлеб Воронецкий с Подсолнечником

0.582

Хлеб Пряный

Поджаренные Обычные Вафли

0.582

Хлеб Пряный

Хлеб Пряный

0.625

Хлеб Гречишный с Медом

Хлеб Бородинский Особый

0.612

Бублики, с изюмом

Пшеничные Булки

0.612

Омлет или Яичница

Пирог с Мясом

0.408

Салат Капрезе

Хлеб Фитнес

0.369

Значения результатов варьируются от 0.369 до 0.625. Данная мера не является вероятностью. Чтобы узнать, какие объекты являются дубликатами, необходимо установить границу. В данном случае дубликатами являются объекты, функция сходства которых принимает значение больше 0.62. Данная граница послужит критерием отбора дубликатов при формировании матрицы сходства.

Формирование матрицы сходства и поиск групп дубликатов

Формирование матрицы сходства происходит для всех кластеров, определенных микросервисом группировки.

Формирование матрицы осуществляется с помощью перебора всех пар кластера и расчета функции сходства для каждой пары. Элементы матрицы записываюnся в DataFrame (pandas). Результатом формирования матриц сходства является словарь, где ключом является номер кластера, а значением матрица (DataFrame). Этот словарь сохраняется в файле с помощью такого инструмента, как pickle [39], который позволяет сериализовать и десериализовать объекты.

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

0:

Урбеч Натуральная Паста из Ядер Фисташек Биопродукты

Паста из Ядер Фисташек Урбеч

Семена, подсолнечника, Семечки, поджаренные без доб. масла, с солью

семена, подсолнечника, Семечки, поджаренные без доб. масла, без соли

1:

Масло кешью, обычное, без доб. соли

Масло кешью, обычное, с доб. Соли

2:

Паста Арахисовая Хрустящая Hy-Top

Паста Арахисовая Мягкая Hy-Top

3:

Орехи, кешью, поджаренные с доб. масла, без доб. соли

Орехи, кешью, поджаренные с доб. масла, с доб. соли

4:

Орехи, микс (смесь), с арахисом, обжаренные без масла, без доб. соли

Орехи, микс (смесь), с арахисом, обжаренные без масла, с доб. соли

5:

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

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

6:

Паста Hy-Top арахисовая хрустящая

7:

Фисташки, обжаренные без доб. масла, без доб. соли

Фисташки, обжаренные без доб. масла, с доб. соли

0:

Геркулес Традиционный Геркулес

Геркулес Геркулес

Геркулес Геркулес

Хлопья Овсяные "Геркулес Традиционный" Геркулес

Хлопья Геркулес Традиционный Геркулес

Овсяные Хлопья с Отрубями Сила Злаков

Овсяные Хлопья с Пшеничными и Ржаными Отрубями Сила Злаков

Овсяная Крупа

Крупа, овсяная

1:

Кашка Минутка с Персиком Кунцево

Кашка Минутка с Черникой Кунцево

2:

Овсяная каша Myllyn Paras с дыней

3:

Каша Овсяная с Малиной Myllyn Paras

Каша Овсяная с Клубникой Myllyn Paras

Овсяная каша Myllyn Paras с клубникой и сахаром

Овсяная каша Myllyn Paras с малиной и сахаром

Овсяная каша Myllyn Paras с черникой и сахаром

4:

Овсяные хлопья 4 Life органические

5:

Овсяные Хлопья Геркулес

Геркулес Овсяные Хлопья Геркулес

Геркулес Овсяные Хлопья Геркулес

Овсяные Хлопья Геркулес Геркулес

Хлопья Овсяные Геркулес Геркулес

Овсяные Хлопья "Геркулес" Геркулес

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

Иерархическая кластеризация выполнена с использованием scipy. cluster. hierarchy:

Z = hierarchy. single (matrix) c = fcluster (Z,bound, criterion='distance')

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

Рисунок 4.2 Диаграмма сформировавшихся кластеров при иерархической кластеризации

Количество групп кластеров будет зависеть от того, где провести линию границы (оранжевая линия на рисунке). При поиске дубликатов в продуктах питания установлена граница, равная 1. Результат также имеет определенные погрешности. На это влияет как функция сходства, ошибка которой составляет 13%, так и установка границы для отбора кластеров. В целом, иерархическая кластеризация показала лучшие результаты, чем k_medoids. Таким образом, иерархическая кластеризация выбрана основным средством для группировки матрицы сходства.

Результаты группировки дубликатов продуктов питания:

0

Свинина, бекон, приготовленный в микроволновке

Бекон (Приготовленный в Микроволновой Печи)

1

Свинина, бекон, жаренная с небольшим количеством жира

Бекон (Жареный)

2

Бекон, свинина, жаренный

Бекон (в Любом Виде)

Копченый или Вяленный Бекон

3

Курица, крылышки, мясо с кожицей, жареные (например, в духовке)

Куриные Крылышки с Кожей (Запеченные)

4

Сыр, моцарелла, из снятого молока, 16%

Сыр Моцарелла (Частично Обезжиренное Молоко)

5

Сыр, проволоне, с пониж. содерж. жира, 18%

Сыр Мюнстер (Обезжиренный)

6

Фарш, свинина, приготовленный

Свиной Фарш (Приготовленный)

7

Сыр, моцарелла, из снятого молока, с низким содерж. влаги, 20%

Сыр Моцарелла (из Частично Обезжиренного Молока)

Сыр Моцарелла

8

Икра

9

Икра Красная

10

Жареное или Запеченное Куриное Крыло (Кожа Съедена)

11

Куриные Бедра

12

Жареные или Запеченные Куриные Бедра

13

Жареные или Запеченные Куриные Бедра (Кожа Съедена)

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

Реализация микросервиса поиска ассоциативных правил

Поиск ассоциатвных правил выполняется с помощью алгоритма Apriori. Для его реализации испоьзована библиотека apyori https: //pypi. python.org/pypi/apyori/1. 1. 1.

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

rules = list (apriori (transactions)),

где transactions представляют массив массивов:

transactions = [

['id1', 'id2'],

['id3', 'id4'],

]

Полученные правила записываются в базу данных. Пример правила:

{

"_id": ObjectId ("591fc8a3c2d4b23316094821"),

"confidence": 1.0,"condition": [

"577e2c61069836fd08b7a645",

"577e2c63069836fd08b7ac49",

"577e2c63069836fd08b7ad15"

],

"seq": [

"577e2c67069836fd08b7b48d"] }

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

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

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

Примеры полученных результатов приведены в табл.4.3.

Таблица 4.3 Анализ ассоциативных правил

Входные объекты

Дополняющие объекты

Курица, отварная

Чечевица, зрелые семена, вареная, с солью

Шпинат, сырой

Томаты, помидоры (грунтовые)

Курица, отварная

Баклажан, отварной, со сливом, с доб. соли

Кус-кус, приготовленный

Курица, отварная

Каша гречневая из крупы ядрица

Капустный салат, по-домашнему (коул слоу)

Макароны, из цельной пшеницы, приготовленные

Курица, отварная

Шпинат, сырой

Горбуша, отварная

Шпинат, сырой

Каша гречневая из крупы ядрица

Масло, льняное

Индейка, отварная

Рис, коричневый, среднезерный, приготовленный

Томаты, помидоры (грунтовые

Масло, льняное |

Огурцы (грунтовые) |

Петрушка, сырая

На этапе реализации разработано четрые микросервиса: группировки, управления данными, де-дупликации и поиска ассоциативных правил; созданы коммуникации между ними посредством gRPC, а также реализованы способы связи с клиентом в виде REST API. Работа системы проверена на данных из области питания.

Заключение

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

Работоспособность системы проверена на примере работы с данными из области формирования рациона питания пользователей. Группировка объектов выполнена с помощью алгоритма кластеризации k_means, который на тестовых примерах показал достаточно точные результаты. Поиск дубликатов выполнен с помощью комбинации таких методов машинного обучения и анализа данных, как tf_idf, cosine similarity, gradient boosted decision trees и иерархической кластеризации. Поиск дубликатов предложено искать в несколько стадий: разметка данных, поиск функции сходства, формирование матрицы сходства, группировка матрицы сходства. Данный алгоритм на примерах показал точность более 80%.

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

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

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

По этой причине разработанный прототип модуля анализа требует следующих доработок:

1) расширение функциональности системы за счет добавления новых методов анализа;

2) разработка вариативных методов для уже существующих методов.

Расширение методов анализа позволит для большего числа случаев подобрать верное решение.

Другими необходимыми действиями для превращения системы в программный продукт являются:

1. Оптимизация решения. Представленные технологии не являются самым лучшим решением для внедрения системы. Представленные методы требуют распределенных вычислений, что обеспечивается, например, такой технологией, как Apache Spark http: //spark. apache.org/.

2. Разработка веб-клиента.

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

Библиографический список

1. Linden G., Smith B., York J. Amazon.com recommendations: itemto-item collaborative filtering // Internet Computing. - 2003 - 7 (1) - P.76-80.

2. Google, Netflix, Pandora: How to build a Recommender Systems // [Электронный ресурс] URL: http://jimi. ithaca.edu/~dturnbull/Papers/Turnbull_RecommenderSystem _DrydenHS_April13. pdf (дата обращения: 13.11.2016).

3. Mythili S., Madhiya E. An Analysis on Clustering Algorithms in Data Mining // International Journal of Computer Science and Mobile Computing. - January 2014 - Val.3 - P.334-340.

4. Kanungo T., Mount D., Netanyahu N. A local search approximation algorithm for k-means clustering // Comput. Geom. - 2004 - 28 (2-3) - P.89_112.

5. Arthur D., Vassilvitskii S. K-means++: The advantages of careful seeding // Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. - 2007 - P.1027_1035.

6. Park H. S., Jun C. H. A simple and fast algorithm for K-medoids clustering // Expert Systems with Applications. - 2009 - 36 (2) - P.3336-3341.

7. Kumar J., Tiwari N., Ramaiya M. A Survey: On Association Rule Mining // International Journal of Engineering Research and Applications (IJERA). - February 2013 - Vol.3, Issue 1 - P. 2065-2069.

8. Abaya S. A. Association Rule Mining based on Apriori Algorithm in Minimizing Candidate Generation // International Journal of Scientific & Engineering Research. - 2012 - Vol.3, Issue 7.

9. Kaur C. Association Rule Mining using Apriori Algorithm: A Survey // International Journal of Advanced Research in Computer Engineering & Technology (IJARCET). - June 2013 - Vol.2 - P. 2081-2084.

10. Elmagarmid A. K., Ipeirotis P. G., Verykios V. S. Duplicate Record Detection: A Survey // IEEE Transaction on Knowledge and Data Engineering. - 2017 - Vol. 19 No.1 - P.1-17.

11. Slomczynski K., Powaіko P., Krauze T. The Large Number of Duplicate Records in International Survey Projects: The Need for Data Quality Control // Cross-National Studies: Interdisciplinary Research and Training Program. - 2015.

12. Maddodi S., Attigeri G. V., Dr. Kaarunakar A. K. Data Deduplication Techniques and Analysis // Third International Conference on Emerging Trends in Engineering and Technology. - 2010 - P.664-668.

13. CvengroЎs P. Universal Recommender System: Master Thesis. - Prague: Charles University in Prague, 2011. - 91 p.

14. Смолин Д.В. Введение в искусственный интеллект: конспект лекций. - М.: ФИЗМАТЛИТ. - 208 с. - ISBN 5-9221-0513-2.

15. Беркинблит М.Б. Нейронные сети. - М.: МИРОС и ВЗМШ РАО, 1993. - 96 с. - ISBN 5_7084-0026-9.

16. Witten I. H., Frank E. Data Mining: Practical Machine Learning Tools and Techniques (Second Edition). - Morgan Kaufmann, 2005. - ISBN 0-12-088407-0.

17. Jurafsky D., Martin J. H. Speech and Language Processing, 2nd edition. - Pearson Prentice Hall, 2008. - ISBN 978-0-13-187321-6.

18. Барсегян А.А., Куприянов М.С., Степаненко В.В. Методы и модели анализа данных: OLAP и Data Mining. - СПб.: БХВ-Петербург, 2004. - 336 с. - ISBN 5-94157-522-Х.

19. Kaufman L., Rousseeuw P. J. Finding Groups in Data: An Introduction to Cluster Analysis (1 ed.). - New York: John Wiley, 1990. - ISBN 0-471-87876-6.

20. K-means // scikit-learn [Электронный ресурс] URL: http://scikit-learn.org/stable/modules/generated/sklearn. cluster. KMeans.html (дата обращения: 13.11.2016).

21. Frey B. J., Dueck D. Clustering by passing messages between data points // Science. - 2007 - 315 (5814) - P.972-976.

22. Affinity Propagation // scikit-learn [Электронный ресурс] URL: http://scikit-learn.org/stable/modules/clustering.html#affinity-propagation (дата обращения: 13.11.2016).

23. Mooi E., Sarstedt M. A Concise Guide to Market Research. - Springer-Verlag Berlin Heidelberg, 2011.

24. Salton G., Fox E. A. and Wu H. Extended Boolean information retrieval // Magazine Communications of the ACM. - 1983 - Vol.26, Issue 11 - P.1022-1036.

25. Manning C. D., Raghavan P., Schьtze H. Introduction to Information Retrieval. - Cambridge University Press, 2008.

26. Friedman J. Greedy Function Approximation: A Gradient Boosting Machine // The Annals of Statistics. - 2001 - Vol.29, No.5 - P.1189-1232.

27. Introduction to Boosted Trees // XGBoost [Электронный ресурс] URL: http://xgboost. readthedocs. io/en/latest/model.html (дата обращения: 13.11.2016).

28. Trevor H., Robert T., Jerome F. The Elements of Statistical Learning (PDF) (2nd ed.). - New York: Springer, 2009. - P.520-528.

29. Hierarchical clustering // SciPy.org [Электронный ресурс] URL: https: // docs. scipy.org/doc/scipy-0.18.1/reference/cluster. hierarchy.html (дата обращения: 13.11.2016).

30. Чубукова И.А. Data Mining: учебное пособие. - Москва: Интуит НОУ, 2016. - 471 с. - ISBN 978-5-9556-0064-2.

31. Apriori - масштабируемый алгоритм поиска ассоциативных правил // BaseGroup Labs [Электронный ресурс] [Режим доступа: https: // basegroup.ru/community/articles/apriori] (дата обращения: 10.10.2016).

32. The MongoDB 3.2 Manual // MongoDB [Электронный ресурс] URL: https: // docs. mongodb.org/manual/ (дата обращения: 20.09.2016).

33. PyMongo 3.2.2 Documentation // MongoDB [Электронный ресурс] URL: https: // api. mongodb.org/python/current/ (дата обращения: 20.09.2016).

34. User's Guide // Flask [Электронный ресурс] URL: http://flask. pocoo.org/ (дата обращения: 01.11.2016).

35. About gRPC // GRPC [Электронный ресурс] URL: http://www.grpc. io/about/ (дата обращения: 01.11.2016).

36. Pattern: Microservice Architecture // microservices. io [Электронный ресурс] URL: http://microservices. io/patterns/microservices.html (дата обращения: 03.04.2017).

37. Balalaie A. Microservices Architecture Enables DevOps: Migration to a Cloud-Native Architecture // IEEE Software. - 2016 - 33 (3) - P.42-52.

38. Protocol Buffers // Google Developers [Электронный ресурс] URL: https: // developers. google.com/protocol-buffers/ (дата обращения: 06.04.2017).

Страница:


Подобные документы

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.

© 2000 — 2023, ООО «Олбест» Все права защищены