数据聚类是模式识别的重要分支,它在模式分析、数据挖掘、信息获取、图像分割、决策等领域都有重要的应用。而这些领域的问题,通常都没有关于数据的先验知识可供利用。正是由于实际问题存在这些难以逾越的限制条件,因此,数据聚类应运而生,它特别适合对未标记数据点间的关系进行探索。数据聚类就是研究如何对未标记的数据进行分组或分类的学科,它不需要事先提供任何标记的样本,聚类的任务就是找出大量数据的内在结构,将这些未标记的数据点聚合成有意义的类别,以对它们的结构进行评价。在典型的聚类算法中,用于聚类的数据点是固定不动的,通过设计函数找到聚类中心或边界。然而,近年来,一些研究者提出动点聚类的新思想,他们将数据点考虑为自身可移动的Agent,通过设计简单规则,让数据点自动完成聚类。另一方面,量子计算的研究方兴未艾,在过去十年间,量子计算取得了一系列惊人的成就,以奇特的量子效应,如量子内在并行性、量子纠缠等为基础的量子算法,已经提供了量子计算可能比经典计算更强大的有力证据。如Shor的大数质因子分解量子算法,将经典计算中的NP完全问题转化为一个P问题,以多项式时间完成经典算法指数时间才能完成的任务。这些成就让我们意识到量子算法可能比已知最好的经典算法更快更好地解决问题,甚至解决某些经典计算无法有效解决的问题。更重要的是,它提供了一条寻找潜在算法加速的新途径。本文的研究主要分为两个部分：(1)经典世界中的动点聚类算法。受近年来兴起的动点聚类思想的启发,本文提出基于改进随机游动模型,基于复杂网络上的Flocking,基于演化网络上的博弈等几种动点聚类算法。(2)量子世界中的聚类算法。受量子计算已取得的惊人成就的鼓舞,本文将数据聚类问题与量子计算结合起来,提出基于量子随机游动和基于量子博弈的聚类算法,它们也可以看作是本文提出的两种经典世界中的动点聚类算法的量子化。本文的主要研究内容概括如下：(1)基于改进随机游动模型的聚类算法。随机游动是一类特殊的随机过程,本文提出一种改进的随机游动模型,并基于此模型建立聚类算法,并证明了算法的收敛性。算法中,数据点既是图的顶点,又是可移动的粒子,因而数据点形成的图的形状将随时间变化。每个移动的数据点又可以看作是一个局域控制系统,通过控制器调整转移概率并确定下一步的转移方向。当数据点根据简单规则在空间中作随机游动时,相似的数据点逐渐游动到同一个位置,并稳定下来形成一个聚类,而不同的聚类则相互远离。最后,当算法收敛时,聚类也就自动形成。(2)基于复杂网络上的Flocking聚类算法。复杂网络是近年提出的一种描述社会网络的拓扑结构,本文将数据点考虑为可移动的Agent,并且为每个Agent添加长程链接,从而将它们之间的关系用一个时变的复杂网络来表示。由此,将经典Flocking模型推广到复杂网络拓扑上,进而研究了一种基于复杂网络上的Flocking聚类算法。复杂网络的结构不仅为数据聚类提供了新的拓扑,更重要的是,复杂网络中的长程链接还为数据点提供了无法直接感知的隐含信息,并且加快了算法的收敛速度。最后,数据点会在算法收敛时,自动形成分离的群落,每个群落对应一个聚类。(3)基于演化网络上的博弈聚类算法。演化博弈理论植根于对生物界中动植物的竞争与合作现象的研究,本文将数据点看作有一定决策能力的博弈参与人,提出一种基于演化网络上的博弈聚类算法。每个博弈参与人的目的都是使自己的收益最大化,通过观察周围邻居的收益,断掉与低收益邻居的连边,而重新与有高收益的邻居相连,从而使得网络开始演化。在博弈参与人不断调整自己连边的过程中,某些策略会在网络中传播,并最终成为演化稳定策略。聚类在参与人博弈的过程中自然涌现,最后,采用相同演化稳定策略的数据点被分为一类,演化稳定策略的个数对应了聚类的类数。(4)基于量子随机游动的聚类算法。量子随机游动是经典随机游动的量子模拟,本文将量子随机游动与数据聚类结合起来,提出一种基于量子随机游动的聚类算法。量子随机游动与经典随机游动的区别在于,它的演化是酉的和可返的,而且,可能的经典路径在量子随机游动中产生相干。这就使得在量子随机游动中,粒子位置的概率分布与经典情况完全不同,这就为量子聚类算法得到更好的结果提供了机会。本文首先研究了两个基于一维量子随机游动的聚类算法,然后将一维量子随机游动推广到高维,从而建立基于高维随机游动的聚类算法,最后讨论了参数对聚类算法的影响。(5)基于量子博弈的聚类算法。量子博弈是经典博弈的量子模拟,在提出的基于量子博弈的聚类算法中,数据点作为可以使用量子策略的博弈参与人与对手进行2×2量子博弈。量子博弈利用量子纠缠态,使得博弈双方在使用量子策略时隐含地相互影响,从而获得与经典博弈不同的结果。本文考虑了两类量子策略情况、设计了两种收益矩阵和两种断边重连函数,并分别讨论和分析了不同条件组合对博弈参与人总收益和算法收敛速度的影响。