Аппроксимация несколькими прямыми

@psm · Регистрация: 18.10.2012

Студворк — интернет-сервис помощи студентам

Дан набор точек (координаты X и Y), нужно провести через них несколько прямых (например, 2) так, чтобы отклонение было минимальным. Каким образом можно это реализовать?

Зосима · 22.10.2012, 17:52

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

Вот, что я набросал:

Matlab M
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
clear;
clc;
 
A = load('дг1.txt');
 
x = A(:,1);
y = A(:,2);
 
dy1 = 5*diff(y); % разности между соседними отсчетами
dy2 = 5*diff( y(1:2:end) ); % разности через один отсчет
dy3 = 5*diff( y(1:3:end) ); % разность через два отсчета
 
x = 0:length(y)-1;
bx = x(1:2:end-1);
dx = x(1:3:end-3);
 
plot(x,y)
hold on
plot(x(2:end),dy1,'-r')
plot(bx,dy2,'-g')
plot(dx,dy3,'-c')
legend('y','dy1','dy2','dy3')
grid on

Результат на рисунке снизу.
Хоть эта процедура мало что дала, однако можно заметить положительный пик на голубой линии (dy3) на участке начального подъема функции и два наибольших отрицательных пика в окрестностях спада ф-ции.
Возможно из этого можно выудить нужные участки для апроксимации. Я пока не додумался как.

@sova_f · 22.10.2012, 19:40

Проблема в том, что целиком картинка - это и есть динамограмма. А так только кусочек, причем не показательный, т.к. там есть возвратный процесс. Ну увидели мы пики, а дальше что? Как программа должна распознать, что этот пик - начало обратного процесса, а вот этот - выход туда-то...?

@psm · 23.10.2012, 07:23 **[ТС]**

График (динамограмма, нагрузка от положения) и есть замкнутый, в идеале - параллелограмм. Просто на моем рисунке он был развернут (нагрузка от времени).

Можно попробовать ввести ограничение на величину пиков, получаемым при помощи diff, может удастся разделить на области.

Но все-таки надо как-то исходить из погрешности.

Зосима · 23.10.2012, 15:07

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

Верхняя область:

Нижняя область:

Общий вид:

И привожу код (громоздкий, 68 строк, поэтому прячу под спойлер):

Кликните здесь для просмотра всего текста

Matlab M
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
clear;
clc;
 
A = load('дг1.txt');
 
%x = A(:,1);
y = A(:,2);
x = (0:length(y)-1)';
ym = mean(y); % среднее значение
 
% *** Верхняя часть ***
% выделяем область выше средноего
y_up = y( y>ym );
x_up = x( find( y>ym ) );
n_up = length(y_up);
% обрезаем по 1/5 точек с концов
y_up1 = y_up(fix(n_up/5):fix(4*n_up/5));
x_up1 = x_up(fix(n_up/5):fix(4*n_up/5));
% линейно интерполируем 
ru = fit(x_up1, y_up1,'poly1');
% рассчитываем интерполированую прямую
yfu = ru(x_up);
% отображаем уровень
w_up = mean(yfu);
disp(['Верхний уровень : ',num2str(w_up)]);
% строим графики
figure
plot(x_up, y_up,'--g',x_up1, y_up1,'-r',...
    x_up, yfu,'-b',x_up,w_up*ones(1,length(x_up)),'-m')
legend('исходная область',...
    'обрезанная область',...
    'интерполяция',...
    'среднее интерполяции')
 
% *** Нижняя часть ***
% выделяем область ниже средноего
y_dn = y( y<ym );
x_dn = x( find( y<ym ) );
n_dn = length(y_dn);
% обрезаем 1/3 точек с начала
y_dn1 = y_dn(fix(n_dn/3):n_dn);
x_dn1 = x_dn(fix(n_dn/3):n_dn);
% линейно интерполируем 
rd = fit(x_dn1, y_dn1,'poly1');
% рассчитываем интерполированую прямую
yfd = rd(x_dn1);
% отображаем уровень
w_dn = mean(yfd);
disp(['Нижний уровень : ',num2str(w_dn)]);
% строим графики
figure
plot(x_dn, y_dn,'--g',x_dn1, y_dn1,'-r',...
    x_dn1, yfd,'-b', x_dn1,w_dn*ones(1,length(x_dn1)),'-m')
legend('исходная область',...
    'обрезанная область',...
    'интерполяция',...
    'среднее интерполяции')
% *** отображаем результаты ***
 
figure
plot(x,y,'--b',x,ym*ones(1,length(y)),'-c',...
    x_up,w_up*ones(1,length(x_up)),'-r',...
    x_dn1,w_dn*ones(1,length(x_dn1)),'-m')
legend('Исходный график',...
    'Общее среднее',...
    'Верхнее среднее',...
    'Нижнее среднее')

Конечно, это только две области и до идеала еще далеко, но уже кое что!

P.S.: А фронты можно попробовать выделить из окрестностей пересечения графика со средней линией! Но это уже в следующий раз

@psm · 24.10.2012, 06:59 **[ТС]**

Интересно. Другие прямые, наверно, можно найти из остатков.

Но придется каждый раз обрезать какую-то (определять "на глаз"?) часть точек, т.е. не не сам алгоритм определяет область для линейной аппроксимации.

@VTsaregorodtsev · 27.10.2012, 22:29

psm, Я бы исходную задачу решал методом расщепления. Итерации:
1) сработка алгоритма кластерного анализа,
2) внутри каждого кластера аппроксимация прямой,
3) новое распределение точек по кластерам (но уже не алгоритмом кластерного анализа - а по тому, какой прямой лучше аппроксимируется точка),
4) переход на п.2 для нового расчёта коэффициентов регрессии в каждом кластере.
Очевидно, что процесс сходящийся (пусть и к квазиоптимальному решению), т.к. и п.2, и п.3 минимизируют функции невязки (т.е. решение после выполнения пункта получается лучше, чем до его выполнения).

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

@psm · 29.10.2012, 07:21 **[ТС]**

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

@psm · 13.11.2012, 06:22 **[ТС]**

Есть еще идеи?

Новые блоги и статьи Все статьи Все блоги /
Установка ChatGPT (Codex) на Windows без использования Microsoft Store Fabien159 28.10.2026 Здравствуйте всем читающим! Опишу процесс установки ChatGPT (Codex) на Windows, если по каким-то причинам у вас не получается устанавить его через Microsoft Store. И так: 1. Скачиваем с. . .	Программное добавление префикса в нумерацию документов Maks 27.10.2026 Реализация из решения ниже выполнена в самописной конфигурации на БСП (помощь начинающему коллеге). Задача: Программно добавить префикс в нумерацию документов. Решение: В модуле объекта. . .	После закрытия оутлука продолжает висеть процесс в диспетчере задач Maks 27.10.2026 С недавнего времени в продакшене возникла проблема: при закрытии оутлука в диспетчере задач продолжал висеть процесс outlook. exe. Проблема возникла после установки MS Office 2021 LTSC на машинах, под. . .	Baragoz - DPS/HPS бот для WoW 3.3.5a, многоязычный AmbA 26.10.2026 Хотите ещё ботов? У меня есть один! А я пока отдохну от него. https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=12062&stc=1&d=1793007952 Инструкция внутри. https:/ / youtu. be/ VpfFZSUDGnQ. . .
Особенности gif сгенерированных в Си russiannick 21.10.2026 Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности. Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .	FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3) 8Observer8 18.10.2026 Содержание блога \| English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .	Локальный http сервер Argus19 17.10.2026 Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .	Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .

@psm 0 / 0 / 0 Регистрация: 18.10.2012 Сообщений: 39

	Аппроксимация несколькими прямыми 18.10.2012, 09:08. Показов 5987. Ответов 27 Метки нет (Все метки) Дан набор точек (координаты X и Y), нужно провести через них несколько прямых (например, 2) так, чтобы отклонение было минимальным. Каким образом можно это реализовать? 0

@sova_f 301 / 214 / 7 Регистрация: 16.10.2012 Сообщений: 485
	22.10.2012, 19:40
	Проблема в том, что целиком картинка - это и есть динамограмма. А так только кусочек, причем не показательный, т.к. там есть возвратный процесс. Ну увидели мы пики, а дальше что? Как программа должна распознать, что этот пик - начало обратного процесса, а вот этот - выход туда-то...? 0

@psm 0 / 0 / 0 Регистрация: 18.10.2012 Сообщений: 39
	23.10.2012, 07:23 [ТС]
	График (динамограмма, нагрузка от положения) и есть замкнутый, в идеале - параллелограмм. Просто на моем рисунке он был развернут (нагрузка от времени). Можно попробовать ввести ограничение на величину пиков, получаемым при помощи diff, может удастся разделить на области. Но все-таки надо как-то исходить из погрешности. 0

@psm 0 / 0 / 0 Регистрация: 18.10.2012 Сообщений: 39
	24.10.2012, 06:59 [ТС]
	Интересно. Другие прямые, наверно, можно найти из остатков. Но придется каждый раз обрезать какую-то (определять "на глаз"?) часть точек, т.е. не не сам алгоритм определяет область для линейной аппроксимации. 0

@VTsaregorodtsev 3147 / 1746 / 276 Регистрация: 19.02.2010 Сообщений: 4,557
	27.10.2012, 22:29
	psm, Я бы исходную задачу решал методом расщепления. Итерации: 1) сработка алгоритма кластерного анализа, 2) внутри каждого кластера аппроксимация прямой, 3) новое распределение точек по кластерам (но уже не алгоритмом кластерного анализа - а по тому, какой прямой лучше аппроксимируется точка), 4) переход на п.2 для нового расчёта коэффициентов регрессии в каждом кластере. Очевидно, что процесс сходящийся (пусть и к квазиоптимальному решению), т.к. и п.2, и п.3 минимизируют функции невязки (т.е. решение после выполнения пункта получается лучше, чем до его выполнения). Финальное решение может зависеть от результатов работы п.1. Например, метод динамических ядер при старте с разных начальных положений ядер кластеров может сходиться к разным решениям (к разным разбиениям на кластеры). Но не думаю, что у Вас столько много данных, чтобы даже несколько пробных запусков указанного алгоритма (и последующий выбор лучшего решения) требовали более 1-2 минут расчётов (если, конечно, программист умеет писать быстрые математические программы). 0

@psm 0 / 0 / 0 Регистрация: 18.10.2012 Сообщений: 39
	29.10.2012, 07:21 [ТС]
	А можно подробнее про алгоритм кластерного анализа?? Каким образом можно разбить данное множество точек на подмножества, которые будут аппроксимироваться прямыми? Как я понимаю, в методе динамических ядер разбиение на классы происходит, исходя из расстояния между ними. Но вряд ли это получится, потому что точки распределены неравномерно по определенной кривой, это не просто скопление. Миниатюры 0

@psm 0 / 0 / 0 Регистрация: 18.10.2012 Сообщений: 39
	13.11.2012, 06:22 [ТС]
	Есть еще идеи? 0