algorithm - 执行此操作需要哪种算法？

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) 点，您可以找到 a 和 b，然后对照所有其他点检查生成的曲线。选择 y 观察次数最少的两个 x 值，并对所有 y 进行尝试。如果有偏差，即你的方程是

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

您需要查看三个 x 值。

如果您不知道频率，您可以尝试相同的技术，不幸的是解决方案可能不是唯一的，可能有多个 w 适合。

编辑 据我了解您的问题，每个 x 都有一个真正的 y 值和一堆不正确的值。你想找到真正的价值。最好的方法是通过少量点拟合曲线，并检查曲线是否适合其他集合中的某个 y 值。

如果不是所有的 x 值都具有有效的 y 值，那么同样的技术也适用，但是您需要查看更大的一组对、三元组或四元组（基本上每对、三元组或四元组具有不同的 y 值）

如果您的问题是其他问题，我怀疑是，请说明。

1. 定义正弦曲线。大多数人认为这意味着形式的功能a cos(w * x) + b sin(w * x) + c。如果您的意思不同，请指定它。

2 明确说明成功的样子。一个说 10 分而不是 100 分的例子会很好。

非常不清楚这与组合优化有什么关系。

Answer 2

您正在尝试进行曲线拟合，根据您想要拟合曲线的曲线类型（线性、多项式等），有几种算法。我不知道是否有针对正弦曲线的特定算法（傅立叶近似），但我的第一个想法是使用具有正弦多项式近似的多项式拟合算法。

我想知道您是否需要在另一个更大的程序中执行此操作，或者您是否正在尝试自己完成此任务。如果是这样，那么您最好使用统计软件包，我更喜欢的是R。它允许您导入数据并拟合曲线并在几行中绘制图形，您还可以在批处理模式下使用 R 从脚本甚至程序中调用它（这是我倾向于做的）。

Answer 3

正弦方程非常普遍，如果你取所有 y 的任何随机值，这些值可以拟合到正弦函数中，除非你给出条件，例如。频率<100 或所有参数都是整数，理论上无法区分噪声和数据，因此请首先从您的数据源/实验中找到此类条件。

Answer 4

正弦曲线是指一个函数增加 n 步，然后减少 n 步，等等？如果是这样，您可以将数据建模为通过上行链路和下行链路连接的节点序列。对于每个节点（y 的可能值），记录仅上升或下降链接的链的长度和结束值（每个节点将有多个链）。然后你扫描相同长度和相反方向的连续运行，以一些初始偏移量为模。