1   2

---

СОДЕРЖАНИЕ

 

ВВЕДЕНИЕ.

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ.

1.1. СОЦИАЛЬНЫЕ ГРАФЫ..

1.2. МАШИННОЕ ОБУЧЕНИЕ.

1.3. EMBEDDINGS.

1.4. DATA MINING..

2. ПРАКТИЧЕСКАЯ ЧАСТЬ. 3

2.1. СБОР СЕТЕВЫХ ПРОФИЛЕЙ..

2.2. ВЫЧИСЛЕНИЕ EMBEDDINGS.

2.3. ПОДГОТОВКА ДАННЫХ..

2.4. АНАЛИЗ ДАННЫХ И ОБУЧЕНИЕ RANDOM FOREST.

ЗАКЛЮЧЕНИЕ..

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ.

 

ВВЕДЕНИЕ

 

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

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

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

Особенность существующих решений рассматриваемой задачи [10, 14, 18, 19, 20, 25] заключается в том, что для прогнозирования дохода они используются только характеристики сетевого профиля пользователя. Например: возраст, пол, место жительства, сведения об образовании.

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

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

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

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

Предмет исследования – методы машинного обучения для получения embeddings на основе данных социальных сетей.

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

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

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

В соответствии с целью исследования и выдвинутыми гипотезами, были поставлены следующие задачи:

1. Анализ современного состояния аспектов проблемы исследования.
2. Разработка программного обеспечения для автоматического сбора данных о сетевом профиле и заработной плате пользователей, а также о социальном окружении пользователей в социальных сетях.
3. Анализ перспектив применения методов с использованием данных о социальном окружении пользователей в социальных сетях для прогнозирования заработной платы.
4. Разработка методов решения для задачи прогнозирования зарплаты пользователей.
5. Разработка программных средств для решения задачи прогнозирования зарплаты пользователей.

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

 

1.1. СОЦИАЛЬНЫЕ ГРАФЫ

 

1.1.1. СОЦИАЛЬНАЯ СЕТЬ

 

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

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

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

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

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

1. Приватность данных. Зачастую доступ к данным пользователей разрешён только для зарегистрированных и авторизованных участников сети, что требует поддержки эмуляции пользовательской сессии с помощью специальных учётных записей.
2. Ограничения доступа и блокировки. С целью предотвращения несанкционированного автоматического сбора данных и ограничения нагрузки на инфраструктуру сервиса социальной сети, владельцы сервиса вводят явные или скрытые ограничения на допустимое количество запросов от одного пользовательского аккаунта и/или IP-адреса в единицу времени.
3. Размерность данных обуславливает необходимость в параллельном методе сбора данных, а также в методах получения репрезентативной выборки пользователей социальной сети.
4. Истинность данных. При заполнении своего профиля в социальной сети пользователи зачастую по ошибке или преднамеренно не заполняют некоторые поля либо дают ложную информацию о фактах своей биографии, интересах и предпочтениях. Кроме того, в контентных сетях (Twitter, YouTube) пользовательский профиль часто ограничен набором базовых атрибутов, недостаточным для решения многих задач, предполагающих персонализацию результатов.
5. Обновление и изменение функционала и модели социальной сети, вследствие ее дальнейшего развития.

 

1.1.2. СОЦИАЛЬНЫЙ ГРАФ

 

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

Социальные графы обладают двумя полезными свойствами:

1. В большинстве социальных графов присутствует одна большая компонента связности, которая захватывает большинство вершин. Например, в социальной сети Facebook 99.91% вершин находятся в одной компоненте связности.
2. Социальные графы в среднем имеют малое расстояние между двумя случайными вершинами. Это объясняется теорией шести рукопожатий: любые два человека на Земле разделены в среднем пятью уровнями общих знакомых.

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

Характер взаимоотношений одного социального объекта с другими отображают метрики взаимодействий:

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

Особенности связей отдельных объектов и всего графа в целом отображают метрики связей:

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

Кластеры социального графа, имеющие отличительные друг от друга особенности, отображают метрики сегментаций:

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

 

1.1.3. ГРАФ ИНТЕРЕСОВ

 

Неявный социальный граф – это граф, формируемый на основе социальных связей в исходном социальном графе.

Граф интересов – это неявный социальный граф, состоящий из вершин пользовательских профилей и вершин интересов, соединенных связями.

Связи в графе интересов бывают трех типов:

1. Пользовательский профиль – пользовательский профиль. Пользователи в социальной сети взаимодействуют напрямую.
2. Пользовательский профиль – интерес. То чем интересуется пользователь в социальной сети.
3. Интерес – интерес. В случае схожих или взаимосвязанных интересов.

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

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

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

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

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

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

 

1.1.4. ИДЕНТИФИКАЦИЯ ПОЛЬЗОВАТЕЛЕЙ

 

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

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

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

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

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

 

1.2. МАШИННОЕ ОБУЧЕНИЕ

 

1.2.1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

 

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

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

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

С помощью обучения с учителем решаются следующие задачи:

1. Классификация. В задаче классификации множество ответов, меток класса, конечно. Класс – это множество всех объектов с заданным значением метки.
2. Регрессия. От задачи классификации отличается тем, что множество ответов состоит из действительных чисел или числовых векторов.

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

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

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

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

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

 

1.2.2. ДЕРЕВЬЯ РЕШЕНИЙ

 

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

Дерево состоит из узлов, “ветвей” и “листьев”, как на рисунке 1.2. Узел представляет собой функцию, по значению которой происходит переход в один дочерних узлов. Ветвь – это ребро, содержащее одно из возможных значений функции родительского узла. Лист – это узел, атрибутом которого является, в случае классификации, значение класса. Работа алгоритма начинается из корневого узла.

Рис 1.2 Пример дерева решений

Формально, дерево решений – это функция , где:

1. – корневой узел.
2. – множество узлов.
3. – множество листьев.
4. — функция ветвления.
5. – функция перехода по значению функции ветвления.

Бинарное дерево решений – это дерево решений, в котором .

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

Пусть дана задача классификации объектов по двум признакам  и . На рисунке 1.4 показано разделение пространства объектов линиями, параллельными координатным осям. Каждой области пространства соответствует определенная метка класса: , , , , .

Рис 1.3 Сложное разделение объектов в двумерном пространстве

Рис 1.4 Простое разделение объектов в двумерном пространстве

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

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

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

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

Например, пусть в рамках задачи классификации дано обучающее множество, состоящее из 100 объектов с большим количеством характеристик m, разделенных на 2 класса. 95 объектов относятся к первому классу, 5 ко второму.

Оптимальным решением разбиения на первом шаге будет присвоение любому объекту метки со значением 1. В результате получится дерево, состоящее из одного корневого листа со значением класса 1. На обучающем множестве данное дерево будет работать с точностью 95%.

Пусть дано тестовое множество, состоящее из 100 объектов. Первые 40 объектов относятся к классу 1, а следующие 60 объектов к классу 2. В этом случае точность на тестовом множестве составит всего 40%.

 

1.2.3. БЭГГИНГ

 

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

Рис 1.6 Схема работы бэггинга

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

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

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

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

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

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

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

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

 

1.2.4. RANDOM FOREST

 

Random forest – алгоритм машинного обучения, основанный на беггинге с применением деревьев решений.

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

Псевдокод обучения Random forest для задачи классификации, описанной в разделе 1.5.1, с обучением  деревьев, выглядит следующим образом:

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

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

• Добавить дочерние узлы для текущего узла.

2. Вернуть обученные деревья .

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

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

 

1.3. EMBEDDINGS

 

1.3.1. ГРАФЫ В МАШИННОМ ОБУЧЕНИИ

 

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

Большинство традиционных подходов решения этой проблемы основываются на: вычислении различных статистик (среднее количество ребер у вершины, коэффициенты кластеризации), функциях ядер, определении функций для описания локальных окрестностей вершины [12]. Традиционные подходы имеют ряд ограничений в применении, поскольку они не могут адаптироваться в процессе обучения, а их внедрение является трудоемким и затратным процессом.

За последнее время появилось несколько новых подходов, основанных на прямом кодировании. Идея этих подходов заключается в получении отображения, представляющего вершины или части графа как точки в пространстве векторов с низкой размерностью  – embeddings [17]. Целью является оптимизация отображения с сохранением информации о структуре исходного графа. После оптимизации, полученные представления могут быть использованы в качестве входных данных для последующих задач машинного обучения.

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

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

 

1.3.2. КОДЕР-ДЕКОДЕР

 

Огромное количество исследований по внедрению информации об узлах в модель привело к сложному разнообразию концептуальных идей и подходов. Обобщением для всех них является модель кодер-декодер (см. рис 1.7). Она состоит из двух ключевых функций: кодер – отображающий информацию о вершине или части графа в низкоразмерный вектор, декодер — извлекающий информацию из набора низкоразмерных векторов [13].

 

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

1. Заранее определяемая функция близости двух узлов в графе .
2. Функция кодера .
3. Функция декодера .
4. Заранее определяемая функция погрешности, связанной с кодированием, . Позволяет измерить расхождение между декодированными значениями близости и истинными значениями .

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

 

 

1.3.3. ЦЕПИ МАРКОВА

 

Пусть дан ориентированный граф . Каждая дуга графа  имеет вес .  определяет вероятность перехода из вершины  в  на одном шаге. Сумма вероятностей переходов из вершины  в каждую из вершин, с которыми она связана дугами , равна 1:

Определение 3. Цепь Маркова называется неприводимой, если в ней из любого состояния можно попасть в любое другое.

Замечание 1. Цепь Маркова над графом  является неприводимой, если  – сильно связанный граф.

Определение 4. Вершина v называется периодической, если:

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

Определение 5. Цепь Маркова называется непериодической, если все её состояния непериодические.

Теорема 1. Фундаментальная теорема цепей Маркова. Каждая конечная, неприводимая, непериодическая цепь Маркова имеет стационарное случайное распределение , которое может быть достигнуто из любого начального распределения.

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

 

1.3.4. СЛУЧАЙНОЕ БЛУЖДАНИЕ

 

Пусть  – это не двудольный, неориентированный граф. А матрица  яв

ляется его матрицей смежности и содержит в себе вероятности перехода из одной из вершины  в одну из ее соседних вершин  или 0, если вершины не связаны:

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

Замечание 5. .

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

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

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

 

1.3.5. NODE2VEC

 

Пусть  – это не двудольный, неориентированный граф.

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

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

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

Случайное блуждание второго порядка – это случайное блуждание первого порядка с параметрами  и , в котором , где:

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

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

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

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

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

Nod2Vec – алгоритмический каркас, основанный на случайном блуждании второго порядка и стохастическом градиентном спуске, предназначенный для репрезентативного представления узлов графа [11].

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

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

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

LearnFeatures(G = (V, E, W), r, l, p, q)

pi = PreprocessModifiedWeights(G, p ,q)

G’ = (V, E, pi)

init walks to empty

for all u in V do

for i = 1 to r do

walk = node2vecWalk(G’, u, l)

walks add walk

 f = StochasticGradientDescent(walks)

return f

node2vecWalk(G’ = (V, E, pi), u, l)

init walk to [u]

for i = 1 to l do

curr = walk.last

 v_cur = GetNeighbors(curr, G’)

 s = aliasSample(v_curr, pi)

walk add s

return walk

Где:

1. – исходный граф.
2. – количество случайных блужданий, совершаемых из каждого узла.
3. – длина одного случайного блуждания.
4. walks – совокупность всех выполненных случайных блужданий.
5. f – результат стохастического градиентного спуска, embedding.

 

1.4. DATA MINING

 

1.4.1. ОПРЕДЕЛЕНИЯ И ЗАДАЧИ

 

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

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

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

Задачи подразделяются по типам производимой информации, это наиболее общая классификация задач Data Mining.

 

1.4.2. ОСНОВНЫЕ ЭТАПЫ

 

Процесс Data Mining является своего рода исследованием. Он состоит из определенных этапов (см. рис. 1.12), включающих в себя элементы: сравнения, типизации, классификации, обобщения, абстрагирования, повторения.

В результате исследования выстраивается модель, используемую в процессе принятия решений.

Процесс Data Mining включает следующие этапы:

1. Анализ предметной области.
2. Постановка задачи.
3. Подготовка данных.
4. Построение моделей.
5. Проверка и оценка моделей.
6. Выбор модели.
7. Применение модели.
8. Коррекция и обновление модели.

 

1.4.3. ПРОВЕРКА И ОЦЕНКА МОДЕЛЕЙ

 

Адекватность модели – это соответствие модели моделируемому объекту или процессу. Проверка модели подразумевает проверку ее достоверности или адекватности. Она заключается в определении степени соответствия модели реальности. Адекватность модели проверяется путем тестирования.

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

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

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

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

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

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

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

 

1.4.4. ВЫБОР МОДЕЛИ

 

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

Основные характеристики модели, которые определяют ее выбор, – это точность модели и эффективность работы алгоритма.

 

1.4.5. ПРИМЕНЕНИЕ, КОРРЕКЦИЯ И ОБНОВЛЕНИЕ МОДЕЛИ

 

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

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

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

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

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

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

---

1   2