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

Федеральное агентство связи

Федеральное государственное бюджетное образовательное учреждение высшего образования

«Поволжский государственный университет телекоммуникаций и информатики»

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

Разработка интеллектуальной информационной системы анализа пользователей соцсети

А.С. Кирьянцев

Самара 2017



Содержание

Введение

1. Аналитическая часть

1.1 Содержательное описание объекта исследования

1.2 Перспективы применения ИИС анализа пользователей соцсети

1.3 Обзор алгоритмов кластеризации

1.4 Описание алгоритма SCAN

1.5 Выбор средств проектирования и разработки ИИС

2. Проектная часть

2.1 Разработка архитектуры ИИС

2.2 Функциональное моделирование

2.3 Инфологическое проектирование

2.4 Проектирование базы знаний

3. Экспериментальная часть

3.1 Алгоритм работы прототипа интеллектуальной информационной системы

3.2 Программное обеспечение функционирования ИИС

3.3 Обоснование эффективности проекта

Заключение

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



Введение

Анализ социальных сетей (англ. Social network analysis) представляет собой исследование социальных сетей, рассматривающее социальные отношения в терминах теории сетей. В настоящее время анализ соцсетей стремительно набирает популярность, благодаря появлению онлайн-севисов таких как LiveJournal, Facebook, Twitter и др. С этим связан феномен социализации персональных данных: стали публично доступными биографии, переписка, дневники, фото, видео, аудиоматериалы, заметки о путешествиях и т.д. Таким образом, социальные сети являются уникальным источником данных о личной жизни и интересах реальных людей. Это открывает беспрецедентные возможности для решения исследовательских и бизнес-задач (многие из которых до этого невозможно было решать эффективно из-за не достатка данных), а также создания вспомогательных сервисов и приложений для пользователей социальных сетей. Кроме того, этим обуславливается повышенный интерес к сбору и анализу социальных данных со стороны компаний и исследовательских центров [7].

Актуальность бакалаврской работы состоит в постоянной необходимости поиска и уточнения целевой аудитории и увеличения релевантности рекламных сообщений.

Предмет исследования: способы предположения возможных интересов пользователя на основе анализа его профиля в социальной сети «Вконтакте».

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

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

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

· Дать содержательное описание объекта исследования;

· Ознакомиться с перечнем предоставляемых открытых данных о пользователе;

· Проанализировать алгоритмы кластеризации;

· Разработать архитектуру интеллектуальной информационной системы (ИИС);

· C помощью методологии UML разработать правила для получения дополнительных данных;

· Осуществить инфологическое моделирование базы данных;

· Спроектировать базу знаний;

· Реализовать программный прототип.

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

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

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

Третья глава раскрывает процесс проектирования, разработки ПО, и расчет ТЭО.

В заключении сделаны основные выводы и результаты по проделанной работе.



1. Аналитическая часть

1.1 Содержательное описание объекта исследования

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

Саму теорию анализа социальных сетей придумали Эмиль Дюркгейм и Георг Зиммель, ещё до появления социальных сетей. В их работах речь шла про важность изучения шаблонов отношений людей. Ведь термин социальная сеть появился благодаря социологам в начале XX века и означала комплект сложных отношений между личностями. Основными задачами информационной системы пассивной и активной работы с соц. сетями являются (рис. 1.1): мониторинг и анализ соц. сетей (Для анализа происходящих в социальных сетях процессов), прогнозирование и управление (для перевода соц. сети в требуемое состояние).



Рис. 1.1 - Социальная сеть

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

Исследование предполагает ряд стадий обрабатывания основных сведений. Во-первых, расчет базисных характеристик, что дает возможность ответить на обыкновенные численные вопросы вида «какое количество групп у пользователя ?». Затем обнаружение статистических и структурных закономерностей в данных дает представление природы исследуемой сети. К примеру, виды распределений, к которым принадлежат обсуждения этих либо иных тем. С точки зрения фактических дополнений максимальная заинтересованность предполагает обнаружение своеобразных закономерностей в ограниченных предметных обсуждениях.

Мониторинг нужен уже после идентификации точной модели информационного процесса. Могут применяться статистические модели и модификации динамических действий в графах (распространение эпидемий, каскадное поведение).

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

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

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

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

4) Предметы анализа социальных сетей. Системы смогут сфокусироваться в рассмотрении последующих предметов социальной сети: сети «в полном» (присутствие поддержки определенных агрегированных глобальных характеристик); суб-сетей и сообществ; в отдельности присвоенных пользователей (присутствие поддержки акторориентированных локальных характеристик); информационных уведомлений (присутствие поддержки характеристик упоминания определенных информативных объектов); суждений (присутствие поддержки характеристик тональности информации касательно определенных информативных предметов); наружных конструкций (либо информативных ресурсов сети Сеть интернет). Замечание: информационным объектом способен являться определенная личность, явление, предприятие и т.п.

5) Режимы анализа данных. В системах может отсутствовать возможность анализа данных, или возможность ретроспективного анализа данных или анализа данных в режиме реального времени.

6) Режимы сбора данных. Системы могут осуществлять сбор всего объема данных или осуществлять сбор данных по определенной тематике.

7) Охват источников данных. Системы могут собирать и анализировать данные из многих социальных сетей (Facebook, Вконтакте), блогов (Blogger), микроблогов (Twitter, Instagram), форумов и т.п.

8) Объемы обрабатываемых данных. Системы могут быть рассчитаны на модельные объемы данных или на промышленные объемы данных (BigData).

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

1.2 Перспективы применения ИИС анализа пользователей соцсети

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

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

Анализ социальных сетей имеет свои теоретические корни в работе ранних социологов, таких как Эмиль Дюркгейм, который писал о важности изучения закономерностей отношений, связывающих социальных субъектов. В начале 20 века социологи использовали концепцию «социальных сетей» для обозначения сложных наборов отношений между членами социальных систем во всех масштабах: от межличностного до международного. В 1930-ых Джейкоб Морено и Хелен Дженнингс представили основные аналитические методы. В 1954 году Джон Арундел Барнс начал использовать этот термин систематически, чтобы обозначать шаблоны связей, охватывая концепции, традиционно используемые общественностью, и те, которые используются социологами: ограниченные группы (например, племена, семьи) и социальные категории (например, пол, этническая принадлежность) , Ученые, такие как Рональд Берт, Кэтлин Карли, Марк Грановеттер, Дэвид Кракхардт, Эдвард Лауманн, Анатолий Рапопорт, Барри Уэлман, Дуглас Р. Уайт и Харрисон Уайт расширили использование систематического анализа социальных сетей. Даже при изучении литературы сетевой анализ был применен Анхеером, Герхардсом и Ромо, Воутером Дэ Нойем, и Баргретом Сенекалом. Действительно, анализ социальных сетей нашел применение в различных учебных дисциплинах, а также практические приложения, такие как противодействие отмыванию денег и терроризму.

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

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

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

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

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

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

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

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

Например, если у пользователя не указан город, но при этом состоит в нескольких группах в названии которых стоит слово “Самара”, то можно предположить что городом, в котором живёт пользователь, является Самара.

Также можно сопоставить интересы по названиям групп, например, у пользователя есть несколько групп со словами “велопробег”, “велосипеды”, “велоспрот”, то можно предположить, что данному пользователю интересны велосипеды и все что с ними связанно.

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

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

? пол;

? дата рождения;

? телефон;

? друзья;

? место работы;

? номер школы или школ, в которых обучался пользователь, включая букву класса и года поступления и выпуска;

? университеты, в которых обучался пользователь, включая факультет, год выпуска и поступления;

? семейное положение;

? родственники;

? текущий город, указанный в профиле.

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

Следует указать еще один аспект, связанный со спецификой соцсетей: зачастую пользователь либо не предоставляет о себе информацию, либо предоставляет ложные сведения. Согласно исследованию ВЦИОМ, сообщать о себе недостоверные данные хотя бы однажды приходилось больше половины пользователей этих ресурсов (51%), причем наиболее часто искажается информация об имени и возрасте (по 29%), об увлечениях (22%), о половой принадлежности пользователя, музыкальных художественных пристрастиях (по 18%). Этот факт значительно усложняет задачу анализа интересов пользователей соцсетей.

В 1950 году британский математик Алан Тьюринг опубликовал в журнале «Разум» свою работу «Компьютер и интеллект», в которой он описал тест для проверки программы разведки. Он предложил разместить исследователя и программу в разных комнатах, пока исследователь не определит, кто стоит за стеной - человек или программа, чтобы разумно учитывать поведение программы. Это было одно из первых определений интеллектуальности, Е. А. Тьюринг предложил назвать интеллектуальное поведение программы, которое будет моделировать разумное поведение человека.

С тех пор появилось множество определений интеллектуальных систем (ИС) и искусственного интеллекта (ИИ). Сам термин AI (Искусственный интеллект) был предложен в 1956 году на семинаре в Дартсмутском колледже (США). Ниже приведём некоторые из этих определений.

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

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

Рассмотрим основные направления исследований в области искусственного интеллекта.

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

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

Для ИИС типичны следующие характеристики:

· развитые коммуникативные навыки;

· способность решать сложные, плохо формализуемые задачи;

· способность к самообучению;

· приспособляемость;

Каждая из перечисленных характеристик условно соответствует своему классу ИИС. Различные системы могут иметь один или несколько признаков интеллекта с различной степенью проявления.

Объем проблем, решаемых ИС, включает задачи, которые, как правило, имеют следующие функции:

Они не знают алгоритма решения проблем (такие проблемы будут называться интеллектуальными задачами);

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

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

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

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

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

* отчеты на специальных языках данных, предназначенных для ввода и обработки исходных данных на компьютере;

* базы данных на компьютерных носителях.

На рисунке 1.2 представлена схема бизнес процесса - как будет работать ИИС, остальные подробности реализации данной ИИС будет рассмотрена ниже.

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

- сложность алгоритма;

- дополнительные данные, необходимые для кластеризации;

- может ли после кластеризации вершин остаться одна или несколько вершин, которые не поддаются кластеризации;

- работает ли алгоритм на взвешенных алгоритмах;

- есть ли возможность нахождения пересекающихся кластеров.



Рис. 1.2 - Схема бизнес процесса «Как будет»

1.3 Обзор алгоритмов кластеризации

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

Structural Clustering Algorithm for Networks (SCAN). Данный алгоритм определяет ядра в графе, то есть такие вершины, у которых достаточно много смежных вершин (определяется параметром ), имеющих с ядром много общих соседей (определяется параметром ). На основании этого и выделяются кластеры. Особенностью алгоритма является его умение находить мосты между кластерами и выбросы.

Bigclam. Алгоритм, основан на Cluster Affiliation Model. В этой модели рассматривается матрица F размера , элемент которой имеет смысл силы принадлежности (affiliation strength) i-ой вершины к j-ому сообществу. Устанавливается связь между матрицей F и самим графом, после чего методом максимизации правдоподобия для заданного графа подбирается оптимальная матрица F. Важно, что матрица F позволяет детектировать пересекающиеся кластеры.

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

Для выбора алгоритма были проведены несколько тестов:

1) Тест на модульность - демонстрирует плотность связей между вершинами внутри кластера и разреженность связей между самими кластерами.

2) Тесты F1-score - определяющие точность совпадения предсказанных кластеров с истинными.

Рис. 1.3 - Результат теста на модульность



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

Результаты тестов представлены ниже, на рисунке 1.3 и 1.4:

Рис. 1.4 - Результат теста F1-score

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

- Walktrap не подходит для наших целей из за низкого показателя модульности.

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

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

Учитывая выводы, сделанные выше, для данной ИИС был выбран алгоритм SCAN.



1.4 Описание алгоритма SCAN

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

Сетевая кластеризация (или разбиение графа) является фундаментальным подходом для обнаружения скрытых структур в сетях, которые из-за многих интересных приложений привлекают повышенное внимание в сетях компьютерной науки, физике и биоинформатике. Разработаны различные методы. Эти методы имеют тенденцию группировать сети таким образом, что в каждом кластере существует плотное множество ребер и несколько ребер между кластерами. Алгоритмы на основе модульности и нормированный разрез являются успешными примерами. Однако они не различают роли вершин в сетях. Некоторые вершины являются членами кластеров; Некоторые вершины являются концентраторами, которые соединяют многие кластеры, но не принадлежат ни одному из них, а некоторые вершины являются выбросами, которые имеют только слабые ассоциации с определенным кластером. Ситуация проиллюстрирована в рисунке 1.3. Существующие методы, такие как основанный на модульности алгоритм, разбивают этот пример на два кластера: один состоит из вершин от 0 до 6, а другой состоит из вершин с 7 по 13. Они не изолируют вершину 6, концентратор, членство в котором либо кластер является спорным, или вершина 13, которая имеет только одно соединение с сетью.



Рис. 1.5 - Сеть с двумя кластерами, концентратором и выбросом

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

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

Вернемся к примеру на рисунке X. Рассмотрим вершины 0 и 5, которые соединены ребром. Их окрестности являются множествами вершин {0, 1, 4, 5, 6} и {0, 1, 2, 3, 4, 5} соответственно. Они имеют много соседей и поэтому разумно группируются в одном кластере. Напротив, рассмотрим окрестности вершины 13 и вершины 9. Эти две вершины связаны друг с другом, но имеют только два общих соседа, то есть {9, 13}. Поэтому сомнительно, что они должны быть сгруппированы в один и тот же кластер. Ситуация для вершины 6 немного отличается. У этого есть много соседей, но они редко взаимосвязаны.

Наш метод SCAN идентифицирует два кластера {0, 1, 2, 3, 4, 5} и {7, 8, 9, 10, 11, 12} и изолирует вершину 13 как выброс, а вершину 6 - как концентратор.

SCAN имеет следующие преимущества:

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

- Высокая скорость: время работы в сети с n вершинами и m ребрами равно O (m). Напротив, время работы алгоритма быстрой модульности, самого быстрого существующего алгоритма сетевой кластеризации, составляет O (md log n).

Сетевая кластеризация (или разбиение граф) - это деление графика на набор подграфов, называемых кластерами. Более конкретно, данный параметр G = {V, E}, где граф V является множеством вершин, а E является множеством ребер между вершинами, целью разбиения графа является разбиение G на k непересекающихся подграфов Gi = {Vi, Ei}, в котором Vi ? Vj = Ц для любого i=?j, и . Количество под-графов k, может быть или не может быть известно априори. Проблема поиска хорошей кластеризации сетей изучалась в течение нескольких десятилетий во многих областях, особенно в области информатики и физики. Здесь мы рассмотрим некоторые из наиболее распространенных методов.

Метод минимального-максимального отрезка стремится разбить граф G = {V, E} на два кластера A и B. Принцип кластеризации минимального-максимального сводит к минимуму число связей между A и B и максимизирует число соединения внутри каждого. Вырез определяется числом ребер, которые необходимо удалить, чтобы изолировать вершины в кластере A от тех, которые находятся в кластере B. Алгоритм минимального-максимального отрезка ищет кластеризацию, которая создает два кластера, срез которых минимизирован и при этом максимизирует число оставшихся ребер.

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

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

Оба метода минимального-максимального отрезка и нормализованного отрезка разбивают граф на два кластера. Чтобы разделить граф на k кластеров, нужно принять подход «сверху вниз», разбив граф на два кластера, а затем еще разделить эти кластеры и т. Д., Пока не будут обнаружены k кластеров. Не существует гарантии оптимальности рекурсивной кластеризации. Мера количества кластеров, которая должна быть получена, когда k неизвестна, отсутствует. Нет индикатора для остановки процедуры деления пополам.

1.5 Выбор средств проектирования и разработки ИИС

Средство для проектирования разработки было выбрано - UML, так как данное средство является более гибким и актуальным на данный момент, чем SADT или ARIS.

UML - это язык визуализации. Написание моделей на UML преследует одну элементарную цель - облегчение процесса передачи информации о системе. За любым символом UML стоит строго конкретная семантика, что позволяет избегать погрешностей интерпретации (ответы на вопросы вида «а что имел в виду разработчик Х, когда он описал иерархию классов Y…» и т.п. будут достаточно прозрачны).

Язык UML был выбран ещё потому что обладает следующими преимуществами:

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

UML позволяет описать систему фактически со вcех вероятных точек зрения и разные нюансы поведения системы.

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

UML расширяем, и позволяет вводить собственные текстовые и графические стандарты, что позволяет использовать ??п не только в сфере программной инженерии.

UML стал очень распространён и динамично развивается.

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

· Читаемость

· Повторное использование

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

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

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

Как средства разработки были выбраны:

MongoDB - это система управления базами данных, которая часто противопоставляется MySQL. Данная СУБД не использует реляционных подход и язык SQL для запросов, вместо этого, она использует документо-ориентированный подход и конструкции языка программирования для запросов. Благодаря данному подходу она может хранить большие обьёмы данных и предоставляет оперативный доступ к ним.

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



2. Проектная часть

2.1 Разработка архитектуры ИИС

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

На сервере ИИС находится три программных комплекса:

- Сервер Node.JS, запускающий код бизнес логики и код API (Application Programming Interface) для связи сервера и клиентского браузера через протоколы HTTP 1.0 и Sockets.

- Сервер баз данных SQLite используется для хранения промежуточных данных и результатов анализа профайлов.

- База знаний, содержащая алгоритмы и модели для идентификации интересов.

Рис. 2.1 - Диаграмма размещения в UML

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

2.2 Функциональное моделирование

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

Рис. 2.2 - Диаграмма вариантов использования в UML

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

Краткое описание вариантов использования представлено ниже.

Вариант использования «Просмотр друзей пользователя» позволяет менеджеру получить список друзей пользователя, так же в случае необходимости менеджер может запросить у ИИС анализ интересов друзей.

Вариант использования «Просмотр групп пользователя» позволяет менеджеру получить список групп пользователя, так же в случае необходимости менеджер может запросить у ИИС анализ интересов групп.

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

Вариант использования «Просмотр интересов пользователя» позволяет менеджеру получить анализ интересов пользователя.

Вариант использования «Анализ интересов» позволяет менеджеру получить результат анализа интересов для любой сущности.

Вариант использования «Построение графа друзей» позволяет менеджеру получить граф друзей для определённого пользователя.

Предусловия для некоторых вариантов использования:

Предусловием варианта использования «Просмотр интересов группы» является выполнение вариантов использования «Анализ интересов».

Предусловием варианта использования «Просмотр интересов пользователя» является выполнение вариантов использования «Анализ интересов» и «Построение графа друзей».

Основной поток для варианта «Просмотр интересов пользователя» выглядит следующим образом:

1) Пред началом варианта происходит анализ интересов для данного пользователя.

2) Так же перед началом происходит построения графа друзей.

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

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

Рис. 2.2 - Диаграмма состояний для ИИС

Рассмотрим каждое из состояний подробнее:

- Ввод идентификатора пользователя - на данном этапе пользователь вводит идентификатор пользователя на странице в браузере;

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

- Получение списка друзей - сервер ИИС начинает поиск друзей пользователя;

- Получение интереса друзей - сервер ИИС начинает парсинг интересов друзей с использованием базы знаний;

- Расчет общих интересов - суммирование всех интересов и разбиение пользователей по группам;

- Предположение интересов для друзей - расчет интересов для групп;

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

- Вывод результатов пользователю - отправка результатов расчетов в браузер пользователя с сервера и отображение в браузере результатов расчетов.

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

2.3 Инфологическое проектирование

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

Рассмотрим подробнее каждую сущность и её задачи.

Рис. 2.3 - Диаграмма ER (физический уровень)

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

Данная сущность (рисунок 2.5) хранит id пользователя который пользуется ИИС, его имя, токен, который был выдан при авторизации сервером Вконтакте, e-mail и идентификатор данного пользователя в социальной сети Вконтакте.

Рис. 2.4 - Сущность Error

Рис. 2.5 - Сущность ApplicationUser

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

Рис. 2.6 - Сущность Queue

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

Рис. 2.7 - Сущность WallPost

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



Рис. 2.8 - Сущность User

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

комментариев, репостов, указатель - является ли данная запись рекламой и прикреплена ли она.

Рис. 2.9 - Сущность GroupWallPost

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

Рис. 2.10 - Сущность Group

Сущность Intrest осуществляет хранение интересов, имеет следующие поля для хранения данных: идентификатор интереса, идентификатор

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

Рис. 2.11 - Сущность Intrest

2.4 Проектирование базы знаний

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

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

Два основных типа баз знаний являются человеко-читаемыми и машино-читаемыми.

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

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

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

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

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

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

Некоторые преимущества деревьев решений:

· Просто понять и интерпретировать. Деревья можно визуализировать.

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

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

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

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

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

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

· Хорошо работает, даже если его предположения несколько нарушены истинной моделью, из которой были созданы данные.

Недостатки деревьев решений включают:

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

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

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

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

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

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

Дерево решений для установления города пользователя.

Переменные:

Город - Город указанный в профиле пользователя

ГрупИмя - Имя группы в которой состоит анализируемый пользователь

УниверИмя - Название университета который указан в профиле анализируемого пользователя

ГруппМесто - Место указанное в анализируемой группе.

Условия:

1) ЕСЛИ Город = “” и (ГрупИмя = “*самара*” или ГрупИмя = “*63ру*”), ТО Город = “Самара”

2) ЕСЛИ Город = “” и УниверИмя = “*ПГУТИ*” ТО Город = “Самара”

3) ЕСЛИ Город = “” и (ГрупИмя1 = “*рок над волгой*” и ГрупИмя2 = ”*экспо волга*” , ТО Город = “Самара”

4) ЕСЛИ Город = “” и ГруппМесто = “*Самара*”, ТО Город = “Самара”

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



Рис. 2.12 - Дерево решений для поиска города пользователя

Дерево решений для установления интересов пользователя.

Переменные:

ГрупИмя - Название группы в которой состоит пользователь.

Интер - Предпологаемый интерес пользователя

Условия:

1) ЕСЛИ ГрупИмя = “*суши*”, ТО Интер += “Китайская кухня”

2) ЕСЛИ ГрупИмя = “*велосипеды*” или ГрупИмя = “*scott*” или ГрупИмя = “*велоспорт*”, ТО Интер += “Велосипеды”

3) ЕСЛИ ГрупИмя = “*пицца*” или ГрупИмя = “*pizza*”, ТО Интер += “Пицца”

4) ЕСЛИ ГрупИмя = “*wedding*” или ГрупИмя = “*свадьба*” или ГрупИмя = “*свадебные*”, ТО Интер += “Свадьба”

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

...