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

12.2.1. Случай, когда переменные измерены в количественной шкале.

Рассмотрим задачу кластер-анализа (классификации) в формулировке, обобщающей постановку задачи отыскания главных компонент. Будем искать номинальную категоризованную переменную (фактор) , имеющую k категорий, такую, чтобы критерий вида

где — корреляционное отношение (см., например, [7,12]) между — весовой коэффициент, Иными словами, нужно получить такую классификацию объектов, которая наилучшим образом, в смысле критерия (12.7), объясняла бы наблюдающийся разброс переменных . Вес же определяет степень важности, которую придаем «объяснению» переменной посредством фактора .

Такого рода группировки объектов в [110] предлагается называть объясняющими (фактор «объясняет» переменные ).

Далее будем полагать, что матрица данных X центрирована. Классификационную переменную z можно представить в виде булевой матрицы Z с k столбцами и строками и такой, что элемент если объект принадлежит классу категории переменной в противном случае.

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

Коэффициент корреляционного отношения центрированного признака и номинальной категоризованной переменной z можно записать в виде

где — оценка дисперсии признака среднее значение признака для объектов, попавших в класс (т. е. с категорией фактора ; — количество объектов в классе.

Замечание. Следует помнить, что, строго говоря, в формулах (12.7) и (12.8) имеем дело с оценкой коэффициента по выборке объема , поэтому над ними следовало бы поставить символ Однако поскольку это не приводит к путанице, в данном параграфе опускаем этот символ и слово «оценка» применительно к упомянутым величинам.

Далее имеем (легко проверяется непосредственным вычислением)

где — -компонентный вектор, строка матрицы X. Откуда

Используя (12.9), критерий (12.7) после некоторых преобразований можно представить в виде

(12.10)

где матрица

Учитывая известное равенство для квадратичных форм критерий можно представить в более компактной форме

где — матрица смежности объектов из X, элемент если принадлежат одному и тому же классу, и — в противном случае.

Элементы матрицы суть просто взвешенные скалярные произведения объектов (столбцов матрицы X)

где V — диагональная матрица,

Если перейти к нормированным переменным то можно записать

Итак,

(12.11)

С другой стороны, непосредственным вычислением легко проверяется, что

(12.12)

где — вектор средних значений для класса. Следовательно,

(12.13)

где — матрица межклассового рассеивания.

Матрицу же можно рассматривать как полную матрицу рассеивания. Рассмотрим два случая выбора весов

а) пусть . Тогда и критерий примет вид

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

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

Критерий Т отличается от только наличием знаменателя Отсюда следует, что если в исходной метрике для получения классификации использовать критерий Т, то это эквивалентно максимизации следующей взвешенной суммы корреляционных отношений

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

В табл. 12.3 суммированы результаты о соотношениях между метриками и соответствующими им критериями в терминах сумм корреляционных отношений и матриц рассеивания.

Таблица 12.3

(см. скан)

Классификация, объясняемая через переменные. Группировку объектов, получаемую на основе максимизации критерия (12.7), можно рассматривать как группировку, которая «объясняет» разброс переменных с помощью классификационного признака . Ниже рассмотрим критерий группировки, который можно интерпретировать как критерий, «объясняющий» получаемую на основе его максимизации группировку, т. е. категории некоторой номинальной переменной , посредством переменных Будет показано, что при определенном выборе метрики объясняющая группировка совпадает с объясняемой.

Введем критерий вида

(12.14)

где — квадрат коэффициента множественной корреляции между фиктивной бинарной переменной и переменными — весовые коэффициенты.

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

(12.15)

где

Докажем следующее утверждение: если выбрать вес , то критерий эквивалентен критерию , где S — матрица ковариаций для X.

Для этого запишем аналитическое выражение коэффициента множественной корреляции в виде (см. § 17.2)

и

Матрица является матричным представлением проекционного оператора Р, проектирующего -мерные векторы на подпространство, натянутое на строки матрицы X. С другой стороны, — вектор средних для группы. Поэтому

(12.16)

Учитывая, что получим после подстановки (12.16) в (12.14)

В отличие от критерия критерий афинноинвариантен. В махаланобисовой метрике и критерий (объясняющая группировка) и К? (объясняемая группировка) совпадают.

12.2.2. Границы значений некоторых критериев классификации.

Дадим две оценки величины критерия полезные для целей интерпретации, а именно для получения представления о том, насколько удачным с формальной (критериальной) точки зрения является полученное разбиение. Эти оценки в какой-то степени заменяют статистические критерии, определяющие значимость классификации (отличие ее от случайной).

Граница снизу. Первая граница носит эвристический характер, хотя и является, по-видимому, достаточно точной и измеряет среднее значение критерия на множестве всех возможных разбиений объектов на классов. Будем предполагать, что случайным образом многократно генерируется классификационная матрица Z и каждый раз вычисляется значение критерия Рассмотрим только случай нормированных переменных, полагая веса . Для получения оценки используем представление в виде (12.10). Значение квадратичной формы можно представить в виде

где значение — соответственно максимальное (минимальное) собственное число матрицы

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

Аналогичное равенство приближенно верно при любом

Поэтому имеем приближенно

где

Более точно

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

Граница, определяемая разбиением, предполагающим, что центры классов лежат на одной прямой. Граница случ получена при усреднении значений критерия по множеству всех возможных разбиений, в том числе и очень неудачных разбиений, порожденных чисто случайным механизмом, когда точки, удаленные друг от друга, попадают в один кластер и, наоборот, очень близкие точки могут оказаться в разных кластерах. Поэтому реальное значение критерия даваемой процедурами классификации обычно существенно больше случ (12.17). С другой стороны, известно, что наилучшее разбиение (в смысле любого из критериев достигается в подклассе разбиений, получаемых с помощью линейных дискриминантных плоскостей [56, 60].

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

Верхняя граница для значения критерия. Для получения этой границы обратимся к представлению в виде (12.10). Векторы взаимно ортогональны, и норма вектора Используя экстремальные свойства собственных векторов (см. гл. 13), получаем после некоторых преобразований, что , где — собственные числа матрицы U, упорядоченные в порядке убывания.

Так как — при любом (поскольку имеется только ненулевых собственных чисел), имеем

Заметим далее, что ненулевые собственные числа матрицы U совпадают с собственными числами матрицы корреляций

12.2.3. Случай, когда центры классов лежат на одной прямой.

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

Этот случай и будем рассматривать дальше. Без ограничения общности можно также считать, что

Критерий для выбора вектора направления А и разбиения z запишем в виде

(12.19)

Здесь у — новый признак, линейная комбинация исходных данных . Значение критерия (12.19) не зависит от длины вектора А. Пусть теперь классификация Z фиксирована. Определим вектор А, дающий критерию (12.19) максимальное значение. При этом потребуем выполнения следующего условия нормировки — ковариационная матрица т. е. будем требовать, чтобы проекция имела единичную дисперсию.

Корреляционное отношение при выполнении условия нормировки можно представить в виде

После дифференцирования по А с учетом условия нормировки с помощью множителя Лагранжа получаем уравнение, которому должен удовлетворять искомый вектор А

(12.21)

где — матрица межклассового разброса.

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

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

1. Переходим к метрике Махаланобиса и центрируем данные.

2. Задаем некоторое начальное направление

3. Производим группировку проекций объектов на А

Подсчитываем центры и матрицу В. Проверяем условие остановки (стабилизацию центров).

4. Пересчитываем А

здесь В — матрица межгруппового рассеивания по центрам. Переходим на шаг 3.

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