第4卷第6期 智能系统学报 Vol.4 No.6 2009年12月 CAAI Transactions on Intelligent Systems Dec.2009 doi:10.3969/i.issn.16734785.2009.06.013 支持向量数据描述的基因表达数据聚类方法 季瑞瑞，刘丁 (西安理工大学信控中心，陕西西安710048) 摘要：为改善传统的基因表达数据聚类方法正确率偏低的问题，研究了支持向量数据描述(SVDD)算法在基因表 达数据聚类中的应用，该方法通过寻找最优分类超球实现对数据集的有效聚类.将类间信息融人入聚类有效性评估准 则中，通过模拟退火优化算法寻找SVDD算法中的最优核函数参数和惩罚因子，在训练时引入非样本数据提高运算 效率.对酵母细胞生长周期的基因表达数据集的仿真实验结果表明，在新的聚类有效性评估准则下进行参数寻优， 能够更快更好地得到最佳参数，同时，算法具有聚类精度高和运算速度快的优点. 关键词：基因表达数据；支持向量数据描述；聚类；模拟退火 中图分类号：TP18文献标识码：A文章编号：16734785(2009)060544-05 Improved gene expression data clustering using a support vector domain description algorithm JI Rui-rui,LIU Ding (Center of Information and Control Engineering,Xi'an University of Technology,Xi'an 710048,China) Abstract:The application of the support vector domain description (SVDD)algorithm in gene expression data clus- tering was proposed as a means to improve the low accuracy of current clustering methods.This method effectivly clustered the dataset by finding the optimal separating hyper-sphere.Inter-class information was introduced into the current clustering assessment criterion in the form of a minimum within-class distance.The simulated annealing (SA)algorithm was used to find the optimal kernel function parameter and the punishment factor of the SVDD algo- rithm.Non-sample data were added in training to increase computational efficiency.Simulation results using the yeast cell cycle expression dataset showed that optimal parameters can be obtained faster and more accurately with the new assessment criteria.Similar improvements were found in clustering accuracy and speed. Keywords:gene expression data;SVDD;clustering;simulated annealing 随着人类基因组计划(HGP)的顺利实施与基 因，这样利用聚类结果可以对未知功能的基因进行 因芯片技术的发展，人们可以观察到成千上万的基 划分和识别. 因在某个生命现象中的表达情况.由于生物体本身 传统的聚类方法虽然能够得到不错的效果，但 的复杂性，这些数据往往是高维、海量的，如何从这 是存在一定的弊端，如：需要预先指定聚类数目；对 些数据中挖掘出有用的信息，发现基因的功能具有 边界和噪声数据敏感以及误判问题；如果需要加入 重要的研究意义.目前对基因表达数据的处理主要 新的类别，必然影响整个系统.起源于SVM的支持 是进行聚类分析.常用的聚类算法有K-均值法(K 向量数据描述算法(support vector domain descrip means)I、自组织映射法(S0M)[23]、神经网络、 ion,SVDD)9o把聚类看作是样本的“认知”，通过 主元分析、支持向量机(SVM)6、动态模型)、隐 寻找覆盖样本在特征空间的最优超球实现对数据的 马尔可夫模型8]等，其最终目的是寻找多类目标样 聚类，不仅减少了误判率，同时新类别的介入也不需 本集的最佳划分，同一类一般是具有已知功能的基 重新训练全部样本.研究了基于SVDD的基因表达 数据的聚类问题，改进了聚类有效性评价准则，并以 收稿日期：200906-23. 此作为寻找SVDD参数的准则，通过优化算法寻找 通信作者：季瑞瑞.E-mail:heziri423@163.com. 最佳参数，提高了计算效率，改善了误判问题，从而
第6期 季瑞瑞，等：支持向量数据描述的基因表达数据聚类方法 ·545· 提高了对于未知功能基因的认知能力： Vapnik的理论)，利用满足Mercer条件的K(x,x,) 代替内积运算，将样本映射到一个高维特征空间，当 1支持向量数据描述 选择合适的核函数时，可以得到关于样本数据的最佳 支持向量聚类的基本思想是通过在特征空间中 描述.引入核函数后，上述的目标优化问题变为 寻找包围目标样本点的超球体，并通过最小化该超 maxL 球体的体积，使得目标样本点尽可能的被包围在超 ∑aK(·)-公 K(x·x）, i=1=1 球体内部，而非目标样本点尽可能的在超球体外部， (5) 从而实现不同类之间的有效划分.超球体内的点认 (6) 为是目标类数据，超球体外的点被认为是非目标类 数据，位于球表面上的点就是支持向量.SVDD采用 只有少量的样本满足上式的等号，其对应的 超球来覆盖样本数据，使得聚类的收敛域更小，聚类 不为0，称之为支持向量.利用任一支持向量可以求 效果更精确，从而较好地解决误判的问题。 出超球的半径： 1.1问题描述 R2=K(xg·x)-2∑a,K(x·x)+ SVDD问题描述如下：设有n个样本数据，包围 这些样本的最小超球的球面中心为a,球面半径为 2aaK·). (7) i=1=1 R,则寻找该最小超球的过程变成求解以下的目标 对于一个测试样本，可以依据下面的条件判断 函数： 是否接受其为该类对象，如果满足 min[R2+C∑专：]， (1) l云-a2=(z·z)-2∑a,K(x·x)+ 8.t.l(x:)-a川2≤R2+点，点：≥0，Hi(2) 式中：C为惩罚因子，：是为了提高超球的鲁棒性， ∑a,aK(x·）≤R, 允许包含非目标样本而引入的松弛变量： =1J=1 则认为是该类样本，否则拒绝， 将上述问题引入Lagrange乘子a&:和y:,转化成 根据Tax和Duin的结论9)：高斯型核函数相对 Lagrange极值问题： 于线性核函数和多项式核函数具有更好的性能.其 (R,a5a,）=R+cg. 1- 形式为K(x,x)=e2.本文采用的是高斯型核 含aR+--2a+a]-氵 函数 1.2参数选择 式中：：≥0，y≥0. 由上可知，聚类的好坏取决于如何调节惩罚因 求解该式的极值，分别对R、α和：求偏导并令 子C和高斯核函数的宽度σ.惩罚因子C实现错分 其为0，得 样本的比例和算法复杂度之间的折衷.它的选取一 2a=1,a=2 aixi, 般由具体的问题而定，C越小，对经验误差的惩罚 C-a;-yi=0,Vi. 小，学习的复杂度小而经验风险值较大，超球的边界 由于a&≥0，Y:≥0，可以将C-a:-Y:=0转换 越平滑，得到的支持向量的个数越少.SVDD性能的 成0≤a:≤C. 优劣还受到高斯核参数σ的影响，σ越小，超球的 重新改写上面的等式，整个问题变为求解式(3)： 边界越紧致，得到的支持向量的个数越多.如何得到 mL=立a4(x‘x)-。】 最佳的参数，日前还没有统一的方法，常用的方法是 a（x:·）, 采用试凑法，针对某个特定的问题，通过多次尝试得 (3) 到满意的结果，例如交叉验证法和网格搜索法2] 本文将聚类评估准则作为目标函数，采用智能算法 s.l.∑a:=1,0≤am:≤C (4) 进行参数寻优，从而避免反复凑试参数的繁琐和耗 由于实际的样本分布不一定是球形的，根据 时，并且通过在酵母基因表达数据的聚类分析中进
·546 智能系统学报 第4卷 行实验，验证了算法的有效性 证超球边界两边都得到支撑，同时对于边界噪声也 有一定的抑制作用， 2改进的支持向量数据描述算法 加入非目标样本类别信息后的约束条件变为 2.1聚类有效性评价准则 y:(R2+5:-‖x-a‖2)≥0,5≥0，Vi, 评价聚类算法的有效性，即能否将基因正确的 (11) 聚类，对于选择聚类算法来预测未知基因的功能有 「1，目标样本； 一定的指导意义.目前，对于生物数据聚类评价使用 式中：y={-1,非目标样本 最多的是由Yeung提出的聚类有效性的内部检验方 此时的Lagrange极值问题变为 法—FOM法B).假设n个基因被聚成k类：C, C2,·,Ck,令R(g;e)表示原始数据矩阵中基因g在 maxL=R2+C∑点- 条件e(e=1,…,m)下的表达水平，uc(e)表示C:类 内的基因在条件e下的平均表达水平，则 三a[+6-(》 FOM(k)= ∑FOM(e,k). 2a+a)]-Y, 8=1 式中： 式中：a≥0，Y:≥0. 求解该式的极值，分别对R、α和：求偏导并令 FOM(e,k)= L方∑(R(x,e)-e(e)2 其为0，得到 Nn台 (8) ag.-1.a =1 FOM(e,k)为条件e下所有基因表达水平距离 C-aiyi-Yi=0,Yi. 均差平方和的方根，反应类内的变异.FOM(k)表示 如果设a=αy:,并用核函数代替内积运算，则会得 把整个数据集聚成k类时，所有类的类内变异总和. 到一个和式(5)形式一样的目标函数， FOM越小就表明类内的变异越小，算法的聚类效果 越好 maxL=∑K(x·x) 由于FOM法并没有考虑使用类间的信息，本文 将类间信息融入聚类有效性评价中，定义Dis(k)反 ∑a,K(· (12) =1=1 映类间的变异： 可以看出，引入非目标样本，只是增加了训练样 Dis(e,. 本的数量，并没有影响训练的复杂度。 Dis()= 2.3参数的优化 式中： 模拟退火算法是一种全局最优算法，本文利用 1(ue.(e)-e,(e)2(9) 该方法来搜索SVDD的核函数参数σ和C.采用上 Dis(e,k)= 述的聚类有效性评价准则作为适应值，通过模拟退 式中：4c,(e)表示C:类内的基因在条件e下的平均 火算法进行搜索迭代，找到满意的SVDD参数.其具 表达水平 体步骤和算法如下： 定义： 1)初始化参数设置； Val FOM()-Dis(k). (10) 2)随机产生初始SVDD模型，计算其适应值ft- 如果类内变异越小，类间变异越大，则Vl值越 ness Val; 小，聚类的质量越高.本文将Vl作为评价聚类算法 3)通过随机扰动产生新的SVDD模型，计算新 的目标函数，用来引导SVDD的参数选取， 的适应值finess'; 2.2非目标样本的引入 4)按照Metropolis准则接受或放弃新的参数； 为了提高算法收敛的速度，本文采用有监督的 5)重复3)和4)完成一次Metropolis迭代过程； SVDD进行训练，即加入非目标样本类别信息，以保 6)判断适应值是否满足要求，如果满足，则算
第6期 季瑞瑞，等：支持向量数据描述的基因表达数据聚类方法 ·547. 法结束，输出SVDD模型；否则，按照一定的退火方 表2不同聚类算法正确率比较 案衰减t,重复3)、4)、5)继续寻优，直至得到满意的 Table 2 Accuracy comparison of different clustering methods 结果 聚类 聚类正确率/% 算法 G G,/MM/G S 3 S/G2平均值 实验结果与分析 Aag器lo- 79.0363.9358.3560.8754.01 63.24 3.1实验数据 merative 本文采用已知类别的446条酵母(Yeast)细胞 K-mean84.2176.9268.4272.73 70.82 74.62 生长周期的表达数据作为实验数据，每个基因表达 FCM 90.7088.8976.9269.2366.67 78.48 数据是80维的，分别表示不同的实验条件下、不同 SOM 97.2293.3365.0064.7180.00 82.80 时间，点的基因表达水平值，根据其细胞周期内的表 SVDD 10090.4887.8985.8592.12 91.27 达峰值分为5类：166个G,类型、115个S类型、56 图1是各种聚类算法的Val值在不同类别数下 个G2类型、42个M类型、67个M/G1类型.其中G: 变化的曲线.由于Val融入了类间信息，对聚类的有 生长期(growth);S:合成期(synthesis);M:分裂期 效性评价更加客观和全面.图1中的曲线高低和表 (mitosis).在不同阶段可能会有交界.在聚类分析之 2的结果基本一致，说明使用Vl指导聚类算法的 前，先对基因表达数据进行了归一化处理 选择有一定的意义.从图1中也可以看出，本文算法 3.2结果与分析 的Val值最小，这不仅由于SVDD算法本身的特点， 对于多类分类问题，当训练某一类的最小超球 而且在训练时引入非目标样本，使得超球更加紧凑， 时，非目标样本从其他各类中利用“自举法”产生， 对于算法的收敛也有促进作用。 采用本文算法对实验数据进行聚类，仿真结果如下. 15 14 表1对比了网格搜索法和模拟退火法在SVDD 13 Agglomerative 12 参数寻优中的结果，与传统的网格搜索法相比，采用 11 SOM 10 模拟退火算法来确定SVDD参数不仅缩短了训练时 9 间，减少了支持向量的数目，提高了计算效率，而且一 8 定程度上改善了训练样本和测试样本的聚类正确率. 6 665588672880068 5 表1网格搜索法和模拟退火方法的比较 510市202530 类别数 Table 1 Comparison of cross-validation and SA 图1各聚类算法的Val值 性能比较 网格搜索法 模拟退火法 Fig.1 The Val of different clustering methods (C,σ)最优值 (21.365,2.245) (23.487,2.341) 4 结束语 训练时间/s 8.68 2.79 支持向量数/个 138 $ 聚类是基因表达数据分析的重要步骤，通过聚 训练样本 类分析，可以预测基因功能，构建基因调控网络，进 93.96 94.14 聚类正确率/% 而对内部的生命现象进行解释.采用支持向量数据 测试样本 89.83 89.94 描述算法，通过寻找最优超球来覆盖样本数据，较好 聚类正确率/% 地解决了常用聚类算法存在的误判问题.为了避免 表2给出了不同聚类算法对测试数据集的聚类 寻找核函数参数和惩罚因子的繁琐工作，改进了聚 正确率，可见，SVDD算法的聚类正确率相对于常用 类有效性评估准则，以此作为目标函数，通过模拟退 的聚类算法有了很大提高，验证了通过寻找半径最 火优化算法得到SVDD的参数，在训练过程中加入 小的最优超球来覆盖属于同一类的数据样本点的 非样本数据，从而提高了计算效率、聚类精度和对边 SVDD算法可以得到更紧凑的聚类结果，不仅减少 界噪声的抑制能力.将本文算法应用在酵母基因表 了误判率，同时，这种类似于认知样本的聚类算法， 达数据聚类分析中，结果验证了其有效性和快速性， 当新的类别出现时，不需要重新训练全部样本
·548· 智能系统学报 第4卷 vector machine classification for large data sets via mini- 参考文献： mum enclosing ball clustering[J].Neurocomputing,2008, [1]BEISEN M,SPELLMAN P T,BROWN P O,et al.Cluster 71:611-619. analysis and display of genome-wide expression patterns [11]边肇祺，张学工.模式识别[M].2版.北京：清华大学出 [J].Proc Natl Acad Sci,1998,95(12):14863-14868. 版社，2002：296-304. [2]P TAMAYO,SLONIM D,MESIROV J,et al.Interpreting [12]BOSER B E,GUYON I M,VAPNIK V N.A training al- patterns of gene expression with self organizing maps[J]. gorithm for optimal margin classifier[C]//Proc 5th Annu Proceedings of National Academy of Sciences,1999,96(6): ACM Workshop on Compute Learning Theory.Haussier, 2907-2912. Ed,1992:144-152 [3]SUGIYAMA A,KOTANI M.Analysis of gene expression [13]YEUNG K Y,HAYNOR D R,RUZZO W L.Validating data by using self-organizing maps and k-means clustering clustering for gene expression data[J].Bioinformatics, [J].Neural Network,2002(5):1342-1345. 2001,17(4):309-318. [4]HERRERO J,VALENCIA A,DOPAZO J.A hierarchical [14]岳峰，孙亮，王宽全，王永吉，左旺孟.基因表达数 unsupervised growing neural network for clustering gene ex- 据的聚类分析研究进展[J].自动化学报，2008,34 pression patterns[J].Bioinformatics,2001:17(2):126- (2):113-120. 136. YUE Feng,SUN Liang,WANG Kuanquan,WANG [5]YUNG Y,RUZZO W.An empirical study on principal com- Yongji,ZUO Wangmeng.State-of-the art of cluster analy- ponent analysis for clustering gene expression data[J]. sis of gene expression data[J].Acta Automatica Sinica, Bioinformatics,2001:17(9):763-774. 2008,34(2):113-120 [6]BURGES C J C.A tutorial on support vector machines for 作者简介： pattern recognition[J].Data Mining and Knowledge Discov- 季瑞瑞，女，1978年生，讲师，博士 ey,1998,2(2):147. 研究生，主要研究方向为人工智能与模 [7]WU Fangxiang,ZHANG W J,KUSALIK A J.Dynamic mod- 式识别、生物信息处理与建模.发表学 el-based clustering for time-course gene expression data[J]. 术论文6篇，其中被I检索3篇. Journal of Bioinformatics and Computational Biology,2005,3 (4):821-836. [8]JI X L,YUAN Y,LI Y D,SUN Z R.HMMGEP:clustering gene expression data using hidden Markov models [J]. 刘丁，男，1957年生，教授，博士生 Bioinformatics,2004,20(11):1799-1800. 导师，中国人工智能学会常务理事，主要 [9]TAX D M J,DUIN R P W.Support vector domain descrip- 研究方向为复杂系统的建模与控制、智 tion[J].Pattern Recognition Letters,1999,20 (11/13): 能机器人、系统控制等.发表学术论文 1191-1199 100余篇，其中被SC1,EI检索50余篇. [10]CERVANTES J,LI Xiaoou,YU Wen,LI Kang.Support
