2.6. МЕТОД ЦЕНТРА ТЯЖЕСТИ

Представление классов центрами тяжести очень распространено. По словам Уишарта [13], очевидно, Торндайк 112] является первым, кто предложил процедуру итеративного уточнения местоположения центров тяжести, в чем можно убедиться, в частности, прочитав следующую его фразу (1954 г.): «Вообще говоря, элемент является неправильно расклассифицированным, если он к членам другого кластера ближе, чем к членам своего В подобных случаях производится «переназначение» элементов, начиная с наиболее очевидных промахов, и при этом пересчитываются средние значения внутриклассовых расстояний. Эти изменения производятся до тех пор, пока никакое

следующее изменение не сможет уменьшить величину среднего внутриклассового разброса».

Затем Себастьян [11], Дженси [71 и Форжи [6] усовершенствовали процедуру итеративного повторного перераспределения элементов по классам, близкую по своей сути к той, что была предложена Торндайком. Наконец, Мак-Куин [9] предложил следующую процедуру.

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

Болл и Холл [1] и [2] создали очень популярный в США метод, названный ISOOATA. Он состоит в случайном отборе элементов в качестве центров классов и в назначении (без изменения центров классов) оставшихся объектов по классам по принципу ближайшего соседства к центру. После такого распределения объектов по классам центры классов пересчитываются. Если два центра классов слишком близки друг к другу, тогда эти два класса объединяются; одновременно если дисперсия одного класса слишком велика, тогда он разделяется на два класса. Этот процесс продолжается до стабилизации центров классов и требует априорного выбора некоторого числа «порогов», в сравнении со значениями которых принимается решение о слиянии или разделении классов.

В статье Фридмана и Рубина [51 подвергается сомнению критерий внутриклассовой дисперсии и предлагается критерий, инвариантный относительно линейного преобразования переменных. Все описанные алгоритмы требуют от пользователя «размещения» своих объектов в евклидовом пространстве, в то время как в предлагаемом нами подходе этого не требуется.

2.6.1. Пространство представительств

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

Отправляясь от этого метрического пространства определяем в качестве пространства представительств множество

Мера адекватности между и определяется таким образом:

2.6.2. Оптимизационная задача

В данном случае оптимизационная задача состоит в отыскании такой пары которая минимизирует критерий

где центр тяжести класса следовательно, представляет центров тяжести классов разбиения

Очевидно, что критерий выражает среднюю внутриклассовую дисперсию разбиения

2.6.3. Алгоритм

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

Гипотеза 1. Минимум существует и единствен, каково бы ни было а в

Проверим соблюдение этого условия в нашем случае:

Одно из хорошо известных свойств евклидова расстояния определяет справедливость следующего положения:

минимум существует и единствен, это — центр тяжести класса т.е.

где представление элемента а в (т.е. вектор координат элемента а в пространстве Гипотеза 2.

(с очевидностью следует из определения Таким образом, алгоритм, приведенный в 1.3.5, учитывая предложение из 1.3.6, дает возможность сделать этот критерий убывающим.

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

2.6.4. Распространение на непрерывный случай

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

Рассмотрим вероятностное пространство множество наблюдений (пространство элементарных событий); — борелевское поле (т. е. минимальная -алгебра множеств) на

— определенная на положительная мера, такая, что а о функции на говорят, что она измерима в борелевское поле если для любого и соответствующего имеем;

где есть «образ меры» порожденный Следовательно, для любой функции являющейся -измеримой, имеем:

2.6.4.1. Определения

Пусть множество наблюдений, — борелевское поле на положительная мера на . Тогда:

1) мера, определенная на множествах соотношением называется мерой плотности по отношению к и обозначается

2) положительная мера называется абсолютно непрерывной по отношению к если из следует

3) положительная мера называется сингулярной по отношению к мере если существует такое, что

4) две числовые и -измеримые функции и называются эквивалентными по положительной мере если для всякого

5) будем называть центром тяжести подмножества множества вектор такой, что

где такое, что

Теорема Лебега — Никодима. Пусть некоторая положительная мера на существует единственный класс числовых

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

причем есть функция плотности на образе множества Тогда мера Лебега абсолютно непрерывна по отношению к

2.6.4.2. Построение алгоритма динамических сгущений

Напомним используемые обозначения. Расстояние задано в и определяет отображение пространства Билинейная симметричная форма задана в определяет отображение и позволяет для любых пар связанных между собой соотношениями устанавливать соответствие

Будут использованы также два разбиения множества на классов, связанные между собой некоторым соотношением

Построение функции назначения. Определим класс соотношением

Его построение сводится, таким образом, к построению следующей разделяющей гиперплоскости классов с номерами

Если то имеем соотношение

Построение функции представительства. Вычисляем который является центром тяжести класса

при

Критерий записывается в виде

Так как билинейные формы, то, если имеем

Замечание. Если есть конечное множество, то для всякого В этой ситуации если существует такое, что в противном случае.

Алгоритм метода центра тяжести является, следовательно, частным случаем только что определенного алгоритма.

2.6.4.3. Теорема

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

Доказательство. Пусть Таким образом, мы имеем следующие соотношения:

По определению центра тяжести для всякого

так что

Функция назначения по определению «устроена» так, что для всякого

Следовательно, при любом

откуда, суммируй на получаем

из этого вытекает, что

Пусть Тогда -Последовательность ограничена снизу и, как только что показано, убывающая. Следовательно, она сходится.

2.6.4.4. Пример

Рассмотрим вероятностное пространство в котором множество действительных чисел, — борелевское поле на положительная мера, такая, что а по теореме

Лебега — Никодима существует плотность по мере Лебега Возьмем в данном примере следующую функцию плотности:

причем

Требуется произвести разбиение множества (и, следовательно, на два класса (т.е.

Рис. 2.1

Вариант 1. Положим Разделяющая гиперплоскость (которая в данном случае является точкой на определяется уравнением

Соответственно

Вариант 2. Положим Решение соответствующей оптимизационной задачи (см. примеч. пер. на с. 49) дает нам в качестве разделяющей гиперплоскости уравнение

Соответственно (рис. 2.2).

Рис. 2.2