Огляд алгоритмів кластеризації схем на основі дерева оптимального згортання

Міністерство  освіти та науки України

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

Інститут  комп’ютерних наук та інформаційних  технологій

 

 

                                                                                                                 Кафедра: ПЗ

                                                                    

 

Курсова робота

 

з дисципліни: “ Комбінаторні моделі в автоматизованих системах ”

на  тему:  “ Огляд алгоритмів кластеризації схем на основі дерева оптимального згортання”

 

 

 

 

  Виконав:

ст. гр.

                                                                                                                        

                         

    Перевірив:

                                                                                                                           

 

 

 

 

 

 

 

«Львів – 2010»

Зміст

Вступ………………………………………………………………………………..3

1.Ієрархічна кластерізація…………………………………………………………4

   1.1.Постановка задачі……………………………………………………………4

   1.2. Формулювання задачі……………………………………………………….5

   1.3. Алгоритмізація задачі формування кластерів……………………………..5

   1.4. Формування списку пар елементів/кластерів, зв’язаних між собою ……5

   1.5. Визначення критерію об’єднання для виділених пар…………...........…...6

   1.6. Упорядкування пар за значенням критерію…………………….................6

   1.7. Вибір пар елементів/кластерів для об’єднання……………………………6

   1.8. Вилучення пар елементів із списку впорядкованих пар………………….7

   1.9. Модифікація впорядкованого списку пар…………………………………7

2. Опис структур даних……………………………………………………….....8

3. Особливості програмної реалізації…………………………………………..10

4. Експериментальні дослідження процесу згортання схеми………………..11

5. Алгоритми послідовного пакування схем в процесі побудови дерева

оптимального  згортання схем……………………………………………………13

6. Алгоритми послідовного пакування схем на основі побудованого

дерева оптимального згортання………………………………………………….14

Висновок…………………………………………………………………………..17

Література…………………………………………………………………………18 

Вступ

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

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

Для розв’язання  задач можна застосовувати метод  оптимального згортання схеми, який полягає в паралельно-послідовному формуванні підсхем, що мають однакові або близькі за взаємною зв’язністю елементів характеристики. Метод  оптимального згортання схеми виявляє  ієрархічну кластерну структуру  схеми на основі багатокрокового  процесу ідентифікації та об’єднання підсхем, які є щільнішими за інші. Бажано виявити реальні згустки  схеми, їхнє взаємне входження –  менших у більші – та зв’язки між ними. Це сприяє виділенню окремих сильно зв’язних груп, а також вказуватиме на їхнє взаємне входження. Одержання якісних кластерів є не менш важливим за швидкодію роботи алгоритму. Хороші результати кластеризації дають змогу спростити багато інших задач, таких, як декомпозиція, оптимізаційні задачі.

Якість  кластеризації можна оцінювати залежно від якості множини окремих кластерів верхніх рівнів, близьких за розмірами, які не мають входжень один в одного.

 

 

 

 

 

 

 

1.Ієрархічна кластерізація

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

Рис. 1. Приклад представлення кластеризації

Мета кластеризації - побудувати оптимальне розбиття об'єктів на групи.

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

 

1.1. Постановка задачі

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

 

1.2. Формулювання задачі

Більшість реальних складних схем можна представити  як пару: S=(P, E); (1), де P={_p1,…,p_n} –множина елементів, E={e₁,…,e_m} – множина зв’язків між елементами.

Необхідно виявити сильно зв’язні згустки системи та побудувати дерево оптимального згортання T^R, яке відображає ієрархічне входження малих згустків (кластерів) у більші та корінь якого відповідає всій схемі. У випадках, коли система містить кілька незв’язаних підсистем, будується ліс дерев F^R={T^R₁,…,T^R_n}.

 

1.3. Алгоритмізація задачі формування кластерів

Метод оптимального згортання схеми ґрунтується  на виявленні сильно зв’язних згустків схеми – кластерів. На кожному кроці два елементи (кластери) об’єднуються в один, кластери формують дерево оптимального згортання T^R, яке відображає ієрархічне входження малих згустків у більші та корінь якого відповідає всій схемі. Базові кроки алгоритму побудови дерева оптимального згортання схеми T^R є такі:

 

1.4. Формування списку пар елементів/кластерів, зв’язаних між собою

Для побудови пар елементів P_T використовується інформація зі списків NetList i ElementList. Для кожного зв'язка із множини зв'язків існує множина елементів, для яких цей зв'язок є спільним.Net₁={p₁,p₂,p₄,p₈} зв’язок Net₁ формує пари з елементів P_T1=p₁p₂; P_T2=p₁p₄; P_T3=p₁p₈; P_T4=p₂p₄ ;P_T5=p₂p₈; P_T6=p₄p₈.

Зв’язок, який об'єднує n елементів, формує число M = (n-1)*n/2 пар. Для кожної пари елементів визначаються множини зовнішніх, внутрішніх та довгих зв’язків і критеріїв згортання. Множина внутрішніх зв’язків пари є результатом перетину множин зв'язків елементів, які утворюють пару.

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

 

1.5. Визначення критерію об’єднання для виділених пар

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

Досліджуються три критерії згортання:

1) η1 = E^Ext(P_T) – E^Int(P_T);

2) η2 = E^Ext(P_T) – E^Int(P_T) – E^com(P_T);

3) η3 = Et^Ext(P_T)

де:

E^Ext(P_T) – кількість зовнішніх зв’язків пари елементів;

E^Int(P_T) – кількість внутрішніх зв’язків пари елементів;

E^com(P_T) – кількіцсть довгих зв’язків пари елементів.

 

1.6. Упорядкування пар за значенням критерію

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

 

1.7. Вибір пар елементів/кластерів для об’єднання

Розглядаються два підходи до вибору пар елементів/кластерів  для об’єднання:

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

Відібрані пари формують множину пар елементів  кандидатів для об’єднання. З цієї множини для об’єднання (утворення  нових кластерів) відбираються пари, які не конфліктують між собою. Конфліктуючі пари – це пари, в яких є спільний один з елементів: P_T1 = p₁p₂ , P_T2 = p₁p₃ , p₁ –спільний елемент.

 

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

Всі відібрані  пари, які згорнулись у кластери, усуваються із списку впорядкованих  пар. Пари, які конфліктували, заносяться на початок списку. У результаті згортання список пар постійно скорочується.

 

1.9. Модифікація впорядкованого списку пар

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

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

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

 

2. Опис структур даних

Структури даних програми використовують однонапрямлені і двонапрямлені списки та списки з розгалуженням. Також використовуються динамічні масиви різних структур і  простих типів даних. Зв’язки  кожної пари подають у вигляді  списків, які характеризують її внутрішні, зовнішні та довгі зв’язки. Робота зі списками зв’язків побудована так, щоб звести до мінімуму

затрати пам’яті  і повторні обчислення.

Пари  елементів будуються зі списків ElementList і NetList. ElementList – це спискова структура, кожен зв’язок якої підпорядкований одному елементу схеми та містить список зв’язків, інцидентних до цього елемента (рис. 2), NetList – спискова структура, кожен елемент якої відповідає одному зв’язку схеми та містить список елементів, інцидентних до цього (рис. 3). Пара елементів – це структура, яка містить: назву першого елемента; назву другого зв’язку; посилання на список зовнішніх зв’язків; посилання на список внутрішніх зв’язків, посилання на список довгих зв’язків, інформацію про кількість внутрішніх і зовнішніх зв’язків; значення критерію згортання; два прапорці, які вказують, з чого утворена пара (елементів, кластерів, елемента і кластера); посилання на список зв’язків для першого елемента (кластера); посилання на список зв’язків для другого елемента (кластера).

Рис. 2. Представлення структури NetList

Рис. 3. Представлення структури ElementLis

Рис. 4. Представлення структури даних для пари елементів/кластерів

 

На рис. 4 подано інформацію, що зберігається в пам’яті про пару зв’язаних елементів. Введено такі позначення: P_α іP_b– елементи, або кластери, які утворюють пару; e^ext, e^int, e^com – список внутрішніх, зовнішніх довгих зв’язків між P_α і P_b; η– значення критерію згортання; N^ext, N^int, N^long – кількість внутрішніх, зовнішніх і довгих зв’язків пари P_α і P_b; f1, f2 – прапорці, які вказують, чи P_α і P_b є елементами, чи кластерами; e_a , e_b – посилання на списки всіх зв’язків для елементів (кластерів). Пари, які згорнулись, записуються в масив. Елементи цього масиву є структурами і містять таку інформацію: P_α і P_b – назва елементів чи кластерів, які утворили цей кластер; С – назва утвореного кластера; N_c – кількість елементів, які об’єднує кластер С; Itr – кількість ітерацій, потрібних для згортання кластера С. На рис. 4. представлена інформація про модель дерева згортання.