7.4. Алгоритмы метода динамических сгущений

Изложим, следуя в основном [106], один общий подход к статистической обработке данных, предложенный Э. Диде и его сотрудниками и названный «методом динамических сгущений» — МДС (Methode des Nuees Dinamiques — MND). Этот подход хотя и формулируется в терминах общей задачи классификации, но, по существу, при соответствующем подборе управляющих параметров индуцирует разнообразные методы решения следующего широкого класса задач:

1) разбиение данной совокупности объектов или признаков на некоторое число (известное заранее или нет) однородных классов — собственно проблема автоматической классификации;

2) снижение размерности (числа анализируемых показателей) массива исходных данных, отбор наиболее информативных показателей;

3) статистический анализ предпочтений, задача их типологизации и агрегирования;

4) статистический анализ линейных моделей регрессионного типа;

5) оптимальная (в рамках решаемой конкретной задачи) оцифровка анализируемых переменных;

6) статистический анализ «двухвходовых» таблиц сопряженности.

Основная идея МДС, являющаяся далеким обобщением идеи метода -средних (см. п. 7.2.1, 7.2.2), достаточно отчетливо выражена словами Э. Диде: «Среди всех разбиений на k классов следует найти разбиение, относительно каждого класса которого заданное «ядро» оказалось бы наиболее представительным.

Понятие ядра имеет самый широкий смысл: ядро класса (т. е. группы точек) может быть подгруппой точек, центром тяжести, осью, случайной переменной и т. д.» [106, с. 25] (курсив наш. — В. Б.).

7.4.1. Основные понятия и общая схема метода. Пусть — исследуемое множество объектов, каждый из которых характеризуется -мерным вектором признаков, т. е. .

Пространством k покрытий называется множество, каждый элемент которого представляет собой систему подмножеств (классов) элементов X, удовлетворяющих заданной структуре классов. На практике встречаются обычно следующие типы структур классов: разбиения, покрытия, иерархии.

Пространством представителей L называется множество, каждый элемент которого может служить представителем (ядром) класса элементов X. Выбирается мера сходства между объектом и представителем .

Например:

а) тогда — квадрат стандартного евклидова расстояния;

б) где М — некоторое семейство расстояний (см. § 5.2). Тогда . Семейство М обычно задается в параметрическом виде, например: — семейство махаланобисского типа, где М — положительно определенная, симметрическая матрица;

2) — семейство «сити блок» (City Block)

Пространством k представительств для пространства покрытий называется множество наборов

Для построения представительства I покрытия

1) выбирается пространство представителей L и мера сходства ;

2) выбирается функция представительства g, относящая к классу S, представителя

Например, .

Для построения покрытия отвечающего представительству

1) выбирается пространство покрытий

2) выбирается функция назначения f, с помощью которой каждый объект X получает «назначение» в тот или инон класс, т. е. Например, — минимальное дистанционное разбиение выборки X, порожденное набором относительно меры сходства .

Метод динамических сгущений состоит из следующих частей (этапов):

1. Выбор пространства покрытий

2. Выбор пространства представителей L и меры сходства .

3. Выбор оптимизируемого критерия позволяющего, используя , измерить «степень адекватности» между всяким покрытием и всяким представительством этого покрытия . Критерий W строится обычно так, чтобы он принимал только неотрицательные значения.

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

5. Построение алгоритма динамических сгущений (ADC), состоящего в последовательном итеративном использовании функций начиная с некоторого покрытия или представительства

6. Изучение свойств сходимости алгоритма динамических сгущений.

7.4.2. Алгоритмы классификации.

Основная цель настоящего раздела — изложить подход МДС к построению алгоритмов автоматической классификации. Подробное описание, практические рекомендации и примеры применения этих алгоритмов содержатся в [106].

У всех рассматриваемых ниже алгоритмов одинаковыми являются:

пространство k покрытий — множество всех разбиений совокупности X на k непересекающихся классов;

вид оптимизируемого критерия :

где - разброс i-гo класса относительно представителя (ядра) U и — некоторая мера сходства между объектом X и представителем

способ построения функции назначения При выбранных ядрах классов и мерах сходства объект X относится к классу по правилу минимального дистанционного разбиения:

где

способ построения функции представительства g. При выбранном пространстве представителей L задается пространство представительств как подмножество наборов выделяемое в некоторыми условиями. Тогда для заданного разбиения его представительство g (S) находится как решение задачи условной минимизации критерия т. е.

В наиболее важном частном случае, когда представительство находитсякак решение задачи безусловной минимизации на

где

Схема алгоритма

1. Выберем начальное разбиение

2. Пусть построено разбиение Найдем представительство (набор ядер)

3. Найдем разбиение ).

4. Если то переходим к 2, заменив на . Если то полагаем и заканчиваем работу алгоритма.

Для получения конкретного варианта алгоритма классификации по приведенной схеме достаточно описать только следующие его компоненты:

а) пространство представителей L;

б) меру сходства

в) условия, выделяющие пространство представительств

В приведенных ниже алгоритмах будем использовать терминологию и, по возможности, обозначения из [106].

Пусть — множество подмножеств исследуемой совокупности объектов . Для обозначим через число элементов (мощность) множества Р. Предположим, что на X задана положительная нормированная мера (распределение массы) т. е. функция , такая, что

Опишем сначала компоненты а, б, в алгоритмов, в которых представителями классов являются подмножества точек классифицируемой совокупности X, т. е. i Е П (X).

1. Метод ядерного разбиения

а)

б)

где d (X, Y) — некоторая мера близости между объектами из X;

в)

2. Метод, использующий ядра фиксированной мощности

а)

б)

в)

3. Метод, использующий ядра переменной мощности

а)

где — фиксированный уровень массы ядра;

б)

в)

Следующая группа алгоритмов использует в качестве ядер точки пространства признаков (формальные объекты).

Будем считать, что пространством признаков является , т. е. .

1. Метод центра тяжести

а)

б)

где — квадрат расстояния махаланобисского типа и М — фиксированная симметрическая положительно определенная матрица.

Разброс i-гo класса относительно ядра в этом случае имеет вид

в)

Когда , где и М — единичная матрица, то этот алгоритм представляет собой алгоритм -средних параллельного типа.

2. Метод адаптивных расстояний

а) , где — некоторое семейство мер сходства в ;

б)

в) ;

В [106] исследуются отдельно варианты с квадратичными и неквадратичными расстояниями.

Квадратичные расстояния. В этом случае — семейство махаланобисского типа.

1. Независимый выбор меры сходства для каждого класса, т. е. и представитель класса S; находится как решение задачи:

где — подмножество в , составленное из матриц с определителем, равным

Решая эту задачу, получаем (см. гл. 11) — центр класса , где — ковариационная матрица элементов класса.

Теоретико-вероятностная модель, в рамках которой этот алгоритм оптимален, описана в п. 5.4.6. Каждое из наблюдений извлекается из одной из k нормальных генеральных совокупностей При этом и 2, неизвестны.

Модели, в которой каждое наблюдение извлекается из одной из k нормальных генеральных совокупностей с общей ковариационной матрицей , где и неизвестны, соответствует алгоритм:

2. Мера сходства, общая для всех классов, т. е. и состоит из наборов .

В этом случае для заданного разбиения представительство находится как решение задачи:

которую нельзя расщгпить на k задач поиска представителей каждого класса в отдельности. Решая эту задачу, получаем (см. гл. 11):

Неквадратичные расстояния. В качеств основного примера рассматривается семейство «сити блок», которое приводит к методу, использующему медианную оценку центра класса.

Представитель класса , где - центр класса, — мера сходства, ассоциированная с этим классом, находится как решение задачи:

Так как

получаем , где — — медиана значений признака по всем элементам класса . Положим , где

Тогда

т. е.