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

COBWEB

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

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

Задача кластеризации – частный случай задачи обучения без учителя, которая сводится к разбиению имеющегося множества объектов данных на подмножества таким образом, что элементы одного подмножества существенно отличались по некоторому набору свойств от элементов всех других подмножеств. Объект данных обычно рассматривается как точка в многомерном метрическом пространстве, каждому измерению которого соответствует некоторое свойство (атрибут) объекта, а метрика – есть функция от значений данных свойств. От типов измерений этого пространства, которые могут быть как числовыми, так и категориальными, зависит выбор алгоритма кластеризации данных и используемая метрика. Этот выбор продиктован различиями в природе разных типов атрибутов. Кластерный анализ выполняет следующие основные задачи: Разработка типологии или классификации. Исследование полезных концептуальных схем группирования объектов. Порождение гипотез на основе исследования данных. Проверка гипотез или исследования для определения, действительно ли типы (группы), выделенные тем или иным способом, присутствуют в имеющихся данных.

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

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

Пусть [math]{\displaystyle X}[/math] — множество объектов, [math]{\displaystyle Y}[/math] — множество номеров (имён, меток) кластеров. Задана функция расстояния между объектами [math]{\displaystyle \rho (x,x')}[/math]. Имеется конечная обучающая выборка объектов [math]{\displaystyle X^{m}=\{x_{1},\dots ,x_{m}\}\subset X}[/math]. Требуется разбить выборку на непересекающиеся подмножества, называемыекластерами, так, чтобы каждый кластер состоял из объектов, близких по метрике [math]{\displaystyle \rho }[/math], а объекты разных кластеров существенно отличались. При этом каждому объекту [math]{\displaystyle x_{i}\in X^{m}}[/math] приписывается номер кластера {\displaystyle y_{i}}</math>. Алгоритм кластеризации — это функция [math]{\displaystyle a\colon X\to Y}[/math], которая любому объекту [math]{\displaystyle x\in X}[/math] ставит в соответствие номер кластера [math]{\displaystyle y\in Y}[/math]. Множество [math]{\displaystyle Y}[/math] в некоторых случаях известно заранее, однако чаще ставится задача определить оптимальное число кластеров, с точки зрения того или иного критерия качества кластеризации. В алгоритме COBWEB реализовано вероятностное представление категорий. Принадлежность категории определяется не набором значений каждого свойства объекта, а вероятностью появления значения. Например, [math]{\displaystyle P(A_{j}=u_{ij}|C_{k})}[/math] - это условная вероятность, с которой свойство [math]{\displaystyle A_{j}}[/math], принимает значение [math]{\displaystyle u_{ij}}[/math], если объект относится к категории [math]{\displaystyle C_{k}}[/math]. Для каждой категории в иерархии определены вероятности вхождения всех значений каждого свойства. При предъявлении нового экземпляра система COBWEB оценивает качество отнесения этого примера к существующей категории и модификации иерархии категорий в соответствии с новым представителем. Критерием оценки качества классификации является полезность категории (category utility). Критерий полезности категории был определен при исследовании человеческой категоризации. Он учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий.