Найти параметры линейной зависимости методом наименьших квадратов
Решения задач: метод наименьших квадратов
Метод наименьших квадратов применяется для решения различных математических задач и основан на минимизации суммы квадратов отклонений функций от исходных переменных. Мы рассмотриваем его приложение к математической статистике в простейшем случае, когда нужно найти зависимость (парную линейную регрессию) между двумя переменными, заданными выборочными данным. В этом случае речь идет об отклонениях теоретических значений от экспериментальных.
Иногда дополнительно к нахождению уравнения регрессии требуется: найти остаточную дисперсию, сделать прогноз значений, найти значение коэффициента корреляции, проверить качество аппроксимации и значимость модели. Примеры решений вы найдете ниже. Удачи в изучении!
Примеры решений МНК
Пример 1. Методом наименьших квадратов для данных, представленных в таблице, найти линейную зависимость
Пример 2. Прибыль фирмы за некоторый период деятельности по годам приведена ниже:
Год 1 2 3 4 5
Прибыль 3,9 4,9 3,4 1,4 1,9
1) Составьте линейную зависимость прибыли по годам деятельности фирмы.
2) Определите ожидаемую прибыль для 6-го года деятельности. Сделайте чертеж.
Пример 3. Экспериментальные данные о значениях переменных х и y приведены в таблице:
1 2 4 6 8
3 2 1 0,5 0
В результате их выравнивания получена функция Используя метод наименьших квадратов, аппроксимировать эти данные линейной зависимостью (найти параметры а и b). Выяснить, какая из двух линий лучше (в смысле метода наименьших квадратов) выравнивает экспериментальные данные. Сделать чертеж.
Пример 4. Данные наблюдений над случайной двумерной величиной (Х, Y) представлены в корреляционной таблице. Методом наименьших квадратов найти выборочное уравнение прямой регрессии Y на X.
Метод наименьших квадратов для линейной зависимости y = f(x)
Программа МНК
Введите данные
Данные и аппроксимация y = a + b·x
i – номер экспериментальной точки;
xi – значение фиксированного параметра в точке i;
yi – значение измеряемого параметра в точке i;
ωi – вес измерения в точке i;
yi, расч. – разница между измеренным и вычисленным по регрессии значением y в точке i;
Sxi(xi) – оценка погрешности xi при измерении y в точке i.
Результат
График
Кликните по графику,
чтобы добавить значения в таблицу
Данные и аппроксимация y = k·x
Результат
График
Кликните по графику,
чтобы добавить значения в таблицу
Инструкция пользователя онлайн-программы МНК.
В поле данных введите на каждой отдельной строке значения `x` и `y` в одной экспериментальной точке. Значения должны отделяться пробельным символом (пробелом или знаком табуляции).
Третьим значением может быть вес точки `w`. Если вес точки не указан, то он приравнивается единице. В подавляющем большинстве случаев веса экспериментальных точек неизвестны или не вычисляются, т.е. все экспериментальные данные считаются равнозначными. Иногда веса в исследуемом интервале значений совершенно точно не равнозначны и даже могут быть вычислены теоретически. Например, в спектрофотометрии веса можно вычислить по простым формулам, правда в основном этим все пренебрегают для уменьшения трудозатрат.
Данные можно вставить через буфер обмена из электронной таблицы офисных пакетов, например Excel из Майкрософт Офиса или Calc из Оупен Офиса. Для этого в электронной таблице выделите диапазон копируемых данных, скопируйте в буфер обмена и вставьте данные в поле данных на этой странице.
Для расчета по методу наименьших квадратов необходимо не менее двух точек для определения двух коэффициентов `b` – тангенса угла наклона прямой и `a` – значения, отсекаемого прямой на оси `y`.
Для оценки погрешности расчитываемых коэффициентов регресии нужно задать количество экспериментальных точек больше двух. Чем больше количество экспериментальных точек, тем более точна статистическая оценка коэффицинетов (за счет снижения коэффицинета Стьюдента) и тем более близка оценка к оценке генеральной выборки.
Получение значений в каждой экспериментальной точке часто сопряжено со значительными трудозатратами, поэтому часто проводят компромиссное число экспериментов, которые дает удобоваримую оценку и не привеодит к чрезмерным трудо затратам. Как правило число экспериментах точек для линейной МНК зависимости с двумя коэффицинетами выбирает в районе 5-7 точек.
Краткая теория метода наименьших квадратов для линейной зависимости
Допустим у нас имеется набор экспериментальных данных в виде пар значений [`y_i`, `x_i`], где `i` – номер одного эксперементального измерения от 1 до `n`; `y_i` – значение измеренной величины в точке `i`; `x_i` – значение задаваемого нами параметра в точке `i`.
В качестве примера можно рассмотреть действие закона Ома. Изменяя напряжение (разность потенциалов) между участками электрической цепи, мы замеряем величину тока, проходящего по этому участку. Физика нам дает зависимость, найденную экспериментально:
`I = U / R`,
где `I` – сила тока; `R` – сопротивление; `U` – напряжение.
В этом случае `y_i` у нас имеряемая величина тока, а `x_i` – значение напряжения.
В качестве другого примера рассмотрим поглощение света раствором вещества в растворе. Химия дает нам формулу:
`A = ε l C`,
где `A` – оптическая плотность раствора; `ε` – коэффициент пропускания растворенного вещества; `l` – длина пути при прохождении света через кювету с раствором; `C` – концентрация растворенного вещества.
В этом случае `y_i` у нас имеряемая величина отптической плотности `A`, а `x_i` – значение концентрации вещества, которое мы задаем.
Мы будем рассматривать случай, когда относительная погрешность в задании `x_i` значительно меньше, относительной погрешности измерения `y_i`. Так же мы будем предполагать, что все измеренные величины `y_i` случайные и нормально распределенные, т.е. подчиняются нормальному закону распределения.
В случае линейной зависимости `y` от `x`, мы можем написать теоретическую зависимость:
`y = a + b x`.
С геометрической точки зрения, коэффициент `b` обозначает тангенс угла наклона линии к оси `x`, а коэффициент `a` – значение `y` в точке пересечения линии с осью `y` (при `x = 0`).
Нахождение параметров линии регресии.
В эксперименте измеренные значения `y_i` не могут точно лечь на теоеретическую прямую из-за ошибок измерения, всегда присущих реальной жизни. Поэтому линейное уравнение, нужно представить системой уравнений:
`y_i = a + b x_i + ε_i` (1),
где `ε_i` – неизвестная ошибка измерения `y` в `i`-ом эксперименте.
Зависимость (1) так же называют регрессией, т.е. зависимостью двух величин друг от друга со статистической значимостью.
Задачей восстановления зависимости является нахождение коэффициентов `a` и `b` по экспериментальным точкам [`y_i`, `x_i`].
Для нахождения коэффициентов `a` и `b` обычно используется метод наименьших квадратов (МНК). Он является частным случаем принципа максимального правдоподобия.
Тогда сумма квадратов ошибок будет
Принципом МНК (метода наименьших квадратов) является минимизация суммы (2) относительно параметров `a` и `b`. Минимум достигается, когда частные производные от суммы (2) по коэффициентам `a` и `b` равны нулю:
Раскрывая производные, получаем систему из двух уравнений с двумя неизвестными:
Раскрываем скобки и переносим независящие от искомых коэффициентов суммы в другую половину, получим систему линейных уравнений:
Решая, полученную систему, находим формулы для коэффициентов `a` и `b`:
Оценка погрешностей коэффициентов линии регресии
Для более точной оценки погрешности вычисления коэффициентов `a` и `b` желательно большое количество экспериментальных точек. При `n = 2`, оценить погрешность коэффициентов невозможно, т.к. аппроксимирующая линия будет однозначно проходить через две точки.
Погрешность случайной величины `V` определяется законом накопления ошибок
`S_V^2 = sum_(i=1)^p (frac(partial f)(partial z_i))^2 S_(z_i)^2`,
где `p` – число параметров `z_i` с погрешностью `S_(z_i)`, которые влияют на погрешность `S_V`;
`f` – функция зависимости `V` от `z_i`.
Распишем закон накопления ошибок для погрешности коэффициентов `a` и `b`
`S_y^2 = S_(y_i)^2` – погрешность (дисперсия, квадрат стандартного отклонения) в измерении `y` в предположении, что погрешность однородна для всех значений `y`.
Подставляя в полученные выражения формулы для расчета `a` и `b` получим
В большинстве реальных экспериментов значение `Sy` не измеряется. Для этого нужно проводить несколько паралельных измерений (опытов) в одной или нескольких точках плана, что увеличивает время (и возможно стоимость) эксперимента. Поэтому обычно полагают, что отклонение `y` от линии регрессии можно считать случайным. Оценку дисперсии `y` в этом случае, считают по формуле.
Делитель `n-2` появляется потому, что у нас снизилось число степеней свободы из-за расчета двух коэффициентов по этой же выборке экспериментальных данных.
Такую оценку еще называют остаточной дисперсией относительно линии регрессии `S_(y, ост)^2`.
Оценка значимости коэффициентов проводится по критерию Стьюдента
Если рассчитанные критерии `t_a`, `t_b` меньше табличных критериев `t(P, n-2)`, то считается, что соответсвующий коэффициент не значимо отличается от нуля с заданной вероятностью `P`.
Если `t_a F(P, n-1, n-2)`, считается статистически значимым с вероятностью `P` различие между описанием зависимости `y = f(x)` с помощью уравенения регресии и описанием с помощью среднего. Т.е. регрессия лучше описывает зависимость, чем разброс `y` относительно среднего.
© метод-наименьших-квадратов.рф, 2017 – 2021
Метод наименьших квадратов
Метод наименьших квадратов (МНК) — это статистическая процедура для довольно точного прогнозирования поведения зависимых переменных.
Например, можно понять, как будет меняться товарооборот (значение “y”) сети магазинов с изменением размеров торговой площади (значение “x”).
Суть МНК — из всех линейных функций найти наилучшее приближение к реальности. Это можно сделать путём поиска функции с наименьшим отклонением (точнее по процессу МНК: поиск минимальной суммы квадратов отклонений значений y (игрек) от полученного уравнения регрессии).
Решение МНК
Мы ищем уравнение линейной регрессии, которое выглядит так: y = ax + b
Метод 1
Шаги, которые мы будем делать для поиска y = ax + b (сейчас мы их все пройдём на примере):
Шаг 1: Для каждой точки (x, y) вычислить x² и xy.
Шаг 2: Суммировать все x, y, x² и xy, это даст нам Σx, Σy, Σx² и Σxy (если кто забыл, Σ означает “сумма”).
Шаг 3: Рассчитать наклон a по этой формуле:
, где N – количество данных
Шаг 4: Рассчитать значение числа b:
, где N – количество данных
Шаг 5: Подставить найденные числа по местам в уравнение (y = ax + b)
Пример
После некоторых наблюдений, у нас появились данные о размерах и продажах некой торговой сети, у которой 5 магазинов:
| Размер (x) | Продажи (y) |
|---|---|
| 2 | 4 |
| 3 | 6 |
| 5 | 8 |
| 7 | 10 |
| 9 | 12 |
Для наглядности, например, это магазины мороженого, и 2-метровая лавочка продаёт в месяц 4 тонны мороженого, 7 метровая — 10 тонн.
Сразу можно записать, что N = 5 (количество данных; т.е. всего у нас данные по пяти магазинам, ведь у нас 5 строк данных).
Для каждой точки (x, y) вычисляем x² и xy. Для этого, к уже существующим столбцам добавим ещё два: x² и xy.
Шаг 2: Суммировать все x, y, x² и xy, это даст нам Σx, Σy, Σx² и Σxy (складываем каждый столбик):
| x | y | x² | xy |
|---|---|---|---|
| 2 | 4 | 2² = 4 | 2 × 4 = 8 |
| 3 | 6 | 3² = 9 | 3 × 6 = 18 |
| 5 | 8 | 25 | 40 |
| 7 | 10 | 49 | 70 |
| 9 | 12 | 81 | 108 |
| Σx = 26 | Σy = 40 | Σx² = 168 | Σxy = 244 |
Шаг 3: Рассчитать a (наклон графика) по этой формуле:
, где N – количество данных
Помним, что N = 5, значит:
Шаг 4: Рассчитать значение числа b:
, где N – количество данных
Помним, что N = 5, значит:
Шаг 5: Подставить найденные числа по местам в уравнение
y = ax + b ⇒ y = 1,0976x + 2,29248
Далее можем проверить. Можем составить вот такой график, вместе с данными точками и полученной функцией:
Также мы можем использовать эту функцию, чтобы понять, как будут зависеть продажи фирмы от размера помещения. Например: руководство хочет открыть магазин размером в 11,5 м². Для этого подставляем 11,5 вместо x:
y = 1,0976x + 2,29248 ⇒ y = 1,0976 × 11,5 + 2,29248 = 14,91488
Ответ: этот магазин размером в 11,5 м² будет продавать около 15 тонн мороженого в месяц.
Метод 2
Мы продолжаем искать уравнение линейной регрессии, которое выглядит так: y = ax + b.
Используем тот же пример с сетью магазинов.
| Размер (x) | Продажи (y) |
|---|---|
| 2 | 4 |
| 3 | 6 |
| 5 | 8 |
| 7 | 10 |
| 9 | 12 |
Шаг 1: Опять суммируем все x, y, x² и xy, т.е. находим Σx, Σy, Σx² и Σxy (складываем каждый столбик):
| x | y | x² | xy |
|---|---|---|---|
| 2 | 4 | 2² = 4 | 2 × 4 = 8 |
| 3 | 6 | 3² = 9 | 3 × 6 = 18 |
| 5 | 8 | 25 | 40 |
| 7 | 10 | 49 | 70 |
| 9 | 12 | 81 | 108 |
| Σx = 26 | Σy = 40 | Σx² = 168 | Σxy = 244 |
Шаг 2: Записать вот такую систему уравнений (так мы будем искать параметры a и b):
Шаг 3: Помним, что N = 5. Таким образом, из нашего примера получаем систему:
Лучше конечно её переписать красиво:
Шаг 4: Решить систему.
Находим a = 1,0976; b = 2,29248; и ставим по местам в функцию (y = ax + b). Получается y = 1,0976x + 2,29248
Для проверки лучше составить график с данными точками и найденной функцией, как в методе 1.
Методы наименьших квадратов без слёз и боли
Итак, очередная статья из цикла «математика на пальцах». Сегодня мы продолжим разговор о методах наименьших квадратов, но на сей раз с точки зрения программиста. Это очередная статья в серии, но она стоит особняком, так как вообще не требует никаких знаний математики. Статья задумывалась как введение в теорию, поэтому из базовых навыков она требует умения включить компьютер и написать пять строк кода. Разумеется, на этой статье я не остановлюсь, и в ближайшее же время опубликую продолжение. Если сумею найти достаточно времени, то напишу книгу из этого материала. Целевая публика — программисты, так что хабр подходящее место для обкатки. Я в целом не люблю писать формулы, и я очень люблю учиться на примерах, мне кажется, что это очень важно — не просто смотреть на закорючки на школьной доске, но всё пробовать на зуб.
Итак, начнём. Давайте представим, что у меня есть триангулированная поверхность со сканом моего лица (на картинке слева). Что мне нужно сделать, чтобы усилить характерные черты, превратив эту поверхность в гротескную маску?
Пример 1: сглаживание данных
Давайте расскажу, как это работает. Начнём издалека, представьте, что у нас есть обычный массив f, например, из 32 элементов, инициализированный следующим образом:
А затем мы тысячу раз выполним следующую процедуру: для каждой ячейки f[i] мы запишем в неё среднее значение соседних ячеек: f[i] = ( f[i-1] + f[i+1] )/2. Чтобы было понятнее, вот полный код:
Каждая итерация будет сглаживать данные нашего массива, и через тысячу итераций мы получим постоянное значение во всех ячейках. Вот анимация первых ста пятидесяти итераций:
Если вам неясно, почему происходит сглаживание, прямо сейчас остановитесь, возьмите ручку и попробуйте порисовать примеры, иначе дальше читать не имеет смысла. Триангулированная поверхность ничем принципиально от этого примера не отличается. Представьте, что для каждой вершины мы найдём соседние с ней, посчитаем их центр масс, и передвинем нашу вершину в этот центр масс, и так десять раз. Результат будет вот таким:
Разумеется, если не остановиться на десяти итерациях, то через некоторое время вся поверхность сожмётся в одну точку ровно так же, как и в предыдущем примере весь массив стал заполнен одним и тем же значением.
Пример 2: усиление/ослабление характеристических черт
Полный код доступен на гитхабе, а здесь я приведу самую важную часть, опустив лишь чтение и запись 3Д моделей. Итак, триангулированная модель у меня представлена двумя массивами: verts и faces. Массив verts — это просто набор трёхмерных точек, они же вершины полигональной сетки. Массив faces — это набор треугольников (количество треугольников равно faces.size()), для каждого треугольника в массиве хранятся индексы из массива вершин. Формат данных и работу с ним я подробно описывал в своём курсе лекций по компьютерной графике. Есть ещё третий массив, который я пересчитываю из первых двух (точнее, только из массива faces) — vvadj. Это массив, который для каждой вершины (первый индекс двумерного массива) хранит индексы соседних с ней вершин (второй индекс).
Первое, что я делаю, это для каждой вершины моей поверхности считаю вектор кривизны. Давайте проиллюстрируем: для текущей вершины v я перебираю всех её соседей n1-n4; затем я считаю их центр масс b = (n1+n2+n3+n4)/4. Ну и финальный вектор кривизны может быть посчитан как c=v-b, это не что иное, как обычные конечные разности для второй производной.
Непосредственно в коде это выглядит следующим образом:
Ну а дальше мы много раз делаем следующую вещь (смотрите предыдущую картинку): мы вершину v двигаем v := b + const * c. Обратите внимание, что если константа равна единице, то наша вершина никуда не сдвинется! Если константа равна нулю, то вершина заменяется на центр масс соседних вершин, что будет сглаживать нашу поверхность. Если константа больше единицы (заглавная картинка сделана при помощи const=2.1), то вершина будет сдвигаться в направлении вектора кривизны поверхности, усиливая детали. Вот так это выглядит в коде:
Кстати, если меньше единицы, то детали будут наоборот ослабляться (const=0.5), но это не будет эквивалентно простому сглаживанию, «контраст картинки» останется:
Пример 3: добавляем ограничения
Давайте вернёмся к самому первому примеру, и сделаем ровно то же самое, но только не будем переписывать элементы массива под номерами 0, 18 и 31:
Остальные, «свободные» элементы массива я инициализировал нулями, и по-прежнему итеративно заменяю их на среднее значение соседних элементов. Вот так выглядит эволюция массива на первых ста пятидесяти итерациях:
Вполне очевидно, что на сей раз решение сойдётся не к постоянному элементу, заполняющему массив, а к двум линейным рампам. Кстати, действительно ли всем очевидно? Если нет, то экспериментируйте с этим кодом, я специально привожу примеры с очень коротким кодом, чтобы можно было досконально разобраться с происходящим.
Лирическое отступление: численное решение систем линейных уравнений.
Пусть нам дана обычная система линейных уравнений:
Её можно переписать, оставив в каждом из уравнений с одной стороны знака равенства x_i:
Пусть нам дан произвольный вектор , приближающий решение системы уравнений (например, нулевой).
Тогда, воткнув его в правую часть нашей системы, мы можем получить обновлённый вектор приближения решения .
Чтобы было понятнее, x1 получается из x0 следующим образом:
Повторив процесс k раз, решение будет приближено вектором
Давайте на всякий случай запишем рекурретную формулу:
При некоторых предположениях о коэффициентах системы (например, вполне очевидно, что диагональные элементы не должны быть нулевыми, т.к. мы на них делим), данная процедура сходится к истинному решению. Эта гимнастика известна в литературе под названием метода Якоби. Конечно же, существуют и другие методы численного решения систем линейных уравнений, причём значительно более мощные, например, метод сопряжённых градиентов, но, пожалуй, метод Якоби является одним из самых простых.
Пример 3 ещё раз, но уже с другой стороны
А теперь давайте ещё раз внимательно посмотрим на основной цикл из примера 3:
Я стартовал с какого-то начального вектора x, и тысячу раз его обновляю, причём процедура обновления подозрительно похожа на метод Якоби! Давайте выпишем эту систему уравнений в явном виде:
Потратьте немного времени, убедитесь, что каждая итерация в моём питоновском коде — это строго одно обновление метода Якоби для этой системы уравнений. Значения x[0], x[18] и x[31] у меня зафиксированы, соответственно, в набор переменных они не входят, поэтому они перенесены в правую часть.
Итого, все уравнения в нашей системе выглядят как — x[i-1] + 2 x[i] — x[i+1] = 0. Это выражение не что иное, как обычные конечные разности для второй производной. То есть, наша система уравнений нам просто-напросто предписывает, что вторая производная должна быть везде равна нулю (ну, кроме как в точке x[18]). Помните, я говорил, что вполне очевидно, что итерации должны сойтись к линейным рампам? Так именно поэтому, у линейной функции вторая производная нулевая.
А вы знаете, что мы с вами только что решили задачу Дирихле для уравнения Лапласа?
Кстати, внимательный читатель должен был бы заметить, что, строго говоря, у меня в коде системы линейных уравнений решаются не методом Якоби, но методом Гаусса-Зейделя, который является своебразной оптимизацией метода Якоби:
Пример 4: уравнение Пуассона
А давайте мы самую малость изменим третий пример: каждая ячейка помещается не просто в центр масс соседних ячеек, но в центр масс плюс некая (произвольная) константа:
В прошлом примере мы выяснили, что помещение в центр масс — это дискретизация оператора Лапласа (в нашем случае второй производной). То есть, теперь мы решаем систему уравнений, которая говорит, что наш сигнал должен иметь некую постоянную вторую производную. Вторая производная — это кривизна поверхности; таким образом, решением нашей системы должна стать кусочно-квадратичная функция. Проверим на дискретизации в 32 сэмпла:
При длине массива в 32 элемента наша система сходится к решению за пару сотен итераций. А что будет, если мы попробуем массив в 128 элементов? Тут всё гораздо печальнее, количество итераций нужно уже исчислять тысячами:
Метод Гаусса-Зейделя крайне прост в программировании, но малоприменим для больших систем уравнений. Можно попытаться его ускорить, применяя, например, многосеточные методы. На словах это может звучать громоздко, но идея крайне примитивная: если мы хотим решение с разрешением в тысячу элементов, то можно для начала решить с десятью элементами, получив грубую аппроксимацию, затем удвоить разрешение, решить ещё раз, и так далее, пока не достигнем нужного результата. На практике это выглядит следующим образом:
А можно не выпендриваться, и использовать настоящие солверы систем уравнений. Вот я решаю этот же пример, построив матрицу A и столбец b, затем решив матричное уравнение Ax=b:
А вот так выглядит результат работы этой программы, заметим, что решение получилось мгновенно:
Таким образом, действительно, наша функция кусочно-квадратичная (вторая производная равна константе). В первом примере мы задали нулевую вторую производную, в третьем ненулевую, но везде одинаковую. А что было во втором примере? Мы решили дискретное уравнение Пуассона, задав кривизну поверхности. Напоминаю, что произошло: мы посчитали кривизну входящей поверхности. Если мы решим задачу Пуассона, задав кривизну поверхности на выходе равной кривизне поверхности на входе (const=1), то ничего не изменится. Усиление характеристических черт лица происходит, когда мы просто увеличиваем кривизну (const=2.1). А если const Скрытый текст
Это результат по умолчанию, рыжий Ленин — это начальные данные, голубая кривая — это их эволюция, в бесконечности результат сойдётся в точку:
А вот результат с коэффицентом 2.:
Домашнее задание: почему во втором случае Ленин сначала превращается в Дзержинского, а затем снова сходится к Ленину же, но большего размера?
Заключение
Очень много задач обработки данных, в частности, геометрии, могут формулироваться как решение системы линейных уравнений. В данной статье я не рассказал, как строить эти системы, моей целью было лишь показать, что это возможно. Темой следующей статьи будет уже не «почему», но «как», и какие солверы потом использовать.
Кстати, а ведь в названии статьи присутствуют наименьшие квадраты. Увидели ли вы их в тексте? Если нет, то это абсолютно не страшно, это именно ответ на вопрос «как?». Oставайтесь на линии, в следующей статье я покажу, где именно они прячутся, и как их модифицировать, чтобы получить доступ к крайне мощному инструменту обработки данных. Например, в десяток строк кода можно получить вот такое: