Алгоритм Cobweb

Концептуальные алгоритмы

Алгоритм EM

Модельные алгоритмы

Модельные алгоритмы подразумевают, что у нас есть некоторая модель кластера (его структуры), и мы стремимся найти и максимизировать сходства между этой моделью и имеющимися у нас данными, то есть выделить в данных такие модели, которые и будут кластерами. Часто при этом для представления моделей используется широко разработанный аппарат математической статистики.

Предполагается, что кроме известных нам из наших данных величин существуют еще и неизвестные нам, относящиеся к распределению по кластерам. То есть фактически эти неизвестные "создают" кластер, а мы наблюдаем только результат их деятельности. И именно эти неизвестные мы и стараемся максимально точно оценить.

Алгоритм использует широко известный метод максимизации ожиданий (Expectation Maximization). В наиболее простом случае предполагается, что кластер - это результаты наблюдений, распределенные нормально. Тогда для их характеристики можно применять многомерную функцию Гаусса (многомерное распределение Гаусса) - одно из распределений. И тогда основная задача - это определить, к какому из распределений принадлежит каждая конкретная точка, оценив параметры этих распределений исходя из реального распределения точек.

0. Инициализируем : - среднее отклонение распределений относительно начала координат (т.е. центры кластеров) и вероятности этих распределений для каждой точки. K - число кластеров - задаем.

1. E-шаг:

где -функция плотности распределения.

2. М-шаг:

3. Вычисление и сравнение с P(x_i | μ_j)^t, если да, то стоп - найден локальный максимум. Если нет, то переходим снова к шагу 1.

В алгоритме COBWEB реализовано вероятностное представление категорий. Принадлежность категории определяется не набором значений каждого свойства объекта, а вероятностью появления значения. Например, P(A_j = υ_ij | C_k) - это условная вероятность, с которой свойство A_j, принимает значение υ_ij, если объект относится к категории C_k. Для каждой категории в иерархии определены вероятности вхождения всех значений каждого свойства. При предъявлении нового экземпляра система COBWEB оценивает качество отнесения этого примера к существующей категории и модификации иерархии категорий в соответствии с новым представителем. Критерием оценки качества классификации является полезность категории (category utility). Критерий полезности категории был определен при исследовании человеческой категоризации. Он учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий.

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

CU =	∑	∑	∑	P(A = υ_ij \| C_k)P(C_k \| A = υ_ij)P(A = υ_ij)
	k	i	j

Значения суммируются по всем категориям C_k, всем свойствам A_j и всем значениям свойств υ_ij. Значение P(A_j = υ_ij | C_k) называется предсказуемостью (predictability). Это вероятность того, что объект, для которого свойство A_j- принимает значение υ_ij, относится к категории C_k. Чем выше это значение, тем вероятнее, что свойства двух объектов, отнесенных к одной категории, имеют одинаковые значения. Величина P(C_k | A = υ_ij) называется предиктивностью (predictiveness). Это вероятность того, что для объектов из категории C_k свойство A_j принимает значение υ_ij. Чем больше эта величина, тем менее вероятно, что для объектов, не относящихся к данной категории, это свойство будет принимать указанное значение. Значение P(A = υ_ij) - это весовой коэффициент, усиливающий влияние наиболее распространенных свойств. Благодаря совместному учету этих значений высокая полезность категории означает высокую вероятность того, что объекты из одной категории обладают одинаковыми свойствами, и низкую вероятность наличия этих свойств у объектов из других категорий.

После некоторых преобразований (Байеса в частности) и некоторых агрументированных изменений мы получаем более правильную формулу:

N -число категорий.

Алгоритм COBWEB имеет следующий вид.

cobweb(Node, Instance) Begin if узел Node - это лист, then begin создать два дочерних узла L₁ и L₂ для узла Node; задать для узла L₁ те же вероятности, что и для узла Node; инициализировать вероятности для узла L₂ соответствующими значениями объекта Instance; добавить Instance к Node, обновив вероятности для узла Node ; end else begin добавить Instance к Node, обновив вероятности для узла Node; для каждого дочернего узла С узла Node вычислить полезность категории при отнесении экземпляра Instance к категории С; пусть S₁ - значение полезности для наилучшей классификации C₁; пусть S₂ - значение для второй наилучшей классификации C₂; пусть S₃ - значение полезности для отнесения экземпляра к новой категории; пусть S₄ - значение для слияния C₁ и C₂ в одну категорию; пусть S₅ - значение для разделения C₁ (замены дочерними категориями); end if S₁ - максимальное значение CU, then cobweb(C₁, Instance) %отнести экземпляр к C₁ else if S₃ - максимальное значение CU, then инициализировать вероятности для новой категории C_m значениями Instance else if S₄ - максимальное значение CU, then begin пусть C_m - результат слияния C₁ и C₂; cobweb(C_m, Instance); end else if S₅ - максимальное значение CU, then begin разделить C₁; % C_m - новая категория cobweb(C_m, Instance) end; end

В алгоритме COBWEB реализован метод поиска экстремума в пространстве возможных кластеров с использованием критерия полезности категорий для оценки и выбора возможных способов категоризации.

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

Отнесение экземпляра к наилучшей из существующих категорий.

Добавление новой категории, содержащей единственный экземпляр.

Слияние двух существующих категорий в одну новую с добавлением в нее этого экземпляра.

Разбиение существующей категории на две и отнесение экземпляра к лучшей из вновь созданных категорий.

Для слияния двух узлов создается новый узел, для которого существующие узлы становятся дочерними. На основе значений вероятностей дочерних узлов вычисляются вероятности для нового узла. При разбиении один узел заменяется двумя дочерними.

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