基于SAX方法的时间序列分类问题的多阶段改进研究

J4 ›› 2016, Vol. 38 ›› Issue (05): 988-996.

基于SAX方法的时间序列分类问题的多阶段改进研究

宋伟1，张帆2,叶阳东1，韩鹏3，范明1

（1.郑州大学信息工程学院，河南郑州 450001;
2.华北水利水电大学信息工程学院,河南郑州 450045;3.河南省国家税务局，河南郑州 450000)

收稿日期:2015-11-26 修回日期:2016-01-30 出版日期:2016-05-25 发布日期:2016-05-25
基金资助:
国家自然科学基金（61170223）；河南省基础与前沿技术研究计划（142300410229）；河南省教育厅科学技术研究重点项目（13A520453）

A multiphased improvement for time series
classification based on symbolic aggregation
approximation representation

SONG Wei1，ZHANG Fan2,YE Yangdong1，HAN Peng3，FAN Ming1

（1.School of Information Engineering,Zhengzhou University,Zhengzhou 450001;
2.School of Information Engineering,North China University of Water Resources and Electric Power,Zhengzhou 450045;
3.State Administration of Taxation,Henan Provincial Office,Zhengzhou 450000,China）

Received:2015-11-26 Revised:2016-01-30 Online:2016-05-25 Published:2016-05-25

摘要/Abstract

摘要：

分类问题是数据挖掘中的基本问题之一，时间序列的特征表示及相似性度量是时间序列数据挖掘中分类、聚类及模式发现等任务的基础。SAX方法是一种典型的时间序列符号化表示方法，在采用该方法的基础上对时间序列进行分类，不仅可以有效地降维、降噪，而且具有简单、直观等特点，但是该方法有可能造成信息损失并影响到分类结果的准确性。为了弥补信息损失对分类结果的影响，采用了集成学习中大多数投票方法来弥补BOP表示后的信息损失，从而提高整个分类器的效率。针对一些样本在BOP表示中都损失了相似的重要信息，以至于大多数投票无法进一步提高分类效率的问题，进一步提出了结合集成学习中AdaBoost算法，通过对训练样本权重的调整，从而达到以提高分类器性能来弥补信息损失的效果。实验结果表明，将BOP方法与集成学习相结合的方法框架，不仅能很好地处理SAX符号化表示中的信息损失问题，而且与已有方法相比，在分类准确度方面也有显著的提高。

关键词: 时间序列, SAX, 分类, 集成学习, 多阶段

Abstract:

Classification is one of the basic tasks in data mining, and feature representation and similarity measurement act as the important basis of time series data mining. The symbolic aggregate approximation (SAX) is a typical symbolic representation method which is straightforward and very simple, and which can efficiently converts time series data to a symbolic representation with dimensionality/ noise reduction. But the potential of information loss can affect the accuracy of the classification results. Focusing on the SAX discretization method coupled with the bag of patterns (BOP) representation in classification task, we propose a multiphased approach framework using the AdaBoost algorithm and voting in ensemble learning to remedy the information loss of the SAX representation. Experimental results show that the proposed method can improve classification accuracy greatly.

Key words: time series;SAX;classification;ensemble learning;multiphased

宋伟1，张帆2,叶阳东1，韩鹏3，范明1. 基于SAX方法的时间序列分类问题的多阶段改进研究[J]. J4, 2016, 38(05): 988-996.

SONG Wei1，ZHANG Fan2,YE Yangdong1，HAN Peng3，FAN Ming1. A multiphased improvement for time series
classification based on symbolic aggregation
approximation representation [J]. J4, 2016, 38(05): 988-996.

参考文献［18］

［1］	Fu T.A review on time series data mining［J］.Engineering Applications of Artificial Intelligence,2011,24(1):164181.
［2］	Li Hailin,Guo Chonghui.Survey of feature representations and similarity measurements in time series data mining［J］.Application Research of Computers,2013,30(5):12851291.(in Chinese)
［3］	Lin J,Keogh E,Lonardi S,et al.A symbolic representation of time series,with implications for streaming algorithms［C］∥Proc of the 8th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery(DMKD’03),2003:211.
［4］	Lin J, Keogh E, Wei L, et al.Experiencing SAX:A novel symbolic representation of time series［J］.Data Mining and Knowledge Discovery,2007,15(2):107144.
［5］	Junejo I,Aghbari Z.Using SAX representation for human action recognition［J］.Journal of Visual Communication and Image Representation,2012,23(6):853861.
［6］	Oates T,Mackenzie C,Stein D,et al.Exploiting representational diversity for time series classification［C］∥Proc of the 11th International Conference on Machine Learning and Applications(ICMLA’12),2012:538544.
［7］	Freund Y,Schapire R.Experiments with a new boosting algorithm［C］∥Proc of the 13th Iinternational Conference on Machine Learning,1996:148156.
［8］	Freund Y.An adaptive version of the boost by majority algorithm［J］.Machine Learning,2000,43(3):293318.
［9］	Keogh E,Pazzani M.Derivative dynamic time warping［C］∥Proc of the 1st International Conference on Data Mining,2001:1.
［10］	Chen L,Ng R.On the marriage of lpnorms and edit distance［C］∥ Proc of the 30th International Conference on Very Large Data Bases(VLDB’04),2004:792803.
［11］	Bergroth L,Hakonen H,Raita T.A survey of longest common subsequence algorithms［C］∥ Proc of the 7th International Symposium on String Processing and Information Retrieval(SPIRE 2000),2000:3948.
［12］	Salton G,Wong A,Yang C.A vector space model for automatic indexing［J］.Communications of the ACM,1975,18(11):613620.
［13］	Lin J, Li Y. Finding structural similarity in time series data using BagofPatterns representation［C］∥Proc of the 21st International Conference on Scientific and Statistical Database Management (SSDBM’2009),2009:461477.
［14］	Lin J,Khade R,Li Y.Rotationinvariant similarity in time series using BagofPatterns representation［J］.Journal of Intelligent Information Systems,2012,39(2):287315.
［15］	Jiang Yuan, Zhou Zhihua. A text classification method based on term frequency classifier ensemble［J］.Journal of Computer Research and Development,2006,43(10):16811687.(in Chinese)
［16］	Xie Yuancheng，Yang Jingyu.Using clustering to speed up AdaBoost and detecting noisy data［J］.Journal of Software,2010,21(8):18891897.(in Chinese)
［17］	Cao Ying,Miao Qiguang,Liu Jiachen,et al.Fisher consistent cost sensitive boosting algorithm［J］.Journal of Software,2013,24(11):25842596.(in Chinese)
［18］	Fu Zhongliang. A universal ensemble learning algorithm［J］.Journal of Computer Research and Development,2013,50(4):861872.(in Chinese)
［19］	Breiman L.Bagging predictors［J］.Machine Learning,1996,24(2):123140.
［20］	Freund Y,Schapire R.A decisiontheoretic generalization of online learning and an application to boosting［J］.Journal of Computer and System Sciences,1997,55(1):119139.
［21］	Keogh E, Zhu Q, Hu B, et al.The UCR time series classification/clustering homepage［DB/OL］.［20150706］.http://www.cs.ucr.edu/~eamonn/time_series_data/.
［22］	Hall M,Frank E,Holmes G.The WEKA data mining software:An update［J］.ACM SIGKDD Explorations,2009,11(1):1018.
［23］	Schaffer C.Overfitting avoidance as bias［J］.Machine Learning,1993,10(2):153178.
［24］	Cherkassky V,Mullier F.Guest editorial vapnikchervonenkis (VC) learning theory and its applications［J］.IEEE Transactions on Nerual Networks,1999,10(5):985987.
［25］	Reyzin L, Schapire R. How boosting the margin can also boost classifier complexity［C］∥ Proc of the 23rd International Conference on Machine Learning(ICML’06),2006:753760.
	附中文参考文献：
［2］	李海林,郭崇慧.时间序列数据挖掘中特征表示与相似性度量研究综述［J］.计算机应用研究,2013,30(5):12851291.
［15］	姜远,周志华.基于词频分类器集成的文本分类方法［J］.计算机研究与发展，2006,43(10):16811687.
［16］	谢元澄，杨静宇.使用聚类来加速AdaBoost并实现噪声数据探测［J］.软件学报,2010,21(8):18891897.
［17］	曹莹,苗启广,刘家辰,等.具有Fisher 一致性的代价敏感Boosting 算法［J］.软件学报，2013，24（11）：25842596.
［18］	付忠良.通用集成学习算法的构造［J］.计算机研究与发展,2013,50(4):861872.

[1]	柴燕涛，董德尊，张鹤颖，朱成阳，廖湘科. 基于SDN架构的高性能网络拥塞避免策略[J]. J4, 20160101, 38(01): 1-10.
[2]	谷文俊, 张晟恺, 邱晓梦, 李亚康, 宋伟. 基于双模态的小角散射图像结构表征技术研究[J]. 计算机工程与科学, 2023, 45(08): 1443-1452.
[3]	陈俊彦, 卢贤涛, 黄雪锋, 卢小烨, 廖岑卉珊. 基于Double-Bagging特征降维异质集成入侵检测[J]. 计算机工程与科学, 2023, 45(06): 1011-1019.
[4]	梁毅, 吐尔地·托合提, 艾斯卡尔·艾木都拉, . 多层CNN特征融合及多分类器混合预测的多模态虚假信息检测#br#[J]. 计算机工程与科学, 2023, 45(06): 1087-1096.
[5]	许浪, 李代伟, 张海清, 唐聃, 何磊, 于曦. 基于神经网络的医疗文本分类研究[J]. 计算机工程与科学, 2023, 45(06): 1116-1122.
[6]	刘南艳, 魏鸿飞, 马圣祥. 融合局部动态特征的面部表情识别[J]. 计算机工程与科学, 2023, 45(05): 849-858.
[7]	梅侠峰, 吴晓鸰, 黄泽民, 凌捷. 融合RoBERTa的多尺度语义协同专利文本分类模型[J]. 计算机工程与科学, 2023, 45(05): 903-910.
[8]	胡慧君, 杨雨烟, 易洋, 刘茂福. 基于细粒度信息感知BERT-EEP的情绪分类方法[J]. 计算机工程与科学, 2023, 45(04): 751-760.
[9]	赵亚丽, 余正涛, 郭军军, 高盛祥, 相艳, . 基于情感语义对抗的跨语言情感分类模型[J]. 计算机工程与科学, 2023, 45(02): 338-345.
[10]	苏赋, 罗海波. 改进Stacking集成学习的指纹识别算法[J]. 计算机工程与科学, 2022, 44(12): 2153-2161.
[11]	张睿萍, 宁芊, 雷印杰, 陈炳才. 基于改进Mask R-CNN的生活垃圾检测[J]. 计算机工程与科学, 2022, 44(11): 2003-2009.
[12]	王堃, 郑晨, 张立中, 陈志刚. 一种基于SARIMA-LSTM模型的电网主机负载预测方法[J]. 计算机工程与科学, 2022, 44(11): 2064-2070.
[13]	胡艳芳, 熊文, 高炜. 基于 Spark 平台的网络游戏用户流失预测方法[J]. 计算机工程与科学, 2022, 44(10): 1730-1737.
[14]	文武, 万玉辉, 文志云, . 基于正余弦算法的文本特征选择[J]. 计算机工程与科学, 2022, 44(08): 1467-1473.
[15]	赵春兰, 李屹, 何婷, 武刚, 王兵. 基于动态隶属度的模糊时间序列模型的水质预测研究[J]. 计算机工程与科学, 2022, 44(08): 1488-1496.