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

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

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

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

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

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

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

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

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

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

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

[math]W(C)= \mid D(C) \mid ,H(C)=S(C)/W(C) [/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 } = \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]\mid C_i \mid[/math] количество объектов в [math]i[/math]-ом кластере, [math]k[/math] – количество кластеров, [math]r[/math] – коэффициент отталкивания [math](0 \lt r \le 1)[/math]

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

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

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

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

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

• вычисление нового размера кластера [math]S_{new}(C_i)=S(C_i) \pm \mid(t_n)\mid [/math], где [math]\mid(t_n)\mid[/math] - длина транзакции

• вычисление новой ширины кластера [math]W_{new}(C_i)=\mid D(C_i \cup t_n)|[/math]

• вычисление стоимости [math]\frac{S_{new}(C_i)(\mid C_i \mid \pm 1)}{W_{new}(C_i)^r} - \frac{S(C_i) \mid C_i \mid }{W(C_i)^r}[/math]

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

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

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

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

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

Первая часть алгоритма - инициализация: для каждой транзакции вычисляется кластер, к которому она будет отнесена исходя из максимизации функции стоимости. Для этого вычисляется вспомогательная функция DeltaAdd, которая считает стоимость добавления транзакции к одному из существующих кластеров, либо к пустому. В итоге транзакция помещается в кластер, для которого цена добавления максимальна.

Вторая часть алгоритма - уточняющие итерации: здесь происходит попытка улучшить вычисленные на первом этапе кластеры. В каждой итерации происходит перебор всех транзакций, и для каждой транзакции вычисляется цена удаления ее из текущего кластера и цена добавления в другой кластер. Суммарная стоимость перемещения будет являться суммой стоимостей удаления и добавления. Если максимальная стоимость перемещения данной транзакции в какой-либо больше нуля, то она перемещается в этот кластер.

Вычисления происходят до тех пор, пока за итерацию происходит хотя бы одно перемещение транзакции. Если за итерацию не было произведено ни одного перемещения, то текущее состояние кластеров является устойчивым и оптимальным.

Схема реализации на псевдокоде:

Входные параметры:

-[math]t[/math] - транзакции

-[math]r[/math] - коэффициент отталкивания

Выходной параметр:

-[math]C[/math] кластеры, в начале алгоритма - пустое множество

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

   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 = True
   while move == True:
   move = False
       for t_i in t:
           max = 0
           C_now = t_i.cluster
           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.count+1) / (W_new ^ r) - (C.size * C.count) / (C.wigth ^ r)

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

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

1.6 Последовательная сложность алгоритма

В соответствии с ранее введенным обозначением [math]n[/math] - количество транзакций, [math]m[/math] - длина транзакции(максимальная), [math]k[/math] - количество кластеров.

Основные вычисления восполняются в функции DeltaAdd/DeltaRemove: производится 1 сложение, не более [math]m[/math] сложений/вычитаний, 2 умножения, 2 деления, 2 возведения в степень и 1 сложение - итого [math]m + 8[/math] операций.

Операции выполняются для всех транзаций ([math]n[/math] штук) и для всех кластеров ([math]k[/math] штук). Итого выполняется [math]n*k*(m+8)[/math] операций.

В добавок к этому при добавлении/удалении транзакции к кластеру производится пересчет его характеристик: [math]m+2[/math] операции.

Из того можно сделать вывод, что оценка сложность алгоритма равна [math]O(n*k*m)[/math].

1.9 Входные и выходные данные алгоритма

Входные данные:

[math]n[/math] транзакций длины [math]m[/math] и коэффициент отталкивания [math]r[/math]

Выходные данные:

метки классов для каждой транзакции в соответствии с проведенной кластеризацией(числовая последовательность длины [math]n[/math])

2 Программная реализация алгоритма

2.7 Существующие реализации алгоритма

• http://weka.sourceforge.net/doc.stable/weka/clusterers/CLOPE.html - реализация в open source библиотеке для анализа данных WEKA(Waikato Environment for Knowledge Analysis) на языке Java

3 Литература

[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