Участник:Ilya365365/Алгоритм кластеризации категориальных данных

1 Свойства и структура алгоритма CLOPE

1.1 Общее описание алгоритма CLOPE

Алгоритм CLOPE решает задачу кластеризации категориальных транзакционных данных. Алгоритм основан на эвристическом методе повышения близости транзакций в кластерах при помощи оптимизации параметров кластерной гистограммы. Авторы (Yiling Yang Xudong Guan Jinyuan You ) предложили эффективный, масштабируемый алгоритм, не требующий хранения обучающей выборки в оперативной памяти.

Здесь и далее под категориальными данными понимаются качественные характеристики объектов, измеренные в шкале наименований, то есть при сравнении категориальных данных указывается только, одинаковы или нет объекты относительно данного признака.

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

В основе алгоритма кластеризации CLOPE лежит идея максимизации глобальной функции стоимости, которая повышает близость транзакций в кластерах при помощи увеличения параметра кластерной гистограммы. Для примера рассмотрим выборку из пяти списков покупок: {(apple, banana), (apple, banana, cake), (apple, cake, dish), (dish, egg), (dish, egg, fish)}, или сокращённо {ab, abc, acd, de, def}. Каждый список - транзакция. Каждый купленный предмет является объектом. Представим себе, что мы хотим сравнить между собой следующие два разбиения на кластеры:

1: {{ab, abc, acd}, {de, def}}

2: {{ab, abc}, {acd, de, def}}.

Для первого и второго вариантов разбиения в каждом кластере рассчитаем количество вхождений в него каждого элемента транзакции, а затем вычислим ширину [math]W(c_i)[/math] (количество уникальных объектов кластера), общее число объектов в кластере [math]S(C_i)[/math] и высоту [math]H(C_i) = \frac{S(C_i)}{W(C_i)}[/math]. Например, кластер {ab, abc, acd} имеет вхождения a:3, b:2, c:2, d:1 с H=2 и W=4.

Очевидно, что чем меньше ширина и чем больше высота кластера, тем больше сходство в ходящих в него транзакций. Авторы алгоритма формализовали эту идею, введя следующий функционал: [math] Profit(C)=\frac{\sum^{k}_{i=1} G(C_i) \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid} [/math]  =  [math]\frac{\sum^{k}_{i=1} \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid} {M} [/math]

Здесь [math]k[/math] - количество кластеров, [math]C_i[/math], [math]\mid C_i \mid[/math] - число транзакций в кластере [math] C_i [/math], M - число транзакций в выборке, [math]G(C_i) = \frac{S(C_i)}{W^r(C_i)}[/math], [math]r[/math] - коэффициент отталкивания. Чем больше [math]r[/math], тем больше кластеров будет сгенерировано.

1.2 Математическое описание алгоритма CLOPE

1.2.1 Постановка задачи

Даны конечное множество объектов [math]O = \{o_1, \dots, o_N\}[/math], выборка транзакций [math]D = \{t_1, \dots, t_M\}[/math] и [math]r[/math] - коэффициент отталкивания. Транзакция - вектор произвольной длины, каждая компонента которого является объектом из [math]O[/math]. Требуется найти кластеризацию [math]C[/math] - конечное покрытие [math]D[/math], максимизирующее функцию

[math] Profit(C)=\frac{\sum^{k}_{i=1} G(C_i) \times \mid C_i \mid} {\sum^{k}_{i=1} \mid C_i \mid} [/math]  =  [math]\frac{\sum^{k}_{i=1} \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid} {M} [/math]

1.2.2 Оптимизация функционала

Авторы алгоритма CLOPE предложили жадную стратегию оптимизации [math]Profit[/math].

Введём функции [math]Delete(C_i, t_j, r)[/math], вычисляющую изменение функции [math]Profit(C)[/math] при удалении транзакции [math]t_j[/math] из кластера [math]C_i[/math]; [math]Add(C_i, t_j, r)[/math], вычисляющую изменение функции [math]Profit(C)[/math] при добавлении транзакции [math]t_j[/math] в кластер [math]C_i[/math]; [math]DeltaAdd(C_i, t_j, r)[/math], вычисляющую изменение функции [math]Profit(C)[/math] при перемещении транзакции [math]t_j[/math] из кластера [math]C_l[/math] в кластер [math]C_i[/math]. Ширину [math]W[/math] пустого кластера примем равной 1.

[math]Delete(C_i, t_j, r) = G(\{C_i \backslash t_j\})\times\mid C_i \backslash \{t_j\}\mid - G(C_i)\times\mid C_i\mid [/math]  =  [math] \frac {S(C_i) - size(t_j)}{{W(C_i \backslash \{t_j\})}^r} \times (\mid C_i \mid - 1) - \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid [/math]

[math]Add(C_i, t_j, r) = G(C_i \cup \{t_j\}) \times \mid C_i \cup \{t_j\} \mid - G(C_i)\times\mid C_i\mid[/math]  =  [math] \frac {S(C_i) + size(t_j)}{{W(C_i \cup \{t_j\})}^r} \times (\mid C_i \mid + 1) - \frac {S(C_i)}{{W(C_i)}^r} \times \mid C_i \mid [/math]

[math]DeltaAdd(C_i, t_j, r) = Add(C_i, t_j, r) + Delete(C_l, t_j, r)[/math], где [math]C_l[/math] - кластер, к которому отнесена [math]t_j[/math]

На этапе инициализации алгоритма выполняется проход по выборке, во время которого каждая транзакция помещается в существующий или пустой кластер таким образом, чтобы максимизировать [math]Profit(C)[/math]. Далее происходят уточняющие проходы по выборке. Во время уточняющего прохода каждая транзакция перемещается в существующий или пустой кластер таким образом, чтобы максимизировать [math]Profit(C)[/math]. Если во время уточняющего прохода не было перемещено ни одной транзакции, алгоритм останавливается.

Авторы CLOPE доказали следующую теорему:

Если [math]C_i = argmax_{C_k \in C}DeltaAdd(C_k,t, r)[/math], то перемещение [math]t[/math] в кластер [math]C_i[/math] даст наибольший прирост функции [math]Profit(C)[/math].

Доказательство: Рассмотрим некоторую кластеризацию [math]C[/math] и кластеризацию [math]C^{new}[/math], полученную из [math]C[/math] перемещением [math]t[/math] в кластер [math]C_i[/math]. Тогда [math]Profit(C^{new}) - Profit(C) = \frac{Add(C_i, t, r) + Delete(C_l, t, r)}{M} [/math]  =  [math]\frac{DeltaAdd(C_i, t, r)}{M}[/math]

Следствие 1: Алгоритм CLOPE сходится при любых [math]O[/math], [math]D[/math] и [math]r[/math].

Доказательство следствия 1: Так как [math]DeltaAdd(C_l, t, r)[/math] = 0 ([math]C_l[/math] - кластер, к которому отнесена [math]t[/math]), любое перемещение транзакции увеличивает [math]Profit(C)[/math], следовательно, алгоритм CLOPE сходится при любых [math]O[/math], [math]D[/math] и [math]r[/math].