§5. Функционалы качества разбиения
Материал этого параграфа довольно сложен.
— пометка на полях у Лагутина
Будем считать, что число классов задано (случай, когда оно неизвестно, обсуждается в §6). Пусть обозначает количество объектов (-мерных точек , ) в классе , .
Инерция: общая, внутри- и межклассовая
При разбиении на классы типа «класс с центром» (C4 из §1) в основе многих характеристик качества разбиения лежит формула
- Слева стоит — момент инерции относительно общего центра масс всех объектов.
- Первое слагаемое справа, , — сумма моментов инерции классов относительно их центров масс .
- Второе слагаемое, , характеризует межклассовый разброс: это момент инерции системы, у которой точки каждого класса стянуты в его центр масс.
Формула (6) немедленно вытекает из её одномерного аналога (13) в главе 16.
Смысл по-пацански: общий разброс = разброс внутри компаний + разброс между компаниями. Хорошее разбиение — когда почти весь разброс «между», а внутри тесно.
Перечислим некоторые функционалы качества , определённые на множестве всевозможных разбиений объектов на классов (чем меньше, тем разбиение лучше).
— общая внутриклассовая инерция.
Замечание 5. Как следует из замечания 1 в §3, метод Уорда обеспечивает наименьшее увеличение функционала при каждом шаге процедуры. Однако эта пошаговая оптимальность алгоритма, вообще говоря, не влечёт его оптимальности в том же смысле для любого наперёд заданного числа классов.
— сумма внутриклассовых дисперсий.
Основной результат Дж. Мак-Кина (1967 г.) состоит в доказательстве того, что его вариант алгоритма k-средних (A3 в §2) приводит к локальному минимуму функционала . Точную минимизацию с использованием динамического программирования осуществил Р. Дженсен в 1969 г.
. Последнее равенство справедливо в силу теоремы о межточечных расстояниях (см. решение задачи 5 главы 16).
— сравните с формулой (9) главы 16: это перевёрнутая статистика F-критерия однофакторного дисперсионного анализа.
Смысл по-пацански: – — четыре способа сказать «внутри компаний тесно». считает весь разброс внутри разом. — средний разброс на одного члена компании, так что большая компания не наказывается просто за то, что большая. меряет все внутренние расстояния попарно, каждый с каждым. сравнивает «внутри» с «между» по-честному, со степенями свободы, как в дисперсионном анализе.
Матрицы рассеяния
Ряд функционалов качества разбиения связан с обобщающим формулу (6) матричным тождеством (задача 2)
Здесь:
- — общая матрица рассеяния;
- — матрица внутриклассового разброса: , где — матрица рассеяния -го класса;
- — матрица разброса между классами.
Формула (6) получается из тождества (7) применением к участвующим в нём матрицам операции взятия следа (см. П10). В частности:
- ;
- ;
- ;
- .
Функционалы – изучались Х. Фридманом и Дж. Рубином в 1967 г. Они инвариантны по отношению к невырожденным линейным преобразованиям координат объектов. Действительно, если , где — невырожденная -матрица, то и (см. свойство 5 дисперсии и ковариации из П2). При этом матрица
подобна матрице , поэтому согласно следствию 2 из П10 у них одинаковые следы и определители.
Смысл по-пацански: не волнует, в каких единицах мерить признаки и как их смешивать линейно — хоть в фунтах, хоть в попугаях. Проблема нормировки из §1 для него просто исчезает.
Пример 2. ОМП для многомерной нормальной модели
В целях последующего применения к задаче классификации нормальных совокупностей (пример 3) рассмотрим оценки максимального правдоподобия для параметров многомерной нормальной модели.
Предположим, что случайные -мерные векторы (см. П9) и независимы (). Пусть вектор средних и невырожденная ковариационная -матрица неизвестны, . Общее количество неизвестных параметров с учётом симметричности равно . Согласно П9 плотность случайного вектора задаётся формулой
В силу независимости логарифм функции правдоподобия (§4 главы 9) имеет вид
Максимизация эквивалентна минимизации выражения в квадратных скобках. Положим и разобьём сумму в (9) на два слагаемых на основе тождества, обобщающего теорему Гюйгенса (задача 3):
По кирпичикам: (10) — та же теорема Гюйгенса, только расстояния меряются «линейкой» . Сумма квадратов отклонений от любой точки равна сумме отклонений от центра масс плюс × квадрат расстояния между и . Перекрёстное слагаемое исчезает, потому что .
Первое слагаемое неотрицательно для любой в силу положительной определённости матрицы (почему она положительно определена — вопрос 6) и равно 0 только при . Второе слагаемое от не зависит. Следовательно, достаточно минимизировать по выражение
Введём выборочную ковариационную матрицу
На основе легко проверяемого тождества и линейности оператора получаем
По кирпичикам: — это число, а след числа равен ему самому. Значит, (под следом множители можно циклически переставлять). Складываем по с и : сумма — это ровно .
Учитывая формулу (13), выражение (11) можно переписать в виде
Минимизация суммы (14) по эквивалентна минимизации функции
(постоянные и добавлены для дальнейших преобразований).
Так как и — ковариационные матрицы, то (согласно замечанию из П10) они неотрицательно определены, а даже положительно определена в силу невырожденности. Обозначим через собственные значения пары матриц , то есть решения характеристического уравнения (см. П10). Тогда
Поскольку при , из последнего соотношения получаем, что . Равенство имеет место только при , то есть для (почему — вопрос 7).
Смысл по-пацански: функция — это «яма» с дном ровно в . Каждое собственное значение показывает, во сколько раз «подозреваемая» ошибается против выборочной вдоль своей оси. Ошиблась в любую сторону — штраф. Штраф ноль только тогда, когда ошибок нет ни по одной оси, то есть когда и есть .
Таким образом, оценками максимального правдоподобия параметров и являются, соответственно, статистики и .
Смысл по-пацански: как и в одномерье, ОМП для среднего — выборочное среднее, для ковариаций — выборочная ковариационная матрица с делителем (не ). Вся матричная акробатика нужна только чтобы честно это доказать.
Пример 3. Нормальные наблюдения и функционалы качества
Предположим, что каждое наблюдение () извлечено из одного из нормальных законов (). При этом и , вообще говоря, неизвестны. Задача исследователя — определить, какие из наблюдений извлечены из класса , какие — из и т. д. Числа в общем случае также неизвестны.
Введём векторный параметр разбиения , где — номер класса (от 1 до ), к которому относится наблюдение . Тогда задачу разбиения на классы можно сформулировать как задачу оценивания неизвестных параметров при «мешающих» неизвестных параметрах и . Обозначим весь набор неизвестных параметров через . Тогда логарифм функции правдоподобия (см. формулу (9)) будет равен, с точностью до сдвига на константу, величине
Максимизируем выражение (15) по . Оговоримся сразу, что состоятельность оценки остаётся под сомнением, поскольку размерность вектора превосходит общее число наблюдений .
Смысл по-пацански: у каждого объекта свой неизвестный номер класса , а сверху ещё средние и ковариации. Неизвестных больше, чем наблюдений, — как угадывать пароль, в котором символов больше, чем у тебя попыток. Метод работает и даёт разумные разбиения, но гарантии «с ростом всё сойдётся» здесь нет: каждый новый объект приносит и новое неизвестное.
Рассуждения, аналогичные проведённым в примере 2, показывают, что оценками максимального правдоподобия для параметров при фиксированных являются центры масс классов . Подставляя их в (15) и учитывая тождество (10), получаем, что достаточно минимизировать по и функцию
которая, принимая во внимание равенства (12) и (13), совпадает с
где — выборочная ковариационная матрица класса . Отметим, что , где — матрица рассеяния класса из пояснения к формуле (7).
Анализ выражений (16) и (17) в некоторых частных случаях приводит к ряду интересных выводов.
Случай 1. (), причём параметр известен. Тогда минимизация (16) по равносильна минимизации функционала качества разбиения на классы . Вот откуда «законность» k-средних и метода Уорда: это ОМП для облаков-шаров одинакового размера.
Случай 2. (), где матрица известна. В этом случае минимизируемым функционалом является
где под расстоянием между точками и подразумевается
Случай 3. (), где матрица неизвестна. Тогда выражение (17) можно представить в виде
где
Точно так же, как и в примере 2, находим, что матрица минимизирует сумму (19). Подставив её в формулу (19), замечаем, что второе слагаемое превращается в константу, а минимизация первого по равносильна минимизации функционала .
Замечание 6. Если матрицы ковариаций () совпадают, то можно обобщить одномерный F-критерий однофакторного дисперсионного анализа (см. формулу (9) главы 16) на многомерную нормальную модель. Например, для проверки гипотезы о равенстве средних в качестве статистик критерия будем использовать монотонные функции от . Положим для краткости (её называют лямбдой Уилкса). Известно, что при справедливости гипотезы :
- а) , если и ;
- б) , если и ;
- в) , если и .
Для других значений и и больших можно указать хорошую аппроксимацию, предложенную М. Бартлеттом (1947 г.): статистика имеет приближённо -распределение с степенями свободы.
Обобщение на многомерный случай F-критерия двухфакторного дисперсионного анализа (см. пример 1 главы 17) тоже существует.
Случай 4. Матрицы ковариаций не равны между собой и неизвестны. Минимизируя отдельно каждое слагаемое в сумме (17), находим, что оценками максимального правдоподобия для служат выборочные ковариационные матрицы . Подставив их в формулу (17), превращаем вторые слагаемые в квадратных скобках в константы. При этом минимизируемый по функционал приобретает вид
Заметим, что функционал равносилен (взвешенному) среднему геометрическому определителей матриц , в то время как функционал эквивалентен определителю матрицы, равной (взвешенному) среднему арифметическому этих же матриц (см. формулу (20)).
Смысл по-пацански: каждый функционал качества — это чья-то вероятностная модель в маскировке. Шары одного размера — . Одинаковые эллипсоиды известной формы — . Одинаковые эллипсоиды неизвестной формы — . Эллипсоиды кто во что горазд — . Выбрал функционал — значит, молча выбрал модель.
Пример 4. Собака или волк: дискриминантный анализ
В таблице на рис. 16 у Лагутина указаны размеры челюстей и зубов 30 собак (номера 1–30), 12 волков (номера 31–42) и ископаемого черепа неизвестного животного (номер 43), найденного в четвертичном слое. Данные — Де Бониса. Измеряемые характеристики:
- длина черепа;
- длина верхней челюсти;
- ширина верхней челюсти;
- длина верхнего карнивора;
- длина первого верхнего моляра;
- ширина первого верхнего моляра.
Требуется решить, к какому из классов (собак или волков) следует отнести неизвестное животное.
Для того чтобы это сделать, воспользуемся статистической моделью случайного выбора единственного наблюдения из некоторого многомерного нормального закона. Заранее известно, что этот закон является одним из заданных законов , .
В соответствии с принципом максимального правдоподобия будем считать областью притяжения закона () множество таких точек , где плотность распределения больше других. Это равносильно тому, что величина
имеет наименьшее значение среди (см. формулу (8)). При и получается разбиение прямой на две области притяжения: граница между ними проходит там, где пересекаются две колоколообразные плотности.
Замечание 7. В случае данный способ выбора между законами с произвольными (известными) плотностями и минимизирует сумму вероятностей ошибок I и II рода при проверке гипотезы (см. §1 главы 13) против альтернативы по единственному наблюдению .
Доказательство. Обозначим через критическое множество критерия для проверки гипотезы против альтернативы . Тогда
Интеграл в правой части принимает наименьшее значение в случае, когда множество состоит из всех точек, где подынтегральная функция неположительна, то есть .
Отметим, что оптимальное множество принадлежит (при ) семейству критических множеств из критерия Неймана — Пирсона (см. §2 главы 13): .
Для можно получить оценку сверху:
Здесь — расстояние Бхаттачария. Оно инвариантно относительно взаимно однозначных преобразований координат и обращается в нуль при . Известно, что для двух нормальных законов
В частности, при видим, что , где обозначает расстояние Махаланобиса (см. формулу (18)).
По кирпичикам: откуда оценка. Так как , получаем . Первое равенство — это и есть доказанное замечание 7: при оптимальном в каждой точке «платим» меньшую из двух плотностей.
Расчёт
Применим эти результаты к данным о собаках () и волках ().
- Чтобы уравнять влияние размеров черепа и зубов (первые на порядок больше последних), нормируем столбцы таблицы рис. 16 с помощью устойчивого к выделяющимся наблюдениям преобразования (нормировка N3 из §1).
- Так как истинные и неизвестны, используем вместо них оценки максимального правдоподобия и .
В результате подсчётов получим значения и . Поскольку , в соответствии с принципом максимального правдоподобия неизвестное ископаемое животное, скорее всего, было собакой. При этом значение приводит к оценке суммы вероятностей ошибок I и II рода величиной .
Мы пересчитали всё заново, и книжные числа воспроизводятся точно (, , ) при одном уточнении: медиану и MAD для нормировки нужно считать по всем 43 строкам, включая неизвестное животное.
Сверх книги посчитаем и лямбду Уилкса из замечания 6 для 42 известных животных. Получается , по пункту б) при степенях свободы, . Средние собак и волков различаются, в чём, впрочем, никто и не сомневался. Строго говоря, критерий предполагает равные ковариационные матрицы, а дискриминантный анализ выше их не уравнивал.
Ещё одна проверка — скользящий контроль. Каждое из 42 известных животных по очереди «прячем», оцениваем модели по остальным и классифицируем спрятанное. Ошибаемся на двух из 42. Это честнее, чем оценка : та использует оценки параметров так, будто это истинные значения.
Этот вывод подтверждает и диаграмма рассеяния нормированных признаков 1 (длина черепа) и 4 (длина верхнего карнивора) — рис. 19 у Лагутина; её можно построить в режиме «Диаграмма рассеяния» виджета и в §8. На основе диаграммы можно заключить, что главным признаком, с помощью которого различаются собаки и волки, является размер зубов.
Бабушка, а почему у тебя такие большие зубы?
— Красная Шапочка
Смысл по-пацански: череп собачий — по зубам видно. Волчьи карниворы длиннее, и это различие сильнее, чем по любой длине черепа: собаки бывают и мелкие, и крупные, а зубы у волка всё равно больше.