软件开发项目名称/seo关键词快速排名前三位

摘要

相似度度量是时间序列数据挖掘中的核心问题。尽管大多数解决这个问题的方法已经开发出来，但是随着数据量的快速增长，我们认为支持快速和准确的相似性度量是一个具有挑战性的需求。本文提出了一种新的时间序列表示模型和相似度度量方法，该方法能够捕捉时间序列的主要趋势，实现快速的相似度检测。我们将新方法与最先进的时间序列相似方法和降维方法进行了比较。

介绍

时间序列数据挖掘是一个受到广泛关注的研究课题，其目的是发现时间序列数据中隐藏的模式。这类数据的来源非常广泛，包括语音识别[1]、金融和市场数据分析[2]、生物医学测量[3]、传感器组网[4]、运动物体轨迹跟踪[5]等。此外，挖掘时间序列的各种任务，可以归纳为7个方面:按内容查询[6]，聚类[7]，分类[8]，分割[9]，预测[10]，异常检测[11]，基序发现[12]。由于时间序列的高维问题，对时间序列数据的管理和分析主要集中在数据表示和相似度度量问题上。

• 数据表示模型。以一种可以有效处理的形式表示数据是数据挖掘的第一步。理想的时间序列表示既能保持数据的原始特征，又能具有简单的格式。此外，它可以加快检测过程，同时强调提高精度。
• 相似性度量。合理的相似度测度应具备以下特征:符合人类认知，兼顾局部尺度和全局尺度上最突出的特征，具有无条件识别任意对象的能力。

根据上述要求，本文的动机是设计一种新的时间序列表示模型和一种新的相似度度量，以实现快速准确的相似度检测。首先，新的表示模型既能对时间序列进行低维近似，又能保留时间序列的重要特征。其次，对时间序列的分布和变化要敏感。换句话说，新方法应该根据不同的数据分布产生不同的结果。此外，新算法还应适用于不同类型的数据集。随着信息产业的快速发展，每天产生的数据种类繁多，仅能处理单一类型数据的算法在应用中受到很大的约束。最后，它应该比现有的系统更快地处理时间序列。由于数据量大的挑战，许多现有的类似措施无法及时完成任务。为了解决这个问题，新方法必须尽快处理时间序列。
在本文中，我们提出了一种新的时间序列表示模型和相应的相似性度量——FAD。该方法来源于两个思想:相似的时间序列具有相似的趋势，两个数据点的比较可以转化为两种趋势的比较。第一个想法是符合人类的认知，是我们的方法设计出来的概念。第二种思想演示了我们算法的实现过程。
本文的其余部分组织如下。第2节介绍了时间序列表示模型和相似性度量的最新方法。第3节详细介绍了我们的新方法。第4节说明了数据集和实验结果。经过实验，第五部分对全文进行总结。

相关工作

正如我们在引言中提到的，时间序列具有高维性，直接处理它是很费时的。时间序列表示的主要目的是将时间序列以简洁而又富于特征的方式表达出来。在过去的二十年里，大量的时间序列表示模型被开发出来。分段聚合逼近(PAA)[13]可以将n个点的时间序列转换为具有p个分段的新序列(p<<n)，每个分段的大小为n/p,由位于滑动窗口内的数据点的平均值表示。PAA易于实现，在许多应用程序中非常有效。符号聚合近似(SAX)[14]将时间序列转换为由符号组成的离散字符串。该算法包括两个阶段。第一阶段采用PAA算法对时间序列进行降维。第二种方法将平均值段转换为离散的字符串。微分时间序列分段逼近(DSA)[15]以原始序列的导数形式逼近时间序列。DSA通过将每个片段的标准差设置为自然阈值，可以自动对时间序列进行分段。PAA、SAX、DSA都可在线性时间内完成。
相似度度量在时间序列数据挖掘领域中具有重要意义。动态时间翘曲(Dynamic Time warp, DTW)[16]作为一种经典的相似度度量，被广泛应用于时间序列的相似度搜索和检测。它通过最小化它们之间的总距离来执行一个级数到另一个级数的非线性映射。DTW虽然是时间扭曲感知，但容易出现“奇点”问题，从而降低精度，导致时间序列之间的不对称。为了解决奇点现象，Keogh[17]提出了一种DTW的变体，称为导数动态时间扭曲(DDTW)。该算法的新颖之处在于通过估计时间序列数据点的导数来获得原始数据的趋势信息，从而寻找对奇异点更有鲁棒性的新的扭曲路径。为了解决时间序列的高维问题，提出了利用时间序列的几个粗版本上的时间序列间的距离来快速搜索动态时间序列（FTW）[18]的方法。
DDTW和DTW的时间复杂度是$O\left(n^2\right)$，FTW通过裁剪大量的搜索候选人在速度上有明显的提升。

片段距离对齐FAD

A.分段和数据表示
趋势估计序列是包含时间序列趋势信息的特征丰富序列。FAD的设计理念是基于类似的时间序列有类似的变化趋势这一概念。因此，给定时间序列$T=\left(x_1,x_2,...,x_n\right),x_i\in \mathbb{R}$，FAD的第一步是通过公式（1）得到趋势估计序列$\hat{T}=(\widehat{x_1},\widehat{x_2},...,\widehat{x_n})$.

在我们的方法中，分割过程与片段的形成过程是相同的。分割步骤的关键思想是根据点的趋势估计值对时间序列进行分割。具体来说，我们设置了一个阈值来判断数据的变化幅度。如果有一个点的趋势估计值小于 $\epsilon$，可以看出该点与前一个点相比变化不大。这两个点用相同的符号表示。否则，如果两者之间有明显变化，这将导致相邻点的不同表示符号。通过这种方式，FAD可以将趋势序列转换为符号表示序列。

其中，$R_h$是$\widehat{x_h}$的符号化表示，$\epsilon$为变化趋势的阈值。$\epsilon$不小于0，参数$\lambda$表示用于表示原始序列的符号数目。例如，我们可以将原始数据转换为-1、0、1或-2、-1、0、1、2等组成的序列。这取决于数据的特性。注意$\lambda$是一个不小于1的整数。
然后，FAD的第二步是对趋势估计序列$\hat{T}=(\widehat{x_1},\widehat{x_2},...,\widehat{x_n})$进行变换，得到序列$\bar{T}=(S_1,...,S_p)$,其中，$S_i=(R_{j1},...,R_{j{k}_j})$，图1展示了整个过程。

很容易观察到，时序中大多数相邻点具有相同的变化趋势，即大多数相邻点具有相同的符号表示。为了更简洁地表达级数，我们将相邻的点用相同的符号合并。
因此，通过合并具有相同符号的相邻点，得到原始时间序列的一个片段。为了避免时间轴信息的丢失，每个片段在合并时都会记录具有相同符号的相邻点的数量。例如，图1中的R的第一个子序列被表示为（0,4）。
到目前为止，我们可以看出一个片段实际上是由两个元素表示的。一种是表示符号，另一种是符号的数目。表示符号可以看作是时间序列趋势的近似值，符号的个数可以反映趋势的持续时间。通过这种方式，可以对原始时间序列进行分段，而分段分隔符就是原始序列中的断点。因此，长度为p的时序$\bar{T}=(S_1,...,S_p)$可以表示为$((R_1,k_1),...,(R_p,k_p))$,其中$S_j$可以看做是$(R_j,k_j)$。
B.相似性度量
获得时序$\bar{T}$后，我们提出一种新的相似性度量方法。注意，我们将两个时间序列点之间的比较转换为它们的片段之间的比较。因此，在进行相似度度量时，需要考虑三个条件。
1）.如果序列$\overline{T_1}$和$\overline{T_2}$对应的片段有不同的趋势，这意味着两个子序列的趋势是不同的。在本例中，我们将两个片段之间的距离定义为(3)。

其中$S{1}_i$和$S{2}_j$分别是序列$\overline{T_1}$和$\overline{T_2}$的子序列，$R{1}_i$和$R{2}_j$是$S{1}_i$和$S{2}_j$对应的符号表示。
2）.如果序列$\overline{T_1}$和$\overline{T_2}$对应的片段有相同的趋势，这表明它们有相似的变化趋势。因此，它们之间的距离主要取决于它们的长度差异。我们通过（4）计算它们的距离。

$k{1}_i$和$k{2}_j$分别是$S{1}_i$和$S{2}_j$的点的数目，$\gamma$是一个可调参数，用于改变相同符号到不同符号的距离比值。直观上，同一符号片段的距离必须小于不同符号片段的距离。因此，

3）由于时间序列的长度不等以及FAD的时间扭曲，往往会在某个序列中留下一些片段，没有片段可以映射。事实上，没有映射的片段可以被看作与任何属于case 1的片段都不相似。我们定义它们的距离如(5)所示。

通常，我们可以将两个片段的距离定义为(6):

给定两个时间序列$\overline{T_1}$和$\overline{T_2}$，长度分别为p1和p2，它们之间的距离可定义为(7)。

表I更详细地显示了FAD的伪代码实现。该算法首先计算时序$T_1$和$T_2$的趋势估计序列，并将其转为符号化表示$R_1$和$R_2$。合并$R_1$和$R_2$中的相同符号得到特征序列$\overline{T_1}$和$\overline{T_2}$。假设i和j分别表示$\overline{T_1}$和$\overline{T_2}$中当前片段的下标，将两个序列的距离初始化为0.对于符号相同的映射片段，可以通过(4)计算它们之间的距离，由于两个片段映射正确，两个下标值都需要增加(第8-10行)。否则，如果映射片段具有不同的符号，则可能是错误的映射。因此，其中一个片段应该与其他系列中的下一个片段保持一致。在这种情况下，只需要增加一个序列的下标。我们根据两个序列的左长度来更新它。为了平衡两个序列的左长，我们增加了其中较长的下标。作为惩罚，它们之间的距离由(3)(第12-17行)计算。
很容易计算出FAD满足三角形不等式。正如我们在附录部分中证明的那样，FAD是一个度量。因此，现有的索引结构可用于FAD。


C.计算复杂度分析
该算法时间复杂度为$O(max(\lambda n,\lambda m))$

实验验证

在本节中，我们将FAD与用于时间序列表示模型和相似性度量的最新方法进行了比较，其中包括作为时间序列模型的PAA、SAX和DSA，以及作为相似性度量的FTW和DDTW。由于我们的工作目标是评估FAD在时间序列数据挖掘任务中的能力，我们使用标准分类和聚类框架进行评估，包括K-means聚类、聚类层次聚类和最近邻分类。所有实验均在Intel E5-2620 CPU 64.0 G的平台上进行.
A.评估框架
作为最基本的基于实例的学习方法，1-NN分类算法在我们的评估工作中至关重要。此外，与K-NN相比，1-NN分类具有不含参数，允许方法间比较的优点。我们还采用了流行的K-means算法，该算法具有简单、计算量低的特点。由于K-means算法需要选择输出聚类的数量，为了简单起见，我们采用了可以进行相关分类的数据集。因此，在每次集群评估中，我们将输出集群的数量设置为类的实际数量。由于初始聚类中心对K-means算法的性能有很大的影响，因此我们在随机选取初始聚类中心的同时，多次运行K-means算法以获得相对可靠的结果。分层聚类使我们能够在不依赖于聚类初始化的聚类框架中评估竞争的方法。在我们的工作中，我们雇用了使用算术平均的非加权对组法(UPGMA)算法，它是聚类算法的一种，基于群平均链接计算两个聚类之间的距离。
B.评估标准
为了评估竞争方法的有效性，我们直接将分类和聚类的结果与我们选择的数据集中可用的数据的内在分布进行比较。
F-measure或F-score (F)是最广泛使用的外部标准。它被定义为精确§和召回®两个信息检索概念之间的调和均值。

C.数据描述
实验中使用的10个时间序列数据集来自UCR时间序列分类/聚类主页[20]。数据资源由Keogh等人提供，它来源于各种应用，包括叶子的形状、心电图(ECG)数据、地震等。表二总结了有关数据的详细资料。