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

Основные авторы описания: Линь Данил (1.1-1.10, 2.7)

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

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

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

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

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

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

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

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

В алгоритме 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), которая учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий.

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

Чтобы встроить новый объект в дерево классификации, алгоритм 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 -число категорий.

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

Простой пример дерева классификации

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

1. [1 0 1]
2. [0 1 1]
3. [0 1 0]
4. [0 1 1]

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

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

 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

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

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

[math] O(|C|*|A|*|V|*|O|)[/math], где

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

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

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

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

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

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

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

• Working python implementation of COBWEB библиотека реализации алгоритмов COBWEB и COBWEB/3 для языка Python.

3 Литература

[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/