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

Авторы: Ю.Ю.Потапов, А.М.Скрипник.

Алгоритм концептуальной кластеризации COBWEB
Последовательный алгоритм
Последовательная сложность	[math] O(|C|*|A|*|V|*|O|)[/math]
Объём входных данных	[math]|O|[/math]
Объём выходных данных	[math]1[/math]

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

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

Задача кластеризации является одной из важнейших задач интеллектуального анализа данных в различных проблемных областях – технических, естественнонаучных, социальных. Кластеризация является примером задачи обучения без учителя и сводится к разбиению исходного множества объектов на подмножества классов таким образом, что элементы одного класса были бы схожи между собой, а элементы различных классов были бы максимально различны.[9]

Алгоритм COBWEB - классический метод инкрементальной концептуальной кластеризации, который был изобретен профессором Дугласом Фишером в 1987 году.

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

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

• Обозначим: [math] O = \{O_1 \dots O_n\} [/math] - множество распознаваемых объектов, характеризуемых аттрибутами [math] A = \{A_1 \dots A_m\} [/math], которые могут принимать значения [math] V = \{V_{11} \dots V_{mk}\} [/math]. Ставится задача кластеризации исходного множеста объектов на классы [math] C = \{C_1 \dots C_l\} [/math] так, чтобы максимизировать функцию полезности кластеризации.

Полезность кластеризации рассматривается как функция CU, определяющая сходство объектов в рамках одного кластера, и их различие по отношению к объектам из других кластеров:

[math] CU = \frac{\sum_{C_k \in C} P(C_k) [\sum_{i} \sum_{j} P(A_i = V_{ij} | C_k)^2 - \sum_{i} \sum_{j} P(A_i = V_{ij})^2]}{|C|} [/math]

[math] P(A_i = V_{ij}) = \frac{|\{O_l | O_l \in C, A_i = V_{ij}\}|}{|\{O_l | O_l \in C\}|} [/math]

[math] P(A_i = V_{ij} | C_k) = \frac{|\{O_l | O_l \in C_k, A_i = V_{ij}\}|}{|\{O_l | O_l \in C_k\}|} [/math]

При выполнении алгоритма итерационно строится дерево классификации. Каждая вершина дерева представляет собой класс. Срез дерева представляет возможное разбиение на непересекающииеся классы. Функция полезности CU применяется именно к срезу.

Каждая вершина дерева содержит следующие данные:
[math]P(C_k)[/math] - вероятность объекта принадлежать данному классу
[math]P(A_i = V_{ij} | C_k)[/math] - вероятность объекта иметь значение [math]V_{ij}[/math] у аттрибута [math]A_i[/math] при условии принадлежности к классу [math]C_k[/math]
[math]\{O_i\}[/math] - множество объектов, принадлежащих данному классу.

Алгоритм использует операции четырёх типов:

• Отнесение объекта к существующему классу
• Создание нового класса
• Объединение двух классов в один
• Разбиение одного класса на два

Рис.1 показывает операции добавления нового класса и занесения объекта в существующий класс
Рис.2 показывает операции объединения
Рис.3 показывает разбиения классов

Рис.1 a)Начальное состояние, b)Операция добавления нового класса, c)Операция занесения в существующий класс

Рис.2 Объединение двух классов в один

Рис.3 Разбиение одного класса на два

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

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

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

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

• Отнесение объекта к существующему классу
• Создание нового класса
• Объединение двух классов в один
• Разбиение одного класса на два

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

1. Используя первый объект Object, создаем корень дерева Root
2. COBWEB(Node, Object):
   1. Если Node является листом дерева:
      1. Cоздать два дочерних узла L1 и L2 для узла Node
      2. Задать для узла L1 те же вероятности, что и для узла Node
      3. Инициализировать вероятности для узла L2 соответствующими значениями объекта Object;
      4. Добавить Object к Node, обновив вероятности для узла Node
   2. Если Node не является листом:
      1. Добавить Object к Node, обновив вероятности для узла Node
      2. Для каждого дочернего узла [math]C[/math] узла Node вычислить полезность категории при отнесении экземпляра Object к категории [math]C[/math]
         пусть [math]S_1[/math] - значение полезности для наилучшей классификации [math]C_1[/math]
         пусть [math]S_2[/math] - значение для второй наилучшей классификации [math]C_2[/math]
         пусть [math]S_3[/math] - значение полезности для отнесения экземпляра к новой категории
         пусть [math]S_4[/math] - значение для слияния [math]C_1[/math] и [math]C_2[/math] в одну категорию
         пусть [math]S_5[/math] - значение для разделения [math]C_1[/math] (замены дочерними категориями)
      3. Если [math]S_1[/math] - максимальное значение, то отнести объект к [math]C_1[/math]: COBWEB([math]C_1[/math], Object)
         Если [math]S_3[/math] - максимальное значение, то инициализировать вероятности для новой категории [math]C_m[/math] значениями Object
         Если [math]S_4[/math] - максимальное значение, то пусть [math]C_m[/math] - результат слияния [math]C_1[/math] и [math]C_2[/math]: COBWEB([math]C_m[/math], Object)
         Если [math]S_5[/math] - максимальное значение, то разделить [math]C_1[/math] и для новой категории [math]C_m[/math]: COBWEB([math]C_m[/math], Object)

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

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

Сложность вычисления [math] CU = \frac{\sum_{C_k \in C} P(C_k) [\sum_{i} \sum_{j} P(A_i = V_{ij} | C_k)^2 - \sum_{i} \sum_{j} P(A_i = V_{ij})^2]}{|C|} [/math] - это [math] O(|C|*|A|*|V|*|O|)[/math], где

• [math]|C|[/math] - количество классов в срезе
• [math]|A|[/math] - количество аттрибутов объекта
• [math]|V|[/math] - количество возможных значений
• [math]|O|[/math] - количество объектов.

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

На данном информационном графе изображен алгоритм выбора нужного действия при добавлении нового объекта в дерево классификации. А именно функция COBWEB, которая во время выполнения программы вызывается рекурсивно.

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

• Красные узлы графа - вычисление функции полезности CU после добавления объекта в один из узлов-потомков
• Оранжевый - вычисление функции полезности CU после создания нового класса и добавления объекта в него
• Фиолетовый - вычисление двух максимальных значений для CU
• Желтый - вычисление функции полезности CU после объединения двух классов с максимальными функциями полезности
• Коричневый - вычисление функции полезности CU после разбиения класса с максимальной функцией полезности
• Голубой - выбрать действие, после которого функция полезности оказалась максимальной и вызвать рекурсивно функцию COBWEB от соответствующего узла и текущего объекта

Рис.4 Граф алгоритма COBWEB

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

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

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

Также, большой ресурс параллелизма заключается в самой операции [math] CU = \frac{\sum_{C_k \in C} P(C_k) [\sum_{i} \sum_{j} P(A_i = V_{ij} | C_k)^2 - \sum_{i} \sum_{j} P(A_i = V_{ij})^2]}{|C|} [/math], так как вычисление слагаемых суммы может происходить массово параллельно для всех возможных значений [math]A_i[/math] и [math]V_{ij}[/math] всех объектов [math]O_k \in C[/math]

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

Так как основные операции выполняются над числами, интерпретирующими вероятности, то алгоритм оперирует данными примерно одного порядка точности.

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

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

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

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

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

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

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

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

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

2.3 Возможные способы и особенности параллельной реализации алгоритма

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

• представленный иерархически ресурс параллелизма, опирающийся на структуру циклических конструкций и на граф вызовов программы;
• комбинацию (иерархию) массового параллелизма и параллелизма конечного;
• возможные способы распределения операций между процессами/нитями;
• возможные способы распределения данных;
• оценку количества операций, объёма и числа пересылок данных (как общего числа, так и в пересчёте на каждый параллельный процесс);

и другие.

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

2.5 Динамические характеристики и эффективность реализации алгоритма

Это объемный раздел AlgoWiki, поскольку оценка эффективности реализации алгоритма требует комплексного подхода [5], предполагающего аккуратный анализ всех этапов от архитектуры компьютера до самого алгоритма. Основная задача данного раздела заключается в том, чтобы оценить степень эффективности параллельных программ, реализующих данный алгоритм на различных платформах, в зависимости от числа процессоров и размера задачи. Эффективность в данном разделе понимается широко: это и эффективность распараллеливания программы, это и эффективность реализации программ по отношению к пиковым показателям работы вычислительных систем.

Помимо собственно показателей эффективности, нужно описать и все основные причины, из-за которых эффективность работы параллельной программы на конкретной вычислительной платформе не удается сделать выше. Это не самая простая задача, поскольку на данный момент нет общепринятой методики и соответствующего инструментария, с помощью которых подобный анализ можно было бы провести. Требуется оценить и описать эффективность работы с памятью (особенности профиля взаимодействия программы с памятью), эффективность использования заложенного в алгоритм ресурса параллелизма, эффективность использования коммуникационной сети (особенности коммуникационного профиля), эффективность операций ввода/вывода и т.п. Иногда достаточно интегральных характеристик по работе программы, в некоторых случаях полезно показать данные мониторинга нижнего уровня, например, по загрузке процессора, кэш-промахам, интенсивности использования сети Infiniband и т.п. Хорошее представление о работе параллельной MPI-программы дают данные трассировки, полученные, например, с помощью системы Scalasca.

2.6 Выводы для классов архитектур

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

На практике это сделать можно по-разному: либо все свести в один текущий раздел, либо же соответствующие факты сразу включать в предшествующие разделы, где они обсуждаются и необходимы по смыслу. В некоторых случаях, имеет смысл делать отдельные варианты всей части II AlgoWiki применительно к отдельным классам архитектур, оставляя общей машинно-независимую часть I. В любом случае, важно указать и позитивные, и негативные факты по отношению к конкретным классам. Можно говорить о возможных вариантах оптимизации или даже о "трюках" в написании программ, ориентированных на целевые классы архитектур.

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

Для многих пар алгоритм+компьютер уже созданы хорошие реализации, которыми можно и нужно пользоваться на практике. Данный раздел предназначен для того, чтобы дать ссылки на основные существующие последовательные и параллельные реализации алгоритма, доступные для использования уже сейчас. Указывается, является ли реализация коммерческой или свободной, под какой лицензией распространяется, приводится местоположение дистрибутива и имеющихся описаний. Если есть информация об особенностях, достоинствах и/или недостатках различных реализаций, то это также нужно здесь указать. Хорошими примерами реализации многих алгоритмов являются MKL, ScaLAPACK, PETSc, FFTW, ATLAS, Magma и другие подобные библиотеки.

3 Литература

[1] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

[2] Воеводин В.В., Воеводин Вад.В. Спасительная локальность суперкомпьютеров //Открытые системы. - 2013. - № 9. - С. 12-15.

[3] Воеводин Вад.В., Швец П. Метод покрытий для оценки локальности использования данных в программах // Вестник УГАТУ. — 2014. — Т. 18, № 1(62). — С. 224–229.

[4] Антонов А.С., Теплов А.М. О практической сложности понятия масштабируемости параллельных программ// Высокопроизводительные параллельные вычисления на кластерных системах (HPC 2014): Материалы XIV Международной конференции -Пермь: Издательство ПНИПУ, 2014. С. 20-27.

[5] Никитенко Д.А. Комплексный анализ производительности суперкомпьютерных систем, основанный на данных системного мониторинга // Вычислительные методы и программирование. 2014. 15. 85–97.

[6] Обзор алгоритмов кластеризации числовых пространств данных: https://habrahabr.ru/post/164417/

[7] Wiki: https://en.wikipedia.org/wiki/Cobweb_(clustering)

[8] Java implementation: http://weka.sourceforge.net/doc.dev/weka/clusterers/Cobweb.html

[9] МОДЕЛЬ И МЕТОД КОНЦЕПТУАЛЬНОЙ КЛАСТЕРИЗАЦИИ ОБЪЕКТОВ, ХАРАКТЕРИЗУЕМЫХ НЕЧЕТКИМИ ПАРАМЕТРАМИ // Фундаментальные исследования. – 2014. – № 9 (часть 5) – С. 993-997 - http://www.fundamental-research.ru/ru/article/view?id=35003

[10] Fisher D. Knowledge Acquisition Via Incremental Conceptual Clustering, 1987. – P. 142–153. - http://link.springer.com/article/10.1007/BF00114265

[11] Методы и средства анализа данных - Алгоритм Cobweb: http://bourabai.ru/tpoi/analysis6.htm#.D0.90.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC_Cobweb

[12] Python implementation: https://github.com/cmaclell/concept_formation

[13] Java Machine Learning Library: http://java-ml.sourceforge.net/api/0.1.5/net/sf/javaml/clustering/Cobweb.html