6.8.3.4.    Инвариантные критерии

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

желательно, чтобы разделение давало большие значения. Конечно, как мы отметили в разд. 4.11, тот факт, что ранг Sg не может превышать с—1, означает, что не более чем с—1 этих собственных значений будут не равны нулю. Тем не менее хброшими считаются такие разделения, у которых ненулевые собственные значения велики.

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

Используя соотношение S7-=Swr+Sa, можно вывести следующие инвариантные модификации для tr iSw и 15^г|;

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

По отношению к функциям критерия, включающим St, отметим, что Sr не зависит от того, как выборки разделены на группы. Таким образом, группировки, которые минимизируют |5^|/|5^-|, в точности те же, которые минимизируют |Svrl- Если мы вращаем и масштабируем оси так, что Sj- становится единичной матрицей, можно видеть, что минимизация tr Sг^Sv^г эквивалентна мини-

мизации критерия суммы квадратов ошибок tr Sw после этой нормировки. Рис. 6.14 иллюстрирует эффект такого преобразования. Ясно, что этот критерий страдает теми же недостатками, о которых мы предупреждали в разд. 6.7, и является, вероятно, наименее желательным критерием.

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

Разнообразие функций критериев, о которых здесь говорилось, и небольшие различия между ними не должны заслонить их существенной общности. В каждом случае основой модели служит то, что выборки образуют с хорошо разделенных облаков точек. Матрица внутригруппового рассеяния 5w используется для измерения компактности этих точек, и основной целью является нахождение наиболее компактной группировки. Хотя этот подход оказался полезным во многих задачах, он не универсален. Например, он не выделит очень плотное облако, расположенное в центре редкого облака, или не разделит переплетенные вытянутые группы. Для таких случаев нужно создать другие критерии, которые больше подходят к структуре существующей или искомой.

Когда найдена функция критерия, грулпировка становится корректно поставленной задачей дискретной оптимизации: найти такие разделения множества выборок, которые приводят к экстремуму функции критерия. Поскольку множество выборок конечно, существует конечное число возможных разделений. Следовательно, теоретически задача группировки всегда может быть решена трудоемким перебором. Однако на практике такой подход годится лишь для самых простых задач. Существует приблизительно с"/с! способов разделения множества из п элементов на с подмножеств ‘), и этот экспоненциальный рост при большом п просто давит. Например, скрупулезный поиск лучшего набора из пяти групп в случае 100 выборок потребует рассмотрения более чем 10” разделений. Поэтому в большинстве применений перебор практически невозможен.

Наиболее часто используемым подходом для поиска оптимального разделения является итеративная оптимизация. Основная идея заключается в нахождении некоторого разумного начального разделения и в «передвижении» выборок из одной группы в другую, если это передвижение улучшает функцию критерия. Как и процедуры подъема на вершину к общем случае, такой подход гарантирует локальный, но не глобальный максимум. Различные начальные точки Могут привести к разным решениям, и никогда не известно, было ли найдено лучшее решение. Несмотря на эти ограничения, вычислительные требования выполнимы, и такой подход приемлем.

Рассмотрим использование итеративного улучшения для минимизации критерия суммы квадратов ошибок J^, записанного как

здесь

где

Предположим, что выборка х, находящаяся в данный момент в группе SPи передвигается в группу ^j. Тогда изменяется на

и J] увеличивается на

Приняв предположение, что ПіФ\ (одиночных групп в разбиении не должно быть), такое же вычисление показывает, что хпі изменяется на

и Jі уменьшается;

Эти Соотношения значительно упрощают вычисления изменения функции критерия. Переход х из в Sj положителен, если уменьшение Ji больше, чем увеличение JЭто случай, если

что обычно получается, когда х ближе к т^, чем к rrij. Если перераспределение выгодно, наибольшее уменьшение в сумме квадратов ошибок достигается выбором группы, для которой пу/(п^4-1)||х—т;||^ минимально. Это приводит к следующей процедуре группировки;

Процедура: Базовая Минимальная Квадратичная Ошибка

1. Выбрать первоначальное разделение выборок на группы и вычислить J^ и средние Ші, . . ., Шс.

Цикл; 2. Выбрать следующую выборку — кандидата на передвижение X. Предполагается, что х находится в SCі.

3. Если «і = 1, перейти к Следующий; иначе вычислить

4.   Передвинуть х в &h, если pfe^p;- для всех /.

5.   Вновь вычислить Je, шг и mft.

Следующий: 6. Если Jе не изменилось после п попыток, останов;

иначе перейти к Цикл.

Если эту процедуру сравнить с процедурой Базовые Изоданные, описанной в п. 6.4.4, то ясно, что первая процедура в основном представляет собой последовательный вариант второй. Тогда как процедура Базовые Изоданные ждет, пока все п выборок будут перегруппированы перед обновлением значений, процедура Базовая Минимальная Квадратичная Ошибка обновляет значения после перегруппировки каждой выборки. Экспериментально было замечено, что эта процедура более чувствительна к локальным минимумам; другой ее недостаток состоит в том, что результаты зависят от порядка, в котором выбираются кандидаты. Однако это по крайней мере пошаговая оптимальная процедура, и ее легко модифицировать для применения к задачам, в которых выборки получаются последовательно, а группировка должна производиться в масштабе реального времени.

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