急性白血病论文 -基于增强显现模式的癌症分类算法

—30— 基于增强显现模式的癌症分类算法 卢新国 1，李 丹 1，王海军 2 (1. 湖南大学计算机与通信学院，长沙 410082；2. 河南科技大学理学院，洛阳 471003) 摘 要：针对提取显现模式时在小样本情况下频率近似于概率的缺陷，在衡量分类信息能力熵的计算中引入贝叶斯估计概率 P(Ci, Sj)， 提高熵的可靠度，在此基础上提取癌症表达中的增强显现模式，提出 2 种基于增强显现模式的癌症分类算法。在急性白血病数据集上进行 实验，结果表明，该算法能提高癌症的正确率。 关键词：显现模式；癌症分类；基因表达模式 Cancer Classification Algorithm Based on Improved Emerging Pattern LU Xin-guo1, LI Dan1, WANG Hai-jun2 (1. School of Computer and Communication, Hunan University, Changsha 410082; 2. School of Science, Henan University of Science and Technology, Luoyang 471003) 【Abstract】For the defect of frequency similar to the probability when extracting Emerging Pattern(EP) in the case of small samples, Bayesian is introduced to evaluate the probability P(Ci, Sj) in measuring classified information capacity entropy for improving the reliability of entropy. It extracts Improved Emerging Pattern(IEP) from the cancer expression and gives two kinds of cancer classification algorithms based on IEP. Experiments are taken on the Acute Leukemia dataset and the results show the algorithm can improve the accuracy of cancer detection. 【Key words】Emerging Pattern(EP); cancer classification; gene expression pattern 计 算 机 工 程 Computer Engineering 第 36 卷 第 8 期 Vol.36 No.8 2010 年 4 月 April 2010 ·博士论文· 文章编号：1000—3428(2010)08—0030—03 文献标识码：A 中图分类号：TP181 1 概述 近年来，研究人员利用微阵列(Microarray)技术获得了成 千上万个基因的表达水平(expression level)，从而得到大规模 基因表达谱数据(gene expression profiles)，因此，通过基因表 达谱进行癌症诊断及治疗研究具有非常重要的意义。如何有 效癌症基因表达谱，并利用分类特征基因找出决定样本 类别的一系列基因表达规则，对于癌症的诊断与治疗以及药 物发现具有重要意义，也是当前生物信息学研究的重点课[1]。 研究人员利用基因表达谱数据通过分类方法对基因模式 挖掘和癌症识别展开了研究[2-3]，但是这些分类算法不能挖掘 有生物学意义的基因表达规则，不利于生物学研究人员更好 地理解疾病与基因间的本质联系。文献[4]提出一种基因表达 中的显现模式(Emerging Pattern, EP)，并给出一种基于显现模 式的癌症分类算法(PCL)。 2 相关知识 定义 1(分割信息熵) 对于样本集 S，如果 T 是子集 S1, S2 在特征 A 的分割点，则 ( , ; )E A T S 为这个分割的信息熵： 1 2 1 2 ( , ; ) ( ) ( ) S S E A T S Ent S Ent S S S = + (1) 其中，设 S 分为 k 个类别 C1,C2,…,Ck。 1 ( ) ( , ) lb( ( , )), 1,2 k j i j i j i Ent S P C S P C S j = = − =∑ (2) 其中，P(Ci, Sj)为样本集 Sj 中类别 Ci 出现的频率。 定义 2(显现模式) 对于数据集 D1 和数据集 D2，显现模 式是支持度在 D1 和 D2 中变化显著的模式[4]。 3 增强显现模式 由式(1)、式(2)可知，割点分割基因后对应的熵越小，类 别判断能力越强。在理想情况下，当割点完全将 2 种类别分 隔开时，熵达到最小值 0。式(2)中的 P(Ci, Sj)为样本集 Sj 中类 别 Ci 出现的频率，而不是样本集 Sj 属于类别 Ci 的概率。由 伯努利大数定理可知，P(Ci, Sj)在样本容量趋于无穷大时收敛 于真实概率，在样本容量不大的情况下与真实概率存在偏差。 为了缓解概率的有偏估计问题，同时提高小样本情况下 熵度量的鲁棒性。引入贝叶斯估计，使 P(Ci, Sj)更贴近 Sj 属 于类别 Ci 的真实概率，m-估计定义如下： ( , )i j in mpP C S n m += + (3) 其中， |{ }| |; |{ }| |i j i jn s s S s C n s s S= ∈ ∧ ∈ = ∈ 。m 为一个等效样 本大小的常量，它确定了对于观察到的数据如何衡量 p 的作 用。在缺少其他信息时选择 p 的一种典型的方法是假定均匀 的概率。式(3)可以理解为将 n 个实际的观察样本扩大，加上 m 个按 p 分布的虚拟样本，这里令 m=72, p=1/2。 定义 3(增强显现模式) 利用式(3)计算基因的分割信息 熵，通过上一节方法获取的基因表达的显现模式，称为增强 基金项目：国家自然科学基金资助项目(60873184)；湖南省自然科学 基金资助项目(07JJ5085) 作者简介：卢新国(1979－)，男，博士，主研方向：数据挖掘，机器 学习，生物信息学；李 丹，硕士研究生；王海军，讲师、硕士 收稿日期：2009-09-27 E-mail：hnluxinguo@hotmail.com —31— 显现模式(Improved Emerging Patterns, IEP)。 对急性白血病样本集的 7 129 个基因计算每个基因以及 割点，并依据最小描述长度原则提取出 857 个特征基因以及 对应这些基因的割点。这就表明这 857/7 129=12.02%的基因 是分类能力较强的特征基因，而其他基因则认为是噪声可以 忽略掉，从而大大降低生成 EP 的复杂度。 4 基于 IEP 的癌症分类算法 4.1 增强显现模式的癌症分类算法 利用基因表达的 IEP，在癌症识别中提出了一种增强显 现模式的癌症分类算法(CCIEP)。给定 2 个训练集 DP 和 DN 以及一个测试样本 T，分别从 DP 和 DN 中挖掘 IEP。将 DP 的 EP 依据它们的频率降序排列后表示为 ( ) ( ) ( ) 1 2, , , P P P P iIEPs IEP IEP IEP= " 同样，DN 的 IEP 依据它们的频率降序排列为 ( ) ( ) ( ) 1 2, , , N N N N jIEPs IEP IEP IEP= " 假设测试样本 T 满足 DP 中的如下 IEP： 1 2 ( ) ( ) ( )( ) , , , x P P P P i i iIEPs T IEP IEP IEP= " 其中， 1 2 xi i i i< < <" ≤ ，以及 DN 中的如下 IEP： 1 2 ( ) ( ) ( )( ) , , , y N N N N j j jIEPs T IEP IEP IEP= " 其中， 1 2 yj j j j< < <" ≤ 。 计算样本 T 分属 2 个类别的似然度。假设分别使用 DP 和 DN 中的前 k(k< ，则 T 属于 DP 类，否则为 DN 类。 CCIEP 具体算法描述如下： Require：癌症亚型训练数据集 DP 和 DN，测试样本 T Outputting：T 的癌症亚型 1: 利用 D 表示 DP 和 DN 的所有样本集合，D=DP∪DN； 2: 利用式 (1)~式 (3)分割基因的表达水平，根据基因分割点的 CIE 对基因排序，挖掘增强的基因表达规则； 3: 利用 Max-Miner 挖掘 DP, DN 基因表达规则的最大边界 P P P θ P 1 2 mLargeBorder (D ) { },{D ,D , , D }=< φ >… 以及最大边界 N N N θ N 1 2 nLargeBorder (D ) { },{D ,D , , D }=< φ >… 4: For Each of {DP, DN} do 5: SD 是处理数据的癌症亚型，AD={DP, DN}-SD， K 是最大边界中右边界中模式的数目； 6: For j=1 to k do 7: 根据边界差 SD j 1 2 kBorderDiff ( { },{D , , , } )} , { },{D D D< φ >′ ′ ′> < φ … 生成 IEP 的表达边界 SD jIEPBorder(D )，其中， AD SD i i jD =C D′ ∩ ； 8: (SD) SD s j jIEP (IEPBorder(D ))= ∪ ； 9: End for 10: End for 11: 抽取 T 中存在于 P(D ) sIEP 和 N(D )sIEP 中的 IEP，并根据在 DP 和 DN 中的频率排序， 1 2 x (P) (P) (P) P i i iIEPs IEP ,IEP , ,IEP(T)={ )… 1 2 y (N) (N) (N) N j j jIEPs IEP ,IEP , ,IEP(T)={ }… 12: 根据式(5)、式(6)计算样本 T 属于 DP 和 DN 的似然度 Scorep(T) 和 ScoreN(T)； 13: 预测样本 T 的癌症类型，如果 P NScore (T) Score (T)> ，则 样本 T∈DP，否则 T∈DN。 4.2 近邻算法 在实验中发现训练样本中 2 类子集的 IEP 的频率并不相 同，但是同一子集则连续存在若干个频率相同的 IEP，容易 出现 ( ) ( )P NScore T Score T≈ 。在这种情况下，如何预测样本 T 的癌症类型的问题，在基于 IEP 的癌症识别中提出一种 KIEP 近邻算法。 先从 DP 和 DN 中训练样本 S，假设 S 的癌症类型是 SD， SD {∈ DP, DN}，抽取满足 IEPsSD 的 IEPsSD(S)， 1 2 ( ) ( ) ( )( ) , , , x SD SD SD SD i i iIEPs S IEP IEP IEP= " (6) 同样，对于测试样本 T 抽取满足 IEPsSD 的 IEPsSD(T)， 1 2 ( ) ( ) ( ) ' ' '( ) , , , x SD SD SD SD i i iIEPs T IEP IEP IEP= " (7) 然后根据 IEPsSD(S), IEPsSD(T)计算样本 S 和样本 T 之间 的似然度 Score(S, T)： ' 1 ( ) ( , ) ( ) m SD k i SD m m frequency EP Score S T frequency EP= = ∑ (8) 其中，k 是用于计算预测似然度选取 IEP 的数目。 将训练集中每一个 S 的 ( , )Score S T 按降序排列，并挑选 K 个具有最大 ( , )Score S T 训练样本 'S 识别样本 T 的癌症 类型： if |{ '}| / 2 ' else P P N D S K S D T D ⎧ > ∧ ∈⎢ ⎥⎪ ⎣ ⎦∈⎨⎪⎩ (9) KIEP 具体算法描述如下： Require: 癌症亚型训练数据集 DP 和 DN，测试样本 T, K Outputting: T 的癌症亚型 1: 执行算法 CCIEP 步骤 1~步骤 11； 2: For Each S {D∈ P, DN} do 3: 设 SD 是样本 S 的类别标识，k 是最大边界中右边界中模 式的数目； 4: 抽取样本 S 中符合 IEPs(SD)的 IEP， IEPsSD(S)={IEP(SD)i1’, IEP(SD)i2’,…, IEP(SD)ix’}, SD={ALL, AML}; 5: 根据式(6)~式(8)计算样本 S 和 T 的似然度，并选择 K 个 与 T 具有最高似然度的样本{S’}； 6: End For 7: For Each S’ {S’} do∈ 8: If S’∈DP then 9: Count(DP)++; 10: Else 11: Count(DN)++; 12: End If 13: End For 14: If Count(DP)>Count(DN) then 15: 样本 S 识别为 DP； 16: Else 17: 样本 S 识别为 DN； 18: End If 5 实验结果与分析 5.1 实验数据集 白血病的基因表达谱包含 72 个急性白血病样本，其中， 有 47 个急性淋巴性白血病(ALL)；25 个急性骨髓性白血病 (AML)。每个样本都包含了 7 129 个基因的表达数据。 —32— 5.2 IEP 的获取 通过 EP 中获取的基因表达分割方法，在白血病数据集 中分离出 866 个分类特征基因[5]。利用定义 3 中获取 IEP 的 基因表达分割方法在白血病数据集中分离出 857 个分类特征 基因。尽管现在只有 857 个特征基因，但要计算对应 IEP 的 计算量非常巨大。本文只重点考虑熵最小的前 50 个基因。对 应的割点将这 50 个基因分割成总共 100 个区间，每个区间与 它对应的基因相联系，即成一个规则项。为了区分这 100 个 规则项以及后续算法的简化要求，本文将其编号。第 1 个基 因的 2 个规则项编号为 1 和 2，第 i 个基因的 2 个规则项编号 为(i*2-1)和(i*2)，第 50 个基因的 2 个规则项编号为 99 和 100。 本文采用基于边界的 EP 挖掘算法 MBD-LLBORDER[6]。在急性 淋巴性白血病(ALL)和急性骨髓性白血病(AML)，分别抽取增 长率大于等于 1 的 IEP，在 ALL 中挖掘了 12 043 个 IEP，在 AML 中挖掘了 9 654 个 IEP。 5.3 癌症识别 本文采用留一交叉检验(Leave-One-Out Cross Validation, LOOCV)的方法进行样本类型的识别，即在 72 个样本集上每 次选择一个样本作为测试样本 T，其余 71 个样本作为训练数 据集挖掘 IEP，利用 CCIEP 和 KIEP 预测测试样本 T 的癌症 类型。又从数据集中重新选择一个没有经过测试的样本作为 测试样本，重复该过程，直到所有样本都经过测试为止。统 计所有识别结果正确的样本数，并计算算法的分类正确率。 在算法 CCIEP 和 KIEP 计算似然度，在式(4)、式(5)、式(8) 中，k 设为 20。在 KIEP 中，K＝5。并利用 PCL, SVM 和 KNN 在 Leukemia 数据集上进行 LOOCV 测试实验。同样在 PCL 中似然度计算中 k 设为 20。在 SVM 和 KNN 训练中，SVM 采用径向基函数(RBF)作为核函数，KNN 相似性度量函数采 用 Pearson 相关系数，K=5，选择 5.2 节中选取的 50 个基因 作为特征基因。上述实验重复 10 遍，并计算平均正确率，实 验结果如表 1 所示。可以看出，CCIEP 和 KIEP 利用 20 个 IEP 来计算似然度，取得了很好的分类精度，比 PCL 分别提高了 3.1%, 4.4%。在抽取 IEP 时，引入贝叶斯估计，增加虚拟样 本空间，扩展了样本容量，使得抽取的特征基因和基因表达 规则更具辨别性，有效消除了噪声对基因表达模式的影响。 表 1 实验结果比较 分类方法 基因特征数(包括基因、 显现模式、增强显现模式) 平均正确率/(%) CCIEP 20 96.2 KIEP(K＝5) 20 97.5 PCL 20 93.1 SVM 50 94.5 KNN(K＝5) 50 85.3 6 结束语 本文提出 2 种在癌症识别中基于增强显现模式的基因分 类算法。实验表明，这 2 种算法具有较好的癌症检测正确率。 但该方法只在急性白血病数据集上进行了实验，在其他数据 集上的性能有待进一步检验；如何快速有效地挖掘 IEP，也 是下一步的研究重点。 参考文献 [1] Quackenbush J. Microarray Analysis and Tumor Classification[J]. The New England Journal of Medicine, 2006, 354(23): 2463-2472. [2] Cho S B, Won H H. Machine Learning in DNA Microarray Analysis for Cancer Classification[C]//Proc. of APBC’03. Adelaide, Australia: [s. n.], 2003. [3] Conde L, Mateos A, Herrero J, et al. Unsupervised Reduction of the Dimensionality Followed by Supervised Learning with a Perceptron Improves the Classification of Conditions in DNA Microarray Gene Expression Data[C]//Proc. of Neural Networks for Signal Processing. [S. l.]: IEEE Press, 2002. [4] Li Jinyan, Liu Huiqing, Downing J R, et al. Simple Rules Underlying Gene Expression Profiles of More than Six Subtypes of Acute Lymphoblastic Leukemia(ALL) Patients[J]. Bioinformatics, 2003, 19(1): 71-78. [5] Tan A H, Pan Hong. Predictive Neural Networks for Gene Expression Data Analysis[J]. Neural Networks, 2005, 18(3): 297-306. [6] Dong Guozhu, Li Jinyan. Mining Border Descriptions of Emerging Patterns from Dataset Pairs[J]. Knowledge and Information Systems, 2005, 8(2): 178-202. 编辑 顾姣健 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (上接第 29 页) 7 结束语 本文研究了在不确定时延网络上网络控制系统的稳定性 问题和在时延和扰动双重影响下的 H∞ 优化控制

方案

气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载

，经过 仿真证实有效后，架设了基于 Internet 的扳手劲竞赛控制系 统，并且在实验室与互联网上通过远程的扳手劲竞赛实验验 证其效果能达到指标 γ 。 参考文献 [1] 曾明如, 祝 琴. 随机时延网络控制系统的状态反馈控制[J]. 南昌大学学报: 理科版, 2007, 31(5): 493-495, 507. [2] Feng Guang, Liu Hongwei. Internet-based Intelligence Time-delayed Networked Control Systems[C]//Proc. of ICCA’07. Guangzhou, China: [s. n.], 2007. [3] 王 武. 随机时延网络控制系统的 H∞输出反馈控制器设计[J]. 控制理论与应用, 2008, 25(5): 920-924. [4] 樊卫华. 网络控制系统的建模与控制[D]. 南京: 南京理工大学, 2004. [5] 曾远立. 基于 Internet 网络诱导滞后的扳手劲竞赛控制系统研 究[D]. 广州: 广东工业大学, 2008. 编辑 张 帆