`
阅读更多

在时间序列分析中,断点检测(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)。

 

 

  • 大小: 80.1 KB
  • 大小: 50.4 KB
  • 大小: 188.5 KB
1
1
分享到:
评论

相关推荐

    Breakout检测R包BreakoutDetection.zip

    BreakoutDetection(Breakout Detection)是 Twitter 的开源的,可以便捷和快速检测 Breakout 的 R 包。BreakoutDetection 通过健壮的 E-Statistics 来实现。BreakoutDetection 包可以在广泛的各种场景使用,比如,...

    多种深度强化学习算法在雅达利游戏breakout中的设计与实现

    在《Breakout》中,DDPG可以学习到平滑的动作序列,以连续控制球的轨迹。 4. **演员-评论家(Actor-Critic)算法**: 这类算法结合了策略梯度和值函数的优化,其中“演员”负责更新策略,而“评论家”则提供策略质量...

    基于transformer的序列建模强化学习算法开发.zip

    《基于Transformer的序列建模强化学习算法开发》 在当今的AI领域,深度学习和强化学习是两大核心技术,而Transformer模型则是近年来在自然语言处理(NLP)领域中备受瞩目的创新。本项目旨在深入理解并复现基于...

    breakout-game_前端小游戏_breakout_

    【标题】"breakout-game_前端小游戏_breakout_" 指的是一款利用原生JavaScript编写的打砖块游戏。在Web开发领域,前端小游戏是一种常见的练习项目,它可以帮助开发者提升JavaScript编程技能,同时也能增强对HTML、...

    matlab开发-Breakout

    《MATLAB开发:Breakout游戏实现详解》 MATLAB,作为一种强大的数学计算和数据分析软件,也被广泛用于图形用户界面(GUI)和游戏开发。本文将深入探讨如何利用MATLAB进行"Breakout"游戏的开发,这是一款类似Pong的...

    Breakout_RSI - MetaTrader 5脚本.zip

    通过 Breakout RSI 指标,交易者可以自动化识别可能的市场突破,节省手动分析的时间,同时减少因人为判断失误导致的交易风险。然而,任何指标都不能保证100%的交易成功,因此,结合其他分析方法,如趋势线、支撑阻力...

    BreakOut15 - MetaTrader 4EA.zip

    《MetaTrader 4 EA——BreakOut15智能交易系统详解》 在外汇交易领域,MetaTrader 4(MT4)平台因其强大的图表分析工具、自动化交易功能和丰富的技术指标而备受推崇。其中,智能交易系统(Expert Advisor,简称EA)...

    Breakout Version下载资源

    《Breakout Version下载资源》是源自唐胜555的一款基于smbx平台的地图资源,主要为玩家提供了独特的游戏体验。smbx是一款开源的、免费的超级马里奥兄弟游戏制作工具,允许用户创建自己的游戏关卡和世界,极大地扩展...

    EURUSD breakout - MetaTrader 5EA.zip

    【标题解析】:“EURUSD breakout - MetaTrader 5 EA.zip” 这个标题表明我们讨论的是一个基于MetaTrader 5(MT5)平台的自动交易系统,也被称为专家顾问(Expert Advisor,简称EA)。"EURUSD breakout"部分指的是该...

    打砖块breakout

    "打砖块Breakout"是一款经典的街机游戏,它的核心玩法是通过控制一块挡板反射一个小球,击碎屏幕上排列的砖块。在这个基于OpenGL编写的版本中,我们可以深入探讨几个重要的IT知识点。 1. **OpenGL**: OpenGL是一个...

    breakout_breakout_powerbuilder_

    《PB中的Breakout游戏开发详解》 在信息技术领域,编程游戏是学习编程和软件开发的绝佳途径。"Breakout",又称打砖块,是一款经典的街机游戏,因其简单而富有挑战性的玩法深受程序员喜爱。在PowerBuilder(简称PB)...

    Breakout box2d学习代码

    【标题】"Breakout box2d学习代码"是基于Box2D物理引擎和Cocos2D 2.1框架创建的一款经典打砖块游戏(Breakout)的学习资源。这个项目旨在帮助初学者理解和掌握如何利用Box2D进行游戏开发,以及在Cocos2D 2.1环境下...

    强化学习-Breakout-v0.zip

    【描述】描述中的"强化学习-Breakout-v0.zip"可能是一个教学材料或课程作业,包含了学生或研究人员在探索和应用强化学习算法到Breakout游戏上的工作。"Breakout-v0"是OpenAI Gym库中的一个版本,它为AI提供了与游戏...

    breakout2-1.0-linux

    "breakout2-1.0-linux" 是一个基于Linux平台的游戏程序,由流行的跨平台应用程序框架QT构建。这个压缩包包含的是游戏的可执行文件,用户可以直接在Linux系统上运行,无需进行安装步骤,简化了游戏的使用流程。游戏...

    cocos2d和box2d来制作一个Breakout游戏

    《使用Cocos2d和Box2D创建Breakout游戏》 Breakout游戏,又名打砖块,是一款经典的街机游戏,玩家通过控制一块挡板反射弹球,击碎屏幕上方的各种砖块。本教程将深入讲解如何利用Cocos2d和Box2D这两个强大的开源框架...

    Stratix IV GX 开发套件HSMC_breakout_header原理图和PCB源文件

    在这个特定的资源中,我们主要关注的是HSMC(High-Speed Mezzanine Connector)Breakout Header的相关设计资料,包括原理图、PCB布局和组装信息。 首先,HSMC是一种高速连接器,它提供了高速信号传输的能力,常用于...

    5 day Breakout - MetaTrader 4脚本.zip

    指标 5 day Breakout

    channel_breakout_entry - MetaTrader 5脚本.zip

    《MetaTrader 5中的"channel_breakout_entry"脚本详解》 在金融市场交易中,有效的策略往往是基于对市场波动性的理解和利用。"channel_breakout_entry"脚本是针对MetaTrader 5 (MT5) 平台设计的一个智能交易系统...

    Chin Breakout Alert - MetaTrader 4脚本.zip

    MT4平台支持自定义指标、脚本和EA(Expert Advisor,智能交易系统),其中“Chin Breakout Alert”是一款针对MT4平台的自定义指标。 【Chin Breakout Alert指标介绍】 "Chin Breakout Alert" 指标,顾名思义,是一...

    Breakout2021:2021春招算法备战

    Breakout2021:2021春招算法备战

Global site tag (gtag.js) - Google Analytics