Выявления периодичности данных

[Warlornhor]

Доброго времени суток.

Кто-нибудь имел дело с задачей выявление периодичности (цикла) из ряда чисел, например простая последовательность: 5 4 3 0 3 4 5 0 5 4 3 0... Тут вопросов почти нет, находим массивы одинаковых чисел и если нашли значит цикл имеет место быть. Однако, в реальности может быть такая последовательность: 5 3.8 3.1 0.5 3.2 4.1 4.7 0.2 5.2 3.9 2.9 0 .... Что делать тут?

Какие могут быть числа не известно, известен диапазон, например [0, 1], период тоже не известен. Нужно определить наличие цикла. Если вдруг кто знает литературу на этот счет, то буду рад.

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

[ffldove]

Доброго времени суток.

Кто-нибудь имел дело с задачей выявление периодичности (цикла) из ряда чисел, например простая последовательность: 5 4 3 0 3 4 5 0 5 4 3 0... Тут вопросов почти нет, находим массивы одинаковых чисел и если нашли значит цикл имеет место быть. Однако, в реальности может быть такая последовательность: 5 3.8 3.1 0.5 3.2 4.1 4.7 0.2 5.2 3.9 2.9 0 .... Что делать тут?

Какие могут быть числа не известно, известен диапазон, например [0, 1], период тоже не известен. Нужно определить наличие цикла. Если вдруг кто знает литературу на этот счет, то буду рад.

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

Ну так если к примеру 5 раз подряд следующее число больше предыдущего, а потом 5 раз меньше и они в определенном диапазоне значит цикл. Или тот же вариант что и вы описали но с определенной погрешностью (в вашем втором варианте это 0.1). Или я не понял задачи?
ПС
Посмотрел внимательнее цифры, у вас разрыв между 4,7 и 0,2 специально или случайно? Тоесть может быть восхождение вверх, затем вниз, затем вверх, затем разрыв (случайное число) и снова вниз? Тогда можно просто выкидывать выбивающиеся числа (например если дельта больше скольких то) и если дальше идет опять цикл (период) значит предыдущее значение было случайным.
ПС ПС
Напоминает расчеты каких то приборов с определенной погрешностью, не угадал?

[Warlornhor]

Вариант может не сработать: 5 4 3 2 1 0 0.5 1 1.5 2 2.5 2.4 2.3 2.2 2.1 .... Это не цикл, точнее цикл, но приближение к цели имеет место быть, на таком шаге останавливаться нельзя.

Я искренне верю что какой-нибудь математик уже написал несколько статей на этот счет или может даже книг, а может даже где-то это выложил... Должен быть алгоритм, формулы...

[Warlornhor]

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

[ffldove]

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

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

[Warlornhor]

Значит Вы наверное слышали про очень пологие экстремумы, так называемые равнины, ошибка там уменьшается очень медленно и может быть такой случай, что дельта, вроде, не уменьшается ~10^(-5), но сразу после этой равнины идет обрыв, а путь к нему лежит по кругу, тот способ который Вы предложили будет работать в простейших случаях, но всякое бывает. А задача основная еще немного сложнее --- найти цикл для векторов данных.

[deadhead]

А задача основная еще немного сложнее --- найти цикл для векторов данных.

Может задача все таки найти экстремум? Почему вы не используйте алгоритмы с переменным шагом? или алгоритмы адаптированные к наличию "оврагов"?

[Warlornhor]

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

[deadhead]

Для периодичности - RS-анализ

А фиксированный шаг - очень критично? Может имеет смысл сперва аппроксимировать данные гладкой функцией?

[Portnov]

Периодичность обычно выявляют преобразованием Фурье (см. хотя бы в википедии). С вычислительной точки зрения - см. быстрое преобразование Фурье и библиотеку libfftw.