Skip to Content

§5. Функционалы качества разбиения

Материал этого параграфа довольно сложен.

— пометка на полях у Лагутина

Будем считать, что число классов kk задано (случай, когда оно неизвестно, обсуждается в §6). Пусть nln_l обозначает количество объектов (mm-мерных точек xi\boldsymbol x_i, i=1,…,ni = 1, \dots, n) в классе SlS_l, l=1,…,kl = 1, \dots, k.

Инерция: общая, внутри- и межклассовая

При разбиении на классы типа «класс с центром» (C4 из §1) в основе многих характеристик качества разбиения лежит формула

∑i=1n∣xi−xˉ∣2=∑l=1k∑xi∈Sl∣xi−xˉl∣2+∑l=1knl∣xˉl−xˉ∣2.(6)\sum_{i=1}^n|\boldsymbol x_i - \bar{\boldsymbol x}|^2 = \sum_{l=1}^k\sum_{\boldsymbol x_i \in S_l}|\boldsymbol x_i - \bar{\boldsymbol x}_l|^2 + \sum_{l=1}^kn_l|\bar{\boldsymbol x}_l - \bar{\boldsymbol x}|^2. \tag{6}
  • Слева стоит VtotV_{tot} — момент инерции относительно общего центра масс xˉ\bar{\boldsymbol x} всех объектов.
  • Первое слагаемое справа, VintV_{int}, — сумма моментов инерции IlI_l классов SlS_l относительно их центров масс xˉl\bar{\boldsymbol x}_l.
  • Второе слагаемое, VoutV_{out}, характеризует межклассовый разброс: это момент инерции системы, у которой точки каждого класса стянуты в его центр масс.

Формула (6) немедленно вытекает из её одномерного аналога (13) в главе 16.

Смысл по-пацански: общий разброс = разброс внутри компаний + разброс между компаниями. Хорошее разбиение — когда почти весь разброс «между», а внутри тесно.

Перечислим некоторые функционалы качества FF, определённые на множестве всевозможных разбиений SS объектов на kk классов (чем F(S)F(S) меньше, тем разбиение SS лучше).

F1=∑l=1kIl≡VintF1 = \sum_{l=1}^kI_l \equiv V_{int} — общая внутриклассовая инерция.

Замечание 5. Как следует из замечания 1 в §3, метод Уорда обеспечивает наименьшее увеличение функционала F1F1 при каждом шаге процедуры. Однако эта пошаговая оптимальность алгоритма, вообще говоря, не влечёт его оптимальности в том же смысле для любого наперёд заданного числа классов.

F2=∑l=1k1nlIlF2 = \sum_{l=1}^k\frac1{n_l}I_l — сумма внутриклассовых дисперсий.

Основной результат Дж. Мак-Кина (1967 г.) состоит в доказательстве того, что его вариант алгоритма k-средних (A3 в §2) приводит к локальному минимуму функционала F2F2. Точную минимизацию F2F2 с использованием динамического программирования осуществил Р. Дженсен в 1969 г.

F3=∑l=1k∑xi,xj∈Sl∣xi−xj∣2=2∑l=1knlIlF3 = \sum_{l=1}^k\sum_{\boldsymbol x_i, \boldsymbol x_j \in S_l}|\boldsymbol x_i - \boldsymbol x_j|^2 = 2\sum_{l=1}^kn_lI_l. Последнее равенство справедливо в силу теоремы о межточечных расстояниях (см. решение задачи 5 главы 16).

F4=[1n−kVint]/[1k−1Vout]F4 = \Bigl[\frac1{n - k}V_{int}\Bigr]\Big/\Bigl[\frac1{k - 1}V_{out}\Bigr] — сравните с формулой (9) главы 16: это перевёрнутая статистика F-критерия однофакторного дисперсионного анализа.

Смысл по-пацански: F1F1–F4F4 — четыре способа сказать «внутри компаний тесно». F1F1 считает весь разброс внутри разом. F2F2 — средний разброс на одного члена компании, так что большая компания не наказывается просто за то, что большая. F3F3 меряет все внутренние расстояния попарно, каждый с каждым. F4F4 сравнивает «внутри» с «между» по-честному, со степенями свободы, как в дисперсионном анализе.

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

Ряд функционалов качества разбиения связан с обобщающим формулу (6) матричным тождеством (задача 2)

Wtot=Wint+Wout.(7)\boldsymbol W_{tot} = \boldsymbol W_{int} + \boldsymbol W_{out}. \tag{7}

Здесь:

  • Wtot=∑i=1n(xi−xˉ)(xi−xˉ)T\boldsymbol W_{tot} = \sum_{i=1}^n(\boldsymbol x_i - \bar{\boldsymbol x})(\boldsymbol x_i - \bar{\boldsymbol x})^T — общая матрица рассеяния;
  • Wint\boldsymbol W_{int} — матрица внутриклассового разброса: Wint=∑l=1kWl\boldsymbol W_{int} = \sum_{l=1}^k\boldsymbol W_l, где Wl=∑xi∈Sl(xi−xˉl)(xi−xˉl)T\boldsymbol W_l = \sum_{\boldsymbol x_i \in S_l}(\boldsymbol x_i - \bar{\boldsymbol x}_l)(\boldsymbol x_i - \bar{\boldsymbol x}_l)^T — матрица рассеяния ll-го класса;
  • Wout=∑l=1knl(xˉl−xˉ)(xˉl−xˉ)T\boldsymbol W_{out} = \sum_{l=1}^kn_l(\bar{\boldsymbol x}_l - \bar{\boldsymbol x})(\bar{\boldsymbol x}_l - \bar{\boldsymbol x})^T — матрица разброса между классами.

Формула (6) получается из тождества (7) применением к участвующим в нём матрицам операции взятия следа (см. П10). В частности:

  • F1=Vint=tr⁡WintF1 = V_{int} = \operatorname{tr}\boldsymbol W_{int};
  • F5=det⁡WintF5 = \det\boldsymbol W_{int};
  • F6=tr⁡(WintWtot−1)F6 = \operatorname{tr}\bigl(\boldsymbol W_{int}\boldsymbol W_{tot}^{-1}\bigr);
  • F7=det⁡(WintWtot−1)=det⁡Wint/det⁡WtotF7 = \det\bigl(\boldsymbol W_{int}\boldsymbol W_{tot}^{-1}\bigr) = \det\boldsymbol W_{int}/\det\boldsymbol W_{tot}.

Функционалы F6F6–F7F7 изучались Х. Фридманом и Дж. Рубином в 1967 г. Они инвариантны по отношению к невырожденным линейным преобразованиям координат объектов. Действительно, если x~i=Bxi\tilde{\boldsymbol x}_i = \boldsymbol B\boldsymbol x_i, где B\boldsymbol B — невырожденная (m×m)(m \times m)-матрица, то W~int=BWintBT\tilde{\boldsymbol W}_{int} = \boldsymbol B\boldsymbol W_{int}\boldsymbol B^T и W~tot=BWtotBT\tilde{\boldsymbol W}_{tot} = \boldsymbol B\boldsymbol W_{tot}\boldsymbol B^T (см. свойство 5 дисперсии и ковариации из П2). При этом матрица

W~intW~tot−1=BWintBT(BT)−1Wtot−1B−1=BWintWtot−1B−1\tilde{\boldsymbol W}_{int}\tilde{\boldsymbol W}_{tot}^{-1} = \boldsymbol B\boldsymbol W_{int}\boldsymbol B^T(\boldsymbol B^T)^{-1}\boldsymbol W_{tot}^{-1}\boldsymbol B^{-1} = \boldsymbol B\boldsymbol W_{int}\boldsymbol W_{tot}^{-1}\boldsymbol B^{-1}

подобна матрице WintWtot−1\boldsymbol W_{int}\boldsymbol W_{tot}^{-1}, поэтому согласно следствию 2 из П10 у них одинаковые следы и определители.

Смысл по-пацански: F7F7 не волнует, в каких единицах мерить признаки и как их смешивать линейно — хоть в фунтах, хоть в попугаях. Проблема нормировки из §1 для него просто исчезает.

Пример 2. ОМП для многомерной нормальной модели

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

Предположим, что случайные mm-мерные векторы ξi∼N(μ,Σ)\boldsymbol\xi_i \sim \mathcal N(\boldsymbol\mu, \boldsymbol\Sigma) (см. П9) и независимы (i=1,…,ni = 1, \dots, n). Пусть вектор средних μ=(μ1,…,μm)\boldsymbol\mu = (\mu_1, \dots, \mu_m) и невырожденная ковариационная (m×m)(m \times m)-матрица Σ\boldsymbol\Sigma неизвестны, θ=(μ,Σ)\boldsymbol\theta = (\boldsymbol\mu, \boldsymbol\Sigma). Общее количество неизвестных параметров с учётом симметричности Σ\boldsymbol\Sigma равно m+m(m+1)/2m + m(m + 1)/2. Согласно П9 плотность случайного вектора ξi\boldsymbol\xi_i задаётся формулой

p(x,θ)=(2π)−m/2(det⁡Σ)−1/2exp⁡{−12(x−μ)TΣ−1(x−μ)}.(8)p(\boldsymbol x, \boldsymbol\theta) = (2\pi)^{-m/2}(\det\boldsymbol\Sigma)^{-1/2}\exp\Bigl\{-\tfrac12(\boldsymbol x - \boldsymbol\mu)^T\boldsymbol\Sigma^{-1}(\boldsymbol x - \boldsymbol\mu)\Bigr\}. \tag{8}

В силу независимости логарифм функции правдоподобия (§4 главы 9) имеет вид

ln⁡L(θ)=−12[nln⁡det⁡Σ+∑i=1n(xi−μ)TΣ−1(xi−μ)]+const.(9)\ln L(\boldsymbol\theta) = -\frac12\Bigl[n\ln\det\boldsymbol\Sigma + \sum_{i=1}^n(\boldsymbol x_i - \boldsymbol\mu)^T\boldsymbol\Sigma^{-1}(\boldsymbol x_i - \boldsymbol\mu)\Bigr] + \text{const}. \tag{9}

Максимизация L(θ)L(\boldsymbol\theta) эквивалентна минимизации выражения в квадратных скобках. Положим xˉ=(x1+⋯+xn)/n\bar{\boldsymbol x} = (\boldsymbol x_1 + \dots + \boldsymbol x_n)/n и разобьём сумму в (9) на два слагаемых на основе тождества, обобщающего теорему Гюйгенса (задача 3):

∑i=1n(xi−μ)TΣ−1(xi−μ)=n(xˉ−μ)TΣ−1(xˉ−μ)+∑i=1n(xi−xˉ)TΣ−1(xi−xˉ).(10)\sum_{i=1}^n(\boldsymbol x_i - \boldsymbol\mu)^T\boldsymbol\Sigma^{-1}(\boldsymbol x_i - \boldsymbol\mu) = n(\bar{\boldsymbol x} - \boldsymbol\mu)^T\boldsymbol\Sigma^{-1}(\bar{\boldsymbol x} - \boldsymbol\mu) + \sum_{i=1}^n(\boldsymbol x_i - \bar{\boldsymbol x})^T\boldsymbol\Sigma^{-1}(\boldsymbol x_i - \bar{\boldsymbol x}). \tag{10}

По кирпичикам: (10) — та же теорема Гюйгенса, только расстояния меряются «линейкой» Σ−1\boldsymbol\Sigma^{-1}. Сумма квадратов отклонений от любой точки μ\boldsymbol\mu равна сумме отклонений от центра масс xˉ\bar{\boldsymbol x} плюс nn × квадрат расстояния между μ\boldsymbol\mu и xˉ\bar{\boldsymbol x}. Перекрёстное слагаемое исчезает, потому что ∑(xi−xˉ)=0\sum(\boldsymbol x_i - \bar{\boldsymbol x}) = \boldsymbol 0.

Первое слагаемое неотрицательно для любой Σ\boldsymbol\Sigma в силу положительной определённости матрицы Σ−1\boldsymbol\Sigma^{-1} (почему она положительно определена — вопрос 6) и равно 0 только при μ=xˉ\boldsymbol\mu = \bar{\boldsymbol x}. Второе слагаемое от μ\boldsymbol\mu не зависит. Следовательно, достаточно минимизировать по Σ\boldsymbol\Sigma выражение

nln⁡det⁡Σ+∑i=1n(xi−xˉ)TΣ−1(xi−xˉ).(11)n\ln\det\boldsymbol\Sigma + \sum_{i=1}^n(\boldsymbol x_i - \bar{\boldsymbol x})^T\boldsymbol\Sigma^{-1}(\boldsymbol x_i - \bar{\boldsymbol x}). \tag{11}

Введём выборочную ковариационную матрицу

Σ^=1n∑i=1n(xi−xˉ)(xi−xˉ)T.(12)\hat{\boldsymbol\Sigma} = \frac1n\sum_{i=1}^n(\boldsymbol x_i - \bar{\boldsymbol x})(\boldsymbol x_i - \bar{\boldsymbol x})^T. \tag{12}

На основе легко проверяемого тождества yTBy=tr⁡(yyTB)\boldsymbol y^T\boldsymbol B\boldsymbol y = \operatorname{tr}(\boldsymbol y\boldsymbol y^T\boldsymbol B) и линейности оператора tr⁡\operatorname{tr} получаем

∑i=1n(xi−xˉ)TΣ−1(xi−xˉ)=ntr⁡(Σ^Σ−1).(13)\sum_{i=1}^n(\boldsymbol x_i - \bar{\boldsymbol x})^T\boldsymbol\Sigma^{-1}(\boldsymbol x_i - \bar{\boldsymbol x}) = n\operatorname{tr}(\hat{\boldsymbol\Sigma}\boldsymbol\Sigma^{-1}). \tag{13}

По кирпичикам: yTBy\boldsymbol y^T\boldsymbol B\boldsymbol y — это число, а след числа равен ему самому. Значит, yTBy=tr⁡(yTBy)=tr⁡(yyTB)\boldsymbol y^T\boldsymbol B\boldsymbol y = \operatorname{tr}(\boldsymbol y^T\boldsymbol B\boldsymbol y) = \operatorname{tr}(\boldsymbol y\boldsymbol y^T\boldsymbol B) (под следом множители можно циклически переставлять). Складываем по ii с y=xi−xˉ\boldsymbol y = \boldsymbol x_i - \bar{\boldsymbol x} и B=Σ−1\boldsymbol B = \boldsymbol\Sigma^{-1}: сумма ∑(xi−xˉ)(xi−xˉ)T\sum(\boldsymbol x_i - \bar{\boldsymbol x})(\boldsymbol x_i - \bar{\boldsymbol x})^T — это ровно nΣ^n\hat{\boldsymbol\Sigma}.

Учитывая формулу (13), выражение (11) можно переписать в виде

n[ln⁡det⁡Σ+tr⁡(Σ^Σ−1)].(14)n\bigl[\ln\det\boldsymbol\Sigma + \operatorname{tr}(\hat{\boldsymbol\Sigma}\boldsymbol\Sigma^{-1})\bigr]. \tag{14}

Минимизация суммы (14) по Σ\boldsymbol\Sigma эквивалентна минимизации функции

ψ(Σ)=tr⁡(Σ^Σ−1)−m−ln⁡det⁡(Σ^Σ−1)\psi(\boldsymbol\Sigma) = \operatorname{tr}(\hat{\boldsymbol\Sigma}\boldsymbol\Sigma^{-1}) - m - \ln\det(\hat{\boldsymbol\Sigma}\boldsymbol\Sigma^{-1})

(постоянные mm и ln⁡det⁡Σ^\ln\det\hat{\boldsymbol\Sigma} добавлены для дальнейших преобразований).

Так как Σ^\hat{\boldsymbol\Sigma} и Σ\boldsymbol\Sigma — ковариационные матрицы, то (согласно замечанию из П10) они неотрицательно определены, а Σ\boldsymbol\Sigma даже положительно определена в силу невырожденности. Обозначим через λ1≥λ2≥⋯≥λm≥0\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_m \ge 0 собственные значения пары матриц (Σ^,Σ)(\hat{\boldsymbol\Sigma}, \boldsymbol\Sigma), то есть решения характеристического уравнения det⁡(Σ^Σ−1−λE)=0\det(\hat{\boldsymbol\Sigma}\boldsymbol\Sigma^{-1} - \lambda\boldsymbol E) = 0 (см. П10). Тогда

ψ(Σ)=∑l=1m(λl−1−ln⁡λl).\psi(\boldsymbol\Sigma) = \sum_{l=1}^m(\lambda_l - 1 - \ln\lambda_l).

Поскольку λ−1−ln⁡λ≥0\lambda - 1 - \ln\lambda \ge 0 при λ≥0\lambda \ge 0, из последнего соотношения получаем, что ψ(Σ)≥0\psi(\boldsymbol\Sigma) \ge 0. Равенство имеет место только при λ1=⋯=λm=1\lambda_1 = \dots = \lambda_m = 1, то есть для Σ=Σ^\boldsymbol\Sigma = \hat{\boldsymbol\Sigma} (почему — вопрос 7).

Смысл по-пацански: функция λ−1−ln⁡λ\lambda - 1 - \ln\lambda — это «яма» с дном ровно в λ=1\lambda = 1. Каждое собственное значение λl\lambda_l показывает, во сколько раз «подозреваемая» Σ\boldsymbol\Sigma ошибается против выборочной Σ^\hat{\boldsymbol\Sigma} вдоль своей оси. Ошиблась в любую сторону — штраф. Штраф ноль только тогда, когда ошибок нет ни по одной оси, то есть когда Σ\boldsymbol\Sigma и есть Σ^\hat{\boldsymbol\Sigma}.

Таким образом, оценками максимального правдоподобия параметров μ\boldsymbol\mu и Σ\boldsymbol\Sigma являются, соответственно, статистики xˉ\bar{\boldsymbol x} и Σ^\hat{\boldsymbol\Sigma}.

Смысл по-пацански: как и в одномерье, ОМП для среднего — выборочное среднее, для ковариаций — выборочная ковариационная матрица с делителем nn (не n−1n - 1). Вся матричная акробатика нужна только чтобы честно это доказать.

Пример 3. Нормальные наблюдения и функционалы качества

Предположим, что каждое наблюдение ξi\boldsymbol\xi_i (i=1,…,ni = 1, \dots, n) извлечено из одного из kk нормальных законов N(μl,Σl)\mathcal N(\boldsymbol\mu_l, \boldsymbol\Sigma_l) (l=1,…,kl = 1, \dots, k). При этом μl\boldsymbol\mu_l и Σl\boldsymbol\Sigma_l, вообще говоря, неизвестны. Задача исследователя — определить, какие n1n_1 из nn наблюдений извлечены из класса N(μ1,Σ1)\mathcal N(\boldsymbol\mu_1, \boldsymbol\Sigma_1), какие n2n_2 — из N(μ2,Σ2)\mathcal N(\boldsymbol\mu_2, \boldsymbol\Sigma_2) и т. д. Числа nln_l в общем случае также неизвестны.

Введём векторный параметр разбиения γ=(γ1,…,γn)\boldsymbol\gamma = (\gamma_1, \dots, \gamma_n), где γi\gamma_i — номер класса (от 1 до kk), к которому относится наблюдение ξi\boldsymbol\xi_i. Тогда задачу разбиения на классы можно сформулировать как задачу оценивания неизвестных параметров γ1,…,γn\gamma_1, \dots, \gamma_n при «мешающих» неизвестных параметрах μl\boldsymbol\mu_l и Σl\boldsymbol\Sigma_l. Обозначим весь набор неизвестных параметров через θ=(γ,μ1,…,μk,Σ1,…,Σk)\boldsymbol\theta = (\boldsymbol\gamma, \boldsymbol\mu_1, \dots, \boldsymbol\mu_k, \boldsymbol\Sigma_1, \dots, \boldsymbol\Sigma_k). Тогда логарифм функции правдоподобия (см. формулу (9)) будет равен, с точностью до сдвига на константу, величине

−12∑l=1k[nl(γ)ln⁡det⁡Σl+∑xi∈Sl(γ)(xi−μl)TΣl−1(xi−μl)].(15)-\frac12\sum_{l=1}^k\Bigl[n_l(\boldsymbol\gamma)\ln\det\boldsymbol\Sigma_l + \sum_{\boldsymbol x_i \in S_l(\boldsymbol\gamma)}(\boldsymbol x_i - \boldsymbol\mu_l)^T\boldsymbol\Sigma_l^{-1}(\boldsymbol x_i - \boldsymbol\mu_l)\Bigr]. \tag{15}

Максимизируем выражение (15) по θ\boldsymbol\theta. Оговоримся сразу, что состоятельность оценки θ^\hat{\boldsymbol\theta} остаётся под сомнением, поскольку размерность вектора θ\boldsymbol\theta превосходит общее число наблюдений nn.

Смысл по-пацански: у каждого объекта свой неизвестный номер класса γi\gamma_i, а сверху ещё средние и ковариации. Неизвестных больше, чем наблюдений, — как угадывать пароль, в котором символов больше, чем у тебя попыток. Метод работает и даёт разумные разбиения, но гарантии «с ростом nn всё сойдётся» здесь нет: каждый новый объект приносит и новое неизвестное.

Рассуждения, аналогичные проведённым в примере 2, показывают, что оценками максимального правдоподобия для параметров μl\boldsymbol\mu_l при фиксированных γ,Σ1,…,Σk\boldsymbol\gamma, \boldsymbol\Sigma_1, \dots, \boldsymbol\Sigma_k являются центры масс классов xˉl=xˉl(γ)=1nl∑xi∈Sl(γ)xi\bar{\boldsymbol x}_l = \bar{\boldsymbol x}_l(\boldsymbol\gamma) = \frac1{n_l}\sum_{\boldsymbol x_i \in S_l(\boldsymbol\gamma)}\boldsymbol x_i. Подставляя их в (15) и учитывая тождество (10), получаем, что достаточно минимизировать по Σ1,…,Σk\boldsymbol\Sigma_1, \dots, \boldsymbol\Sigma_k и γ\boldsymbol\gamma функцию

∑l=1k[nlln⁡det⁡Σl+∑xi∈Sl(xi−xˉl)TΣl−1(xi−xˉl)],(16)\sum_{l=1}^k\Bigl[n_l\ln\det\boldsymbol\Sigma_l + \sum_{\boldsymbol x_i \in S_l}(\boldsymbol x_i - \bar{\boldsymbol x}_l)^T\boldsymbol\Sigma_l^{-1}(\boldsymbol x_i - \bar{\boldsymbol x}_l)\Bigr], \tag{16}

которая, принимая во внимание равенства (12) и (13), совпадает с

∑l=1k[nlln⁡det⁡Σl+nltr⁡(Σ^lΣl−1)],(17)\sum_{l=1}^k\bigl[n_l\ln\det\boldsymbol\Sigma_l + n_l\operatorname{tr}(\hat{\boldsymbol\Sigma}_l\boldsymbol\Sigma_l^{-1})\bigr], \tag{17}

где Σ^l=1nl∑xi∈Sl(xi−xˉl)(xi−xˉl)T\hat{\boldsymbol\Sigma}_l = \frac1{n_l}\sum_{\boldsymbol x_i \in S_l}(\boldsymbol x_i - \bar{\boldsymbol x}_l)(\boldsymbol x_i - \bar{\boldsymbol x}_l)^T — выборочная ковариационная матрица класса SlS_l. Отметим, что Σ^l=1nlWl\hat{\boldsymbol\Sigma}_l = \frac1{n_l}\boldsymbol W_l, где Wl\boldsymbol W_l — матрица рассеяния класса SlS_l из пояснения к формуле (7).

Анализ выражений (16) и (17) в некоторых частных случаях приводит к ряду интересных выводов.

Случай 1. Σl=σ2E\boldsymbol\Sigma_l = \sigma^2\boldsymbol E (l=1,…,kl = 1, \dots, k), причём параметр σ\sigma известен. Тогда минимизация (16) по γ\boldsymbol\gamma равносильна минимизации функционала качества разбиения на классы F1=VintF1 = V_{int}. Вот откуда «законность» k-средних и метода Уорда: это ОМП для облаков-шаров одинакового размера.

Случай 2. Σl=Σ\boldsymbol\Sigma_l = \boldsymbol\Sigma (l=1,…,kl = 1, \dots, k), где матрица Σ\boldsymbol\Sigma известна. В этом случае минимизируемым функционалом является

F8=∑l=1k∑xi∈Sld(xi,xˉl),F8 = \sum_{l=1}^k\sum_{\boldsymbol x_i \in S_l}d(\boldsymbol x_i, \bar{\boldsymbol x}_l),

где под расстоянием между точками x\boldsymbol x и y\boldsymbol y подразумевается

d(x,y)=(x−y)TΣ−1(x−y)(расстояние Махаланобиса).(18)d(\boldsymbol x, \boldsymbol y) = (\boldsymbol x - \boldsymbol y)^T\boldsymbol\Sigma^{-1}(\boldsymbol x - \boldsymbol y) \quad (\text{расстояние Махаланобиса}). \tag{18}

Случай 3. Σl=Σ\boldsymbol\Sigma_l = \boldsymbol\Sigma (l=1,…,kl = 1, \dots, k), где матрица Σ\boldsymbol\Sigma неизвестна. Тогда выражение (17) можно представить в виде

n[ln⁡det⁡Σ+tr⁡(Σ^intΣ−1)],(19)n\bigl[\ln\det\boldsymbol\Sigma + \operatorname{tr}(\hat{\boldsymbol\Sigma}_{int}\boldsymbol\Sigma^{-1})\bigr], \tag{19}

где

Σ^int=1n∑l=1knlΣ^l=1n∑l=1kWl=1nWint.(20)\hat{\boldsymbol\Sigma}_{int} = \frac1n\sum_{l=1}^kn_l\hat{\boldsymbol\Sigma}_l = \frac1n\sum_{l=1}^k\boldsymbol W_l = \frac1n\boldsymbol W_{int}. \tag{20}

Точно так же, как и в примере 2, находим, что матрица Σ^int\hat{\boldsymbol\Sigma}_{int} минимизирует сумму (19). Подставив её в формулу (19), замечаем, что второе слагаемое превращается в константу, а минимизация первого по γ\boldsymbol\gamma равносильна минимизации функционала F5=det⁡WintF5 = \det\boldsymbol W_{int}.

Замечание 6. Если матрицы ковариаций Σl\boldsymbol\Sigma_l (l=1,…,kl = 1, \dots, k) совпадают, то можно обобщить одномерный F-критерий однофакторного дисперсионного анализа (см. формулу (9) главы 16) на многомерную нормальную модель. Например, для проверки гипотезы о равенстве средних H0 ⁣:μ1=μ2=⋯=μkH_0\colon \boldsymbol\mu_1 = \boldsymbol\mu_2 = \dots = \boldsymbol\mu_k в качестве статистик критерия будем использовать монотонные функции от F7=det⁡Wint/det⁡WtotF7 = \det\boldsymbol W_{int}/\det\boldsymbol W_{tot}. Положим для краткости L≡F7L \equiv F7 (её называют лямбдой Уилкса). Известно, что при справедливости гипотезы H0H_0:

  • а) n−k−1k−1⋅1−LL∼F2k−2, 2(n−k−1)\dfrac{n - k - 1}{k - 1}\cdot\dfrac{1 - \sqrt L}{\sqrt L} \sim F_{2k-2,\,2(n-k-1)}, если m=2m = 2 и k≥2k \ge 2;
  • б) n−k−m+1m⋅1−LL∼Fm, n−k−m+1\dfrac{n - k - m + 1}m\cdot\dfrac{1 - L}L \sim F_{m,\,n-k-m+1}, если m≥1m \ge 1 и k=2k = 2;
  • в) n−k−m+1m⋅1−LL∼F2m, 2(n−k−m+1)\dfrac{n - k - m + 1}m\cdot\dfrac{1 - \sqrt L}{\sqrt L} \sim F_{2m,\,2(n-k-m+1)}, если m≥1m \ge 1 и k=3k = 3.

Для других значений mm и kk и больших nn можно указать хорошую аппроксимацию, предложенную М. Бартлеттом (1947 г.): статистика −(n−1−m+k2)ln⁡L-\bigl(n - 1 - \frac{m + k}2\bigr)\ln L имеет приближённо χ2\chi^2-распределение с m(k−1)m(k - 1) степенями свободы.

Обобщение на многомерный случай F-критерия двухфакторного дисперсионного анализа (см. пример 1 главы 17) тоже существует.

Случай 4. Матрицы ковариаций Σl\boldsymbol\Sigma_l не равны между собой и неизвестны. Минимизируя отдельно каждое слагаемое в сумме (17), находим, что оценками максимального правдоподобия для Σl\boldsymbol\Sigma_l служат выборочные ковариационные матрицы Σ^l\hat{\boldsymbol\Sigma}_l. Подставив их в формулу (17), превращаем вторые слагаемые в квадратных скобках в константы. При этом минимизируемый по γ\boldsymbol\gamma функционал приобретает вид

F9=∑l=1knlln⁡det⁡Σ^l.F9 = \sum_{l=1}^kn_l\ln\det\hat{\boldsymbol\Sigma}_l.

Заметим, что функционал F9F9 равносилен (взвешенному) среднему геометрическому определителей матриц Σ1,…,Σk\boldsymbol\Sigma_1, \dots, \boldsymbol\Sigma_k, в то время как функционал F5F5 эквивалентен определителю матрицы, равной (взвешенному) среднему арифметическому этих же матриц (см. формулу (20)).

Смысл по-пацански: каждый функционал качества — это чья-то вероятностная модель в маскировке. Шары одного размера — F1F1. Одинаковые эллипсоиды известной формы — F8F8. Одинаковые эллипсоиды неизвестной формы — F5F5. Эллипсоиды кто во что горазд — F9F9. Выбрал функционал — значит, молча выбрал модель.

Пример 4. Собака или волк: дискриминантный анализ

В таблице на рис. 16 у Лагутина указаны размеры челюстей и зубов 30 собак (номера 1–30), 12 волков (номера 31–42) и ископаемого черепа неизвестного животного (номер 43), найденного в четвертичном слое. Данные — Де Бониса. Измеряемые характеристики:

  1. длина черепа;
  2. длина верхней челюсти;
  3. ширина верхней челюсти;
  4. длина верхнего карнивора;
  5. длина первого верхнего моляра;
  6. ширина первого верхнего моляра.

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

Для того чтобы это сделать, воспользуемся статистической моделью случайного выбора единственного наблюдения из некоторого многомерного нормального закона. Заранее известно, что этот закон является одним из kk заданных законов N(μl,Σl)\mathcal N(\boldsymbol\mu_l, \boldsymbol\Sigma_l), l=1,…,kl = 1, \dots, k.

В соответствии с принципом максимального правдоподобия будем считать областью притяжения закона N(μl,Σl)\mathcal N(\boldsymbol\mu_l, \boldsymbol\Sigma_l) (l=1,…,kl = 1, \dots, k) множество таких точек x∈Rm\boldsymbol x \in \mathbb R^m, где плотность распределения N(μl,Σl)\mathcal N(\boldsymbol\mu_l, \boldsymbol\Sigma_l) больше других. Это равносильно тому, что величина

hl(x)=ln⁡det⁡Σl+(x−μl)TΣl−1(x−μl)h_l(\boldsymbol x) = \ln\det\boldsymbol\Sigma_l + (\boldsymbol x - \boldsymbol\mu_l)^T\boldsymbol\Sigma_l^{-1}(\boldsymbol x - \boldsymbol\mu_l)

имеет наименьшее значение среди h1,…,hkh_1, \dots, h_k (см. формулу (8)). При m=1m = 1 и k=2k = 2 получается разбиение прямой на две области притяжения: граница между ними проходит там, где пересекаются две колоколообразные плотности.

Замечание 7. В случае k=2k = 2 данный способ выбора между законами с произвольными (известными) плотностями p1p_1 и p2p_2 минимизирует сумму α+β\alpha + \beta вероятностей ошибок I и II рода при проверке гипотезы H1 ⁣:p(x)=p1(x)H_1\colon p(\boldsymbol x) = p_1(\boldsymbol x) (см. §1 главы 13) против альтернативы H2 ⁣:p(x)=p2(x)H_2\colon p(\boldsymbol x) = p_2(\boldsymbol x) по единственному наблюдению x0∈Rm\boldsymbol x_0 \in \mathbb R^m.

Доказательство. Обозначим через GG критическое множество критерия для проверки гипотезы H1H_1 против альтернативы H2H_2. Тогда

α+β=∫Gp1(x) dx+∫Rm∖Gp2(x) dx=1+∫G(p1(x)−p2(x))dx.\alpha + \beta = \int_Gp_1(\boldsymbol x)\,d\boldsymbol x + \int_{\mathbb R^m\setminus G}p_2(\boldsymbol x)\,d\boldsymbol x = 1 + \int_G\bigl(p_1(\boldsymbol x) - p_2(\boldsymbol x)\bigr)d\boldsymbol x.

Интеграл в правой части принимает наименьшее значение в случае, когда множество GG состоит из всех точек, где подынтегральная функция неположительна, то есть p2(x)≥p1(x)p_2(\boldsymbol x) \ge p_1(\boldsymbol x). ■\blacksquare

Отметим, что оптимальное множество GG принадлежит (при c=1c = 1) семейству критических множеств из критерия Неймана — Пирсона (см. §2 главы 13): Gc={x∈Rm ⁣:p2(x)/p1(x)≥c}G_c = \{\boldsymbol x \in \mathbb R^m\colon p_2(\boldsymbol x)/p_1(\boldsymbol x) \ge c\}.

Для α+β\alpha + \beta можно получить оценку сверху:

α+β≤e−B,гдеB=−ln⁡∫p1(x)p2(x) dx.\alpha + \beta \le e^{-B}, \qquad \text{где}\quad B = -\ln\int\sqrt{p_1(\boldsymbol x)p_2(\boldsymbol x)}\,d\boldsymbol x.

Здесь B=B(p1,p2)B = B(p_1, p_2) — расстояние Бхаттачария. Оно инвариантно относительно взаимно однозначных преобразований координат и обращается в нуль при p1=p2p_1 = p_2. Известно, что для двух нормальных законов

B=12ln⁡det⁡(Σ1+Σ22)(det⁡Σ1)(det⁡Σ2)+18(μ2−μ1)T(Σ1+Σ22)−1(μ2−μ1).B = \frac12\ln\frac{\det\bigl(\frac{\boldsymbol\Sigma_1 + \boldsymbol\Sigma_2}2\bigr)}{\sqrt{(\det\boldsymbol\Sigma_1)(\det\boldsymbol\Sigma_2)}} + \frac18(\boldsymbol\mu_2 - \boldsymbol\mu_1)^T\Bigl(\frac{\boldsymbol\Sigma_1 + \boldsymbol\Sigma_2}2\Bigr)^{-1}(\boldsymbol\mu_2 - \boldsymbol\mu_1).

В частности, при Σ1=Σ2\boldsymbol\Sigma_1 = \boldsymbol\Sigma_2 видим, что B=d(μ1,μ2)/8B = d(\boldsymbol\mu_1, \boldsymbol\mu_2)/8, где d(x,y)d(\boldsymbol x, \boldsymbol y) обозначает расстояние Махаланобиса (см. формулу (18)).

По кирпичикам: откуда оценка. Так как min⁡(a,b)≤ab\min(a, b) \le \sqrt{ab}, получаем α+β=∫min⁡(p1,p2)≤∫p1p2=e−B\alpha + \beta = \int\min(p_1, p_2) \le \int\sqrt{p_1p_2} = e^{-B}. Первое равенство — это и есть доказанное замечание 7: при оптимальном GG в каждой точке «платим» меньшую из двух плотностей.

Расчёт

Применим эти результаты к данным о собаках (l=1l = 1) и волках (l=2l = 2).

  • Чтобы уравнять влияние размеров черепа и зубов (первые на порядок больше последних), нормируем столбцы таблицы рис. 16 с помощью устойчивого к выделяющимся наблюдениям преобразования Z′=(Z−MED)/MADZ' = (Z - MED)/MAD (нормировка N3 из §1).
  • Так как истинные μl\boldsymbol\mu_l и Σl\boldsymbol\Sigma_l неизвестны, используем вместо них оценки максимального правдоподобия xˉl\bar{\boldsymbol x}_l и Σ^l\hat{\boldsymbol\Sigma}_l.

В результате подсчётов получим значения h1=−2,94h_1 = -2{,}94 и h2=39,7h_2 = 39{,}7. Поскольку h1<h2h_1 < h_2, в соответствии с принципом максимального правдоподобия неизвестное ископаемое животное, скорее всего, было собакой. При этом значение B=4,08B = 4{,}08 приводит к оценке суммы вероятностей ошибок I и II рода величиной e−B≈0,017e^{-B} \approx 0{,}017.

Мы пересчитали всё заново, и книжные числа воспроизводятся точно (h1=−2,940h_1 = -2{,}940, h2=39,671h_2 = 39{,}671, B=4,079B = 4{,}079) при одном уточнении: медиану и MAD для нормировки нужно считать по всем 43 строкам, включая неизвестное животное.

Собака или волк: дискриминантный анализ

h собак
h волков

Признаки нормированы по N3 (медиана и MAD) по всем 43 строкам рис. 16; μ_l и Σ_l заменены оценками максимального правдоподобия (Σ̂ с делителем n). Относим череп к закону с меньшим h.h₁ (собаки) = -2,94, h₂ (волки) = 39,67 → собака. Расстояние Бхаттачария B = 4,08, оценка α + β ≤ e−B = 0,0169. Как в книге: h₁ = −2,94, h₂ = 39,7, B = 4,08, e^{−B} ≈ 0,017.Скользящий контроль: из 42 известных животных, классифицированных по моделям без них самих, ошибочно отнесено 2.Замечание 6 (собаки против волков, H₀: μ₁ = μ₂ при общей Σ): L = det W_int / det W_tot = 0,1764, F = 27,23 при (6, 35) степенях свободы, p = 8,2e-12; приближение Бартлетта χ² = 64,19, p = 6,3e-12.

Сверх книги посчитаем и лямбду Уилкса из замечания 6 для 42 известных животных. Получается L=0,176L = 0{,}176, по пункту б) F=27,2F = 27{,}2 при (6, 35)(6,\ 35) степенях свободы, p≈8⋅10−12p \approx 8\cdot10^{-12}. Средние собак и волков различаются, в чём, впрочем, никто и не сомневался. Строго говоря, критерий предполагает равные ковариационные матрицы, а дискриминантный анализ выше их не уравнивал.

Ещё одна проверка — скользящий контроль. Каждое из 42 известных животных по очереди «прячем», оцениваем модели по остальным и классифицируем спрятанное. Ошибаемся на двух из 42. Это честнее, чем оценка e−Be^{-B}: та использует оценки параметров так, будто это истинные значения.

Загрузка редактора…

Этот вывод подтверждает и диаграмма рассеяния нормированных признаков 1 (длина черепа) и 4 (длина верхнего карнивора) — рис. 19 у Лагутина; её можно построить в режиме «Диаграмма рассеяния» виджета и в §8. На основе диаграммы можно заключить, что главным признаком, с помощью которого различаются собаки и волки, является размер зубов.

Бабушка, а почему у тебя такие большие зубы?

— Красная Шапочка

Смысл по-пацански: череп собачий — по зубам видно. Волчьи карниворы длиннее, и это различие сильнее, чем по любой длине черепа: собаки бывают и мелкие, и крупные, а зубы у волка всё равно больше.

Проверь себя

Тест

Какой функционал качества не меняется при любом невырожденном линейном преобразовании координат объектов (например, при смене единиц измерения признаков)?

Тест

В модели нормальной смеси все Σ_l = σ²E с известным σ. Какой функционал тогда минимизирует оценка максимального правдоподобия для разбиения?
Обновлено