3.2. Кластерний аналіз.

Класифікація – це віднесення об’єкта до його класу. Методи класифікації поділяють на два тири:

а) з навчанням – групи заздалегідь визначені;

б) без навчання – утворення таких груп на основі парметричних чи непараметричних критеріїв.

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

Є два типи інтересів користувача:

1) вияснити з якою мірою впевненості при використанні даної чисельної моделі можна вважати існування разних підмножин;

2) є підозра, що істинної відмінності між підмножинами немає, але для полегшення аналізу дуже великого числа елементів варто мати такі підмножини, отримавши їх шляхом штучного розчленування.

Інколи бажано транспонувати матрицю даних і класифікувати ознаки за їх значенням для різних об’єктів – зворотня класифікація.

Типи ознак:

Поліноміальні – (ознаки з невпорядкованими станами) визначаються станами (пр.: піщаник, граніт, базальт, крейда), хоча, можлива нумерація станів. Номер не несе ніякого змістового навантаження. Частинним випадком є бінарні (якісні) ознаки з двома станами.

Порядкові – (ознаки з впорядкованими станами) мають впорядкований ряд станів: рідкісний, порядковий, звичайний, багатющий. Хоча порядок має зміст, але відстані між станами невизначені.

Чисельні – (інколи метричні чи кількісні) вимірювані чи обчислювані кількості. Вимагають вибору шкали. В програмах обробки даних слід передбачити пропущені значення ознак.

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

Серіально-залежні – умовно визначувані, коли попадання деякої ознаки в певний стан робить неможливим визначення іншої.

Типи класифікацій. Чисельні класифікації включають різні числові процеси, з яких вибирають найбільш відповідні. Послідовність вибору показано на рисунку:

Рис.1. Послідовності вибору чисельних класифікацій.

Виключаючі / не виключаючі. Виключаючі – кожен елемент може бути лише в одній підмножині. Не виключаючі – один елемент може бути в різних підмножинах.

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

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

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

Монотетичні і політетичні. Монотетичні – поділ здійснюється на основі однієї ознаки, яка має максимальну інформативність. В політетичній всі ознаки враховуються однаковою мірою.

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

Міри подібності і відмінності. На практиці всі сучасні системи мають справу з мірами відмінності об’єктів. Виділяють два головних класи:

1. -міри, що можуть бути обчислені для двох елементів чи груп елементів до їх об’єднання, якщо відомі їх характеристики.

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

Для стандартного набору програм класифікації на практиці використовують наступні:

1. коефіцієнт кореляції;

2. міри, основані на Евклідовій метриці;

3. міри, основані на Манхеттенській метриці;

4. інформаційні статистики.

Введемо позначення: , – значення та ознак для двох об’єктів , . У випадку бінарних ознак використовують – позначення, де – число ознак, які мають обидва об’єкти; – число ознак, які не зустрічаються ні в одному з об’єктів; – числа ознак, які має лише один з об’єктів.

Коефіцієнт кореляції. Нехай і - значення для -ої з -ознак -го та -го об’єктів, а , - середнє для ознак цих об’єктів.

.

Якщо ознаки представлені дихотомічно, тобто, коли і - рівні “0” чи “1”, то в цьому випадку використовують позначення , а для обчислення коєфіцієнта кореляції використовують формулу -коєфіцієнта Пірсона

. (8)

При цьому порядкові змінні можуть опрацьовуватись так само, як числові. У випадку, коли мають номінальні і числові ознаки, номінальну ознаку з станами розглядають як набір з незалежних бінарних ознак з станами “0” та “1” і вважають дійсними числами.

Евклідова метрика, тобто метрика Мінковського другого порядку визначається співвідношенням

. (9)

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

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

Для номінальних ознак, коли серед об’єктів, з яких знаходиться в стані номінальної ознаки, як показник розсіювання, обчислюють дисперсію за формулою

,

а у випадку повністю бінарних ознак (не стандартизовану) Евклідова відстань обчислюють як

.

Манхеттенська метрика. Ця метрика є частинним випадком метрики Мінковського порядку 1

.

Значення часто ділять на число ознак. Для числових ознак переважно використовують

метрику Брея-Кертиса

,

причому , при цьому використовують стандартизовані додатні дані та

Канберівську метрику

.

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

Інформаційна статистика. В основі цієї статистики використовується Шеннонівське поняття інформації, основане на .

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

. (1)

Нехай інформаційний зміст двох груп і А відповідно рівний та , і нехай обидві ці групи об’єднано в одну групу С з інформаційним змістом . Тоді можна визначити інформаційний виграш від об’єднання двох груп за формулою

. (2)

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

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

. (3).

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

. (4)

Ця величина називається переданою інформацією. Наступний приклад пояснює суть інформаційної статистики.

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

.

Для другої ознаки маємо таку саму величину:

.

Для – третьої:

.

Для – четвертої:

.

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

Агломеративні стратегії об’єднання.

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

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

, (3).

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

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

Конкретні стратегії об’єднання.

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

Стратегія найближчого сусіда. Відстань між двома групами визначається як відстань між двома найближчими об’єктами з цих груп. Її параметри: , , . Сильно стягує простір.

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

Розділяючі стратегії (дивізивні).

Загальна характеристика. Теоретичні переваги дивізивних стратегій над агломеративними полягають в наступному:

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

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

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