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

 

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

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

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

 

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

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

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). Інформація, що відповідає першій ознаці рівна

.

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

.

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

.

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

.

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