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

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

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

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

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

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

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

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

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

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

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

[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 объекта:

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.

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

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

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.10 Свойства алгоритма

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