Методи і алгоритми неієрархічної кластеризації для задач інтелектуального аналізу даних

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

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

Національний університет «Львівська політехніка»

05.13.06 - Інформаційні технології

Автореферат дисертації на здобуття наукового ступеня

кандидата технічних наук

Методи і алгоритми неієрархічної кластеризації для задач інтелектуального аналізу даних

Файсал М. Е. Сардієх

Львів 2011

Дисертацією є рукопис

Робота виконана у Національному університеті "Львівська політехніка" Міністерства освіти і науки, молоді та спорту України

Науковий керівник

доктор технічних наук, професор

Лобур Михайло Васильович,

завідувач кафедри “Cистеми автоматизованого проектування”

Національного університету "Львівська політехніка

Офіційні опоненти

доктор технічних наук, професор

Сікора Любомир Степанович,

професор кафедри

“Автоматизовані системи управління“

Національного університету

"Львівська політехніка"

кандидат фізико-математичних наук, доцент

Гече Федір Елемірович,

доцент кафедри

“Кібернетика і прикладна математика“

Ужгородського національного університету

Захист відбудеться 4 липня 2011р. о 1000 годині на засіданні спеціалізованої вченої ради Д 35.052.14 у Національному університеті "Львівська політехніка" (79013, м.Львів-13, вул. С.Бандери, 28а, ауд 108, V навч. корп.).

З дисертацією можна ознайомитися у бібліотеці Національного університету "Львівська політехніка" (79013, м. Львів, вул. Професорська, 1).

Автореферат розісланий 3 червня 2011 р.

Вчений секретар спеціалізованої вченої ради, к.т.н., доц.Батюк А.Є.

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

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Стрімкий розвиток і поширення нових інформаційних технологій набуває сьогодні характеру глобальної інформаційної революції, виявляє зростаючий вплив на політику, економіку, управління, фінанси, науку, культуру і інші сфери життєдіяльності в рамках національних кордонів і світу в цілому. Як підкреслюється в Окінавській Хартії глобального інформаційного суспільства, прийнятої лідерами «вісімки» 22 липня 2000 року, «інформаційно-комунікаційні технології (ІТ) є одним з найважливіших факторів, що впливають на формування суспільства XXI століття». Настає новий етап у розвитку процесів обміну інформацією. На даному етапі розвитку людської цивілізації практично вже сформовано світовий інформаційний простір. Тому актуальною є задача підвищення ефективності пошуку необхідної інформації в глобальному інформаційному просторі. Це завдання вимагає розроблення та дослідження методів і алгоритмів розбиття інформаційних моделей об'єктів на групи і класи. Завдання такого роду виникають в таких сучасних інформаційних технологіях як Data Mining, Text Mining, Web Mining, розпізнавання образів, машинне навчання.

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

Найважливіший внесок у розвиток методів і алгоритмів кластеризації внесли такі вчені як Айвазян С.А. - розробив методи класифікації багатовимірних спостережень, Бухштабер В.М. - розробив ряд методів автоматичної класифікації на основі математичних моделей, Єнюков І.С. - розробив методи кластеризаціїї об'єктів із категоризаційними ознаками, Мешалкін Л.Д. - розробив локальні методи класифікації, Мандель І.Д. - дослідив ряд функцій оцінки якості кластеризації. Цими авторами розроблено ряд методів і алгоритмів кластеризації і класифікації багатовимірних інформаційних моделей об'єктів.

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота безпосередньо пов'язана з планами наукових досліджень, які виконуються за тематикою кафедри “Системи автоматизованого проектування” Національного університету “Львівська політехніка” по темі: “Розроблення методів та засобів оброблення гетерогенних даних в САПР”, термін виконання червень 2010 р. - грудень 2011 р. (№ держ. реєстр. 0110U005020).

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

Для досягнення зазначеної вище мети необхідно вирішити такі задачі:

провести аналіз сучасного стану інформаційних технологій для зберігання, обробки та пошуку інформації;

виконати аналіз сучасного стану методів та алгоритмів кластеризації інформаційних моделей об'єктів різної фізичної природи;

розробити нові та удосконалити існуючі методи та алгоритми неієрархічної кластеризації інформаційних моделей об'єктів різної фізичної природи;

розробити математичне та програмне забезпечення системи неієрархічної кластеризації інформаційних моделей об'єктів.

Об'єкт дослідження - процес неієрархічної кластеризації інформаційних моделей об'єктів різної фізичної природи.

Предмет дослідження - методи та засоби інформаційних технологій оптимальної кластеризації інформаційних моделей об'єктів різної фізичної природи.

Методи дослідження - кластерний аналіз для побудови методів і алгоритмів неієрархічної кластеризації, теорія графів для побудови моделі пошукового простору, лінійна алгебра для побудови розрахункових залежностей, теорія баз даних для розроблення інформаційного забезпечення багатоваріантної неієрархічної кластеризації, теорія систем для побудови діалогового забезпечення системи неієрархічної кластеризації.

Наукова новизна отриманих результатів полягає в тому, що:

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

* отримав подальший розвиток метод знаходження центрів кластерів, що дозволило розробити на його основі евристичний алгоритм пошуку центрів кластерів (ЕАПЦК), який, на відміну від існуючих, за початкову точку приймає центр ваги множини інформаційних моделей об'єктів, дає змогу визначити центри кластерів для випадку погано відокремлених областей і покращує значення критеріїв кластеризації;

* розвинуто метод k-середніх, що дозволило розробити на його основі в комбінації з методом порогової величини алгоритми для знаходження кластерів, які на відміну від методу порогової величини не перетинаються і оптимальні відносно критеріїв, що наведені в третьому розділі;

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

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

* розроблені методи та моделі були використані для реалізації математичного забезпечення програмної системи кластерного аналізу інформаційних моделей об'єктів довільної фізичної природи;

* розроблена структура бібліотеки (ансамблю) алгоритмів неієрархічної кластеризації інформаційних моделей об'єктів довільної фізичної природи, яка не вимагає задання початкової кількості та положення центрів кластерів і здійснює оптимальне розбиття на кластери;

* розроблено діалоговий інтерфейс системи неієрархічної кластеризації, який дозволяє здійснювати введення і виведення інформації в текстовому та графічному 2D і 3D режимах.

Особистий внесок здобувача. Всі наукові результати теоретичних і практичних досліджень, які викладені в дисертації ? одержані автором особисто. У друкованих працях, опублікованих у співавторстві, дисертанту належать: [3, 9] ? розроблення алгоритму пошуку оптимальної кількості кластерів; [6] - аналіз інформаційних технологій data mining і knowledge discovery; [4, 8] - розроблення алгоритму оцінки оптимальності результатів кластеризації за критерієм відстані; [1, 7, 10] - розроблення методу і алгоритму на його основі для графового адаптивного пошуку кількості і положення центрів кластерів; [2, 12] - розроблення і дослідження алгоритмів кластеризації для великих колекцій документів; [5, 8, 11] - розроблення архітектури автоматизованої системи кластерного аналізу неієрархічними методами; [4,13] - розроблення алгоритмів неієрархічної кластеризаціі.

Апробація результатів дисертації. Основні наукові, теоретичні положення та практичні результати дисертаційної роботи доповідалися і обговорювалися на: Міжнародній науково-технічній конференції «Комп'ютерні науки та інформаційні технології», СSIT (Львів, 2010), Українсько-польській науково-технічній конференції «САПР у проектуванні машин. Питання впровадження та навчання», CADMD (Львів, 2008); Міжнародній конференції «Перспективні технології і методи проектування МЕМС», MEMSTECH (Львів, 2008, 2009, 2010); Міжнародній науково-технічній конференції «Досвід розробки та застосування приладо-технологічних САПР в мікроелектроніці», CADSM (Львів-Поляна, 2009, 2011).

Публікації. За результатами досліджень, які викладені в дисертації, опубліковано 13 наукових праць, з-поміж яких 4 статті опубліковано у фахових наукових виданнях за переліком ВАК України, 9 публікацій в матеріалах міжнародних конференцій.

Структура та обсяг дисертації. Дисертаційна робота складається із вступу, чотирьох розділів, висновків, додатків та списку літературних джерел. Загальний обсяг дисертації складає 125 сторінок, з них 107 сторінок основного текстуё 42 рисунки, 8 таблиць. Список літератури містить 146 найменувань.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

Показано, що найбільш перспективними сучасними інформаційними технологіями є Data Mining, Text Mining і Web Mining. Саме застосування і розвиток цих технологій дає змогу в даний час і в найближчому майбутньому здійснити ефективний пошук інформації в сучасному насиченому інформаційному просторі.

Показано важливість використання ефективних методів і алгоритмів кластеризації в сучасних інформаційних технологіях.

Виконано аналіз характеристик сучасних ієрархічних і неієрархічних методів кластеризації щодо вирішення завдань побудови адаптивних інформаційно-пошукових систем, систем пошуку текстової інформації, пошуку інформації в INTERNET.

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

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

У результаті проведеного аналізу програмного забезпечення для рішення задач кластеризації встановлено, що найчастіше при вирішенні завдань кластеризації використовуються наступні програмні системи: SPSS, STATISTICA, SAS. Також встановлено, що для вирішення завдань неієрархічної кластеризації в цих системах, в основному, використовується класичний метод k-середніх.

У другому розділі наведена формальна постановка задачі кластеризації інформаційних моделей та розроблені методи і алгоритми пошуку початкової кількості та положення центрів кластерів. Формальна постановка задачі неієрархічної кластеризації полягає в наступному.

Інформаційна модель об'єкта для неієрархічної кластеризації - це вектор числових ознак, які характеризують властивості об'єкта:

.

Нехай - множина n інформаційних моделей, кожна з яких володіє d ознаками. Нехай - множина алгоритмів кластеризації. Кожен алгоритм кластеризації генерує розбиття для даної множини D на кластери . Нехай - множина всіх кластерів, що отримані множиною алгоритмів L. Метою неієрархічної кластеризації є отримання оптимального розбиття на кластери , , яке відповідає оптимальним значенням критеріїв кластеризації. При цьому елементи множини T повинні задовільняти наступним умовам:

кожен кластер повинен мати хоча б одну інформаційну модель;

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

Для представлення інформаційних моделей текстових документів використовувується зважений вектор частот характерних слів:

,

де tfi - частота входження i-того характерного слова в документ (відношення кількості входження певного слова в документ до загальної кількості слів у документі); N - загальна кількість слів у документі; dfi - кількість входження i-того слова в документ.

Частоти слів зважуються порядками обернених частот входження слів в документи для зменшення впливу розбіжності в частотах.

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

Алгоритм складається з таких кроків:

Крок 1. Обчислити центр ваги множини інформаційних моделей об'єктів . Якщо , тоді перейти на наступний крок, інакше центром кластеру вибрати і ЗУПИНКА.

Крок 2. Центром першого кластеру вибрати точку , яка знаходиться на максимальній відстані від . Якщо таких точок декілька, то вибрати одну із них. Покласти , і перенумерувати елементи . Якщо , тоді перейти до наступного кроку, інакше - ЗУПИНКА.

Крок 3. Обчислити евклідові відстані від точок множини D до центру першого кластера , .

Крок 4. Вибрати максимальну відстань

Крок 5. Вибрати центр другого кластера , , і перенумерувати елементи . Якщо , тоді перейти до наступного кроку, інакше - ЗУПИНКА

Крок 6. Обчислити евклідові відстані від точок множини D до центрів першого і другого кластерів , , .

Крок 7. Для кожного індексу вибрати мінімальну величину .

Крок 8. В отриманій множині вибрати максимальну величину і виконати присвоєння .

Крок 9. Якщо , тоді вибрати центр третього кластеру , , , перенумерувати і обчислити . Якщо , то перейти до наступного кроку. У випадку, коли або - ЗУПИНКА.

Крок 10. Обчислити відстані від точок множини D до центрів першого, другого і третього кластерів , , , .

Крок 11. Для кожного індексу вибрати мінімальну величину .

Крок 12. В отриманій множині вибрати максимальну величину і виконати присвоєння .

Крок 13. Якщо , тоді вибрати центр четвертого кластеру , , , перенумерувати елементи і обчислити . Якщо , тоді перейти до наступного кроку. У випадку, коли , або - ЗУПИНКА.

Алгоритм продовжує роботу до тих пір, поки не виконається одна з умов або .

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

Параметр визначає швидкість збіжності алгоритму. Параметр Т задає порогову величину.

Для досліджуваної множини інформаційних моделей об'єктів в d-мірному просторі обчислюється матриця евклідових відстаней:

,

де .

Рис. 1. Схема роботи графового адаптивного алгоритму пошуку кількості та положення центрів кластерів

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

Робота алгоритму полягає у виконанні таких кроків:

Крок 1. Визначити початкову кількість активних вузлів графа

,

де - кількість елементів множини D.

Крок 2. Визначити максимальну відстань між точками вузлів графа

.

Крок 3. Визначити початкові параметри алгоритму

, , , ,

де - наперед задане натуральне число.

Крок 4. Визначити вагові коефіцієнти

де .

Крок 5. Визначити початкові активності вузлів графа

, .

Крок 6. Встановити індекс ітерації k = 0.

Крок 7. Виконати розрахунок активностей вузлів графа

.

Крок 8. Визначити кількість вузлів графа, для котрих виконується умова , і присвоїти змінній p.

Крок 9. Зменшити кількість активних вузлів графа

,

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

Крок 10. Якщо , тоді перехід на крок 11, інакше , і перехід на крок 7.

Крок 11. Обчислити відстані між точками активних вузлів графа

.

Крок 12. Обчислити мінімальну відстань між точками активних вузлів графа

.

Крок 13. Якщо і , тоді і перехід на крок 4, інакше - ЗУПИНКА.

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

У третьому розділі розробляються і досліджуються неієрархічні алгоритми кластеризації, в основі яких лежить метод k-середніх. Показано, що основним недоліком алгоритмів на базі методу k-середніх є те, що вони вимагають початкового задання кількості та положення центрів кластерів. Інформація про ці параметри на початковому етапі дослідження інформаційного простору, як правило, відсутня. Тому актуальним завданням є розроблення таких алгоритмів, які вимагають задання мінімальної кількості початкових параметрів, прості в реалізації, дозволяють проводити багатоваріантний аналіз і дають задовільні результати. Найбільш відомим з таких алгоритмів є класичний алгоритм порогової величини. До недоліків такого алгоритму належить те, що в результаті його роботи отримуються кластери сферичної форми з великою кількістю областей перетину. Тому розроблені дві модифікації цього алгоритму: модифікація, яка визначає стабільні положення центрів кожної кластерної області та алгоритм якісного порогу.

В роботі запропоновано модифікований алгоритм порогової величини, який визначає стабільні положення центрів кожної кластерної області. Цей алгоритм є комбінацією класичного алгоритму порогової величини і алгоритму k-середніх. Особливість розробленої комбінації полягає в тому, що, на відміну від алгоритму порогової величини, в кожній області кластеризації спочатку обчислюється стабільний геометричний центр множини інформаційних моделей і ця множина інформаційних моделей надалі вилучається з розгляду як черговий кластер. Процес кластеризації продовжується до тих пір, поки ми не отримаємо порожню множину інформаційних моделей. На відміну від алгоритму k?середніх цей алгоритм не вимагає задання кількості і початкового положення центрів кластерів, і, на відміну від алгоритму порогової величини, цей алгоритм не утворює областей перетину кластерів.

Робота алгоритму полягає у виконанні таких кроків:

Крок 1. Визначити мінімальну і максимальну відстані між точками інформаційних моделей об'єктів

.

Крок 2. Визначити максимальне значення порогової величини

.

Крок 3. Визначити крок і початкове значення порогової величини

,

де .

Крок 4. Вибрати першу точку центра кластера

, ,

.

Крок 5. Встановити початкове значення індексу кластера q = 1, .

Крок 6. Визначити множину точок, які належать до q - того кластера наступним чином

, якщо ,

де , .

Крок 7. Методом k-середніх визначити стабільне положення q - того центра кластера і множину точок, які належать до q - того кластера .

Крок 8. Вилучити множину точок кластера з подальшого розгляду.

\, ,

впорядкувати індекси елементів множини , враховуючи індекси видалених точок.

Крок 9. Якщо , то перехід на крок 13, інакше на крок 10.

Крок 10. .

Крок 11. Визначити наступну точку центра кластера з використанням попередніх центрів кластерів

, .

Крок 12. Перехід на крок 6.

Крок 13. Збільшити величину порогу .

Крок 14. Якщо , тоді перехід на крок 5, інакше - ЗУПИНКА.

В роботі запропоновано алгоритм якісного порогу. У цьому алгоритмі кожна точка інформаційної моделі розглядається як можливий центр кластера. Для заданої величини радіуса сфери кластера (порогової величини) обчислюється стабільне положення центру кластера за допомогою алгоритму k-середніх. Підраховується кількість точок у кожному кластері для кожної точки множини. За перший кластер приймається той, для якого кількість точок максимальна. Цей кластер вважається першим знайденим кластером і виключається з подальшого розгляду. Процес триває до досягнення порожньої множини точок. Перевагою алгоритму є те, що він дозволяє визначити кластери з найбільшим скупченням точок і, тим самим, покращити критерії оптимальності. Недоліком є низька швидкодія.

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

Робота алгоритму полягає у виконанні таких кроків:

Крок 1. Визначити мінімальну і максимальну відстані між точками інформаційних моделей об'єктів

Крок 2. Визначити максимальне значення порогової величини

Крок 3. Визначити крок і початкове значення порогової величини

,

де .

Крок 4. Встановити початкове значення індексу перебору точок множини D

q=1, t=n, Bq=D.

Крок 5. Встановити початкове значення індексу проміжного кластеру

p=1.

Крок 6. Визначити початкове положення центру p - того проміжного кластеру

, .

Крок 7. Визначити множину точок, які належать до p - того проміжного кластера

якщо ,

де ,

Крок 8. Методом k-середніх визначити стабільне положення центру кластера Zp і множину точок, які належать до p - того проміжного кластера .

Крок 9. Визначити кількість точок, які належать до проміжного кластера

Крок 10. Збільшити значення індексу проміжного кластера

p=p+1.

Крок 11. Якщо , тоді перехід на крок 6, інакше перехід на крок 12.

Крок 12. Визначити індекс проміжного кластера, котрий містить найбільшу кількість точок

.

Крок 13. Визначити множину точок q-того кінцевого кластера

.

Крок 14. Видалити множину точок q-того кластера з подальшого розгляду

,

впорядкувати елементи множини , враховуючи індекси видалених точок.

Крок 15. Якщо тоді перехід на крок 18, інакше перехід на крок 16.

Крок 16. .

Крок 17. Якщо тоді перехід на крок 5.

Крок 18. Збільшити значення порогової величини .

Крок 19. Якщо , тоді перехід на крок 4, інакше - ЗУПИНКА.

Розглянуті особливості застосування алгоритму k-середніх в комбінаціїї з ієрархічними методами для кластеризації великих колекцій документів.

Істотною проблемою при застосуванні методів кластеризації є контроль оптимальності кластеризації. Пропонується використовувати точні і наближені оцінки оптимальності кластеризації. Точна оцінка оптимальності кластеризації здійснюється за допомогою розрахунку таких величин:

середній об'єм отриманих кластерів;

середня міжкластерна відстань;

середня відстань між центрами кластерів.

Об'єм кластера оцінюється як середнє значення суми відстаней між усіма точками інформаційних моделей, які належать даному кластеру.

де gs - кількість об'єктів в кластері Ks, , Nc - кількість отриманих кластерів.

Оцінка середнього об'єму отриманих кластерів розраховується за такою формулою

.

Відстань між кластерами розраховується як відстань між множинами

,

де - mA - кількість об'єктів в множині A; mB - кількість об'єктів в множині B.

Середня відстань між усіма отриманими кластерами

де Rc - відстань між кластерами Ki та Kj.

Середня відстань між центрами отриманих кластерів

,

де - Zi - центр i - того кластера; Zj - центр j - того кластера.

Точні оцінки оптимальності вимагають значного часу розрахунку. Тому пропонується використовувати для оцінки оптимальності індексні функції: «силуетний» індекс, індекс Дана, індекс Деві-Болдвіна.

«Силуетний» індекс дає оцінку оптимальності віднесення інформаційної моделі кожного об'єкта до належного кластера. Оптимальне значення «силуетного» індексу близьке до одиниці.

Індекс Дана дає наближену оцінку відношення відстані між кластерами до діаметру кластерів. Оптимальне значення цього індексу - максимальне.

Індекс Деві-Болдвіна дає наближену оцінку відношення діаметру кластерів до відстані між кластерами. Оптимальне значення цього індексу - мінімальне.

Запропоновано алгоритм пошуку оптимального розбиття на кластери, який полягає в багатоваріантному розрахунку розбиття на кластери та оцінці на кожній ітерації оптимальності розбиття на кластери.

У четвертому розділі розроблена структура підсистеми неієрархічного кластерного аналізу, яка включає модулі пошуку початкової кількості та положення центрів кластерів, модулі пошуку розбиття на кластери за допомогою класичного алгоритму порогової величини, модифікованого алгоритму порогової величини, алгоритму якісного порогу, алгоритму ISODATA, k-середніх, k-медоідів, модулів точної і наближеної оцінки оптимальності розбиття на кластери.

Структура підсистеми наведена на рис. 2.

Особливістю підсистеми є те, що вона дає можливість проводити дослідження методів та алгоритмів неієрархічної кластеризації щодо широкого кола завдань дослідження інформаційних моделей об'єктів різної фізичної природи. Розроблено засоби візуалізації результатів аналізу, які дозволяють виводити кінцеві результати розподілу точок по кластерах, проміжні результати покрокового рішення завдань, 2D і 3D графічне представлення результатів кластеризації. Діалогове забезпечення підсистеми дозволяє вводити нові дані з заданого файлу, генерувати дані випадковим чином, коректувати (додавати, видаляти) дані.

Інтерфейс користувача дозволяє виводити проміжні покрокові і кінцеві результати кластеризації, виводити результати кластеризації в окремий файл, вибирати довільні комбінації і порядок виконання алгоритмів.

Рис.2. Структура підсистеми неієрархічного кластерного аналізу.

Суттєвою особливістю розробленої ситеми є її орієнтація на пошук оптимального розбиття на кластери. Для цієї мети розроблена реляційна база даних результатів кластеризації. База даних зберігає результати кластерного аналізу кожного набору даних різними алгоритмами і з застосуванням різних метрик. Оскільки багатоваріантний пошук розбиття на кластери вимагає порівняння результатів кластерного аналізу різними методами, то така база даних дозволяє зберігати результати кластеризації і значення критеріїв кластеризації для кожного варіанту. Перевага бази даних полягає в тому, що вона містить лише зв'язки «один-до-багатьох» і клас належності обох сутностей в кожному зв'язку - обов'язковий. Це дозволило обійтись без введення асоціативних сутностей, що, в свою чергу, підвищило швидкодію роботи з базою даних і зменшило витрати зовнішньої пам'яті. Структура реляційних відношень для кожної сутності інфологічної моделі приведена в тексті дисертації. Інфологічна модель бази даних наведена на рис. 3.

Структура системи і діалогове забезпечення дозволяють вибирати алгоритми системи та їх комбінації в поєднанні з різними способами оцінки метричної відстані

У системі реалізовані наступні оцінки метрики: евклідова відстань, квадрат евклідової відстані, відстань Чебишева, степенева відстань, відстань Махалонабіса. Відстань Махалонабіса дозволяє здійснювати редукцію розмірності інформаційних моделей об'єктів.

Проведено дослідження складності розроблених неієрархічних алгоритмів кластеризації. Часова складність порівнювалася на тестових задачах, розмірність котрих змінювалася від n=10 до n=200.

Рис.3. Інфологічна модель бази даних

Тестові приклади генерувалися таким чином, що по кожній координатній осі числові значення вибиралися в інтервалі [-10,0;10,0] за допомогою генератора випадкових нормально розподілених чисел. Кількість кластерів приймалася рівною 5. Залежність часу розрахунку від розмірності задачі наведена на рис. 4.

Проведено дослідження розроблених методів та алгоритмів на відомих тестових наборах даних Iris і Haberman. Оцінка оптимальності кластеризації виконувалася за допомогою точних і наближених індексних критеріїв оптимальності. Розбіжність була в межах 10%. Застосування наближених індексних критеріїв дало економію в часі на 30% у порівнянні із застосуванням точних критеріїв. Тестовий набір Iris містить три добре розділені кластери. Найкращий за критеріями оптимальності результат для цього набору був отриманий при застосуванні графового адаптивного алгоритму пошуку центрів кластерів в комбінації з алгоритмом k-середніх.

Рис. 4. Оцінка складності розроблених неієрархічних алгоритмів кластеризації

Тестовий набір Haberman містить два погано відокремлені кластери. Найкращий за критеріями оптимальності результат для цього набору був отриманий при застосуванні евристичного алгоритму пошуку центрів кластерів у комбінації з алгоритмом k-середніх. В усіх проведених тестових розрахунках найкращим виявилося використання в якості метрики квадрату евклідової відстані.

Модифікований алгоритм порогової величини і алгоритм якісного порогу доцільно використовувати на початкових стадіях дослідження області кластеризації, оскільки ці алгоритми дають економію в часі до 20% у порівнянні з класичними алгоритмами k-середніх і k-медоідів.

ОСНОВНІ РЕЗУЛЬТАТИ І ВИСНОВКИ

У дисертаційній роботі вирішена наукова задача розроблення методів і алгоритмів оптимальної неієрархічної кластеризації інформаційних моделей об'єктів довільної фізичної природи.

При цьому отримано такі результати:

1. Проведений аналіз існуючого стану розвитку методів і алгоритмів кластеризації інформаційних моделей об'єктів довільної фізичної природи, що дало можливість визначити недоліки методів, алгоритмів і програмних систем.

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

3. Отримав подальший розвиток метод знаходження центрів кластерів, що дозволило розробити на його основі евристичний алгоритм пошуку центрів кластерів (ЕАПЦК), який, на відміну від існуючих, за початкову точку приймає центр ваги множини інформаційних моделей об'єктів, дає змогу визначити центри кластерів для випадку погано відокремлених областей і покращує критерії оптимальності на 20%.

4. Розвинуто метод k-середніх, що дозволило розробити на його основі, в комбінації з методом порогової величини, алгоритми для знаходження кластерів, які, на відміну від методу порогової величини, не перетинаються і оптимальні відносно критеріїв, що наведені в третьому розділі.

5. Отримав подальший розвиток метод багатоваріантного розбиття на кластери, що дозволило на його основі розробити алгоритм, який, на відміну від існуючого, дає змогу використовувати індексні оцінки оптимальності розбиття на кластери, що в, свою чергу, дозволило підвищити швидкодію на 30%.

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

7. Розроблена база даних, котра дозволяє зберігати результати багатоваріантного кластерного аналізу різними методами кластеризації із застосуванням різних методів оцінки критеріїв кластеризації.

8. Розроблено діалоговий інтерфейс системи неієрархічної кластеризації, який дозволяє здійснювати введення інформації, виведення інформації в текстовому та графічному 2D і 3D режимах.

СПИСОК ОСНОВНИХ ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

Адаптивний метод і алгоритм пошуку центрів кластерів за допомогою нейронної мережі / [Стех Ю.В., Файсал М.Е. Сардіх, Лобур М.В., Домброва М.С., Арцибасов В.Є.] // Моделювання та інформаційні технології. Зб. наук. пр. ІППМЕ ім.Г.Є. Пухова НАН України. - Київ, 2010. - Вип.57. - С. 271-277.

Розробка і дослідження алгоритмів кластеризації для великих колекцій документів / [Стех Ю.В., Файсал М.Е. Сардіх, Лобур М.В., М.С. Домброва М.С., Арцибасов В.Є.] // Моделювання та інформаційні технології. Зб. наук. пр. ІППМЕ ім.Г.Є. Пухова НАН України. - Київ, 2010, - Вип.58. - С. 283-290.

Алгоритм пошуку оптимальної кількості кластерів / [Стех Ю. В., Файсал М.Е. Сардіх, Лобур М. В., Керницький А.Б.] // Вісник НУ “Львівська політехніка” : Комп'ютерні системи проектування. Теорія і практика. - 2009. - № 651. - С. 129-131.

Алгоритмічна оцінка оптимиальності результатів кластеризації за критерієм відстані / [Стех Ю. В., Файсал М.Е. Сардіх, Керницький А.Б., Домброва М.С.] // Вісник НУ “Львівська політехніка” : Комп'ютерні системи проектування. Теорія і практика. - 2010. - № 685. - С. 131-134.

Dialog graphical system of classification with the help of distance function / [Stekh Y., Faisal M.E. Sardieh, Kernytskyy A., Nykyforchyn R.]// Proc. of the XVI Ukrainian-Polish Conference on “CAD in Machinery Design. Implementation and Education Problems” CADMD. - Lviv,2008 - P. 88-89.

Some trends in knowledge discovery and data mining / [Lobur M., Stekh, Y., Kernytskyy A., Faisal M.E. Sardieh] // Proc. of the IVth International Conference MEMSTECH. - Lviv-Polyana, 2008. - P. 95-97

Stekh Y. Neural network based clastering algorithm / Stekh Y., Faisal M.E. Sardieh, Lobur M. // Proc. of the Vth International Conference MEMSTECH. - Lviv-Polyana, 2009. - P. 168-169.

Graphical System for Pattern Recognition / [Stekh Y., Faisal M.E. Sardieh, Kernytskyy A., Lobur M.] // Proc. of the Xth International Conference CADSM. - Lviv-Polyana, 2009. - P. 483.

Stekh Y. Estimation of optimal clustering results / [Stekh Y., Faisal M.E. Sardieh, Kernytskyy A., Dombrova M.] // Proc. of the Vth International Conference on Computer Science and Information Technologies. - Lviv, 2010. - P. 173-174.

Stekh Y. Algorithm for clastering Web documents / [Stekh Y., Faisal M. E. Sardieh, Lobur M., Dombrova M.]// Proc. of the VIth International Conference MEMSTECH. - Lviv-Polyana, 2010. - P. 187.

Stekh Y. System for a cluster analysis / Stekh Y., Fajsal M.E. Sardieh, Lobur M. // Proc. of the Xth International Conference TCSET. - Lviv-Polyana, 2010. - P. 236.

Dеvelopment and study of clustering algorithms for large sets of data / [Stekh Y., Lobur M., Faisal M.E. Sardieh, Dombrova M., Artsibasov V.] // Proc. of the XIth International Conference CADSM. - Lviv-Polyana, 2011. - P. 202-204.

Research and development of methods and algorithms non-hierarchical clustering / [Stekh Y., Lobur M., Faisal M.E. Sardieh, Dombrova M., Artsibasov V.] // Proc. of the XIth International Conference CADSM. - Lviv-Polyana, 2011. - P. 205-207.

АНОТАЦІЇ

Файсал М.Е Сардієх. Методи і алгоритми неієрархічної кластеризації для задач інтелектуального аналізу даних. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 - інформаційні технології. - Національний університет «Львівська політехніка», Львів, 2011.

У дисертаційній роботі розв'язано наукову задачу розроблення методів і алгоритмів оптимальної неієрархічної кластеризації інформаційних моделей об'єктів довільної фізичної природи. Вперше розроблений метод і адаптивний алгоритм на його основі для графового адаптивного пошуку кількості і положення центрів кластерів а також розрахункові залежності для визначення оптимальних початкових параметрів роботи алгоритму. Отримав подальший розвиток метод знаходження центрів кластерів, що дозволило розробити на його основі алгоритм, який, на відміну від існуючих, за початкову точку приймає центр ваги множини інформаційних моделей об'єктів. Розвинуто метод k-середніх, що дозволило знаходити найбільш вагомі кластери, які оптимальні з точки зору кількості інформаційних моделей об'єктів. Отримав подальший розвиток метод оптимального розбиття на кластери, що дозволило на його основі розробити алгоритм, який, на відміну від існуючого, дозволяє використовувати індексні оцінки оптимальності розбиття на кластери, що в свою чергу дозволило підвищити швидкодію.

Ключові слова: інформаційна технологія, інформаційна модель, кластерний аналіз, оптимальна кластеризація, пошук центрів кластерів, алгоритм порогової величини, алгоритм k-середніх.

Файсал М.Е Сардиєх. Методы и алгоритмы неиерархической кластеризации для задач интеллектуального анализа данных. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 - информационные технологии - Национальний университет «Львовская политехника», Львов, 2011.

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

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

Ключевые слова: информационная технология, информационная модель, кластерный анализ, оптимальная кластеризация, поиск центров кластеров, алгоритм пороговой величины, алгоритм k-средних.

Faisal M.E Sardiеh. Research and development of methods and algorithms for non-hierarchical clustering for the intellectual tasks of data analysis. - Manuscript.

PhD thesis (candidate of technical science) by specialty 05.13.06 - information technology. - Lviv Polytechnic National University, Lviv, 2011.

This thesis research addressed the problem of developing methods and algorithms for the optimal non-hierarchical clustering for information models of arbitrary physical nature. First developed a method and an adaptive algorithm based on this for the adaptive search the number of cluster centers and their position as well as the calculated dependence to determine optimal initial parameters of the algorithm. Has been further developed a method for finding the cluster centers, which allowed us to develop on its basis an algorithm which, unlike existing ones, for the starting point takes the center of gravity of the set of information models of objects. Developed a method for k-means, which allowed to find the most weighty clusters that are optimal in terms of quantity of information models of objects. Was further developed method of optimal partitioning into clusters, which allowed him to develop the basis of an algorithm which, unlike the existing one, allows the use of index estimates the optimality of the partition into clusters, which in turn will allow better performance.

Key words: information technology, information model, cluster analysis, the optimal clustering, the search for cluster centers, the threshold magnitude algorithm, the algorithm k-means.

Размещено на Allbest.ru

...