Сжать климат до k чисел
Климат города в статье о методе главных компонент описан 24 числами: средняя температура и сумма осадков каждого месяца. Хранить нужно меньше. Разрешено заменить каждый город точкой на какой-нибудь k-мерной плоскости в 24-мерном пространстве — не обязательно проходящей через ноль и не обязательно вдоль осей, — а восстанавливать город этой точкой. Каков наименьший возможный средний квадрат промаха?
Формально: даны n точек x1, …, xn в пространстве размерности d и число k. Для k-мерной плоскости P промах точки — квадрат расстояния от неё до P. Найдите наименьшее по всем k-мерным плоскостям значение среднего промаха
$$E_k = \min_P \frac{1}{n}\sum_{i=1}^{n} \operatorname{dist}^2(x_i, P).$$0-мерная плоскость — это одна точка. Тесты с третьего по шестой — климат 469 городов из статьи: температура в десятых долях градуса, осадки в миллиметрах.
Вход
В первой строке n, d, k (1 ≤ n ≤ 2000, 1 ≤ d ≤ 30, 0 ≤ k ≤ d). Дальше n строк по d целых чисел, по модулю не больше 10⁵.
Выход
Одно число — Ek, с абсолютной или относительной погрешностью 10⁻⁶.
Примеры
Пример 1
4 2 1 0 1 2 3 4 4 6 7
0.091180794
Пример 2
3 3 0 1 2 3 4 0 6 7 8 2
20.444444444
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Начните с k = 0: какая точка лучше всех заменяет облако, и чему тогда равен средний промах? Через что он выражается в терминах матрицы ковариаций?
2Подсказка 2
Если оставить k столбцов с наибольшей дисперсией, промах — сумма дисперсий остальных. Но плоскость может идти под углом к осям. В каких осях матрица ковариаций диагональна?
3Идея
Лучшая плоскость проходит через центр масс облака: сдвиг к нему уменьшает промах любой плоскости, как для k = 0, где лучшая точка — среднее, а промах — сумма дисперсий, след матрицы ковариаций S = (1/n)·Σ(xi − x̄)(xi − x̄)T. Сумма квадратов расстояний до точек плоскости раскладывается по теореме Пифагора на «тень» на плоскость и «промах» поперёк. Чем больше тени, тем меньше промах, а сумма теней на плоскость с ортонормированным базисом v1, …, vk равна ΣvjTSvj. Наибольшее значение этой суммы — сумма k наибольших собственных значений S, и достигается оно на главных компонентах. Значит,
$$E_k = \lambda_{k+1} + \lambda_{k+2} + \dots + \lambda_d,$$сумма отброшенных собственных значений. Это утверждение Эккарта и Янга (1936) в форме для облаков точек.
4Разбор
Центрируем столбцы, строим матрицу S размера d × d и находим все её собственные значения. Для симметричной матрицы 30 × 30 удобен метод вращений Якоби: каждое вращение в плоскости двух координат обнуляет пару внедиагональных элементов, сумма их квадратов от прохода к проходу быстро падает, и на диагонали остаются собственные значения. Хватает десятка проходов. Степенной метод с исчерпыванием тоже годится, но когда собственные значения близки, он сходится медленно, а здесь нужны все.
Сумму отброшенных значений лучше складывать напрямую, а не как след минус сумму оставленных: во втором случае маленький ответ получается вычитанием двух больших чисел. На климате городов две компоненты оставляют средний промах в несколько раз меньше, чем две лучшие оси-столбцы; это видно, если сравнить с ошибочным решением ниже.
4+Решение
5Сложность
O(n·d²) на матрицу ковариаций и O(d³) на проход Якоби, проходов — единицы и десятки.
6Типичные ошибки
- Оставить столбцы, а не направления. Выбрать k столбцов с наибольшей дисперсией и отбросить остальные — естественно, но это лишь одна из плоскостей, параллельная осям. Температуры соседних месяцев сильно связаны, и плоскость под углом выигрывает многократно.
- Не центрировать. Собственные значения матрицы ΣxixiT/n без вычитания среднего описывают плоскости, проходящие через ноль, — а лучшей плоскости через ноль проходить не нужно.
- Терять маленький ответ. При k = d ответ ровно 0; в седьмом тесте облако лежит в 4-мерной плоскости, и ответ тоже ноль — вычисленный с точностью до округления.