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

30.01.24

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

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

Скачать исходный код

Наименование Файл Версия Размер
Метод Дугласа-Пойкера для эффективного хранения метрик:
.zip 44,46Kb
1
.zip 44,46Kb 1 Скачать

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

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

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

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

Вот простой график, а допустимую погрешность возьмем 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    4679    user1959478    50    

34

Регулярные выражения на 1С

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

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

1 стартмани

09.06.2023    7675    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

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

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

1 стартмани

21.03.2022    7949    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

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

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4559    fishca    13    

36

Интересная задача на Yandex cup 2021

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

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8954    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

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

31.08.2021    7984    dusha0020    8    

70

Алгоритмы распределения сумм (наивная методика, Алгоритм Кэхэна)

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

Многим встречалась задача распределения суммы и вытекающая из нее проблема округления, каждый решал ее по-своему, все ли способы вам известны?

08.07.2021    8489    con-men    33    

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

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

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

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

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

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

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