基于LSH的shapelets转换方法

丁智慧，乔钢柱，程 谭，宿 荣

中北大学 大数据学院，太原030051

时间序列是随时间观测和变化的一系列时值，广泛用于金融行业[1]、医疗领域[2]、天气预测[3]等。近年来随着时间积累和数据类别的增长，时间序列的数量和维度也大量增长，海量高维数据的分析处理成了目前各个行业面临的挑战。时间序列数据的分类问题是数据挖掘中一类重要方法，其目的是从已标定类别的训练集中提取出带有能够区分类别的显著性特征，分类器根据这些特征与未标记类别的时间序列之间的相似性进行分类。根据文献[4]将时间序列分类算法分为基于全局特征的算法、基于局部特征的算法和集成算法。基于全局特征的算法是将整条时间序列作为特征进行相似性比较，解决该类问题最具代表的方法是基于欧氏距离（Euclidean Distance）和动态时间规整（Dynamic Time Wrapping，DTW）的最近邻（1-NN）算法，但采用欧氏距离会因为相位漂移影响结果，而DTW 算法消耗大量的时间和空间，只适用于小型数据集，对海量数据无能为力。近些年的研究均集中于寻找更优秀的距离度量方法[5-8]，例如Batista 等人[6]提出复杂性不变的度量方式（CID）、Jeong 等人[8]提出全局加权DTW（WDTW）增加了一个基于扭曲路径中各点之间的扭曲距离的乘法权重惩罚。基于局部特征的算法将时间序列的一部分作为特征，有分段聚集近似（PAA）[9]、符号聚集近似（SAX）[10]等分段表示方法，以及通过选择多个区间并使用汇总测度作为特征的分类方法[11]，基于shapelets 的分类算法[12]枚举出数据集中所有的子序列，通过信息增益选择最佳shapelets 作为决策树节点分类准则，具有分类精度高、速度快、可解释性强的优点。……