聚类分析是当前机器学习的一个研究热点,它旨在将数据集合拆分组成若干有意义的簇（也叫“类”）,从而实现对数据的解释和识别。基于图的聚类（本文中也简称为图聚类）是一种较新的聚类方法,它先将数据表达为一个图,然后再将聚类问题转化为图划分问题。相比其它聚类方法,许多研究已证实图聚类方法更具有竞争力。本质上,图聚类方法几乎能对任意流形状数据进行聚类,这克服了传统聚类方法只善于对凸形态数据进行聚类的不足,因此获得了广泛地研究。本文的研究内容主要围绕图聚类算法、图优化理论和半监督学习等内容进行展开。研究目的是探究图聚类算法的基本框架,发现图聚类算法的优缺点和提出新的图聚类算法等。作为主要研究成果,在深入探讨了Yang等人在2016年提出的低秩双随机矩阵分解聚类（即Data-Cluster-Data,简称DCD）算法^[25]的基础上,本文提出了以下两个新的图聚类算法:1)图优化的DCD（即Graph-Optimized DCD,简称GoDCD）算法。针对DCD算法存在“聚类结果好坏严重依赖于初始相似关联矩阵构造质量”的缺点,我们在GoDCD中引入了用图优化的思想,即将相似关联矩阵和聚类指示矩阵进行交替优化,从而得到了比DCD算法更好的聚类效果。2)半监督的DCD（即Semi-Supervised DCD,简称SSDCD）算法。由于DCD属于无监督聚类算法,没有利用任何先验数据知识（如部分弱标签数据）,这往往会得不到更好的聚类结果。而在实际问题中,经常会获得少量的弱标签数据,例如成对约束信息。本文将成对约束引入DCD模型,将DCD从无监督情形推广到半监督情形,从而提高了聚类效果。