摘要：数据的高维度是造成时序数据相似性搜索困难的主要原因。最有效的解决方法是对时序数据进行维归约，然后对压缩后的数据建立空间索引。目前维归约的方法主要是离散傅立叶变换(DFT)和离散小波变换(DWT)。提出了一种新的方法，利用离散余弦变换(DCT)进行维归约，并在此基础上给出了对时序数据进行范围查询和近邻查询的相似性搜索方法。与基于DFT、DWT的搜索方法相比，该方法在理论分析和实验结果上都显示出较高的效率。
关键词：时间序列; 离散余弦变换; 范围查询; 近邻查询
中图分类号： TP311.13
文献标识码：A
0引言
时间序列（简称时序）是一组有序的、随时间变化的数值序列，例如股票价格数据、产品销售记录、地区气温等。时间序列数据的挖掘是数据挖掘的一个重要分支，研究它会带来广泛的社会效益。例如在股票市场，通过对股票价格的历史走势分析，可以预测未来的走势；电力部门可以通过对用电量的分析，指导电力分配；医学领域，医生能通过对药物疗效的数据分析，掌握药物的特性等。
时间序列数据的挖掘体现在多个方面，比如从时间序列中发现关联规则，时序数据集的分类以及聚类等。所有这些工作的前提都是要比较时间序列之间的相似性。度量两个序列的相似性，标准的方法是采用欧式距离。两个时间序列的欧式距离为在进行序列的相似性搜索之前还给出一个阈值ε，如果D(,)≤ε，我们就说,两者在ε内相似。
时序数据相似性搜索面临的一个困难是它的高维性。如果直接对时序数据库中所有序列依次进行扫描，计算与查询序列的距离，计算量是非常大的，并且在查询序列变化时，还要再重新扫描数据库，这对庞大的数据库而言是不现实的。而大部分连续的时间序列中的点不是相互独立的，而是彼此相关的，因此一定存在信息冗余。所以相似性搜索最有效的方法是先对时间序列进行维归约(dimension reduction)以提取序列的特征，然后用空间索引结构建立基于特征空间的索引。这种方法首先由Agrawal提出，用离散傅立叶变换(DFT)将时间域上的时间序列数据变换为频率域上的序列数据，用前k个系数作为序列的特征，然后针对特征空间建立索引结构［1］。但这种方法限制每个序列的长度相同，Faloutsos克服了这个困难，通过滑动窗口(sliding window)将时间序列分解为一系列长度相同的子序列，再由子序列抽取特征进行相似性搜索［2］。
近年来，Chan和Fu首次用离散小波变换(DWT)进行维归约，通过保留小波变换后的前k个位置的系数，即低频特征，得到时间序列的一个粗略逼近，并通过实验证明了DWT的优越性［3］。在此基础上，一些学者做了更深入的研究［4~6］。其中，Wu等对用DFT和DWT进行搜索做了全面的比较［6］。
本文基于欧式距离，从时间序列经DFT变换后序列系数的复对称性中得到启发，提出一种新的方法，用离散余弦变换(DCT)将时间序列从时间域变换到频率域，然后抽取k个特征并映射到k维空间上的点，并通过建立空间索引结构(R树)来加快搜索速度。这主要是因为DCT具有两方面的优势：
1） DCT变换后的前k个系数能量集中和去相关性能都优于DFT和DWT［7］，因此抽取特征量的能量与原来的序列更接近，从而加强了搜索时的剪枝处理能力，提高了查询的准确性和速度；
2） DFT变换后的每个系数都是复数，所以对于k个系数要建立2k维的空间索引结构；而DCT变换后的每个系数是实数，所以空间索引结构的维数保持不变，因此降低了存储空间。
目前，以欧式距离作为相似性评价函数，用DWT进行查询是最好的相似性搜索方法，而用DFT查询是经典的搜索方法。所以本文用我们提出的方法和基于DFT、DWT的相似性搜索方法做了详细的比较，理论分析与实验都显示了DCT的优越性。
1离散余弦变换
离散余弦变换是一种实数域变换，克服了离散傅立叶变换中复数域运算的缺点，符合人类语言及图像信号的特点。因此已应用于数字信号处理、频谱分析等领域中［7］。离散余弦变换有两种定义方法，我们只给出本文中使用的一种定义［7］。
定义1设时间序列，经变换后的序列为，则有
其中，k=1,2,…,n－1。
上述的DCT定义是一个正交变换［7］，而正交变换保持欧式距离［4］，很容易得到下面的能量保持定理和距离保持定理。
定理1设是序列经DCT变换后的序列，则有
定理2设,分别是序列,经DCT变换后的序列，则有上述定理表明两个序列的欧式距离在时间域和频率域相同，而且很容易推得下面的定理
