[жж][математика?] Прямая

метод наименьших квадратов? :-D

Не совсем. В МНК минимизуется КВАДРАТ отклонения, а не расстояние. А задача с минимальным средним расстоянием существенно сложнее.

линия тренда?

хотя херню сказал, она же не прямая

http://www.sinisha.ru/math/mnk.html

Есть и такой метод: метод наименьшей суммы модулей. По-англицки - LAD (least absolute deviation).

И, кстати, есть методы еще меньших порядков (например, квадратный корень из модуля) - они менее чувствительны к выбросам. Но выбросы можно и по какому-нибудь критерию трех сигм отсеять.

Метод наименьших квадратов с метрикой || ||=| |^\frac{12}

Расстояние от точки до прямой - это длина нормали, проведенной из точки до плоскости. Пусть точки у тебя имеют координаты xi,yi, а прямая имеет уравнение Ax+Bx+C=0 тебе надо минимизировать сумму функций di=|(A*xi+B*yi+С)/sqrt(A^2+B^2)|

http://ru.wikipedia.org/wiki/Алгоритм_Брезенхэма

Может и не то, но напомнило.

Ты читать умеешь? Или только ссылки кидать?

тенденция?

> Расстояние от точки до прямой - это длина нормали, проведенной из точки до плоскости.

До какой ещё плоскости?

ЕМНИП, то, что ищет ТС, называется «линейная аппроксимация методом наименьших квадратов». По ссылке можно построит график. Чё надо?

Сори, до прямой конечно же.

МНК минимизирует квадрат ошибки т.е. di=(yi-F(xi))^2 ТС в словесной формулировке требует минимизировать гораздо более сложную функцию di=|(A*xi+B*yi+С)/sqrt(A^2+B^2)|

я, конечно, всё понял, но так условия ставят только ... (с)Татьяныч

>Есть множество точек. Нужно построить прямую, чтобы среднее расстояние от каждой точки до прямой было минимально. Есть ли название у такой прямой?

линейная регрессия.

>Есть множество точек. Нужно построить прямую, чтобы среднее расстояние от каждой точки до прямой было минимально. Есть ли название у такой прямой?

но если тебе действительно наименьшее среднее расстояние надо, а не наименьшее среднеквадратичное, то тогда только численными методами поиск минимума.

Еще раз прочти, что ТС надо и перестань постить тупак.

Единственный вопрос ТС-а: «Есть ли название у такой прямой?»
Аппроксимация МНК - это общее название метода, что конкретно ты будешь минимизировать: квадрат отклонения или квадрат расстояния - не так важно. Так что сам ПНХ со своим

В МНК минимизуется КВАДРАТ отклонения, а не расстояние.

И не забудь включить flash.

Скажи мне только: ты идиот? Ты расстояние от КВАДРАТА расстояния отличить можешь?

ТС хочет минимизировать расстояние, а ты как упорный идиот лезешь со своим МНК.

Ох блин. Ты так убедительно называешь меня идиотом, что я почти поверил. МНК - это просто название. Он позволяет решить именно то, что требуется - аппроксимировать линейно набор точек, а расстояние считать как угодно. На, двоечник, читай.

Лучше говорить «метод наименьших отклонений», тогда можно сюда и МНК приплести, и метод наименьшего модуля, и т.д., и т.п.

Сделай милость, выпиши на листочке задачу, которую нужно оптимизировать и убедись, что никакими квадратами там не пахнет.

Изобретаешь терминологию? В википедии это называют «методы регрессионного анализа».

> убедись, что никакими квадратами там не пахнет
Серьёзно? Может лучше ты напишешь формулу вычисления расстояния между двумя точками - то, что нужно оптимизировать, - а потом подумаешь, нужно ли делать лишний раз sqrt?

Сделай милость

Сделай вдоль.

А лучше спроси у своего преподавателя математики, потом расскажешь. А то я аж что-то засомневался.

Хорошо, для дебилов выписываю решение:

Расстояниие от точки (x_i,y_i) до прямой Ax+BY+C

di = |A*x_i + B*x_i +C|/sqrt(A^2+B^2)

минимизуем сумму L = \sum_{i=1}^N d_i = 1/sqrt(A^2 + B^2) \sum |A*x_i + B*x_i +C|-> extr

ГДЕ ЗДЕСЬ МНК?

Понарегалось школьников, блин.

Расстояние от точки до прямой, конечно же, а не между двумя точками, моя ошибка.
Но это неважно. МНК ищет минималное отклонение. Из того, что у тебя получилось убираем модуль - это будет «отклонение» (так?). Переходим к МНК при возведении этого дела в квадрат. Теперь ждём ТС, чтобы понять, что ему было надо.

> Из того, что у тебя получилось убираем модуль - это будет «отклонение» (так?)

Нет, не так. Модель убирать нельзя, потому что расстояние — неотрицательная величина.

МНК ищет минималное отклонение.

МНК минимизует квадрат отклонения, как ясно из его названия. Для множества экспериментальных точек (x_i, y_i) процедура МНК ищет такую функцию f(x) из заданного класса (например, линейную f(x) = a*x+b), которая минимизует следующую форму

\sim_{i=1}^n (y_i - f(x_i))^2 -> extr

Как видно, это НЕ та же самая задача, что найти

\sim_{i=1}^n |(y_i - f(x_i)| -> extr

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

Черт его знает, как это по-русски. Я привык к англоязычным статьям. Там это называется LAD. Кстати, аппроксимацию лучше строить, минимизируя медиану отклонения, а не ее абсолютную или среднюю величину. Но это уже не аналитическая задача.

Это не совсем то.

LAD ищет минимум суммы отклонений от точки до прямой (в графической интерпритации параллельно оси Y).

По сути МНК упрощение LAD. LAD ищет минимум суммы ошибок, а МНК - минимум суммы квадратов ошибок

В задаче ТС требуется минимизировать сумму расстояний от точек (нормалей к искомой прямой).

Вот какую-то статью нагуглил: http://en.cnki.com.cn/Article_en/CJFDTOTAL-GKSX200404017.htm Правда, она, видимо, на китайском, да и просто так не скачаешь.

> Есть множество точек. Нужно построить прямую

Это единственная часть вопроса, которую я понял.

чтобы среднее расстояние от каждой точки до прямой было минимально.

Что за зверь такой - «среднее расстояние от каждой точки»?

Можно взять расстояния от каждой точки до прямой (опускаешь перпендикуляры, берёшь их длины и задаёшься вопросом одновременного минимума). Маловероятно, неэффективно, но возможно. Ещё можно брать среднее расстояние от всех точек до прямой (берёшь расстояния, находишь среднее (тут вопрос ещё какое именно среднее ты хочешь взять, кстати), ищешь его минимум). Это лучше предыдущего варианта, и тоже возможно.

Так что поясни, плз, чего ты хотел на самом деле, тогда можно будет дать ответ на твой вопрос. Пока думаешь советую почитать про линейную регрессию на википедии. Возможно, ты ищешь именно это.

Что за зверь такой - «среднее расстояние от каждой точки»?

вероятно сумма расстояний от точек до прямой деленная на кол-во точек. Расстояние от точки до прямой по определению длина перпендикуляра опущенного из точки на плоскость. Формулу приводили не один раз так что повторяться не буду. Задача решаема средствами функционального анализа. По сравнению с МНК задача на пару порядков более сложная, т.к. надо решить задачу нелинейной оптимизации.

> Задача решаема средствами школьной математики и информатики.

fix. Найти уравнение прямой, перпендикулярной данной, и проходящей через определенную точку просто; найти точку пересечения двух прямых - ещё проще. Пространство интересующих нас значений параметров можно оценить, проводя прямые через каждую пару точек и запоминая максимальные и минимальные значения. Ну а дальше полный перебор пространства с некоторым шагом даст столь нужное решение.

По сравнению с МНК задача на пару порядков более сложная,

Вычислительно разве что, и то лишь если для решения этой задачи применять полный перебор, а в МНК применять известные формулы :)

Мне одному кажется что ТС спрашивал не как строить а как называется?

Проблема в том, что МНК решается аналитически. А здесь - только итерации.

Эх, не пригодилась мне эта «прямая» )= Но всё равно спасибо всем

А разве в самом начале не сказали, что это - аппроксимирующая прямая, или линейная регрессия - кому как нравится?

Ты бы лучше к исходу 10-й страницы с этой фразой появился =)

>Ты бы лучше к исходу 10-й страницы с этой фразой появился =)

Да, я что-то отписал на форум, а сам попытался с другой стороны к проблеме подойти.

Найти длинну перпендикуляра сможет школьник 9-го класса, а вот задача минимизации нелинейных функций многих переменных - это уже функан.

Да даже минимизировать методом ньютона - тебе на каждом шаге надо гессиан считать. А я и говорил про вычислительную сложность

> Найти длинну перпендикуляра сможет школьник 9-го класса

О том и речь.

задача минимизации нелинейных функций многих переменных - это уже функан.

Оптимально, быстро - ты прав. Градиент считать или какую другую функцию на каждом шаге. Но полным перебором? Комп помощнее и - любой справится :)

А я и говорил про вычислительную сложность

Ну так вот, о чём и речь.

Аналитически - это в простейших случаях. АФАИР до кубических уравнений. Правда, обычно ими же и обходятся, только обзывают cspline-ами.

А вы, батенька, большой оригинал бутфорсом перебирать. Из-за таких как ты и происходит глобальное потепление. Есть же отлично работающие методы, которые гораздо быстро и с заданной точностью найдут решение.

> а вот задача минимизации нелинейных функций многих переменных - это уже функан.

Какой функан, обычного матанализа хватает. Проблема в этой задаче в том, что необходимые условия экстремума содержат разрывные функции x/|x| = sign(x) неизвестных параметров, поэтому не то что метод Ньютона, но даже градиентный спуск применять трудно. Проще всего, конечно, минимизовать безградиентными методами, вроде координатного спуска с золотым сечением, но он не быстро-то сходится

Блин, читал ЛОР, никого не трогал. А тут оказывается люди, знающие матан живут, а я все на математических форумах спрашивал... Спасибо, hired777!

>Блин, читал ЛОР, никого не трогал. А тут оказывается люди, знающие матан живут, а я все на математических форумах спрашивал... Спасибо, hired777!

лол.

Тебя, походу, и не такие откровения в будущем ожидают :)