Метод Дугласа-Пойкера для эффективного хранения метрик

30.01.24

Разработка - Математика и алгоритмы

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

Скачать файл

ВНИМАНИЕ: Файлы из Базы знаний - это исходный код разработки. Это примеры решения задач, шаблоны, заготовки, "строительные материалы" для учетной системы. Файлы ориентированы на специалистов 1С, которые могут разобраться в коде и оптимизировать программу для запуска в базе данных. Гарантии работоспособности нет. Возврата нет. Технической поддержки нет.

Наименование По подписке [?] Купить один файл
Метод Дугласа-Пойкера для эффективного хранения метрик:
.zip 44,46Kb
1
1 Скачать (1 SM) Купить за 1 850 руб.

Метод Дугласа-Пойкера

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

Строго прошу на википедию.

Давайте в картинках

Вот простой график, а допустимую погрешность возьмем 1.

 

 

На графике значение функции аппроксимируем прямой. Максимальная погрешность в столбце №5, и она больше 1. Ломаем линию.

 

 

Теперь в столбце №6

 

 

Теперь №7

 

 

Готово!

 

 

Итого: для того чтобы хранить данный график в памяти можно выкинуть 4 столбца из 9. Значения столбцов 2,3,4 можно восстановить по столбцам 1 и 5. Погрешность, кстати, получилась 0.

Большие данные

Я взял данные о занятом дисковом пространстве из системы мониторинга Zabbix. Zabbix каждую минуту записывает занятое место на разделе. В этом разделе мы храним резервные копии Postgres.

Один раз в 2 суток в раздел падает свежая полная резервная копия БД, а самая старшая копия из 4х удаляется. В течении дня на этот раздел падает архив журнала транзакций. Иногда это 5МБ/минута иногда больше, а ночью меньше. Все зависит от интенсивности работы с БД.

Вот такой график рисует Zabbix

 

 

На графике видны периоды полного резервного копирования и аномалия на 25.01.24 09:00. Во время "аномалии" выполнялась обновление не самой маленькой 1С:Бухгалтерии, изменений много вот и скачок архивированных данных.

На графике 10.000 значений. Мне удалось сократить это число до 144.

 

Реализация алгоритма

Данные записаны в CSV-файл без заголовка. В каждой строчке записана временная метка и значение занятого объема. Файл упорядочен по метке времени. Значения целочисленные. Всего ~10000 строк.

Сперва читаем файл, ничего сложного

ЧтениеТекста = новый ЧтениеТекста;
ЧтениеТекста.Открыть(Диалог.ПолноеИмяФайла, "windows-1251");
	
МассивДанных = новый Массив();

Пока Истина Цикл
	
	Стр = ЧтениеТекста.ПрочитатьСтроку();
	Если Стр = Неопределено Тогда
		Прервать;
	КонецЕсли;
	
	МассивПодстрок = СтроковыеФункцииКлиентСервер.РазложитьСтрокуВМассивПодстрок(Стр,",");	
	Д = новый Структура("ДатаВремя,Значение", неопределено, неопределено);
	
	МассивДанных.Добавить( СтруктураДанных(Число(МассивПодстрок[0]), Число(МассивПодстрок[1])) );
	
КонецЦикла;

Ну и сама процедура реализующая метод Дугласа-Пойкера

// Функция - Применить метод Дугласа-Пойкера https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm
//
// Параметры:
//  МассивДанных - Массив	- Массив структур данных с полями ДатаВремя,Значение. Поля структуры целочисленые значения. Упорядочено по ДатаВремя
//  Погрешность	 - Число	- Целое Положительное.
// 
// Возвращаемое значение:
//   - МассивДанных с удаленными "ненужными" столбцами.
//
&НаКлиенте
Функция ПрименитьМетодДугласаПойкера(МассивДанных, Погрешность)

	Результат = новый Массив();
	
	МассивОтрезков = новый Массив();
	МассивОтрезков.Добавить(новый Структура("Начало,Конец", 0, МассивДанных.Количество()));	
	
	ВставитьДанныеВРезультат(Результат, МассивДанных[0]);
	ВставитьДанныеВРезультат(Результат, МассивДанных[МассивДанных.Количество()-1]);
		
	Пока МассивОтрезков.Количество()>0 Цикл
		
		Отрезок = МассивОтрезков[МассивОтрезков.Количество()-1];
		МассивОтрезков.Удалить(МассивОтрезков.Количество()-1);
		
		ц=Отрезок.Начало+1;
		МаксДельта = Погрешность;
		МаксЦ = неопределено;
		Пока ц < Отрезок.Конец Цикл
			
			ПрогнозируемоеЗначение = МассивДанных[Отрезок.Начало].Значение + 
				(МассивДанных[ц].ДатаВремя - МассивДанных[Отрезок.Начало].ДатаВремя)*(МассивДанных[Отрезок.Конец-1].Значение - МассивДанных[Отрезок.Начало].Значение)/
				(МассивДанных[Отрезок.Конец-1].ДатаВремя - МассивДанных[Отрезок.Начало].ДатаВремя);
				
			Дельта = Макс(ПрогнозируемоеЗначение-МассивДанных[ц].Значение, МассивДанных[ц].Значение-ПрогнозируемоеЗначение);
			Если Дельта > МаксДельта Тогда
				
				МаксЦ = ц;
				МаксДельта = Дельта;
				
			КонецЕсли;
			
			ц = ц + 1;
			
		КонецЦикла;
		
		Если МаксЦ<>Неопределено Тогда
			
			МассивОтрезков.Добавить( новый Структура("Начало,Конец", Отрезок.Начало, МаксЦ+1) );
			МассивОтрезков.Добавить( новый Структура("Начало,Конец", МаксЦ, Отрезок.Конец) );
			
			ВставитьДанныеВРезультат(Результат, МассивДанных[МаксЦ]);
			
		КонецЕсли;
		
	КонецЦикла;
	
	Возврат Результат;
	
КонецФункции

Процедура ВставитьДанныеВРезультат(Результат, Данные)
	
	Для ц=0 По Результат.Количество()-1 Цикл
		
		Если Результат[ц].ДатаВремя = Данные.ДатаВремя Тогда
			Возврат;
		ИначеЕсли Результат[ц].ДатаВремя > Данные.ДатаВремя Тогда
			Прервать;
		КонецЕсли;
		
	КонецЦикла;
	
	Результат.Вставить(ц, Данные); 
	
КонецПроцедуры

 

Обработка

Приложенная обработка (Работает в режиме совместимости 8.2.19, сорри) и формирует две таблички.

Табличка «обработанные данные» содержит нашу таблицу с удаленными «лишними» столбцами.

Табличка «Сырые данные» содержит данные файла, столбец с приближенными значениями и столбец с «погрешность». Мне эти данные нужны были, чтобы отладить обработку.

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

 

 

Проверить можно, если скачать обработку. Исходные данные в архиве, слишком большой объем для формата статьи.

А вот так выглядит обработка с данными из моего примера «с картинками».

 

 

 

Вывод

Сырые данные можно эффективно сокращать.

Обработка практика программирования алгоритмы

См. также

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    6646    user1959478    50    

36

Математика и алгоритмы Разное Платформа 1С v8.3 Конфигурации 1cv8 Россия Абонемент ($m)

Расширение (+ обработка) представляют собою математический тренажер. Ваш ребенок сможет проверить свои знание на математические вычисление до 100.

2 стартмани

29.09.2023    2673    maksa2005    8    

25

Математика и алгоритмы Инструментарий разработчика Программист Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    10202    7    SpaceOfMyHead    18    

61

Математика и алгоритмы Программист Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Три задачи - три идеи - три решения. Мало кода, много смысла. Мини-статья.

03.04.2023    3940    RustIG    9    

25

Механизмы платформы 1С Математика и алгоритмы Программист Платформа 1С v8.3 Россия Бесплатно (free)

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

23.11.2022    3052    gzharkoj    14    

24

Математика и алгоритмы Программист Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    8876    7    kalyaka    11    

44
Комментарии
Подписаться на ответы Инфостарт бот Сортировка: Древо развёрнутое
Свернуть все
1. Diversus 2327 30.01.24 13:39 Сейчас в теме
Добрый день. Отличная теоретическая статья, спасибо.
Мне кажется в реализации, надо бы сделать "сжатие" не всех данных целиком, а пачками по N-штук (скажем, миллион записей).
Просто на реально больших данных в сотни миллиардов строк, может не хватить памяти.
Выход простой: читать файл пачками и каждую пачку сжимать отдельно друг от друга.
В этом случае размер увеличится незначительно, а потребление памяти сократится достаточно серьезно.
2. stopa85 39 30.01.24 13:44 Сейчас в теме
(1) да и это не проблема. Можно резать миллионами, можно днями.

У меня простейшая и не самая эффективная реализация.
3. ivanov660 4567 30.01.24 18:39 Сейчас в теме
Мне понравилось, отлично.
4. spectre1978 61 31.01.24 10:45 Сейчас в теме
хороший вариант для хранения незашумленных данных. Если же хранимая последующая метрика будет прыгать в достаточно широких пределах относительно предыдущей, причем в обе стороны - сильно сэкономить не получится.
5. MaxMiller 31.01.24 12:25 Сейчас в теме
Можно же учитывать и предел погрешности, чтобы выкидывать из расчета аномальные шумы. То есть резкие сверхвысокие или сверхнизкие показатели отсеивать. Но и тут найдутся свои ньюансы, пожалуй. Короче говоря представленное здесь решение очень годное, но не универсальное, вот и всё)
8. stopa85 39 31.01.24 13:01 Сейчас в теме
(4) А у Вас есть пример зашумленных данных? Могли бы поделиться? Мне интересно)

Как раз идея, что должно быть очень прыгать не должно. Но загрузку процессора упростить наверное не очень получится. Она ведь прыгает от 0 до 100 много раз в секунду.
6. CheBurator 2696 31.01.24 12:53 Сейчас в теме
"На графике значение функции аппроксимируем прямой. Максимальная погрешность в столбце №5, и она больше 1. Ломаем линию." - вызывает вопросы почему аппроксимация начальная =1, в то время как среднее значение 2,5555 и по идее должно аппроксимироваться прямой на 3 ну или на 2 ...
9. stopa85 39 31.01.24 13:03 Сейчас в теме
(6)
ызывает вопросы почему аппроксимация начальная =1

Просто соединяю начальную и конечные точки прямой. На моем графике и там и там единичка.
7. CheBurator 2696 31.01.24 12:53 Сейчас в теме
..не, можно и на нуле прямой сапросксимировать или на 1000...
10. stopa85 39 31.01.24 13:18 Сейчас в теме
(7) нет, нельзя.

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

Поэтому начальное приближение - отрезок соединяющий первую точку и последнюю.
11. CheBurator 2696 31.01.24 13:31 Сейчас в теме
12. artbear 1562 01.02.24 14:50 Сейчас в теме
(0) Интересный подход, спасибо!
Подумаю, как можно использовать на наших данных

мелкая опечатка "анамалия"
Оставьте свое сообщение