1. 研究目的与意义
自从基因芯片技术产生以来，大量的生物数据需要分析，这些数据大多规格化后以矩阵形式表示和存储。基因芯片数据中隐藏了大量有用的局部模式，而传统聚类只能寻找全局信息，无法找到局部信息，而大量的生物学信息就隐藏在这些局部信息中。
为寻找这些信息，cheng and church于2000年提出了双聚类(bicluster)概念[1]。
cheng 和 church首先提出双聚类并应用于基因表达数据挖掘中。为了评价该子矩阵的相似程度 cheng 和 church 提出了均方残值的概念 , 均方残值越低表明子矩阵的数据相似性越强 , 即表达相关性越强。
2. 国内外研究现状分析
(1)基于传统类的双聚类如getz g[2]等人提出的耦合双向聚类（coupled two-way clustering）算法。算法开始于初矩阵，创建两个集合，一个只包含所有列另一个只包含所有行。对这两个集合分别运用分层聚类,以产生稳定的行和列的聚类,迭代上述聚类过程来寻找符合条件的稳定子集,将每次产的稳定基因子集和条件子集分别加在各自的集合中如此直到没有新的稳定的双聚类出现。这类算法特别适合基因芯片数据的挖掘与分析，如在分析结肠癌白血病的基因数据中，用此算法确定相关数据的子集，发现被掩盖和隐藏完整的数据集。这类算法实现上比较容易，可以根据不同的需求选择不同的传统聚类算法，算法更加灵活。但这类算法无法脱离聚类的全局性，不能很好的寻找局部模式。为克服基于传统聚类算法的缺陷，应该尽量避免传统聚类的全局聚类的思想。
(2)贪心迭代搜索cheng and church 首次使用这种方法寻找双聚类，提出了著名的 cc（cheng and church）[1]算法。cc算法通过逐步删除，可以使子矩阵的平均平方残基降低的行和列，得到一个最初的双聚类，然后逐步添加不会使子矩阵平均平方残基增加的行和列，得到一个较满意的双聚类。为找到更多双聚类算法使用随机数覆盖已经找到的双聚类，再进行删除和添加过程从而得到指定个数的双聚类结果。算法能够较快地得到用户指定数目的双聚类，而且能摆脱传统聚类的局限性更好的提高寻找基因数据中的大量有用的局部信息，适合找出具有全局一致或行列一致表达值的双聚类，但缺陷很明显，随机数替换会改变原始数据造成结果的不精确，也无法找到重叠的双聚类而且容易陷入局部最优。曲华[3]在实现了cc算法的前提下对算法的第二阶段扩展空间过程进行了改进，并对算法的两个重要参数alfa和delta的取值，结合实验数据集的实际运行效果进行了初步的讨论，提出了建议。delta是打分函数h的阈值，用来表示数据波动的一致性程度。它的大小直接影响矩阵聚类的质量。alfa在成批删除和添加过程中都用的到，它直接影响聚类的速度。曲华建议delta在[120,180]之间取值，alfa取值推荐在[1.8,3.2]之间。yang[4]等人对 cc 算法进行了改进，提出了 floc算法，该算法首先生成一定数量的种子，然后通过计算添加或删除某一行或列，每一步尽量使得双聚类的中间结果增益改变最大。floc算法可以找到可重叠的双聚类，但双聚类的结果好坏与运行时间极其依赖初始聚类，而这些聚类都是随机产生的。双聚类的贪心策略效率较高，但结果容易陷入局部最优。
(3)双聚类穷举策略严格的来说采用穷举方式寻找双聚类是不现实的。因为原数据矩阵的子矩阵数量一般都非常巨大，所以采用穷举法来寻找双聚类算法，多数为穷举小的子矩阵然后合并这些子矩阵的过程。wang[5]等人提出的δ-pcluster 算法先找到所有基因对和条件对中满足一定条件的双聚类，然后根据条件对的聚类结果对基因对的聚类结果进行剪枝，以基因对条件上的聚类结果剪枝，得到较少的小双聚类构建前缀树，通过后序遍历寻找双聚类。δ-pcluster 算法只为加法模型定义了收敛函数，多以只能限制在加法模型的双聚类上。samba[7]算法是另一个比较重要的基于穷举的双聚类算法，该算法使用统计模型将双聚类问题转化为一个完全平衡二分图搜索问题，再寻找基因表达谱模式，即寻找具有波动一致性的子矩阵问题转化为在二分图中找稠密子图问题。然而，这一算法的重要意义在于：对于基因表达谱进行双聚类分析，实质上是一个np-hard问题。所以，使用穷举策略的双聚类算法虽然能够找到较优的双聚类，但算法的时间复杂度会随矩阵规模的增大而呈指数增长。因此必须限制双聚类矩阵的大小，同时利用算法技巧优化穷举过程，才能保证算法的效率。
3. 研究的基本内容与计划
主要研究cheng 和church提出的biclustering算法，对算法的定义，数学模型理解到位。了解他们引入残基的概念。
对双聚类算法的主要步骤和框架进行分析
为算法的总体设计和实现环境学习matlab编程知识
4. 研究创新点
对CHENG andCHURCH算法用UCI数据集中的具体数据对算法进行性能分析
