在时间序列分析中,断点检测(breakout detection)是一个很基本的问题。
通过捕捉时序数据中的断点(breakout),来发现时序数据所表示的系统在过去是否发生了某种事件(event),进而为系统诊断提供必要的数据支持。
为了实现对时序断点的检测,我们首先需要对时序的整体时序做拟合。
这里我们通过一条直线来拟合一段时序,如果时序的趋势发生了变化,则用多条直线来拟合整条时序数据。
如下是对一条波动规律明显的时序做拟合之后的结果。
每个红色线条的转折点,就是我们找到的断点。
以上数据是我们在实验环境下,为了检测算法效果而人工构造的一条时序。
那么,该算法在实际情况下表现如何?
一下是一条实际的股票价格时序数据。我们通过该算法进行断点检测,并将断点红红色线条连起来的效果:
更进一步,将拟合之后的线段图分段画出如下:
其中黑色表示原始时序,红色表示划分得到的断点,蓝线表示断点之间子序列的线性拟合结果。
算法介绍:
算法所使用的关键技术:
1. 单变量线性回归,用来拟合某一段时序
2. 动态规划算法, 用来全局最大化断点检测效果。
算法核心代码:
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include "lsp.h" static double loss(double * s, int n){ int i; double t; double g0 = 0.0, g1 = 0.0; double h00 = 0.0, h01 = 0.0, h10 = 0.0, h11 = 0.0; double hv00 = 0.0, hv01 = 0.0, hv10 = 0.0, hv11 = 0.0; double l0, l1; // grad and hessian matrix for (i = 0; i < n; i++){ t = s[i]; g0 += t; g1 += t * (1.0 + i); h00 += 1.0; h01 += 1.0 + i; h11 += (1.0 + i) * (1.0 + i); } h10 = h01; // inverse of hessian t = h00 * h11 - h01 * h10; hv00 = h11 / t; hv01 = hv10 = -h01 / t; hv11 = h00 /t; // the theta l0 = hv00 * g0 + hv01 * g1; l1 = hv10 * g0 + hv11 * g1; // sqare loss t = 0.0; for (i = 0; i < n; i++){ t += (l0 + l1 * (i + 1) - s[i]) * (l0 + l1 * (i + 1) - s[i]); } return t; } int * lsp(double * ts, int n, int min_size, double beta, int *ol){ if (!ts || min_size < 2 || n < 2 * min_size || !ol){ return NULL; } // prev breakout point int * prev = (int*)malloc(sizeof(int) * (n + 1)); memset(prev, 0, sizeof(int) * (n + 1)); // number of breakout point int * num = (int*)malloc(sizeof(int) * (n + 1)); memset(num, 0, sizeof(int) * (n + 1)); // F scores double * F = (double*)malloc(sizeof(double) * (n + 1)); memset(F, 0, sizeof(double) * (n + 1)); // loss double * lossv = (double*)malloc(sizeof(double) * (n + 1)); memset(lossv, 0, sizeof(double) * (n + 1)); for (int s = 2 * min_size; s < n + 1; ++s){ for (int t = min_size; t < s - min_size + 1; ++t){ //double ls = loss(ts + prev[t], t - prev[t]); double ls = lossv[t]; double rs = loss(ts + t, s - t); double as = loss(ts + prev[t], s - prev[t]); double score = (as - ls - rs) * (t - prev[t]) * (s - t) / \ ((s - prev[t]) * (s - prev[t])) - num[t] * beta; score += F[t]; if (score > F[s]){ num[s] = num[t] + 1; F[s] = score; prev[s] = t; lossv[s] = rs; } } } int k = num[n]; *ol = k; int * re = (int*)malloc(sizeof(int) * k); memset(re, 0, sizeof(int) * k); int i = n; while(i > 0){ if (prev[i]) re[--k] = prev[i]; i = prev[i]; } free(prev); prev = NULL; free(num); num = NULL; free(F); F = NULL; free(lossv); lossv = NULL; return re; }
算法复杂度上限为:O(n * n * n)。
相关推荐
BreakoutDetection(Breakout Detection)是 Twitter 的开源的,可以便捷和快速检测 Breakout 的 R 包。BreakoutDetection 通过健壮的 E-Statistics 来实现。BreakoutDetection 包可以在广泛的各种场景使用,比如,...
在《Breakout》中,DDPG可以学习到平滑的动作序列,以连续控制球的轨迹。 4. **演员-评论家(Actor-Critic)算法**: 这类算法结合了策略梯度和值函数的优化,其中“演员”负责更新策略,而“评论家”则提供策略质量...
《基于Transformer的序列建模强化学习算法开发》 在当今的AI领域,深度学习和强化学习是两大核心技术,而Transformer模型则是近年来在自然语言处理(NLP)领域中备受瞩目的创新。本项目旨在深入理解并复现基于...
【标题】"breakout-game_前端小游戏_breakout_" 指的是一款利用原生JavaScript编写的打砖块游戏。在Web开发领域,前端小游戏是一种常见的练习项目,它可以帮助开发者提升JavaScript编程技能,同时也能增强对HTML、...
《MATLAB开发:Breakout游戏实现详解》 MATLAB,作为一种强大的数学计算和数据分析软件,也被广泛用于图形用户界面(GUI)和游戏开发。本文将深入探讨如何利用MATLAB进行"Breakout"游戏的开发,这是一款类似Pong的...
通过 Breakout RSI 指标,交易者可以自动化识别可能的市场突破,节省手动分析的时间,同时减少因人为判断失误导致的交易风险。然而,任何指标都不能保证100%的交易成功,因此,结合其他分析方法,如趋势线、支撑阻力...
《MetaTrader 4 EA——BreakOut15智能交易系统详解》 在外汇交易领域,MetaTrader 4(MT4)平台因其强大的图表分析工具、自动化交易功能和丰富的技术指标而备受推崇。其中,智能交易系统(Expert Advisor,简称EA)...
《Breakout Version下载资源》是源自唐胜555的一款基于smbx平台的地图资源,主要为玩家提供了独特的游戏体验。smbx是一款开源的、免费的超级马里奥兄弟游戏制作工具,允许用户创建自己的游戏关卡和世界,极大地扩展...
【标题解析】:“EURUSD breakout - MetaTrader 5 EA.zip” 这个标题表明我们讨论的是一个基于MetaTrader 5(MT5)平台的自动交易系统,也被称为专家顾问(Expert Advisor,简称EA)。"EURUSD breakout"部分指的是该...
"打砖块Breakout"是一款经典的街机游戏,它的核心玩法是通过控制一块挡板反射一个小球,击碎屏幕上排列的砖块。在这个基于OpenGL编写的版本中,我们可以深入探讨几个重要的IT知识点。 1. **OpenGL**: OpenGL是一个...
《PB中的Breakout游戏开发详解》 在信息技术领域,编程游戏是学习编程和软件开发的绝佳途径。"Breakout",又称打砖块,是一款经典的街机游戏,因其简单而富有挑战性的玩法深受程序员喜爱。在PowerBuilder(简称PB)...
【标题】"Breakout box2d学习代码"是基于Box2D物理引擎和Cocos2D 2.1框架创建的一款经典打砖块游戏(Breakout)的学习资源。这个项目旨在帮助初学者理解和掌握如何利用Box2D进行游戏开发,以及在Cocos2D 2.1环境下...
【描述】描述中的"强化学习-Breakout-v0.zip"可能是一个教学材料或课程作业,包含了学生或研究人员在探索和应用强化学习算法到Breakout游戏上的工作。"Breakout-v0"是OpenAI Gym库中的一个版本,它为AI提供了与游戏...
"breakout2-1.0-linux" 是一个基于Linux平台的游戏程序,由流行的跨平台应用程序框架QT构建。这个压缩包包含的是游戏的可执行文件,用户可以直接在Linux系统上运行,无需进行安装步骤,简化了游戏的使用流程。游戏...
《使用Cocos2d和Box2D创建Breakout游戏》 Breakout游戏,又名打砖块,是一款经典的街机游戏,玩家通过控制一块挡板反射弹球,击碎屏幕上方的各种砖块。本教程将深入讲解如何利用Cocos2d和Box2D这两个强大的开源框架...
在这个特定的资源中,我们主要关注的是HSMC(High-Speed Mezzanine Connector)Breakout Header的相关设计资料,包括原理图、PCB布局和组装信息。 首先,HSMC是一种高速连接器,它提供了高速信号传输的能力,常用于...
指标 5 day Breakout
《MetaTrader 5中的"channel_breakout_entry"脚本详解》 在金融市场交易中,有效的策略往往是基于对市场波动性的理解和利用。"channel_breakout_entry"脚本是针对MetaTrader 5 (MT5) 平台设计的一个智能交易系统...
MT4平台支持自定义指标、脚本和EA(Expert Advisor,智能交易系统),其中“Chin Breakout Alert”是一款针对MT4平台的自定义指标。 【Chin Breakout Alert指标介绍】 "Chin Breakout Alert" 指标,顾名思义,是一...
Breakout2021:2021春招算法备战