Python优化算法调整线越过尽可能多的点

Question

这是我的第一篇文章。对不起，如果它看起来像一堵文字墙。 希望有人能理解我的问题并提供可以执行此操作的示例模块或一些代码来尝试。 我正在处理时间序列 csv 数据，下面的示例行，列是 (datetime,O,H,L,C)

1999-10-26 21:00:00 68.81 68.83 68.07 68.19
1999-10-27 21:00:00 68.19 68.2 66.83 67.43
1999-10-28 21:00:00 67.43 68.06 66.91 68.06
1999-10-29 21:00:00 68.06 68.11 66.31 66.66
1999-01-11 22:00:00 66.66 67.15 66.09 66.63
1999-02-11 22:00:00 66.63 67.38 66.42 66.58
1999-03-11 22:00:00 66.58 67.73 66.42 67.48
1999-04-11 22:00:00 67.48 67.81 66.54 66.76
1999-05-11 22:00:00 66.76 68.2 66.54 67.87

这就是金融价格数据中的烛台，可以像这样直观地表示:

现在，我想要实现的是自动绘制一条线，该线会越过尽可能多的灯芯(烛台上的垂直线)，同时不会越过超过指定公差数量的烛体(绿色或红色区域) )

希望这是有道理的。 例子。越过尽可能多的灯芯(在本例中为蜡烛图下方)的线将从位置 4 开始，大约 66.4，然后向上倾斜直到位置 9，大约 66.55...

根据上图，我想象中的线条看起来像什么

如果我提供起始位置，是否有可以执行此操作的模块？ 基本上，类似于一条最佳拟合线，但实际上穿过所有点(一个点是一条垂直线，所以是 x 轴上的一个范围)，同时避免穿过红色/绿色区域，因此本质上是一条趋势线(不是曲线)

如果因为线是对角线而这太复杂了，您不妨提供一个水平线的示例来做同样的事情(只有 x 轴的一个值)。例如，如最后两条记录的数据 L(第 4 列)所示，值 66.54 也将起作用(它将穿过所有灯芯，并触及最后两个灯芯) 看到黄线穿过或触及所有低灯芯

在这种情况下，起始位置蜡烛的值(x 轴)无关紧要，也进行了调整

该线将从预定义的点开始(例如，我可能会选择图像中的位置 5，这是最低点)并继续直到获得最佳结果，因此它可以在任何地方停止。然后我计划使用基于这两点的角度值来延长这条线。

所以我正在寻找的输出实际上只是线的结束位置((x，y)如果对角线趋势线)或只是 x 轴值(水平线)。将根据算法优化选择起点 (A) 和终点，其中线应尽可能多地穿过蜡烛的垂直线(仅查看起点的右侧)但保持穿过蜡烛的计数蜡烛体区域低于可接受的阈值容差，直到找不到更好的解决方案。 (二)

我看过 Bresenham 的线算法和其他一些算法，但没有看到如何在 python 中对此类时间序列数据准确地实现它。我希望它像使用 fbprophet 一样简单

真实的 csv 文件重量高达 500MB，包含多达 600 万行 我更喜欢详尽的算法而不是遗传算法，后者每次都会产生不同的结果...

在此期间，我有一些关于如何尝试执行此操作的想法，但找不到任何带有示例的合适模块来加速该过程

如果这仍然不清楚......我想最大化线穿过垂直线的次数，如蜡烛中间所示(图片上的白线)，同时保持允许的次数也可以穿过仅限于所选值的绿色/红色区域。

我使用 pyqtgraph 进行可视化 制作情节的示例代码: http://www.pyqtgraph.org/downloads/0.10.0/pyqtgraph-0.10.0-deb/pyqtgraph-0.10.0/examples/customGraphicsItem.py

Answer 1

如果我没理解错的话，您想要最大化斜线与一组等距垂直线段的交点数量(允许/不允许交叉烛台使问题有点模糊)。

而且如果我也没有理解错的话，一次可以有百万段。

如果直线的斜率是固定的，设 m，您可以剪切空间，使直线变为水平，端点垂直平移 m.i 对于段 i(假设单位间距)。

然后，通过增加纵坐标对端点进行排序，您可以在平移直线时轻松获得水平重叠线段的数量。这需要 N Log N 操作进行排序，并使用 N 操作来构造计数函数。

现在对于任何斜坡，您可以获得最大数量的交叉点。如果这个函数足够平滑，你可以通过黄金比例或类似的方法搜索这个函数的最大值。