基本信息

  • 论文题目：基于趋势特征表示的 shapelet 分类方法

（Shapelet classification method based on trend feature representation）

  • 论文地址：http://www.joca.cn/EN/Y2017/V37/I8/2343

原理

在 Shaplet 被提出后的几年里，出现了很多算法来提高 Shapelet 效率和扩展其应用范围，《Shapelet classification method based on trend feature representation》简称 TDTS 提出了一种基于趋势的 top-K shapelet。

其核心方法有三个：

  • 对分段后的子序列进行基于趋势的符号化处理

    符号化的原理请见 SAX 论文，简单地说，它实现了连续到离散的转化，用简单的值表征一个序列，包含趋势的符号化方法用二元组<K,u>表示序列，其中 K 是斜率，u 是该序列的终点值。

    它使用滑动窗口计算窗口内的斜率，当斜率变化大于某一阀值时（趋势改变时），则产生一个分段点 u 并继续滑动．所有分段完成后，后对每一段进行符号化，最终生成转换后的 TFSA．

  • 保持趋势特征的 shapelet 发现算法

    随机覆盖序列的子序列，然后对未覆盖的子序列进行 Hash 碰撞检测，得出碰撞频次，进行频次分析．使用该方法选出的 shapelet 在自身所在类中碰撞频次较高，而在其它类中频次较低，因此更具代表性．

  • 使用图对子序列进行相关性分析，去除相关特征。

    把上一步得到的 shapelets 按信息增益排序，然后作为点加入图中；依次遍历所有点，计算它与其它点是否相似，如果相似，则在两点间建立一条边；然后开始从信息增益最大的点开始加入目标集合，如果与该点相似的其它点（有边相连）已加入目标集合，则跳过该点．由此保证目标集合中的点尽量不相关．

问与答

  • 趋势指啥？

    趋势指上升（正值）、降（负值）、平稳（零）等时间趋势

  • 用图干啥？

    当获取多个子序列时，去掉其中相关性强的子序列

  • 为啥取 Top-k？

    从所有可选的 shapelets 里选前 k 个最重要的子序列，相对于只取最重要的一个子序列，有更强的表征能力。

  • 图和趋势有什么关系？

    文中同时使用了这两种方法，它们之前没有什么关系。