动态数据不同于传统静态数据,动态数据中存在着时间维度,在实际的应用场景中体现为数据的数量以及特征会随着时间动态演化。这也导致无法简单的使用静态聚类方法对动态数据进行分析。对动态数据进行聚类称为演化聚类问题,如何有效地利用历史数据一直是演化聚类的一个难题,现有的演化聚类算法大都受到时间平滑假设的局限,没有从数据本身考虑动态数据的内在联系。本文将演化聚类问题转化为动态图上的聚类问题进行研究,使用数据驱动的方式构建动态图,提供了一种更加鲁棒性的演化聚类分析方法。当前对演化聚类的研究已经引起了大量研究者的关注。但由于聚类属于无监督学习的范畴,缺乏标签信息的指导,所以传统的方法大都基于时间平滑假设。这导致了以下三个问题(1)目前动态数据越趋复杂,很多数据在演化时会呈现出分叉演化的特性,传统方法不能很好地处理这种问题;(2)时间平滑假设对当前数据与最近的历史进行了约束,但当前数据与最近历史之间的时间差在不同数据集中有很大差异,时间平滑假设却只能同等的处理这些数据。这使得传统方法在处理时间差较大的数据时难以获得较好的结果;(3)动态数据由于其演化特性,往往数据样本数量在不同时间会变化,并且随着时间的增长,数据量也会大大增多,导致计算复杂度过高的问题。传统的演化聚类方法往往难以解决这方面的问题。针对这些问题,本文分别提出了三种动态图上的聚类算法进行解决。本文主要的研究工作和取得的研究成果如下:(1)提出了基于演化树的动态图聚类算法,用于处理数据在演化过程中的分叉特性。通过设计树形平滑,利用图的协方差距离度量,获得动态演化树形结构,较好地处理了演化聚类中的分叉现象,并在多个真实数据集上进行了实验,获得了比其他方法更好的聚类效果。(2)提出了基于演化图的动态图聚类算法,利用数据驱动的图结构描述数据复杂演化结构。解决了数据在演化过程中由于时间上大间隔跨度无法平滑的问题。通过利用动态图的邻居关系来对当前时刻的数据进行约束,加入动态图的结构平滑用于求解优化目标,较好地处理了时间片的不连续问题。多个真实数据集上实验表明,该方法不仅提高动态聚类质量,同时还可以发现数据的演化规律。(3)提出了基于图核的演化图聚类算法,用于处理节点剧烈变化的情况,同时降低动态图的聚类算法时间复杂度。通过利用图核来构建演化图,达到对动态图聚类数据进行了大幅度压缩的效果,大大降低了动态聚类算法的时空复杂度,同时提供一种处理节点数目剧烈变化的高效方法。在真实数据集上的实验结果表明该方法在聚类质量和计算代价上均优于同类算法。