10.3. Иерархическая структура многообразия алгоритмов АК

В данной модели алгоритма АК одни и те же множества и L могут быть получены для различных конкретизаций множеств Z и соответственно. Таким образом, в рамках данной модели алгоритма АК элементы ее структуры являются варьируемыми параметрами. Покажем, как эти параметры позволяют восстанавливать иерархическую структуру многообразия алгоритмов.

10.3.1. Модель алгоритма k-средних параллельного типа.

Пусть . Для простоты будем считать, что -мерное евклидово пространство наделено стандартной метрикой: где — координаты векторов X и Y соответственно.

В качестве первой конкретизации множества Z возьмем список номеров классов Положим и будем отождествлять каждое отображение с разбиением множества О на классы где Имеем: Каждый класс будем описывать его средним, т. е. в качестве возьмем само пространство и положим

Таким образом и потому в L можно ввести метрику следующим образом: где

Так как строим модель алгоритма параллельного типа, то в качестве Р должны взять одноэлементное множество (выборка О вся участвует в классификации на каждом шаге), поэтому в дальнейших формулах компоненты Р и G модели можно не учитывать. Операторы К. и D возьмем, следуя базисной модели ядерного алгоритма с Детальное описание этих операторов дано в п. 7.2.1. Непосредственно из конструкции этих операторов следует, что функционал

где является интерпретирующим для этой модели (см. §. 10.4). Итак, модель алгоритма -средних параллельного типа описана. Начнем модификацию ее параметров.

10.3.2. Модель алгоритма (k-r)-средних.

Эта модель связана с введением класса «джокер» (см. § 10.2). Задается «порог отказа» , и если значение меры сходства объекта X с каждым из k ядер классов превосходит , то такой объект относится к символическому классу

Итак,

В этом случае точно такое же, как в алгоритме -средних.

Далее, — объединение пространства и изолированной точки . В качестве L возьмем часть множества отображений в , состоящую из всех отображений, переводящих символ Тогда каждая точка будет иметь вид

Операторы К и D зададим формулами (10.13) и (10.14) соответственно с

Имеем:

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

(10.18)

является интерпретирующим для этой модели.

Можно подвести первые итоги.

Получение модели алгоритма -средних иллюстрирует подъем снизу вверх в описываемой иерархии. Действительно, отправляясь от модели 10.3.1, получаем данную модель с дополнительным параметром Утверждение, что модель 10.3.2 лежит выше по иерархии, чем модель 10.3.1, обосновывается тем, что, отправляясь от модели 10.3.2 и устремляя очевидно, получим модель 10.3.1.

10.3.3. Модель алгоритма Форель.

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

Применение алгоритма Форель опирается на гипотезу: выборка О представляет собой объединение , где — компактный кластер, ядро которого совпадает с его геометрическим центром, а точки из лежат на достаточном удалении от кластера . Следующая модель описывает алгоритмы, опирающиеся на аналогичную гипотезу в предположении, что ядро компактного кластера совпадает с взвешенным центром.

10.3.4. Модель алгоритма выделения размытого кластера.

Параметром модели является невозрастающая функция , такая, что . В этой модели и пространство допустимых классификаций имеет вид для некоторого Согласно терминологии теории размытых множеств (см. п. 7.5.1) каждая такая классификация s задает размытый класс в О. Класс описывается точкой из (формальным элементом, как и в алгоритме Форель), т. е. Разброс класса относительно ядра задается формулой

Для завершения описания модели осталось указать операторы К. и D. Пусть на шаге алгоритма получен размытый класс и его ядро . Тогда

т. е.

Здесь — описание класса Для получения из данного алгоритма алгоритма 10.3.3 иадо спуститься вниз по иерархии, положив

10.3.5. Модель алгоритма -средних.

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

Обозначим через стандартный -мерный симплекс, т. е. множество точек . Пронумеруем вершины симплекса так, чтобы вершина имела координаты где 1 стоит на месте. Теперь в качестве второй конкретизации множества Z в модели 10.3.1 возьмем симплекс . Тогда из этой модели можно отождествить с частью множества отображений из О в , состоящего из всех отображений, переводящих О в подмножество вершин

Каждую точку можно однозначно записать в виде где Поэтому каждое линейное отображение т. е. такое отображение, что однозначно определяется набором образов вершин Следовательно, в новой конкретизации множества Z модели 10.3.1 множество L можно отождествить с множеством всех линейных отображений из

В новой интерпретации множеств и L функционал {10.17) можно записать в виде

(10.19)

где если — в противном случае, a Тогда согласно общей схеме оптимизационного подхода к построению операторов К. и D (см. формулы (10.6) и (10.7)), имеем:

— отображение из О в , такое, что

т. e. минимум берется по всем возможным значениям классификаций s для данного X. Аргумент, в котором функция из (10.20) достигает минимума, может быть не единственным, поэтому необходимо фиксировать еще способ выбора требуемого аргумента. В формуле для классификатора из алгоритма -средних (см. п. 7.2.1) заложен в явном виде способ выбора, наиболее употребительный на практике. Далее имеем — линейное отображение из такое, что такое, что

т. е.

Итак, требуемая модификация параметров модели 10.3.1 завершена. Она немедленно приводит к модели алгоритма нечеткой классификации, который назвали выше алгоритмом -средних.

Для возьмем в качестве множество всех отображений из О в . Таким образом, классификация ставит в соответствие объекту X вектор , в котором координата имеет смысл степени принадлежности объекта X к классу. Множество L возьмем таким же, как в модели 10.3.1. Интерпретирующий функционал возьмем вида (10.19), но теперь будем считать, что функции являются параметрами модели. Операторы К и D зададим согласно формулам (10.20) и (10.21).

10.3.6. Модель алгоритма нечеткой классификации Беждека.

Для того чтобы спуститься от модели 10.3.5 к модели 10.3.6, достаточно конкретизировать вид весовых функций рассматриваемых как функции на симплексе A (k). В алгоритме Беждека (см. п. 7.5.2)

В этом случае можно дать явное решение оптимизационной задачи (10.20): найти

при условии, что Это решение использовано в описанном (см. п. 7.5.2) алгоритме Беждека.

10.3.7. Модель алгоритма -средних.

Модель 10.3.5 описывает ядерный алгоритм нечеткой классификации, поэтому точно так же, как был осуществлен подъем алгоритма -средних до алгоритма -средних, можно от алгоритма -средних перейти вверх по нашей иерархии до алгоритма -средних. Таким образом получается модель алгоритма, отстоящая от модели 10.3.1 уже на два уровня.

10.3.8. Модель алгоритма -средних для весовых функций Беждека.

Спускаясь вниз по уровням иерархии от модели 10.3.7, получаем:

— изолированная точка, т. е. — конус с вершиной Далее, L — часть множества линейных отображений в Y, состоящая из всех отображений, при которых вершина переходит в точку Классификатор К и дескриптор D задаются формулами:

В заключение отметим, что при a 1 от модели 10.3.8 переходим (спускаемся по иерархии) к модели 10.3.3, а, полагая

от модели 10.3.4 — к модели 10.3.8.