Участник:Андрей Туманов/Алгоритм кластеризации категориальных данных CLOPE

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

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

Алгоритм CLOPE (Clustering with sLOPE) неирархический метод кластеризации, предназначенный для кластеризации огромных наборов категориальных данных. К достоинствам алгоритма относятся высокие масштабируемость и скорость работы и качество кластеризации, что достигается использованием глобального критерия оптимизации на основе максимизации градиента высоты гистограммы кластера. Отличается простотой программной реализации.

Во время работы алгоритм хранит в памяти небольшое количество информации по каждому кластеру и требует минимальное число сканирований набора данных. CLOPE автоматически подбирает количество кластеров, причем это регулируется одним единственным параметром - коэффициентом отталкивания [math]\displaystyle{ r }[/math]. При этом он обеспечивает более высокую производительность и лучшее качество кластеризации в сравнении с многими иерархическими алгоритмами.

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

Пусть имеется база транзакций [math]\displaystyle{ D }[/math], состоящая из множества транзакций [math]\displaystyle{ \{t_1,t_2,...,t_n\} }[/math]. Каждая транзакция есть набор объектов [math]\displaystyle{ \{i_1,...,i_m\} }[/math]. Множество кластеров [math]\displaystyle{ \{C_1,...,C_k\} }[/math] есть разбиение множества [math]\displaystyle{ \{t_1,...,t_n\} }[/math], такое, что [math]\displaystyle{ C_1 \cup \dots \cup C_k=\{t_1,...,t_n\} }[/math] и [math]\displaystyle{ C_i \ne \empty }[/math] и [math]\displaystyle{ C_i \cap C_j = \empty }[/math], для [math]\displaystyle{ i \ge 1, k \ge j }[/math]. Каждый элемент [math]\displaystyle{ C_i }[/math] называется кластером, а [math]\displaystyle{ n, m, k }[/math] – количество транзакций, количество объектов в базе транзакций и число кластеров соответственно.

Каждый кластер [math]\displaystyle{ C }[/math] имеет следующие характеристики:

[math]\displaystyle{ D(C) }[/math] – множество уникальных объектов;

[math]\displaystyle{ Occ(i,C) }[/math] – количество вхождений (частота) объекта [math]\displaystyle{ i }[/math] в кластер [math]\displaystyle{ C }[/math];

[math]\displaystyle{ S(C)= \sum_{i \in D(C)} Occ(i,C)= \sum_{t_i \in C} \mid t_i \mid , }[/math]

[math]\displaystyle{ W(C)= \mid D(C) \mid ,H(C)=S(C)/W(C) }[/math]

Функция стоимости:

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

где [math]\displaystyle{ \mid C_i \mid }[/math] количество объектов в [math]\displaystyle{ i }[/math]-ом кластере, [math]\displaystyle{ k }[/math] – количество кластеров, [math]\displaystyle{ r }[/math] – коэффициент отталкивания [math]\displaystyle{ (0 \lt r \le 1) }[/math]

С помощью параметра [math]\displaystyle{ r }[/math] регулируется уровень сходства транзакций внутри кластера, и, как следствие, финальное количество кластеров. Этот коэффициент подбирается пользователем. Чем больше [math]\displaystyle{ r }[/math], тем ниже уровень сходства и тем больше кластеров будет сгенерировано.

Постановка задачи кластеризации алгоритмом CLOPE выглядит следующим образом:

для заданных [math]\displaystyle{ D }[/math] и [math]\displaystyle{ r }[/math] найти разбиение [math]\displaystyle{ C }[/math] такое, что: [math]\displaystyle{ Profit(C) \longrightarrow max }[/math].

Вычислительное ядро алгоритма

Вычислительное ядро алгоритма состоит в вычислении на каждой итерации функции стоимости:

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

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

Алгоритм состоит из следующих этапов:

1. Инициализация. На этом этапе происходит первый проход по таблице с транзакциями для построения начального разбиения, для каждой транзакции определяется кластер исходя из максимизации стоимости.

2. Итерация. На данном этапе для каждой транзакции проводится попытка перемещения в другой кластер для максимизации функции стоимости.

Схема реализации последовательного алгоритма

Инициализация:

   for t_i in t:
   max = 0
       for C_j in C:
           if DeltaAdd(C_j,t_i,r) > max:
               max = DeltaAdd(C_j,t_i,r)
               C_best = C_j
   put t_i in C_best

Итерации:

   move = False
   while move == False:
       for t_i in t:
           max = 0
           C_now = t_i.C
           removeCost = DeltaRemove(C_now,t_i,r)
           for C_j in C:
               if DeltaAdd(C_j,t_i,r) + removeCost > max:
                   max = DeltaAdd(C_j,t_i,r) + removeCost
                   C_best = C_j
       if max > 0
           del t_i from C_now
           put t_i in C_best
           move = True

Вспомогательная функция DeltaAdd:

   function DeltaAdd(C,t,r)
       S_new=C.size + t.itemCount
       W_new=C.wigth
       for item in t_i:
           if C_j.occ(item) = 0
               W_new = W_new + 1
       return S_new * (C.N+1) / (W_new ^ r) - (C.S * C.N) / (C.W ^ r)

Вспомогательная функция DeltaRemove:

   function DeltaRemove(C,t,r)
       S_new=C.size - t.itemCount
       W_new=C.wigth
       for item in t_i:
           if C_j.occ(item) = 1
               W_new = W_new - 1
       return S_new * (C.N-1) / (W_new ^ r) - (C.S * C.N) / (C.W ^ r)

Литература

[1] Yang, Y., Guan, H., You. J. CLOPE: A fast and Effective Clustering Algorithm for Transactional Data In Proc. of SIGKDD’02, July 23-26, 2002, Edmonton, Alberta, Canada.

[2] Нейский И.М. Классификация и сравнение методов кластеризации

[3] Павлин Н. Кластеризация категорийных данных: масштабируемый алгоритм CLOPE, https://basegroup.ru/community/articles/clope

[4] Філонова О.О., Вороной С.М.. Алгоритм кластеризации поискових профилей пользователей для системы персонализации сайта, http://masters.donntu.org/2014/fknt/filonova/library/article2.htm