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

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

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

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

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

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

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

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

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.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 достаточно эффективен и выполняет кластеризацию на разумное число классов. Поскольку в нем используется вероятностное представление принадлежности, получаемые категории являются гибкими и робастными. Кроме того, в нем проявляется эффект категорий базового уровня, поддерживается прототипирование и учитывается степень принадлежности. Он основан не на классической логике, а, подобно методам теории нечетких множеств, учитывает "неопределенность" категоризации как необходимый компонент обучения и рассуждений в гибкой и интеллектуальной манере.