Автоматический поиск линейного участка (пропорционального)

[myrakhovskyi.a]

Добрый день. Помогите решить такую задачу: НУЖНО НА ГРАФИКЕ (ДИАГРАММА РАСТЯЖЕНИЯ) АВТОМАТИЧЕСКИ НАЙТИ ЛИНЕЙНЫЙ УЧАСТОК (УЧАСТОК ПРОПОРЦИОНАЛЬНОСТИ). Этот участок в начале кривой. Сами кривые имеют разный вид - но характер кривых в принципе похож.
Варианты кривых в папке и массивы данных тоже прикреплены. https://drive.google.com/open?id=0B5XrMKnxpxOUdXl0T0p1Y1QtTGM
Участок линейности может быть с каким-то отклонением (в пределах допуска).
Пробовал методом наименьших квадратов, но или очень маленький участок находит, или конец участка берется за перегибом.
Как должен быть найден данный участок - показал на картинках.
Спасибо за помощь!

[svv]

Участок приблизительно линейный, если вторая производная мала по модулю.
Вторую производную можно найти по формуле $f''_n=\frac{f_{n-1}-2f_n+f_{n+1}}{h^2}$, где $h$ — шаг независимой переменной, но
1) эта формула годится только для сетки с постоянным шагом;
2) она очень чувствительна к шумам.
С тем и другим можно успешно бороться.

(Оффтоп)

myrakhovskyi.a в сообщении #1237405 писал(а):

НУЖНО НА ГРАФИКЕ (ДИАГРАММА РАСТЯЖЕНИЯ) АВТОМАТИЧЕСКИ НАЙТИ ЛИНЕЙНЫЙ УЧАСТОК (УЧАСТОК ПРОПОРЦИОНАЛЬНОСТИ)

Так, пожалуйста, не пишите. Это называется «капслокинг», это всё равно, что громко кричать. Даже в Правилах форума есть соответствующий пункт (I-1н, а также III-1).

[Dmitriy40]

А это точно имеет отношение именно к математике? По мне вопрос скорее алгоритмический и в тему компьютерных вычислений.
Я бы попробовал сделать примерно так: зададим отрезок $[a; b]$ на оси $X$, изначально включающий все точки. Для заданной величины погрешности $\Delta$ определим четырёхугольник $\{(a; y(a)+\Delta); (a; y(a)-\Delta); (b; y(b)-\Delta); (b; y(b)+\Delta)\}$ ("натянем резинки на точки с максимальной погрешностью"). Любые линейные апроксимации с заданной погрешностью пройдут гарантированно внутри этого четырёхугольника. После чего проверим что все остальные внутренние точки отрезка точно попадают внутрь четырёхугольника. Если попали - всё, линейный участок найден. Если нет, то сдвигаем тот конец отрезка, к которому ближе лежит непопадающая точка (это гарантирует нахождение наибольшего линейного участка если их несколько) на одну точку внутрь отрезка и повторяем вычисление четырёхугольника и проверку попадания всех точек в цикле. Цикл гарантированно завершится или нахождением линейного участка, или на соседних двух точках, через которые прямую можно провести всегда - это будет указанием на отсутствие линейного участка с заданной погрешностью.
Время работы алгоритма квадратично по количеству точек, это минус.
После нахождения линейного участка если потребуется можно и апроксимацию вычислить, методом наименьших квадратов или ещё как.
PS. На самом деле найден будет видимо не именно линейный участок, а участок, который можно апроксимировать линейной функцией с погрешностью не более заданной. Не уверен что это совпадает с исходной задачей.

[myrakhovskyi.a]

Dmitriy40 в сообщении #1237455 писал(а):

А это точно имеет отношение именно к математике? По мне вопрос скорее алгоритмический и в тему компьютерных вычислений.
Я бы попробовал сделать примерно так: зададим отрезок $[a; b]$ на оси $X$, изначально включающий все точки. Для заданной величины погрешности $\Delta$ определим четырёхугольник $\{(a; y(a)+\Delta); (a; y(a)-\Delta); (b; y(b)-\Delta); (b; y(b)+\Delta)\}$ ("натянем резинки на точки с максимальной погрешностью"). Любые линейные апроксимации с заданной погрешностью пройдут гарантированно внутри этого четырёхугольника. После чего проверим что все остальные внутренние точки отрезка точно попадают внутрь четырёхугольника. Если попали - всё, линейный участок найден. Если нет, то сдвигаем тот конец отрезка, к которому ближе лежит непопадающая точка (это гарантирует нахождение наибольшего линейного участка если их несколько) на одну точку внутрь отрезка и повторяем вычисление четырёхугольника и проверку попадания всех точек в цикле. Цикл гарантированно завершится или нахождением линейного участка, или на соседних двух точках, через которые прямую можно провести всегда - это будет указанием на отсутствие линейного участка с заданной погрешностью.
Время работы алгоритма квадратично по количеству точек, это минус.
После нахождения линейного участка если потребуется можно и апроксимацию вычислить, методом наименьших квадратов или ещё как.
PS. На самом деле найден будет видимо не именно линейный участок, а участок, который можно апроксимировать линейной функцией с погрешностью не более заданной. Не уверен что это совпадает с исходной задачей.

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

[Toucan]

myrakhovskyi.a, замечания за
- капслок;
- отсутствие собственных попыток решения задачи;
- избыточное цитирование.

[electric_retard]

myrakhovskyi.a
Не пробовали ISO\ГОСТ почитать, согласно которому проводились измерения?
Вот например решение вашей задачи для композитов, пункт 3.9.

[ewert]

myrakhovskyi.a в сообщении #1237405 писал(а):

Как должен быть найден данный участок - показал на картинках

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

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

[Sender]

Можно ещё считать корреляцию с какой-нибудь линейной функцией. Чем ближе к единице, тем участок ближе к линейному. Если требуется именно пропорциональность - просто косинусную метрику:

$$\frac{(\int_a^b xf(x)dx)^2}{\int_a^b( f(x))^2dx\int_a^b x^2dx}$$

[upgrade]

Линейный участок - это $y=kx$ для всех точек участка
Отклонение от среднего для линии будет тоже с множителем $k$, линейные участки можно так найти:
$\frac{y}{x}-\sqrt{\frac{D(y)}{D(x)}}=0$ или $\frac{\frac{y}{x}}{\sqrt{\frac{D(y)}{D(x)}}}=1$ для всех точек линейного участка с ненулевыми координатами точек $(x,y)$, которые входят в расчет дисперсии.

[realeugene]

myrakhovskyi.a в сообщении #1237405 писал(а):

Участок линейности может быть с каким-то отклонением (в пределах допуска).

Пожалуйста, сформулируйте определение допуска.

Задача, конечно, не вполне математическая, а техническая, так как относится к обработке реальных измерений с неизвестно какого рода погрешностями, и её решение зависит от жесткости требований, которые предъявляются к решению. Вам предварительно нужно понять ответы на следующие вопросы:
1. Как именно вашему алгоритму допустимо ошибиться? Чем будут определяться ошибки вашего алгоритма
2. Что вам делать, если вашему аппарату подсунут какой-нибудь эластомер без линейного участка?
3. Как в конце концов вам протестировать, что ваш алгоритм работает приемлемо во всех интересных вам случаях?

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

[myrakhovskyi.a]

realeugene в сообщении #1237975 писал(а):

myrakhovskyi.a в сообщении #1237405 писал(а):

Участок линейности может быть с каким-то отклонением (в пределах допуска).

Пожалуйста, сформулируйте определение допуска.

Вы правы.
Конечно, когда диаграмма растяжения имеет прямой участок который явно выражен (это стали и металлы), то найти его не представляет большой трудности. Когда такого участка нет, то можно найти самый минимальный линейный участок.
В стандартах испытаний на растяжения говорится о том, что такую процедуру, как поиск участка пропорциональности и дальше точки условного предела текучести - должен проводить специалист вручную. Такая процедура занимает много времени, и с современными приборами - более точно будет написать алгоритм поиска такого участка программно.
Дело в том, что при построении графика (слишком много данных) т.к. эти данный считываются с большой скоростью. Из-за того, что много данных то при максимальном приближении (просмотре) графика видно - то он рисуется не сплошной прямой - плавной линией, а ступеньками. При апроксимации графика- ступеньки более-менее выравниваются, но все равно график рисуется не одной плавной линией.
В данный момент попробовали сделать поиск линейного участка МНК - но так как график - ступеньками, то программно находится просто одна ступенька которая считается линейным участком. А нужно чтоб расстояние между началом линии и ее концом было как можно больше.
Теперь что касается допуска: например программа нашла линейный участок (одну ступеньку на графике) и промеряла угол между линиейным участком и осью Хов, а потом остановилась, потому как следующая ступенька имеет уже немного другой угол к оси Хов. Можно ввести доверительный интервал, который бы говорил, что когда известен угол первого отрезка с осью Хов, то разница между углом первого участка и углом второго (следующего) может быть плюс /минус 1%.
С лучшей точность 1% оператор с помощью карандаша и линейки на графике в ручную не нарисует этот участок.

[realeugene]

myrakhovskyi.a в сообщении #1237998 писал(а):

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

Понимаете, в чём тут проблема? Оператор - он человек, как правило, с высшим инженерным образованием. Он, во-первых, много лет учился физике-технике-математике, и, во-вторых, он долго приобретал собственный личный опыт эксперта практически. Но если вы его попросите написать критерии решения этой задачи, то наверняка он не сможет их описать непротиворечиво и при этом ничего не забыть. Так уж устроена человеческая интуиция. С другой стороны, компьютер - это тупая железяка, которая сама учиться не умеет (уже есть прогресс в этой области, но всё равно требуется опытный специалист в машинном обучении). Вам придётся самому описать алгоритм решения вашей задачи во всех деталях, используя в качестве эталона опыт эксперта. Не думайте, что это легко и просто.

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

1. Предварительная обработка/генерация признаков. Это может быть фильтрация, прореживание, сглаживание ступенек и так далее. В результате вам нужно получить минимальный набор данных, приемлемый как для дальнейшей компьютерной обработки, так и для анализа человеком, не потеряв при этом существенную для вас информацию. Например, каждую горизонтальную ступеньку, возникающую из-за каких-то ошибок в реализации вашего железа, можно заменить одной точкой. Можно, также, потом этот сглаженный график продифференцировать. Возможность понимания ваших предобработанных данных человеком в вашем случае тоже важна, так как вы сами должны понять, в чём именно ваши компьютерные эвристики отличаются от мнения эксперта.

2. Генерация гипотез. У вас это просто. Вам, в результате, нужно найти наилучший интервал, на котором график линеен в некотором смысле. Гипотеза - это у вас просто интервал, с заданными началом и концом. Переберите в двойном цикле все возможные интервалы.

3. Отсечение гипотез. Для каждой гипотезы в цикле вы должны понимать, приемлема ваша гипотеза как "линейный участок", или нет, безотносительно к тому, что может существовать линейный участок лучше. Неприемлемые гипотезы выкидываете без сожаления, приемлемые обрабатываете дальше. Критерий написания эвристик для этого этапа: любая прошедшая через него гипотеза в принципе может быть выдана как решение вашей задачи. Это одна функция, получающая на вход предобработанные данные с первого этапа и интервал, и возвращающая ответ "да" или "нет".

4. Выбор наилучшей гипотезы. Нужно сравнить все гипотезы, полученные на шаге 3, и выбрать из них одну наилучшую по какому-то критерию. Этот выбор должен быть комплексным и учитывать такие факторы, как длина гипотезы, расстояние от начала, разброс точек на интервале и так далее. Попытайтесь написать одну функцию сравнения, выбирающую из двух поданных на вход гипотез лучшую. Функция сравнения не должна быть идеально точной, достаточно, чтобы лучшая по мнению эксперта гипотеза побеждала в сравнении все остальные. Имея такую функцию вы, просто, по мере генерации гипотез, их попарно сравниваете и оставляете себе лучшую.

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

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

Успехов!

-- 03.08.2017, 15:03 --

myrakhovskyi.a в сообщении #1237998 писал(а):

С лучшей точность 1%

Учтите, что "точность 1%" не может быть критерием допуска гипотез в вашем алгоритме, так как вы сами не знаете правильное значение измеряемых величин.

[Dmitriy40]

myrakhovskyi.a в сообщении #1237998 писал(а):

Можно ввести доверительный интервал, который бы говорил, что когда известен угол первого отрезка с осью Хов, то разница между углом первого участка и углом второго (следующего) может быть плюс /минус 1%.

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

Избавиться от ступенек перед МНК несложно: спрямите график наклонными линиями, между ступеньками (или их серединами), примерно как и собрались делать для поиска углов. И натравливайте МНК уже на такие почти совпадающие прямые (в смысле отрезки с почти одинаковой ориентацией). Фактически это вариант классического усреднения. Усредняете, потом МНК для получения прямой.
Или вместо самой функции работать с её нарастающей суммой (фактически площадью под кривой). Апроксимировать её (вероятно параболой), а уж взять производную и получить апроксимацию исходной функции тривиально. Это автоматом усреднит и ступеньки и шумы.

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

PS. Вообще же мне кажется у Вас некоторая путаница с постановкой задачи. Одно дело определить границы линейного участка (т.е. участка, который можно апроксимировать прямой с погрешностью не более заданной), другое дело найти коэффициенты этой вот прямой (что и делается например через МНК). Плюс так и непонятно, есть ли до начала обработки весь массив данных или данные поступают потоком. Плюс насколько велики шумы или эти ваши ступеньки (их же проще сначала пофильтровать с заданной АЧХ, а уж потом анализировать данные).

-- 03.08.2017, 15:18 --

Согласен с realeugene, перед погружением в частности (МНК, углы, величины допусков и прочее) надо детальнее определиться с постановкой задачи и общими методами решения. Я тоже слишком полез вглубь.