第３８卷 第７期
２０１５年７月计 算 机 学 报ＣＨＩＮESE ＪＯＵＲＮＡＬＯF ＣＯMPＵＴEＲS Ｖｏｌ．３８Ｎｏ．７Ｊｕｌｙ２０１５
收稿日期：２０１３-１０-２０；最终修改稿收到日期：２０１４-１２-０９．本课题得到中央高校基本科研基金（２０１５ＹＪS０４９）资助．原继东，男，１９８９年生，博士研究生，主要研究方向为数据挖掘和模式识别．E -ｍａｉｌ：１２１１２０７８＠ｂｊｔｕ．ｅｄｕ．ｃｎ．王志海，男，１９６３年生，博士，教授，博士生导师，主要研究领域为数据挖掘和机器学习．韩 萌，女，１９８２年生，博士研究生，讲师，主要研究方向为数据挖掘和机器学习．游 洋，男，１９９１年生，硕士研究生，主要研究方向为下一代互联网技术与数据处理方法．基于逻辑sha p elets 转换的时间序列分类算法
原继东１），２） 王志海１），２） 韩萌１），２） 游洋３）
１）（北京交通大学计算机与信息技术学院 北京 １０００４４）
２）（交通数据分析与挖掘北京市重点实验室
北京 １０００４４）３）（西北大学电子工程与计算机系 埃文斯顿美国６０２０１）
摘 要 时间序列ｓｈａｐｅｌｅｔｓ是序列之中最具有辨别性的子序列．解决时间序列分类问题的有效途径之一是通过
ｓｈａｐｅｌｅｔｓ转换技术，
将其发现与分类器的构建相分离，其主要优点是优化了ｓｈａｐｅｌｅｔｓ的选择过程并能够灵活应用不同的分类策略．
但此方法也存在不足，仅仅简单地应用这些ｓｈａｐｅｌｅｔｓ而忽略它们之间的逻辑组合关系，有可能降低分类的效果；
另外，离线式的发现ｓｈａｐｅｌｅｔｓ的过程是相当耗时的．文中针对后一个问题，采用了一种基于智能缓存的计算重用技术，
将发现ｓｈａｐｅｌｅｔｓ的时间复杂度降低了一个数量级．在此基础上，作者提出了一种基于合取或析取的逻辑ｓｈａｐｅｌｅｔｓ转换方法，并通过在多个经典的基准数据集上测试，表明了该方法能够在提升分类准确性的同时保持ｓｈａｐｅｌｅｔｓ所具有的解释力．
关键词 时间序列；分类；ｓｈａｐｅｌｅｔｓ；
逻辑ｓｈａｐｅｌｅｔｓ中图法分类号ＴP３１１ DOI 号１０．１１８９７／SP．Ｊ．１０１６．２０１５．０１４４８
A Lo g ical Sha p elets Transformation for Time Series Classification
ＹＵＡＮＪｉ-Ｄｏｎｇ１
），２） ＷＡＮＧＺｈｉ-Ｈａｉ１），２） ＨＡＮMｅｎｇ１），２） ＹＯＵＹａｎｇ３）１）（
School o f Com p uter and In f ormation Technolo gy ，Bei j in g J iaoton g Universit y ，Bei j in g １０００４４）
２）（Bei j in g Ｋe y Laborator y o f Tra ff ic Data Anal y sis and Minin g ，Bei j in g １０００４４）３）（De p artment o f Electrical En g ineerin g and Com p uter Science ，Northwestern Universit y ，Evanston ６０２０１，USA ）Abstract Ｔｈｅｓｈａｐｅｌｅｔｓｏｆｔｉｍｅｓｅｒｉｅｓａｒｅｓｕｂｓｅｑｕｅｎｃｅｓｏｆｔｉｍｅｓｅｒｉｅｓｔｈａｔａｒｅｒｅｐｒｅｓｅｎｔａｔｉｖｅｏｆｃｌａｓｓｍｅｍｂｅｒｓ．Ｏｎｅｏｆｔｈｅｍｏｓｔｐｒｏｍｉｓｉｎｇａｐｐｒｏａｃｈｅｓｔｏｓｏｌｖｅｐｒｏｂｌｅｍｓｏｆｔｉｍｅｓｅｒｉｅｓｃｌａｓｓｉｆｉｃａｔｉｏｎｉｓｔｏｓｅｐａｒａｔｅｔｈｅｐｒｏｃｅｓｓｏｆｆｉｎｄｉｎｇｓｈａｐｅｌｅｔｓｆｒｏｍｃｌａｓｓｉｆｉｃａｔｉｏｎａｌｇｏｒｉｔｈｍｓｂｙａｐｐｌｙｉｎｇａｓｈａｐｅｌｅｔｔｒａｎｓｆｏｒｍａｔｉｏｎ．Ｔｈｅｍａｉｎａｄｖａｎｔａｇｅｓｏｆｔｈｉｓａｐｐｒｏａｃｈａｒｅｔｈａｔｉｔｃｏｕｌｄｏｐｔｉｍｉｚｅｔｈｅｐｒｏｃｅｓｓｏｆｓｈａｐｅｌｅｔｓｓｅｌｅｃｔｉｏｎ，ａｎｄｔｈｅｎｖａｒｉｏｕｓｃｌａｓｓｉｆｉｃａｔｉｏｎｓｔｒａｔｅｇｉｅｓｍｉｇｈｔｂｅａｄｏｐｔｅｄ．Ｈｏｗｅｖｅｒ，ｔｈｅｒｅａｌｓｏｅｘｉｓｔｓｏｍｅｌｉｍｉｔａｔｉｏｎｓｉｎｔｈｅｐｒｏｃｅｓｓ．Fｉｒｓｔ，ｏｎｌｙｄｉｒｅｃｔｌｙｅｍｐｌｏｙｉｎｇｔｈｅｓｅｓｈａｐｅｌｅｔｓ，ｗｈｉｌｅｉｇｎｏｒｉｎｇｌｏｇｉｃａｌｒｅｌａｔｉｏｎｓｈｉｐｂｅｔｗｅｅｎｔｈｅｍ，ｔｈｅｃｌａｓｓｉｆｉｃａｔｉｏｎａｃｃｕｒａｃｙｍａｙｂｅｃｕｔｄｏｗｎ．Sｅｃｏｎｄ，ｔｈｅｐｒｏｃｅｓｓｉｓｍｕｃｈｍｏｒｅｔｉｍｅｃｏｎｓｕｍｉｎｇｓｉｇｎｉｆｉｃａｎｔｌｙ，ｅｖｅｎｔｈｏｕｇｈｓｈａｐｅｌｅｔｓａｒｅｃｏｍｐｕｔｅｄｏｆｆｌｉｎｅ．Ｉｎｔｈｉｓｐａｐｅｒ，ｔｈｅｌａｔｔｅｒｐｒｏｂｌｅｍｉｓａｄｄｒｅｓｓｅｄｂｙｕｓｉｎｇａｎｉｎｔｅｌｌｉｇｅｎｔｃａｃｈｉｎｇｂａｓｅｄａｎｄｒｅｕｓａｂｌｅｓｋｉｌｌ，ｗｈｉｃｈｒｅｄｕｃｅｓｔｈｅｔｉｍｅｃｏｍｐｌｅｘｉｔｙｏｆｆｉｎｄｉｎｇｓｈａｐｅｌｅｔｓｂｙａｎｏｒｄｅｒｏｆｍａｇｎｉｔｕｄｅ．Ｏｎｔｈｉｓｂａｓｉｓ，ａｎｏｖｅｌｔｒａｎｓｆｏｒｍａｔｉｏｎｔｈａｔｉｓｂａｓｅｄｏｎｃｏｎｊｕｎｃｔｉｖｅｏｒｄｉｓｊｕｎｃｔｉｖｅｏｆｓｈａｐｅｌｅｔｓｉｓｐｒｏｐｏｓｅｄ．Eｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｈａｖｅｓｈｏｗｎｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｌｏｇｉｃａｌｓｈａｐｅｌｅｔｓｔｒａｎｓｆｏｒｍａｔｉｏｎｏｎｃｌａｓｓｉｃｂｅｎｃｈｍａｒｋｄａｔａｓｅｔｓｕｓｅｄｆｏｒｔｈｅｓｅｐｒｏｂｌｅｍｓ，ｗｈｉｃｈｃａｎｉｍｐｒｏｖｅｃｌａｓｓｉｆｉｃａｔｉｏｎａｃｃｕｒａｃｙ，ａｎｄｗｈｉｌｓｔｒｅｔａｉｎｉｎｇｔｈｅｉｒｉｎｔｅｒｐｒｅｔａｂｉｌｉｔｙ．
Ke y words ｔｉｍｅｓｅｒｉｅｓ；ｃｌａｓｓｉｆｉｃａｔｉｏｎ；ｓｈａｐｅｌｅｔｓ；ｌｏｇｉｃａｌｓｈａｐｅｌｅｔｓ