2010研究生数学建模(A题).pdf
全全全全国国国国第第第第七七七七届届届届研研研研究究究究生生生生数数数数学学学学建建建建模模模模竞竞竞竞赛赛赛赛 题 目 基于 SVM 和 LDA-GA 的基因图谱信息提取方法的研究 摘 要： 本文针对提取基因图谱信息的问题，运用浮动顺序搜索算法、RBF 支持向量机和遗 传线性判别算法（LDA-GA）等方法，在不处理噪声、降噪以及融入其他有价值的信息 三种条件下分别建立能够有效提取样本基因图谱信息的模型， 并利用样本数据针对每种 条件下得到的基因“标签”的分类能力进行测试和分析。 针对问题 1， 首先以 Bhattacharyya 距离为评价函数， 对样本中 2000 个基因进行无关 基因的剔除，得到 388 个信息基因；然后，在信息基因集合中，根据浮动顺序搜索算法 搜索得到 35 个候选分类特征子集，为问题 2 中基因标签的筛选提供必要条件。 针对问题 2，根据样本数据，利用候选分类特征子集对 RBF 支持向量机进行训练， 采用“留一法”和“独立测试实验”对所建支持向量机进行测试。通过对测试结果的分 析与评价，筛选出具有最佳分类效果的特征子集，作为基因“标签”。通过实验得到的 基因“标签”为 7 维向量。 针对问题 3， 分析 NT_I 及 NT_两类噪声， 建立噪声模型并对样本数据进行降噪处 理。运用处理后的样本数据，确定新的基因“标签”。实验结果表明，新的基因“标签” 具有更高的分类精度。 针对问题 4，根据有助于诊断肿瘤的相关信息，利用 LDA-GA 方法对有价值的生理 基因进行筛选得到最优生理基因向量，与候选分类子集组合形成广义候选分类子集，并 通过支持向量机对其筛选，确定广义基因“标签”。实验结果表明，广义基因“标签” 为 4 维向量，且具有更佳的分类效果。 关键词：Bhattacharyya 距离，浮动式顺序搜索算法，RBF 支持向量机，NT_I 及 NT_ 噪声模型，LDA-GA 算法 参赛队号 队员姓名 参赛密码 （由组委会填写由组委会填写） 2 一一、 问题重述问题重述 癌症起源于正常组织在物理或化学致癌物的诱导下，基因组发生的突变。而基因在 结构上发生碱基对的组成或排列顺序的改变，更改了基因原来的正常分布。因此，探讨 基因分布的改变与癌症发生之间的关系具有深远的意义。 DNA 微阵列是指固定有称之为探针的核苷酸序列的固体基片或膜，它是能够快速、 高效地检测 DNA 片段序列和基因表达水平的新技术。根据核苷酸分子在形成双链时所 遵循的碱基互补原则，可以检测出样本中与探针阵列中互补的核苷酸片段，从而得到样 本中关于基因表达的信息，即基因表达谱。随着大规模基因表达谱技术的发展，已经获 得人类各组织的正常的基因表达谱，为各类病人的基因表达谱提供了参考基准。如果可 以在分子水平上利用基因表达谱准确地辨别是否患有肿瘤， 对诊断和治疗肿瘤具有重要 意义。因为正常人和肿瘤患者均具有其基因的特征表达谱，所以从 DNA 微阵列测量的 成千上万个基因中找出决定样本类别的一组基因“标签”，即“信息基因”，能够从分 子水平上准确识别是否患有肿瘤，且为医学诊断、简化实验分析及抗癌药物研制提供便 捷和帮助。 然而，由于基因数目很大，在判断肿瘤基因标签的过程中，需要剔除掉大量“无关 基因”，从而大大缩小需要搜索的致癌基因范围。事实上，在基因表达谱中，一些基因 的表达水平在所有样本中都非常接近，可以认为这些基因与样本类别无关，没有对样本 类型的判别提供有用信息，反而增加信息基因搜索的计算复杂度，所以首先必须对这些 “无关基因”进行剔除，然后有效地提取基因图谱信息得到基因标签。 此外，肿瘤是致癌基因、抑癌基因、促癌基因和蛋白质通过多种方式作用的结果， 因此在确定肿瘤的基因标签时，应该设法充分利用其他有价值的信息，例如将与临床问 题相关的主要生理学信息融合到基因分类研究中。 因此，本文需要完成以下几个问题： 1 由于基因表示之间存在着很强的相关性，所以对于某种特定的肿瘤，似乎会有 大量的基因都与该肿瘤类型识别相关， 但一般认为与一种肿瘤直接相关的突变基因数目 很少。如何根据上述观点，利用附件中的数据，选择最好的分类因素； 2 对于给定的结肠癌数据，如何从分类的角度确定相应的基因“标签”； 3 基因表达谱中不可避免地含有噪声，对含有噪声的基因表达谱提取信息时会产 生偏差。通过建立噪声模型，分析给定数据中的噪声能否对确定基因标签产生有利的影 响； 4 在肿瘤研究领域通常会已知若干个信息基因与某种癌症的关系密切，建立融入 了肿瘤研究领域中有助于诊断肿瘤信息的确定基因“标签”的数学模型。 3 二二、 问题分析问题分析 基因表达谱作为描绘特定细胞或组织在特定状态下的基因表达种类和丰度信 息，能够提供丰富的信息进行正常和患有肿瘤两类样本的辨别，为医学诊断及抗 癌药物研制便捷。目前，肿瘤分类领域的一个目标是采用尽可能少的信息基因以 获得尽可能高的样本分类准确率，这是因为：(1)选择尽可能少的信息基因意味着 尽可能多地去掉了包含在样本中的噪音；(2)意味着减少肿瘤诊断的成本；(3)分类 准确率高的信息基因通常与肿瘤的发生发展存在紧密的联系。然而，仅仅采取一 种基因选择方法很难选出满足条件的信息基因子集，因此需要进行两个阶段，即 初选阶段和复选阶段。初选阶段利用适当的条件限制先从成千上万个基因中选出 信息基因，从而大幅降低基因的搜索空间，然后进行复选得到能有效判别正常与 患有肿瘤的基因标签。 该题首先需要参赛者解决的问题是：根据 DNA 微阵列测定得到的基因表达谱，采用 有效的算法，得到准确辨别正常和患有肿瘤的两类样本的基因标签，并对附件中提供的 样本进行准确辨别。另外，基因表达谱中不可避免地含有噪声，会影响基因表达谱的提 取，因此需要建立适当的噪声模型对基因标签筛选过程进行优化。最后，由于肿瘤是多 种因素共同作用的结果，因此在确定肿瘤标签时，还要充分考虑其他有价值的信息。具 体来说，需要考虑的问题如下： 1 信息基因的初选-“无关基因”的剔除 对于某特定组织的基因表达谱，含有数量庞大的基因，其中绝大部分的基因在正常 和患有肿瘤两种状态下的基因表达水平具有相似性，无法对辨别作出贡献。这类基因被 称为“无关基因”。对于问题 1，首先需要选取一定标准，作为衡量某基因是否为“无 关基因”的判断条件，然后对样本的基因表达谱进行筛选，剔除“无关基因”，并利用 浮动顺序搜索算法得到候选分类特征子集。 2 基因标签的选取 与患有肿瘤相关的基因数目可能含有若干个， 对于问题 2， 需要在问题 1 的处理结果 组成的基因子集空间中，选取适当的算法，搜索得到能够准确判断正常或者患有肿瘤的 基因标签。 能够使用的算法包含：支持向量机、多指标评价模型等。为了得到更为准确的基因 标签，避免某次搜索受样本噪声等问题的干扰，可以进行多次搜索，每次均将支持向量 机和多指标评价模型相结合进行筛选， 通过对结果的分析与评价，筛选出具有最佳分 类效果的基因集合，即为基因“标签”。 3 噪声模型的引入 对于问题 3，将噪声干扰考虑到基因表达谱的分析中，分析可能存在的各种噪声，如 实验过程中的随机干扰等噪声，如果确定患有肿瘤的基因标签中某基因所占比率很小， 那么在受到噪声干扰时则容易产生辨别偏差。 而通过引入噪声模型排除或削弱该基因在 辨别是否患有肿瘤的过程中的贡献，从而提高了分类的正确性，因此噪声模型的建立可 能会对基因标签的确定产生有利的影响。 4 在模型中融入肿瘤研究领域中有利信息 在肿瘤的研究领域内，已经存在若干有利于构建更完善的确定基因标签的信息，对于问 题 4，通过完善上述数学模型，将这类信息融入到前面建立的模型中，增强基因标签判 4 断的准确性。通常我们会想到很多判别模型，比如：Fisher 判别法、贝叶斯判别法、支 持向量机判别法等模型，在对有助于诊断肿瘤的信息具体分析后，即可尝试建立相应的 判别模型。 三三、 模型假设模型假设 假设一：样本中的数据真实，来源可靠，能够作为检验模型准确性的样本； 假设二：样本具有普遍性，能够作为寻找基因“标签”的依据； 假设三：样本数据里的噪声具有一般性。 5 四四、 符号说明符号说明 符号 含义 指定的 Bhattacharyya 距离的阈值 _ maxi D 有i个基因的特征子集中具有最大评价函数值的 基因集合 i J D 有i个基因特征子集的 Bhattacharyya 距离 , i K x x 核函数 )1( i f 分类准确度 )2( i f 被选基因数目 “留一法”权值 i V 基因表达水平 iG 基因i的表达向量 V S 协方差矩阵 I 染色体 二进制向量 实数向量 B S 类间散布矩阵 W S 类内散布矩阵 6 五五、 模型模型的的建立与解答建立与解答 5.1 问题问题 1 5.1.1 理论分析 因为基因表示之间存在很强的相关性，所以对于某种特定的肿瘤，可能会有大量的 基因都与该肿瘤类型识别相关。然而，在基因表达谱中，含有大量对样本类别的判别影 响很小的基因。这些基因的表达水平在所有样本中都非常接近，不会为样本类型的判别 提供有效的信息，反而会增加信息基因搜索的计算复杂度1。例如附件中给出的基因表 达谱中，某些基因在健康状况正常和患有癌症两个类别里的分布，无论其均值还是方差 均无明显差别，对样本类别的判定贡献很小。因此，需要剔除无关基因，缩小搜索的有 效范围。 作为对基因的初选过程，需要一种适用性强、判别效率较高且容易实现的算法。因 此，选择以 Bhattacharyya 距离为评价函数及浮动顺序搜索算法作为问题 1 的解决方案。 5.1.2 基于 Bhattacharyya 距离和浮动顺序搜索算法的基因分类方法 分类错误概率是模式识别中特征有效性的最佳度量，在降维空间中，特征选择的理 想目标是达到分类错误概率最小，然而这点往往难于做到。因此，使得错误概率上界最 小常常是一种合理的选择7。由 Chernoff 提出的错误概率上界是最小的，称为 Chernoff 上界。 根据 Chernoff 上界2,3得到误差的上边界，即： 11 ijij P errorPPpxpxdx （1） 其中01， i 和 j 为需要判别的类别，P error为分类错误概率，积分部分覆 盖所有特征空间，并可以等价为： 1k ij pxpxdxe （2） 其中， 1 1 1 11 1ln 22 T ij ijijij ij k ， i 和 j 为相应的协方差。 当0.5时，分类错误概率误差具有 Bhattacharyya 边界，并由此时 k表达式化 简得到基因的 Bhattacharyya 距离2，即： 22 12 22 12 12 11 0.5ln 422 ij Bk （3） 上式的 Bhattacharyya 距离能够度量基因中含有的类别信息量，其由两部分组成，第 一项表现了基因在两个类别中分布均值的差异对样本分类的作用； 第二项体现了分布方 7 差的不同对样本分类的作用。这两部分具有相互促进的作用，即使基因在两类不同样本 中分布的均值相同，只要分布的方差具有较大差异，仍然可以获得较大的 Bhattacharyya 距离值。而且，由式（3）可知，当某个基因的 Bhattacharyya 距离具有较大值时， k e 项具有较小值，从而分类错误概率的上界具有较小值。从模式分类2的角度看，某个基 因的 Bhattacharyya 距离越大，表示可以利用该基因的信息进行越好的分类。 因此， 利用 Bhattacharyya 距离作为衡量指标， 能够较好地对样本中基因谱进行初选， 剔除无关基因，得到对判别是否患有肿瘤具有帮助的信息基因集合。 附件提供的基因表达谱中，共有 62 个样本，每个样本均含有 2000 个基因的表达数 据。其中，22 个样本被诊断为健康状况正常，40 个样本被诊断为患有癌症。针对两类 样本，对每个基因进行 Bhattacharyya 距离计算，并作出基因的 Bhattacharyya 距离分布 的直方图，如图 1 所示。 图 1 候选基因的 Bhattacharyya 距离分布直方图 根据基因所含样本类别信息的多少，选取阈值并将基因分为“信息基因”和“无关 基因”两类。设 1 S 为信息基因集合， 2 S 为无关基因集合，则“信息基因”与“无关基因” 可以定义如下： 1 2 ( ) SB s s SB s 其中s为基因， B s为基因s的 Bhattacharyya 距离，为指定的 Bhattacharyya 距离 的阈值。从图 1 可知，绝大部分基因的 Bhattacharyya 距离小于 0.1。这些基因在样本中 两个类别中的分布的均值和方差均无较大差异，因此可以作为无关基因被剔除。 基因表达谱中基因 Bhattacharyya 距离的详细分布情况如表 1 所示。 根据表 1 和式子 可知： 在阈值为0.1时， 在 2000 个基因中， 信息基因数为 388 个， 无关基因数为 1612 个。其中，388 个信息基因均在一定程度上具有样本的分类信息，可以作为进一步分类 的基础。 8 表 1 基因 Bhattacharyya 距离分布情况 Bhattacharyya 距离 基因个数 所占百分比 00.1 1612 80.6% 0.10.2 302 15.1% 0.20.3 63 3.15% 0.30.5 20 1% 0.51.0 3 0.15% 根据初步筛选得到的 388 个信息基因，可以形成 388116 26.304 10个不同的基因组 合，每个组合称为一个特征子集。考虑到最优搜索算法的复杂度，采用次优搜索算法， 即浮动顺序搜索算法4对特征子集所构成的空间进行搜索，进一步得到维数不同的候选 特征基因子集。 浮动顺序搜索算法(Floating Sequential Search Algorithm，FSSA)，又称增l减r算法， 该算法避免了顺序前进法和后退法中特征被选入（或剔除）就无法再剔除（或选入）的 缺点，在选择过程中增加了局部回溯过程5。 类似地，采用特征子集的 Bhattacharyya 距离 i J D作为浮动顺序搜索算法的评价函 数，评估特征子集对样本分类的贡献，即： 12 1 12 1212 12 112 ln 822 T i J D （4） 其中)( i DJ表示具有i个基因特征子集 i F 的 Bhattacharyya 距离。 1 和 2 为特征子集 i D 中的基因在正常和患有癌症两个类别样本中分布的均值向量， 1 和 2 为对应的协方 差矩阵。 令 _maxi D为含有i个基因的特征子集中具有最大评价函数值的基因集合， 它是所 有维数为i的特征基因子集中对分类贡献最大的基因集合。 利用浮动顺序搜索算法在特征子集空间中进行搜索，得到具有不同维数的候选特征 子集 _maxi D。 _max ,dim,1,2, i i FFSA nDDi in算法具体步骤如下： step1：初始化 i=2，n=50，, 21max_2 ggD 21,g g为 388 个候选基因集 0 G 中 Bhattacharyya 距离最大的两个基因； step2: max_20 DGG，G即为候选基因集中去掉当前基因子集的其余基因组成的几 何； 9 step3:建立新子集 max_max_)1( gDD ii ,其中Gg 并且)(max)( max_)1( DJDJ i ， , 1)dim(| 0111 GDiDDD iii ； step4：搜索新的子集 max_) 1(max_ ii GG，使)(arg(max( max_ DJGi，其中 ,)dim(| max_)1( iiii GGiGGD； step5：若)()( max_max_ii DJDJ，则1 ii，转 step7；否则令 max_max_ii DD ； step6：如果2i，转到 step2；否则，1 ii，转到 step4 ； step7：如果ni 或 Bhattacharyya 距离评价函数中开始出现奇异协方差矩阵，退 出；否则，转 step2。 浮动顺序搜索算法的算法流程图如图 2 所示。 10 2_max12 ,Dg g 12 ,g g 02_max GGD G (1)_max_max ii DDg gG (1)_max ()max() i J DJ D 1110 |dim()1, iii DDDiDG _max(1)_maxii GG _max arg(max( () i GJ D (1)_max |dim(), iiii DGGi GG _max_max ()() ii J DJ D _max_maxii D D 2i 1ii 1ii in 图 2 浮动顺序搜索算法流程图 附件样本中有正常样本 22 个，肿瘤样本 40 个，在执行浮动顺序搜索算法过程中， 式（3）中的协方差矩阵 1 出现奇异，根据该算法中 step7 的截止条件，程序运行结束， 此时36i ，因此候选特征基因子集的最大维数为 36，并得到 35 个具有维数不同的候 选基因特征子集 _max, 2,3,36 i Di ，如附表 1 所示。 5.1.3 小结 11 对于第 1 问，首先利用 Bhattacharyya 距离作为评价指标进行基因的初选，剔除无关 基因，从样本中的 2000 个基因中得到 388 个信息基因，之后在信息基因所生成的特征 基因子集空间内，利用浮动顺序搜索算法，得到 35 个具有维数不同的候选特征基因子 集，每个候选特征基因子集均是在具有对应维数的特征基因子集中评价函数值最大的。 从结果上讲， 所选取的 Bhattacharyya 距离评价函数及浮动顺序搜索算法适用于题中 要求， 能够高效地对基因表达谱中的无关基因进行剔除， 因此可以作为最好的分类因素。 所得到的结果可以作为第 2 问中基因标签选取的基础。 12 5.2 问题问题 2 5.2.1 理论分析 相对于基因数目，样本的数量很小，如果直接用于分类会造成小样本的学习问题。 另外，分类准确率高的信息基因通常与肿瘤的发生发展具有密切的联系，因此，为了得 到较好的分类效果，需要减少用于分类识别的信息基因数目。 支持向量机 （SVM） 8是由 Vapnik 领导的 AT. PEPTIDYL-PROLYL CIS-TRANS ISOMERASE, MITOCHONDRIAL 5.3.4 去除噪声对确定基因“标签”的有利影响 24 （1）如图 14 所示，其中虚线表示的数据点集为去噪之前的误分次数，实线表示的是去 噪之后的误分次数，可以看出无论是“独立测试实验”还是“留一法”来评价误分次数， 去噪之后的误分次数的平均水平普遍低于去早之前，尤其是“独立测试实验”中，去噪 后的误分次数比较明显的低于去噪之前。 0510152025303540 0 2 4 6 8 10 候选特征子集的维数 误分次数 基于“独立测试实验”的误分次数（去噪后） 基于“留一法”的误分次数（去噪后） 基于“独立测试实验”的误分次数（去噪前） 基于“留一法”的误分次数（去噪前） 图 14 去噪前后“留一法”以及“独立测试实验”误分次数 （2）如图 15 所示，其中红色曲面表示去噪之后的候选特征基因子集的评价值，蓝色表 示的是去噪之前的评价值，可以看出，红色的曲面基本高于蓝色曲面，说明经过去噪之 后候选特征基因子集的分类效果普遍高于去噪之前。 而且两个曲面的最高点属于红色曲 面，说明去噪之后的最优候选特征基因自己（即基因“标签”）优于去噪之前，这意味 着去噪之后所筛选出的基因标签叫去噪之前有更好的分类效果， 而且去噪之后的基 因“标签”的维数低于去噪之前。总之，去除噪声对确定基因“标签”的具有有利影响。 图 15 去噪前后基于多指标评价函数的候选特征基因子集评价 红色曲面表示去噪之后的评价值 蓝色曲面表示去噪之前的评价值 25 5.4 问题问题 4 通常情况下，肿瘤研究领域中会已知若干个生理基因与某种癌症的关系紧密，而有 些专家10指出在基因分类研究中不应该忽略基因低水平表达、差异不大表达的情况，并 应当将临床问题相关的主要生理学信息融入到基因分类的研究中。最后，根据以上信息 建立融入了有助于诊断肿瘤信息的确定基因“标签”的模型。 5.4.1 理论分析 肿瘤研究领域中有若干重要信息，对判别是正常或者患有肿瘤具有重要的贡献，比 如题中提供的临床生理学信息：大约90%结肠癌在早期有 5 号染色体长臂 APC 基因的 失活，而只有40% 50%的 ras 相关基因突变。 基因失活在本题中是指基因不表达或者表达值降低。因此，在选择基因“标签”的 过程中，不仅要从基因突变导致癌变的角度考虑，同时可以通过引入基因失活等特征对 模型进行优化。从样本中的基因表达谱中找到 APC 基因，其基因表达值均值和方差均 较小，参考前三个问题中针对基因“标签”的求取方法，可见 APC 基因在基因标签的 选择中被过早的剔除。然而，根据临床的生理学信息，这 APC 基因对判定是否患有肿 瘤具有较大的判定作用，因此在筛选的过程中，需要保证 APC 等在肿瘤研究领域对分 类具有重要作用的基因被保留，从而增强模型的判别准确性。 因此，提出广义基因“标签”的概念，即在原始基因标签基础上增加临床上具有重 要分类信息的基因。具体的广义基因“标签”的选择方法是，在肿瘤研究领域中具有重 要判别信息的基因中，首先利用 LDA-GA 方法进行筛选，得到一定维数的最优生理基 因向量，然后将其加入到去噪后的每一个候选分类特征子集，得到广义候选分类特征子 集，然后利用 RBF 支持向量机进行筛选，得到具有最佳分类效果的广义基因“标签”。 具体过程如图 16 所示。 图 16 广义基因“标签”确定模型框图 5.4.2 建立确定广义基因“标签”的数学模型 临床上，有很多对判别是否患有肿瘤具有非常重要贡献的依据，这些信息涉及的范 围较广，如果仅仅从信息基因的角度进行辨别，会出现判别不准确的情况。然而，针对 肿瘤这种特殊重症的诊断需要很高的准确性。因此，需要从多方面对此分类问题进行考 察，尽可能地扩大考察范围，得到较为准确的数学模型。 根据文献中的数据，BRCAI 抑癌基因定位于 17 号染色体长臂，该基因的突变引起 恶性肿瘤发生的易感器官有乳腺、卵巢、结肠及前列腺等，统计表明乳腺癌-卵巢有 80% 90%伴有 BRCAI 突变11； P16 蛋白多重肿瘤抑制基因 （MTSI） 的表达产物， MTSI 定位于人类第 9 号染色体短臂不到40kb范围内，MTSI 基因在肿瘤中的总突变率为 75% 12；PTEN 基因定位于染色体10 23.3 q，含有 9 个外显子，定位于 10 号染色体。该 26 基因在许多进展期的肿瘤中均有发现。PTEN 基因在大肠癌中的突变率为75% 13。大约 90%结肠癌在早期有 5 号染色体长臂 APC 基因的失活，而只有 40%50%的 ras 相关基 因突变1。以上数据能够作为具有代表性的生理基因参与筛选，筛选过程具有很强的典 型性。 在和癌症相关的生理信息基因集合中，为了选择一个小的生理信息基因子集，本文 采用一个嵌入式算法来实现这个目标，这个基于 LDA 的遗传算法将遗传算法和 Fisher 线性判别分析相结合，其主要优势是：不仅将 LDA 分类器融入遗传算法的适应度函数 中，而且在遗传算法的交叉和变异算子中也融入了 LDA 的判别系数。这样就把与问题 相关的信息融入到选择操作中了，因此使用该算法可以实现高精度的肿瘤判别。 首先对 LDA-GA 方法进行简单介绍。 （1） 线性判别算法（LDA） LDA 是众所周知的降维和分类算法，它是通过将数据投影到一个低维空间来进行 数据的较佳分类。近年来，LDA 更多地被应用在微阵列数据的分析中。 在利用 LDA 方法解决二分类问题时，首先需要明确这个问题的定义。考虑一个含 有 1 C 和 2 C 两个类别的样本集合， 其中 1 C 类含有 1 n 个样本数据， 2 C 类含有 2 n 个样本数据， 而每个样本均能用q个变量来描述。因此，对于矩阵 , ij Xx1, ;in1,jq中的 元素，我们定义 k 为集合 k C 的均值，为所有样本的均值，即： 1 ik ki xC x n （14） 11 i ikk xk xn nn （15） 数据可以利用 B S 和 W S 两个矩阵描述， 其中 B S 为类间散布矩阵， W S 为类内散布矩阵。 T Bkkk k Sn （16） ik T Wikik kxC Sxx （17） 如果定义 V S 为协方差矩阵，那么 VBW SSS。 LDA 算法的目标是寻找一个初始变量的线性组合，使得两类的均值较好地分离，其 能通过被分配到每个类别中的数据变量的总和来量度。因此，LDA 最终确定向量w， 使得当 T W w S w具有最小值时， T B w S w有最大值。通过向量 opt w来实现这个双目标优化， 可以通过最大化下式来得到 opt w： 27 T B T W w S w J W w S w （18） 可以证明，当 1 W S 存在时，向量 opt w是 1 WB SS 的单个特征值所对应的特征向量。一 旦 opt w的基准线被确定，LDA 就会提供一种分类方法（分类器）。然而，在本文中，我 们特别关注这个向量的判别系数：这些系数的绝对值表示q个初始变量对分类的重要 性。 （2） 基于 LDA 的遗传算法（LDA-GA） 利用基因滤波算法对生理信息基因进行初选后，对于一个含有p个基因的集合，基 于 LDA 的遗传算法被用来执行在大小为2 p 的空间中的组合搜索。搜索的目的是在可能 的基因组合中确定具有高预测精度的最小基因子集。下文中将会提出该算法的一般步 骤，并对基于 LDA 的遗传算法中的成分进行分析。特别地，将会解释 LDA 和遗传算法 是如何进行结合的。 一般遗传步骤 本文的基于 LDA 的遗传算法遵循如下传统遗传算法的模板，并具有优秀的策略。 初始种群：初始种群是在每条染色体所包含的基因数目范围从0.6p到0.75p 之间的集合中随机生成的。 进化：当前种群P的染色体是根据适用度函数进行排序的。种群P中染色体最 “优”的10%被直接复制到下一个种群 P ，并从P中移除。 P 中剩下90%的染色体 由交叉和变异生成。 交叉和变异：父染色体是在P中剩下的染色体中，根据相邻染色体对决定的。利 用特别的交叉算子，每次产生一个子体。这个子体在加入下一个种群 P 前经历一个 变异过程。 终止条件：当到达一个预先设定好的迭代数目，或者当种群中出现一条染色体的 基因子集很小时，进化过程则终止。 染色体编码 通常地，一条染色体简单地用来代表一个候选基因子集。这里提到的遗传算法中， 一条染色体具有更多的信息，并由一对向量定义如下： ;I （19） 其中，和具有如下含义：代表一个二进制向量并能有效地代表一个候选基因子 集。 每个等位基因 i 代表相应的基因 i g 被选择1 i 或者未被选择0 i 。 染色体中的代 28 表一个实数向量，其中每个 i 与基因 i g 的特征向量的判别系数一致。正如第二部分解释 的，判别系数代表了基因 i g 对基准值 opt w的贡献。因此，一条染色体可以表示如下： 1212 ,;, pp I （20） 其中和的长度由p和t统一去噪后候选基因数目决定。 需要注意的是，这种染色体编码方式具有更广泛的适用性，且比大多数利用遗传算 法进行的特征选择更丰富， 就是说， 除了候选基因子集之外， 染色体还包括其他信息 （比 如这里的 LDA 判别系数），这些信息在设计强有力的交叉和变异操作时有很大帮助。 适应度评价 在 LDA-GA 方法中基因搜索的目的是寻找 “好的” 基因子集， 它们具有最小的维数， 同时具有最高的预测准确性。为了达到这两个目标，设计一个适应度函数，同时考虑到 如下指标（虽然有些冲突）。 在评价一条染色体;I 时，适应度函数与染色体分类准确度（ 1 f ）和染色体中 被选基因数目（ 2 f ）有关。准确地说， 1 f 是利用 LDA 分类器对训练数据集进行分类， 评估基因子集的分类准确度得到的，并且正式定义如下： 1 TPTN fI TPTNFPFN （21） 其中，TP和TN分别代表实际的正常和患病样本，如：准确分类；()FP FN是被误分 为正常（患病）样本的患病（正常）的样本数量。 适应度函数的第二部分 2 f可以通过下面方程进行计算： 2( ) 1 m fI p （22） 其中，m表示候选基因子集中值为“1”的位的个数，如：被选择基因的个数；p表 示和去噪后预选基因个数相对应的染色体的长度。 适应度函数f定义为下述的加权求和： 12 ( )( )(1)( )f If IfI 01 （23） 其中，是一个参数， 其允许我们给 1 f和 2 f分配一个相对重要因素。 给赋一个大于 0.5 的值，遗传搜索将会向高分类精度的解进行（可能会以选择更多的基因为代价）。相反， 29 使用小的值有助于向小的基因子集方向搜索。因此，变化的会改变遗传算法的搜索 方向。 最后，值得注意的是f的取值范围是0,1；那么，一个f值大的解就比一个f值小 的解好。 将临床数据内容利用 LDA-GA 方法筛选后，得到最优生理基因向量，该向量包含 各类生理基因中最有代表性的几个基因， 能够给予对广义候选分类特征子集的选择的有 效贡献。 随后， 将最优基因生理向量分别加入到第 3 问中去噪后的候选分类特征子集中， 得到的每个广义候选分类特征子集，均含有两部分：其一是候选分类特征子集部分，其 二是最优基因生理向量。 为了简化问题，本文选取的最优生理基因向量维数是 1，利用 LDA-GA 方法选取的 结果为 APC 基因。因此， 将 APC 基因分别加入去噪后的每个候选分类特征子集。这样， 就可以利用广义候选分类特征子集对 RBF 支持向量机进行训练，通过测试结果的分析 和评价，筛选出具有最佳分类效果的广义特征子集，即广义基因“标签”。 5.4.3 模型测试 将附表2中所有35个候选特征基因子集的维数均增1， 即35,.,2 , 1, 869 igDD ii ， i D为融入了有助于诊断肿瘤信息的确定基因“标签”的特征基因子集，用他们来分别 训练支持向量机。 基于支持向量机对候选分类特征子集进行效果测试，其中“留一法”的测试次数为 40 次，“独立测试实验”的测试次数为 22 次。先将它们的测试效果以误分次数的方式 显示。图 17 中 35 个候选特征分类子集分别训练支持向量机，经“留一法”和“独立测 试实验”得到其分类效果，如图 17 所示： 0510152025303540 0 2 4 6 8 10 广义候选特征子集维数 误分次数 基于“独立测试实验”的误分次数 基于“留一法”的误分次数 图 17 “留一法”以及“独立测试实验”误分次数 由图 17 并比较图 12 可知，其分类效果与未加有助于诊断肿瘤信息的确定基因“标签” 时相比，虽然在总体层面上变化并不明显，但其对低维的候选特征子集的分类效果有提 30 高作用，下面进一步利用空间对比图展示融入有助于诊断肿瘤信息的确定基因“标签” 后的分类效果。 图 18 融入新基因前后基于多指标评价函数的候选特征基因子集评价 由图 18 可知，权值的变化对于基因“标签”的决定起到了重要的作用，当较小时， 该基因“标签”为 6 维，当较大时，该基因“标签”为 5 维甚至是 4 维。其评价值始 终高于未加有助于诊断肿瘤信息的确定基因“标签”，证明在此种情况下融入有助于诊 断肿瘤信息的确定基因“标签”进一步提高了分类的效果。 六六、模型模型评价及改进评价及改进 1基于 Bhattacharyya 距离和浮动顺序搜索算法及 SVM 的确定基因“标签”的模型 以 Bhattacharyya 距离作为评价指标，能够将基因表达谱中 2000 个基因缩减至 388 个信息基因，大幅降低了搜索的复杂度，提高了搜索效率，具有较强的剔除无关基因作 用。随后，在所得信息基因构成的特征分类子集空间中，利用浮动顺序搜索算法搜索得 到维数从 2 到 36 共 35 个候选特征分类子集，利用 SVM 及多指标评价模型筛选出含有 7 个基因的具有较佳分类效果的基因“标签”。利用“留一法”及“独立测试实验”评 价并得到最优特征分类子集，其中“留一法”误分次数为 1 次，“独立测试实验”误分 次数为 2,维度为 7，最终确定其为基因“标签”，但没有考虑样本的噪声对评价结果的 影响。 2引入 NT_I 及 NT_II 噪声模型进一步提高基因“标签”的分类效果 在进行基因筛选之前先对样本集进行去除噪声的处理，通过分别去除 NT_I 以及 NT_II 两类噪声进一步提高了样本的合理性，之后正常筛选基因。其最终确定的基因标 签对样本的“留一法”误分次数为 2，“独立测试实验”误分次数为 3，维数为 5，由于 维数得到了降低，因而根据多指标评价模型，其综合评价效果进一步得到了提升。 3确定广义基因“标签”模型进一步提高基因“标签”的分类效果 在引入噪声模型的基础之上进一步融入这些有助于诊断肿瘤信息的确定基因“标 签”，之后正常筛选基因。其最终确定的基因标签对样本的“留一法”误分次数为 3， “独立测试实验”误分次数为 3，维数可以达到 4，由于维数可以进一步降低，因而根 据多指标评价模型，其综合评价效果进一步得到的提高。 红色曲面表示未融入肿瘤信息基因的评价值 绿色曲面表示融入肿瘤信息基因的评价值 31 模型的改进，本模型虽然对基因“标签”的分类效果进行了很大限度的提升，但是 仍然有以下内容可以期望在今后进一步的研究中得到完善：1 建立的噪声模型没有考虑 到所有可能出现的噪声，需要进一步完善噪声模型。2 当待选择的特征分类子集数量较 大时，浮动搜索算法的执行时间会变得很长，如何设计快速的搜索算法是下一步改进的 重要方面。 32 附表 1 不同维数下候选基因特征子集所含基因 维数 候选基因特征子集所含基因 2 22,1772 3 22,1771,1897 4 22,1771,1897,1346 5 22,1771,1897,1346,1750 6 22,698,1897,1346,1924,1740 7 22,698,1897,1346,1924,1740,1352 8 22,698,1897,1346,1924,1740,1352,1423 9 22,698,1897,1346,1924,1740,1352,1423,1522 10 22,698,1897,1346,1924,1740,1352,1423,1522,95 11 1260,377,1897,1346,1924,1740,1352,1423,1522,95,516 12 1260,377,1897,1346,1924,1740,1352,1423,1522,95,516,252 13 1260,377,1897,1346,1924,174
