肿瘤信息基因启发式宽度优先搜索算法研究

肿瘤信息基因启发式宽度优先搜索算法研究内容摘要：

p a t hp a r e n tNgGg jii ..2*  ， 6 )1(1  ppj ， pi1 ， 再把 第 2 层的所有结点 按 降序排列， 检查 ).m ax(arg2)1(1m a x cN jA c c ppj 是否 满足要求，如果满足，则 算法 找到了满足条件的基因子集，否则 选择 排在 前 面的 p 个结点作为扩展结点，继续类似搜索。 需要注意的是，不同节点的路径 所代 表的信息基因集 在不考虑顺序的前提下可能相同，因此在计算节点的分类性能时如果发现前面已计算过，则该节点的分类性能 记为 0 以避免扩展不 必要的节点。 显然， HBSA 算法的搜索宽度 并不随搜索深度的增加而 大幅 增加，因此，算法实际上是一个带有启发信息的定向柱形搜索算法。 虽然从局部看选择 信息 基因的方式采用的是递增方式，但宏观看 则是混合方式，因为 那些 没有潜力的基因组合在搜索过程中被抛弃了。 HBSA 算法还可以根据具体情况灵活使用，比如在选择每一层的待扩展节点时，未必每次都 固定 选择 前 p 个 节点，也可以选择 分类能力大于某一阈 值的所有节点作为待扩展节点，这种情况下需要为每一层设置不同的 阈值，且下一层的阈值大于上一层的阈 值 ， 显然这会 导致每一层所 选择的待扩展结点的数量不同，但 优点是增加了算法的适应性，其中 阈 值的设 定非常关键。 10N…… 11N21NpN112N12pN…… )1(2ppN…… 21N}{ 1pg}{ pg}{ pg}{ 1g}{ 2g}{ 2g 图 2 启发式宽度优先 搜索信息基因 子集 示意图 HBSA算法 实现 在获得最佳信息基因子集 *A 的过程中， 并不需要真正构造搜索树， 只需保留每一 次搜索到的满足给定要求的信息基因 子集及其分类性能指标就能达到预期目标。 为实现上的方便 定义 了 分类矩阵pwjiaCM  )( , ， 直观表示如式 (8)。 111 ,1 1 ,1 ,{ } { }ppww w pggT a aCMT a a (8) 采用 行标记向量 ),( 21 wTTTR o w  依次标记 CM 的每一行，其中 iT ( wi1 )表示 已选择的信息基因子集 ， 采用列标记向量 }){},{},({ 21 pgggC o l u m n  依次标记 CM 的每一列 ，其中 *Ggk ，pk1 ， 而 ])[][(, jC o l u m niR o wA c ca ji ＝ ， 其中 wi1 ， pj1。 下面给出 HBSA 算法实现的基本框架 ， 算法中的 )(TAcc 可以采用 分类器 对样本的实际分类准确率来度量 ，我们的 实验采用 SVM 分类器来 完成对肿瘤数据集的分类任务，这时 )(TAcc 返回 信息基因子集 T 对 肿瘤 样本 集 的 SVM 分类 准确率。 算法： HBSA(M , p ,w ,Depth )； 输入 ： 基因 表达谱 M ,p 为初选信息基因 个数 , w 为选择的基因子集个数， Depth 为迭代深度 ； 输出 ： 最佳 信息基因集合 *A ； 1. For each gene Ggj do 2. B[j]:= )( jgBFSC。 //B 为一数组，用以保存每个基因的 BFSC 分值 ； 3. End for 4. B:=Sort(B)。 //对数组按降序排列 7 5. *G :=Selected(G ,B, p )。 //选择前 p 个基因 构成 初选信息 基因集合 *G ； 6. For each gene *Ggi 7. }{:][ igiColumn  ； 8. ][:][ iC o lu mniR o w  ； 9. End for 10. iter:=1； 11. Repeat //第一次迭代求 CM 时， CM 为一个对称矩阵 ,所以只需求下三角阵 ； 12. 构造分类矩阵 CM ， 使 Row 的每一个分量依次对应于 CM 每一行， 使 Column 依次对应于 每一列； 13. 计算分类矩阵 CM ， ])[][(, jC o l u m niR o wA c ca ji ＝ ； //计算前需要对 ][][ jC o lu mniR o w 所标记的样本集做规格 化处理 (均值为 0，方差为 1)； 14. 把分类矩阵 CM 转化为一维向量 ),( 21 pwvvvV   ， 使每一个分量][][].)1[( jC o l u m niR o ws e tjpiV － ， jiacjpiV ,].)1[( － ， 然后对 V 中的 分量 按 信息 基因子集的分类性能 指标 降序排列 ，并选出前 w 个分量， 重新构造 行标记向量setiViRow ].[:][  ， wi1。 15. ).m ax ( cVa ccu ra cy  ； 16. iter:=iter+1。 17. Until )100( accuracy or )iter( Depth＝ ； //当分类准确率达 到 100%或迭代 深度 达到预定 值Depth 时循环结束； 18. 依次选出 V 中分类 性能最大的 信息基因子集 ，并加入到 *A 中 ； 19. Return *A。 //算法结束 ,返回搜索到 的 最佳信息基因子集 ，我们认为 *A 就是与肿瘤 的发生发展有 特 定 联 系的基因集合。 对于能够以 100％准确率来分类的肿瘤样本数据集，当 HBSA 算法发现了能够以 100％准确率来分类样本集的信息基 因子集后，算法就结束了，但是对于不能够以 100％准确率来分类的肿瘤样本数据集， 算法则执行到指定的迭代 深度 Depth 时 结束，但我们并不知道 Depth 设为何值比较合适， Depth 值设置不当会导致求得的信息基因子集 远离最佳条件。 对于这种情况，则 以第 iter＋ 1 次迭代求得的最高分类准确率1iteraccuracy 不大于第 iter 次求得的 iteraccuracy 为迭代结 束条件 是一个比较好的解决方法。 算法中最耗时的操作是 计算 )(TAcc ，如果把 计算 )(TAcc 看成 耗费 一个 单位时间的 基本操作，则计算一次 CM 的时间复杂度为 )( pwO  ，整个算法的时间复杂度为 )( pwDe pthO 。 尽管 这是一个 多项式时间复杂度算法，但 算法 的执行仍然十分耗时，不过 最佳信息基因子集的选择工作主要在实验室完 成，临床应用只是依据所选择的 最佳信息基因子集 为标记基因 来诊断肿瘤，所以 HBSA 算法是可行的。 支持向量机 SVM 是由 Vapnik[26]提出的基于统计学习理论并采用结 构风险最小化原理的一种机器学习方法，具有较强的泛化能力， 采用数量有限 的训练集就可以得到一个针对独立测试集的分类错误率相对较小的分类模型。 它将输入数据映射到高维特征空间，构造最优分类超平面，用来区分 带有 标记的两 类样本，当线性不可分时，可用核函数把数据自动地映射到线性空间 ,在肿瘤分类领域常用 Gauss 径向基核函数 (Radial Basis Function, RBF) )e x p (),( 2yxyxK  来完成这一任务 [27]， SVM 非常 适合 这种 具有高维和小样本特点的肿瘤 数据集 [28,29]。 我们的 实验采用了 Chang 等 开发的支持向量机软件 LIBSVM[30]， 训练 SVM 需要指定调整参数 C 和核函数参数 。 然而 ， 搜索最佳 参数 对 （ C , ） 是 一件 非常耗时的工作。 通常 在分类前样本 集已经过规格 化处理，所以样 本集对参数 C 不敏感，因此 ， 在 实验中参数 C 分别取 200、 400、 600、 800 和 1000 即可满足需求 ， 而参数  可以这样取值：对 C 的每一个取值，如果  值在 110－ 量级则  分别取 ,  ，如果  值在210－ 量级则  分别取 ,  ，依次类推， 限定  最小取值在 510－ 量级， 最大取值在 10量级， 8 这相当于在一个受限的二维网格上搜索最佳参数对，实验表明这是一个有效的寻找最佳参数对 （ C ，  ）的方法 ，且能大 幅 减少计算量。 由于分类器的泛化性能涉及它在独立测试集上的预测能力，因此，分类器性能评估方法在实际的分类器设计中非常重要，因此，如何评估分类器的性能 是一个值得 进一步 探讨的问题。 在肿瘤分类 领域， 通常采用 k折交叉验证方法 (kfold Cross Validation, kfold CV)来评估分类模型的泛化性能， 但 问题是究竟 k 取何值时 能够获得最佳的分类准确率，或者说是哪种 k折交叉验证分类准确率更能客观反映肿瘤分类模型的泛化性能。 由于肿瘤样 本规模小，许多文献采用留一法 (Leaveoneout Cross Validation, LOOCV)来评估肿瘤分类模型，但是 , Breiman 等 [31]认为 5折 或 10折 交叉验证方法优于留一法 ，而 Asyali 等 [32]针对基因表达谱样本集的交叉验证评估方法也是这样推荐的。 我们的 实验发现，样本集的不同划分对分类准确率有一定的影响 ，且 5折或 10折交叉验证分类准确率也不能客观反映肿瘤分类模 型的泛化性能。 为消除样本集的不同划分对分类器泛化性能的影响，有必要设计 一种能够客观反映分类器性能的评估方法。 记 ()CVk 表示 样本集的 k折交叉验证 分类 准确率， 其中 2 km ， m 为样本总数， 则分类准确率均值 定义为：21 ( ( ) )1 mkm e a n C V km   ，而标准差 定义为：22( ( ( ) )2mkC V k me anstd m 。 因此， 具有最大分类准确率均值与最小标准 差的基因子集的泛化误差也是最小的 ，称这种评估方法 为全折交叉验证方法，采用这种方法获得的分类准确率 均值 被称为全折 交叉验证分类准确率 ，而标准差表示样本集的不同划分对分类准确率的 影响程度。 然而在 HBSA 算法中直接采用全折交叉验证分类准确率作为启发信息会大幅增加计算量，因此我们 首先 采用 计算量相对较小的 4折 交叉验证 分类准确率作为 HBSA 算法的启发信息， 搜索出所有具有最 高 4折交叉验证分类准确率的 最佳信息 基因子集 *A 后，再采用 全折交叉验证方法来评估 *A 中的 基因子集 ， 实验证明 采用这种评估方法获得的分类模型的分类性能与具体的样本划分关系不大。 4 实验 实验数据 为便于实验结果比较，我们采用了三种研究得 比较充分的肿瘤数据集，一种是白血病数据集 (Leukemia dataset)[1]， 一种是结肠癌数据集 (Colon Tumor dataset)[33]，另一种是多肿瘤亚型的 SRBCT 数据集 [13]。 在公开 发布的肿瘤数据集中，结肠癌数据集是最难分类的 肿瘤 数据集 之一 ， 绝大多数 分类 方法都很难 以 100％的 交叉验证 准确率来分类该数据集。 由于 Leukemia 和 Colon Tumor 这两个数据集都是二分类数据集， 所以不妨称一类为正类样本，另一类为负类样本，具体信息见表 1。 表 1 网上发布的 与肿瘤有关的 二分类 样本 集 （ Leukemia 和 Colon Tumor） 序号 数据集名称与下载网址 基因数量 样本总量 正类样本数量 负类样本数量 1 急性白血病数据集 (Leukemia Dataset)[1] 7,129 72 47(ALL) 25(AML) 2 结肠癌数据集 (Colon Tumor Dataset)[33] 2,000 62 40(Tumor) 22(Normal) 我们从网站 下载了 SRBCT 数据集，该数据集包括 88个样本，每一个样本包含 2,308 个基因。 根据发布者的建议 ，样本被划分为 63 个训练样本和 25 个测试样本，且测试样本集中 包括 5 个与肿瘤无关的样本 , 其数据集特征描述见表 2。 63 个训练样本包括 23 个 Ewing 肿瘤亚型 (EWS)、 20 个 rhabdomyosara 肿瘤亚型 (RMS)、 12 个 neuroblastoma 肿瘤亚型 (NB)和 8 个 Burkitt lymphomas 肿瘤亚型 (BL)。 测试样本集包括 6 个 EWS 样本、 5 个 RMS 样本、 6 个 NB 样本、 3 个 BL 样本和 5 个非肿瘤样本， 在我们的 实验中 去掉了这 5 个非肿瘤样本。 表 2 SRBCT 数据集的特点描述 肿瘤亚型 原数据集 训练集 测试集 EWS 29 23 6 9 NB 18 12 6 RMS 25 20 5 BL 11 8 3 NonSRBCT 5 0 5 Total 88 63 25 实验方法 针对 Leukemia、 Colon Tumor和 SRBCT 三种肿瘤样本集分别设计了三种实验方法： BFSC。