基因分类

基因分类（精选3篇）

基因分类 篇1

摘要：提出了一种基于遗传算法 (GA) 优化支持向量机 (SVM) 分类决策树的用于肿瘤基因分类的新方法。该方法针对基因表达数据样本少维数高的特点, 采用了支持向量机分类间隔作为遗传算法适应度函数。利用遗传算法在每一决策树结点自动选择最优或近优的分类决策, 实现了对决策树的优化。试验结果表明, 在样本有限的情况下, 与传统的方法相比, 该方法比单个决策树算法具有更高的分类精度。

关键词：遗传算法,基因表达谱,决策树,支持向量机

0、引言

随着基因芯片技术的发展，采用数据挖掘技术对基因表达谱数据进行分析，挖掘和发现其中蕴含的信息和知识，是当前生物信息学研究的重点课题。肿瘤基因表达谱数据具有样本少，维数过高的特点，每个样本都记录了组织细胞中所有可测基因的表达水平，但实际上只有少数基因真正同样本类别相关，包含了样本分类信息，这类基因称为特征基因。目前人们对该问题已进行了一定程度上的探索，然而，如何在成千上万个基因表达谱中有效选出样本的分类特征基因，一直是肿瘤基因表达谱分析中的难点所在，仍有待深入研究。

决策树是数据挖掘中一种常用的分类方法，虽有些学者对决策树算法应用到基因表达谱分类进行了初步研究，但其仅将决策树之间的节点进行交叉，整个搜索空间是固定在有限的范围内，而这个范围又是由初始样本集确定的。另外有些实验中虽然产生变异节点，但是搜索的空间太大，不易产生局部最优解。因此，考虑到有限的样本会导致决策树算法无法很好的区分整个数据集，本文尝试引入遗传算法（GA），结合决策树（SVM）和遗传算法（GA）的优势，利用遗传算法的全局搜索能力优化决策树，获取最优的参数组合，并利用决策树算法在处理连续属性时的优势来改进遗传算法中变异算子，减少搜索时间，提高分类精度。

1、问题描述

基于肿瘤基因表达谱数据的分类问题，就是根据已知的肿瘤基因样本数据，划分为训练集和测试集。利用遗传算法优化支持向量机决策树算法构建分类器，对测试集数据进行分类分析，确定肿瘤的类型。基本步骤如下图1所示。

2、遗传算法优化决策树的原理

遗传算法 (Genetic Algorithm，简称GA) 是近几年发展起来的一种崭新的全局优化算法，它借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。由于仅采用单个决策树算法对基因表达数据进行分类时，不能有效的对全部数据进行分类，分类精度较低。而遗传算法由于具有强大的全局优化搜索功能，能使个体之间的信息进行交换，对决策树进行调整和重新组合，进而出现更优的决策树。

2.1 遗传算法的设计

1）初始种群的产生：由于种群数目过大增加遗传算法的运算时间，同时会使种群形态过于分散，使算法收敛困难，所以我们选择种群规模的大小为训练样本的30%。

2）编码：本文采用二进制编码的策略来实现原始训练样本集类别的编码。把所有的染色体表示成一个长度为K (K由初始种群数目决定）的二进制字符串，每一个二进制位是0或者1。1表示基因在特征基因子集中，而0表示不在其中。

3）适应度函数的确定：染色体的适应度函数由基因子集的分类精度和基因子集大小决定。采用精英机制，将适应度最高的15%挑选出来，作为新一代种群。

4）遗传算子：遗传算法是根据优胜劣汰的原则选择种群中的优秀个体。为了使染色体完整地包含当前决策节点训练样本所属的类别种类，又避免染色体基因出现重复，本算法只采用了选择操作算子和变异操作算子。

1) 选择算子。如果还没有满足遗传算法终止的条件，根据"适者生存"的原理，从上一代种群的遗传结果中繁殖适应度较大的染色体个体进入下一代种群的继续进行遗传操作。显然适应度高的个体，繁殖的下一代染色体数目较多;而适应度较小的染色体个体，繁殖的数目较小，甚至被淘汰。

2) 变异算子。变异算子即在染色体中引入新基因以促进种群的进化。根据选择概率和适应度高的原则从父代子群中选择染色体。一旦选中某个染色体进行遗传操作，, 则随机选择其中1个或者多个基因进行变异。单个基因变异概率较高，而多个基因变异一般赋予较低的概率。此外，为了防止同一条染色体中出现重复基因，染色体中某一比特位上的基因发生变异时，变异后的基因编码对应的比特位的基因应相应地变换为变异比特位的原基因编码。

2.2 遗传算法优化决策树生成算法

将遗传算法（GA）应用到支持向量机（SVM）优化中时，决策树生成算法的基本步骤如下：

SETP 1:将全部训练样本集所属类别按实值编码策略进行编码，并在根节点调用GA将原始训练样本所属类别划分为两类。

SETP 2:判断各子节点是否只包含一类样本，若是，则转向步骤4，反之转向步骤3。

SETP 3:若结点包含两类以上样本，剔除其父节点染色体中本子节点不包含的类别对应的基因，形成新的染色体，并调用遗传算法（GA）将本节点的样本所属类别划分为两类。转向步骤2。SETP 4:循环结束，生成最优决策树。

3、实验结果及说明

本实验中所有的数据均采用Singh D等人公布的前列腺癌基因表达谱数据集，做为实验样本集。前列腺癌基因表达谱数据集共有102个样本，其中50个正常样本，52个患病样本，每个样本均含12700个基因的表达数据。将这个数据集划分为训练样本集和测试样本集，50个正常样本中，28个作为训练样本，21个作为测试样本。52个患病样本中，31个为训练样本，21个为测试样本。如图2所示。

本文是基于训练集而不是全部的数据集的数据来挑选特征基因，然后用GA/SVM算法设计的分类模型对测试集的样本进行测试，从而保证了实验的客观性。由于遗传算法是随机方法，不能确保每次运行的结果都能得到相同的特征子集。因此，本文求取15次运行结果的均值和标准差来评价GA/SVM方法的性能。对前列腺癌基因表达谱数据集的测试集运行GA/SVM方法15次，选出了15个基因子集，并统计这15个子集的平均性能指标。实验中的算法均采用VC++编程实现。从结果中很明显可以看到（如表1所示），对于不同的样本抽样和种群大小，通过遗传算法优化后的精度要比普通的单个决策树算法的精度高。对于单个决策树生成算法，每个子集包含特征基因为64个，平均分类精度仅为81.39%，而优化后的决策树精度为95.35%，高于单个决策树生成的精度。

实验证明，通过遗传算法对决策树进行优化，能得到更高的精度。尤其是待分类数目较多，在样本有限的情况下，通过对决策树的优化得到更加满意的结果。

3、结束语

本文提出的遗传算法（GA）优化支持向量机（SVM）决策树算法参数，获取了最优的参数组合，改进遗传算法的变异算子，减少了搜索时间。把该方法应用到前列腺癌基因表达谱数据集的分类中，实验结果表明了其有效性和可行性，对肿瘤的临床诊断和生物医学研究起到一定的参考作用。

参考文献

[1]Singh D, Febbo P, RossK, et al.Gene expression correlates of clinicalprostate cancer behavior[J].Cancer Cell, 2002, 1 (2) :203-209.

[2]Golub R R, Slonim D K, Tamayo P, et al.Molecular classification ofcancer:class discovery and class prediction by gene expression monitoring[J].Science, 1999, 289:531-537.

[3]Alon U, Barkai N, Notterman D A, et al.Broad patterns of geneexpression revealed by clustering analysis of tumor and normal colon tissuesprobed by oligonucleotide arrays[J].Proc Natl AcadSci Usa, 1999, 96:6745-6750.

[4]Takahashi F, Abe S.Decision-tree-based multiclass support vectormachines[C].Proc of the 9th Int Conf on Neural Information Processing.Singapore, 2002, (3) :1418-1422.

[5]何爱香, 朱云华, 安凯.基于遗传算法和支持向量机的肿瘤分子分类[J].数据采集与处理, 2007, 22 (1) :84-89.

[6]连可, 陈世杰, 周建明.基于遗传算法的SVM多分类决策树优化算法研究[J].控制与决策, 2009, 24 (1) :7-12.

基因分类 篇2

1 DNA条形码技术

2002年Tautz提出DNA分类的概念, 建立以DNA序列为基础的物种识别体系。随后, Herbert等提出DNA条形码概念 (DNA Barcoding) 。Herbert倡导利用线粒体COⅠ基因 (线粒体细胞色素氧化酶亚基I基因) 作为通用序列, 建立全球性的物种鉴别系统。

2003年, 在美国的冷泉港, 全球的生物学专家经过两次会议的讨论, 提出了国际DNA条形码计划--i BOL (International Barcode of Life) 。2004年, 拥有来自50多个国家170多个组织成员的"生命条形码联盟"成立。目前, 还有针对鸟类、鱼类、鳞翅目昆虫、极地生物的条形码计划在陆续实施中。2007年5月, 涵盖了序列信息、物种描述、地理分部信息、标本图片等信息的生命条形码数据系统 (Barcode of Life Data Systems, BOLD) 在加拿大圭尔夫大学正式筹建。截止到目前为止, BOLD中已收集到170185个种类, 与条形码有关的1930087条序列, 这其中超过70%的为昆虫。

2 COⅠ基因

COⅠ基因是全球性物种鉴别系统的通用序列。与其他的基因片段相比, COⅠ基因有许多优点, 序列长度适中且既相对保守又足够的变异。

2003年, Herbert等首次分析了200个亲缘关系较近的鳞翅目昆虫的COⅠ片段, 结果显示, COⅠ片段能够全部的鉴别出这些鳞翅目昆虫。同年, Herbert又基于COⅠ片段对鳞翅目的882种昆虫进行了研究分析, 推算出鳞翅目昆虫的种间遗传差异为6.5%。此后, DNA条形码广泛用于了昆虫学的分类和坚定, 尤其是在鳞翅目昆虫中。鳞翅目DNA条形码协会 (All Leps Barcodes of Life, http://www.lepbarcoding.org) 目前已收录了15906个鳞翅目物种超过39万条条形码序列, 这些都是序列全部是基于COⅠ片段。

3 COⅠ基因在我国昆虫分类中的应用

鳞翅目昆虫是利用DNA条形码技术进行研究的最多的昆虫类群。诸立新等利用COⅠ基因对尾凤蝶属 (鳞翅目, 凤蝶科) 四种蝴蝶进行了分子系统学研究;冷海楠等也利用COⅠ基因对松毛虫属部分地理种群进行了分类与系统学研究。此外, 我国学者利用COⅠ基因对昆虫纲其他科属种类进行了大量的研究。付景和张迎春等对鞘翅目瓢虫科4个亚科27种瓢虫进行了分类学研究;郑福山等对小萤叶甲属部分种类进行了分子系统学研究;潘程莹等利用COⅠ基因对直翅目斑腿蝗科7种蝗虫进行了分类学研究。以上研究均取得预期的结果, 结果表明COⅠ基因是开展昆虫分类研究的一种有效的必要的分类手段。

4 COⅠ基因在我国未来昆虫分类中的展望

物种的鉴定分类工作是一门基础科学工作, 是很多科学研究开展的基础。昆虫作为地球上最大的动物群体, 传统的分类手段已经不能满足当前科研工作的需要了。DNA条形码技术的出现, 很好的解决了这一难题, 作为通用序列的COⅠ基因必将在未来的昆虫分类学工作中起到极其重要的作用。

在国际上, BOLD系统正以每年300万条徐磊, 30万个样本的速度扩充。国外利用COⅠ基因进行的昆虫分类鉴定工作已经取得极大的成果, 这些生物信息数据, 不但可以为坚定物种服务, 同时能够获取大量的为系统发育学、种群遗传学等学科服务的数据。在我国, 这项工作正处于发展的起步时期, 尚没有系统化、规模化。因此, 及早的建立一个属于我国的完整类群的条形码数据库非常必要。这个数据库的建立将不仅对昆虫分类学上有着极大作用, 也将在生物多样性调查研究、保护生物学等领域起到巨大的作用。

摘要：本文介绍了近年来在昆虫分类学领域研究热点之一的DNA条形码技术, 综述了我国基于COⅠ基因进行的昆虫分类学研究, 并对COⅠ基因对我国昆虫分类学的未来应用进行了展望。

关键词：DNA条形码,COⅠ基因,昆虫分类

参考文献

[1]彩万志, 庞雄飞等.普通昆虫学[M].北京:中国农业大学出版社, 2001.7[1]彩万志, 庞雄飞等.普通昆虫学[M].北京:中国农业大学出版社, 2001.7

[2]Hebert PDN, Cywinska A, Ball SL, deWaard JR, 2003a.Biological i-dentifications through DNA barcodes.Proc.R.Soc.Biol.Sci.Ser.B, 270:313-321.[2]Hebert PDN, Cywinska A, Ball SL, deWaard JR, 2003a.Biological i-dentifications through DNA barcodes.Proc.R.Soc.Biol.Sci.Ser.B, 270:313-321.

[3]Hebert PDN, Ratnasingham S, deWaard JR, 2003b.Barcoding ani-mal life:cytochrome c oxidase subunit 1 divergences among closelyrelated species.Proc.R.Soc.Biol.Sci.Ser.B, 270, S96-s99.[3]Hebert PDN, Ratnasingham S, deWaard JR, 2003b.Barcoding ani-mal life:cytochrome c oxidase subunit 1 divergences among closelyrelated species.Proc.R.Soc.Biol.Sci.Ser.B, 270, S96-s99.

[4]诸立新, 吴笑兵等.基于COⅠ基因部分序列对尾凤蝶属 (鳞翅目, 凤蝶科) 四种蝴蝶分子系统关系及相关问题的探讨[J].动物分类学报, 2006, 31 (1) :25-30.[4]诸立新, 吴笑兵等.基于COⅠ基因部分序列对尾凤蝶属 (鳞翅目, 凤蝶科) 四种蝴蝶分子系统关系及相关问题的探讨[J].动物分类学报, 2006, 31 (1) :25-30.

[5]冷海楠, 迟德富等, 松毛虫属部分地理种群COⅠ基因序列分析[J].东北林业大学学报, 2010, 38 (11) :105-108.[5]冷海楠, 迟德富等, 松毛虫属部分地理种群COⅠ基因序列分析[J].东北林业大学学报, 2010, 38 (11) :105-108.

[6]付景, 张迎春.27种瓢虫mtDNA-COⅠ基因序列分析及系统发育研究 (鞘翅目:瓢虫科) [J].昆虫分类学报, 2006, 28 (3) :179-186.[6]付景, 张迎春.27种瓢虫mtDNA-COⅠ基因序列分析及系统发育研究 (鞘翅目:瓢虫科) [J].昆虫分类学报, 2006, 28 (3) :179-186.

[7]郑福山, 杜予州等.基于线粒体COⅠ基因序列的小萤叶甲属部种类分子系统学研究[J].昆虫学报, 2007, 50 (5) :507-507.[7]郑福山, 杜予州等.基于线粒体COⅠ基因序列的小萤叶甲属部种类分子系统学研究[J].昆虫学报, 2007, 50 (5) :507-507.

基因分类 篇3

关键词：关联规则,基因表达数据,支持向量机,疾病辅助诊断

0 引言

DNA微阵列[1]技术是分子生物学领域的一项重大技术突破。人们可以利用微阵列技术从全基因组水平定量或定性检测基因转录产物mRNA的表达丰度, 即基因表达数据。基因表达数据中蕴含着基因活动的信息, 在基因层面上反映了细胞当前的生理状态, 如细胞是处于正常状态还是恶化状态、药物对肿瘤细胞是否有效等。因此, 基因表达数据在药物疗效判断以及对于恶性肿瘤、遗传性疾病等疾病的辅助诊断有着重要的意义。

由于基因表达数据实验的特性以及现有技术的限制, 基因表达数据与以往数据挖掘的相关数据有较大的区别, 具体表现为样本数量小、样本维度高等特性。这些特性给基因表达数据分析带来前所未有的困难, 成为了实现微阵列技术的瓶颈之一。因此, 如何克服上述困难, 成为了基于基因表达数据的疾病辅助诊断方法主要研究思路。将传统有监督学习方法推广到基因表达数据领域, 一般而言有基因选择和关联规则挖掘这两种方法[2]。

在基因选择方法上, 一般采用特征选择法去降低基因表达数据的维度, 然后调用常用的分类方法对这些降维后的基因表达数据进行训练以及分类。目前较具代表性的方法有支持向量机迭代特征剔除算法SVM-RFE[3]以及基于条件互信息[4]的特征选择算法。基因选择方法的主要优势在于它能够与不同种类的分类器结合, 达到较高的分类精度。然而, 现有的基因选择方法不能捕捉到基因之间的非线性关联, 并且分类结果缺乏可解释性是其主要缺点。

与基因选择方法相比, 关联规则筛选方法提供了一种有效、易于理解的方式对基因之间的各种联系进行描述, 受到生物学家的欢迎。关联规则兴趣度测量以及分类模型的选取是基于关联规则的基因表达数据分类模型的两个重要内容。其中关联规则兴趣度测量的代表性研究有Cong等人的短规则优先 (Short方法) [5]和Cai的最大/最小子关联规则优先准则 (MinSC、MaxSC方法) [6]。在分类模型方面, 关联规则分类模型RCBT[5]以及改进关联规则分类模型IRCBT[6]是现有的两种高效、基于关联规则的基因分类模型。分类模型的选取对于基因表达数据的分类精度起决定性的作用, 一个有效的分类模型可以显著地提高其最终的分类精度。

基于上述分析, 本文主要的研究思路如下:克服由基因表达数据样本数量小、维度高等特性所带来的困难, 在保持良好的分类精度的基础上提高分类结果的可解释性。其实现过程主要通过在一个统一的框架内结合对关联规则以及支持向量机分类模型的应用, 达到基因选择和关联规则挖掘方法各自优势的整合。为此, 本文提出了一种基于关联规则的支持向量机分类模型ASSO-SVM。ASSO-SVM首先对基因表达数据进行关联规则提取, 通过这一步可以令有价值的频繁模式被挖掘出来;然后根据每个训练样本是否被这些挖掘出来的频繁模式所覆盖这一准则, 将原始的基因表达数据集转换为二进制向量集;最后, AS-SO-SVM采用支持向量机作为分类器, 对上一步经过转换后的数据进行训练, 并最终完成对基因表达数据进行分类这一过程。

1 相关工作

1.1 基因表达关联规则

自1993年R.Agrawal[7]等人首先提出在交易数据库中挖掘关联规则和频繁模式后, 关联规则挖掘算法及应用得到迅速发展。关联规则能够解决基因选择算法在理解性方面所遇到的困难。Li[8]等人在研究白血病发病机理时发现以下一条关联规则:“IF the expression of 40454_at is≥8280.25 AND the expression of 41425_at is≥6821.75, THEN this sample is subtype E2A-PBX1”。这里不仅指出40454_at、41425_at这两个基因与白血病子型E2A-PBX1的关系, 还指出各个基因的表达情况和癌症的关系, 例如41425_at的表达水平大于8280.25。显然这种结果大大降低了进行生物学解释的难度, 具有实际的应用价值。以下内容将在基因表达数据层面上对关联规则所涉及的一些概念作出简单介绍。

(1) 基本概念

假设基因表达数据集D由一个n行m列的矩阵组成, 集合R={r1, r2, …, rn}和I={I1, I2, …, Im}分别代表矩阵的全体行和列。其中R中的每一个元素rn代表一个样本, 而I中的一个子集Im被称为项集或模式, 代表一种关于基因表达的状态。集合C={C1, C2, …, Cn}表示每一个样本rn所属的类别。这里需要特别说明的是, 每一个样本属于并且只可属于一种类别。基因表达关联规则是由项集和样本类别一起构成, 一条典型的基因表达关联规则γ具有形如A→co的蕴含式, 其中A→I且c0∈C, A与co分别称为关联规则的前件和后件。

给定一个特定的集合, I'的行支持集为R (I') ={ri|ri∈R, 且I'ri}, 即包含项集I'的最大样本集合。类似地, 对于一个特定的样本的集合, 它的项支持集为I (R') ={Ij|Ij∈I, 且对任意的r∈R', 有Ij∈r}, 也就是样本集合R'中各个样本共同包含的项的最大集。

针对基因表达数据这一研究对象, 常用的关联规则兴趣度度量为支持度和置信度。对于关联规则γ:A→co, 其支持度为|R (A∪co) |, 即同时包含A和co的样本占总体样本数的比例;而其置信度则是|R (A∪co) |/|R (A) |, 即在所有包含项集A的样本集中, 包含co的样本所占的比例。

(2) 关联规则等价类

关联规则等价类是关联规则挖掘领域非常重要的概念, 最早由Cong[9]等人在基因表达数据的关联规则挖掘研究中提出, 用于解决高维数据上的关联规则数量组合爆炸问题。一个关联规则等价类由关联规则集G={γ1, γ2, …, γr}组成, 其中G的行支持集为R', 当且仅当它满足以下两个条件:

条件1任意的γ∈G, R (γ) =R'。

条件2若R (γ) =R', 则γ∈G。

显然, 一个关联规则等价类内所有的规则都具有同样的支持度和置信度。

Cong还提出, 在一个关联规则等价类中, 存在着两种特殊的关联规则, 上界关联规则UBR (Upper Bound Rule) 以及下界关联规则LBR (Lower Bound Rule) 。其中UBR是关联规则等价类中唯一的一条具有下述特征的规则:其前件项集是关联规则等价类内其余所有关联规则前件项集的超集。相对于UBR的唯一性, LBR则是由一条或多条这样的关联规则组成:由它们的前件项集的子集所组成的关联规则都不属于该关联规则等价类。UBR以及LBR的作用主要在于从关联规则等价类中选择k个最有价值的关联规则。

1.2 支持向量机

在我们面临的大量实际分类问题中, 绝大多数的样本都是低维、线性不可分的, 使得这类问题的解决往往比较困难。而由Vapnik[10]提出的支持向量机理论则非常巧妙地解决了非线性分类问题。支持向量机是一种监督式学习的方法, 它广泛地应用于统计分类以及回归分析中, 现已经在许多领域 (生物信息学, 文本和手写识别等) 都取得了成功应用。

支持向量机首先利用核函数将输入空间中线性不可分的样本映射到一个更高维的特征空间里, 从而使得问题变得线性可分;然后在这个特征空间里建立一个分类面, 使得某一类样本能与其它类别样本区分开来。Vapnik使用分类间隔作为分类器的推广能力的度量。如图1所示, 线性分类器的方程为y=w×x+b, 其分类间隔是直线w×x+b=1与w×x+b=-1的距离, 可通过计算得出此时的分类间隔为2/‖w‖。SVM通过令分类间隔最大化来提高分类器的推广能力, 即便在小样本、高维的基因表达数据下仍可较好地解决分类问题。

解决基因表达数据的分类问题, 可用现时较为成熟的机器学习方法, 如神经网络、支持向量机、聚类等等。鉴于基因之间的关系往往是非线性的, 以及基因表达数据存在高维、小样本和高噪声的特性, 支持向量机对这些条件都具有较好的适应性, 本文最终选择了支持向量机作为分类模型。

2 基于关联规则与支持向量机的分类模型

传统上对基因表达数据进行分类常常有以下两个步骤:第一步是“基因选择”, 也称为“特征提取”。主要目的是在原始的基因表达数据集里面将有意义的特征提取出来, 以及生成相应的训练集和测试集。第二步是将训练集和测试集作为分类器的输入, 完成分类的过程并最终获得分类结果。在此情况下, 由于没有将生物学先验知识与分类器结合应用, 传统的分类方法普遍都存在着分类结果不容易进行生物学解释的问题。

这里我们提出一种新的分类模型ASSO-SVM, 它结合了关联规则以及支持向量机特性的分类模型。ASSO-SVM属于有监督学习方法, 主要包含以下三个步骤:

第一步关联规则的挖掘。我们在这一步从基因表达数据挖掘出我们感兴趣的关联规则。现时存在多种挖掘关联规则的方法, 传统上衡量关联规则的兴趣度有支持度以及置信度这两种。Cong的研究[5]根据最小描述长度原理选取最短的k个LBR作为最具代表性的关联规则 (Short) 作为兴趣度。Cai[6]在Cong研究的基础上提出用最大子关联规则置信度 (MaxSC) 以及最小子关联规则置信度 (MinSC) 去度量关联规则。在我们的研究里将采用Short、MaxSC以及MinSC作为衡量关联规则重要性的兴趣度, 并且在实验当中对这三种兴趣度作出对比分析。实验中所有的关联规则将以以下形式存储:{RulegroupID:Rule1, Rule2, …, Rulen}。其中项Rulen代表一个基因表达关联规则, 由若干个唯一标记各个基因的“基因ID”组成;而RulegroupID则表示这些关联规则所属的关联规则等价类。

第二步对原始的基因表达数据集进行转换, 数据集被划分为训练集以及测试集两部分, 并且结合前一步获取自关联规则的先验知识将数据集转换为二进制形式。我们根据训练集或测试集中的样本是否被前一步挖掘出来的模式所覆盖为准则以实现该转换过程。假如样本smp1被关联规则ar1所覆盖, 那么结果文件里对应smp1和ar1的变量将被赋值为1, 否则被赋值为0。经过这一步后, 所有的样本都结合了关联规则的先验信息, 同时我们将获得一系列形如“01001”的二进制字符串作为新的训练集和测试集。关于这一步的具体框架如算法1所示。

第三步用SVM分类器对数据集进行分类。在向分类器输入数据之前, 我们还要对由第二步生成的结果进行格式转换。这是由于分类器对输入数据的格式有一定要求, 二进制字符串一般不能直接作为分类器的数据输入。经过格式转换之后, 我们便可将其作为分类器的数据输入。分类器在训练数据的过程中不断调整参数, 我们的程序将依据各个核函数的训练结果, 自动选择出最优核函数, 并获得最终的分类结果。

算法1 ASSO-SVM对原始基因表达数据集的转换

输入:DS:原始基因表达训练 (或测试) 样本集

RS:关联规则集

输出:RC:新基因表达训练 (或测试) 样本集

为了更好地理解算法所描述的整个转换过程, 我们将用一个简单的例子说明:假设“smp:{1, 3, 6, 8, 10∶1}”是原始基因表达训练 (或测试) 样本集DS的一个样本 (注意这里“∶1”是一种类标记, 表示该样本属于正类, 而“∶0”则表示该样本属于负类) , 以及由上一步挖掘所得、对应正类的关联规则集RS为{{1, 3}, {1, 2}, {1, 6}, {3, 8, 10}}。我们通过检查RS的每一个元素ar的所有项是否都出现在smp中, 将smp与ar进行匹配。显然, 对于RS的首个元素{1, 3}, 其项“1”以及“3”都出现在smp:{1, 3, 6, 8, 10}中, 匹配成功, 因此我们把“1”插入结果文件RC的第一位中;对于RS的第二条关联规则{1, 2}, 由于其中的一个项“2”没有出现在smp中, 匹配失败, 因此我们将“0”插入结果文件的第二位;以此类推, 在遍历了RS的所有规则之后, 我们便可得到对应RS以及smp的二进制字符串{1, 0, 1, 1}。最后将该二进制字符串与smp的类标记“∶1”结合, 便得到新的训练集{1, 0, 1, 1∶1}作为算法的输出结果。

3 实验分析

3.1 数据集

实验采用Leukemia[11]、DLBCL[12]、Lung Cancer[13]和Bortezomib[14]这四个公开的基因表达数据集对算法性能进行测试。这些数据集可从Gene Expression Omnibus的官方网站获得。数据集的具体信息见表1所示, 其中“D”、“F”、“AML”等分别指代各种疾病的类型。

3.2 实验框架

在实验中, ASSO-SVM的关联规则的挖掘算法和筛选标准为Cong等人的Short准则, 以及Cai等人的MaxSC和MinSC准则, 相关算法可在其各自的项目主页下载。ASSO-SVM的所有算法都是在Visual C++6.0环境中编程实现, SVM分类器采用LibSVM 3.1+Python 3.2.2。运行环境为一台操作系统为Windows 7 (64位) , CPU为Intel Core i3-330M (双核) , 4GB内存的PC。

在获取ASSO-SVM的分类精度的过程中, 本实验采用三折交叉检验方法。在三折交叉检验框架中, 数据集被随机分成三份大小一样的子集 (fold) , 每次将其中一份用作训练, 其余两份用作测试。上述过程共被重复三次, 以三次结果的均值作为最终结果。为了消除随机因素对实验的影响, 我们采用了30次三折交叉检验的平均值作为后续的实验结果。

为了公平地对比各种挖掘准则, 在参数设置方面, 实验首先采用Cong等人的行枚举方法挖掘top-10个关联规则等价类, 然后再采用不同的兴趣度从每个关联规则等价类中挖掘出top-20个LBR。另一方面, 为了测试ASSO-SVM分类器的准确性, 实验还分别采取了两种不同的分类器RCBT和IRCBT与之进行比较。

3.3 分类精度分析

(1) 不同兴趣度度量之间的对比

表2、表3和表4分别给出了3种分类器在Short、MaxSC和MinSC关联规则筛选标准下的分类精度, 其中每个数据集上分类精度最高的算法用粗体标出。总体上说, ASSO-SVM分类模型相对RCBT和IRCBT分类模型获得了较佳的分类效果, 证明了ASSO-SVM的高效性。同时, 我们发现ASSO-SVM分类器在3种关联规则筛选标准的性能上非常接近, 从侧面验证出AS-SO-SVM具有较好的推广能力。

(2) 与SVM直接应用在原始基因表达数据的情况作比较

为了验证关联规则挖掘对分类精度的影响, 表5给出了对原始基因表达数据直接使用SVM分类器的分类精度。虽然这种方法也利用到SVM分类器, 但与ASSO-SVM分类模型相比, 这种方法没有经过关联规则挖掘的步骤。实验结果反映出在对高维、连续的原始基因表达数据分类上, 使用ASSO-SVM时的分类精度优于单纯利用SVM分类器时的分类精度。这说明了关联规则挖掘是一种有效的特征选择方法, 对高维、连续的基因表达数据具有良好的适应性。另外, SVM分类器属于一种“黑盒类”分类模型, 存在分类结果不容易进行解释的问题, 而结合了关联规则先验知识的ASSO-SVM则有助于解决这个问题。因此, 进行关联规则挖掘是很有必要的。

3.4 参数敏感性分析

为了研究参数设置对实验结果的影响, 我们分别设置不同的UBR数量和LBR数量进行实验。实验将在DLBCL数据集上进行研究, 其他数据集上也有类似结果, 此处不再赘述。实验总体上反映了ASSO-SVM分类模型对LBR数量和UBR数量的鲁棒性。

图2给出了LBR数量与分类精度关系。当LBR的数量大于20时, 分类器已经捕捉到了数据集大部分的信息。更进一步地挖掘出过量的LBR将会对分类精度产生负面的作用。这可从当LBR的数量设置为80时, 分类精度产生明显下降的情况看出。该现象也体现出选择适量LBR的必要性。

图3则说明了UBR数量与分类精度关系。与LBR的情况相似, 当在实验中设置过量的UBR时, 其分类精度会下降。例如, 当设置UBR的数量为40时, ASSO-SVM+MinSC与ASSO-SVM+MaxSC这两种组合的分类精度相对其在UBR为20时的分类精度大约有1%的下降。

4 结语