数据时代下智能化是各种设备和应用发展的一大趋势,各种数据挖掘技术正被用于实现这一目标。虽然数据时代的前景十分美好,但是也充满着各种挑战。首先,数据搜集和存储的代价越来越小,而人们处理数据的速度却远不及数据增长的速度。其次,获取的数据存在包括噪声、无结构性、信息缺省等多方面的质量问题,这为数据分析带来了不少困难。现实中获取的数据大部分为无监督类型的,快速高效的无监督学习方法不仅能够适当缓解数据处理压力,而且能够根据其所发现的价值帮助后续的数据收集工作。聚类分析是无监督学习的重要内容,有着久远的发展历史。相比起其他聚类方法,关联聚类能够不需预定义而自动选择合适的簇类数目进行聚类,这种特性使其更加适用于真实数据场景。然而关联聚类因其求解十分困难,多年来一直未能得到广泛应用。鉴于此,本文针对关联聚类问题进行了如下研究：(1)分别对关联聚类、最小k-割问题和二次半分配问题的数学优化形式进行了重构,一方面阐述了三者之间的相互关系和求解难度,另一方面以此说明利用现有的解决类似问题的松弛技术很难有所突破,应寻求其他方法。(2)通过对关联聚类求解难点的分析,引入聚类指示矩阵和聚类分配这两个新的变量,对原问题进行重新形式化,松弛掉问题的非关键约束,提出了一种单次迭代时间复杂度为O(|V|+|E|)的基于伪期望最大的迭代算法—-Pseudo-EM。此外,本文讨论了一种启发式的聚类指示矩阵的初始化方法和数据的稀疏性问题,并利用实验验证了算法的有效性。(3)本文最后探索了关联聚类的扩展应用,文中列举了两个关于聚类分析的典型应用——图像分割和社区挖掘。在图像分割中,基于Pseudo-EM的算法表现出了比谱聚类更加自然的分割结果。在社区挖掘中,算法能够十分接近地恢复真实的社区数目,并且所挖掘的社区质量也比其他算法更优。