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

COBWEB

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

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

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

Для решения многих практических задач в настоящее время используется концептуальная кластеризация данных, ярким представителем которой является метод COBWEB. Алгоритм 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 итеративно проходит всё дерево в поисках «лучшего» узла, к которому отнести этот объект. Выбор узла осуществляется на основе помещения объекта в каждый узел и вычисления полезности категории получившегося среза. Также вычисляется полезность категории для случая, когда объект относится к вновь создаваемому узлу. В итоге объект относится к тому узлу, для которого полезность категории больше.

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] приписывается номер кластера[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). Критерий полезности категории был определен при исследовании человеческой категоризации. Он учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий. Критерий полезности категории максимизирует вероятность того, что два объекта, отнесенные к одной категории, имеют одинаковые значения свойств и значения свойств для объектов из различных категорий отличаются. обозначим через – множество распознаваемых объектов, характеризуемое бинарными параметрами , принимаемыми одно из возможных значений . – множество формируемых кластеров, где n – заранее неизвестно. Полезность кластеризации в методе COBWEB рассматривается как функция CU, определяющая сходство объектов в рамках одного кластера, и их различие по отношению к объектам из других кластеров. Внутриклассовое сходство определяется условной вероятностью , а межклассовое сходство условной вероятностью . Функция полезности кластеризации определяется в виде (*CU HERE*), где n – количество кластеров.

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

Метод COBWEB строит дерево классификации с вероятностными описаниями концептов. Выбор возможного способа кластеризации объектов основан на значениях функции полезности кластеризации. При построении дерева классификации используются следующие 4 операции:

• отнесение объекта к наилучшему из существующих кластеров
• добавление нового кластера, содержащего единственный объект
• слияние двух существующих кластеров в один новый с добавлением в нее этого объекта
• разбиение существующего кластера на два и отнесение объекта к лучшему из вновь созданных кластеров

Модель концептуальной кластеризации

Пошаговое описание метода концептуальной кластеризации:

1. Шаблон:Anchor Вводится корневой кластер С0, свойства которого совпадают со свойствами первого объекта О1 = [V11, …, V1m]. Для каждого последующего объекта Оi = [Vi1, …, Vim] выполняется цикл, реализующий шаги 2‒6, в рамках которых выполняются 4 выше представленные операции.
2. Шаблон:Anchor Объект Оi добавляется поочередно в кластеры С1, C2,…, Сk. После каждого добавления вычисляется полезность кластеризации СU1,…, СUk.
3. Шаблон:Anchor Для объекта Оi создается новый кластер Сk + 1, объект помещается в кластер и вычисляется полезность кластеризации CUk + 1.

4# Шаблон:Anchor Объединяются два кластера с максимальными значением полезности кластеризации из СU1, …, СUk. Образуется новый кластер, в него добавляется объект Оi. Вычисляется полезность кластеризации CUk + 2.

1. Шаблон:Anchor Объект Оi добавляется в кластер с максимальным значением полезности кластеризации из СU1 ,…, СUk. Образуется новый кластер с двумя кластерами-потомками. Вычисляется полезность кластеризации CUk + 3.
2. Шаблон:Anchor Выбирается максимальное значение полезности кластеризации среди полезностей СU1,…, СUk,CUk + 1, CUk + 2, CUk + 3, в соответствии с ним выбирается операция разбиения объектов по кластерам.