MERLIN
一、文献相关信息
- 文献名：
《MERLIN: Parameter-Free Discovery of Arbitrary Length
Anomalies in Massive Time Series Archives》 - 作者：
Takaaki Nakamura，Makoto Imamura，Ryan Mercer，Eamonn Keogh - 发表会议
ICDM - 发表日期
2020年
二 、重要定义
- 非自匹配：给定一个时间序列T，其中包含一个从p位置开始长度为L的子序列C和一个从q位置开始的匹配子序列M，如果∣ p − q ∣ ≥ L |p-q|≥L ∣p −q ∣≥L，则称M是在D i s t ( M , C ) Dist(M,C)D i s t (M ,C )距离处与C的非自匹配。
- 时间序列Discord：给定一个时间序列T，如果 D与其 最近的非自匹配的距离最大，则从位置i开始长度为L的子序列 D称为T的Discord。
三、论文拟解决的主要问题
- 解决Discord的效用会由于用户选择的子序列长度的敏感性而降低的问题
- 在大量的时间序列集中有效并准确地找到所有可能长度的Discord（异常）
四、论文的主要研究内容
- 正式定义了时间序列Discord
- 介绍了一种可伸缩性的算法——MERLIN
- 回顾了SOTA异常发现算法，文本的算法重复的使用了该算法，并且说明了参数r（异常的范围）的设置至关重要
- 展示了本文想法的通用性，并表明MERLIN可以发现一些微妙的异常
五、论文使用的算法
- MERLIN算法：
1~ 6：对于试图发现的第一个Discord的长度，可以设置r = 2 𝐿 r=2\sqrt𝐿r =2 L ，并一直将其减半，直到成功；7~ 14：在这里，可以使用之前的Discord距离减去一个距离，比如1%。在不太可能的情况下，这太保守，导致失败，可以继续减去1%，直到成功；15 ~ 24：计算平均值M、标准差S，利用r = M − 2 S r =M-2S r =M −2 S来预测一个好的r值，直到成功。
; 六、实验评估
1. 发现超细微的异常现象
例子1 ：
下图为一名51岁男性的心电图（ECG），在大约一半的位置处有一个明显的异常。
假设只考虑中心静脉压（CVP）数据，则聚氯乙烯异常在CVP中并不明显，但MERLIN可清楚地显示了该异常的位置，如下图所示：
例子2：
下图为来自火星科学实验室（MSL）探测器好奇号的数据片段：
由上图可知：MERLIN能够发现数据中的微妙异常。
2. 不同尺度的异常
例子1：
先重新访问一下纽约市的出租车需求数据集，下图显示了该数据的一个子集，只有从5小时到4天的每个长度的前1个motif：
MERLIN在上图中发现了长达4天的异常现象，反映了在正常日子所包围的情况下，感恩节是异常的。
例子2：
台北新建区办公地铁站类似但更长的客运量数据集：
搜索了10小时到10天的范围，只发现了7个异常，一些是自然原因，一些是文化文物，下图显示了其中4个异常：
例子3：
墨尔本市来自城市各地点一个月的行人交通量数据如下：
MERLIN发现的异常如上图所示，发现的最短的异常在语义上是有意义的，它对应于一个快闪舞表演的视频:：https://www.youtube.com/watch?v=gLzDFjiRQE8.
3. 可伸缩性
为了测试MERLIN算法的可伸缩性，比较了MERLIN和SCRIMP、D R A G M L DRAG_{ML}D R A G M L ，结果如下所示：
对于短时间序列，所有算法的性能都很相似，但随着时间序列长度的增加，SCRIMP的二次复杂度开始显示出来，D R A G M L DRAG_{ML}D R A G M L 所花时间也逐渐增大，只有MERLIN随着时间序列长度的增加，其所花时间比较稳定，证明了其具有很好的可伸缩性。
4. Yahoo基准
例子1：
由上图中图可知，如果只考虑5到64，将得到完美的结果。只有当考虑一个不现实的值大于65时，才得到一个假阳性；由上图底图可知，可以检测到7个异常中的6个异常，并且没有假阴性。
5. NASA基准
扫描所有的数据集，寻找那些人眼在5秒内无法明显解决的例子。排除接近冗余的示例外，只有 三个数据集通过了该测试，在它们上运行MERLIN的结果如下图所示：
结果表明，除了上图中心中一个小的假阳性区域外，在三个数据集上都获得了完美的结果（找到了异常）。
6. 汽油基准
下图展示了在两个更具挑战性的示例上运行MERLIN的结果：
C temperature T 中的单一异常很容易发现，但可能有一个小区域，本文报告了假阳性；RT_level中的单一异常很容易被发现。
; 七、LSTM和MERLIN
- LSTM需要训练数据，并仔细设置8个参数
- MERLIN没有训练数据的情况下发现了微妙的异常，只需考虑MinL（异常下界长度）和MaxL（异常上界长度）
八、论文的创新点
- 首次提出了MERLIN算法
- 在大量的时间序列中发现所有长度的异常
Original: https://blog.csdn.net/qq_41307208/article/details/124150276
Author: Nicole 可
Title: 【MERLIN】
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/697536/
转载文章受原作者版权保护。转载请注明原作者出处！