随着基因芯片技术的不断发展,已经获取了海量的基因表达数据。从已有的基因数据中挖掘有价值的信息,对于探讨基因的功能甚至某些细胞过程都有重大意义。聚类方法广泛的应用于此类数据的分析,特别是当前的研究热点——基因聚类问题。利用聚类算法找出相似基因,进而可以通过已知基因的信息去推断大量未知基因的功能。在众多聚类算法中,K-Means算法是最受欢迎的划分方式。它采用经典的梯度下降策略,以迭代的重定位方式分割数据集,快速给出聚类结果。然而K-Means算法有两大缺点：对初始质心敏感和易陷入局部极小,导致处理大规模、高维数据时聚类结果不理想。运用遗传算法(GA)在整个解空间搜索基因聚类问题的最优划分可以明显改善最终的聚类效果。但传统的交叉操作会产生非法分割即空类,导致大量的重复计算。因此直接利用GA处理基因聚类问题会付出高昂的计算代价,特别是针对大规模基因表达数据,各个聚类质心的收敛速度非常缓慢。遗传K均值算法(GKA)在保持遗传框架的前提下,采用K-Means算法代替交叉操作进行局部更新,算法融合后显著的改善了GA处理低维基因聚类时收敛过缓的缺陷,获得了给定基因表达数据集的全局意义下的最优分割。然而对于某些高维基因数据,GKA的收敛速度仍不尽如人意。为了得到更全面的基因聚类算法,我们尝试了添加扰动项的XK-Means算法,并且通过补类的策略避免了选取合理扰动边界带来的大量计算,得到了改进算法——IXK-Means。更进一步,效仿GKA的混合方式,将IXK-Means引入到遗传框架中,提出了一种新的收敛到全局最优的基因聚类算法一—GXKA。本文首先介绍了基本的划分聚类算法及遗传框架下的聚类方法,接着在第三章中叙述了GXKA的计算流程及其算法细节,最后在第四章中,利用有限Markov链原理给出了GXKA的收敛性证明,并且进行了真实基因表达数据的实验。通过这些理论及实验的分析,我们得到了如下结论：(1)满足一定条件下,GXKA以概率1收敛到全局最优划分；(2)在相同的停机条件下,就三个评价聚类指标(MSE、类紧度D1和类分离度D2)而言,IXK-Means优于XK-Means的聚类效果；(3)GXKA的收敛速度相比GKA有了质的提高,大致只要GKA一半的进化时间就可以收敛到GKA的MSE稳态,有效的缓解了处理基因聚类时遗传框架带来的时间复杂度问题。