єдине ціле
У випадках, коли для угруповання використовуються значення одного-двох параметрів, завдання кластеризації може бути відносно швидко вирішена вручну або, наприклад, звичайними засобами роботи з реляційними базами даних. Коли параметрів багато, виникає потреба в автоматизації процесу виявлення кластерів.
Надаваний аналітичними службами SQL Server 2008 алгоритм кластеризації (Microsoft Clustering), використовує ітераційні методи для угруповання варіантів з такими характеристиками в кластери. Алгоритм спочатку визначає наявні зв'язки в наборі даних і на основі цієї інформації формує кластери.
Ідею можна проілюструвати за допомогою діаграм на малюнку 21. На першому етапі (малюнок 21, а) є безліч варіантів, далі (малюнок 21, b) йде ітераційний процес формування кластерів, і в підсумку отриманий відносно невеликий набір кластерів, яким можна поставити ідентифікатори і продовжити аналіз.
Рис. 21. Перехід від окремих варіантів до кластерів
Microsoft Clustering містить реалізацію двох алгоритмів кластеризації. Перший з них, алгоритм середніх (англ. Means), реалізує, так звану жорстку кластеризацию. Це означає, що варіант може належати тільки одному кластеру. Ідея алгоритму полягає в наступному:
. Вибирається число кластерів.
. З вихідного безлічі даних випадковим чином вибираються записів, які будуть служити початковими центрами кластерів.
. Для кожного запису вихідної вибірки визначається найближчий до неї центр кластера. При цьому записи, «притягнуті» певним центром, утворюють початкові кластери.
. Обчислюються центроїди - центри тяжкості кластерів. Кожен центроид - це вектор, елементи якого являють собою середні значення ознак, обчислені за всіма записами кластера. Центр кластера зміщується в його центроид.
Кроки 3 і 4 итеративно повторюються, при цьому може відбуватися зміна меж кластерів і зміщення їх центрів. У результаті мінімізується відстань між елементами всередині кластерів. Зупинка алгоритму виробляється тоді, коли кордони кластерів і розташування центроїдів не перестануть змінюватися від ітерації до ітерації, т. Е. На кожній ітерації в кожному кластері залишатиметься один і той же набір записів.
Другий метод, реалізований у Microsoft Clustering, це максимізація очікувань (англ. Expectation-maximization, EM). Він відноситься до методів м'якою кластеризації, т. Тобто. Варіант в цьому випадку належить до декількох кластерам, а для всіх можливих поєднань варіантів з кластерами обчислюються ймовірності.
При кластеризації методом EM алгоритм итеративно уточнює початкову модель кластеризації, підганяючи її до даних, і визначає ймовірність приналежності точки даних кластеру. Цей алгоритм закінчує роботу, коли ймовірна модель відповідає даним. Функція, використовувана для встановлення відповідності, - логарифм функції правдоподібності даних, що вводяться в модель.
Якщо в процесі формуються порожні кластери або кількість елементів в одному або декількох кластерах виявляється менше заданого мінімального значення, нечисленні кластери заповнюються повторно за допомогою нових точок і алгоритм EM запускається знову. Результати роботи алгоритму максимізації очікування є імовірнісними: кожна точка даних належить усім кластерам, але з різною ймовірністю. Оскільки метод допускає перекриття кластерів, сума елементів всіх кластерів може перевищувати число елементів навчального набору.
. 4.3.6 Алгоритм взаємозв'язків
Алгоритм взаємозв'язків або асоціативних правил (Association Rules) дозволяє виявити часто зустрічаються поєднання елементів даних і використовувати виявлені закономірності для побудови прогнозу.
Для виявлення часто зустрічаються наборів об'єктів може використовуватися алгоритм Apriori, реалізація якого лежить в основі алгоритму Microsoft Association Rules, що використовується в SQL Server 2008. Алгоритм Apriori послідовно виділяє часто зустрічаються одно-, дво-, ..., n-елементні набори. На му етапі виділяються елементні набори. Для цього спочатку виконується формування наборів-кандидатів, після чого для них розраховується підтримка.
Підтримка (від англ. support) використовується для вимірювання популярності набору елементів. Наприклад, підтримка набору елементів - загальна кількість транзакцій, які містять як, так і.
Щоб кількісно охарактеризувати правило, використовується ймовірність (англ. probability). Цей же показник іноді називається вірогідністю.
Probability. (26)
Імовірність для набору розраховується як відношення числа транзакцій, що містять цей набір, до загального числа транзакцій.
Щоб оцінити взаємну залежність елементів використовується важливість (англ. importance) або показник інтересу.
Importance (27) <...
