聚类是人们认识和理解世界的最基本方式之一,广泛应用于分子生物学、金融、市场、电子商务等众多领域的数据分析。聚类的目标是根据一个对象群体的属性数据,基于相似性函数,寻找多个对象分组,使得同一组内的对象相似度高,而不同组的对象相似度低。同组内具有共同特征的对象称为一个簇(cluster)。在计算对象相似性时,若将对象的全部属性用于比较,即是人们通常所指的聚类,或称为单向聚类；在一些应用场合中,我们期望使用部分属性而不是全部属性衡量对象的相似性,这种利用部分属性来比较对象特征的聚类计算则称为双向聚类。双向聚类结果中,同组内具有共同特征的对象称为一个双向簇(bicluster)。聚类数据通常表示为实数矩阵,行对应于对象,列对应于属性。对于单向聚类计算,恰当地重排序行或列后,簇在聚类矩阵中对应于条状子矩阵；而对于双向聚类计算,恰当地重排序行和列后,双向簇在聚类矩阵中对应于块状子矩阵。在众多应用领域中,聚类实数矩阵可简化为元素均为0/1的两元矩阵。例如,在文本挖掘技术中,矩阵的行表示文档,列表示关键词。若文档i中包含关键词j,则矩阵的元素(i,j)值为1,否则为O。若一个子矩阵的元素均为1,则这个矩阵中的文档含有相同关键词,这些文档可能属于同一领域。此外,有时为便于分析或计算,也会将实数矩阵转化为两元矩阵。由于两元矩阵的重要性和普遍性,两元矩阵聚类分析算法广泛应用于市场购物篮分析、文本挖掘技术、基因表达谱分析、电子商务数据分析、社区发现等领域。本文主要研究两元矩阵上的两个聚类问题：带缺失值的两元指纹向量聚类问题、两元矩阵的k-子矩阵划分问题。1.带缺失值的两元指纹向量聚类问题带缺失值的两元指纹向量聚类问题源自于计算生物学中的基因表达谱聚类分析。基因是控制生命体性状的基本遗传单位,它是基因组序列上的一个片段。了解基因的功能,对于我们研究生命奥秘至关重要。然而,在已测序的基因中,功能尚且未知的超过40%。如何快速、准确推断基因功能是目前分子生物学亟待解决的问题。序列相似性比对是发现基因功能的一个重要方法,但遗憾的是在基因的一个功能家族中,基因序列相似性是很弱的,此外,还有一些基因,其功能是相同的,但没有任何序列相似性,故不能完全依靠序列比对推断基因功能。另外一种用来推断基因功能的重要方法是DNA微阵列技术,此项技术是近年来发展起来的分子生物学革命性技术之一。DNA微阵列实验产生的数据称为基因表达谱。由于基因表达谱分析算法的重要性和极具挑战性,使其成为当前分子生物学中研究的热点问题。基因表达谱可表示为一个m×n实数矩阵A=[aij]m*n,行表示基因,列表示实验条件。矩阵A的元素aij表示基因i在条件j下的表达水平。基因表达谱中存在较多数据未能真实反应基因的表达水平,称之为缺失数据(missing values)。在基因表达谱中,缺失数据可能会多达10%甚至更高,至少有一个缺失数据的基因占到90%以上。如何处理这些缺失值是分析基因表达谱的一个重要问题。聚类是分析基因表达谱的重要方法。在大多数基因表达谱聚类算法中,或是没有考虑缺失值,或是简单地替之以随机数。Figueroa、Borneman等人将基因表达谱转换为0-1-N向量集,称为两元指纹向量集,提出了带缺失值的指纹向量聚类计算问题,称为带缺失值的两元聚类问题(the binary clustering with missing values problem,简记为BCMV).在聚类的同时,此算法考虑了如何通过计算确定缺失值的数值。记BCMV(p)为含有常量参数p的BCMV I问题,p表示指纹向量中缺失值个数均不超过po Figueroa等给出了BCMV(1)的多项式时间精确算法；证明了BCMV(3)是NP-难的；给出了求解BCMV问题的启发式算法—贪心图划分算法(GCP)及其散列表实现法。BCMV(2)的复杂性则一直没有确定。本文讨论了BCMV(2)问题的复杂性,以三元素严格覆盖问题作为归约问题,证明其为NP-难的。此外,本文基了Figueroa等给出的GCP算法,给出了一种改进实现方式：链表法。理论证明链表法的时间、空间复杂度均低于散列表法,求解速度快于散列表法。实践表明,求解相同实例时,链表法计算耗时平均为散列表法的20%;当计算缺失值位数超过6的实例时,链表法计算耗时几乎总不超过散列表法的11%。此外,本文提出了求解BCMV(?)司题的基于线性规划舍入法的算法(the BCMV algorithm based on LP-rounding,简记为BLP),其近似比为BLP算法的速度略快于GCP链表法。本文使用闵可夫斯基测度和雅可比相似度系数比较了BLP算法与GCP算法的聚类质量,比较结果表明,BLP算法略优于GCP算法。2.两元矩阵的k-子矩阵划分问题以矩阵A=[aij]m*n表示m个对象、且每个对象有n个属性的数据集,其中aij表示第i个对象的第j个属性值。双向聚类的最简单求解目标是寻找矩阵行(对象)的一个子集,及列(属性)的一个子集,使得此行子集中的对象在此列子集中的属性下是高度相似的。这样的对象子集及属性子集下的数据称为双向簇。如果双向聚类问题的实例是两元矩阵,则双向聚类的目标是在矩阵中寻找元素值全为“1”的子矩阵(双向簇)。在许多应用,双向聚类的目标是同时寻找多个子矩阵(双向簇)。实际上,Madeira和Oliveira等人已经讨论了这个问题,并总结出了8种双向簇解格式：行与列排他式、行排他式、列排他式、无重叠棋盘式、树结构无重叠式、任意重叠式等。本文所研究的两元矩阵的k-子矩阵划分问题属于行列排他式解格式的双向聚类问题。两元矩阵的子矩阵划分问题(the submatrix partition of binary ma-trices problem,简记为SPBM)是双向聚类的一种计算模型。SPBM要求在两元矩阵中寻找多个行、列排他,且元素均为1的子矩阵,且使得矩阵的每一行(列)出现且仅出现在一个子矩阵中。记κ-SPBM为含有常量参数k的SPBM问题,k表示要求寻找的子矩阵为常数k个。本文中,我们讨论了κ-SPBM的复杂性。证明中用到了单调三取一可满足问题(M03)和二分图的二分团k划分问题(the partition of a bipartite into k bicliques problem,简记为κ-PBB),其中k是一个正整数常量。MO3是由Schaefer证明的一个著名NP-完全问题；k≥3时,κ-PBB的复杂性尚且是未知的。本文首先证明了M03问题的一个变体形式是NP-完全的。然后,以此变体形式的M03问题为归约问题,证明了3-PBB是NP-完全的,进而证明了κ-PBB(κ≥3)亦是NP-完全的。最后,以κ-PBB (κ≥3)为归约问题,证明了κ-SPBM (κ≥3)是NP-完全的。此外,本文还给了一个求解κ-SPBM算法的指数精确算法。本文的进一步研究工作主要包括二个方面：1.真实世界的数据大多是有噪声的数据,如分子生物学领域的基因表达谱、物联网领域的传感器数据、金融领域的股票数据等。因此,设计可以处理噪声数据的方法是十分必要的。目前,对于聚类分析,用于处理噪声数据的方法大体可分三类：图方法、贝叶斯法、概率法。准二分团法(quasi-biclique)是图方法中的主要方法。初步猜想准二分团问题的两个变体形式：最多边准二分团、准二分团划分问题均是NP-难的,下步将尝试证明这类未解决问题的复杂性,并设计求解算法。2.尽管不存在比较聚类算法性能的“黄金标准”,但是如何针对不同数据,选择恰当的聚类算法?如何比较某些算法的性能?仍是非常重要的。因此,不同聚类算法的性能比较方法及如何根据数据特点、聚类要求选择恰当聚类方法也是下一步的重要研究内容。