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

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

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

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

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

Пусть имеется база транзакций [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], при котором

1. [math]\displaystyle{ C_1 \cup \ldots \cup C_k = \{t_1,...,t_n\} }[/math]
2. [math]\displaystyle{ C_i }[/math] [math]\displaystyle{ \ne }[/math] [math]\displaystyle{ \empty }[/math] [math]\displaystyle{ \land }[/math] [math]\displaystyle{ C_i }[/math] [math]\displaystyle{ \cap }[/math] [math]\displaystyle{ C_j= \empty }[/math], для [math]\displaystyle{ 1 }[/math] [math]\displaystyle{ \le }[/math] [math]\displaystyle{ i }[/math], [math]\displaystyle{ j }[/math] [math]\displaystyle{ \le }[/math] [math]\displaystyle{ k }[/math].

Для каждого кластера [math]\displaystyle{ C }[/math] определяются следующие характеристики :

[math]\displaystyle{ D(C) }[/math] — множество уникальных объектов в данном кластере [math]\displaystyle{ 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{ C }[/math],

[math]\displaystyle{ W(C) }[/math]  =  [math]\displaystyle{ \mid }[/math] [math]\displaystyle{ D(C) }[/math] [math]\displaystyle{ \mid }[/math] — ширина кластера,

[math]\displaystyle{ H(C) }[/math]  =  [math]\displaystyle{ \frac{S(C)}{W(C)} }[/math] — высота кластера.

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

[math]\displaystyle{ Profit(C) = \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{ r }[/math], тем ниже уровень сходства и тем больше кластеров будет сгенерировано.

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

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

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

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

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

• [math]\displaystyle{ S_{new}(C_i)=S(C_i) \pm \mid(t_n)\mid }[/math],

• [math]\displaystyle{ W_{new}(C_i)=\mid D(C_i \cup t_n)| }[/math]

• вычисление стоимости добавления(удаления)[math]\displaystyle{ \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. Инициализация. Последовательно для каждой транзакции считается цена добавления ко всем существующим или новому пустому кластерам. В результате, транзакция занимает место в том кластере, для которого цена добавления максимальна(если это пустой кластер, то необходимо его создать). В конечном итоге все транзакции будут находиться в кластерах.
2. Итерации. Этот этап нужен для возможного улучшения результата, полученного на первом шаге. При этом для каждой транзакции вычисляется стоимость удаления из кластера, в котором она находится, и цена добавления в каждый существующий или пустой кластер. Необходимо посчитать и найти максимальную суммарную стоимость удаления и добавления транзакции к каждому кластеру. Если максимальная стоимость положительная, то данная транзакция перемещается в этот кластер. Это выполняется для каждой транзакции. Итерация повторяется до тех пор, пока результат улучшается. Как только за итерацию ничего не меняется, алгоритм заканчивает работу.

Описание реализации алгоритма на псевдокоде

Вход:

    [math]\displaystyle{ t }[/math] - транзакции,
    [math]\displaystyle{ r }[/math] - коэффициент отталкивания

Выход:

    [math]\displaystyle{ C }[/math] - множество кластеров

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

  while  не конец do
      read следующую транзакцию [math]\displaystyle{ t }[/math]
      определить существующий кластер или пустой [math]\displaystyle{ C_j }[/math], который дает максимум функции стоимости [math]\displaystyle{ Profit }[/math]
      write транзакцию в кластер [math]\displaystyle{ C_j }[/math]
  end while 

итерация:

    repeat
       в начало таблицы транзакций
       change = false
       while не конец таблицы do
          read следующую транзакцию [math]\displaystyle{ t_i }[/math] из таблицы
          sum_max = 0
          for для каждого кластера [math]\displaystyle{ C_j }[/math]
             вычислить сумму [math]\displaystyle{ Sum }[/math] стоимости удаления из кластера [math]\displaystyle{ C_i }[/math] и добавления транзакции к [math]\displaystyle{ C_j }[/math](j<>i)
             if  Sum > sum_max then
                   sum_max = Sum 
                   запомнить номер кластера [math]\displaystyle{ l }[/math] 
             end if
          end for
          if sum_max>0  
             change = true
             write транзакцию [math]\displaystyle{ t_i }[/math] в кластер [math]\displaystyle{ C_l }[/math], который максимизирует функцию цены
          end if
       end while
    until not change
    delete все пустые кластеры

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

Пусть [math]\displaystyle{ n }[/math] - количество транзакций, [math]\displaystyle{ m }[/math] - максимальное количество объектов транзакции, [math]\displaystyle{ k }[/math] - количество кластеров.

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

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

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

Сложность алгоритма равна [math]\displaystyle{ O(n*k*m) }[/math].

Ресурс параллелизма алгоритма

Вычисления стоимости добавления и удаления транзакции выполняются независимо для всех кластеров. Именно поэтому все такие вычисления для одной транзакции можно производить параллельно. Таким образом, сложность алгоритма с [math]\displaystyle{ O(n*k*m) }[/math] понижается до [math]\displaystyle{ O(n*m) }[/math], где [math]\displaystyle{ k }[/math] - количество кластеров.

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

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

[math]\displaystyle{ n }[/math] транзакций максимальной длины [math]\displaystyle{ m }[/math] и коэффициент отталкивания [math]\displaystyle{ r }[/math].

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

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

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

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

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

• Количество кластеров определяет отношение последовательной и параллельной сложности алгоритма : [math]\displaystyle{ \dfrac{O(n*m*k)}{O(n*m)} = k }[/math]
• Быстро работает для большого количества данных

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

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

Первое описание данного алгоритма появилось совсем недавно, этим можно объяснить небольшое количество его реализаций.

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

Помимо этого существуют пользовательские реализации алгоритма:

• https://github.com/infozor/php_mysql_clustering_clope - реализация алгоритма на PHP
• https://github.com/Tolsi/scala-clope - реализация алгоритма Scala

Литература

<references \>