еризації
Велике достоїнство кластерного аналізу в тому, що він дозволяє здійснювати розбиття об'єктів не по одному параметру, а по цілому набору ознак. Завдання кластеризації полягає в розділенні досліджуваної безлічі об'єктів на групи схожих об'єктів, званих кластерами.
Формально задача кластеризації описується таким чином.
Дано безліч об'єктів даних, кожен з яких представлений набором атрибутів. Потрібно побудувати безліч кластерів і відображення безлічі на безліч, т. Е.. Відображення задає модель даних, що є вирішенням завдання. Якість рішення задачі визначається кількістю вірно класифікованих об'єктів даних.
Безліч визначимо наступним чином:
, (6)
де - досліджуваний об'єкт.
Кожен з об'єктів характеризується набором параметрів:
(7)
Кожна змінна може приймати значення з деякого безлічі:
. (8)
Завдання кластеризації полягає в побудові множини:
. (9)
Тут - кластер, що містить схожі один на одного об'єкти з безлічі:
, (10)
де - величина, що визначає міру близькості для включення об'єктів в один кластер;
- міра близькості між об'єктами, звана відстанню.
Невід'ємне значення називається відстанню між елементами, якщо виконуються наступні умови:
., для всіх.
., тоді і тільки тоді, коли.
..
..
Якщо расстояніеменьше деякого значення, то говорять, що елементи близькі і поміщаються в один кластер. В іншому випадку говорять, що елементи відмінні один від одного і їх поміщають в різні кластери.
Більшість популярних алгоритмів, що вирішують завдання кластеризації, використовують як формат вхідних даних матрицю відмінності Рядки і стовпці матриці відповідають елементам множини. Елементами матриці є значення в рядку і стовпці. Очевидно, що на головній діагоналі значення будуть дорівнюють нулю:
(12)
Відстані між об'єктами припускають їх представлення у вигляді точок мірного простору. У цьому випадку можуть бути використані різні відстані, наприклад:
1. Евклідова відстань - Іноді може виникнути бажання звести в квадрат стандартне евклідова відстань, щоб надати великі ваги більш віддаленим один від одного об'єктам. Це відстань обчислюється таким чином:
(13)
2. Відстань за Хеммінг є просто середнім різниць по координатах. Обчислюється за формулою:
(14)
3. Відстань Чебишева може виявитися корисним, коли бажають визначити два об'єкти як різні raquo ;, якщо вони розрізняються за якої-небудь однієї координаті (яким-небудь одним виміром). Обчислюється за формулою:
(15)
4. Відстань Махаланобіса обчислюється за формулою:
16)
5. Пікове відстань передбачає незалежність між випадковими змінними, що говорить про відстані в ортогональному просторі. Але в практичних додатках ці змінні не є незалежними.
(17)
1.4.2.3 Завдання пошуку асоціативних правил
Позначимо об'єкти, що становлять досліджувані набори (itemsets), наступним безліччю:
(11)
де - об'єкти, що входять в аналізовані набори;- Загальна кількість об'єктів.
Набори об'єктів з безлічі, що зберігаються в БД і піддаються аналізу, називаються транзакціями. Опишемо транзакцію як підмножина множини:
. (12)
Набір транзакцій, інформація про які доступна для аналізу, позначимо наступним безліччю:
, (13)
де - кількість доступних для аналізу транзакцій.
Безліч транзакцій, в які входить об'єкт, позначимо наступним чином:
. (14)
Деякий довільний набір об'єктів (itemset) позначимо наступним чином:
. (15)
Безліч транзакцій, в які входить набір, позначимо наступним чином:
. (16)
Відношення кількості транзакцій, в яке входить набір, до загальної кількості транзакцій називається підтримкою (support) набору і позначається:
. (17)
При пошуку аналітик може вказати мінімальне значення підтримки цікавлять його наборів. Набір називається частим (large itemset), якщо значення його підтримки більше мінімального значення підтримки, заданого користувачем:
. 18)
Таким чином, при пошуку асоціативних правил потрібно знайти безліч всіх частих наборів:
. (19)
1.4.3 Огляд алгоритмів інтелектуального аналізу даних
Існує велика кількість методів і алгоритмі...
