Участник:Bogdan/Проведение поверхностей наилучшего приближения

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
Строка 96: Строка 96:
== Методы, минимизирующие расстояния до объектов ==
== Методы, минимизирующие расстояния до объектов ==
 +
 +
== Сравнение ==
 +
 +
<tex>y = ax+b</tex>
 +
 +
=== MNK ===
 +
 +
<tex>\Psi(a,b) = \sum^{n}_{i=0}{(ax_i+b-y_i)^2}</tex>
 +
 +
<tex>\left\{\begin{matrix} (\sum^{n}_{i=0}{x_i})a + (n+1)b = \sum^{n}_{i=0}{y_i},\\ (\sum^{n}_{i=0}{x_i^2})a + (\sum^{n}_{i=0}{x_i})b = \sum^{n}_{i=0}{y_ix_i}\end{matrix}\right.</tex>
 +
 +
=== MNP ===
 +
 +
<tex>\Psi(a,b) = \sum^{n}_{i=0} \frac{(ax_i+b-y_i)^2}{a^2+1}</tex>
 +
 +
<tex>\left\{\begin{matrix} (\sum^{n}_{i=0}{x_i})a + (n+1)b = \sum^{n}_{i=0}{y_i},\\ (\sum^{n}_{i=0}{x_i^2-y_i^2})a + (\sum^{n}_{i=0}{x_i})b + (\sum^{n}_{i=0}{y_ix_i})a^2 + 2(\sum^{n}_{i=0}{y_i})ab - ab^2 - (\sum^{n}_{i=0}{x_i}) a^2b= \sum^{n}_{i=0}{y_ix_i}\end{matrix}\right.</tex>
== Заключение ==
== Заключение ==
== Список литературы ==
== Список литературы ==

Версия 08:11, 23 ноября 2008

Содержание

Введение

На практике мы часто сталкиваемся с задачей о сглаживании экспериментальных зависимостей.

Пусть зависимость между двумя переменными x и y выражается в виде таблицы, полученной опытным путем. Это могут быть результаты опыта или наблюдений, статистической обработки материала и т.п.

x x1 x2 ... xi ... xn
y y1 y2 ... yi ... yn

Требуется наилучшим образом сгладить экспериментальную зависисмость между переменными x и y, т.е. по возможности точно отразить общую тенденцию зависимости y от x, исключив при этом случайные отклонения, связанные с неизбежными погрешностями измерений или статистических наблюдений. Такую сглаженную зависимость стремятся представить в виде формулы y = f(x).

Формулы, служащие для аналитического представления опытных данных, получили название эмпирических формул.

Задача нахождения эмпирических формул разбивается на два этапа. На первом этапе нужно установить вид зависимости y = f(x), т.е. решить, является ли она линейной, квадратичной, логарифмической или какой-либо другой. Второй этап – определение неизвестных параметров этой функции.

Часто вид эмпирической зависимости известен, но числовые параметры неизвестны. Будем считать, что зависимость полиномиальная, а для определения параметров полинома рассмотрим следующие методы.

Методы восстановления регрессии, минимизирующие невязку ответов

Метод наименьших квадратов

Пусть функция y = f(x) задана таблицей своих значений: y_i = f(x_i), i = 0,1,...,n. Требуется найти многочлен фиксированной степени m, для которого среднеквадратичное отклонение (СКО) \sigma = \sqrt{\frac{1}{n + 1}\sum^{n}_{i=0}{(P_m(x_i)-y_i)^2}} минимально.

Так как многочлен P_m(x) = a_0+a_1x+a_2x^2+...+a_mx^m определяется своими коэффициентами, то фактически нужно подобрать набор кофициентов a_0,a_1,...,a_m, минимизирующий функцию \Psi(a_0,a_1,...,a_m) = \sum^{n}_{i=0}{(P_m(x_i)-y_i)^2} = \sum^{n}_{i=0}({\sum^{m}_{j=0}{a_jx_i^j}-y_i)^2}.

Используя необходимое условие экстремума, \frac{\partial\Psi}{\partial a_k} = 0, k = 0,1,...,m получаем так называемую нормальную систему метода наименьших квадратов: \sum^{m}_{j=0}{(\sum^{n}_{i=0}{x_i^{j+k}})a_j} = \sum^{n}_{i=0}{y_ix_i^k}, k = 0,1,...,m.

Полученная система есть система алгебраических уравнений относительно неизвестных a_0,a_1,...,a_m. Можно показать, что определитель этой системы отличен от нуля, то есть решение существует и единственно. Однако при высоких степенях m система является плохо обусловленной. Поэтому метод наименьших квадратов применяют для нахождения многочленов, степень которых не выше 5. Решение нормальной системы можно найти, например, методом Гаусса.

Запишем нормальную систему наименьших квадратов для двух простых случаев: m = 0 и m = 2. При m = 0 многочлен примет вид: P_0(x) = a_0. Для нахождения неизвестного коэффициента a_0 имеем уравнение: (n+1)a_0 = \sum^{n}_{i=0}{y_i}. Получаем, что коэффициент a_0 есть среднее арифметическое значений функции в заданных точках.

Если же используется многочлен второй степени P_2(x) = a_0+a_1x+a_2x^2, то нормальная система уравнений примет вид:

\left\{\begin{matrix} (n+1)a_0 + (\sum^{n}_{i=0}{x_i})a_1 + (\sum^{n}_{i=0}{x_i^2})a_2 = \sum^{n}_{i=0}{y_i},\\ (\sum^{n}_{i=0}{x_i})a_0 + (\sum^{n}_{i=0}{x_i^2})a_1 + (\sum^{n}_{i=0}{x_i^3})a_2 = \sum^{n}_{i=0}{y_ix_i},\\ (\sum^{n}_{i=0}{x_i^2})a_0 + (\sum^{n}_{i=0}{x_i^3})a_1 + (\sum^{n}_{i=0}{x_i^4})a_2 = \sum^{n}_{i=0}{y_ix_i^2} \end{matrix}\right.

Пример

Пусть функция задана таблицей своих значений:

x -3 -1 0 1 3
y -4 -0.8 1.6 2.3 1.5

Приблизим функцию многочленом 2-ой степени. Для этого вычислим коэффициенты нормальной системы уравнений:

\sum^{4}_{i=0}{x_i}=0 ,\sum^{4}_{i=0}{x_i^2}=20 ,\sum^{4}_{i=0}{x_i^3}=0 ,\sum^{4}_{i=0}{x_i^4}=164

\sum^{4}_{i=0}{y_i}=0.6 ,\sum^{4}_{i=0}{y_ix_i}=19.6 ,\sum^{4}_{i=0}{y_ix_i^2}=-21

Составим нормальную систему наименьших квадратов, которая имеет вид:

\left\{\begin{matrix} 5a_0 + 0a_1 + 20a_2 = 0.6,\\ 0a_0 + 20a_1 + 0a_2 = 19.6,\\ 20a_0 + 0a_1 + 164a_2 = -21 \end{matrix}\right.

Решение системы легко находится:a_0 = 1.234,a_1 = 0.98,a_2 = -0.278..

Таким образом, многочлен 2-ой степени найден: P_2(x) = 1.234 +0.98x -0.278x^2..

Нахождение оптимальной степени многочлена

Предположим, что функцию f можно с высокой точностью аппроксимировать многочленом P_m(x) некоторой степени m. Если эта степень заранее неизвестна, то возникает проблема выбора оптимальной степени аппроксимирующего многочлена в условиях, когда исходные данные y_i содержат случайные ошибки. Для решения этой задачи можно принять следующий алгоритм: для каждого m=0,1,2,... вычисляется величина \sigma_m = \sqrt{\frac{1}{n - m}\sum^{n}_{i=0}{(P_m(x_i)-y_i)^2}}. За оптимальное значение степени многочлена следует принять то значение m, начиная с которого величина \sigma_m стабилизируется или начинает возрастать.

Определение параметров эмпирической зависимости

Часто из физических соображений следует, что зависимость y = f(x) между величинами хорошо описывается моделью вида y = g(x,a_0,a_1,...,a_m), где вид зависимости g известен. Тогда применение критерия наименьших квадратов приводит к задаче определения искомых параметров a_0,a_1,...,a_m из условия минимума функции: \Psi(a_0,a_1,...,a_m) = \sum^{n}_{i=0}{(g(x_i,a_0,a_1,...,a_m)-y_i)^2}.

Если зависимость от параметров a_0,a_1,...,a_m нелинейна, то экстремум функции \Psi(a_0,a_1,...,a_m) = \sum^{n}_{i=0}{(g(x_i,a_0,a_1,...,a_m)-y_i)^2} ищут методами минимизации функций нескольких переменных.

Методы, минимизирующие расстояния до объектов

Сравнение

y = ax+b

MNK

\Psi(a,b) = \sum^{n}_{i=0}{(ax_i+b-y_i)^2}

\left\{\begin{matrix} (\sum^{n}_{i=0}{x_i})a + (n+1)b = \sum^{n}_{i=0}{y_i},\\ (\sum^{n}_{i=0}{x_i^2})a + (\sum^{n}_{i=0}{x_i})b = \sum^{n}_{i=0}{y_ix_i}\end{matrix}\right.

MNP

\Psi(a,b) = \sum^{n}_{i=0} \frac{(ax_i+b-y_i)^2}{a^2+1}

\left\{\begin{matrix} (\sum^{n}_{i=0}{x_i})a + (n+1)b = \sum^{n}_{i=0}{y_i},\\ (\sum^{n}_{i=0}{x_i^2-y_i^2})a + (\sum^{n}_{i=0}{x_i})b + (\sum^{n}_{i=0}{y_ix_i})a^2 + 2(\sum^{n}_{i=0}{y_i})ab - ab^2 - (\sum^{n}_{i=0}{x_i}) a^2b= \sum^{n}_{i=0}{y_ix_i}\end{matrix}\right.

Заключение

Список литературы

Источник — «http://recognition.su/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Bogdan/%D0%9F%D1%80%D0%BE%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BE%D0%B2%D0%B5%D1%80%D1%85%D0%BD%D0%BE%D1%81%D1%82%D0%B5%D0%B9_%D0%BD%D0%B0%D0%B8%D0%BB%D1%83%D1%87%D1%88%D0%B5%D0%B3%D0%BE_%D0%BF%D1%80%D0%B8%D0%B1%D0%BB%D0%B8%D0%B6%D0%B5%D0%BD%D0%B8%D1%8F»