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

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


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
1) провести обзор основных методов кластеризации социальных сетей
2) классифицировать бизнес-задачи, решаемые с помощью кластеризации социальных сетей
3) найти наиболее эффективные методы кластерного анализа для выделенных видов бизнес-задач
4) проверить классификацию на реальной задаче
Структура данной работы такова: сначала такой метод анализа, как кластеризация будет рассмотрен подробнее, с приведением примеров и оценкой их эффективности, затем будут классифицированы задачи, основанные на выделении кластеров в социальных сетях, будут выведены рекомендации по использованию исследованных алгоритмов применительно к выделенным группам задач, а также, одна из этих рекомендаций будет подтверждена с помощью реально возникшей задачи из бизнеса.
Данная мера является расстоянием между объектами на геометрической плоскости:
Часто, когда необходимо увеличить значение большого расстояния между объектами, используется квадрат Евклидова расстояния.
2) Манхэттэнское расстояние (расстояние городских кварталов)
Величина данного расстояния между двумя точками определяется как сумма модулей разностей их координат:
При применении данной формулы при определении ошибки снижается влияние отдельных выбросов, т.к. они, в отличие от случая применения Евклидова расстояния, не возводятся в квадрат.
Это расстояние равно максимальной разнице между одной из двух пар координат точек:
Пожалуй, самым популярным алгоритмом кластеризации является k-means. Он состоит из следующих шагов:
1) Находится количество кластеров k
2) Случайным образом выбираются k точек, являющихся центрами будущих кластеров
3) Каждая точка присваивается кластеру с ближайшим центром, и находится расстояние от этой точки до центра кластера
4) Для каждого кластера находится новый центр, являющийся «центром масс» точек этого кластера
5) Начиная с п.3 процесс повторяется, пока не будет достигнуто необходимое разбиение. Чаще всего алгоритм останавливается, когда суммарная ошибка в каждом кластере снизилась на незначимую величину
Другим примером алгоритмов квадратичной ошибки является k-medoids. Он полностью повторяет алгоритм k-means с тем отличием, что центр находится не как среднее, а как медоид всех точек.
Также, существует алгоритм FOREL, действующий по принципу, схожему с k-means. Последовательность его действий такова:
1) Выбирается случайный элемент из выборки
2) Выделяем все элементы выборки, находящиеся на расстоянии меньшем, чем R от первоначально выбранного элемента
3) Вычисляется новый центр кластера путем нахождения центра масс
4) Шаги 2 и 3 повторяются, пока центр кластера не сдвинется на незначительную величину
5) Элементы найденного кластера удаляются
6) Алгоритм повторяется до тех пор, пока каждый элемент не будет присвоен какому-либо кластеру
Алгоритмы данного вида относительно просты и универсальны, однако, перед их применением необходимо знать количество кластеров, для чего приходится прибегать к различным алгоритмам, решающим данную проблему.
Иерархические алгоритмы . Следующий вид алгоритмов, иерархические алгоритмы, имеет два подвида: восходящие и нисходящие. Изначально восходящие алгоритмы присваивают каждый элемент отдельному кластеру, таким образом, на первом шаге количество кластеров равно количеству элементов. Затем данные кластеры итеративно объединяются до получения устраивающего разбиения. Менее популярные нисходящие алгоритмы сначала помещают все элементы в один кластер, а затем разбивают его итеративно не части. На выходе получается дерево разбиений.
Но объединение или разъединение кластеров проходит не случайным образом. Очевидно, стоит объединять кластеры, находящиеся ближе друг к другу, чем остальные. Вопрос лишь состоит в том, как определять расстояние между ними. Существует ряд методов, позволяющих находить его, ниже приведены некоторые из них:
При данном методе расстояние между кластерами приравнивается расстоянию между ближайшими их вершинами.
Расстояние между кластерами равно максимальному расстоянию между точками кластеров. Данный метод непригоден при объединении кластеров, имеющих продолговатую форму.
Расстояние между кластерами равно среднему расстояний между всеми парами точек. Различают взвешенный и невзвешенный методы средней связи, в зависимости от размера кластеров, если они сильно отличаются - применяется весовой коэффициент, находящийся из размера кластера.
Этот метод основывается на вычислении расстояния между центрами масс кластеров, также существуют взвешенный и невзвешенный виды этого метода.
Данный метод рассчитывает сумму расстояний между элементами кластера и его центром до и после присоединения к нему другого кластера и объединяет его с тем, который обеспечивает минимальный прирост этой ошибки, чем очень похож на методы квадратичной ошибки.
Алгоритмы иерархической кластеризации позволяют получить разные «уровни» разбиений, что даст возможность выбрать оптимальное разбиение. Однако, велик риск выполнения излишних операций, что может быть критично в условиях ограниченности времени.
1) она должна полностью охватывать виды задач, решаемых с помощью алгоритмов кластеризации
2) необходимо учесть возможный контекст задач
3) данная классификация должна иметь возможность быть разложенной на подгруппы задач
1) Неоднородность имеющихся данных.
Многие компании, получая первоначальный набор данных, которые они прежде не обрабатывали, сталкиваются с проблемой их тщательного анализа. Причем, сложность состоит не только в размере этих данных, но и в определении степени их однородности. Метод анализа, примененный ко всей совокупности полученных данных, может показать в корне неверную информацию.
Чтобы этого избежать, перед анализом данных необходимо понять их структуру. Сделать это можно с помощью кластеризации. Разделив все данные по кластерам, будет легче понять, из каких групп они состоят, чтобы в дальнейшем анализировать каждую из этих групп в отдельности и таким образом увеличить точность принимаемых решений.
В процесс решения данной задачи большое количество кластеров будет вносить лишь излишнюю сложность в дальнейший их анализ, поэтому необходимо выделять небольшое количество кластеров, обычно до 5.
2) Оптимизация процесса дальнейшей обработки данных.
Зачастую, когда компания применяет сложные методы анализа, задействующие большие вычислительные мощности, либо, когда она вынуждена постоянно присваивать новые объекты уже имеющимся кластерам (например, определять сегмент новых клиентов для предложения им релевантных товаров и услуг), не имеет смысла анализировать всю совокупность данных. В таком случае, необходимо сократить их количество, повысив таким образом скорость получения результатов. Это также может быть сделано с помощью кластеризации. После получения набора кластеров, в каждом из них находится наиболее типичный объект, характеризующий весь кластер, и дальнейший анализ проводится уже не со всеми группами объектов, а только лишь с несколькими, наиболее типичными из них. Необходимо также учесть, что в небольших кластерах найденное среднее значение всех параметров их объектов может сильно отличаться от того среднего значения, которое будет получено при увеличении размеров кластеров. В таком случае, придется либо разработать индивидуальный подход к анализу малых кластеров, а также постоянно отслеживать их состав, для точного определения наиболее типичного представителя.
Из-за того, что результаты кластеризации в этом случае будут анализироваться в дальнейшем, нужно добиться максимальной схожести объектов внутри них.
3) Необходимо регулярное подтверждение состава кластеров.
Как уже говорилось в предыдущем пункте, проблема проверки состава имеющихся кластеров всплывает довольно часто. Действительно, компании необходимо понимать, актуально ли существующее разбиение на кластеры. Для этого нужно постоянно анализировать поступающие данные и выделять те элементы, которые нельзя отнести ни к одному из имеющихся кластеров, а также отслеживать частое появление элементов, сильно отличающихся от средних значений присваиваемых им кластеров. При возникновении данной проблемы необходимо сделать акцент на отличии элементов друг от друга, и увеличить вес расстояния между ними.
К сожалению, приведенная выше классификация задач не является полной. Это связано с наличием дополнительных требований к выполнению кластеризации. Каждый алгоритм может быть оценен с помощью следующих параметров: скорость, точность, надежность и интерпретируемость.
С ростом популярности кластеризация стала использоваться повсеместно для решения большого количества задач. Почти все они задают алгоритмам ограничение по времени получения результатов. С дальнейшим развитием и ростом популярности кластерного анализа, эти требования будут становиться только жестче из-за растущей конкуренции между компаниями и увеличивающейся важности таких параметров, как скорость получения информации и принятия решений. Эти параметры напрямую зависят от того, насколько быстро алгоритм кластеризации сможет обработать имеющиеся данные. Скорость работы алгоритма зависит от трех составляющих: мощности ЭВМ, силами которой обрабатывается алгоритм, качества входных данных, а также сложности и избыточности операций, составляющих алгоритм. Величина ресурсов ЭВМ, как правило, может быть увеличена либо количественно, что подразумевает собой дополнительные траты, часто очень большие, либо же качественно, с помощью оптимизации процесса использования этих ресурсов.
Следующий, не менее важный параметр каждого алгоритма - точность. Наряду со скоростью принимаемых решений, также важна и их точность, ведь решение, принятое быстрее других, но с меньшей точностью, способно принести не только меньшие прибыли, но и колоссальные убытки. Этот параметр, так же, как и скорость, зависит от качества данных, а также от сложности и проработанности алгоритма. Под проработанностью в данном случае понимается наличие в алгоритме неочевидных необработанных исключений, которые могут выдать ошибку в результате применения. Как правило, чем алгоритм популярней, тем меньше вероятность того, что он выдаст ошибку. Под качеством же данных понимается не только отсутствие пропусков, несоответствий типов, но и то, насколько легко алгоритму будет определить элементы в кластеры. Для избегания попадания объектов в чужие кластеры, зачастую необходимо провести предварительную обработку данных, в ходе которой упрощать данные, например, выделять ключевые свойства объектов, по которым можно почти однозначно определить их принадлежность кластерам.
Не менее важна и надежность алгоритма. Под надежностью понимается способность алгоритма анализировать пропущенные или зашумленные данные, а также его возможности по работе в условиях нарушения каких-либо предпосылок.
Еще одна характеристика, присущая любому алгоритму - интерпретируемость. Она зависит от того, что получается в результате обработки алгоритма и влияет на необходимость дальнейшей обработки. Возможность отследить промежуточные результаты работы алгоритма становится все более востребованной, для своевременного отслеживания ошибок.
К сожалению, почти невозможно одновременно улучшить все вышеперечисленные параметры, поэтому, в зависимости от ситуации, приходится идти на компромисс и выбирать более быстрые и менее точные алгоритмы в условиях нехватки времени, либо увеличивать точность и интерпретируемость алгоритмов за счет их скорости.
1) Выделенные классы с высокой долей вероятности покрывают все потенциальные бизнес-задачи из-за высокоуровневой группировки целей кластеризации.
2) Учтен контекст задач, а именно - возможные дополнительные требования к алгоритмам, влияющие на их выбор.
3) Вследствие обширности классификации возможно дальнейшее разбиение в зависимости от дополнительных требований к алгоритмам, а также отрасли компании и подразделения, в которых возникают эти задачи.
1) Неоднородность имеющихся данных.
Данная группа задач характерна тем, что о данных известно немногое. Непонятна структура данных, неизвестно, в какие группы объединяются элементы графов, а также, насколько эти данные полны, т.е. какая доля данных в среднем отсутствует у каждого элемента. Особенностью требований к данным задачам также является наличие небольшого количества кластеров, которых будет достаточно для понимания дальнейшей структуры графа и его элементов. Задачи этого класса можно эффективно решать с помощью методов квадратической ошибки. Например, для этого хорошо подойдет алгоритм k-means, доступный к внедрению для широкого класса специалистов по причине своей простоты и доступности на языке Python. Для этого лишь необходимо установить один из пакетов, например, scikit-learn. Если в графе социальной сети нужно выделить центральный узел, лучше всего подойдет k-medoids, т.к. данный алгоритм за центр кластера берет только элементы графа, что сэкономит время на вычисление центрального узла. Кроме того, при наличии вершин в графе, которые не могут быть точно отнесены вышеприведенными алгоритмами к отдельным кластерам, либо для мониторинга склонности клиентов менять свой кластер, лучше всего подойдет c-means. По причине того, что в результате использования данного алгоритма каждая вершина получает вероятность принадлежности к каждому кластеру, можно присвоить эту вершину одному из них, на основании малейшего перевеса в его сторону.
Но так как мы говорим о кластеризации социальных сетей, открыты для рассмотрения методы, основанные на теории графов. Основная выгода их использования для решения рассматриваемого класса задач состоит в отсутствии необходимости задавать количество кластеров, оно будет найдено в процессе работы алгоритма. Хоть это и сильно не изменит количество кластеров, но может повлиять на принятие дальнейших решений. При использовании k-means, для экономии времени будет задано, например, 3 кластера, которые в целом действительно легко выделить на общем графе. Но при дальнейшем увеличении количества вершин в графе, возможно разбиение одного из существующих кластеров на два и более. Использование методов теории графов дает шанс избежать этого и получить более точное количество кластеров при сохранении скорости и точности кластеризации практически на том же уровне. К сожалению, действие каждого алгоритма должно быть предельно понятно исследователю, в чем нельзя быть уверенным при применении теории графов в кластеризации. К тому же, пакеты, необходимые для этого, более специфичны, и могут вызвать проблемы у исследователей, пытающихся их установить.
В результате проведенного анализа стоит резюмировать, что лучшими методами для решения данных задач являются методы, использующие теорию графов, однако, в тех случаях, когда компания не имеет возможности их применить (чаще всего из-за доступности пакетов и нехватки квалифицированных кадров), приходится применять алгоритмы квадратичной ошибки, в ходе применения которых может быть сделана ошибка в выборе числа кластеров, которая потенциально может стать критической.
2) Оптимизация процесса дальнейшей обработки данных.
Алгоритмы, решающие задачи этого типа должны уметь получать несколько разбиений, т.к. исследователю необходимо решить, насколько крупными должны быть кластеры. Лучше всего для этого подойдут алгоритмы иерархической кластеризации. Результатом их применения является дерево разбиений элементов графа, которое позволит просмотреть несколько вариантов расположения кластеров практически без траты времени. Основываясь на опыте некоторых исследователей, лучшим критерием кластеризации является сумма квадратических ошибок, предложенная Уордом. В таком случае, как правило, получается более визуально понятное разбиение. Стоит заметить, что чем точнее необходимо определять кластеры в графе, тем меньшее расстояние между ними должно быть в кластерах, но в тоже время, вырастет риск непопадания каких-либо вершин в кластеры. Этот недостаток может быть несущественен, когда необходимо получить небольшие группы элементов с тесными связями между ними, а все остальные неважны для анализа.
3) Необходимо регулярное подтверждение состава кластеров.
Данные задачи характерны жестким набором кластеров, что открывает возможность использования алгоритмов квадратичной ошибки, главный недостаток которых (определение числа кластеров), в данном случае пропадает, а, следовательно, открывается возможность к их применению.
В результате анализа была получена следующая таблица выбора алгоритмов в зависимости от возникающей задачи:
Первичный анализ структуры социальной сети
Метод минимального покрывающего дерева, метод Гирвана-Ньюмана, k-means,k-medoids, c-means
Это приложение, позволяющее работать почти с 40 языками, включая популярные языки анализа данных, такие как Python, R, Julia и Scala. Оно находится в открытом доступе и позволяет создавать документы и обмениваться ими. Как правило, Jupyter Notebook применяют для анализа данных, машинного обучения и проверки статистических гипотез и т.д. Его особенностью является наличие браузерного вида, не требующего установки на локальный компьютер. Это же свойство, при использовании какой-либо организацией, позволяет централизованно хранить код и результаты его выполнения.
Рис. 3.1. Домашняя страница Jupyter Notebook
Еще одной особенностью Jupyter Notebook является возможность просмотра промежуточных результатов выполнения кода. В отличие от обычных IDE, в Jupyter можно запускать отдельные строчки кода, которые буду мгновенно выполняться, а результаты запоминаться для дальнейшего кода.
Эта среда разработки, как и Jupyter Notebook, находится в открытом доступе. Она позволяет работать со многими языками, например, с PHP, C/C++, Python и т.д.
Основное преимущество работы с Eclipse - возможность установки большого количества расширений, включающих в себя как модули языков, так и расширения, позволяющие работать с базами данных, серверами приложений и т.д.
Последняя IDE, описываемая в данной работе. Данная среда разработки выделяется среди остальных относительно небольшим весом и легкостью использования. Она была разработана специально для использования Python, но также поддерживает C/C++ и Fortran.
Он имеет встроенные возможности визуализации графов, которых достаточно в большинстве случаев.
Рис.3.5. Представление графа в Jupyter Notebook
Это библиотека языка Python, ползволяющая работать с визуализацией графов. Она позволяет работать в том числе с ориентированными и взвешенными графами, с такими их характеристиками, как степени вершин, длины путей и т.д. Данная библиотека позволяет достичь высокой производительности и способна обрабатывать графы с несколькими миллионами вершин и десятками миллионов ребер между ними. Для работы networkX также требуется установленный Graphviz.
Рис.3.6. Визуализация графа с помощью networkX
1) Был проведен обзор литературы, в ходе которого были изучены основные виды алгоритмов кластеризации: алгоритмы квадратичной ошибки, иерархические и графовые алгоритмы. Кроме того, был рассмотрен механизм прореживания графа, позволяющий повысить эффективность кластеризации.
2) Вся группа задач, возникающих в бизнесе, была разбита на следующие группы: проблемы, связанные с неоднородностью данных, задачи оптимизации обработки данных, а также задачи, требующие регулярного подтверждения состава кластеров.
3) Для выделенных классов бизнес-проблем были выработаны рекомендации по выбору оптимальных алгоритмов кластеризации на основе их параметров.
4) Одна из рекомендаций была протестирована на реальной задаче и была таким образом подтверждена.
1) Все задачи разделяются только на большие группы, практически невозможно провести точную классификацию, которая будет работать в 100% случаев.
2) На выбор оптимального алгоритма сильно влияет контекст задачи, включающий в себя возможность использования дополнительного ПО, возможность визуализации результатов анализа, потребность в скорости, точности, надежности, а также интерпретируемости алгоритмов.
3) Методы работы с графами на языке Python находятся на начальном уровне развития и имеют высокий потенциал стать основным способом анализа социальных сетей.
4) Анализ социальных сетей имеет высокий потенциал ввиду ориентации всего мира на коммуникацию и связь между людьми. Кроме того, при дальнейшем развитии алгоритмов, способных качественно анализировать ориентированные и взвешенные связи между вершинами графа, существенно вырастут возможности по принятию компаниями решений исходя из информации о данных связях.
Сущность и понятие кластеризации, ее цель, задачи, алгоритмы; использование искусственных нейронных сетей для кластеризации данных. Сеть Кохонена, самоорганизующиеся нейронные сети: структура, архитектура; моделирование кластеризации данных в MATLAB NNT. дипломная работа [3,1 M], добавлен 21.03.2011
Обзор существующих решений на основе открытых данных. Выбор социальных сетей для извлечения данных. Ограничение геолокации сообщений из социальных сетей. Разработка формата хранения. Визуализация собранных данных методом теплой карты. Архитектура системы. дипломная работа [1,0 M], добавлен 18.11.2017
Изучение понятия социальных сетей. Классификация социальных сетей по тематике и по форме общения их аудитории: общетематические, специализированные, глобальные, мультимедийные, блоги, микроблоги. Facebook - одна из самых популярных социальных сетей. презентация [405,6 K], добавлен 05.06.2013
Алгоритмы кластеризации данных, отбора факторов, построения множественной линейной регрессии, оценки параметров процесса на скользящем постоянном интервале. Решение задач анализа данных на нейронных сетях и результаты моделирования нелинейных функций. контрольная работа [1,5 M], добавлен 11.01.2016
Понятие и общая характеристика социальных сетей, принципы их функционирования, достоинства и недостатки использования. Формирование функциональных требований к информационному пространству научных исследований. Направления исследований социальных сетей. дипломная работа [222,7 K], добавлен 18.07.2014
История развития и классификация социальных сетей. Характеристика наиболее популярных социальных сетей. Сети Рунета: ВКонтакте, Одноклассники, Мой круг, Мой мир (на www.mail.ru), RuSpace. Социальная сеть Facebook как лидер среди социальных сетей. реферат [4,0 M], добавлен 23.06.2012
Анализ методов и средств выявления мнений пользователей социальных сетей. Обзор средств мониторинга и анализа, подбор необходимого программного обеспечения и технических средств. Разработка архитектуры базы данных, реализация программных модулей. дипломная работа [3,7 M], добавлен 19.01.2017
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Кластерный анализ социальных сетей курсовая работа. Программирование, компьютеры и кибернетика.
Реферат по теме Максимизация прибыли посредством оперативно-тактического изменения цен и порядок применения скидок с...
Автореферат На Тему Шлунково-Кишкові Захворювання
Реферат На Тему Казахстан 4 Класс
Реферат по теме Развитие образования в Азии
Форм Государственного Устройства Курсовая Работа
Реферат по теме Донецкий край в древности
Курсовая Работа На Тему Національний Доход: Суть, Виробництво, Розподіл І Використання
Реферат: Мораль и политика возможен ли компромисс
Языки И Образование Эссе
Реферат по теме Ангиома Лимфангиома
Эволюция Казахстана Эссе
Дипломная работа по теме Положительное влияние средств массовой информации на процесс воспитания в подростковом возрасте
Контрольная работа по теме Сущность политической социализации личности
Ведение Пациентов В Орит Реферат
Реферат по теме Іпотека об'єктів незавершеного будівництва
Курсовая работа по теме Анализ хозяйственной деятельности промышленного предприятия ООО 'Рубин'
Гк Рф Курсовая
Реферат по теме Однополосный радиопередатчик
Реферат: Как помочь насекомым. Скачать бесплатно и без регистрации
Фипи Русский Темы Сочинений
Возмещение вреда, причинённого здоровью гражданина - Государство и право дипломная работа
Правовое воспитание. Основные аспекты понимания законности - Государство и право контрольная работа
Биохимия жидкостей полости рта - Биология и естествознание презентация