Клъстериране на категорични данни, мащабируем CLOPE алгоритъм, BaseGroup Labs

Въведение и основни идеи

минималния възможен брой "сканирания" на таблица от база данни;
работа в ограничено количество RAM на компютъра;
алгоритъмът може да бъде прекъснат, докато записвате междинни резултати, за да продължите изчисленията по-късно;
алгоритъмът трябва да работи, когато обекти от базата данни могат да бъдат извлечени само в режим на еднопосочен курсор (т.е. в режим на навигация на запис).

Алгоритъмът CLOPE, който ще разгледаме в тази статия, е много подобен на LargeItem, но по-бърз и лесен за внедряване в софтуера. CLOPE е предложен през 2002 г. от група китайски учени. В същото време той осигурява по-висока производителност и по-добро качество на групиране в сравнение с алгоритъма LargeItem и много йерархични алгоритми.

Терминът транзакция тук се отнася до някакъв произволен набор от обекти, било то списък с ключови думи на статия, стоки, закупени в супермаркет, набор от симптоми на пациент, характерни фрагменти от изображение и т.н. Задачата на клъстерирането на транзакционните данни е да се получи такова разделяне на целия набор от транзакции, така че подобни транзакции да попаднат в един и същи клъстер, а различни - в различни клъстери.

Алгоритъмът за клъстериране CLOPE се основава на идеята за максимизиране на функцията на глобалните разходи, което увеличава близостта на транзакциите в клъстери чрез увеличаване на параметъра на хистограмата на клъстера. Помислете за прост пример от 5 транзакции: . Представете си, че искаме да сравним следните две групи:

За първата и втората опция за разделяне във всеки клъстер ние изчисляваме броя на появяванията на всеки елемент на транзакция в него и след това изчисляваме височината (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>. Наборът от клъстери 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):

$$ Печалба (C) = \frac ^k G(C_i)\times\m >

Ci е броят транзакции в i-тия клъстер, k е броят на клъстерите, r е положително реално число, по-голямо от 1.

Формалното изложение на проблема с клъстерирането чрез алгоритъма CLOPE е както следва: за дадени D и r намерете дял C: Profit(C,r) -> макс.

Реализация на алгоритъма

Да предположим, че транзакциите се съхраняват в таблица на база данни. Най-доброторешението се търси по време на последователно итеративно изброяване на записите в базата данни. Тъй като критерият за оптимизация е глобален по природа, базиран само на изчисляването на H и W, производителността и скоростта на алгоритъма ще бъдат значително по-високи, отколкото при сравняване на транзакции по двойки.

Изпълнението на алгоритъма изисква първото преминаване през таблицата на транзакциите, за да се изгради първоначалното разделение, определено от функцията Profit(C,r). След това са необходими малък (1-3) брой допълнителни сканирания на таблици, за да се подобри качеството на групирането и да се оптимизира разходната функция. Ако не са настъпили промени в текущото преминаване през таблицата, тогава алгоритъмът спира работата си. Псевдокодът на алгоритъма е както следва.

// Фаза 1 - инициализация
До края
прочете следващата транзакция от таблицата [t, -];
постави t в съществуващия или нов клъстер Ci, което дава максимална печалба (C,r);
запишете [t,i] в таблицата (номер на клъстер);
// Фаза 2 - Итерация
Повторете
отидете в началото на таблицата;
преместен := невярно;
до края на масата
прочетете [t,i];
постави t в съществуващ или нов клъстер Cj, който максимизира печалбата(C,r);
ако Ci>Cj тогава
напишете [t,i];
преместен := вярно;
още (не е преместен).
изтрийте всички празни клъстери;

Както можете да видите, алгоритъмът CLOPE е мащабируем, тъй като може да работи в ограничено количество компютърна RAM. По време на работа само текущата транзакция и малко количество информация за всеки клъстер се съхранява в RAM, което се състои от: броя на транзакциите N, броя на уникалните обекти (или ширината на клъстера) W, проста хеш-таблица за изчисляване на Occ(i,C) и стойността на площта Sклъстер. Те се наричат клъстерни характеристики (CF). За простота нека ги обозначим като свойства на клъстер C, например C.Occ[i] означава броя на срещанията на обект i в клъстер C и т.н. Може да се изчисли, че за съхраняване на честотата на срещане на 10 000 обекта в 1000 клъстера са необходими около 40 MB RAM.

За да завършим внедряването на алгоритъма, имаме нужда от още две функции, които изчисляват увеличението на Profit(C,r) при добавяне и премахване на транзакция от клъстера. Това е лесно да се направи, като се знаят стойностите S, W и N на всеки клъстер:

функция DeltaAdd(C,t,r): двойно;
започвам
S_new := C.S + t.ItemCount;
W_ново := C.W;
за i:=0 до t.ItemCount–1 направи
if (C.Occ[t.items[i]]=0) then W_new := W_new + 1;
резултат := S_new*(C.N+1)/(W_new) r –C.S*C.N/(C.W) r
край;

Тук 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 максимизира печалбата(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

Като цяло клъстерирането на транзакционни данни има много общо с анализа на асоциациите. И двете технологии за извличане на данни разкриват скрити зависимости в наборите от данни. Но има и разлики. От една страна, клъстерирането дава общ поглед върху набора от данни, докато асоциативният анализ открива специфични връзки между атрибутите. От друга страна, правилата за асоцииране могат да се използват веднага, докато клъстерирането най-често се използва като първи етап на анализ.

В заключение подчертаваме предимствата на алгоритъма CLOPE: