Training supervisors

Ministry of Education and Science of Ukraine

Lviv Polytechnic National University

Software Department

Report
about research training related to master’s qualification work

The student of _________________________________

_________________________________

(first name, last name, patronymic)

Training organization___________ __________________________

___________ __________________________

(organization name)

Terms of training: from «» to «»

Training supervisors

University supervisor _______________________________

(signature) (position, Name)

Organization supervisor _______________________________

(signature) (position, Name)

Master’s qualification work _______________________________

(signature)

supervisor _______________________________

(degree, academic status, Name)

Score ______________ Date_ _____________

Lviv – 2015

ЗМІСТ

РОЗДІЛ 1. ЗАГАЛЬНА ІНФОРМАЦІЯ ПРО LSU І ІНСТИТУТ КОМПЮТЕРНИХ НАУК ТА ІНЖЕНЕРІЇ. 3

РОЗДІЛ 2. ДОБУВАННЯ ДАНИХ З СОЦІАЛЬНИХ МЕРЕЖ, ДОСЛІДЖЕННЯ ГРАФІВ ТА ПРОГРАМНИХ ЗАСОБІВ ЇХ АНАЛІЗУ.. 4

2.1. Важливість добування даних з соціальних мереж.. 4

2.2. Як дані соціальних мереж можна представити у вигляді графу. 4

2.3. Міри центральності 5

2.4. SNAP. 6

2.5. NodeXL.. 6

2.6. GraphML.. 7

2.7. Завдання на базі практики. 7

РОЗДІЛ 3. Результати отримані на базі практики. 8

3.1. Демонстраційний додаток. 8

3.2. Проблеми, що виникли. 9

РОЗДІЛ 4. АНАЛІЗ ЗОБРАЖЕННЯ ЗРАЗКУ КРОВІ. 10

4.1. Додаток для аналізу зображення зразку крові 10

4.2. Обрані засоби. 10

4.2. Архітектура ядра. 11

4.3. Алгоритми. 12

ВИСНОВКИ.. 14

СПИСОК ЛІТЕРАТУРИ.. 15

Додаток A. UML діаграма класів ядра. 16

Додаток Б. UML діаграма послідовностей для класифікації 17

Додаток В. Визначення звязних компонент. 18

Додаток Г. Гістограма спільних ознак інтенсивності 19

Додаток Д. Класифікація клітин. 20

РОЗДІЛ 1. ЗАГАЛЬНА ІНФОРМАЦІЯ ПРО LSU І ІНСТИТУТ КОМПЮТЕРНИХ НАУК ТА ІНЖЕНЕРІЇ

Університет штату Луізіана розміщений в місті Батон Руж штату Луізіана, США. Університет є головним вишом у системі університетів Луізіани. [1]

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

Протягом практики я був задіяний в одному з дослідницьких проектів під керівництвом Др. Баумгартнера в LSU. Я отримав доступ до лабораторії, безпровідного аккаунту і репозиторію проекту. Протягом роботи над проектом, всі люди, які були задіяні в різних проектах під керівництвом Др. Баумгарнтера зустрічалися щотижня для того, щоб обговорити проекти. Протягом кожної зустрічі я мав можливість послухати і поцікавитися, що відбувається в інших проектах, а також розказати про мої успіхи в проекті, в якому я був задіяний. Др. Баумгартнер давав мені рекомендації, що робити далі і як можна спробувати справитись з проблемами, що виникали по ходу роботи над проектом. Також я мав можливість працювати разом з іншою студенткою, що була задіяна в тому ж проекті, що і я.

РОЗДІЛ 2. ДОБУВАННЯ ДАНИХ З СОЦІАЛЬНИХ МЕРЕЖ, ДОСЛІДЖЕННЯ ГРАФІВ ТА ПРОГРАМНИХ ЗАСОБІВ ЇХ АНАЛІЗУ

2.1. Важливість добування даних з соціальних мереж

Добування даних з соціальних мереж є досить новою областю досліджень з багатьма невирішеними проблемами. Ця область потребує нових підходів Data Mining і маштабованих алгоритмів, які б обєднали різні дисципліни, концепції і теорії. В загальному, соціальні мережі можна розглядати як світ соціальних атомів (індивідумів), сутностей (контенту, мереж) і взаємодій між цими індивідумами та сутностями. [3]

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

2.2. Як дані соціальних мереж можна представити у вигляді графу

В соціальних мережах люди взаємодіють між собою через дружбу, e-mail, блоги, купляючи схожі продукти і багатьма іншими способами. Аналізувати соціальні мережі можна представивши їх як граф. [3]

Рис 2.1: Приклад соціального графу

Як приклад, розглянемо множину осіб в соціальній мережі. Кожна особа може бути представлена у вигляді вузла, і двоє осіб що дружать між собою можуть бути зєднані ребром. [3]

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

- Хто є найбільш популярним чи дружелюбним в мережі.

- Через яку особу зєднані різні групи людей?

- Як люди згуртовані навколо якоїсь ідеї чи інформації?

- Як допомогти різним організація координувати між собою дії. Тощо.

2.3. Міри центральності

Міри центральності визначають найбільш важливі вузли в графі. Центральність вузла – це функція, що присвоює кожній вершині в мережі певне дійсне значення. Чим більше значення, тии більш центральною є вершина в мережі (яке б визначення центральності не використовувалось). [4]

Щоб зрозуміти, яка міра центральності важлива в даному проекті, потрібно проаналізувати різні міри графів. Було обрано три міри центральності:

1) Degree Centrality. В реальних відносинах між людьми, ми зазвичай вважаємо людей з великою кількістю звязків більш важливими. Degree centrality відображає цю ідею, як значення. Degree centrality представляє вершини з більшою кількістю звязків важливішими. In-degree і out-degree міри властиві для орієнтованих графів. In-degree centrality вимірює, наскільки популярною є вершина, в той час, як out-degrees, вимірює наскільки дружелюбною є вершина [3].

2) Betweenness centrality – визначає скільки є між довільною парою вершин найкоротших шляхів, що пролягають через певну іншу вершину. Вершина з більшим значенням betweenness centrality має більший вплив на обмін даними в мережі, з припущенням, що обімн даниими відбувається найкоротшими шляхами.[6]

3) Closeness centrality – є мірою, що визначає наскільки швидко дві вершини можуть обмінятися інформацією. Отже, чим більш центральними є вершини тим ближче вони знаходяться до всіх інших вершин. Формально, вони будуть мати найменшу середню відстань до всіх інших вершин. [3]

SNAP

Для даного проекту важливо мати оптимізовані і гнучкі засоби зберігання і аналізу графів. Також потрібно мати можливість розробляти нові алгоритми на базі цих засобів.

Stanford Network Analysis Platform (SNAP) є бібліотекою для аналізу графів і мереж загального використання, написаною на C++. Вона може бути легко масштабована для великих мереж. Ця бібліотека містить ефективні алгоритми для маніпулювання великими графами, обчислення їх структурних властивостей, генерування послідовних чи випадкових графів, тощо. Нажаль немає самостійної бібліотеки цього проеку, проте проект надає набір С++ класів. SNAP також використовується і є доступним через графічну оболонку NodeXL, яка інтегрує засоби аналізу мереж в пакет Microsoft Office, зокрема в Excel. [7]

NodeXL

Оскільки інформація в соціальних медіа може бути представлена у вигляді орієнтованого графу, то нам потрібен інструмент, що може завантажувати такий граф з мережі і надавати можливість його обробки. З цим завданням може справитись NodeXL. NodeXL є вільним пакетом програмних засобів для аналізу мереж і візуалізаці для Microsoft Excel, що доступний з відкритим кодом. NodeXL містить набір вбудованих бібліотек класів, побудованих на основі WPF. Для цього пакету є можливість розробити розширення для імпорту даних з різних джерел. На даний час існує багато готових розширень, серед яких розширення для імпорту даних з соціальної мережі Facebook, що є однією з цільових мереж в рамках даного дослідження. NodeXL може імпортувати дані з соціальної мережі і представити їх у вигляді графу. Цей граф пізніше може бути візуалізований. NodeXL реалізовує методи обчислення загальновживаних мір графів, використовуючи бібліотеку SNAP. Серед таких мір: центральність, коефіцієнт кластеризації, тощо. NodeXL підтримує орієнтовані і неорієнтовані мережі. Він реалізовує різні алгоритми визначення спільнот і дозволяє користувачам автоматично визначати кластери в їхніх соціальних мережах. [8]

GraphML

NodeXL забезпечує багато різних варіантів зберігання графу. Одна з них –формат GraphML.

GraphML – це файловий формат на основі XML, головним призначенням якого є збереження графів. GraphML визначає спільний формат для представлення структури графа. Він використовує синтаксис на основі XML і підтримує велику різноманітність можливих типів графів, включаючи орієнтовані, неорієнтовані, змішані графи, гіперграфи і специфічні атрибути для різних предметних областей. Завдяки синтаксису, що базується на XML, цей формат може бути розширений. Він також забезпечує простий механізм зберігання даних, що повязані з вершинами чи ребрами. [9]

2.7. Завдання на базі практики

Моїм завданням під час практики в LSU було: дослідити принципи роботи SNAP і NodeXL, дослідити можливості збереження даних в GraphML, дослідити міри центральності графів, дослідити засоби, з допомогою яких дані з соціальних мереж можуть бути представлені у вигляді графу, як обєднати графи отримані з різних сторінок соціальної мережі Facebook, і як таке обєднання вплине на різні міри графу.

РОЗДІЛ 3. Результати отримані на базі практики

3.1. Демонстраційний додаток

В кінці практики мною було розроблено демонстраційний додаток. Цей додаток забезпечує можливості завантаження мереж з різних сторінок Facebook; збереження графу в файл формату GraphML; обчислення мір графу, зокрема різні міри центральності і коефіцієнт кластеризації; обхід вершин і ребер графу; обєднання різних графів в один.

Всі ці функції реалізовані з використанням засобів бібліотеки класів NodeXL. Моїм завданням було використати цю бібліотеку і дослідити завантажені нею графи і їхні міри. Для цього я розробив простий клас на мові C#, що реалізує виклики методів бібліотек NodeXL і забезпечує певні маніпуляції над графом.

Розширення NodeXL завантажує дані з соціальних мереж в граф за наступними правилами:

- Кожна особа представляється як окрема вершина

- Кожен запис представляється як окрема вершина іншого типу

- Якшо учасник спільноти прокоментував якийсь запис/інший коментарій, між ним і творцем цього запису створюється зв'язок типу «Коментатор»

- Якщо інший учасник прокоментував той же запис, між ним та іншии коментаторами встановлюється зв'язок типу «Спів-коментатор»

- Якщо учасник вподобав запис, тоді зв'язок має тип «Вподобач»

- Якщо інший учасник вподобав той же запис, то між ним та іншими вподобачами встановлюється зв'язок «Спів-вподобач»

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

Дата добавления: 2015-10-23