Введение 2
Постановка задачи 4
Обзор литературы 5
Глава 1. Обнаружение сообществ 8
1.1. Обзор предметной области 8
1.2. Система для распределённых вычислений на графах GraphChi 11
1.3. Алгоритм Гирвана-Ньюмана и его реализация на GraphChi 13
1.3.1. Нахождение кратчайших путей и вычисление промежуточности 15
1.4. Вычисление PageRank 21
1.4.1. Определение и краткий обзор существующих подходов 21
1.4.2. Описание выбранного алгоритма и его реализация на GraphChi 24
1.5. Алгоритм распространения меток (Label Propagation Algorithm) 26
1.5.1. Описание метода и его реализация на GraphChi 27
1.6. Обобщение модулярности на ориентированные графы и LinkRank 28
1.7. Тестирование работы алгоритмов 29
Глава 2. Текстовая классификация и тематическое моделирование 32
2.1. Предварительная обработка текстовой информации 32
2.2. Обзор подходов к классификации документов 36
2.2.1 Байесовский классификатор 37
2.2.2. Практическая реализация разделения сообщений на категории 39
2.5. Тематическое моделирование 43
2.5.1. Латентное размещение Дирихле 43
2.5.2. Критерий качества модели 45
2.6. Практическая реализация тематического моделирования 45
Глава 3. Тестирование работы программы 47
3.1. Сбор информации из социальной сети ВКонтакте 47
3.2. Обнаружение сообществ в полученной социальной сети 49
3.3. Текстовая классификация и тематическое моделирование сообщений
пользователей полученной сети 50
Выводы 55
Заключение 57
Приложение 1 58
Список литературы

Купить

За последние десятилетия огромное внимание стало уделяться связям, существующим в нашем обществе, что привело к появлению отдельного направления исследований. Ученые рассматривают социальные отношения в рамках теории сетей, в основе которой лежит математическая теория графов, а также эмпирические исследования в области различных общественных наук (антропологии, социологии, биологии и др.)[1]. Основные термины теории сетей включают в себя понятие узла (отвечает за отдельного участника в пределах сети) и связи (отображает различные отношения между участниками сети: дружеские, рабочие, учебные и другие) [1].
Данное направление исследований в последнее время переживает новый подъем благодаря появлению социальных онлайн-ресурсов таких как социальные сети, форумы и др. На сегодняшний день социальные сети (такие как Facebook, Вконтакте, Instagram, Одноклассники, Twitter и др.) являются одними из самых посещаемых сайтов во всем мире [2]. Доступность большого объёма персональной информации пользователей (интересы, мнения, связи с другими пользователями) открывает большие возможности для эффективного решения исследовательских и бизнес-задач, решение которых раннее было очень кропотливым, трудоёмким, а зачастую невозможным, что делает данное направление исследований актуальным. Исследованиями социальных данных активно занимаются университеты Стэнфорд [3, 4], Карнеги-Меллон, Оксфорд, INRIA, а также компании Facebook, Google, Yahoo!, LinkedIn и многие другие [5].
Под анализом социальных данных понимается их обработка, позволяющая определить организацию исходной сети, обобщая их по определенному критерию, и выявить какие-либо признаки, характеризующие эти данные, такие как: интересы участников, их образ жизни, мнения по каким-либо вопросам и т.д.
Анализ социальных данных позволяет произвести моделирование распространения информации в сети, выявить характерные признаки поведения пользователя, помогает в развитии систем рекомендаций, а также прогнозировании связей. В частном секторе фирмы используют анализ социальных сетей для поддержки такой деятельности, как взаимодействие и анализ клиентов, маркетинг и бизнес-аналитика. Использование анализа социальных сетей государственным сектором включает в себя развитие стратегий участия руководства, использование средств массовой информации и основанное на сообществах решение проблем.
Основными сложностями в работе с социальными данными являются: их большой объем, многообразие, неоднозначное качество получаемой информации (недостоверная информация, спам, ложные аккаунты), которые делают процесс анализа вручную почти невозможным. К примеру, в социальной сети ВКонтакте на сегодняшний день зарегистрировано более 350 миллионов пользователей [6], а база данных социальной сети Facebook содержит более 1 миллиарда пользовательских аккаунтов и более 100 миллиардов связей между ними. Каждый день пользователи добавляют более 200 миллионов фотографий и оставляют более 2 миллиардов комментариев [5]. В связи с этим, возникает потребность в новых решениях, позволяющих осуществлять распределённую обработку данных, а также сделать её более доступной для большего количества исследователей.
Постановка задачи:
Целью данной работы является создание инструментария для сбора и обработки сложно связанных социальных данных, который по данному социальному графу и связанному с ним набору сообщений пользователей позволяет обнаружить сообщества среди участников сети, провести текстовую классификацию, разделив имеющиеся текстовые данные на категории, а также составить тематические модели для полученных категорий.
Процесс достижения поставленной цели можно представить в виде следующего набора задач:
1. Исследование предметной области
• Изучение принципов работы и модели программирования GraphChi
• Изучение существующих алгоритмов обнаружения сообществ, выбор оптимального решения и его обоснование
• Выбор решения для классификации текстов и тематического моделирования на русском языке
2. Реализация выбранных методов:
• Выбор средств для реализации
• Программирование выбранных алгоритмов
3. Тестирование разработанного программного обеспечения
• Сбор данных из социальной сети
• Анализ полученных данных, подведение итогов
Обзор литературы
В связи с растущим интересом исследователей к задачам анализа социальных данных за последние годы было написано немало статей, освещающих разные аспекты данной проблемы. В работе [1] собраны основные термины и основополагающие понятия и утверждения теории социальных сетей.
В первой части данной работы рассмотрена задача обнаружения сообществ в социальных сетях. Рассматриваемые далее алгоритмы были имплементированы с помощью системы для распределенной обработки графов - GraphChi, основные принципы работы который описаны A. Kyrola в работе [7]. В статье [12] авторы сравнивают производительность работы алгоритмов обнаружения сообществ, реализованных на GraphChi и с помощью MapReduce. Первая программа была запущена на обычном персональном компьютере, вторая - на кластере Amazon EC2, и было установлено, что первая показала результаты, превосходящие вторую по производительности в 4-6 раз.
К.В. Воронцов в своей работе [8] описал основные существующие алгоритмы кластеризации. В работах [9, 11] рассмотрены алгоритмы обнаружения сообществ, основанные на удалении ребер с максимальной промежуточностью, которые были включены в разработку инструментария. В работе [13] У. Брандес предлагает алгоритм для эффективного вычисления промежуточности для вершин, который затем модифицирует для вычисления промежуточности многих других видов, в том числе, промежуточности ребер, что и было использовано в данной работе.
Далее была рассмотрена задача вычисления PageRank узлов в графе. В работах [15, 16, 17, 18, 19] рассмотрены различные подходы к решению данной задачи. В работах [15, 17] авторы предлагают алгебраические подходы для вычисления PageRank, которые дают точный результат вычисления, но являются вычислительноёмкими. В работе [18] авторы рассматривают основные алгоритмы, основанные на методе Монте-Карло, которые позволяют аппроксимировать значение PageRank, при этом достигая значительных улучшений в быстродействии в сравнении с алгебраическими подходами. A.D. Sarma, A.R.Molla, G.Pandurangan, E. Upfal предложили алгоритм для распределенного вычисления значения PageRank, основанный на симуляции случайных блужданий, сложность которого составляет logfnf), который был использован при создании данного инструментария.
В статьях [20, 21] описан алгоритм распространения меток для обнаружения сообществ. Авторы отмечают в качестве его преимуществ перед другими алгоритмами - простоту, а также низкую вычислительную сложность. Одной из проблем в реализации функции обнаружения сообществ в рамках данного инструментария было то, что модулярность (основная метрика качества для данной задачи) определена только для неориентированных графов, в то время как многие из социальных отношений являются ориентированными. В работе [22] предложено обобщение модулярности на ориентированные графы, которое было использовано в качестве решения данной проблемы.
Во второй части данной работы рассмотрено создание функционала для текстовой классификации и тематического моделирования сообщений пользователей социальной сети. Ключевые понятия и теория были получены из классической книги Daniel Jurafsky and James H. Martin по компьютерной обработке естественных языков [24]. Для реализации текстовой классификации на языке программирования Python были использованы работы [25, 27]. В первой из них описаны основные принципы работы с библиотеками для обработки естественных языков в Python. Во второй описан принцип работы мультиномиального байесовского классификатора, а так же различных его модификаций. Также источником информации при создании данной функции инструментария послужили работы К. Воронцова [29, 32], в которых подробно описаны наиболее распространенные на данный момент тематические модели, принципы их работы, их достоинства и недостатки.
Купить