精华内容
下载资源
问答
  • Time Series Shapelets A New Primitive for Data Mining shapelets论文2009
  • shapelets是描述时间序列局部特征的子序列,它能最大程度对不同类别进行区分。从它的发明至今一直吸引着研究者的关注,但是由于过高的时间复杂度阻碍了它被广泛应用。一种快速查找多个shapelets的方法(Non-Similar ...
  • 时间序列:Shapelets

    千次阅读 多人点赞 2019-09-06 15:39:14
    Time Series Shapelets:A New Primitive for Data Mining 本篇论文发表于2009年,首次提出了shapelets这一概念。 摘要 shapelets是时间序列的一个子序列,可以称作最大区分子序列。这里的最大指的是这个子序列的...

    Time Series Shapelets:A New Primitive for Data Mining

    本篇论文发表于2009年,首次提出了shapelets这一概念。

    摘要

    shapelets是时间序列的一个子序列,可以称作最大区分子序列。这里的最大指的是这个子序列的区分能力最大。常用的近邻算法是一种全局性的方法,因为它需要用到全部的数据集,而shapelets属于一种局部模式,它使用具有区分能力的子序列来进行分类与聚类。它有两个优点:(1)局部模式;(2)具有很强的可解释性。

    1、引言

    近邻算法有两个弱点(1)时间空间开销大;(2)可解释性差,具体来说就是不能告诉我们为什么一个特定的对象被分配给一个特定的类。shapelets可以减轻这两个弱点。
    论文中举了一个形象的例子来让读者直观的感受一下什么是shapelets。
    第一排树叶是荨麻草,第二排树叶是马鞭草,有些叶子被昆虫咬伤
    上图中第一排树叶是荨麻草,第二排树叶是马鞭草也叫“假荨麻”,有些叶子被昆虫咬伤,这两种植物的叶子非常相似。现在要用一个分类器来区分这两种植物。那么应该选用什么特征?因为叶子的大小的颜色几乎是相同的,最好的选择就是基于叶子的形状。但是叶子整体上的形状差异是比较小的,而且由于昆虫咬伤以及其他变形会混淆任何基于全局形状的测量。尝试使用“局部形状”是一个比较好的想法。
    在这里插入图片描述
    如图,形状可以转化为一维的时间序列表示。这种转化后的时间序列可以用来分类、聚类等一系列数据挖掘任务。但是直接使用全部数据的欧式距离或DTW距离的近邻分类器效果并没有明显优于随机猜测(基本上没分出来)。原因就是数据中的噪声(比如本例中的昆虫咬伤)足以掩盖掉形状上的细微差异。但是可以不比较全部的数据,之比较数据中有差异的一小部分,这一个“小部分”便是本文提出的shapelets,体现在上图中就是红色的那一段子序列。
    在这里插入图片描述
    如图上图所示,通过找到的“两个类之间最好的区分子序列”,即shapelets,我们可以发现,两个物种之间最大的区别在于茎与叶子的连接角度,荨麻草大约为90度,假荨麻要比90度大得多(这里可以体现shapelets的可解释性)。找到shapelets并且计算它到数据集中所有实例最近匹配的距离后,就可以构建一个简单的决策树分类器。
    在这里插入图片描述
    如上图所示,红色的那条线是提取出来的shapelets,分类过程就是计算数据集中每个实例到shapelets的距离,如果距离小于5.1它就被分为马鞭草,否则就是荨麻草。那么问题来了,分类阈值5.1哪来的?后面会讲这个问题,目前先放一放。

    到目前为止读者会发现这种分类方法潜在的优点:
    (1)shapelets能够提供可解释的结果,帮助分析人员更好的理解数据。这是其他机器学习和时序分类算法办不到的。
    (2)shapelets有更强的鲁棒性/准确性。因为它是一种“局部特征”,比起那些“全局特征”的分类算法,它的抗噪能力更强。
    (3)shapelets比现有的分类方法更快。

    2、相关工作和背景

    符号表

    在这里插入图片描述
    比较简单的概念就不详细写了。

    定义1:时间序列

    m个实值的有序集。

    定义2:子序列

    定义3:滑动窗口

    定义4:时间序列之间的距离

    使用某种距离计算方法返回两个长度相同的序列之间的距离,比如使用欧氏距离或DTW。

    定义5:时间序列和子序列之间的距离

    所有长度和待测子序列一致的子序列中距离最小的那一个。
    在这里插入图片描述
    如图中,现在原序列中匹配到和子序列最佳的位置,再计算距离。

    定义6:信息熵

    定义7:信息增益

    定义8:最佳分裂点

    这个地方就是前面提到分裂阈值如何取的问题。就是在这个阈值处进行划分所获得的信息增益要大于任何其他点,这个阈值(距离值)就是最佳分裂点。所以说使用shapelets时包括两个步骤,寻找shapelets和相应的最佳分裂点。

    定义9:shapelets

    在shapelets和它对应的最佳分裂点处产生的信息增益要大于任何其他子序列和其他分裂点的信息增益。说白了shapelets就是一个具有区分能力的子序列和一个最佳的分裂阈值,拿这一组东西去分类会产生最佳效果(最大信息增益)。下文会介绍如何寻找shapelets和对应的最佳分裂点,以及如何构造一颗决策树。

    3、蛮力法寻找shapelets

    最简单的方法就是使用蛮力算法进行寻找,但这种方法在实际中并不可行,时间复杂度太高了,必须配合相应的加速技术。这里只是为了介绍它的算法思想。
    在这里插入图片描述
    算法程序入上图:
    给定一个数据集D,给定shapelets的最大和最小长度,最小长度可以为1,最大长度为数据集D中长度最小的序列对应的长度。数据集D中每个序列对应一个类别A或B。第一行生成了所有子序列的候选集,存储在一个列表中。具体做法其实是使用MAXLEN和MINLEN之间所有长度的滑动窗口去截数据集中所有的序列,相当于子序列的一个全集。第二行将最大信息增益bsf_fain赋值为0;接下来3到7行,使用候选集candidates中的每个子序列去分类,寻找分类效果最好的那一个,也就是信息增益最大的那一个便是shapelets。最佳分裂点的选择具体如下图:
    在这里插入图片描述
    假设现在在候选集canditates中拿出一个子序列s,然后将s和数据集D中所有序列的距离计算出来然后排序。如上图中数轴所示,数轴上值代表候选序列和数据集D中序列的距离,蓝色圆形和红色正方形代表两个不同类别,红色虚线箭头所指地方就是最佳分裂点,寻找它的过程是从左到右每相邻两个点之间的均值作为分裂点都计算信息增益,选最大的那个。
    在这里插入图片描述
    上图是生成候选集的过程,就是上面讲过的用户滑动窗口截就行了。
    在这里插入图片描述
    上图是计算每个候选集的信息增益。第一行是寻找最佳分裂点,然后数据集中距离小于阈值的分到D1集合,大于的分到D2集合,分完后计算增益返回。
    寻找一个shapelets的蛮力方法就是这样,可以看到复杂度是相当高的。

    4、子序列距离早弃

    在寻找shapelets中大多数计算量集中在计算子序列和序列的距离上。我们需要的是子序列之间的最小距离而不是所有距离,因此一直当前是最小距离时就可以停止计算。这个方法叫早弃,非常简单但十分有效。
    后面部分以后再更新

    展开全文
  • Time2Graph: Revisiting Time Series Modeling with Dynamic Shapelets(使用动态shapelets重新建模时间序列) 时间序列建模的目的是为了发现按时间排序的数据中的关系。关键问题是如何从一个时间序列中提取关键特征...

    Time2Graph: Revisiting Time Series Modeling with Dynamic Shapelets(使用动态shapelets重新建模时间序列)

    时间序列建模的目的是为了发现按时间排序的数据中的关系。关键问题是如何从一个时间序列中提取关键特征,以前的大部分框架从经典的特性工程和表示学习到基于深度学习的模型。虽然这些方法都取得了很好的效果,但是也因为缺乏可解释性被人诟病。而本文关注的对象shapelet(代表一个类的时间序列子序列)能在分类场景中提供直接的可解释的和解释性的见解,并且基于形状的模型已经被证明在各种实际领域中很有前途。


    在这里插入图片描述

    简介

    现有的工作都是将shapelets视作静态的,但是在现实生活中shapelets是动态的。首先,相同的shapelet出现在不同的时间片可能会产生一系列不同的影响。例如,在检测电力盗窃的情况下,夏季或冬季的低耗电量比春季更令人怀疑,因为制冷或供暖设备需要耗费更多的电力。其次,确定shapelets发展的方式对于充分理解时间序列至关重要。事实上,在特定时间具有小值的shapelets很难将一个偷电贼与一个确实经常消耗低电量的普通用户区分开来。另一种方法将涉及到识别那些曾经拥有高耗电量形状但突然间耗电量很少的用户。换句话说,这里的一个重要线索是shapelets是如何随时间发展的。时间序列中能够反映其在不同时间片上代表性的子序列称为时间感知shapelets。

    挑战

    1. 如何定义和提取出时间感知shapelets
    2. 如何捕捉shapelets的演进
    3. 如何利用shapelets的演化模式对时间序列进行建模

    IDEA

    提出了一种新的方法来学习时间序列的表示,通过提取时间感知的shapelets并构造一个shapelets演化图。我们首先定义了一个两层的时间因子来量化shapelets在不同时间的判别能力,然后构造一个图来表示shapelets的演化模式,最后,将shapelets和时间序列表示的学习问题转化为图嵌入问题。
    在这里插入图片描述
    每个月都可以被一个shapelets所表示(即图a中的数字),shapelets形状如图b第一行所示,图b第二行代表该shapelets和各个月份之间的相关性,图c代表shapelets演进图,其中每个节点代表一个shapelets,边代表从一个shapelets演化到另一个shapelets的概率(边越粗代表演化的概率越大)

    预先知识

    一组时间序列: T = { t 1 , t 2 . . . t ∣ T ∣ } T=\left \{t_1,t_2...t_{|T|} \right \} T={t1,t2...tT}
    每个时间序列都包含 t = { x 1 , x 2 , . . . x n } t=\left \{ x_1,x_2,...x_n\right \} t={x1,x2,...xn}按时间排序的元素
    t t t可以被分为长度为 l l l m m m个片段 所以 t t t可以表示为 t = { { x l ∗ k + 1 , . . . , x l ∗ k + l } } , 0 ≤ k ≤ m − 1 t=\left \{\{ x_{l*k+1},...,x_{l*k+l}\right \}\},0 \leq k \leq m-1 t={{xlk+1,...,xlk+l}},0km1

    两个分片距离度量 d ( s i , s j ) d(s_i,s_j) d(si,sj),如果两个分片的长度不相同那么不能使用欧氏距离,而应该使用DTW(动态规整)来寻找对齐

    DTW动态时间规整算法
    在这里插入图片描述

    定义1:对齐

    两个片段 s i s_i si s j s_j sj可以用DTW来计算最小距离的对齐,一个对齐 a = ( a 1 , a 2 ) a=(a_1,a_2) a=(a1,a2)可以定义为这样的一对坐标序列:

    在这里插入图片描述
    在这里插入图片描述

    对于一个时间序列来说,片段对于时间序列的距离可以定义为
    在这里插入图片描述

    定义2:shapelets

    shapelets v v v是代表某个类的片段。更准确地说,它可以通过一些特定的标准将 T T T分成两个更小的集合,一个接近 v v v,另一个远离 v v v,这样对于一个时间序列分类任务,正样本和负样本可以分成不同的组。该标准可以形式化为

    在这里插入图片描述
    L L L度量了正样本和负样本之间的不同, S ∗ ( v , T ) S_*(v,T) S(v,T)表示相对于特定组 T ∗ T_* T的距离集合,例如正负样本,而 g g g用来衡量两个集合间的距离(例如信息增益或KL散度)

    Time2Graph Framework

    时间感知shapelets提取

    局部因子 w n w_n wn表示某一特定shapelet的第n个元素的内部重要性,则将shapelet v v v与片段 s s s之间的距离重新定义为
    在这里插入图片描述
    直观解释是将权重w投影到最优DTW路径上
    全局因子 目的是测量跨片段间对shapelets的识别能力的影响

    在这里插入图片描述
    通过有监督学习来得到最重要的时间感知shapelets以及对应的 w i w_i wi u i u_i ui

    在这里插入图片描述

    具体算法图如下:

    1. 首先是shapelets候选集的生成算法
      在这里插入图片描述
    2. 时间感知shapelet提取算法
      在这里插入图片描述

    shapelets进化图

    想法:得到shapelets之后,很多工作直接运用于表示时间序列,但是都忽略shapelets之间的相关性(这里包括同时出现以及出现的顺序等等相关性),所以文章提出使用图来表示这种shapelets之间的相关性

    shapelets进化图:定义一个有向带权图, G = ( V , E ) G=(V,E) G=(V,E),每个顶点代表一个shapelets,有向带权边的权重 w i j w_{ij} wij代表shapelet i i i出现在shapelet j j j之后的概率

    图的构建

    在这里插入图片描述
    这里 d ^ i , ∗ ( v i , ∗ , s i ) = u ∗ [ i ] ∗ d ^ ( v i , ∗ , s i ∣ w ∗ ) \hat d_{i,*}(v_{i,*},s_i)=u_*[i]*\hat d(v_{i,*},s_i|w_*) d^i,(vi,,si)=u[i]d^(vi,,siw),限制条件 d ^ i , ∗ ≤ δ \hat d_{i,*} \leq \delta d^i,δ,所以shapelet v i , ∗ v_{i,*} vi, p i , ∗ p_{i,*} pi,的概率被指定给片段 s i s_i si,最后我们将重复边通过把权重相加合并,具体算法见下图:

    在这里插入图片描述
    表示学习
    使用DeepWalk对我的shapelets进化图进行embedding,得到了顶点表示向量 μ ∈ R B \mu \in \mathbb{R}^B μRB,B是嵌入空间维数,然后对于每个时间片段 t = { s 1 , s 2 , . . . , s m } t=\{s_1,s_2,...,s_m\} t={s1,s2,...,sm}相对应的shapelets { v 1 , ∗ , v 2 , ∗ . . . v m , ∗ } \{v_{1,*},v_{2,*}...v_{m,*}\} {v1,,v2,...vm,},以及他们被赋予的概率 { p 1 , ∗ , p 2 , ∗ . . . p m , ∗ } \{p_{1,*},p_{2,*}...p_{m,*}\} {p1,,p2,...pm,},将每个片段赋予的shapelets向量 μ ( v i , j ) \mu(v_{i,j}) μ(vi,j)乘以概率后相加,就得到了每个时间片段的表示如下:
    在这里插入图片描述
    这个时间片段表示可以被应用到下游的分类任务中,比如判断某个时间片是否有偷电的现象
    在这里插入图片描述

    实验部分

    五个数据集,对比了不同的方法
    在这里插入图片描述
    启发:这篇文章所提出的时间感知的shapelets相当于是整个时间序列中的一些代表性子序列,这些子序列能够很好地将时间片段划分为正样本和负样本,然后通过赋予内部权重以及全局权重来衡量shapelets对于整个时间序列的分类效果,得到时间感知的shapelets,最后利用shapelets具有演化性的特点,将时间序列建模成shapelets间的演化过程构建图,通过图嵌入来学习shapelets之间的演化,从而能够将时间序列片段表示为shapelets之间的演化过程,从而利用顶点向量进行分类。重点在于对数据的表征学习,不是通过直接将时间片段直接用shapelets来代表,而是通过捕捉shapelets之间的进化关系,这种基于案例的推理也有一定的解释性,可以看出要做解释性还要从数据建模开始,对于特定的数据进行一定的建模(和prototype很相似)。

    展开全文
  • 这个方法的优点: (1) Shapelets可以提供可解释的结果,这可能有助于领域从业者更好地理解他们的数据。例如,在图3中,我们可以看到shapelet可以概括为:“荨麻有一个茎,它几乎以90度的角度与叶相连。” (2) 使用...

    shapelet猜想

    时间序列分类最简单和稳健的方法是最近邻算法,优点是没有大量参数需要调整,缺点是我们无法深入了解一个特定的对象为什么被分到一个特定的类。
    图1显示了两类叶子的例子,荨麻(刺荨麻)和马鞭草。这两种植物通常被混淆。
    1
    为了区分两种叶子,颜色和大小的可变性使类之间的差异性很小,我们最大的希望是基于叶子的形状。但从总体来看还是相差很细微。尝试将每个叶子转换成一维表示,如图2所示。
    2
    然而,使用(旋转不变)欧几里德距离或动态时间扭曲(DTW)距离的最近邻分类器并没有显著优于随机猜测。原因似乎是数据有点嘈杂(即昆虫咬伤和不同的茎长),而这种噪音足以掩盖形状上的细微差异。然而,假设我们不是比较整个形状,而是只比较两个类别中的一小部分形状,这两个类别是有区别的。
    3
    shapelet已经“发现”这两个物种之间的区别在于荨麻的茎与叶的角度几乎为90度,而马鞭草的茎与叶的连接角度要小得多。找到并记录它与数据库所有对象中最近匹配的子序列的距离之后,我们可以构建图4所示的简单决策树分类器。
    4
    这个方法的优点:
    (1) Shapelets可以提供可解释的结果,这可能有助于领域从业者更好地理解他们的数据。例如,在图3中,我们可以看到shapelet可以概括为:“荨麻有一个茎,它几乎以90度的角度与叶相连。”
    (2) 使用局部特征,因为全局特征可能因为噪声使特征失真
    (3) 计算复杂度低,速度快,分类时间为 O ( m l ) O(ml) O(ml),m是查询时间序列的长度,l是shapelet的长度。

    定义和术语

    时间序列、子序列、滑窗的定义不赘述。
    时间序列的距离 Dist(T, R) , 将两个长度相同的时间序列T和R作为输入,并返回一个非负值d,即T和R之间的距离。我们要求函数Dist对称;即Dist(R,T)=Dist(T,R)。
    从时间序列到其子序列的距离 SubsequenceDist(T, S) , 它将时间序列T和子序列S作为输入,并返回非负值d,取最小的d即从T到S的距离。SubsequenceDist (T, S ) = min( Dist (T, S’ )), S ′ S^{\prime} S表示所有选取的子序列。可以理解为:
    5
    :作为模型表现的评判依据。一个时间序列数据集D由A和B两个类组成,当A类中的对象比例为 p ( A ) p(A) p(A),B类中对象的比例为 p ( B ) p(B) p(B),则D的熵为 I ( D ) = − p ( A ) log ⁡ ( p ( A ) ) − p ( B ) log ⁡ ( p ( B ) ) I(\mathbf{D})=-p(A) \log (p(A))-p(B) \log (p(B)) I(D)=p(A)log(p(A))p(B)log(p(B)).
    在决策树中,每次分割策略将整个数据集D分成两个子集,D1和D2。因此,在对每个数据集进行加权后,剩余的信息由每个子集的加权熵定义。如果D1中的对象的分数为 f ( D 1 ) f(\mathbf{D}_{1}) f(D1),D2中的对象的分数为 f ( D 2 ) f\left ( \mathbf{D}_{2}\right ) f(D2),则拆分后D的总熵为 I ^ ( D ) = f ( D 1 ) I ( D 1 ) + f ( D 2 ) I ( D 2 ) \hat{I}(\mathbf{D})=f\left(\mathbf{D}_{1}\right) I\left(\mathbf{D}_{1}\right)+f\left(\mathbf{D}_{2}\right) I\left(\mathbf{D}_{2}\right) I^(D)=f(D1)I(D1)+f(D2)I(D2) 。这允许我们定义任何拆分策略的信息增益, 拆分前后熵表示为 I ( D ) I(\mathbf{D}) I(D), I ^ ( D ) \hat{I}(\mathbf{D}) I^(D), 假设拆分策略为sp,那么 Gain ⁡ ( s p ) = I ( D ) − I ^ ( D ) , Gain ⁡ ( s p ) = I ( D ) − ( f ( D 1 ) I ( D 1 ) + f ( D 2 ) I ( D 2 ) ) \begin{aligned} \operatorname{Gain}(s p)=I(\mathbf{D})-\hat{I}(\mathbf{D}) &, \\ \operatorname{Gain}(s p)=I(\mathbf{D})-\left(f\left(\mathbf{D}_{1}\right) I\left(\mathbf{D}_{1}\right)+f\left(\mathbf{D}_{2}\right) I\left(\mathbf{D}_{2}\right)\right) \end{aligned} Gain(sp)=I(D)I^(D)Gain(sp)=I(D)(f(D1)I(D1)+f(D2)I(D2)),
    当使用shapelet的距离作为拆分策略时,数据集的一个类中的大多数时间序列对象都接近SubsequenceDist下的shapelet,而另一个类中的大多数时间序列对象则远离它。使用暴力算法,给定一个候选shapelet,计算候选对象与数据集中每个时间序列对象之间的距离。根据距离对候选对象排序进行排序,并在两个相邻距离之间找到一个最佳分割点.
    最佳分割点(OSP) 。一个时间序列数据集D由A和B两类组成。对于shapelet候选者S,我们选择一些距离阈值dth,并将D分为D1和D2,这样对于D1中的每个时间序列对象 T 1 , i T_{1, i} T1,i,SubsequenceDist ( T 1 , i , S ) < d t h \left(T_{1, i}, S\right)<d_{t h} (T1,i,S)<dth,而在D2中,SubsequenceDist ( T 2 , i ˙ , S ) ≥ d t h \left(T_{2, \dot{i}}, S\right) \geq d_{t h} (T2,i˙,S)dth. OSP是一个距离阈值, Gain ⁡ ( S , d O S P ( D , S ) ) ≥ Gain ⁡ ( S , d t h ′ ) \operatorname{Gain}\left(S, d_{O S P(\mathbf{D}, S)}\right) \geq \operatorname{Gain}\left(S, d_{t h}^{\prime}\right) Gain(S,dOSP(D,S))Gain(S,dth)
    使用shapelet,分割策略包含两个因素:shapelet和相应的最优分割点。作为一个具体的例子,在图4中,shapelet在shapelet字典中以红色显示,最佳分割点是5.1。

    shapelet,给对应一个包含两个类别的时间序列D, shapelet (D)是一个子序列,对于任何子序列S,与它相对应的最佳分割点为
    Gain(shapelet(D), d O S P ( D ,  shapelet  D ) ) d_{O S P(\mathbf{D}, \text { shapelet } \mathbf{D}))} dOSP(D, shapelet D)) ) ≥ Gain ⁡ ( S , d OSP   ( D  , s ) \geq \operatorname{Gain}\left(S, d_{\text {OSP }} \text { ( D }, s\right) Gain(S,dOSP  ( D ,s) )

    由于shapelet只是任何长度小于或等于我们数据集中最短时间序列长度的时间序列,因此它可以拥有无限多的可能形状。做一个合理的假设,一个类中的时间序列对象可能包含一些类似的子序列,把这些子序列是看做shapelet的候选对象。
    那么shapelet可能有多少个候选对象呢? 举个例子,数据集有200个实例,每个实例的长度为275。如果设置shapelet最小长度MINLEN=3,最大长度MAXLEN=275,将有7480200个shapelet候选者。对于每一个候选对象,我们需要在k个时间序列对象中找到其最近的邻居。 计算公式如下: ∑ k = M I N L E N M A X L E N ∑ T i ∈ D ( m i − l + 1 ) \sum_{k=M IN L E N}^{M AX L E N} \sum_{T_{i} \in D}\left(m_{i}-l+1\right) k=MINLENMAXLENTiD(mil+1)
    m i m_{i} mi 是来自数据集的时间序列 T i T_i Ti的长度,1≤i≤k; shapelet长度为 l l l.
    这么多候选对象的下使用暴力算法是很费时间的,他们提出一种 修剪策略 在很短的时间内达到相同的效果。

    寻找shapelet

    暴力算法

    6
    先产生所有可能长度的子序列作为候选shapelet的集合;初始最大信息增益为0, 然后检测每个候选集中的shapelet能够多好地区分A、B两类。直观理解,如图6所示,计算每个时间序列到候选对象的距离, 将其放在实数线上,并标注上类别。
    7

    子序列丢弃(subsequence Distance Early Abandon)

    在蛮力法中,通过计算T和每个长度为|S|的子序列的欧氏距离并选择最小值,得到时间序列T到子序列S的距离。当前存在一个最小距离时,我们不再计算每个子序列与候选序列之间的确切距离,而是可以在部分距离超过目前已知的最小距离时停止计算距离,这样达到提高效率的目的。如下图所示:
    7

    熵剪枝(Admissible Entropy Pruning)

    可以使用一种叫做早期熵剪枝的新思想,以避免在寻找形状元素时需要进行大量的距离计算。
    在brute-force算法中,获取候选对象与其每个对象的最近匹配子序列之间的距离是最昂贵的计算,而计算信息增益所需的时间并不重要。不必等到每个时间序列对象到候选对象的所有距离,而是根据当前观察到的距离计算信息增益的上界。如果在搜索过程中的任何时候,上界不能超过目前为止的最佳信息增益,我们将停止距离计算并从考虑中删去该特定的候选对象。如下图:
    8

    通过测量10个时间序列到目前为止最佳候选对象的距离,并根据距离将他们排列成一维表示。A类的6个对象中有5个(用圆圈表示)比来自B类的4个对象中的任何一个(用正方形表示)更接近候选对象。此外,在分割点右侧的5个对象中,只有一个A类对象与B类对象混淆。最佳分割点用一条垂直虚线表示,到目前为止最好的信息增益为:
    8
    考虑其他候选shaplet,前5个计算的距离如下:
    10
    剩下的5种距离放到上图中能使其信息增益比当前信息增益0.4228更小?最可能的情况如下图, 所有A类在左边,B类在右边,或者相反。

    11
    此时信息增益为:
    12
    所以当出现信息增益更低时,停止对剩余对象的距离计算,并将该候选对象永远从考虑中删除。

    将shapelet用于分类

    结合决策树,建立一个shapelet决策树分类器。
    训练一颗决策树,按照决策树常规推理过程就能得到预测结果。

    实验的评估

    一个包含了这项工作中使用的所有数据集和代码,以及包含在所有图表中显示的原始数字的电子表格,以及显示决策树的更大的注释图形等的网页

    表现对比

    在合成闪电(Synthetic Lightning EMP)数据集分类上测试shapelet查找算法的可伸缩性,该分类具有训练/测试分割=2000/18000。对比四种不同的搜索算法记过如下:
    13
    暴力搜索5天时间搜索160个对象,基于熵的修剪有助于将其减少两个数量级以上。

    箭头分类任务

    使用基于角度的方法将弹丸点的形状转换为时间序列,然后随机创建了一个36/175的训练/测试分割。
    14
    可通过底部附近一个由深凹底端连接的未开槽的轴颈区域来区分Clovis箭头。Avonlea箭头是由一个浅凹底端连接的小切口轴区域。shapelet决策树分类器的准确率为80.0%,而旋转不变的最近邻分类器的准确率为68.0%。shapelet决策树分类器不仅具有较高的分类精度,而且比旋转不变的最近邻分类器产生的分类结果快3×10~3倍,而且在处理大多数集合中普遍存在的破碎弹丸点时更具鲁棒性。
    15

    挖掘历史文献

    shapelets在挖掘和注释历史文档方面的应用,识别军徽或纹章盾牌。图14为例,它展示了与不同国家的纹章传统有关的不同形状的例子。
    16
    使用基于角度的方法将护盾的形状转换为时间序列。有些护盾可能会被装饰物或撕裂的部分,因此可能具有完全不同的周长,所以我们没有将时间序列长度标准化。我们从每个类中随机选择10个对象作为训练数据集,剩下的129个对象留作测试。生成的分类器如图15所示。
    17
    shapelet决策树分类器,达到了89.9%的准确率;而对于旋转不变的最近邻欧几里德距离分类器,准确率仅为82.9%。除了精度上的差异之外,shapelets还有两个额外的优点。首先,分类的时间大约是旋转不变的一个最近邻欧几里德距离的3×104倍。其次历史手稿中的许多图像被撕毁或退化, 决策树仍然可以正确地对盾牌进行分类。

    有没有枪的问题

    小麦光谱

    数据集包括加拿大1998年至2005年间种植的775个小麦样品的光谱。分类标签是小麦生长的年份。对象之间的一些相似性/不相似性可以归因于年份。类之间的差异非常细微:
    18
    创建了一个49/726训练/测试分割,确保训练集中每个类有7个对象,然后测试了一个最近邻欧几里德距离分类器的分类精度,分类精度为44.1%(动态时间扭曲在这里没有优于欧几里得距离)。创建一个决策树, 输出如图19所示:
    19决策树的准确率为72.6%,明显优于最近邻法的44.1%。

    critical thinking

    (1)通过提前剪枝和提前丢弃的方式解决了暴力算法中长时间的计算问题。
    (2)对于小样本而言,这是一个很好的算法。需要合适的场景下才能使用,涉及到与外形相关的问题。
    (3)这里认为同一个类别总是存在一处或者多处相似度很高的特征,因此能够做判别,对于同一类别存在大的个体差异的情况没有讨论。

    展开全文
  • 轮子:tslearn→shapelets

    轮子:tslearn→shapelets

    展开全文
  • 基于最佳u-shapelets的时间序列聚类算法.pdf
  • 多元时序Shapelets及其在ICU医学软件应用的研究.docx
  • 时间序列分类算法ST及其实现代码

    千次阅读 2020-05-06 20:18:49
    Shapelets是时间序列的辨别性子序列,可以最好地预测目标变量)。基于shapelet的分类使用shapelet和序列之间的相似性作为辨别性特征。shapelet方法的一个好处是shapelet是可理解的,并且可以提供对问题域的洞察。...
  • (一)sktime ...今天搜索shapelets方面代码的时候看到了这样一个库:pyts,他的GitHub仓库地址是:https://github.com/johannfaouzi/pyts。在他的仓库readme下还放了介绍这个库的论文: 《pyts: A Python
  • 时间序列shapelet是一种短的判别子序列, 它不仅准确,而且对于单变量时间序列(UTS)的分类问题也是具有可解释性的 然而,由于多变量时间序列分类(MTSC)的候选shapelets可能来自不同长度的不同变量,无法直接...
  • Time Series Classification (TSC) is an important and challenging problem in data mining. With the increase of time series data availability, hundreds of TSC algorithms have been proposed....
  • 前提描述:shapelet在处理原始数据之后,shapelets[idx, start, end] 其中idx表示的是选择的shapelet在test数据中的位置,但是因为test数据是随机选择的,所以需要有test数据和其源pcap名称一一对应 第一步保证...
  • 我们提出了一种使用E. Nelson的非标准分析方法来构建扩展的Wiener度量的新方法。 对于新定义,我们为独立随机变量构造了概率度量的非标准化卷积。 作为应用程序,我们考虑对财务时间序列的简单计算。
  • 行为识别特征提取综述

    千次阅读 2014-06-28 10:54:50
    行为识别特征提取综述 转自:... 摘要 ... 人体行为识别目前处在动作识别阶段,而动作识别可以看成是特征提取和分类器设计相结合的过程。特征提取过程受到遮挡,动态背景,
  • 学习笔记3

    2018-12-07 19:52:42
    Clara算法的总结 https://blog.csdn.net/u013834836/article/details/41214709 机器学习:基于层次的聚类算法 ... 聚类(1)——混合高斯模型 Gaussian Mixture Model https://blog.csd...
  • 当前最新最全面的时间序列数据挖掘的研究综述,ACM Survey
  • 深度学习的时间序列分类

    千次阅读 2020-09-17 21:28:58
    为什么要进行时间序列分类? (Why Time Series Classification?) First of all it’s important to underline why this problem is so important today, and therefore why it is very interesting to understand ...
  • 对基于图像的纹理映射进行基于块的优化(Patch-Based Optimization for Image-Based Texture Mapping)  SIGGRAPH 2017  SAIBI,NIMA...
  • "Shapelets Correlated with Surface Normals Produce Surfaces". Technical Report 03-003, October 2003 An example of how much 3D shape you can get from very minimal surface normal information. ...
  • 如图 10 所示,图中的每个节点代表一个 Shapelets,如果两个 Shapelets 连续出现在同一个时序样本中,我们就在它们之间连一条边,边的权重描述了这两个 Shapelets 共现的概率。 图 11:Time2Graph 框架示意图 首先,...
  • 很明显,shapelets 的质量对 TSC 的准确性至关重要。然而,主要的研究集中在从一些 shapelet 候选者中建立准确的模型。为了确定这样的候选者,现有的研究非常简单,例如,枚举一些固定长度的子序列,或者随机选择...
  • 基于深度学习时间序列分类研究综述[论文阅读]

    万次阅读 多人点赞 2019-03-15 10:22:22
    大多数这些方法明显优于NN-DTW(Bagnall等,2017)并且共享一个共同属性,即数据转换阶段,其中时间序列被转换为新的特征空间(例如使用shapelets变换(Bostrom和Bagnall) ,2015)或DTW功能(Kate,2016))。...
  • 该代码扩展了快速Shapelet发现Shapelet提取算法,以从多元时间序列数据中提取Shapelets,并使用提取的Shapelets对时间序列进行分类,从而建立决策树分类器。 先决条件 您需要在计算机上正确安装以下物品。 Python库...
  • 时间序列分类算法_时间序列分类算法简介

    千次阅读 多人点赞 2020-08-30 21:10:18
    时间序列分类算法A common task for time series machine learning is classification. Given a set of time series with class labels, can we train a model to accurately predict the class of new time series?...
  • Kovesi, “Shapelets correlated with surface normals produce surfaces,”in Proc. Int. Conf. Comput. Vis., 2005, pp. 994–1001. 具体上,可以通过卷积来计算相关性,而可以使用图像平面上图像梯度的方向来...
  • 为了在计算复杂度可接受的情况下表示出 Time-aware Shapelets,杨洋教授团队构造了 Shapelet 演化图,其中节点代表 Shapelets,有向边的权重代表 Shapelets 共现的概率。根据 Shapelets 的物理意义和演化图中边的...
  • 杨洋副教授在报告中,针对用户窃电行为预测等实际问题,利用 Shapelets(具有代表性的时序子序列)表征了具有特定意义的时序信号片段,并针对 Shapelets 在不同时间点意义不同、Shapwlets 会发生演化的问题,分别...
  • Using Bespoke estimator-specific methods: We can use Bespoke estimator-specific methods for handling multivariate time series data which helps us in finding shapelets in multidimensional spaces....
  • Yang, Mingqiang, Kidiyo Kpalma, and Joseph Ronsin. "A survey of shape feature extraction techniques." (2008): 43-90. 转载请注明 黄世宇:http://www.cnblogs.com/huangshiyu13/p/6432647.html... 1.介...

空空如也

空空如也

1 2 3 4 5
收藏数 87
精华内容 34
关键字:

shapelets