基于比特序列变化模式聚类的时间序列相似搜索

摘要

时间序列是一种重要的数据类型，在商业、医学、工程和科学等应用领域具有广泛应用。从生活实际中积累的时间序列数据库，记录了大量的重要信息。当前迫切需要提出有效的方法对时间序列进行处理，挖掘数据间隐含相互关系，并找出相似的序列。由于其重要性，时间序列相似性搜索问题正得到越来越多的研究。
　　 时间序列相似性问题的一个重要部分是搜索具有相似变化模式的序列，而目前时间序列相似搜索算法存在一些不足。提出了一种基于比特变化模式的时间序列相似搜索方法，该方法将时间序列的变化模式建模成一定长度的比特序列串，用比特序列串间的比特距离来反应变化模式的相似程度。为了避免对时间序列数据库顺序扫描，该方法对具有相似变化模式的时间序列进行聚类，在聚类得到的簇集上建立B+树索引。搜索过程则分为两步，首先在聚类索引上进行，找出具有相似变化模式的序列的候选集合，然后通过精确搜索剔除候选集中不符合要求的序列形成最终的结果，从而保证了相似搜索的效率。
　　 在实验设计上，模拟数据集由计算机随机产生，维度分别为20d、30d、45d和60d，时间序列记录数从10,000到600,000，实验中的各种相似搜索方法均采用相同的数据集。实验结果表明，该算法能够有效进行相似序列搜索，并能达到良好的搜索效率。