Участник:Казаков Артем/Алгоритм концептуальной кластеризации COBWEB

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

Общая схема описания алгоритмов имеет следующий вид:

1 ЧАСТЬ. Свойства и структура алгоритмов

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

Алгоритм COBWEB – классический метод инкрементальной концептуальной кластеризации. Он создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт и содержит вероятностное описание этого концепта, которое включает в себя вероятность принадлежности концепта к данному узлу и условные вероятности вида: P(Ai = vij|Ck), где Ai = vij – пара атрибут-значение, Ck – класс концепта.

Узлы, находящейся на определённом уровне дерева классификации, называют срезом. Алгоритм использует для построения дерева классификации эвристическую меру оценки, называемую полезностью категории – прирост ожидаемого числа корректных предположений о значениях атрибутов при знании об их принадлежности к определённой категории относительно ожидаемого числа корректных предположений о значениях атрибутов без этого знания. Чтобы встроить новый объект в дерево классификации, алгоритм COBWEB итеративно проходит всё дерево в поисках «лучшего» узла, к которому отнести этот объект. Выбор узла осуществляется на основе помещения объекта в каждый узел и вычисления полезности категории получившегося среза. Также вычисляется полезность категории для случая, когда объект относится к вновь создаваемому узлу. В итоге объект относится к тому узлу, для которого полезность категории больше.

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

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

Пусть [math]X[/math] — множество объектов, [math]Y[/math] — множество номеров (имён, меток) кластеров. Задана функция расстояния между объектами [math]\rho(x,x')[/math]. Имеется конечная обучающая выборка объектов [math]X^m = \{ x_1, \dots, x_m \} \subset X[/math]. Требуется разбить выборку на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из объектов, близких по метрике [math]\rho[/math], а объекты разных кластеров существенно отличались. При этом каждому объекту [math]x_i\in X^m[/math] приписывается номер кластера [math]y_i[/math].

P(Aj = υij | Ck) - это условная вероятность, с которой свойство Aj, принимает значение υij, если объект относится к категории Ck. Для каждой категории в иерархии определены вероятности вхождения всех значений каждого свойства. При предъявлении нового экземпляра система COBWEB оценивает качество отнесения этого примера к существующей категории и модификации иерархии категорий в соответствии с новым представителем. Критерием оценки качества классификации является полезность категории (category utility). Критерий полезности категории был определен при исследовании человеческой категоризации. Он учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий.

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

[math]CU = \sum_{k} \sum_{i} \sum_{j} P(A = u_{ij}|C_k) P(C_K|A = u_{ij}) P(A = u_{ij})[/math]

Значения суммируются по всем категориям Ck, всем свойствам Aj и всем значениям свойств υij. Значение P(Aj = υij | Ck) называется предсказуемостью (predictability). Это вероятность того, что объект, для которого свойство Aj- принимает значение υij, относится к категории Ck. Чем выше это значение, тем вероятнее, что свойства двух объектов, отнесенных к одной категории, имеют одинаковые значения. Величина P(Ck | A = υij) называется предиктивностью (predictiveness). Это вероятность того, что для объектов из категории Ck свойство Aj принимает значение υij. Чем больше эта величина, тем менее вероятно, что для объектов, не относящихся к данной категории, это свойство будет принимать указанное значение. Значение P(A = υij) - это весовой коэффициент, усиливающий влияние наиболее распространенных свойств. Благодаря совместному учету этих значений высокая полезность категории означает высокую вероятность того, что объекты из одной категории обладают одинаковыми свойствами, и низкую вероятность наличия этих свойств у объектов из других категорий.

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

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

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

В алгоритме COBWEB реализован метод поиска экстремума в пространстве возможных кластеров с использованием критерия полезности категорий для оценки и выбора возможных способов категоризации.

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

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

Для слияния двух узлов создается новый узел, для которого существующие узлы становятся дочерними. На основе значений вероятностей дочерних узлов вычисляются вероятности для нового узла. При разбиении один узел заменяется двумя дочерними.

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

cobweb(Node, Instance)

Begin
 if узел Node - это лист, then
   begin
    создать два дочерних узла L1 и L2 для узла Node;
    задать для узла L1 те же вероятности, что и для узла Node;
    инициализировать вероятности для узла L2 соответствующими значениями объекта Instance;
    добавить Instance к Node, обновив вероятности для узла Node ;
   end
 else
   begin
    добавить Instance к Node, обновив вероятности для узла Node;
    для каждого дочернего узла С узла Node вычислить полезность категории при отнесении экземпляра Instance к категории С;
    пусть S1 - значение полезности для наилучшей классификации C1;
    пусть S2 - значение для второй наилучшей классификации C2;
    пусть S3 - значение полезности для отнесения экземпляра к новой категории;
    пусть S4 - значение для слияния C1 и C2 в одну категорию;
    пусть S5 - значение для разделения C1 (замены дочерними категориями);
   end
  if S1 - максимальное значение CU, then
    cobweb(C1, Instance) %отнести экземпляр к C1
  else
    if S3 - максимальное значение CU, then
      инициализировать вероятности для новой категории Cm значениями Instance 
    else 
      if S4 - максимальное значение CU, then 
        begin
          пусть Cm - результат слияния C1 и C2; 
          cobweb(Cm, Instance);
        end 
      else
        if S5 - максимальное значение CU, then 
          begin 
            разделить C1; % Cm - новая категория
            cobweb(Cm, Instance)
          end;
end

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

Пусть [math]B[/math] - среднее число потомков узлов в дереве классификации и [math]n[/math] - число уже классифицированных объектов, тогда [math]log_{B}n[/math] - оценка глубины дерева классификации. Кроме того, положим [math]A[/math] равным числу свойств у классифицируемых объектов, а [math]V[/math] - среднее число значений, которые могу принимать данные свойства. В ходе определения к каком у классу отнести каждый следующий объект из входного набора, необходимо рассчитать значение функции полезности категории. Сложность расчета данной функции есть [math]O(BAV)[/math] и данное действие необходимо повторить для каждого из B потомков (в среднем). Кроме того, для классификации нам необходимо пройти по дереву, имеющему глубину [math]log_{B}n[/math], таким образом мы имеем оценку по сложности [math]O(log_{B}n*B^{2}AV)[/math].

1.7 Информационный граф

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

1.8 Ресурс параллелизма

Основной вычислительной нагрузкой алгоритма является вычисление функции полезности для категорий. Эта часть алгоритма поддается наиболее простому распараллеливанию. Существует два пути к получению параллельной версии исходного алгоритма:

• распараллеливание процесса вычисления совокупности функций полезности
• распараллеливание вычисления каждой конкретной функции полезности

Оба данных подхода к распараллеливанию могут быть использованы вместе.

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

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

2 ЧАСТЬ. Программная реализация алгоритма

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

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

• concept_formation библиотека реализации алгоритмов COBWEB и COBWEB/3 для языка Python.
• Weka библиотека и инструмент для анализа данных на языке Java.
• Java-ML библиотека машинного обучения на языке Java.

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