SAX, SAX 热SAX和EMMA的Java实现

分享于 

13分钟阅读

GitHub

  繁體 雙語
Java implementation of time series symbolic discretization and HOT-SAX time series discord discovery
  • 源代码名称:SAX
  • 源代码网址:http://www.github.com/jMotif/SAX
  • SAX源代码文档
  • SAX源代码下载
  • Git URL:
    git://www.github.com/jMotif/SAX.git
    Git Clone代码到本地:
    git clone http://www.github.com/jMotif/SAX
    Subversion代码到本地:
    $ svn co --depth empty http://www.github.com/jMotif/SAX
    Checked out revision 1.
    $ cd repo
    $ svn up trunk
    
    基于的时间序列符号离散化

    Build Statuscodecov.ioMaven CentralLicense

    这里代码是在 GPL v.2.0 下发布的,并在Java中实现:

    • 符号聚合近似( 例如,SAX ) 工具包堆栈 [1 ]
    • 时间序列主题发现 [2 ]的EMMA ( 基于矩阵逼近的模数) 算法
    • 一种时间序列异常( 不一致) 发现算法 [3 ]
    • 时间序列位图相关例程 [4 ]
    注意,库的大部分功能也可以在Rpython 插件中获得。

    [1] Lin,Temporal,Temporal,Temporal,Temporal,Temporal,Temporal,Temporal,Temporal,Temporal,Temporal,Temporal,Temporal,Temporal,Temporal,Temporal,Temporal,Temporal。

    [2],P,Keogh,,,Proc,Proc,Proc,Proc,Proc,Proc,Proc,Proc,Proc,等。 ICDM ( 2002 )

    [3] Keogh,E,,Fu,A,,: 有效地找到最不寻常的时间序列序列子序列。 ICDM ( 2005 )

    [4],N,Lolla,V.N,Keogh,E.J,Lonardi,S。 Chotirat ( 神经网络) Ratanamahatana,时间系列位图: SDM Apr中的一个实用可视化工具,用于处理大型时间序列数据库( )。 531 -535 )。

    引用这里工作:

    如果你正在为你的学术工作使用这里实现,请参考我们的Grammarviz 3.0纸张:

    ,Gandhi,Gandhi,Gandhi,Gandhi,,,,,,。 变长时间序列模式的交互式发现 ACM。 ,。2018年02月。Data。

    recurrent和异常模式检测的替代解决方案:

    If Pattern 发现时间序列,请查阅我们称为 GrammarViz 2.0的新工具,如有兴趣,请查阅。 这种新方法基于符号离散化。语法推理和算法(。例如,Kolmogorv复杂度),使线性时间变长模式发现和比热 sax discords发现模型更快的数量有序。

    0.0 SAX转换简介

    SAX用于将有理数( 例如,时间序列) 序列转换为字母( 例如,字符串) 序列。 128点转换为 8字母的时间序列的插图:

    SAX in a nutshell

    在数据挖掘中,离散化是最常用的转换,SAX在整个领域中得到了广泛的应用。 在它的作者页面查找关于SAX的更多信息: 作者:,Jessica,keogh,,,,。

    1.0建筑

    代码是用Java编写的,我使用 Maven 来构建它。 使用配置文件 single 构建包含所有依赖项的可以执行 jar:

    
    $ mvn package -P single
    
    
    
    [INFO] Scanning for projects...
    
    
    [INFO] ------------------------------------------------------------------------
    
    
    [INFO] Building jmotif-sax
    
    
    [INFO] task-segment: [package]
    
    
    
    ...
    
    
    
    [INFO] Building jar:/media/Stock/git/jmotif-sax/target/jmotif-sax-1.0.1-SNAPSHOT-jar-with-dependencies.jar
    
    
    [INFO] ------------------------------------------------------------------------
    
    
    [INFO] BUILD SUCCESSFUL
    
    
    
    

    2.0使用CLI转换到SAX转换的时间系列

    jar 文件可以用于将时间序列( 表示为单个列文本文件) 通过 命令行 中滑动窗口转换为 SAX:

    
    $ java -jar target/jmotif-sax-0.1.1-SNAPSHOT-jar-with-dependencies.jar
    
    
    Usage: <main class> [options] 
    
    
    Options:
    
    
     --alphabet_size, -a
    
    
     SAX alphabet size, Default: 3
    
    
     --data, -d
    
    
     The input file name
    
    
     --out, -o
    
    
     The output file name
    
    
     --strategy
    
    
     SAX numerosity reduction strategy
    
    
     Default: EXACT, Possible Values: [NONE, EXACT, MINDIST]
    
    
     --threads, -t
    
    
     number of threads to use, Default: 1
    
    
     --threshold
    
    
     SAX normalization threshold, Default: 0.01
    
    
     --window_size, -w
    
    
     SAX sliding window size, Default: 30
    
    
     --word_size, -p
    
    
     SAX PAA word size, Default: 4
    
    
    
    

    运行时,它会打印时间序列点索引和相应的单词:

    
    $ java -jar"target/jmotif-sax-1.0.1-SNAPSHOT-jar-with-dependencies.jar" 
    
    
     -d src/resources/test-data/ecg0606_1.csv -o test.txt
    
    
    $ head test.txt
    
    
    0, aabc
    
    
    8, aacc
    
    
    13, abcc
    
    
    20, abcb
    
    
    ...
    
    
    
    

    3.0 API用法

    有两个类实现end-to-end的工作流。 这些是 TSProcessor ( 实现时间序列相关函数) 和 SAXProcessor ( 实现离散化)。 下面是典型的使用场景:

    3.1 Discretizing时间序列按块:
    
    //instantiate classes
    
    
    NormalAlphabet na = new NormalAlphabet();
    
    
    SAXProcessor sp = new SAXProcessor();
    
    
    
    //read the input file
    
    
    double[] ts = TSProcessor.readFileColumn(dataFName, 0, 0);
    
    
    
    //perform the discretization
    
    
    String str = sp.ts2saxByChunking(ts, paaSize, na.getCuts(alphabetSize), nThreshold);
    
    
    
    //print the output
    
    
    System.out.println(str);
    
    
    
    
    3.2 Discretizing时间序列通过滑动窗口:
    
    //instantiate classes
    
    
    NormalAlphabet na = new NormalAlphabet();
    
    
    SAXProcessor sp = new SAXProcessor();
    
    
    
    //read the input file
    
    
    double[] ts = TSProcessor.readFileColumn(dataFName, 0, 0);
    
    
    
    //perform the discretization
    
    
    SAXRecords res = sp.ts2saxViaWindow(ts, slidingWindowSize, paaSize, 
    
    
     na.getCuts(alphabetSize), nrStrategy, nThreshold);
    
    
    
    //print the output
    
    
    Set<Integer> index = res.getIndexes();
    
    
    for (Integer idx : index) {
    
    
     System.out.println(idx +"," + String.valueOf(res.getByIndex(idx).getPayload()));
    
    
    }
    
    
    
    
    通过滑动窗口的 3.3多线程离散化 :
    
    //instantiate classes
    
    
    NormalAlphabet na = new NormalAlphabet();
    
    
    SAXProcessor sp = new SAXProcessor();
    
    
    
    //read the input file
    
    
    double[] ts = TSProcessor.readFileColumn(dataFName, 0, 0);
    
    
    
    //perform the discretization using 8 threads
    
    
    ParallelSAXImplementation ps = new ParallelSAXImplementation();
    
    
    SAXRecords res = ps.process(ts, 8, slidingWindowSize, paaSize, alphabetSize, 
    
    
     nrStrategy, nThreshold);
    
    
    
    //print the output
    
    
    Set<Integer> index = res.getIndexes();
    
    
    for (Integer idx : index) {
    
    
     System.out.println(idx +"," + String.valueOf(res.getByIndex(idx).getPayload()));
    
    
    }
    
    
    
    
    3.4时间系列主题( 递归 Pattern ) 发现

    EMMAImplementation 实现了一种使用EMMA算法获取最频繁的结构模式的方法:

    
    //read the data
    
    
    double[] series = TSProcessor.readFileColumn(DATA_FNAME, 0, 0);
    
    
    
    //find the best motif with EMMA
    
    
    MotifRecord motifsEMMA = EMMAImplementation.series2EMMAMotifs(series, MOTIF_SIZE, 
    
    
     MOTIF_RANGE, PAA_SIZE, ALPHABET_SIZE, ZNORM_THRESHOLD);
    
    
    
    //print motifs
    
    
    System.out.println(motifsEMMA);
    
    
    
    

    SAXRecords 实现了一个获取最频繁的SAX单词的方法:

    
    //read the data
    
    
    double[] series = TSProcessor.readFileColumn(DATA_FNAME, 0, 0);
    
    
    
    //instantiate classes
    
    
    Alphabet na = new NormalAlphabet();
    
    
    SAXProcessor sp = new SAXProcessor();
    
    
    
    //perform discretization
    
    
    saxData = sp.ts2saxViaWindow(series, WIN_SIZE, PAA_SIZE, na.getCuts(ALPHABET_SIZE),
    
    
     NR_STRATEGY, NORM_THRESHOLD);
    
    
    
    //get the list of 10 most frequent SAX words
    
    
    ArrayList<SAXRecord> motifs = saxData.getMotifs(10);
    
    
    SAXRecord topMotif = motifs.get(0);
    
    
    
    //print motifs
    
    
    System.out.println("top motif" + String.valueOf(topMotif.getPayload()) +" seen" + 
    
    
     topMotif.getIndexes().size() +" times.");
    
    
    
    
    基于暴力搜索的时间序列异常检测

    BruteForceDiscordImplementation类实现对discords的强制搜索,它旨在作为测试的参考。

    
    discordsBruteForce = BruteForceDiscordImplementation.series2BruteForceDiscords(series, 
    
    
     WIN_SIZE, DISCORDS_TO_TEST, new LargeWindowAlgorithm());
    
    
    
     for (DiscordRecord d : discordsBruteForce) {
    
    
     System.out.println("brute force discord" + d.toString());
    
    
     }
    
    
    
    
    使用HOTSAX的时间序列异常发现

    HOTSAXImplementation 类实现了时间序列不一致发现的HOTSAX算法:

    
     discordsHOTSAX = HOTSAXImplementation.series2Discords(series, DISCORDS_TO_TEST, WIN_SIZE,
    
    
     PAA_SIZE, ALPHABET_SIZE, STRATEGY, NORM_THRESHOLD);
    
    
    
     for (DiscordRecord d : discordsHOTSAX) {
    
    
     System.out.println("hotsax hash discord" + d.toString());
    
    
     }
    
    
    
    

    注意,与HOTSAX一起使用的"正确"策略是 NumerosityReductionStrategy.NONE,但是你可以尝试加速搜索,但不保证。

    库源代码有示例( 测试) 用于在这里使用这些 ,这里是和。

    4.0时间序列位图

    库还实现了简单的例程,将时间序列转换为 [4] 之后的位图。 以下是本文中六个数据集的示例: Six "normal" datasets

    将它的转换为图表频率表并使用Jet调色板着色:

    Six "normal" datasets as bitmaps

    然后,基于图表发生频率( euclidean )的群集( hcave ):

    Six "normal" datasets clustered via bitmap

    5.0线程性能

    plot 显示了在数据集 300_signal1.txt 上使用并行化SAX版本时所达到的加速效果(。 实验中使用的参数: 滑动窗口大小 200,PAA大小 11,字母表大小 7和三个不同的NR策略。

    注意,对于 MINDIST numerosity reduce策略,并行化代码没有基于离散化的第一次执行,而是将结果。 在下面的plot 上,7 + CPU的性能差异是由于服务器负载不均匀,我猜想。

    Performance plot

    使用Aloha制作的

    Made with Aloha!

    版本:

    1.1.4

    • 修正"领带"为--选择一个最小方差的主题

    1.1.3

    • 添加一个带有 fake ADM的EMMA实现
    • 一些旧的代码优化( 破坏一些 api )

    1.1.2

    • 维护发行版--大多数shingling例程的更改,适用于其他项目的API

    1.1.1

    • HOTSAX实现参数 Bug 修复

    1.1.0

    1.0.10

    • shingling/位图CLI修复
    • SAX通过块修复了--正确的符号索引( 感谢s ) !

    1.0.9

    • 修正了误差大小计算的误差
    • 将z 规范添加到距离计算例程中,从而改变了HOTSAX和BRUTEFORCE行为

    1.0.8

    • 添加了 shingling

    1.0.7

    • 删除了logback依赖项

    1.0.5 - 1.0.6

    • 对grammarviz3工作增加离散化近似误差计算

    1.0.4

    • 通过滑动窗口固定SAX转换,最后添加了最后一个窗口

    1.0.3

    • 改进的PAA性能

    1.0.1 - 1.0.2

    • 更多测试,Bug 修复,CI

    0.0.1 - 1.0.0

    • 清理旧JMotif代码并将SAX代码与其他代码分离

    JAVA  IMP  Implementation  SAX  EMMA  
    相关文章