种基于频繁模式的时间序列分类框架

第 32 卷第 2 期 电 子 与 信 息 学 报 Vol.32No.2 2010年 2月 Journal of Electronics & Information Technology Feb. 2010 一种基于频繁模式的时间序列分类框架 万 里①③ 廖建新①② 朱晓民①② 倪 萍①③ ①(北京邮电大学网络与交换技术国家重点实验室 北京 100876) ②(东信北邮信息技术有限公司 北京 100191) ③(卡耐基梅隆大学 匹兹堡 15213) 摘 要：如何提取和选择时间序列的特征是时间序列分类领域两个重要的问题。该文提出 MNOE(Mining Non- Overlap Episode)算法计算时间序列中的非重叠频繁模式，并将其作为时间序列特征。基于这些非重叠频繁模式， 该文提出 EGMAMC(Episode Generated Mixed memory Aggregation Markov Chain)模型描述时间序列。根据似 然比检验原理，从理论上推导出频繁模式在时间序列中出现的次数和 EGMAMC 模型是否能显著描述时间序列之 间的关系；根据信息增益定义，选择能显著描述时间序列的频繁模式作为时间序列特征输入分类模型。在 UCI (University of California Irvine)公共数据集和实际智能楼宇数据集上的实验表明，选择频繁模式作为特征进行分类 的准确率、召回率和 F-Measure 均优于不选择频繁模式作为特征的分类结果。高效的计算和有效的选择非重叠频 繁模式作为时间序列特征有助于提高时间序列分类模型的各项评价指标。 关键词：时间序列分类；频繁模式挖掘；智能楼宇 中图分类号：TP393 文献标识码：A 文章编号：1009-5896(2010)02-0261-06 DOI: 10.3724/SP.J.1146.2009.00135 A Frequent Pattern Based Time Series Classification Framework Wan Li①③ Liao Jian-xin①② Zhu Xiao-min①② Ni Ping①③ ①(State Key Laboratory of Networking and Switching Technology Beijing University of Posts and Telecommunications, Beijing 100876, China) ②(EBUPT Information Technology Co., Ltd, Beijing 100191, China) ③(Carnegie Mellon University, Pittsburgh, US 15213, USA) Abstract: How to extract and select features from time series are two important topics in time series classification. In this paper, a MNOE (Mining Non-Overlap Episode) algorithm is presented to find non-overlap frequent patterns in time series and these non-overlap frequent patterns are considered as features of the time series. Based on these non-overlap episodes, an EGMAMC (Episode Generated Mixed memory Aggregation Markov Chain) model is presented to describe time series. According to the principle of likelihood ratio test, the connection between the support of episode and whether EGMAMC could describe the time series significantly is induced. Based on the definition of information gain, significant frequent patterns are selected as the features of time series for classification. The experiments on UCI (University of California Irvine) datasets and smart building datasets demonstrate that the classification model trained with selecting significant frequent patterns as features outperforms the one trained without selecting them on precision, recall and F-Measure. The time series classification models can be improved by efficiently extracting and effectively selecting non-overlap frequent patterns as features of time series. Key word word文档格式规范word作业纸小票打印word模板word简历模板免费word简历 s: Time series classification; Frequent pattern mining; Smart building 1 引言 给定一个数据样本集合，每个数据样本包括： 2009-02-02 收到，2009-09-03 改回 国 家 杰 出 青 年 科 学 基 金 (60525110) ， 国 家 973 计 划 项 目 (2007CB307100，2007CB307103)和电子信息产业发展基金项目(基 于 3G 的移动业务应用系统)资助课题 通信作者：万里 wanly@ebupt.com 一个输入时间序列 { ( ) | {1,2, , }}iX t t T= ∈x " 及其 离散的分类标签 sC ，其中， ( ) nt R∈x 是一个n维向 量，称作 t 时刻发生的事件， {1,2, , }sC S∈ " 。时间 序列分类的目标是预测新给出的时间序列 jX 的类 标签。时间序列分类技术在通信[1]、生物信息[2]、自 动控制[3]等领域已有广泛应用，但通常情况下时间序 列的长度不相等，即使所有待分类时间序列长度相 更多技术文章，论文请登录www.srvee.com 内容版权归作者所有 262 电 子 与 信 息 学 报 第 32 卷 等，不同序列相同时刻的事件不一定可比，直接套 用一般的分类算法，如SVM，k-近邻搜索[4]等，效果 不一定好。因此，特征提取和选择是研究时间序列 分类的重要课题。 本文主要研究如何从离散时间序列中提取并选 择频繁模式(frequent pattern)作为分类特征(连续 序列可用文献[5]提出的方法转换为离散序列)。现有 的基于频繁模式的分类算法 [6 8]− 大多利用频繁模式 生成基于关联规则的分类模型，文献[6]利用信息增 益建立了根据频繁模式支持度选择分类属性的框 架。这些方法存在两个问题：(1)没有考虑频繁模式 在时间序列中的分布。(2)没有系统的讨论如何根据 频繁模式在时间序列中出现的次数(支持度)选择其 作为分类属性。 本文主要贡献如下：提出一种基于非重叠频繁 模式(Non-overlap Episode)的时间序列分类框架： (1)提出非重叠频繁模式挖掘算法，基于此种模式提 出 EGMAMC 模型 (Episode Generated Mixed memory Aggregation Markov Chain)；(2)根据似然 比检验和信息增益原理，提出利用非重叠频繁模式 支持度进行特征选择的理论框架。(3)在公共数据集 和私有数据集上的实验表明，基于非重叠频繁模式 的时间序列分类方法的分类结果优于传统分类算 法。 2 基于非重叠频繁模式的 EGMAMC 2.1 非重叠频繁模式挖掘算法 文献[9]首次提出非重叠频繁模式的概念：某个 频繁模式在时间序列中出现两次，一个实例中的事 件不在另一个实例的两个事件之间出现。非重叠频 繁模式的支持度是非重叠实例在时间序列中出现的 最大次数。然而文献[9]并没给出直接计算非重叠频 繁模式的方法，因此本文提出 MNOE(Mining Non-Overlap Episode)算法直接计算非重叠频繁模 式。 MNOE 算法如下： 输入：(1)带时间戳的时间序列投影 head,P < body >的集合 1 2{ , , , }nS P P P= " (2) 当前迭代频繁模式长度： l (3) 频繁模式中两个连续事件间允许的最大 时间间隔：maxGap (4) 最小支持度： minSpt 输出：非重叠频繁模式集合 MNOE 是递归算法，具体步骤如图 1 所示 1 将 S 中的 iP 按 .headiP 中最后一个元素的时间戳进行升序 排列。 2 for (S 中每个投影 iP ){ 3 For .bodyiP 中每个元素e 4 If ( .time_stampe 减去 .headiP 中最后一个元素 的时间戳大于 maxGap) 5 结束循环 6 If ( e 是 .bodyiP 中属于|e|事件类型且时间戳最 小的元素且 .headiP 中第一个元素的时间戳大于 HashtableFE(|e|) 对应集合中最后一个元素的时间戳) 7 |e|的支持度增加 1。 8 iP ′=projection(e ， iP ) 9 .add( )iS P′ ′ 10 For HashtableFE 中每个键值|e| 11 if HashtableFE(|e|).size 大于 minSpt 12 调用函数 MNOE( S ′ ， 1l + ， max Gap ， minSpt ) 图 1 MNOE 算法步骤 | e | 表 示 一 个 事 件 类 型 ， > | e |,e =< time_stamp 表示 | e | 类型事件在时间序列中 time_stamp 时刻出现的一个实例。 .headiP 表示当 前迭代步骤所计算频繁模式的前缀， .headiP 表示该 前缀的一个实例， .bodyiP 表示 .headiP 中最后一个 时刻事件以后到时间序列结束时刻的子时间序列。 算法每次迭代的第 1 步对 1 2{ , , , }nS P P P= " 的排序 保证所得非重叠频繁模式在时间序列中出现实例达 到最大值。HashtableF 是以|e|为键值的哈希表， HashtableFE (|e|)为存放现有前缀( .headiP )后紧跟 事件|e|的实例的集合。projection(e )中的投影规则： 新的投影为 iP ′， .head .headi iP P e′ = + ， .bodyiP ′ 为 .bodyiP 中所有时间戳大于 e 的时间戳的事件实例。 S 的初始值即给定的整个时间序列， l 初始值为 0。 2.2 EGMAMC模型 基于一个频繁模式α可定义一个 EGMAMC 模 型。EGMAMC 模型结合 Aggregate Markov(AM) 和 Mixed Memory Markov(MMM)模型，将状态空 间分为 K 类，并假设当前时刻状态在一定概率下受 l 个时刻前状态影响： 设时间序列 1 2{ , , , , , }t TX x x x x= " " ， {1,t ∈ , }T" ， 1 2{ , , , }t nx E e e e∈ = " 为当前时刻状态，E 为 状态空间。本文将 EGMAMC 模型状态空间划分为 两类：频繁模式状态( eK )和噪声状态( nK )。频繁模 式状态代表时间序列中在频繁模式 1 2{ , ,e eS Sα = 1, , }N Ne eS S −" ( ieS 表示在α中第 i 个位置出现的事件) 内出现的事件；噪声状态则代表不在α内出现的事 件。若规定状态间相互影响的最大时间间隔为L ， 更多技术文章，论文请登录www.srvee.com 内容版权归作者所有 第 2 期 万 里等：一种基于频繁模式的时间序列分类框架 263 则基于α的 EGMAMC 模型 αΛ 为 1 1 1 1 1 1 ( | , , ) ( | , , ) ( | ) ( | , , ) ( | , ) ( | ) t t t L L l t t L t t l l L K l t t L t t l t l l k P x x x P l x x P x x P l x x P x k x P k x − − − − − = − − − − = = = = ∑ ∑ ∑ " " " (1) 1( | , , )t t LP l x x− −" ， ( | , )t t lP x k x − ， ( | )l t lP k x − 定义如下： t l ex K−∃ ∈ 且 , nt ll l x K′−′∀ < ∈ 时， (P l 1| ,tx − , ) 1t Lx − =" 否则 1( 1 | , ,t n t LP l x K x− −= ∈ " ) 1nK∈ = 。 ( | )l t lP k x − 表示当前时刻状态类型受 l 个时刻前状态影响，令 ( | )l n t lP k K x η−= = 。当 ek K= 时，如果 1nt l ex S −− = ，则 ( | ,nt e eP x S K= )=1t lx − ， ( nt eP x S≠ | , ) 0e t lK x − = 。当 nk K= 时， ( | , ) 1/t n t lP x K x M− = (M 为时间序列中所有事件类 型个数)。 令当前时刻前L 个时刻状态均为噪声状态的概 率，即 1( , , )t n t L nP x K x K λ− −∈ ∈ =" 。 综上，模型 αΛ (式(1))生成给定时间序列o 的概 率为 ( ) ( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) (1 ) ( | ) ( (1 )) ((1 )(1 )) 1 (1 ) (1 ) 1 nn en e n n eq o q on n e e n e n e e eq o q o q o q on n e e n e q oq o q o q o q o q o P o M M M M α λ ηλη λ η λλ η λ λ η η η λ + ′ ′+ + + ′ + ⎛ ⎞⎛ ⎞ − ⎟⎟ ⎜⎜Λ = − ⎟⎟ ⎜⎜ ⎟ ⎟⎜ ⎜⎝ ⎠ ⎝ ⎠ ⎛ ⎞⎟⎜⋅ − − = ⎟⎜ ⎟⎜⎝ ⎠− ⎛ ⎞⎛ ⎞− − ⎟⎜⎟⎜ ⎟⋅ ⎟ ⎜⎜ ⎟⎟ ⎜⎜ ⎟⎜⎝ ⎠ ⎝ ⎠ = ( )T T ( )(1 ) (1 ) (1 ) (1 ) (1 ) eT e e e q o q o M M M M λ λ λ λ η η λ η λ λ η η η − ⎛ ⎞⎛ ⎞⎛ ⎞ − − ⎟⎜⎟⎟ ⎜⎜ ⎟⎟ ⎜⎟ ⎜⎜ ⎟⎟ ⎟⎜ ⎜⎜ ⎟⎜⎝ ⎠ ⎝ ⎠− ⎝ ⎠ ⎛ ⎞ ⎛ ⎞− −⎟⎜ ⎟⎜⎟ ⎟= ⎜ ⎜⎟ ⎟⎜ ⎜ ⎟⎟ ⎜⎟⎜ ⎝ ⎠⎝ ⎠ (2) 其中 | |T o= 表示时间序列长度， ( )nnq o 为噪声状态转 移到噪声状态的次数， ( )enq o 为噪声状态转移到α第 1 个事件状态( 1eS )的次数， ( )neq o 为频繁模式状态转 移到噪声状态的次数， ( )eeq o′ 为频繁模式状态转移到 “部分”频繁模式状态的次数( 1eS 除外)， ( )eeq o 为频 繁模式状态在o 出现的次数，且 [ ( ) ( )]n en nq o q oλ = + /T 。若 α在o 中出现次数为 fα ，则有 ( )eeNf q oα ≤ ( 1)N fα< + 。因为如果 ( )eeq o 出现次数超过 (N fα 1)+ ，则得到α出现次数为 1fα + ，和前提条件矛盾。 通常情况下N T� ，所以 ( )eeq o Nfα= 。 T(1 )(1 ) (1 ) ( | ) Nf M P o M αλ λ α λ λ η η η −⎛ ⎞ ⎛ ⎞− −⎟⎜ ⎟⎜⎟ ⎟Λ = ⎜ ⎜⎟ ⎟⎜ ⎜ ⎟⎟ ⎜⎟⎜ ⎝ ⎠⎝ ⎠ (3) 在式(3)中，若 ,λ η 一定， [ (1 )/ ] 1M η η− > ，其中 /( 1)M Mη < + ，则 fα 越大， ( | )P o αΛ 越大。当 1/2λ = ， (1 )(1 )λ λλ λ −− 取得最小值1/2，其它参数一 定时，在区间 ( )0,1/2 上 ( | )P o αΛ 与λ负相关。 η越 大，α出现的概率越小，λ越大α的分布越稀疏。 2.3 显著频繁模式 本文用似然比检验衡量 EGMAMC 模型 αΛ 是 否比独立同分布模型更适合作为给定时间序列生成 模型。如果 αΛ 适合生成时间序列o 的假设成立，称 α为o 中的显著频繁模式。 假设 1H ：时间序列o 由 αΛ 生成； 0H ：时间序 列o 由独立同分布模型 iidΛ 生成。似然比检验将拒绝 假设 0H (接受 1H )，如果 1 0 ( | ) ( ) 0 ( | ) P o H L o P o H γ= > > ( Ι类误差决定 γ 大小) (4) 由式(3)，当 /( 1) 1M M η+ < < 或1/2 1λ< < 时，o 中噪声占主要比例， 1H 和 0H 等价。以下讨论均假 设 /( 1)M Mη < + 且 0 1/2λ< < 。 因为 o 在假设 0H 下的似然值为 0( | )P o H = ( )T1/M ，所以由式(4)， 1 0( | ) ( | )P o H P o Hγ γ′> = 。 由式(2)， 1( | )P o H γ ′> 等价于 ( )eeq o Γ> ，则式(4) 等价于 ( ) ( )eeL o q o Γ′ = > ( Ι类误差决定Γ 大小) (5) Ι类误差 faP 是似然比 ( )L o Γ′ > 时接受 0H 的概 率 ( )Tfa 0( ( ) ; ) 1/ ( )P P L o H M QΓ Γ′= > = ，其中 ( )Q Γ | { ; ( ) } |eeo q o Γ= > 表示使得似然比 ( )L o Γ′ > 且长度 为 T 的时间序列个数，且 ( )Q Γ ≤ k TT k C M λ Γ> ∑ (1 )( 1) T kM λ− −⋅ − ，因为长度为 T 的时间序列中，选择 k 个时刻放置频繁模式状态组合数为 kTC ，Tλ 个状态 由其前一时刻噪声状态决定，共有 TM λ 种组合，剩 余状态由离其最近的频繁模式状态决定，共有 (1 )( 1) T kM λ− −− 种组合。因此 ( ) min min T (1 ) fa ( ) ( ) 1/ ( 1) 1 1 1 1 1 1 1 1 11 1 k T T k T k T k T k k k T k T k P M C M M M M C M M T M M M T M M c λ λ Γ λ Γ Γ λ Γ Γ Φ Γ Φ − − > ≤ − ≤ ≤ ≤ − ⎛ ⎞⎟⎜< − ⎟⎜ ⎟⎜⎝ ⎠− ⎛ ⎞ ⎛ ⎞⎟ ⎟⎜ ⎜⋅ − ⎟ ⎟⎜ ⎜⎟ ⎟⎜ ⎜⎝ ⎠ ⎝ ⎠ ⎛ ⎞⎟⎜ ⎟⎜ − ⎟⎜ ⎟⎛ ⎞ ⎜ ⎟⎟⎜ ⎜ ⎟≈ − ⎟⎜ ⎜ ⎟⎟⎜⎝ ⎠ ⎟⎜− ⎛ ⎞⎛ ⎞⎟⎜ ⎟ ⎟⎟⎜ ⎜⎜ −⎟ ⎟⎟⎜ ⎜⎟ ⎟⎜ ⎜ ⎜ ⎟⎜ ⎝ ⎠⎝ ⎠⎝ ⎠ = − ∑ ∑ 1 11 T M T M M ⎛ ⎞⎟⎜ ⎟⎜ − ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎟⎜ ⎛ ⎞⎛ ⎞⎟⎜ ⎟ ⎟⎟⎜ ⎜⎜ −⎟ ⎟⎟⎜ ⎜⎟ ⎟⎜ ⎜ ⎜ ⎟⎜ ⎝ ⎠⎝ ⎠⎝ ⎠ 更多技术文章，论文请登录www.srvee.com 内容版权归作者所有 264 电 子 与 信 息 学 报 第 32 卷 其中 ()Φ ⋅ 为正态随机变量累计分布函数，由中心极 限定理，当 T 足够大时上式第 3 步近似推导成立。 min ( ) 1 T kMc M λ Γ≤⎛ ⎞⎟⎜= ⎟⎜ ⎟⎜⎝ ⎠− 为常数， min( )kλ Γ≤ 表示在所讨 论的k Γ≤ 时间序列集合中λ的最小值。给定 Ι类误 差上限 ε ( 0.5ε = )，则 11T T M M M Γ ⎛ ⎞⎛ ⎞⎟ ⎟⎜ ⎜= + −⎟ ⎟⎜ ⎜⎟ ⎟⎜ ⎜⎝ ⎠⎝ ⎠ 1 1 c εΦ− ⎛ − ⎞⎟⎜⋅ ⎟⎜ ⎟⎜⎝ ⎠，当 T 足够大时Γ 近似等于 /T M ，又因 为 ( )eeq o Nfα= ，根据式(5)可得 ( ) /eeq o Nf T Mα= > 时 拒绝假设 0H 。综上，当 /( )f T MNα > ，0 1/2λ< < 时，α为o 中显著频繁模式。 3 基于支持度的特征选择 给定数据集，属性集合X ，类别集合C ，信息 增益 IG( | )C X 越大，属性集合X 对类别集合C 的区 分能力越大[6]： IG( | ) ( ) ( | )C X H C H C X= − (6) 其中 ( )H C 是数据集中样本所属类别概率的信息熵， ( | )H C X 是条件信息熵，数据集给定则 ( )H C 一定。 由式(6)可知，当 ( | )H C X 达到最小下界 ( | )lbH C X 时，IG( | )C X 达到最大上界 IG( | )ubC X ，即 IG (ub C | ) ( ) ( | )lbX H C H C X= − 。不妨设 {0,1}X ∈ ，C = {0,1} 。属性 x 在数据集中出现的概率 ( 1)P x = = ( )h f ，类别为 1 的样本出现的概率 ( 1)P c p= = ，属 于类别 1 具有属性 x 的样本的概率 ( 1 | 1)P c x= = q= 。当x 为频繁模式时， ( )h f 表示x 在时间序列样 本集合中为显著模式的概率， f 表示 x 在整个数据 集中出现次数 1)。则 2 {0,1} {0,1} 2 2 2 2 ( | ) ( ) ( | ) log ( | ) ( ) log ( )(1 )log (1 ) ( ) ( ( ) ) log ( ( ) 1 ( ) (1 ) ( )(1 ) (1 ) (1 )) log 1 ( ) x c H C X P x P c x P c x h f q q h f q q p h f q h f q p h f h f p h f q q p h f ∈ ∈ = − = − − − − −+ − +− − − −⋅ − − − − ∑ ∑ 若给定数据集，上式中 p为常数，若 ( )h f p≤ ， 当 0q = 或1时 ( | )H C X 达到下界；如果 ( )h f p≥ ， 当 ( )q p h f= 或 1 (1 ) ( )p h f− − 时 ( | )H C X 达到下 界。 ( )h f p≤ 和 ( )h f p≥ 对称，当 ( )h f p≤ 时 0q = 和 1q = 也对称，因此只列出 ( )h f p≤ ， 1q = 时 ( | )H C X 下界取值的讨论： 1) f 和 fα 的含义不同，f 表示频繁模式 α 在数据集中“所有”时间序 列样本中出现的次数； fα 表示 α 在“一个”时间序列样本 o 中出现 的次数。 1 2 2 ( ) ( ) ( | ) ( ( ) 1) log 1 ( ) 1 ( ) 1 1 log , 1 ( ) 1 ( ) lb q p h f p h f H C X h f h f h f p p h f h f = ⎛ ⎞− − ⎟⎜ ⎟= − ⎜ ⎟⎜ ⎟⎜ − −⎝ ⎠ − −+ − − 1 2 2 ( | ) ( ) 1 1 ( ) log 1 ( ) 1 ( ) 1 ( ) ( ) ( ) log 1 ( ) lb qH C X f p h f p ph f h f h f h f p h f h f h f =∂ ∂ ⎛ ⎞− − − ⎟⎜′ ⎟= − −⎜ ⎟⎜ ⎟⎜ − − −⎝ ⎠ −′= − (7) 因 为 2 2( )log log 1 01 ( ) p h f h f − ≤ =− ， 所 以 ( ) 0h f′ ≥ , 1( | ) 0lb q H C X f =∂ ≤∂ ，反之亦然。通常情况下λ一定， ( )h f 一定单调递增。所以，当 ( )h f p≤ 时 f 增加 (lbH C | )X 单调递减，IG ( | )ub C X 增加。基于频繁模 式的时间序列分类框架如下： 输入：时间序列数据集，信息增益阈值 0IG 输出：分类模型 (1)由式(7)计算使 0IG ( ( )) IGub h f ≤ 成立的 ( )h f 的最大值 *( )h f (2)循环： (a)数据集中每个时间序列样本 (b)计算每个样本中的非重叠显著频繁模式(支 持度大于 min /( )S T MN= ，且 0 1/2λ< < )。 (c)记录每个频繁模式在时间序列样本集合中 为显著模式的次数hα 。 (3)结束循环 (4)选择 *( )h h f nα > × 的频繁模式作为时间序 列属性(n 为时间序列样本个数)。 (5)将时间序列中各时刻事件作为样本的属性 和频繁模式属性一起用于训练分类模型。 (6)输出训练后的分类模型 采用文献[10]的方法选择信息增益阈值 0IG 。分 类模型采用 C45，SVM 等传统模型。 4 实验 实验采用准确率(precision)、召回率(recall)和 F-Measure 评价分类模型，采用 SAX 2)方法[5]离散化 连续时间序列，C453)模型作为分类模型，选择时间 序列样本中事件和频繁模式作为属性。 4.1 UCI时间序列数据集实验 “synthetic control signal”(简称“scs”)和 2)http://www.cs.ucr.edu/~eamonn/SAX.htm 3)http://www.cs.waikato.ac.nz/ml/weka/ 更多技术文章，论文请登录www.srvee.com 内容版权归作者所有 第 2 期 万 里等：一种基于频繁模式的时间序列分类框架 265 “Japanese vowel”(简称“jv”)是 UCI 数据库中公 共数据集。“scs”数据集包括 6 种控制信号，每种 信号有 100 个长度为 60 的样本，随机抽取 10%的样 本作为测试集，其余作为训练集。“jv”数据集包括 9 名男性发/ae/音的记录，每条记录长度在 7-29 帧 之间，数据集已划分训练集和测试集，共有 640 个 样本。 从表 1 看出，在各数据集上的实验均表明，选 择频繁模式作为时间序列属性对 3 种指标均有明显 提升。只选择显著频繁模式作为属性分类性能优于 选择所有频繁模式作为属性的分类性能，可见研究 频繁模式的显著性是有必要的。 4.2 智能楼宇传感器采集数据实验 本文将 MNOE 算法和分类框架用于实现某智 能楼宇 WSAN(Wireless Sensor Ad-hoc Network) 数据分析系统 EventMiner。WSAN 采集 6 种类型 事件，每类事件有 3 种取值，采集周期为 1 min 。 本文在 2008 年 6 月到 11 月的数据上进行实验，数 据集中每条记录包括时间戳和在该时刻 6 个传感器 节点所采集的事件。本文用长度为 61 的滑动窗口取 滑动步长为 1，分别将 6-8 月和 9-11 月的数据分为 两组时间序列集合(Dataset1 和 Dataset2)，其中每 条记录的前 60 个时刻的事件作为时间序列样本，第 61 个事件作为分类标志。分别将 Dataset1 和 Dataset2 中所占比例小于 3%的分类标志和其对应 的样本作为噪声删除，然后取 80%的样本作为训练 集，20%的样本作为测试集(如表 2 所示)。 宏平均准确率、召回率和 F-Measure 示于表 3。 由表 3 看出，在实际数据集中，选择显著频繁 模式作为时间序列属性进行分类在准确率、召回率 和 F-Measure 上任具有较大优势。综上，本文所提 出的分类框架在公共数据集和实际应用数据集上均 有很好表现，显著频繁模式的研究是必要的，本文 提出的分类框架具有良好的鲁棒性，简单的选择所 有频繁模式作为属性进行分类并不一定能提升分类 性能。 5 结束语 本文提出一种基于非重叠频繁模式的时间序列 分类框架。框架在特征提取阶段由 MNOE 算法提取 非重叠频繁模式作为待选特征。在特征选择阶段， 利用 EGMAMC 模型选择出显著频繁模式，并根据 信息增益定义选择信息增益大于给定阈值的显著频 繁模式作为时间序列特征进行分类。本文从理论上 推导出频繁模式在时间序列中出现次数与分布和其 是否显著以及是否被选为时间序列特征之间的关 系，因此，在实际分类过程中不用进行似然比检验， 简化了分类过程。根据 EGMAMC 的定义可知模型 是稳定的，从实验中也得到证明。 实验证明，研究显著频繁模式是必要的，简单 的选择所有频繁模式作为时间序列特征并不一定能 提高分类模型性能。下一步工作将集中在研究时间 序列中事件间空间-时序(spatial-temporal)模式对 时间序列分类模型性能的影响。 表 1 宏平均准确率、召回率和 F-Measure 未包含频繁模式 所有频繁模式 显著频繁模式 数据集 准确率 召回率 F-Measure 准确率 召回率 F-Measure 准确率 召回率 F-Measure Scs 0.714 0.5 0.588 0.889 0.8 0.842 0.909 0.852 0.88 Jv 0.556 0.5 0.526 0.667 0.6 0.632 0.636 0.7 0.667 表 2 数据集 数据集 记录数 月份 训练集大小 测试集大小 分类数 Dataset1 131298 6-8 月 101887 25471 5 Dataset2 131072 9-11 月 101711 25427 5 表 3 宏平均准确率、召回率和 F-Measure 未包含频繁模式 所有频繁模式 显著频繁模式 数据集 准确率 召回率 F-Measure 准确率 召回率 F-Measure 准确率 召回率 F-Measure Dataset1 0.667 0.6 0.632 0.6 0.6 0.6 0.571 0.8 0.667 Dataset2 0.444 0.4 0.421 0.5 0.3 0.375 0.571 0.4 0.471 更多技术文章，论文请登录www.srvee.com 内容版权归作者所有 266 电 子 与 信 息 学 报 第 32 卷 参 考 文 献 [1] Boukerche. Handbook of Algorithms for Qireless Networking and Mobile Computing. Chapman & Hall/CRC, 2005. [2] Aach J and Church G. Aligning gene expression time series with time warping algorithms. Bioinformatics, 2001, 17(6), 495-508. [3] Laxman S. Stream prediction using a generative model based on frequent episodes in event sequences. Proceeding of Knowledge Discovery and Data Mining Conference 2008, Las Vegas, Nevada, USA,30 Jul. 2008: 453-461. [4] Vladimir Vapnik. The Nature of Statistical Learning Theory. New York: Springer Verlag, 1999, Chapter 4. [5] Lin J, Keogh E, Lonardi S, and Chiu B. A symbolic representation of time series with implications for streaming algorithms. Proceedings of the 8th ACM SIGMOD workshop on research issues in data mining and knowledge discovery, San Diego, California, 9 Jun. 2003: 2-11. [6] Cheng H, Yan X, Han J, and Hsu C W. Discriminative frequent pattern analysis for effective classification. Proceeding of International Conference on Data Engineering 2007, Istanbul, 17 April, 2007: 716-725. [7] Liu B, Hsu W, and Ma Y. Integrating classification and association rule mining. Proceedings of the 7th International Workshop on New Directions in Rough Sets, Data Mining, and Granular-Soft Computing, London, UK, Springer- Verlag 1999: 443-447. [8] Patel D, Hsu W, and Lee M L. Mining relationships among interval-based events for classification, Proceeding of International Conference on Management of Data / Principles of Database Systems, Vancouver, Canada, 10 Jun. 2008: 393-404. [9] Laxman S, Sastry P S, and Unnikrishnan K P. Discovering frequent episodes and learning Hidden Markov Models: A formal connection. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(11): 1505–1517. [10] Yang Y and Pedersen J O. A comparative study on feature selection in text categorization. Proceeding of International Conference on Machine Learning, San Francisco, USA, 8 Jul. 1997: 412-420. 万 里： 男，1981年生，博士生，卡耐基梅隆大学访问学者，研 究方向为网络智能化、人工智能、信号处理. 廖建新： 男，1965 年生，教授，博士生导师，主要研究方向为网 络智能化. 朱晓民： 男，1974 年生，副教授、硕士生导师，研究方向为智能 网、下一代业务网络、3G 核心网、 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 工程等. 倪 萍： 男，1978 年生，博士生，卡耐基梅隆大学访问学者，研 究方向为网络智能化、人工智能、信号处理. 更多技术文章，论文请登录www.srvee.com 内容版权归作者所有