Участник: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]

[math]max_{C_k \in C} Profit(C^{new}) - Profit(C) [/math]  =  [math] max_{C_k \in C} \frac{DeltaAdd(C_k, t, r)}{M} [/math]  =  [math] max_{C_k \in C} DeltaAdd(C_k,t, r)[/math]

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

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

1.3 Вычислительное ядро

Из доказанных выше утверждений следует, что для нахождения оптимального разбиения не нужно вычислять функцию [math]Profit(C)[/math]. Достаточно уметь эффективно вычислять функцию [math]DeltaAdd(C_i, t_j, r) = \frac {S(C_l) - size(t_j)}{{W(C_l \backslash \{t_j\})}^r} \times (\mid C_l \mid - 1) - \frac {S(C_l)}{{W(C_l)}^r} \times \mid C_l \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]Delete[/math] и [math]Add[/math]

Самая сложная операция при реализации вычислительного ядра - вычисление ширины кластера. Так как для большинства известных задач кластеризации транзакционных данных средняя длина транзакции [math]A = \frac{\sum_{i = 1}^{M}t_i}{M} \lt \lt \mid O \mid[/math], авторы алгоритма рекомендуют хранить информацию об объектах кластера в ассоциативном массиве (словаре), ключом которого является номер объекта, а данными - число вхождений соответствующего объекта в кластер. При реализации словаря авторы CLOPE рекомендуют использовать хэш-таблицу. Таким образом при добавлении или удалении транзакции [math]t[/math] требуется [math]size(t)[/math] раз обратиться к соответствующему словарю для поиска элементов и, в худшем случае, добавить или удалить [math]size(t)[/math] элементов. Эффективная реализация ассоциативного массива является важнейшей и самой частью реализации алгоритма CLOPE.

1.4 Макроструктура алгоритма

1.4.1 Класс Transaction

Класс Transaction - структура данных, описывающая транзакцию. Содержит следующие поля:

• size - количество объектов в транзакции
• objects - массив с номерами объектов
• id - уникальный номер транзакции. Равен 0, если транзакция не отнесена к какому-либо кластеру
• cluster_id - номер кластера, в котором находится транзакция.

Класс Transaction имеет метод add(Cluster)

   add(Cluster):
       cluster_id = Cluster.id;

1.4.2 Класс Cluster

Класс Cluster - структура данных, описывающая кластер. Содержит следующие поля:

• repultion - коэффициент отталкиваня r. Входной параметр CLOPE.
• transaction_map - хэш-таблица, хранящая номера входящих в кластер транзакций
• object_map - словарь, хранящий количество вхождений объектов.
• transaction_quantity - число транзакций, входящих в кластер
• power - число объектов в кластере
• width - ширина кластера (число уникальных объектов)
• profit_summand - вклад кластера в функционал profit
• id - уникальный номер кластера

Класс Cluster содержит следующие методы:

• calculate_profit_summand(power, width, transaction_quantity) вычисляет вклад кластера с заданными параметрами в функционал Profit

    calculate_profit_summand(power, width, transaction_quantity)
        return power * transaction_quantity / width^self.repultion;

• estimate_profit_summand_after_addition(transaction) - оценивает вклад кластера в функционал Profit после добавления транзакции

   estimate_profit_summand_after_addition(transaction)
       new_width = width;
        for each object in transaction:
               if (self.object_map.get(object) == NULL):
                   new_width += 1;
       new_profit = calculate_profit_summand(self.power + transaction.size, 
                                             new_width, 
                                             transaction_quantity + 1); 
        return new_profit;
              

• estimate_profit_summand_after_dellition(transaction) - оценивает вклад кластера в функционал Profit после удаления транзакции

   estimate_profit_summand_after_dellition(transaction)
       new_width = width;
        for each object in transaction:
               if (self.object_map.get(object) == 1) new_width -= 1;
       new_profit = calculate_profit_summand(self.power - transaction.size, 
                                             new_width, 
                                             transaction_quantity - 1); 
        return new_profit;

• add_transaction(transaction) - добавление транзакции

   add_transaction(transaction)
       self.transaction_map.push(transaction.id);
       self.power += transaction.size;
       self.transaction_quantity += 1;
       for each object in transaction.objects:
               if (self.object_map.get(object) == NULL):
                   self.object_map.push((object,1));
               else:
                   self.object_map[object] += 1;
       self.width = self.object_map.size();
       self.profit_summand = calculate_profit_summand(self.power,
                                                      self.width,
                                        self.transaction_quantity);

• delete_transaction(transaction) - удаление транзакции

   delete_transaction(transaction)
       self.transaction_map.pop(transaction.id);
       self.power -= transaction.size;
       self.transaction_quantity -= 1;
       for each object in transaction.objects:
               if (self.object_map.get(object) == 1):
                   self.object_map.pop((object,1));
               else:
                   self.object_map[object] -= 1;
       self.width = self.object_map.size();
       self.profit_summand = calculate_profit_summand(self.power,
                                                      self.width, 
                                        self.transaction_quantity);

Также класс Cluster содержит два конструктора:

• Cluster(id) - конструктор, создающий пустой кластер.
• Cluster(id, transaction) - конструктор, создающий кластер с единственной транзакцией.

1.4.3 Класс CLOPE

Класс CLOPE структура данных, обеспечивающая работу алгоритма. Класс CLOPE содержит следующие поля:

• cluster_map - ассоциативный массив, содержащий информацию о кластерах. Ключ - номер кластера. Кластер с индексом 0 является пустым.
• cluster_quantity - переменная, хранящая количество кластеров
• sample_size - переменная хранящая, количество транзакций.

В классе CLOPE необходимо реализовать следующие методы:

• get_next_transaction() - получение следующей транзакции из файла. Если достигнут конец файла, считывается первая транзакция.
• get_best_move(transaction) - найти кластер, в который следует переместить транзакцию

   get_best_move(transaction)
       if transaction.cluster_id != 0 : //транзакция лежит в кластере
           old_cluster = self.cluster_map[transaction.cluster_id];
           delete_change = old_cluster.profit_summand - 
                           old_cluster.estimate_profit_summand_after_dellition(transaction);
       else: //инициализация
           delete_change = 0;