Алговики - Вклад [ru]

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

2016-12-01T17:59:46Z

Dlin:

{{Assignment}}

Основные авторы описания: [[Участник:Dlin|Линь Данил]] (1.1-1.10, 2.7)

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

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

Алгоритм COBWEB был впервые предложен профессором университета Вандербильта, [[Douglas H. Fisher (Computer Science)|Douglas H. Fisher]] в 1987 году и относится к классу концептуальных алгоритмов кластеризации.

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

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

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

Алгоритм COBWEB – классический метод инкрементальной концептуальной кластеризации. Он создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт и содержит вероятностное описание этого концепта, которое включает в себя вероятность принадлежности концепта к данному узлу и условные вероятности вида: <math>P(A_{j}={\upsilon}_{ij}|C_k)</math>, где <math>A_{i}={\upsilon}_{ij} </math> – пара атрибут-значение, <math>C_{k}</math> – класс концепта.
Узлы, находящейся на определённом уровне дерева классификации, называют срезом. Алгоритм использует для построения дерева классификации эвристическую меру оценки, называемую полезностью категории – прирост ожидаемого числа корректных предположений о значениях атрибутов при знании об их принадлежности к определённой категории относительно ожидаемого числа корректных предположений о значениях атрибутов без этого знания.

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

В алгоритме COBWEB реализовано вероятностное представление категорий. Принадлежность категории определяется не набором значений каждого свойства объекта, а вероятностью появления значения. Например, <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> - это условная вероятность, с которой свойство <math>A_{j}</math>, принимает значение <math>{\upsilon}_{ij}</math>, если объект относится к категории <math>C_{k}</math>. Для каждой категории в иерархии определены вероятности вхождения всех значений каждого свойства. При предъявлении нового экземпляра система COBWEB оценивает качество отнесения этого примера к существующей категории и модификации иерархии категорий в соответствии с новым представителем. Критерием оценки качества классификации является полезность категории (category utility), которая учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий.

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

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

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

<math> CU = \sum_{k} { \sum_{i} { \sum_{j} { {P(A={\upsilon}_{ij}|C_k)} {({P(C_k | A={\upsilon}_{ij})} P(A={\upsilon}_{ij})} } } } </math>

Значения суммируются по всем категориям <math>C_{k}</math>, всем свойствам <math>A_{j}</math> и всем значениям свойств <math>{\upsilon}_{ij}</math>. Значение <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> называется предсказуемостью (predictability). Это вероятность того, что объект, для которого свойство <math>A_{j}</math> - принимает значение <math>{\upsilon}_{ij}</math>, относится к категории <math>C_k</math>. Чем выше это значение, тем вероятнее, что свойства двух объектов, отнесенных к одной категории, имеют одинаковые значения. Величина <math>P(C_k | A={\upsilon}_{ij})</math> называется предиктивностью (predictiveness). Это вероятность того, что для объектов из категории <math>C_k</math> свойство <math>A_j</math> принимает значение <math>{\upsilon}_{ij}</math>. Чем больше эта величина, тем менее вероятно, что для объектов, не относящихся к данной категории, это свойство будет принимать указанное значение. Значение <math>P(A={\upsilon}_{ij}</math> - это весовой коэффициент, усиливающий влияние наиболее распространенных свойств. Благодаря совместному учету этих значений высокая полезность категории означает высокую вероятность того, что объекты из одной категории обладают одинаковыми свойствами, и низкую вероятность наличия этих свойств у объектов из других категорий.

После некоторых преобразований (Байеса в частности) и некоторых агрументированных изменений мы получаем более правильную формулу:

<math>CU= \frac{ \sum_{k=1}^N {P(A={\upsilon}_{ij}|C_k)} \sum_{j} { \sum_{i} {({P(C_k | A={\upsilon}_{ij})}^2 - {P(A={\upsilon}_{ij})}^2)}}}{N} </math>

где N -число категорий.

=== Макроструктура алгоритма ===
[[File:Concept tree.png|thumb|450 px|Простой пример дерева классификации]]

Алгоритм COBEWB создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт. Каждый концепт представляется в виде набора объектов, а объекты являтются бинарными списками. В качестве примера возьмем задачу отнесения особи к определенной биологической группе. Рассмотрим концепт <math>C_1</math>, включающий в себя 4 объекта:

#<code>[1 0 1]</code>
#<code>[0 1 1]</code>
#<code>[0 1 0]</code>
#<code>[0 1 1]</code>

Признаки объекта могут иметь следующий смысл: <code>[мужского_пола, птица, ведущий_ночной_образ_жизни]</code>. Концепт характеризуется целочисленным списком, в котором хранятся суммы соответствующих значений объектов. Для <math>C_1</math> данный счетчик будет <code>[1 3 3]</code>, что означает что биологическая группа включает в себя одну особь мужского пола, три птицы и три особи ведущие ночной образ жизни. Данный счетчик является основанием для вероятностного описания конкретного концепта. Таким образом, вероятность того, что особь, принадлежащая концепту <math>C_1</math>, мужского пола равна <math>1/4 = 0.25</math>, а концепт в целом можно характеризовать как <code>[.25 .75 .75]</code>. Рисунок справа иллюстрирует дерево классификации для 5 концептов. <math>C_0</math> - корневой концепт, включающий в себя все объекты из набора данных. <math>C_1</math> и <math>C_2</math> - концепты-потомки, объединяющие 4 и 6 объектов соответственно. <math>C_2</math> в свою очередь, является концептом-родителем для <math>C_3</math>, <math>C_4</math>, <math>C_5</math>.

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

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

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

<math> O(|C|*|A|*|V|*|O|)</math>, где 

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

=== Информационный граф ===
[[File:cobweb grap.jpg|thumb|650 px|Алгоритм выбора операции ]]

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

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

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

Основной вычислительной нагрузкой алгоритма является вычисление функции полезности для категорий. Однако, именно эта часть алгоритма поддается простому и логичному распараллеливанию. Можно выделить два пути к получению параллельной версии исходного алгоритма:
* распараллеливание вычисления каждой конкретной функции полезности
* распараллеливание процесса вычисления совокупности функций полезности

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

*[https://github.com/cmaclell/concept_formation Working python implementation of COBWEB] библиотека реализации алгоритмов COBWEB и COBWEB/3 для языка Python.

== Литература ==

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

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

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

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

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

2016-12-01T17:58:05Z

Dlin: /* Ресурс параллелизма алгоритма */

Основные авторы описания: [[Участник:Dlin|Линь Данил]] (1.1-1.10, 2.7)

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

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

Алгоритм COBWEB был впервые предложен профессором университета Вандербильта, [[Douglas H. Fisher (Computer Science)|Douglas H. Fisher]] в 1987 году и относится к классу концептуальных алгоритмов кластеризации.

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

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

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

Алгоритм COBWEB – классический метод инкрементальной концептуальной кластеризации. Он создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт и содержит вероятностное описание этого концепта, которое включает в себя вероятность принадлежности концепта к данному узлу и условные вероятности вида: <math>P(A_{j}={\upsilon}_{ij}|C_k)</math>, где <math>A_{i}={\upsilon}_{ij} </math> – пара атрибут-значение, <math>C_{k}</math> – класс концепта.
Узлы, находящейся на определённом уровне дерева классификации, называют срезом. Алгоритм использует для построения дерева классификации эвристическую меру оценки, называемую полезностью категории – прирост ожидаемого числа корректных предположений о значениях атрибутов при знании об их принадлежности к определённой категории относительно ожидаемого числа корректных предположений о значениях атрибутов без этого знания.

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

В алгоритме COBWEB реализовано вероятностное представление категорий. Принадлежность категории определяется не набором значений каждого свойства объекта, а вероятностью появления значения. Например, <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> - это условная вероятность, с которой свойство <math>A_{j}</math>, принимает значение <math>{\upsilon}_{ij}</math>, если объект относится к категории <math>C_{k}</math>. Для каждой категории в иерархии определены вероятности вхождения всех значений каждого свойства. При предъявлении нового экземпляра система COBWEB оценивает качество отнесения этого примера к существующей категории и модификации иерархии категорий в соответствии с новым представителем. Критерием оценки качества классификации является полезность категории (category utility), которая учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий.

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

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

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

<math> CU = \sum_{k} { \sum_{i} { \sum_{j} { {P(A={\upsilon}_{ij}|C_k)} {({P(C_k | A={\upsilon}_{ij})} P(A={\upsilon}_{ij})} } } } </math>

Значения суммируются по всем категориям <math>C_{k}</math>, всем свойствам <math>A_{j}</math> и всем значениям свойств <math>{\upsilon}_{ij}</math>. Значение <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> называется предсказуемостью (predictability). Это вероятность того, что объект, для которого свойство <math>A_{j}</math> - принимает значение <math>{\upsilon}_{ij}</math>, относится к категории <math>C_k</math>. Чем выше это значение, тем вероятнее, что свойства двух объектов, отнесенных к одной категории, имеют одинаковые значения. Величина <math>P(C_k | A={\upsilon}_{ij})</math> называется предиктивностью (predictiveness). Это вероятность того, что для объектов из категории <math>C_k</math> свойство <math>A_j</math> принимает значение <math>{\upsilon}_{ij}</math>. Чем больше эта величина, тем менее вероятно, что для объектов, не относящихся к данной категории, это свойство будет принимать указанное значение. Значение <math>P(A={\upsilon}_{ij}</math> - это весовой коэффициент, усиливающий влияние наиболее распространенных свойств. Благодаря совместному учету этих значений высокая полезность категории означает высокую вероятность того, что объекты из одной категории обладают одинаковыми свойствами, и низкую вероятность наличия этих свойств у объектов из других категорий.

После некоторых преобразований (Байеса в частности) и некоторых агрументированных изменений мы получаем более правильную формулу:

<math>CU= \frac{ \sum_{k=1}^N {P(A={\upsilon}_{ij}|C_k)} \sum_{j} { \sum_{i} {({P(C_k | A={\upsilon}_{ij})}^2 - {P(A={\upsilon}_{ij})}^2)}}}{N} </math>

где N -число категорий.

=== Макроструктура алгоритма ===
[[File:Concept tree.png|thumb|450 px|Простой пример дерева классификации]]

Алгоритм COBEWB создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт. Каждый концепт представляется в виде набора объектов, а объекты являтются бинарными списками. В качестве примера возьмем задачу отнесения особи к определенной биологической группе. Рассмотрим концепт <math>C_1</math>, включающий в себя 4 объекта:

#<code>[1 0 1]</code>
#<code>[0 1 1]</code>
#<code>[0 1 0]</code>
#<code>[0 1 1]</code>

Признаки объекта могут иметь следующий смысл: <code>[мужского_пола, птица, ведущий_ночной_образ_жизни]</code>. Концепт характеризуется целочисленным списком, в котором хранятся суммы соответствующих значений объектов. Для <math>C_1</math> данный счетчик будет <code>[1 3 3]</code>, что означает что биологическая группа включает в себя одну особь мужского пола, три птицы и три особи ведущие ночной образ жизни. Данный счетчик является основанием для вероятностного описания конкретного концепта. Таким образом, вероятность того, что особь, принадлежащая концепту <math>C_1</math>, мужского пола равна <math>1/4 = 0.25</math>, а концепт в целом можно характеризовать как <code>[.25 .75 .75]</code>. Рисунок справа иллюстрирует дерево классификации для 5 концептов. <math>C_0</math> - корневой концепт, включающий в себя все объекты из набора данных. <math>C_1</math> и <math>C_2</math> - концепты-потомки, объединяющие 4 и 6 объектов соответственно. <math>C_2</math> в свою очередь, является концептом-родителем для <math>C_3</math>, <math>C_4</math>, <math>C_5</math>.

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

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

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

<math> O(|C|*|A|*|V|*|O|)</math>, где 

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

=== Информационный граф ===
[[File:cobweb grap.jpg|thumb|650 px|Алгоритм выбора операции ]]

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

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

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

Основной вычислительной нагрузкой алгоритма является вычисление функции полезности для категорий. Однако, именно эта часть алгоритма поддается простому и логичному распараллеливанию. Можно выделить два пути к получению параллельной версии исходного алгоритма:
* распараллеливание вычисления каждой конкретной функции полезности
* распараллеливание процесса вычисления совокупности функций полезности

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

*[https://github.com/cmaclell/concept_formation Working python implementation of COBWEB] библиотека реализации алгоритмов COBWEB и COBWEB/3 для языка Python.

== Литература ==

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

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

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

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

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

2016-12-01T17:57:06Z

Dlin: /* Информационный граф */

Основные авторы описания: [[Участник:Dlin|Линь Данил]] (1.1-1.10, 2.7)

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

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

Алгоритм COBWEB был впервые предложен профессором университета Вандербильта, [[Douglas H. Fisher (Computer Science)|Douglas H. Fisher]] в 1987 году и относится к классу концептуальных алгоритмов кластеризации.

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

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

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

Алгоритм COBWEB – классический метод инкрементальной концептуальной кластеризации. Он создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт и содержит вероятностное описание этого концепта, которое включает в себя вероятность принадлежности концепта к данному узлу и условные вероятности вида: <math>P(A_{j}={\upsilon}_{ij}|C_k)</math>, где <math>A_{i}={\upsilon}_{ij} </math> – пара атрибут-значение, <math>C_{k}</math> – класс концепта.
Узлы, находящейся на определённом уровне дерева классификации, называют срезом. Алгоритм использует для построения дерева классификации эвристическую меру оценки, называемую полезностью категории – прирост ожидаемого числа корректных предположений о значениях атрибутов при знании об их принадлежности к определённой категории относительно ожидаемого числа корректных предположений о значениях атрибутов без этого знания.

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

В алгоритме COBWEB реализовано вероятностное представление категорий. Принадлежность категории определяется не набором значений каждого свойства объекта, а вероятностью появления значения. Например, <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> - это условная вероятность, с которой свойство <math>A_{j}</math>, принимает значение <math>{\upsilon}_{ij}</math>, если объект относится к категории <math>C_{k}</math>. Для каждой категории в иерархии определены вероятности вхождения всех значений каждого свойства. При предъявлении нового экземпляра система COBWEB оценивает качество отнесения этого примера к существующей категории и модификации иерархии категорий в соответствии с новым представителем. Критерием оценки качества классификации является полезность категории (category utility), которая учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий.

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

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

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

<math> CU = \sum_{k} { \sum_{i} { \sum_{j} { {P(A={\upsilon}_{ij}|C_k)} {({P(C_k | A={\upsilon}_{ij})} P(A={\upsilon}_{ij})} } } } </math>

Значения суммируются по всем категориям <math>C_{k}</math>, всем свойствам <math>A_{j}</math> и всем значениям свойств <math>{\upsilon}_{ij}</math>. Значение <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> называется предсказуемостью (predictability). Это вероятность того, что объект, для которого свойство <math>A_{j}</math> - принимает значение <math>{\upsilon}_{ij}</math>, относится к категории <math>C_k</math>. Чем выше это значение, тем вероятнее, что свойства двух объектов, отнесенных к одной категории, имеют одинаковые значения. Величина <math>P(C_k | A={\upsilon}_{ij})</math> называется предиктивностью (predictiveness). Это вероятность того, что для объектов из категории <math>C_k</math> свойство <math>A_j</math> принимает значение <math>{\upsilon}_{ij}</math>. Чем больше эта величина, тем менее вероятно, что для объектов, не относящихся к данной категории, это свойство будет принимать указанное значение. Значение <math>P(A={\upsilon}_{ij}</math> - это весовой коэффициент, усиливающий влияние наиболее распространенных свойств. Благодаря совместному учету этих значений высокая полезность категории означает высокую вероятность того, что объекты из одной категории обладают одинаковыми свойствами, и низкую вероятность наличия этих свойств у объектов из других категорий.

После некоторых преобразований (Байеса в частности) и некоторых агрументированных изменений мы получаем более правильную формулу:

<math>CU= \frac{ \sum_{k=1}^N {P(A={\upsilon}_{ij}|C_k)} \sum_{j} { \sum_{i} {({P(C_k | A={\upsilon}_{ij})}^2 - {P(A={\upsilon}_{ij})}^2)}}}{N} </math>

где N -число категорий.

=== Макроструктура алгоритма ===
[[File:Concept tree.png|thumb|450 px|Простой пример дерева классификации]]

Алгоритм COBEWB создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт. Каждый концепт представляется в виде набора объектов, а объекты являтются бинарными списками. В качестве примера возьмем задачу отнесения особи к определенной биологической группе. Рассмотрим концепт <math>C_1</math>, включающий в себя 4 объекта:

#<code>[1 0 1]</code>
#<code>[0 1 1]</code>
#<code>[0 1 0]</code>
#<code>[0 1 1]</code>

Признаки объекта могут иметь следующий смысл: <code>[мужского_пола, птица, ведущий_ночной_образ_жизни]</code>. Концепт характеризуется целочисленным списком, в котором хранятся суммы соответствующих значений объектов. Для <math>C_1</math> данный счетчик будет <code>[1 3 3]</code>, что означает что биологическая группа включает в себя одну особь мужского пола, три птицы и три особи ведущие ночной образ жизни. Данный счетчик является основанием для вероятностного описания конкретного концепта. Таким образом, вероятность того, что особь, принадлежащая концепту <math>C_1</math>, мужского пола равна <math>1/4 = 0.25</math>, а концепт в целом можно характеризовать как <code>[.25 .75 .75]</code>. Рисунок справа иллюстрирует дерево классификации для 5 концептов. <math>C_0</math> - корневой концепт, включающий в себя все объекты из набора данных. <math>C_1</math> и <math>C_2</math> - концепты-потомки, объединяющие 4 и 6 объектов соответственно. <math>C_2</math> в свою очередь, является концептом-родителем для <math>C_3</math>, <math>C_4</math>, <math>C_5</math>.

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

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

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

<math> O(|C|*|A|*|V|*|O|)</math>, где 

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

=== Информационный граф ===
[[File:cobweb grap.jpg|thumb|650 px|Алгоритм выбора операции ]]

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

*[https://github.com/cmaclell/concept_formation Working python implementation of COBWEB] библиотека реализации алгоритмов COBWEB и COBWEB/3 для языка Python.

== Литература ==

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

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

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

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

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

2016-12-01T17:55:55Z

Dlin: /* Информационный граф */

Основные авторы описания: [[Участник:Dlin|Линь Данил]] (1.1-1.10, 2.7)

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

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

Алгоритм COBWEB был впервые предложен профессором университета Вандербильта, [[Douglas H. Fisher (Computer Science)|Douglas H. Fisher]] в 1987 году и относится к классу концептуальных алгоритмов кластеризации.

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

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

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

Алгоритм COBWEB – классический метод инкрементальной концептуальной кластеризации. Он создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт и содержит вероятностное описание этого концепта, которое включает в себя вероятность принадлежности концепта к данному узлу и условные вероятности вида: <math>P(A_{j}={\upsilon}_{ij}|C_k)</math>, где <math>A_{i}={\upsilon}_{ij} </math> – пара атрибут-значение, <math>C_{k}</math> – класс концепта.
Узлы, находящейся на определённом уровне дерева классификации, называют срезом. Алгоритм использует для построения дерева классификации эвристическую меру оценки, называемую полезностью категории – прирост ожидаемого числа корректных предположений о значениях атрибутов при знании об их принадлежности к определённой категории относительно ожидаемого числа корректных предположений о значениях атрибутов без этого знания.

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

В алгоритме COBWEB реализовано вероятностное представление категорий. Принадлежность категории определяется не набором значений каждого свойства объекта, а вероятностью появления значения. Например, <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> - это условная вероятность, с которой свойство <math>A_{j}</math>, принимает значение <math>{\upsilon}_{ij}</math>, если объект относится к категории <math>C_{k}</math>. Для каждой категории в иерархии определены вероятности вхождения всех значений каждого свойства. При предъявлении нового экземпляра система COBWEB оценивает качество отнесения этого примера к существующей категории и модификации иерархии категорий в соответствии с новым представителем. Критерием оценки качества классификации является полезность категории (category utility), которая учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий.

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

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

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

<math> CU = \sum_{k} { \sum_{i} { \sum_{j} { {P(A={\upsilon}_{ij}|C_k)} {({P(C_k | A={\upsilon}_{ij})} P(A={\upsilon}_{ij})} } } } </math>

Значения суммируются по всем категориям <math>C_{k}</math>, всем свойствам <math>A_{j}</math> и всем значениям свойств <math>{\upsilon}_{ij}</math>. Значение <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> называется предсказуемостью (predictability). Это вероятность того, что объект, для которого свойство <math>A_{j}</math> - принимает значение <math>{\upsilon}_{ij}</math>, относится к категории <math>C_k</math>. Чем выше это значение, тем вероятнее, что свойства двух объектов, отнесенных к одной категории, имеют одинаковые значения. Величина <math>P(C_k | A={\upsilon}_{ij})</math> называется предиктивностью (predictiveness). Это вероятность того, что для объектов из категории <math>C_k</math> свойство <math>A_j</math> принимает значение <math>{\upsilon}_{ij}</math>. Чем больше эта величина, тем менее вероятно, что для объектов, не относящихся к данной категории, это свойство будет принимать указанное значение. Значение <math>P(A={\upsilon}_{ij}</math> - это весовой коэффициент, усиливающий влияние наиболее распространенных свойств. Благодаря совместному учету этих значений высокая полезность категории означает высокую вероятность того, что объекты из одной категории обладают одинаковыми свойствами, и низкую вероятность наличия этих свойств у объектов из других категорий.

После некоторых преобразований (Байеса в частности) и некоторых агрументированных изменений мы получаем более правильную формулу:

<math>CU= \frac{ \sum_{k=1}^N {P(A={\upsilon}_{ij}|C_k)} \sum_{j} { \sum_{i} {({P(C_k | A={\upsilon}_{ij})}^2 - {P(A={\upsilon}_{ij})}^2)}}}{N} </math>

где N -число категорий.

=== Макроструктура алгоритма ===
[[File:Concept tree.png|thumb|450 px|Простой пример дерева классификации]]

Алгоритм COBEWB создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт. Каждый концепт представляется в виде набора объектов, а объекты являтются бинарными списками. В качестве примера возьмем задачу отнесения особи к определенной биологической группе. Рассмотрим концепт <math>C_1</math>, включающий в себя 4 объекта:

#<code>[1 0 1]</code>
#<code>[0 1 1]</code>
#<code>[0 1 0]</code>
#<code>[0 1 1]</code>

Признаки объекта могут иметь следующий смысл: <code>[мужского_пола, птица, ведущий_ночной_образ_жизни]</code>. Концепт характеризуется целочисленным списком, в котором хранятся суммы соответствующих значений объектов. Для <math>C_1</math> данный счетчик будет <code>[1 3 3]</code>, что означает что биологическая группа включает в себя одну особь мужского пола, три птицы и три особи ведущие ночной образ жизни. Данный счетчик является основанием для вероятностного описания конкретного концепта. Таким образом, вероятность того, что особь, принадлежащая концепту <math>C_1</math>, мужского пола равна <math>1/4 = 0.25</math>, а концепт в целом можно характеризовать как <code>[.25 .75 .75]</code>. Рисунок справа иллюстрирует дерево классификации для 5 концептов. <math>C_0</math> - корневой концепт, включающий в себя все объекты из набора данных. <math>C_1</math> и <math>C_2</math> - концепты-потомки, объединяющие 4 и 6 объектов соответственно. <math>C_2</math> в свою очередь, является концептом-родителем для <math>C_3</math>, <math>C_4</math>, <math>C_5</math>.

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

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

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

<math> O(|C|*|A|*|V|*|O|)</math>, где 

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

=== Информационный граф ===
[[File:cobweb grap.jpg]]

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

*[https://github.com/cmaclell/concept_formation Working python implementation of COBWEB] библиотека реализации алгоритмов COBWEB и COBWEB/3 для языка Python.

== Литература ==

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

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

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

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

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

2016-12-01T17:55:26Z

Dlin: /* Информационный граф */

Основные авторы описания: [[Участник:Dlin|Линь Данил]] (1.1-1.10, 2.7)

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

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

Алгоритм COBWEB был впервые предложен профессором университета Вандербильта, [[Douglas H. Fisher (Computer Science)|Douglas H. Fisher]] в 1987 году и относится к классу концептуальных алгоритмов кластеризации.

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

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

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

Алгоритм COBWEB – классический метод инкрементальной концептуальной кластеризации. Он создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт и содержит вероятностное описание этого концепта, которое включает в себя вероятность принадлежности концепта к данному узлу и условные вероятности вида: <math>P(A_{j}={\upsilon}_{ij}|C_k)</math>, где <math>A_{i}={\upsilon}_{ij} </math> – пара атрибут-значение, <math>C_{k}</math> – класс концепта.
Узлы, находящейся на определённом уровне дерева классификации, называют срезом. Алгоритм использует для построения дерева классификации эвристическую меру оценки, называемую полезностью категории – прирост ожидаемого числа корректных предположений о значениях атрибутов при знании об их принадлежности к определённой категории относительно ожидаемого числа корректных предположений о значениях атрибутов без этого знания.

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

В алгоритме COBWEB реализовано вероятностное представление категорий. Принадлежность категории определяется не набором значений каждого свойства объекта, а вероятностью появления значения. Например, <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> - это условная вероятность, с которой свойство <math>A_{j}</math>, принимает значение <math>{\upsilon}_{ij}</math>, если объект относится к категории <math>C_{k}</math>. Для каждой категории в иерархии определены вероятности вхождения всех значений каждого свойства. При предъявлении нового экземпляра система COBWEB оценивает качество отнесения этого примера к существующей категории и модификации иерархии категорий в соответствии с новым представителем. Критерием оценки качества классификации является полезность категории (category utility), которая учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий.

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

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

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

<math> CU = \sum_{k} { \sum_{i} { \sum_{j} { {P(A={\upsilon}_{ij}|C_k)} {({P(C_k | A={\upsilon}_{ij})} P(A={\upsilon}_{ij})} } } } </math>

Значения суммируются по всем категориям <math>C_{k}</math>, всем свойствам <math>A_{j}</math> и всем значениям свойств <math>{\upsilon}_{ij}</math>. Значение <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> называется предсказуемостью (predictability). Это вероятность того, что объект, для которого свойство <math>A_{j}</math> - принимает значение <math>{\upsilon}_{ij}</math>, относится к категории <math>C_k</math>. Чем выше это значение, тем вероятнее, что свойства двух объектов, отнесенных к одной категории, имеют одинаковые значения. Величина <math>P(C_k | A={\upsilon}_{ij})</math> называется предиктивностью (predictiveness). Это вероятность того, что для объектов из категории <math>C_k</math> свойство <math>A_j</math> принимает значение <math>{\upsilon}_{ij}</math>. Чем больше эта величина, тем менее вероятно, что для объектов, не относящихся к данной категории, это свойство будет принимать указанное значение. Значение <math>P(A={\upsilon}_{ij}</math> - это весовой коэффициент, усиливающий влияние наиболее распространенных свойств. Благодаря совместному учету этих значений высокая полезность категории означает высокую вероятность того, что объекты из одной категории обладают одинаковыми свойствами, и низкую вероятность наличия этих свойств у объектов из других категорий.

После некоторых преобразований (Байеса в частности) и некоторых агрументированных изменений мы получаем более правильную формулу:

<math>CU= \frac{ \sum_{k=1}^N {P(A={\upsilon}_{ij}|C_k)} \sum_{j} { \sum_{i} {({P(C_k | A={\upsilon}_{ij})}^2 - {P(A={\upsilon}_{ij})}^2)}}}{N} </math>

где N -число категорий.

=== Макроструктура алгоритма ===
[[File:Concept tree.png|thumb|450 px|Простой пример дерева классификации]]

Алгоритм COBEWB создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт. Каждый концепт представляется в виде набора объектов, а объекты являтются бинарными списками. В качестве примера возьмем задачу отнесения особи к определенной биологической группе. Рассмотрим концепт <math>C_1</math>, включающий в себя 4 объекта:

#<code>[1 0 1]</code>
#<code>[0 1 1]</code>
#<code>[0 1 0]</code>
#<code>[0 1 1]</code>

Признаки объекта могут иметь следующий смысл: <code>[мужского_пола, птица, ведущий_ночной_образ_жизни]</code>. Концепт характеризуется целочисленным списком, в котором хранятся суммы соответствующих значений объектов. Для <math>C_1</math> данный счетчик будет <code>[1 3 3]</code>, что означает что биологическая группа включает в себя одну особь мужского пола, три птицы и три особи ведущие ночной образ жизни. Данный счетчик является основанием для вероятностного описания конкретного концепта. Таким образом, вероятность того, что особь, принадлежащая концепту <math>C_1</math>, мужского пола равна <math>1/4 = 0.25</math>, а концепт в целом можно характеризовать как <code>[.25 .75 .75]</code>. Рисунок справа иллюстрирует дерево классификации для 5 концептов. <math>C_0</math> - корневой концепт, включающий в себя все объекты из набора данных. <math>C_1</math> и <math>C_2</math> - концепты-потомки, объединяющие 4 и 6 объектов соответственно. <math>C_2</math> в свою очередь, является концептом-родителем для <math>C_3</math>, <math>C_4</math>, <math>C_5</math>.

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

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

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

<math> O(|C|*|A|*|V|*|O|)</math>, где 

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

=== Информационный граф ===
[[File:cobweb grap.jpg|thumb|450 px|Простой пример дерева классификации]]

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

*[https://github.com/cmaclell/concept_formation Working python implementation of COBWEB] библиотека реализации алгоритмов COBWEB и COBWEB/3 для языка Python.

== Литература ==

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

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

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

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

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

2016-12-01T17:54:23Z

Dlin: /* Информационный граф */

Основные авторы описания: [[Участник:Dlin|Линь Данил]] (1.1-1.10, 2.7)

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

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

Алгоритм COBWEB был впервые предложен профессором университета Вандербильта, [[Douglas H. Fisher (Computer Science)|Douglas H. Fisher]] в 1987 году и относится к классу концептуальных алгоритмов кластеризации.

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

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

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

Алгоритм COBWEB – классический метод инкрементальной концептуальной кластеризации. Он создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт и содержит вероятностное описание этого концепта, которое включает в себя вероятность принадлежности концепта к данному узлу и условные вероятности вида: <math>P(A_{j}={\upsilon}_{ij}|C_k)</math>, где <math>A_{i}={\upsilon}_{ij} </math> – пара атрибут-значение, <math>C_{k}</math> – класс концепта.
Узлы, находящейся на определённом уровне дерева классификации, называют срезом. Алгоритм использует для построения дерева классификации эвристическую меру оценки, называемую полезностью категории – прирост ожидаемого числа корректных предположений о значениях атрибутов при знании об их принадлежности к определённой категории относительно ожидаемого числа корректных предположений о значениях атрибутов без этого знания.

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

В алгоритме COBWEB реализовано вероятностное представление категорий. Принадлежность категории определяется не набором значений каждого свойства объекта, а вероятностью появления значения. Например, <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> - это условная вероятность, с которой свойство <math>A_{j}</math>, принимает значение <math>{\upsilon}_{ij}</math>, если объект относится к категории <math>C_{k}</math>. Для каждой категории в иерархии определены вероятности вхождения всех значений каждого свойства. При предъявлении нового экземпляра система COBWEB оценивает качество отнесения этого примера к существующей категории и модификации иерархии категорий в соответствии с новым представителем. Критерием оценки качества классификации является полезность категории (category utility), которая учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий.

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

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

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

<math> CU = \sum_{k} { \sum_{i} { \sum_{j} { {P(A={\upsilon}_{ij}|C_k)} {({P(C_k | A={\upsilon}_{ij})} P(A={\upsilon}_{ij})} } } } </math>

Значения суммируются по всем категориям <math>C_{k}</math>, всем свойствам <math>A_{j}</math> и всем значениям свойств <math>{\upsilon}_{ij}</math>. Значение <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> называется предсказуемостью (predictability). Это вероятность того, что объект, для которого свойство <math>A_{j}</math> - принимает значение <math>{\upsilon}_{ij}</math>, относится к категории <math>C_k</math>. Чем выше это значение, тем вероятнее, что свойства двух объектов, отнесенных к одной категории, имеют одинаковые значения. Величина <math>P(C_k | A={\upsilon}_{ij})</math> называется предиктивностью (predictiveness). Это вероятность того, что для объектов из категории <math>C_k</math> свойство <math>A_j</math> принимает значение <math>{\upsilon}_{ij}</math>. Чем больше эта величина, тем менее вероятно, что для объектов, не относящихся к данной категории, это свойство будет принимать указанное значение. Значение <math>P(A={\upsilon}_{ij}</math> - это весовой коэффициент, усиливающий влияние наиболее распространенных свойств. Благодаря совместному учету этих значений высокая полезность категории означает высокую вероятность того, что объекты из одной категории обладают одинаковыми свойствами, и низкую вероятность наличия этих свойств у объектов из других категорий.

После некоторых преобразований (Байеса в частности) и некоторых агрументированных изменений мы получаем более правильную формулу:

<math>CU= \frac{ \sum_{k=1}^N {P(A={\upsilon}_{ij}|C_k)} \sum_{j} { \sum_{i} {({P(C_k | A={\upsilon}_{ij})}^2 - {P(A={\upsilon}_{ij})}^2)}}}{N} </math>

где N -число категорий.

=== Макроструктура алгоритма ===
[[File:Concept tree.png|thumb|450 px|Простой пример дерева классификации]]

Алгоритм COBEWB создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт. Каждый концепт представляется в виде набора объектов, а объекты являтются бинарными списками. В качестве примера возьмем задачу отнесения особи к определенной биологической группе. Рассмотрим концепт <math>C_1</math>, включающий в себя 4 объекта:

#<code>[1 0 1]</code>
#<code>[0 1 1]</code>
#<code>[0 1 0]</code>
#<code>[0 1 1]</code>

Признаки объекта могут иметь следующий смысл: <code>[мужского_пола, птица, ведущий_ночной_образ_жизни]</code>. Концепт характеризуется целочисленным списком, в котором хранятся суммы соответствующих значений объектов. Для <math>C_1</math> данный счетчик будет <code>[1 3 3]</code>, что означает что биологическая группа включает в себя одну особь мужского пола, три птицы и три особи ведущие ночной образ жизни. Данный счетчик является основанием для вероятностного описания конкретного концепта. Таким образом, вероятность того, что особь, принадлежащая концепту <math>C_1</math>, мужского пола равна <math>1/4 = 0.25</math>, а концепт в целом можно характеризовать как <code>[.25 .75 .75]</code>. Рисунок справа иллюстрирует дерево классификации для 5 концептов. <math>C_0</math> - корневой концепт, включающий в себя все объекты из набора данных. <math>C_1</math> и <math>C_2</math> - концепты-потомки, объединяющие 4 и 6 объектов соответственно. <math>C_2</math> в свою очередь, является концептом-родителем для <math>C_3</math>, <math>C_4</math>, <math>C_5</math>.

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

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

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

<math> O(|C|*|A|*|V|*|O|)</math>, где 

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

=== Информационный граф ===
[[File:cobweb_grap.png|thumb|450 px|Простой пример дерева классификации]]

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

*[https://github.com/cmaclell/concept_formation Working python implementation of COBWEB] библиотека реализации алгоритмов COBWEB и COBWEB/3 для языка Python.

== Литература ==

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

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

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

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

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

2016-12-01T17:53:52Z

Dlin: /* Информационный граф */

Основные авторы описания: [[Участник:Dlin|Линь Данил]] (1.1-1.10, 2.7)

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

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

Алгоритм COBWEB был впервые предложен профессором университета Вандербильта, [[Douglas H. Fisher (Computer Science)|Douglas H. Fisher]] в 1987 году и относится к классу концептуальных алгоритмов кластеризации.

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

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

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

Алгоритм COBWEB – классический метод инкрементальной концептуальной кластеризации. Он создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт и содержит вероятностное описание этого концепта, которое включает в себя вероятность принадлежности концепта к данному узлу и условные вероятности вида: <math>P(A_{j}={\upsilon}_{ij}|C_k)</math>, где <math>A_{i}={\upsilon}_{ij} </math> – пара атрибут-значение, <math>C_{k}</math> – класс концепта.
Узлы, находящейся на определённом уровне дерева классификации, называют срезом. Алгоритм использует для построения дерева классификации эвристическую меру оценки, называемую полезностью категории – прирост ожидаемого числа корректных предположений о значениях атрибутов при знании об их принадлежности к определённой категории относительно ожидаемого числа корректных предположений о значениях атрибутов без этого знания.

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

В алгоритме COBWEB реализовано вероятностное представление категорий. Принадлежность категории определяется не набором значений каждого свойства объекта, а вероятностью появления значения. Например, <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> - это условная вероятность, с которой свойство <math>A_{j}</math>, принимает значение <math>{\upsilon}_{ij}</math>, если объект относится к категории <math>C_{k}</math>. Для каждой категории в иерархии определены вероятности вхождения всех значений каждого свойства. При предъявлении нового экземпляра система COBWEB оценивает качество отнесения этого примера к существующей категории и модификации иерархии категорий в соответствии с новым представителем. Критерием оценки качества классификации является полезность категории (category utility), которая учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий.

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

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

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

<math> CU = \sum_{k} { \sum_{i} { \sum_{j} { {P(A={\upsilon}_{ij}|C_k)} {({P(C_k | A={\upsilon}_{ij})} P(A={\upsilon}_{ij})} } } } </math>

Значения суммируются по всем категориям <math>C_{k}</math>, всем свойствам <math>A_{j}</math> и всем значениям свойств <math>{\upsilon}_{ij}</math>. Значение <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> называется предсказуемостью (predictability). Это вероятность того, что объект, для которого свойство <math>A_{j}</math> - принимает значение <math>{\upsilon}_{ij}</math>, относится к категории <math>C_k</math>. Чем выше это значение, тем вероятнее, что свойства двух объектов, отнесенных к одной категории, имеют одинаковые значения. Величина <math>P(C_k | A={\upsilon}_{ij})</math> называется предиктивностью (predictiveness). Это вероятность того, что для объектов из категории <math>C_k</math> свойство <math>A_j</math> принимает значение <math>{\upsilon}_{ij}</math>. Чем больше эта величина, тем менее вероятно, что для объектов, не относящихся к данной категории, это свойство будет принимать указанное значение. Значение <math>P(A={\upsilon}_{ij}</math> - это весовой коэффициент, усиливающий влияние наиболее распространенных свойств. Благодаря совместному учету этих значений высокая полезность категории означает высокую вероятность того, что объекты из одной категории обладают одинаковыми свойствами, и низкую вероятность наличия этих свойств у объектов из других категорий.

После некоторых преобразований (Байеса в частности) и некоторых агрументированных изменений мы получаем более правильную формулу:

<math>CU= \frac{ \sum_{k=1}^N {P(A={\upsilon}_{ij}|C_k)} \sum_{j} { \sum_{i} {({P(C_k | A={\upsilon}_{ij})}^2 - {P(A={\upsilon}_{ij})}^2)}}}{N} </math>

где N -число категорий.

=== Макроструктура алгоритма ===
[[File:Concept tree.png|thumb|450 px|Простой пример дерева классификации]]

Алгоритм COBEWB создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт. Каждый концепт представляется в виде набора объектов, а объекты являтются бинарными списками. В качестве примера возьмем задачу отнесения особи к определенной биологической группе. Рассмотрим концепт <math>C_1</math>, включающий в себя 4 объекта:

#<code>[1 0 1]</code>
#<code>[0 1 1]</code>
#<code>[0 1 0]</code>
#<code>[0 1 1]</code>

Признаки объекта могут иметь следующий смысл: <code>[мужского_пола, птица, ведущий_ночной_образ_жизни]</code>. Концепт характеризуется целочисленным списком, в котором хранятся суммы соответствующих значений объектов. Для <math>C_1</math> данный счетчик будет <code>[1 3 3]</code>, что означает что биологическая группа включает в себя одну особь мужского пола, три птицы и три особи ведущие ночной образ жизни. Данный счетчик является основанием для вероятностного описания конкретного концепта. Таким образом, вероятность того, что особь, принадлежащая концепту <math>C_1</math>, мужского пола равна <math>1/4 = 0.25</math>, а концепт в целом можно характеризовать как <code>[.25 .75 .75]</code>. Рисунок справа иллюстрирует дерево классификации для 5 концептов. <math>C_0</math> - корневой концепт, включающий в себя все объекты из набора данных. <math>C_1</math> и <math>C_2</math> - концепты-потомки, объединяющие 4 и 6 объектов соответственно. <math>C_2</math> в свою очередь, является концептом-родителем для <math>C_3</math>, <math>C_4</math>, <math>C_5</math>.

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

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

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

<math> O(|C|*|A|*|V|*|O|)</math>, где 

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

=== Информационный граф ===
[[File:Concept tree.png|thumb|450 px|Простой пример дерева классификации]]

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

*[https://github.com/cmaclell/concept_formation Working python implementation of COBWEB] библиотека реализации алгоритмов COBWEB и COBWEB/3 для языка Python.

== Литература ==

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

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

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

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

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

2016-12-01T17:53:15Z

Dlin: /* Информационный граф */

Основные авторы описания: [[Участник:Dlin|Линь Данил]] (1.1-1.10, 2.7)

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

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

Алгоритм COBWEB был впервые предложен профессором университета Вандербильта, [[Douglas H. Fisher (Computer Science)|Douglas H. Fisher]] в 1987 году и относится к классу концептуальных алгоритмов кластеризации.

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

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

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

Алгоритм COBWEB – классический метод инкрементальной концептуальной кластеризации. Он создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт и содержит вероятностное описание этого концепта, которое включает в себя вероятность принадлежности концепта к данному узлу и условные вероятности вида: <math>P(A_{j}={\upsilon}_{ij}|C_k)</math>, где <math>A_{i}={\upsilon}_{ij} </math> – пара атрибут-значение, <math>C_{k}</math> – класс концепта.
Узлы, находящейся на определённом уровне дерева классификации, называют срезом. Алгоритм использует для построения дерева классификации эвристическую меру оценки, называемую полезностью категории – прирост ожидаемого числа корректных предположений о значениях атрибутов при знании об их принадлежности к определённой категории относительно ожидаемого числа корректных предположений о значениях атрибутов без этого знания.

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

В алгоритме COBWEB реализовано вероятностное представление категорий. Принадлежность категории определяется не набором значений каждого свойства объекта, а вероятностью появления значения. Например, <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> - это условная вероятность, с которой свойство <math>A_{j}</math>, принимает значение <math>{\upsilon}_{ij}</math>, если объект относится к категории <math>C_{k}</math>. Для каждой категории в иерархии определены вероятности вхождения всех значений каждого свойства. При предъявлении нового экземпляра система COBWEB оценивает качество отнесения этого примера к существующей категории и модификации иерархии категорий в соответствии с новым представителем. Критерием оценки качества классификации является полезность категории (category utility), которая учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий.

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

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

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

<math> CU = \sum_{k} { \sum_{i} { \sum_{j} { {P(A={\upsilon}_{ij}|C_k)} {({P(C_k | A={\upsilon}_{ij})} P(A={\upsilon}_{ij})} } } } </math>

Значения суммируются по всем категориям <math>C_{k}</math>, всем свойствам <math>A_{j}</math> и всем значениям свойств <math>{\upsilon}_{ij}</math>. Значение <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> называется предсказуемостью (predictability). Это вероятность того, что объект, для которого свойство <math>A_{j}</math> - принимает значение <math>{\upsilon}_{ij}</math>, относится к категории <math>C_k</math>. Чем выше это значение, тем вероятнее, что свойства двух объектов, отнесенных к одной категории, имеют одинаковые значения. Величина <math>P(C_k | A={\upsilon}_{ij})</math> называется предиктивностью (predictiveness). Это вероятность того, что для объектов из категории <math>C_k</math> свойство <math>A_j</math> принимает значение <math>{\upsilon}_{ij}</math>. Чем больше эта величина, тем менее вероятно, что для объектов, не относящихся к данной категории, это свойство будет принимать указанное значение. Значение <math>P(A={\upsilon}_{ij}</math> - это весовой коэффициент, усиливающий влияние наиболее распространенных свойств. Благодаря совместному учету этих значений высокая полезность категории означает высокую вероятность того, что объекты из одной категории обладают одинаковыми свойствами, и низкую вероятность наличия этих свойств у объектов из других категорий.

После некоторых преобразований (Байеса в частности) и некоторых агрументированных изменений мы получаем более правильную формулу:

<math>CU= \frac{ \sum_{k=1}^N {P(A={\upsilon}_{ij}|C_k)} \sum_{j} { \sum_{i} {({P(C_k | A={\upsilon}_{ij})}^2 - {P(A={\upsilon}_{ij})}^2)}}}{N} </math>

где N -число категорий.

=== Макроструктура алгоритма ===
[[File:Concept tree.png|thumb|450 px|Простой пример дерева классификации]]

Алгоритм COBEWB создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт. Каждый концепт представляется в виде набора объектов, а объекты являтются бинарными списками. В качестве примера возьмем задачу отнесения особи к определенной биологической группе. Рассмотрим концепт <math>C_1</math>, включающий в себя 4 объекта:

#<code>[1 0 1]</code>
#<code>[0 1 1]</code>
#<code>[0 1 0]</code>
#<code>[0 1 1]</code>

Признаки объекта могут иметь следующий смысл: <code>[мужского_пола, птица, ведущий_ночной_образ_жизни]</code>. Концепт характеризуется целочисленным списком, в котором хранятся суммы соответствующих значений объектов. Для <math>C_1</math> данный счетчик будет <code>[1 3 3]</code>, что означает что биологическая группа включает в себя одну особь мужского пола, три птицы и три особи ведущие ночной образ жизни. Данный счетчик является основанием для вероятностного описания конкретного концепта. Таким образом, вероятность того, что особь, принадлежащая концепту <math>C_1</math>, мужского пола равна <math>1/4 = 0.25</math>, а концепт в целом можно характеризовать как <code>[.25 .75 .75]</code>. Рисунок справа иллюстрирует дерево классификации для 5 концептов. <math>C_0</math> - корневой концепт, включающий в себя все объекты из набора данных. <math>C_1</math> и <math>C_2</math> - концепты-потомки, объединяющие 4 и 6 объектов соответственно. <math>C_2</math> в свою очередь, является концептом-родителем для <math>C_3</math>, <math>C_4</math>, <math>C_5</math>.

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

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

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

<math> O(|C|*|A|*|V|*|O|)</math>, где 

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

=== Информационный граф ===
[[File:cobweb_grap.jpg]

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

*[https://github.com/cmaclell/concept_formation Working python implementation of COBWEB] библиотека реализации алгоритмов COBWEB и COBWEB/3 для языка Python.

== Литература ==

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

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

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

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

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

2016-12-01T17:50:14Z

Dlin: /* Информационный граф */

Основные авторы описания: [[Участник:Dlin|Линь Данил]] (1.1-1.10, 2.7)

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

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

Алгоритм COBWEB был впервые предложен профессором университета Вандербильта, [[Douglas H. Fisher (Computer Science)|Douglas H. Fisher]] в 1987 году и относится к классу концептуальных алгоритмов кластеризации.

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

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

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

Алгоритм COBWEB – классический метод инкрементальной концептуальной кластеризации. Он создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт и содержит вероятностное описание этого концепта, которое включает в себя вероятность принадлежности концепта к данному узлу и условные вероятности вида: <math>P(A_{j}={\upsilon}_{ij}|C_k)</math>, где <math>A_{i}={\upsilon}_{ij} </math> – пара атрибут-значение, <math>C_{k}</math> – класс концепта.
Узлы, находящейся на определённом уровне дерева классификации, называют срезом. Алгоритм использует для построения дерева классификации эвристическую меру оценки, называемую полезностью категории – прирост ожидаемого числа корректных предположений о значениях атрибутов при знании об их принадлежности к определённой категории относительно ожидаемого числа корректных предположений о значениях атрибутов без этого знания.

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

В алгоритме COBWEB реализовано вероятностное представление категорий. Принадлежность категории определяется не набором значений каждого свойства объекта, а вероятностью появления значения. Например, <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> - это условная вероятность, с которой свойство <math>A_{j}</math>, принимает значение <math>{\upsilon}_{ij}</math>, если объект относится к категории <math>C_{k}</math>. Для каждой категории в иерархии определены вероятности вхождения всех значений каждого свойства. При предъявлении нового экземпляра система COBWEB оценивает качество отнесения этого примера к существующей категории и модификации иерархии категорий в соответствии с новым представителем. Критерием оценки качества классификации является полезность категории (category utility), которая учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий.

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

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

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

<math> CU = \sum_{k} { \sum_{i} { \sum_{j} { {P(A={\upsilon}_{ij}|C_k)} {({P(C_k | A={\upsilon}_{ij})} P(A={\upsilon}_{ij})} } } } </math>

Значения суммируются по всем категориям <math>C_{k}</math>, всем свойствам <math>A_{j}</math> и всем значениям свойств <math>{\upsilon}_{ij}</math>. Значение <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> называется предсказуемостью (predictability). Это вероятность того, что объект, для которого свойство <math>A_{j}</math> - принимает значение <math>{\upsilon}_{ij}</math>, относится к категории <math>C_k</math>. Чем выше это значение, тем вероятнее, что свойства двух объектов, отнесенных к одной категории, имеют одинаковые значения. Величина <math>P(C_k | A={\upsilon}_{ij})</math> называется предиктивностью (predictiveness). Это вероятность того, что для объектов из категории <math>C_k</math> свойство <math>A_j</math> принимает значение <math>{\upsilon}_{ij}</math>. Чем больше эта величина, тем менее вероятно, что для объектов, не относящихся к данной категории, это свойство будет принимать указанное значение. Значение <math>P(A={\upsilon}_{ij}</math> - это весовой коэффициент, усиливающий влияние наиболее распространенных свойств. Благодаря совместному учету этих значений высокая полезность категории означает высокую вероятность того, что объекты из одной категории обладают одинаковыми свойствами, и низкую вероятность наличия этих свойств у объектов из других категорий.

После некоторых преобразований (Байеса в частности) и некоторых агрументированных изменений мы получаем более правильную формулу:

<math>CU= \frac{ \sum_{k=1}^N {P(A={\upsilon}_{ij}|C_k)} \sum_{j} { \sum_{i} {({P(C_k | A={\upsilon}_{ij})}^2 - {P(A={\upsilon}_{ij})}^2)}}}{N} </math>

где N -число категорий.

=== Макроструктура алгоритма ===
[[File:Concept tree.png|thumb|450 px|Простой пример дерева классификации]]

Алгоритм COBEWB создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт. Каждый концепт представляется в виде набора объектов, а объекты являтются бинарными списками. В качестве примера возьмем задачу отнесения особи к определенной биологической группе. Рассмотрим концепт <math>C_1</math>, включающий в себя 4 объекта:

#<code>[1 0 1]</code>
#<code>[0 1 1]</code>
#<code>[0 1 0]</code>
#<code>[0 1 1]</code>

Признаки объекта могут иметь следующий смысл: <code>[мужского_пола, птица, ведущий_ночной_образ_жизни]</code>. Концепт характеризуется целочисленным списком, в котором хранятся суммы соответствующих значений объектов. Для <math>C_1</math> данный счетчик будет <code>[1 3 3]</code>, что означает что биологическая группа включает в себя одну особь мужского пола, три птицы и три особи ведущие ночной образ жизни. Данный счетчик является основанием для вероятностного описания конкретного концепта. Таким образом, вероятность того, что особь, принадлежащая концепту <math>C_1</math>, мужского пола равна <math>1/4 = 0.25</math>, а концепт в целом можно характеризовать как <code>[.25 .75 .75]</code>. Рисунок справа иллюстрирует дерево классификации для 5 концептов. <math>C_0</math> - корневой концепт, включающий в себя все объекты из набора данных. <math>C_1</math> и <math>C_2</math> - концепты-потомки, объединяющие 4 и 6 объектов соответственно. <math>C_2</math> в свою очередь, является концептом-родителем для <math>C_3</math>, <math>C_4</math>, <math>C_5</math>.

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

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

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

<math> O(|C|*|A|*|V|*|O|)</math>, где 

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

=== Информационный граф ===
[[File:cobweb_grap.jpg|thumb|450 px|Выбор операции]]

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

*[https://github.com/cmaclell/concept_formation Working python implementation of COBWEB] библиотека реализации алгоритмов COBWEB и COBWEB/3 для языка Python.

== Литература ==

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

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

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

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

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

2016-12-01T17:43:44Z

Dlin: /* Информационный граф */

Основные авторы описания: [[Участник:Dlin|Линь Данил]] (1.1-1.10, 2.7)

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

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

Алгоритм COBWEB был впервые предложен профессором университета Вандербильта, [[Douglas H. Fisher (Computer Science)|Douglas H. Fisher]] в 1987 году и относится к классу концептуальных алгоритмов кластеризации.

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

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

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

Алгоритм COBWEB – классический метод инкрементальной концептуальной кластеризации. Он создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт и содержит вероятностное описание этого концепта, которое включает в себя вероятность принадлежности концепта к данному узлу и условные вероятности вида: <math>P(A_{j}={\upsilon}_{ij}|C_k)</math>, где <math>A_{i}={\upsilon}_{ij} </math> – пара атрибут-значение, <math>C_{k}</math> – класс концепта.
Узлы, находящейся на определённом уровне дерева классификации, называют срезом. Алгоритм использует для построения дерева классификации эвристическую меру оценки, называемую полезностью категории – прирост ожидаемого числа корректных предположений о значениях атрибутов при знании об их принадлежности к определённой категории относительно ожидаемого числа корректных предположений о значениях атрибутов без этого знания.

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

В алгоритме COBWEB реализовано вероятностное представление категорий. Принадлежность категории определяется не набором значений каждого свойства объекта, а вероятностью появления значения. Например, <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> - это условная вероятность, с которой свойство <math>A_{j}</math>, принимает значение <math>{\upsilon}_{ij}</math>, если объект относится к категории <math>C_{k}</math>. Для каждой категории в иерархии определены вероятности вхождения всех значений каждого свойства. При предъявлении нового экземпляра система COBWEB оценивает качество отнесения этого примера к существующей категории и модификации иерархии категорий в соответствии с новым представителем. Критерием оценки качества классификации является полезность категории (category utility), которая учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий.

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

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

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

<math> CU = \sum_{k} { \sum_{i} { \sum_{j} { {P(A={\upsilon}_{ij}|C_k)} {({P(C_k | A={\upsilon}_{ij})} P(A={\upsilon}_{ij})} } } } </math>

Значения суммируются по всем категориям <math>C_{k}</math>, всем свойствам <math>A_{j}</math> и всем значениям свойств <math>{\upsilon}_{ij}</math>. Значение <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> называется предсказуемостью (predictability). Это вероятность того, что объект, для которого свойство <math>A_{j}</math> - принимает значение <math>{\upsilon}_{ij}</math>, относится к категории <math>C_k</math>. Чем выше это значение, тем вероятнее, что свойства двух объектов, отнесенных к одной категории, имеют одинаковые значения. Величина <math>P(C_k | A={\upsilon}_{ij})</math> называется предиктивностью (predictiveness). Это вероятность того, что для объектов из категории <math>C_k</math> свойство <math>A_j</math> принимает значение <math>{\upsilon}_{ij}</math>. Чем больше эта величина, тем менее вероятно, что для объектов, не относящихся к данной категории, это свойство будет принимать указанное значение. Значение <math>P(A={\upsilon}_{ij}</math> - это весовой коэффициент, усиливающий влияние наиболее распространенных свойств. Благодаря совместному учету этих значений высокая полезность категории означает высокую вероятность того, что объекты из одной категории обладают одинаковыми свойствами, и низкую вероятность наличия этих свойств у объектов из других категорий.

После некоторых преобразований (Байеса в частности) и некоторых агрументированных изменений мы получаем более правильную формулу:

<math>CU= \frac{ \sum_{k=1}^N {P(A={\upsilon}_{ij}|C_k)} \sum_{j} { \sum_{i} {({P(C_k | A={\upsilon}_{ij})}^2 - {P(A={\upsilon}_{ij})}^2)}}}{N} </math>

где N -число категорий.

=== Макроструктура алгоритма ===
[[File:Concept tree.png|thumb|450 px|Простой пример дерева классификации]]

Алгоритм COBEWB создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт. Каждый концепт представляется в виде набора объектов, а объекты являтются бинарными списками. В качестве примера возьмем задачу отнесения особи к определенной биологической группе. Рассмотрим концепт <math>C_1</math>, включающий в себя 4 объекта:

#<code>[1 0 1]</code>
#<code>[0 1 1]</code>
#<code>[0 1 0]</code>
#<code>[0 1 1]</code>

Признаки объекта могут иметь следующий смысл: <code>[мужского_пола, птица, ведущий_ночной_образ_жизни]</code>. Концепт характеризуется целочисленным списком, в котором хранятся суммы соответствующих значений объектов. Для <math>C_1</math> данный счетчик будет <code>[1 3 3]</code>, что означает что биологическая группа включает в себя одну особь мужского пола, три птицы и три особи ведущие ночной образ жизни. Данный счетчик является основанием для вероятностного описания конкретного концепта. Таким образом, вероятность того, что особь, принадлежащая концепту <math>C_1</math>, мужского пола равна <math>1/4 = 0.25</math>, а концепт в целом можно характеризовать как <code>[.25 .75 .75]</code>. Рисунок справа иллюстрирует дерево классификации для 5 концептов. <math>C_0</math> - корневой концепт, включающий в себя все объекты из набора данных. <math>C_1</math> и <math>C_2</math> - концепты-потомки, объединяющие 4 и 6 объектов соответственно. <math>C_2</math> в свою очередь, является концептом-родителем для <math>C_3</math>, <math>C_4</math>, <math>C_5</math>.

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

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

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

<math> O(|C|*|A|*|V|*|O|)</math>, где 

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

=== Информационный граф ===
[[File:cobweb_grap.png|thumb|450 px|Выбор операции]]

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

*[https://github.com/cmaclell/concept_formation Working python implementation of COBWEB] библиотека реализации алгоритмов COBWEB и COBWEB/3 для языка Python.

== Литература ==

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

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

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

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

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

2016-12-01T17:43:07Z

Dlin:

Основные авторы описания: [[Участник:Dlin|Линь Данил]] (1.1-1.10, 2.7)

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

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

Алгоритм COBWEB был впервые предложен профессором университета Вандербильта, [[Douglas H. Fisher (Computer Science)|Douglas H. Fisher]] в 1987 году и относится к классу концептуальных алгоритмов кластеризации.

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

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

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

Алгоритм COBWEB – классический метод инкрементальной концептуальной кластеризации. Он создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт и содержит вероятностное описание этого концепта, которое включает в себя вероятность принадлежности концепта к данному узлу и условные вероятности вида: <math>P(A_{j}={\upsilon}_{ij}|C_k)</math>, где <math>A_{i}={\upsilon}_{ij} </math> – пара атрибут-значение, <math>C_{k}</math> – класс концепта.
Узлы, находящейся на определённом уровне дерева классификации, называют срезом. Алгоритм использует для построения дерева классификации эвристическую меру оценки, называемую полезностью категории – прирост ожидаемого числа корректных предположений о значениях атрибутов при знании об их принадлежности к определённой категории относительно ожидаемого числа корректных предположений о значениях атрибутов без этого знания.

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

В алгоритме COBWEB реализовано вероятностное представление категорий. Принадлежность категории определяется не набором значений каждого свойства объекта, а вероятностью появления значения. Например, <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> - это условная вероятность, с которой свойство <math>A_{j}</math>, принимает значение <math>{\upsilon}_{ij}</math>, если объект относится к категории <math>C_{k}</math>. Для каждой категории в иерархии определены вероятности вхождения всех значений каждого свойства. При предъявлении нового экземпляра система COBWEB оценивает качество отнесения этого примера к существующей категории и модификации иерархии категорий в соответствии с новым представителем. Критерием оценки качества классификации является полезность категории (category utility), которая учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий.

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

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

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

<math> CU = \sum_{k} { \sum_{i} { \sum_{j} { {P(A={\upsilon}_{ij}|C_k)} {({P(C_k | A={\upsilon}_{ij})} P(A={\upsilon}_{ij})} } } } </math>

Значения суммируются по всем категориям <math>C_{k}</math>, всем свойствам <math>A_{j}</math> и всем значениям свойств <math>{\upsilon}_{ij}</math>. Значение <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> называется предсказуемостью (predictability). Это вероятность того, что объект, для которого свойство <math>A_{j}</math> - принимает значение <math>{\upsilon}_{ij}</math>, относится к категории <math>C_k</math>. Чем выше это значение, тем вероятнее, что свойства двух объектов, отнесенных к одной категории, имеют одинаковые значения. Величина <math>P(C_k | A={\upsilon}_{ij})</math> называется предиктивностью (predictiveness). Это вероятность того, что для объектов из категории <math>C_k</math> свойство <math>A_j</math> принимает значение <math>{\upsilon}_{ij}</math>. Чем больше эта величина, тем менее вероятно, что для объектов, не относящихся к данной категории, это свойство будет принимать указанное значение. Значение <math>P(A={\upsilon}_{ij}</math> - это весовой коэффициент, усиливающий влияние наиболее распространенных свойств. Благодаря совместному учету этих значений высокая полезность категории означает высокую вероятность того, что объекты из одной категории обладают одинаковыми свойствами, и низкую вероятность наличия этих свойств у объектов из других категорий.

После некоторых преобразований (Байеса в частности) и некоторых агрументированных изменений мы получаем более правильную формулу:

<math>CU= \frac{ \sum_{k=1}^N {P(A={\upsilon}_{ij}|C_k)} \sum_{j} { \sum_{i} {({P(C_k | A={\upsilon}_{ij})}^2 - {P(A={\upsilon}_{ij})}^2)}}}{N} </math>

где N -число категорий.

=== Макроструктура алгоритма ===
[[File:Concept tree.png|thumb|450 px|Простой пример дерева классификации]]

Алгоритм COBEWB создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт. Каждый концепт представляется в виде набора объектов, а объекты являтются бинарными списками. В качестве примера возьмем задачу отнесения особи к определенной биологической группе. Рассмотрим концепт <math>C_1</math>, включающий в себя 4 объекта:

#<code>[1 0 1]</code>
#<code>[0 1 1]</code>
#<code>[0 1 0]</code>
#<code>[0 1 1]</code>

Признаки объекта могут иметь следующий смысл: <code>[мужского_пола, птица, ведущий_ночной_образ_жизни]</code>. Концепт характеризуется целочисленным списком, в котором хранятся суммы соответствующих значений объектов. Для <math>C_1</math> данный счетчик будет <code>[1 3 3]</code>, что означает что биологическая группа включает в себя одну особь мужского пола, три птицы и три особи ведущие ночной образ жизни. Данный счетчик является основанием для вероятностного описания конкретного концепта. Таким образом, вероятность того, что особь, принадлежащая концепту <math>C_1</math>, мужского пола равна <math>1/4 = 0.25</math>, а концепт в целом можно характеризовать как <code>[.25 .75 .75]</code>. Рисунок справа иллюстрирует дерево классификации для 5 концептов. <math>C_0</math> - корневой концепт, включающий в себя все объекты из набора данных. <math>C_1</math> и <math>C_2</math> - концепты-потомки, объединяющие 4 и 6 объектов соответственно. <math>C_2</math> в свою очередь, является концептом-родителем для <math>C_3</math>, <math>C_4</math>, <math>C_5</math>.

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

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

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

<math> O(|C|*|A|*|V|*|O|)</math>, где 

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

=== Информационный граф ===
[[File:cobweb_graph.png|thumb|450 px|Выбор операции]]

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

*[https://github.com/cmaclell/concept_formation Working python implementation of COBWEB] библиотека реализации алгоритмов COBWEB и COBWEB/3 для языка Python.

== Литература ==

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

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

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

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

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

2016-11-28T17:13:38Z

Dlin:

Основные авторы описания: [[Участник:Dlin|Линь Данил]] (1.1-1.10, 2.7)

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

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

Алгоритм COBWEB был впервые предложен профессором университета Вандербильта, [[Douglas H. Fisher (Computer Science)|Douglas H. Fisher]] в 1987 году и относится к классу концептуальных алгоритмов кластеризации.

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

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

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

Алгоритм COBWEB – классический метод инкрементальной концептуальной кластеризации. Он создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт и содержит вероятностное описание этого концепта, которое включает в себя вероятность принадлежности концепта к данному узлу и условные вероятности вида: <math>P(A_{j}={\upsilon}_{ij}|C_k)</math>, где <math>A_{i}={\upsilon}_{ij} </math> – пара атрибут-значение, <math>C_{k}</math> – класс концепта.
Узлы, находящейся на определённом уровне дерева классификации, называют срезом. Алгоритм использует для построения дерева классификации эвристическую меру оценки, называемую полезностью категории – прирост ожидаемого числа корректных предположений о значениях атрибутов при знании об их принадлежности к определённой категории относительно ожидаемого числа корректных предположений о значениях атрибутов без этого знания.

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

В алгоритме COBWEB реализовано вероятностное представление категорий. Принадлежность категории определяется не набором значений каждого свойства объекта, а вероятностью появления значения. Например, <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> - это условная вероятность, с которой свойство <math>A_{j}</math>, принимает значение <math>{\upsilon}_{ij}</math>, если объект относится к категории <math>C_{k}</math>. Для каждой категории в иерархии определены вероятности вхождения всех значений каждого свойства. При предъявлении нового экземпляра система COBWEB оценивает качество отнесения этого примера к существующей категории и модификации иерархии категорий в соответствии с новым представителем. Критерием оценки качества классификации является полезность категории (category utility), которая учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий.

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

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

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

<math> CU = \sum_{k} { \sum_{i} { \sum_{j} { {P(A={\upsilon}_{ij}|C_k)} {({P(C_k | A={\upsilon}_{ij})} P(A={\upsilon}_{ij})} } } } </math>

Значения суммируются по всем категориям <math>C_{k}</math>, всем свойствам <math>A_{j}</math> и всем значениям свойств <math>{\upsilon}_{ij}</math>. Значение <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> называется предсказуемостью (predictability). Это вероятность того, что объект, для которого свойство <math>A_{j}</math> - принимает значение <math>{\upsilon}_{ij}</math>, относится к категории <math>C_k</math>. Чем выше это значение, тем вероятнее, что свойства двух объектов, отнесенных к одной категории, имеют одинаковые значения. Величина <math>P(C_k | A={\upsilon}_{ij})</math> называется предиктивностью (predictiveness). Это вероятность того, что для объектов из категории <math>C_k</math> свойство <math>A_j</math> принимает значение <math>{\upsilon}_{ij}</math>. Чем больше эта величина, тем менее вероятно, что для объектов, не относящихся к данной категории, это свойство будет принимать указанное значение. Значение <math>P(A={\upsilon}_{ij}</math> - это весовой коэффициент, усиливающий влияние наиболее распространенных свойств. Благодаря совместному учету этих значений высокая полезность категории означает высокую вероятность того, что объекты из одной категории обладают одинаковыми свойствами, и низкую вероятность наличия этих свойств у объектов из других категорий.

После некоторых преобразований (Байеса в частности) и некоторых агрументированных изменений мы получаем более правильную формулу:

<math>CU= \frac{ \sum_{k=1}^N {P(A={\upsilon}_{ij}|C_k)} \sum_{j} { \sum_{i} {({P(C_k | A={\upsilon}_{ij})}^2 - {P(A={\upsilon}_{ij})}^2)}}}{N} </math>

где N -число категорий.

=== Макроструктура алгоритма ===
[[File:Concept tree.png|thumb|450 px|Простой пример дерева классификации]]

Алгоритм COBEWB создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт. Каждый концепт представляется в виде набора объектов, а объекты являтются бинарными списками. В качестве примера возьмем задачу отнесения особи к определенной биологической группе. Рассмотрим концепт <math>C_1</math>, включающий в себя 4 объекта:

#<code>[1 0 1]</code>
#<code>[0 1 1]</code>
#<code>[0 1 0]</code>
#<code>[0 1 1]</code>

Признаки объекта могут иметь следующий смысл: <code>[мужского_пола, птица, ведущий_ночной_образ_жизни]</code>. Концепт характеризуется целочисленным списком, в котором хранятся суммы соответствующих значений объектов. Для <math>C_1</math> данный счетчик будет <code>[1 3 3]</code>, что означает что биологическая группа включает в себя одну особь мужского пола, три птицы и три особи ведущие ночной образ жизни. Данный счетчик является основанием для вероятностного описания конкретного концепта. Таким образом, вероятность того, что особь, принадлежащая концепту <math>C_1</math>, мужского пола равна <math>1/4 = 0.25</math>, а концепт в целом можно характеризовать как <code>[.25 .75 .75]</code>. Рисунок справа иллюстрирует дерево классификации для 5 концептов. <math>C_0</math> - корневой концепт, включающий в себя все объекты из набора данных. <math>C_1</math> и <math>C_2</math> - концепты-потомки, объединяющие 4 и 6 объектов соответственно. <math>C_2</math> в свою очередь, является концептом-родителем для <math>C_3</math>, <math>C_4</math>, <math>C_5</math>.

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

COBWEB(root, record):
Input: A COBWEB node root, an instance to insert record
if root has no children then
children := {copy(root)}
newcategory(record) \\ adds child with record’s feature values.
insert(record, root) \\ update root’s statistics
else
insert(record, root)
for child in root’s children do
calculate Category Utility for insert(record, child),
set best1, best2 children w. best CU.
end for
if newcategory(record) yields best CU then
newcategory(record)
else if merge(best1, best2) yields best CU then
merge(best1, best2)
COBWEB(root, record)
else if split(best1) yields best CU then
split(best1)
COBWEB(root, record)
else
COBWEB(best1, record)
end if
end

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

<math> O(|C|*|A|*|V|*|O|)</math>, где 

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

*[https://github.com/cmaclell/concept_formation Working python implementation of COBWEB] библиотека реализации алгоритмов COBWEB и COBWEB/3 для языка Python.

== Литература ==

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

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

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

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

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

2016-11-28T14:22:50Z

Dlin:

Основные авторы описания: [[Участник:Dlin|Линь Данил]] (1.1-1.10, 2.7)

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

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

Алгоритм COBWEB был впервые предложен профессором университета Вандербильта, [[Douglas H. Fisher (Computer Science)|Douglas H. Fisher]] в 1987 году и относится к классу концептуальных алгоритмов кластеризации.

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

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

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

Алгоритм COBWEB [12] – классический метод инкрементальной концептуальной кластеризации. Он создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт и содержит вероятностное описание этого концепта, которое включает в себя вероятность принадлежности концепта к данному узлу и условные вероятности вида: P(Ai = vij|Ck), где Ai = vij – пара атрибут-значение, Ck – класс концепта.
Узлы, находящейся на определённом уровне дерева классификации, называют срезом. Алгоритм использует для построения дерева классификации эвристическую меру оценки, называемую полезностью категории – прирост ожидаемого числа корректных предположений о значениях атрибутов при знании об их принадлежности к определённой категории относительно ожидаемого числа корректных предположений о значениях атрибутов без этого знания. Чтобы встроить новый объект в дерево классификации, алгоритм COBWEB итеративно проходит всё дерево в поисках «лучшего» узла, к которому отнести этот объект. Выбор узла осуществляется на основе помещения объекта в каждый узел и вычисления полезности категории получившегося среза. Также вычисляется полезность категории для случая, когда объект относится к вновь создаваемому узлу. В итоге объект относится к тому узлу, для которого полезность категории больше.

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

В алгоритме COBWEB реализовано вероятностное представление категорий. Принадлежность категории определяется не набором значений каждого свойства объекта, а вероятностью появления значения. Например, <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> - это условная вероятность, с которой свойство <math>A_{j}</math>, принимает значение <math>{\upsilon}_{ij}</math>, если объект относится к категории <math>C_{k}</math>. Для каждой категории в иерархии определены вероятности вхождения всех значений каждого свойства. При предъявлении нового экземпляра система COBWEB оценивает качество отнесения этого примера к существующей категории и модификации иерархии категорий в соответствии с новым представителем. Критерием оценки качества классификации является полезность категории (category utility). Критерий полезности категории был определен при исследовании человеческой категоризации. Он учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий.

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

<math> CU = \sum_{k} { \sum_{i} { \sum_{j} { {P(A={\upsilon}_{ij}|C_k)} {({P(C_k | A={\upsilon}_{ij})} P(A={\upsilon}_{ij})} } } } </math>

Значения суммируются по всем категориям <math>C_{k}</math>, всем свойствам <math>A_{j}</math> и всем значениям свойств <math>{\upsilon}_{ij}</math>. Значение <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> называется предсказуемостью (predictability). Это вероятность того, что объект, для которого свойство <math>A_{j}</math> - принимает значение <math>{\upsilon}_{ij}</math>, относится к категории <math>C_k</math>. Чем выше это значение, тем вероятнее, что свойства двух объектов, отнесенных к одной категории, имеют одинаковые значения. Величина <math>P(C_k | A={\upsilon}_{ij})</math> называется предиктивностью (predictiveness). Это вероятность того, что для объектов из категории <math>C_k</math> свойство <math>A_j</math> принимает значение <math>{\upsilon}_{ij}</math>. Чем больше эта величина, тем менее вероятно, что для объектов, не относящихся к данной категории, это свойство будет принимать указанное значение. Значение <math>P(A={\upsilon}_{ij}</math> - это весовой коэффициент, усиливающий влияние наиболее распространенных свойств. Благодаря совместному учету этих значений высокая полезность категории означает высокую вероятность того, что объекты из одной категории обладают одинаковыми свойствами, и низкую вероятность наличия этих свойств у объектов из других категорий.

После некоторых преобразований (Байеса в частности) и некоторых агрументированных изменений мы получаем более правильную формулу:

<math>CU= \frac{ \sum_{k=1}^N {P(A={\upsilon}_{ij}|C_k)} \sum_{j} { \sum_{i} {({P(C_k | A={\upsilon}_{ij})}^2 - {P(A={\upsilon}_{ij})}^2)}}}{N} </math>

где N -число категорий.

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

=== Макроструктура алгоритма ===
[[File:Concept tree.png|thumb|450 px|Простой пример дерева классификации]]

Алгоритм COBEWB создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт. Каждый концепт представляется в виде набора объектов, а объекты являтются бинарными списками. В качестве примера возьмем задачу отнесения особи к определенной биологической группе. Рассмотрим концепт <math>C_1</math>, включающий в себя 4 объекта:

#<code>[1 0 1]</code>
#<code>[0 1 1]</code>
#<code>[0 1 0]</code>
#<code>[0 1 1]</code>

Признаки объекта могут иметь следующий смысл: <code>[мужского_пола, птица, ведущий_ночной_образ_жизни]</code>. Концепт характеризуется целочисленным списком, в котором хранятся суммы соответствующих значений объектов. Для <math>C_1</math> данный счетчик будет <code>[1 3 3]</code>, что означает что биологическая группа включает в себя одну особь мужского пола, три птицы и три особи ведущие ночной образ жизни. Данный счетчик является основанием для вероятностного описания конкретного концепта. Таким образом, вероятность того, что особь, принадлежащая концепту <math>C_1</math>, мужского пола равна <math>1/4 = 0.25</math>, а концепт в целом можно характеризовать как <code>[.25 .75 .75]</code>. Рисунок справа иллюстрирует дерево классификации для 5 концептов. <math>C_0</math> - корневой концепт, включающий в себя все объекты из набора данных. <math>C_1</math> и <math>C_2</math> - концепты-потомки, объединяющие 4 и 6 объектов соответственно. <math>C_2</math> в свою очередь, является концептом-родителем для <math>C_3</math>, <math>C_4</math>, <math>C_5</math>.
=== Схема реализации последовательного алгоритма ===

COBWEB(root, record):
Input: A COBWEB node root, an instance to insert record
if root has no children then
children := {copy(root)}
newcategory(record) \\ adds child with record’s feature values.
insert(record, root) \\ update root’s statistics
else
insert(record, root)
for child in root’s children do
calculate Category Utility for insert(record, child),
set best1, best2 children w. best CU.
end for
if newcategory(record) yields best CU then
newcategory(record)
else if merge(best1, best2) yields best CU then
merge(best1, best2)
COBWEB(root, record)
else if split(best1) yields best CU then
split(best1)
COBWEB(root, record)
else
COBWEB(best1, record)
end if
end

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

== Литература ==
<references />

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

2016-11-28T13:51:51Z

Dlin:

Основные авторы описания: [[Участник:Dlin|Линь Данил]] (1.1-1.10, 2.7)

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

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

Алгоритм COBWEB был впервые предложен профессором университета Вандербильта, [[Douglas H. Fisher (Computer Science)|Douglas H. Fisher]] в 1987 году и относится к классу концептуальных алгоритмов кластеризации.

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

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

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

Алгоритм COBWEB [12] – классический метод инкрементальной концептуальной кластеризации. Он создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт и содержит вероятностное описание этого концепта, которое включает в себя вероятность принадлежности концепта к данному узлу и условные вероятности вида: P(Ai = vij|Ck), где Ai = vij – пара атрибут-значение, Ck – класс концепта.
Узлы, находящейся на определённом уровне дерева классификации, называют срезом. Алгоритм использует для построения дерева классификации эвристическую меру оценки, называемую полезностью категории – прирост ожидаемого числа корректных предположений о значениях атрибутов при знании об их принадлежности к определённой категории относительно ожидаемого числа корректных предположений о значениях атрибутов без этого знания. Чтобы встроить новый объект в дерево классификации, алгоритм COBWEB итеративно проходит всё дерево в поисках «лучшего» узла, к которому отнести этот объект. Выбор узла осуществляется на основе помещения объекта в каждый узел и вычисления полезности категории получившегося среза. Также вычисляется полезность категории для случая, когда объект относится к вновь создаваемому узлу. В итоге объект относится к тому узлу, для которого полезность категории больше.

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

В алгоритме COBWEB реализовано вероятностное представление категорий. Принадлежность категории определяется не набором значений каждого свойства объекта, а вероятностью появления значения. Например, <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> - это условная вероятность, с которой свойство <math>A_{j}</math>, принимает значение <math>{\upsilon}_{ij}</math>, если объект относится к категории <math>C_{k}</math>. Для каждой категории в иерархии определены вероятности вхождения всех значений каждого свойства. При предъявлении нового экземпляра система COBWEB оценивает качество отнесения этого примера к существующей категории и модификации иерархии категорий в соответствии с новым представителем. Критерием оценки качества классификации является полезность категории (category utility). Критерий полезности категории был определен при исследовании человеческой категоризации. Он учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий.

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

<math> CU = \sum_{k} { \sum_{i} { \sum_{j} { {P(A={\upsilon}_{ij}|C_k)} {({P(C_k | A={\upsilon}_{ij})} P(A={\upsilon}_{ij})} } } } </math>

Значения суммируются по всем категориям <math>C_{k}</math>, всем свойствам <math>A_{j}</math> и всем значениям свойств <math>{\upsilon}_{ij}</math>. Значение <math>P(A_{j}={\upsilon}_{ij}|C_k)</math> называется предсказуемостью (predictability). Это вероятность того, что объект, для которого свойство <math>A_{j}</math> - принимает значение <math>{\upsilon}_{ij}</math>, относится к категории <math>C_k</math>. Чем выше это значение, тем вероятнее, что свойства двух объектов, отнесенных к одной категории, имеют одинаковые значения. Величина <math>P(C_k | A={\upsilon}_{ij})</math> называется предиктивностью (predictiveness). Это вероятность того, что для объектов из категории <math>C_k</math> свойство <math>A_j</math> принимает значение <math>{\upsilon}_{ij}</math>. Чем больше эта величина, тем менее вероятно, что для объектов, не относящихся к данной категории, это свойство будет принимать указанное значение. Значение <math>P(A={\upsilon}_{ij}</math> - это весовой коэффициент, усиливающий влияние наиболее распространенных свойств. Благодаря совместному учету этих значений высокая полезность категории означает высокую вероятность того, что объекты из одной категории обладают одинаковыми свойствами, и низкую вероятность наличия этих свойств у объектов из других категорий.

После некоторых преобразований (Байеса в частности) и некоторых агрументированных изменений мы получаем более правильную формулу:

<math>CU= \frac{ \sum_{k=1}^N {P(A={\upsilon}_{ij}|C_k)} \sum_{j} { \sum_{i} {({P(C_k | A={\upsilon}_{ij})}^2 - {P(A={\upsilon}_{ij})}^2)}}}{N} </math>

где N -число категорий.

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

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

Алгоритм COBEWB создаёт иерархическую кластеризацию в виде дерева классификации: каждый узел этого дерева ссылается на концепт. Каждый концепт представляется в виде набора объектов, а объекты являтются бинарными списками. В качестве примера возьмем задачу отнесения особи к определенной биологической группе. Рассмотрим концепт <math>C_1</math>, включающий в себя 4 объекта:

[[File:Concept tree.png|thumb|450 px|Sample COBWEB knowledge representation, probabilistic concept hierarchy. Blue boxes list actual objects, purple boxes list attribute counts. See text for details. '''Note''': The diagram is intended to be illustrative only of COBWEB's data structure; it does not necessarily represent a "good" concept tree, or one that COBWEB would actually construct from real data.]]
#<code>[1 0 1]</code>
#<code>[0 1 1]</code>
#<code>[0 1 0]</code>
#<code>[0 1 1]</code>

Признаки объекта могут иметь следующий смысл: <code>[мужского_пола, птица, ведущий_ночной_образ_жизни]</code>. Концепт характеризуется целочисленным списком, в котором хранятся суммы соответствующих значений объектов. Для <math>C_1</math> данный счетчик будет <code>[1 3 3]</code>, что означает что биологическая группа включает в себя одну особь мужского пола, три птицы и три особи ведущие ночной образ жизни.Данный счетчик является основанием для вероятностного описания конкретного концепта.
=== Схема реализации последовательного алгоритма ===

COBWEB(root, record):
Input: A COBWEB node root, an instance to insert record
if root has no children then
children := {copy(root)}
newcategory(record) \\ adds child with record’s feature values.
insert(record, root) \\ update root’s statistics
else
insert(record, root)
for child in root’s children do
calculate Category Utility for insert(record, child),
set best1, best2 children w. best CU.
end for
if newcategory(record) yields best CU then
newcategory(record)
else if merge(best1, best2) yields best CU then
merge(best1, best2)
COBWEB(root, record)
else if split(best1) yields best CU then
split(best1)
COBWEB(root, record)
else
COBWEB(best1, record)
end if
end

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

== Литература ==
<references />

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

2016-11-06T17:40:11Z

Dlin:

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

2016-11-06T16:11:23Z

Dlin: Новая страница: «Основные авторы описания: Линь Данил (1.1-1.10, 2.7) == Свойства и структура алго…»