2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Автоматический поиск линейного участка (пропорционального)
Сообщение01.08.2017, 15:52 


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

 Профиль  
                  
 
 Re: Автоматический поиск линейного участка (пропорционального)
Сообщение01.08.2017, 17:18 
Заслуженный участник


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

(Оффтоп)

myrakhovskyi.a в сообщении #1237405 писал(а):
НУЖНО НА ГРАФИКЕ (ДИАГРАММА РАСТЯЖЕНИЯ) АВТОМАТИЧЕСКИ НАЙТИ ЛИНЕЙНЫЙ УЧАСТОК (УЧАСТОК ПРОПОРЦИОНАЛЬНОСТИ)
Так, пожалуйста, не пишите. Это называется «капслокинг», это всё равно, что громко кричать. Даже в Правилах форума есть соответствующий пункт (I-1н, а также III-1).

 Профиль  
                  
 
 Re: Автоматический поиск линейного участка (пропорционального)
Сообщение01.08.2017, 17:30 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Автоматический поиск линейного участка (пропорционального)
Сообщение01.08.2017, 17:37 


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

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

 Профиль  
                  
 
 Re: Автоматический поиск линейного участка (пропорционального)
Сообщение01.08.2017, 18:12 
Админ форума
Аватара пользователя


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

 Профиль  
                  
 
 Re: Автоматический поиск линейного участка (пропорционального)
Сообщение01.08.2017, 21:10 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Автоматический поиск линейного участка (пропорционального)
Сообщение02.08.2017, 00:17 
Заслуженный участник


11/05/08
32166
myrakhovskyi.a в сообщении #1237405 писал(а):
Как должен быть найден данный участок - показал на картинках

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

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

 Профиль  
                  
 
 Re: Автоматический поиск линейного участка (пропорционального)
Сообщение02.08.2017, 15:45 


14/01/11
2916
Можно ещё считать корреляцию с какой-нибудь линейной функцией. Чем ближе к единице, тем участок ближе к линейному. Если требуется именно пропорциональность - просто косинусную метрику:
$$\frac{(\int_a^b xf(x)dx)^2}{\int_a^b( f(x))^2dx\int_a^b x^2dx}$$

 Профиль  
                  
 
 Re: Автоматический поиск линейного участка (пропорционального)
Сообщение03.08.2017, 10:14 


07/08/14
4231
Линейный участок - это $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)$, которые входят в расчет дисперсии.

 Профиль  
                  
 
 Re: Автоматический поиск линейного участка (пропорционального)
Сообщение03.08.2017, 12:13 


27/08/16
9426
myrakhovskyi.a в сообщении #1237405 писал(а):
Участок линейности может быть с каким-то отклонением (в пределах допуска).
Пожалуйста, сформулируйте определение допуска.

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

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

 Профиль  
                  
 
 Re: Автоматический поиск линейного участка (пропорционального)
Сообщение03.08.2017, 13:54 


01/08/17
4
realeugene в сообщении #1237975 писал(а):
myrakhovskyi.a в сообщении #1237405 писал(а):
Участок линейности может быть с каким-то отклонением (в пределах допуска).
Пожалуйста, сформулируйте определение допуска.

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

 Профиль  
                  
 
 Re: Автоматический поиск линейного участка (пропорционального)
Сообщение03.08.2017, 14:34 


27/08/16
9426
myrakhovskyi.a в сообщении #1237998 писал(а):
В стандартах испытаний на растяжения говорится о том, что такую процедуру, как поиск участка пропорциональности и дальше точки условного предела текучести - должен проводить специалист вручную. Такая процедура занимает много времени, и с современными приборами - более точно будет написать алгоритм поиска такого участка программно.

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

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

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

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

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

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

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

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

Успехов!

-- 03.08.2017, 15:03 --

myrakhovskyi.a в сообщении #1237998 писал(а):
С лучшей точность 1%
Учтите, что "точность 1%" не может быть критерием допуска гипотез в вашем алгоритме, так как вы сами не знаете правильное значение измеряемых величин.

 Профиль  
                  
 
 Re: Автоматический поиск линейного участка (пропорционального)
Сообщение03.08.2017, 15:14 
Заслуженный участник


20/08/14
11067
Россия, Москва
myrakhovskyi.a в сообщении #1237998 писал(а):
Можно ввести доверительный интервал, который бы говорил, что когда известен угол первого отрезка с осью Хов, то разница между углом первого участка и углом второго (следующего) может быть плюс /минус 1%.
Фактически это и есть условие на вторую производную, чтобы она была мала по модулю.
Кстати, допуска на разность соседних углов недостаточно, надо не забыть и ограничение на максимальную разницу всех внутренних углов в отрезке, чтобы не получить большой общий изгиб, который ну явно никак не линейный участок.

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

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

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

-- 03.08.2017, 15:18 --

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group