聚类作为无监督学习方法的重要组成部分,在当前的背景下也是研究人员的重点关注领域和一项极具挑战性的任务.最近邻点的连接则是聚类问题的重点研究方向.数据聚类对于机器学习、信息检索和数据挖掘具有重大的意义,因此也成为了研究热点之一.聚类问题的过程是让具有相同类别的对象的相似性尽可能地大,不同类别的对象的相似性尽可能地小.在过去的几十年中,基于图的这种途径的方法被越来越多地应用在聚类问题中,该方法是利用原始数据得到点对点的相似性矩阵,从而得到点与点之间的相似性,最后得出聚类的结果.早期的基于图的聚类算法在初始图的构建过程中,因其完全没有考虑到聚类过程中存在的问题,从而严重影响聚类性能;此外还有一个问题就是早期的方法并没有利用到图的连接结构信息,这导致在聚类性能和图的质量方面还有很大的提升空间.因此,本文将图的连接结构信息和聚类问题相结合,并提出了图连接结构聚类算法.本文算法利用点的相互连接性和最近邻来获得点的从属关系和那些能够决定聚类结果的聚类中心,通过连接一个点所有相关的最近邻点并建立一个网络,这个网络在论文里被称为充分连接集合,然后我们用这个网络的中心来代替这个点.相邻的点所形成的网络大部分都会互相重叠,因此,这些网络的中心可以决定聚类的簇.我们在优化了图模型的同时,也提高了聚类的性能.在现实世界的数据集与合成数据集上,我们新颖的方法同大量优秀的算法的对比实验证实了本文提出的算法的优越性.