6.8. ФУНКЦИИ КРИТЕРИЕВ ДЛЯ ГРУППИРОВКИ

Предположим, что мы имеем множество из выборок которые хотим разделить на точно с непересекающихся подмножеств

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

6.8.1. КРИТЕРИЙ СУММЫ КВАДРАТОВ ОШИБОК

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

Тогда сумма квадратов ошибок определяется как

Эта функция имеет простую интерпретацию. Для данной группы средний вектор лучше всего представляет выборки в так как он минимизирует сумму квадратов длин векторов «ошибок» . Таким образом, измеряет общую квадратичную ошибку, вносимую при представлении выборок центрами с групп Значение зависит от того, как выборки сгруппированы в группы, и оптимальным разделением считается то, которое минимизирует . Группировки такого типа называют разделением с минимальной дисперсией.

Какого типа задачи группировки подходят для критерия в виде суммы квадратов ошибок? В основном — подходящий критерий в случае, когда выборки образуют облака, которые достаточно хорошо отделены друг от друга. Он хорошо будет работать для двух или трех групп рис. 6.11, но для данных на рис. 6.12 не даст удовлетворительных результатов. Менее явные проблемы возникают,

(см. скан)

Рис. 6.11. Двумерное представление данных Андерсона об ирисах

(см. скан)

Рис. 6.12. Диаграмма Герцшпрунга — Рассела.

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

6.8.2. РОДСТВЕННЫЕ КРИТЕРИИ МИНИМУМА ДИСПЕРСИИ

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

где

В уравнении (28) s, интерпретируется как среднеквадратичное расстояние между точками группы и подчеркивает тот факт, что критерий по сумме квадратов ошибок использует как меру подобия евклидово расстояние. Оно также подсказывает очевидный путь получения других функций критериев. Например, можно заменить s средним значением, медианой или, может быть, максимальным расстоянием между точками в группе. В более общем случае можно ввести соответствующую функцию подобия и заменить такими

Рис. 6.13. Задача расщепления больших групп: сумма квадратов ошибок меньше для а, чем для б.

функциями, как

или

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

6.8.3. КРИТЕРИИ РАССЕЯНИЯ

6.8.3.1. Матрицы рассеяния

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

Средний вектор группы

Общий средний вектор

Матрица рассеяния для группы

Матрица рассеяния внутри группы

Матрица рассеяния между группами

Общая матрица рассеяния

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

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

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

6.8.3.2. След в качестве критерия

Самой простой скалярной мерой матрицы рассеяния является ее след — сумма ее диагональных элементов. Грубо говоря, след измеряет квадрат радиуса рассеяния, так как он пропорционален сумме дисперсий по направлениям координат. Таким образом, очевидной функцией критерия для минимизации является след . В действительности это не что иное, как критерий в виде суммы квадратов ошибок, поскольку из (33) и (34) следует

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

6.8.3.3. Определитель в качестве критерия

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

Разделение, которое минимизирует обычно подобно разделению, которое минимизирует но они не обязательно одинаковы. Мы заметили ранее, что разделение, которое минимизирует квадратичную ошибку, может изменяться, если изменяется масштаб по осям. Этого не происходит с Чтобы выяснить, почему это так, рассмотрим невырожденную матрицу Т и преобразование переменных Считая разделение постоянным, мы получаем новые средние векторы и новые матрицы рассеяния Таким образом, изменяется на

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

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

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

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

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

Используя соотношение можно вывести следующие инвариантные модификации для

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

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

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

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

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

Рис. 6.14. Результат преобразования к нормированным главным компонентам (разделение, которое минимизирует в а, минимизирует сумму квадратичных ошибок в б), а — ненормированные, б — нормированные.