浅述双聚类算法

浅述双聚类算法

肖志军

（玉林师范学院计算机科学与工程学院，广西师范大学）

摘要：双聚类（Biclustering）算法在数据挖掘中是一个新兴的算法，对于矩阵类型的数据，其聚类效果很好。本文浅述了双聚类算法的基本特点，并提出了用迭代的双聚类算法对未知的数据进行分类，并对一组数据进行了测试，其分类表现不错。

关键词：双聚类；数据挖掘；迭代；分类

双聚类基础的可以定义为：给定矩阵M，寻找到矩阵M的多个子矩阵A，对于每一个A满足其指定条件进行聚类，最后得到需要的子矩阵B。双聚类方法可在以下一个或者多个问题下使用：1.仅仅是一小部分基因参与的有趣的细胞作用过程的聚类。2.对于一部分特定条件下的细胞作用过程体现为活跃的。3.单个基因可以在多重维度路径下并且全局限制条件对其没限制，可以是活跃的也可以是不活跃的。因此，对于双聚类也得遵循下面约束：1.基因簇按给定特定的部分条件能够被聚类出来。2.聚簇的条件按基因子集能够被清晰定义。3.聚簇不是被独占的和/或全体占有的：一个基因/条件可以属于一个簇或者都不属于在一个子集的条件/基因下。

一．基本分类

双聚类是应用各种算法得到在条件子集下具有共同表达模式的基因子集。得到的双聚簇一般具有以下几种样式：

1.常值型：即得到的双聚簇中基因的表达水平为一个常数，如表1.a

2.行或者列为一个常数：即在一个双聚簇中，每个基因的表达水平为一个常量，或者再一个条件下的所有基因的表达水平为一个常量。如表1.b和表1.c。

3.一致性变化：在一个双聚簇中，基因间得表达水平相差一个常量，双聚簇表1.e中的基因之间的表达水平成倍数关系。

表1聚类结果

发展至今，双聚类的各种启发式算法已经有很多了，但是总体来说，双聚类算法可以分成以下五类：1.结合行与列的迭代聚类法。2.分离和攻克法。3.贪心迭代搜索。4.双聚簇穷举法。5.分配参数鉴别法。

在基因表达矩阵中给定特定条件子集下去发现一个基因群子集所存在的相似度表达模式时，一般的聚类算法是无法实现的，但是此时用双聚类算法中的OP-Cluster算法就可以得出在特定条件子集下的基因群子集的相似长度，利用这个就可以计算出其相似度，最后把他们聚类成一个子矩阵（带权值的双向图）。

在双聚类算法中ChengandChurch算法是最具代表性的算法，他们认为双聚类搜索空间为2的m+n次方，其中m和n代表的是行和列，并且认为寻找所有双聚簇方阵是一个NP难题。ChengandChurch算法主要是通过贪婪算法来删除矩阵的行和列以达到想要的结果，他的算法最初描述如下：

定义：一个子矩阵称为一个δ-bicluster，如果H(I,J)≤δ(δ≥0)。一个bicluster的大小定义为S=|I|﹡|J|。其中H(I,J)为A_IJ的均方残差。

输入：基因表达水平矩阵A，预设值δ＞0

输出：A_IJ，其中H(A_IJ)<δ

初始化：A_IJ=A

WhileH(A_IJ)>δ

计算删除每行和每列后的矩阵的H值，选择使H值减少幅度最大的行或者列，删除该行或者该列，返回A_IJ，直到找不到这样的行或者列为止。

双聚类也可用于基因表达的进化演算上面去，在基因的进化演算中使用到双聚类的一个算法叫做SEBI算法，它可以发现双聚簇通过表达数据。而且SEBI算法在进行数据集观察和实验时不需要设置参数，他可以在一个实验条件集中清晰的找出基因集合的上相似约束和下相似约束。总的来说SEBI算法可以在基因表达数据中找出狡猾难寻的和扩大缩小后的模式。

双聚类运用的领域也是很广的，他不单单是用在我上面提到的基因表达上，因为他主要解决了基因表达问题，所以上面都是以这个为例子来说。双聚类可以应用在生物上也可以应用在非生物学上，在生物学上很多学者都已经用大量的实验证实是相当有用的。比如用微阵列技术收集酵母菌细胞和人类细胞，研究他们在特定条件下的基因表达等级。在非生物学上的应用也很多，比如信息恢复，文本挖掘，协同过滤，数据库搜索，知识挖掘等方面都有广泛的应用。GaulandSchader在此中介绍了双聚类于市场调查的关联性，他们用数据基准阵列去封装营销中收集到的数据，然后通过双聚类算法来得出给定条件下的子矩阵，如此实现调查。

但是双聚类在对于边界噪声点比较多，实验效果差，或者是图形图像比较模糊的数据还是很难进行聚类的，这个同时也约束了他的使用范围。我想这个可以通过结合模糊聚类的话可能可以解决一些问题。而且微阵列通常不满足正态分布，因此在数据分析上面也有一定的局限性。我认为微阵列的不足可以尝试使用贝叶斯算法统计来试试。

二．相关工作

可以尝试用双聚类算法对未知的数据进行分类。如在生物信息中有矩阵类型的数据，行表示样本，列代表基因，那么这类数据是可以用双聚类算法对其进行归类和划分的。算法会用到迭代对类别进行区分。使用威斯康辛乳腺癌数据集，有569个样本，30个基因，分为两类http://archive.ics.uci.edu/ml/machine-learning-databases/breast-cancer-wisconsin/wdbc.data，以上是数据地址。算法步骤如下：

输入：数据矩阵M,残基选择的阈值H,基因占总样本的比为T。

输出：多个子矩阵。

1.计算矩阵M的残基，如果小于H，直接输出，否则进入2.（直接输出就是分为一类了）

2.找出行或者列中残基最大的，进行删除，直到子矩阵M1的残基小于H为止。

3.对M1进行行或者列的增加，计算与当前矩阵行或者列对应的行或者列的残基，把最小的进行增加，直到预判增加后子矩阵M2的残基大于H，则最后这一行或者列不添加。

4.对找出的子矩阵M2进行基因占比计算，小于T则终止（第一个就小于T则说明应全部归为一类或者T的选择不合适或者算法不适用这数据），大于T则在原始矩阵M中删除M2所包含的列（样本）得到M3。

5.迭代地对M3进行2-4.

6.直到出现小于T，则判定无其他分类，剩余的归为一类。

用了准确率，召回率，支持数，这三个指标来衡量分类准确性。

表2结果

precision

recal

support

1

0.941

1.000

272

2

1.000

0.932

197

上表结果可以看出分类的准确性是比较高的，都达到了90%以上。

三．总结

双聚类在生物上的发展是有很大很大的空间的，当然在其他领域上也是一样，这是一个很广很实用的方法，而且现在也只是双聚类发展的起步，他将会在以后的研究中迅速发展起来，更加全面更加实用。

参考文献

[1]Y.ChengandG.M.Church.“Biclusteringofexpressiondata”.InProc.ISMB’00,pages93–103.AAAIPress,2000.

作者简介：肖志军（1975-），男，江西崇义人，高级工程师，硕士，主要研究方向：数据挖掘，人工智能。