Какой алгоритм потребуется для этого?

Question

У меня есть данные этой формы:

• для x = 1, y является одним из {1,4,6,7,9,18,16,19}
• для x = 2, y является одним из {1,5,7,4}
• для x = 3, y является одним из {2,6,4,8,2}
• ....
• для x = 100, y является одним из {2,7,89,4,5}

Только одно из значений в каждом наборе является правильным значением, остальное - случайный шум.

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

Answer 1

Это зависит от того, что вы подразумеваете под «точно», и что вы знаете заранее.Если вы знаете частоту w и что синусоида несмещена, у вас есть уравнение

a cos (w * x) + b sin (w * x)

с двумя (x,у) точки на разных значениях х вы можете найти а и б, а затем проверить сгенерированную кривую по всем остальным точкам.Выберите два значения x с наименьшим количеством y наблюдений и попробуйте это для всех y.Если есть смещение, т.е. ваше уравнение равно

a cos(w * x) + b sin(w * x) + c

Вам нужно взглянуть на три значения x.

Если вы не знаете частоту, вы можете попробовать ту же технику, к сожалению,решения могут быть не уникальными, может подходить более одного w.

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

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

Если ваша проблема в чем-то другом, иЯ подозреваю, что это, пожалуйста, укажите это.

1. Определите синусоиду.Большинство людей воспринимают это как функцию вида a cos(w * x) + b sin(w * x) + c.Если вы имеете в виду что-то другое, укажите это.

2 Укажите, как именно выглядит успех.Пример с скажем 10 баллов вместо 100 было бы неплохо.

Крайне непонятно, как это связано с комбинаторной оптимизацией.

Answer 2

Вы пытаетесь выполнить подгонку кривой , для которой существует несколько алгоритмов в зависимости от типа кривой, к которой вы хотите подогнать свою кривую (линейная, полиномиальная и т. Д.).Я понятия не имею, существует ли конкретный алгоритм для синусоидальных кривых (приближения Фурье), но моей первой идеей будет использование алгоритма полиномиальной аппроксимации с полиномиальной аппроксимацией синуса.

Интересно, нужно ли вамсделать это в ходе другой более крупной программы, или если вы пытаетесь выполнить эту задачу самостоятельно.Если это так, то вам лучше использовать статистический пакет, мой предпочтительный - R .Он позволяет вам импортировать ваши данные, подгонять кривые и рисовать графики всего за несколько линий, и вы также можете использовать R в пакетном режиме для вызова его из скрипта или даже из программы (это то, что я склонен делать).

Answer 3

Под синусоидой вы имеете в виду функцию, которая увеличивается на n шагов, затем уменьшается на n шагов и т. Д.? Если это так, вы можете смоделировать ваши данные как последовательность узлов, соединенных восходящими и нисходящими ссылками. Для каждого узла (возможное значение y) запишите длину и конечное значение цепочек только восходящих или нисходящих ссылок (будет несколько цепочек на узел). Затем вы сканируете последовательные прогоны одинаковой длины и противоположного направления по модулю некоторого начального смещения.

Answer 4

Синусоидальные уравнения являются настолько общими, что, если вы берете любое случайное значение всех y, эти значения могут быть включены в синусоидальную функцию, если вы не зададите условия, например Частота <100 или все параметры являются целыми числами, невозможно дифференцировать шум и данные теоретически, поэтому сначала постарайтесь найти такие условия в вашем источнике данных / эксперименте. </p>