Кластеризація категорійних даних - масштабований алгоритм CLOPE, BaseGroup Labs

Введення та основні ідеї

мінімально можливу кількість "сканувань" таблиці бази даних;
робота в обмеженому обсязі оперативної пам'яті комп'ютера;
роботу алгоритму можна перервати із збереженням проміжних результатів, щоб продовжити обчислення пізніше;
алгоритм повинен працювати, коли об'єкти з бази даних можуть вилучатися лише у режимі односпрямованого курсору (тобто режимі навігації по записам).

Алгоритм CLOPE, який ми розглядаємо в даній статті, дуже схожий на LargeItem, але швидше та простіше у програмній реалізації. CLOPE запропоновано у 2002 році групою китайських вчених. При цьому він забезпечує більш високу продуктивність та кращу якість кластеризації в порівнянні з алгоритмом LargeItem та багатьма ієрархічними алгоритмами.

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

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

Для першого та другого варіантів розбиття в кожному кластері розрахуємо кількість входження до нього кожного елемента транзакції, а потім обчислимо висоту (H) та ширину (W) кластера.Наприклад, кластер має входження a:3, b:2, c:2 з H=2 та W=4. Для полегшення розуміння на рис. 1 ці результати показані геометрично у вигляді гістограм.

Якість двох розбиття оцінимо, проаналізувавши їх висоту H і ширину W. Кластери мають однакові гістограми, отже, рівноцінні. Гістограма для кластера містить 4 різні елементи і має площу 8 блоків (H=2.0, H/W=0.5), а кластер – 5 різних елементів з такою самою площею (H=1.6, H/W=0.32). Очевидно, що розбиття (1) краще, оскільки забезпечує більше накладання транзакцій один на одного (відповідно, параметр H там вище).

На основі такої очевидної та простої ідеї геометричних гістограм і працює алгоритм CLOPE (англ. Clustering with sLOPE). Розглянемо його докладніше більш формальному описі.

Алгоритм CLOPE

Нехай є база транзакцій D, що складається з безлічі транзакцій 1, t2, ..., tn. Кожна транзакція є набір об'єктів 1, ..., im & gt;. Багато кластерів 1,…,Ck> є розбиття множини 1,…,tn>, таке, що C1 … Ck=1,…,tn> і $C_i\neq \varnothing \wedge C_i \bigcap C_j = \varnothing$, для 1 2 то розбиття ,> буде краще (градієнт кожного кластера дорівнює 1/3 проти 1/6 у розбиття >).

Узагальнивши сказане вище, запишемо формулу для обчислення глобального критерію – функції вартості Profit(C):

$$Profit (C) = \frac ^k G(C_i)\times\m >

Ci – кількість транзакцій у i-му кластері, k – кількість кластерів, r – позитивне речове число більше 1.

Формальна постановка задачі кластеризації алгоритмом CLOPE має такий вигляд: для заданих D і r знайти розбиття C: Profit(C,r) -> max.

Реалізація алгоритму

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

Реалізація алгоритму вимагає першого проходу таблиці транзакцій для побудови початкового розбиття, що визначається функцією Profit(C,r). Після цього потрібна незначна (1-3) кількість додаткових сканувань таблиці для підвищення якості кластеризації та оптимізації функції вартості. Якщо у поточному проході таблиці змін не відбулося, то алгоритм припиняє свою роботу. Псевдокод алгоритму має такий вигляд.

// Фаза 1 – ініціалізація
Поки що не кінець
прочитати з таблиці наступну транзакцію [t, -];
покласти t в існуючий або новий кластер Ci, який дає максимум Profit(C,r);
записати [t,i] до таблиці (номер кластера);
// Фаза 2 – Ітерація
Повторювати
перейти на початок таблиці;
moved := false;
поки не кінець таблиці
читати [t, i];
покласти t у існуючий або новий кластер Cj, який максимізує Profit(C,r);
якщо Ci<>Cj тоді
записати [t, i];
moved := true;
поки що (not moved).
видалити всі порожні кластери;

Як видно, алгоритм CLOPE масштабується, оскільки здатний працювати в обмеженому обсязі оперативної пам'яті комп'ютера. Під час роботи в RAM зберігається тільки поточна транзакція та невелика кількість інформації по кожному кластеру, яка складається з: кількості транзакцій N, числа унікальних об'єктів (або ширини кластера) W, простий хеш-таблиці для розрахунку Occ(i,C) та значення S площікластерів. Вони називаються кластерними характеристиками (CF – cluster features). Для простоти позначимо їх як властивості кластера C, наприклад, C.Occ[i] означає число входжень об'єкта i кластер C і т.д. Можна вважати, що з зберігання частоти входжень 10 тис. об'єктів у 1 тис. кластерах потрібно близько 40 Мб оперативної пам'яті.

Для завершення реалізації алгоритму нам потрібні ще дві функції, що розраховують приріст Profit(C,r) при додаванні та видаленні транзакції із кластера. Це легко зробити, знаючи величини S,W та N кожного кластера:

функція DeltaAdd(C,t,r): double;
begin
S_new := C.S + t.ItemCount;
W_new: = C.W;
for i:=0 to t.ItemCount–1 do
if (C.Occ [t.items [i]] = 0) then W_new: = W_new + 1;
result := S_new*(C.N+1)/(W_new) r –C.S*C.N/(C.W) r
end;

Тут t.Items[i] – значення i об'єкта транзакції t. Зауважимо, що DeltaAdd(C,t,r) при додаванні t новий кластер дорівнює S/W r , де S і W – площа і ширина кластера, що складається з транзакції t, що додається.

Реалізація функції приросту Profit(C,r) при видаленні транзакції схожа на DeltaAdd(C,t,r), тому опустимо докладний код.

Наступна теорема гарантує коректність використання функції DeltaAdd.

Теорема. Якщо DeltaAdd(Ci,t) є максимум, то переміщення t кластер Ci максимізує Profit(C,r).

Тепер можна оцінити обчислювальну складність алгоритму CLOPE. Нехай середня довжина транзакції дорівнює A, загальна кількість транзакцій N, максимально можливе число кластерів K. Тимчасова складність однієї ітерації дорівнює O(N*K*A), що показує, що швидкість роботи алгоритму зростає лінійно зі зростанням кластерів та розміру таблиці. Це робить алгоритм швидким та ефективним на великих обсягах.

Завдання прогрибах

Загальна кількість унікальних характеристик об'єктів 116. 2480 записів мають пропущені значення в одному атрибуті.

Якщо такий набір даних подати в описаному вище нормалізованому вигляді, то вийде 8124 транзакції, з яких 2408 будуть довжиною 21, а решта - 22 елементи (пропущені значення ігноруються). І тепер можна застосувати алгоритм CLOPE. Результат роботи CLOPE при r=2.6 для задачі про гриби після 1-ої ітерації (фаза ініціалізації) представлений на рис. 3. У цьому критерієм якості роботи алгоритму є кількість " брудних " кластерів, тобто. таких, у яких є як їстівні (e), і неїстівні (p) гриби. Що менше таких кластерів, то краще. З крос-таблиці на рис. 3 видно, що після 1-ой ітерації залишився лише 1 " брудний " кластер №18. Потрібно ще пару-трійку сканувань бази даних для отримання фінальної кластеризації. Очевидно, що кластер 12 зникне.

Області застосування CLOPE

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

На завершення підкреслимо переваги алгоритму CLOPE: