计算机工程与应用
www.ceaj.org
2018，54（16）
1 引言
时间序列 shapelets 是时间序列中能够最大限度地
表示一个类别的子序列，是时间序列局部特征的表示，
由 Ye 等人
[1]
所提出。shapelets 算法采用时间序列局部
片段进行分类，很大程度上避免了噪声的影响，更加精
确和健壮，同时，s hap elets 分类可以产生具有较高说明
性的结果，能够很明确地显示出类别之间的差异之处，
指明为什么一个特定的对象被分配到一个特定的类中，
帮助研究人员更好地理解数据。shapelets 已经作为时
间序列领域一个重要的研究主题，受到了越来越多的关
注
[2-5]
，还被应用到了医疗服务
[6]
、运动检测
[7]
、电力需求
分析
[8]
、聚类研究
[9]
等领域。
最早提出的基于 shapelets分类是在查找出 shapelets
基础上通过构建决策树的方法来完成的，因此查找出
shapelets的好坏决定了分类的效果。原始查找 shapelets
的方法要产生所有可能的候选集，然后依次计算它们的
基于非相似原理快速查找多个 shapelets
韦庆锋，何国良
WEI Qingfeng, HE Guoliang
武汉大学 软件工程国家重点实验室，武汉 430072
State Key Lab of Soft ware Engineering, Wuhan University, Wuhan 430072, China
WEI Qingfeng, HE Guoliang. Efficient discovery of multiple shapelets based on non-similarity p rinciple. Computer
Engineeri ng and Applications, 2018, 54（16）：119-128.
Ab stract：Time series shapelets are small subsequences that describe the local property of time series and maximally
differentiate cl asses. Since the inception o f s hap elets, researchers h ave paid clo se attention to it. However, because o f the
high time complexity, this m ethod can’t be used widely. A novel method（Non-Similar Discove r of Shapel et, NSDS）is
propos ed to discover time serie s s hap elets quickly. According to the character of non-similar of the shapelets, this pape r
sets a distance threshold to filter out similar subsequence in the cand idate set . Then the class separability is used as the
evaluation criterion of the filtered subsequence, and finally the best performance of mu ltiple shapelets is selected. The
experimental results show that the pro posed method c an gre atly reduce the time of searching shapelets and maintain high
classification accuracy. The method is extend ed to the multivariate time series , and the multiple cl assifiers are used to
improve the classification accurac y.
Key words：time serie s; shapelets; classification; class separability
摘 要：shapelets 是描述时间序列局部特征的子序列，它能最大程度对不同类别进行区分。从它的发明至今一直吸
引着研究者的关注，但是由于过高的时间复杂度阻碍了它被广泛应用。一种快速查找多个 shapelets 的方法（Non-
Similar Discover of Shapelet，NS DS）被提出 ：基于 shapelets 非相似的特性，根据子序列间距离分布设置一个距离阈
值，以此过滤掉候选集中的相似子序列。再使用类可分离性作为过滤后的候选子序列的评价标准，最终选择出性能
最好的多个 shapele ts。通过在单变量时间序列数据集上的实验表明了该方法可以极大缩短查找 shapelets时间，而且
能保持较高的分类准确性。将该方法扩展到多变量时间序列，对多个变量采用组合分类器的方法来提高整体分类
的准确率。
关键词：时间序列；shapelets；分类；类可分离性
文献标志码：A 中图分类号：TP311.13 doi：10.3778/j.i ssn.1002-8331.1704-0035
基金项目：国家自然科学基金（N o.61672391）。
作者简介：韦庆锋（1988—），男，硕士研究生，研究领域为时间序列、数据挖掘，E-mail：wei22357@163.com；何国良（1974—），男，
博士，副教授，研究领域为数据挖掘、智能信息处理、智能算法。
收稿日期：2017-04-07 修回日期：2017-05-22 文章编号：1002-8331（2018）16-0119-10
CN KI网络出版：2017-08-10, http://kns.cnki.net/k cms/detail/11.2127.TP.20170810.0853.01 4.html
Computer Engineering and Applications计算机工程与应用
119
评论0