最大生成树聚类算法研究

摘 要：在生物学研究中，需要对基因进行分类，以获得对种群固有结构的认识，有效鉴别基因表示数据的模式是研究DNA序列的重要基础。在已有最大树聚类理论基础上，引入模糊聚类思想，提出了最大树基因聚类算法，同时将该方法用于基因的聚类分析，实验结果表明它们是有效可行的。

关键词：最大生成树；模糊聚类；簇；相关系数；基因

中图分类号：TP311

文献标识码：A 文章编号：1672-7800（2015）005-0068-02

作者简介：刘芳（1979-），女，辽宁沈阳人，硕士，沈阳理工大学理学院讲师，研究方向为应用数学与计算机辅助几何设计。

0 引言

近年来，随着人们对生命科学的深入研究，开发出许多用于基因分析的工具[2]。利用这些工具，在不同的试验条件下，人们能够对成千上万个基因进行实时监控，以研究由于环境变化引起的基因变化。因此，首先对大量的基因表示数据进行分类，有效地鉴别基因表示数据的模式是研究DNA序列的重要基础。

聚类分析是统计学的一个分支，聚类算法能从空间数据库中直接发现一些有意义的聚类结构。聚类分析以相似性为基础，在一个聚类中的模式比不在同一聚类中的模式之间具有更多相似性。聚类分析算法有划分法、层次法、基于密度的方法、基于网格的方法和基于模型的方法等。但传统的聚类分析把每个待辨识的对象严格地划分到某个类中，这种硬划分的界线是分明的。而客观世界中存在大量界限不分明的聚类问题，它们的类属和性态存在着中介性，适合软划分。Zadeh提出的模糊集理论[3]为这种软划分提供了有力的分析工具，人们开始用模糊方法处理聚类问题，并称之为模糊聚类分析。常用的模糊聚类方法有传递闭包法、动态直接聚类法、最大树法[2]、基于摄动的模糊聚类方法FCMBP、系统聚类法、模糊C-均值法和模糊ISODATA算法。

本文把最大生成树法用于模糊聚类分析，最大生成树可以将数据聚类转换成树分割问题，通过删除最大生成树中某些具有最短距离的边，将最大生成树分为若干子树。本文讨论数据集的最大生成树表示，以及相应的聚类分析方法，并将其用于基因分类。

1 用生成树表示数据

2 最大生成树聚类算法

杨国惠[4]等人提出改进的中心聚类算法，本文在此基础上又提出最大生成树的基因聚类算法，同时通过实例验证了此算法可以得到较好结果。算法描述如下：具有较长边的两个点应属于同一个簇，具有较短边的两个点应属于不同的簇，并将被分割。由推论1，通过清除最大生成树中具有最小距离的k-1条边可得到k个簇，只要不同簇之间点的边距离小于簇内点的边距离，这k个簇则是全局最优解。但是，当不同簇没有用短距离边而是一系列长距离边连接，或者当存在“噪声”和孤立点数据时，该方法可能得不到最好的聚类结果。为了自动决定应该进行多少次有效分割，可在分割算法中检测新产生的子树是否为孤立点，通过消除孤立点并增加有效分割次数，最终获得正确的k个簇。

2.1 算法程序实现

开始

输入：数据集data和聚类数目K

begin

weight←compute_weight（data）；{计算距离矩阵}

t←{1，2，3，…，data_number}；

m=0；

查找weight中的最大值所在的行列值（x，y）；

while（m～= data_number-cluster_number）

begin

if（t（x）～=t（y））

begin

m=m+1；

tree（1，m）=x（1）；

tree（2，m）=y（1）；

tmin=min（t（x（1）），t（y（1）））；

tmax=max（t（x（1）），t（y（1）））；

for j=1：datanumber

if（t（j）==tmax）

t（j）=tmin；

end

weight（x，y） ←∞；

查找weight中的最大值所在的行列值（x，y）；

end

由tree得到聚类结果cluster；

计算聚类误差平方和cluster_err；

计算q值；

end

输出：聚类cluster、误差平方和cluster_err，q值；

结束

3 实验结果与评价

现选择酵母数据集[5]，此数据集中每个基因有79个属性（或79维），选择4个聚类共68个基因，这4个聚类分别为protein degradation（聚类C）、glycolysis（聚类E）、protein synthesis（聚类F）、 protein chromatin（聚类H）。

这个实验的目的是将最大生成树基因聚类算法应用到基因聚类中，同时说明该算法是可行、有效的。为了评价计算结果，使用以下定义。

误差平方和J（k）的定义如下：

J（k）=∑ki=1∑d∈Tid-center（Ti）2（5）

对于用户选择的目标函数和一个整数值K，计算最优k聚类k∈[1，K]，然后比较这些值。设J（k）代表选择的目标函数最佳k聚类的值，里面的k∈[2，K-1]，q（k）的最大值作为最自然的聚类数：

q（k）=J（k-1）-J（k）J（k）-J（k+1）（6）

距离测度采用公式（2）。

从图像中可以看到最大生成树基因聚类算法的最佳聚类数是4，分类的结果完全一致（见图1）[1]。

4 结语

本文在已有最大树聚类理论基础上，引入模糊聚类思想，提出了最大树基因聚类算法，对基因数据的聚类分析有重要的实践价值。特别对于生物学DNA序列信息、蛋白质结构信息的分类更具有意义。

参考文献：

[1] YING XU， VICTOR OLMAN， DONG XU.Clustering gene expression data using a graph-theoretic approach： an application of minimum spanning trees[J]. Bioinformatics， 2002， 18（4）：526-545.

[2] HATHAWAY R J，BEZDEK J C.Optimization of clustering criteria by reformulation[J].IEEE Transactions Fuzzy Systems，1995，3（2）：241-245.

[3] ZADEH L A. Fuzzy sets [J].Information and contral，1965（8）：338-353.

[4] 杨国惠，周春光，等. 最小生成树用于基因表示数据的聚类算法[J].计算机研究与发展，2003，40（10）：1431-1435.

[5] M B EISEN，P T SPELLMAN，P O BROWN，et al.Cluster analysis and display of gene-wide expression patterns[J]. The National Academic of Science，N W，1998.

（责任编辑：黄 健）