Завдання.

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

2. Порівняти точність результатів, наповнення кластерів, центри кластерів і значення цільової функції.

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

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

Початкові дані для виконання роботи знаходяться в файлі lab_CCC_vars.xls в робочому каталозі дисципліни на сервері локальної комп’ютерної мережі кафедри (лист “кластеризація”).

Методичні вказівки

Див. Конспект лекцій з дисципліни.

Приклад розв’язання задачі

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

X1 - валова додаткова вартість у розрахунку на одну людину (у фактичних цінах, грн.);

X2 - територія (тис. кв. км); X3 - інвестиції в основний капітал на одну людину (у порівняльних цінах, грн.);

X4 - прямі іноземні інвестиції на одну людину (дол. США);

X5 - зайнятість населення на 10 тис. чол.;

X6 - грошові доходи населення на одну людину (грн.);

X7 - кредити, надані суб'єктам господарювання на одну людину;

X8 - кількість отриманих патентів на винаходи на 10 тис. чол.

Для порівняльного аналізу вибрані класичні методи - деревовидна кластеризація і метод середніх. Кількість кластерів апріорно задана і дорівнює 2.

По методу середніх отримані наступні результати. До першого кластеру віднесені Дніпропетровська, Донецька, Запорізька, Миколаївська, Одеська, Полтавська і Харківська області.

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

Кластеризація проводилась також з використанням еволюційного моделювання. Критерієм закінчення обчислювального процесу вибрана максимальна кількість ітерацій, яка дорівнювала 1000. Для тих же двох кластерів і восьми факторів кількість змінних (хромосома), для яких проводилася оптимізація фітнес-функції, склала 16. До вибіркової популяції увійшло двадцять елементів. Враховуючи те, що фітнес-функція є поліекстремальною, значення ймовірності мутації збільшено і дорівнювало 0,4. Таке значення подовжило час обчислень, але і значно зросла точність розрахунків за рахунок частішого вибивання цільової функції з локальних мінімумів. Для контролю за процесом обчислень в режимі реального часу виводилася інформація про значення фітнес-функції на кожній ітерації; про середню відстань між центрами кластерів; значення центрів кластерів.

Значення фітнес-функції зменшилося з 6-10⁹ до 11351587, причому на початкових етапах зменшення відбувалося гіперболічно, а на останніх - лінійно. Середня відстань між центрами кластерів зменшувалася лінійно, з дисперсією, що постійно зменшується.

У результаті обчислень отримано два центри кластерів.

Координати першого: X₁ =4553; X₂ =0,01; X₃ =915; X₄ =99; X₅ =4623; X₆ =2554; X₇ =791; X₈ =1,34.

Координати другого: X₁ =2952; X₂ =0,02; X₃ =530; X₄ =58; X₅ =4288; X₆ =1555; X₇ =297; X₈ =0,59.

До першого кластера відносяться Дніпропетровська, Донецька, Миколаївська, Одеська, Полтавська і Харківська області.

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

Лабораторна робота №7

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