时间序列数据广泛存在于生活的各个方面,它记录了事物在每个给定时间间隔内的观测值,具有数据维度高、数据量大的特点。时间序列聚类作为数据挖掘领域的一个重要研究分支,受到人们的广泛关注。传统的研究方法大多直接对整个时间序列进行聚类分析,然而时间序列中存在的噪音等无关数据会影响聚类结果的准确性。最近,一种基于u-shapelets的时间序列聚类方法被提出,该方法利用局部形状特征来区分序列之间的差异,不仅聚类精度高,对聚类结果也有很好的解释性。虽然基于u-shapelets的时间序列聚类方法已经取得一定的成果,但仍存在一些问题。主要体现在三个方面:其一,提取u-shapelets的过程非常耗时,尤其是在一些大数据集上;其二,为了加速u-shapelets的提取而忽略其质量,在一定程度上降低了聚类结果的准确性;其三,原始的u-shapelets质量度量方式不够准确,会影响u-shapelets的辨别性。本文围绕以上问题主要对u-shapelets的提取过程进行研究,其主要内容如下:(1)本文提出一种随机局部搜索u-shapelets的算法(Random Local Search Algorithm,简称RLS算法)。首先,针对提取u-shapelets时间花费高的问题,RLS算法采用随机技术从数据集的整个子序列空间中选取一定数量的子序列,大幅度减少了u-shapelets候选样本的数量;其次,为了改善提取到的u-shapelets质量,引入一种局部搜索策略,求得局部最优子序列作为u-shapelets。本文在27个大小不同的数据集上对RLS算法的有效性进行了验证,实验结果表明,RLS算法在提高u-shapelets的提取效率的同时还提高了聚类结果的准确率。(2)本文提出一种基于特征点提取u-shapelets的算法(Feature Points Algorithm,简称FPs算法)。不同于RLS算法采用随机策略提取子序列,FPs算法在时间序列的特征点上提取子序列,不仅能够过滤掉大量多余的子序列,有效地解决提取u-shapelets时间花费大的问题,还能保证u-shapelets的质量。此外,采用一种新的u-shapelets质量评估方式,充分考虑相似的序列之间的紧密度,可增强提取到的u-shapelets的辨别性。实验结果表明,基于特征点提取u-shapelets的方法在提高u-shapelets的平均提取速度上具有更优的性能,并且能够保证聚类结果的准确性和确定性。