标题：时间序列“小形状”：数据挖掘的新原型
ABSTRACT
- 本文解决的是时间序列分类问题；
- 之前的方法主要是基于KNN的（欧式/DTW）距离分类，有三个问题：
- 可解释性差；
- 需要存储、搜索整个数据集。
- 考虑整体特征，易受噪声影响。
1. INTRODUCTION
- 基本做法：shapelet是数据集中某个序列的一个子序列。分类是让数据集中所有序列和这个子序列计算距离，再设定一个阈值，小于这个阈值的是一类，大于这个阈值的是一类。
- 优化目标：分类的优化目标是信息增益。
- 挑战：如何找到一个最优的shapelet
2. RELATED WORK AND BACKGROUND
- 不等长序列距离度量：遍历所有长序列的子序列，找到距离最小的即为距离
- 熵：一个数据集D分成A，B两个类，其熵值为
p(A),p(B)为A，B所占比例 - 信息增益：将一个数据集D分类后，熵值的变化。
- 选择信息增益的一个原因是可以轻易扩展成多分类问题。
- 最优分割点：给定一个子序列做shapelet，选择哪个分类阈值可以获得最高的分类信息增益。
- shapelet：最优子序列+最优分割点就是shapelet
3. FINDING THE SHAPELET
3.1 Brute-Force Algorithm
最简单的寻找shapelet的方法就是暴力遍历：
- 找出数据集中序列的所有子序列；
- 每个子序列依次作为shapelet候选子序列进行检验；
- 检验时首先计算Candidate和数据集中所有序列的距离，获得距离直方图；
- 根据这个距离直方图找一个最优分割点，返回该情况下的信息增益。
3.2 Subsequence Distance Early Abandon
距离计算可以剪枝，即如果当前的部分欧式距离已经超过BSF，那么直接放弃掉。
3.3 Admissible Entropy Pruning
candidate检验也可以利用上界来进行剪枝。假设现在根据某个candidate做了一半的距离直方图，那么信息增益的上界就是把剩下的一半，一半（总量的1/4）放给距离0，一半放给距离最大值+1，此时信息增益是理论最大的。
如果这个上界的信息增益也不如BSF，那么直接进入下一个candidate。
网友评论