（计算机科学与技术专业论文）基于启发式聚类的混合特征基因选择方法研究.pdf

基于启发式聚类的混合特征基因选择方法研究 摘要 d n a 微阵列技术是基因组信息学研究的主要支撑技术，它为癌症研究提供了 最基本和最必要的信息及依据。然而由于基因芯片数据样本少、高维数高的特点， 在基因芯片数据处理时面临了很多的困难与挑战。如何才能通过合理的算法来识 别出对疾病有鉴别意义的基因集，已经成为了目前基因表达数据处理和分析的热 点研究问题。 所以本文研究和探索了特征基因选择算法，提出了两种基于启发式聚类的混 合特征基因选择方法： 1 基于最小生成树聚类的特征基因选择方法。由于传统的聚类方法，只适合 处理球状数据，而最小生成树聚类算法对图形边界较复杂的数据也能得到较好的 结果。因此，本文应用不同的距离度量方法于p r i m 最小生成树聚类中，动态选择 特征基因集，并用支持向量机进行预测。然后，提出一种精选特征基因集的方法， 进一步去除冗余基因。实验表明该方法有效的降低特征基因的维数并有很好的分 类准确率。 2 基于分步聚类的特征基因选择方法。基因表达谱数据具有高维度，非线性 等特点。而g s i m 能够较好的表达高维数据的相似性，流形距离能够很好的展示基 因之间的复杂关系。本文利用g s i m 和流形距离的优点，提出一种基于分步聚类的 特征基因选择算法，有效的解决在高维，非线性数据空间中分辨率能力下降的问 题。同时，提高分类评估方法的泛化能力，使选择出的特征基因具有更好的鲁棒 性。 关键词：基因表达谱；基因选择；聚类；最小生成树；支持向量机 i i 硕士学位论文 a b s t r a c t a tp r e s e n t ，d n am i c r o a r r a yt e c h n o l o g yi st h em a i ns u p p o r t i n gt e c h n o l o g i e sa t i n f o r m a t i c so fg e n o m e i tp r o v i d et h em o s tb a s i ca n dn e c e s s a r yi n f o r m a t i o nf o r c a n c e rr e s e a r c ha tt h el e v e lo fg e n o m e b e c a u s eg e n ec h i p sh a v es m a l ls a m p l e sb u t h i g hd i m e n s i o n sa n dam a s so f n o i s ed a t a ，h o w e v e r ，t h eg e n ec h i pd a t ap r o c e s s i n ga r e f a c i n gw i t hal o to fd i f n c u l t i e sa n dc h a l l e n g e s h o wt ou s er e a s o n a b l ea l g o r i t h m st o a v o i dt h ec u r s eo fd i m e n s i o n a l i t y ，a tt h es a m et i m ei d e n t i f yt h em o s ts i g n i f i c a n tg e n e s ， h a v eb e c o m eah o tr e s e a r c ho ng e n ee x p r e s s i o nd a t ap r o c e s s i n ga n da n a l y s i sa t p r e s e n t t ot h i se n d ，t h i sp a p e rr e s e a r c ho ni n f b r m a t i v eg e n es e l e c t i o n ，p r e s e n tt w oh y b r i d s i g n if i c a n tg e n e ss e l e c t i o nm e t h o d sb a s eo nh e u r i s t i cc l u s t e r i n g 1 s i g n i f i c a n tg e n es e l e c t i o nm e t h o db a s e do nm i n i m a is p a n n i n gt r e e b e c a u s e t r a d i t i o n a lm e t h o da r es u i t a b l et op r o c e s sb u l b i f o r md a t a ，b u tm i n i m a ls p a n n i n gt r e e c l u s t e r i n g i s g o o da tp r o c e s sd a t aw h i c hh a v ec o m p l e xg r a p h i cb o r d e r v a r i o u s d i s t a n c em e a s u r ea r eu s e di nm i n i m u ms p a n n i n gt r e e sc l u s t e r i n gi ng e n ee x p r e s s i o n d a t at og e tf c a t u r eg e n es e t sd y n a m i c a l l y s u p p o r tv e c t o rm a c h i n ei su s e dh e r ea s c l a s s i f i c a t i o nf o rp r e d i c t i n g a n dt h e nw ep r e s e n tam e t h o dt of u r t h e rd e l e t er e d u n d a n t g e n e si nf e a t u r eg e n es e t t h ee x p e r i m e n t a lr e s u l t ss h o w e dt h a to u r m e t h o dp r o d u c e s i m p r e s s i v ea n dc o m p e t i t i v er e s u l t si nt e r m so fc l a s s i f i c a t i o n 2 s i g n i f i c a n tg e n es e l e c t i o nm e t h o db a s e do nat w o - s t e pc l u s t e r i n g t h eg e n e c h i ph a sm a n yc h a r a c t e r i s t i c ss u c ha sh i g hd i m e n s i o n a l ，n o n l i n e a r g s i mi sa b l et o m o r ea c c u r a t e l ye x p r e s s e s st h es i m i l a r i t yd e g r e ea m o n gh i g hd i m e n s i o n a ld a t a a n da m a n i f o l dd i s t a n c eb a s e do ns i m 订a r i t ym e t r i ci sa b l et os h o wt h ei n t “n s i cl i n ko fg e n e s s ot h i sp a p e rt a k e sa d v a n t a g eo fg s i ma n dm a n i f o l dd i s t a n c ea n dp r e s e n tas i g n i 6 c a n t g e n es e l e c t i o nm e t h o db a s e do nt w o - s t e pc l u s t e r i n g t h i sm e t h o de f f 色c t i v e l ys o l v et h e p r o b l e mt h a tr e s o l u t i o nr a t i od e c l i n ea m o n gh i g hd i m e n s i o n a la n d n o n l i n e a rg e n ed a t a w ea l s oi m p r o v ef o r e c a s tm e t h o d sa b i l i t i e so fg e n e r a l i z a t i o n k e y w o r d s ：g e n ee x p r e s s i o np r o 厅l e s ；f e a t u r es e l e c t i o n ；c l u s t e r i n g ；m i n i m a ls p a n n i n g t r e e ；s u p p o r tv e c t o rm a c h i n e 基丁启发式聚类的混合特征荩凶选择方法研究 图1 1 图1 2 图2 1 图2 2 图2 3 图2 4 图2 5 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 插图索引 特征选择算法框架4 研究路线图5 特征选取范围比较1 2 自组织网络图1 4 b p 神经网络模型l7 决策树示意图1 8 最优分类面示意图2 0 基于最小生成树聚类的特征基因选择方法的步骤一2 4 微阵列数据矩阵和数据集分布2 4 最小生成树聚类算法原理2 7 留一交叉法( l o o c v ) 2 9 独立测试法( i t ) 2 9 “曼哈顿 距离基因数与样本错分数关系图3 0 “欧几里德”距离基因数与样本错分数关系图3 0 “马氏 距离基因数与样本错分数关系图3 0 基因序号与对应错分数关系图3 1 谱系聚类算法原理3 2 基于分步聚类的特征基因选择方法步骤3 3 样本案例( 1 3 是数据点) 3 5 流形距离参数k 的变化对比图3 8 最小生成树聚类中流形距离与欧几里德距离的比对3 9 准确率对比图一4 0 特征基因精选一4 0 硕士学位论文 附表索引 表2 1核函数2l 表3 1基因信息指数分布2 5 表4 1第一步g s i m 谱系聚类3 9 表4 2第二步m a n i f o l d 的最小生成树聚类3 9 表4 3与现有的一些方法比较分类预测准确率4 l v i i 硕十学位论文 第l 章绪论 生物信息学是一门研究生物以及和生物相关的系统中信息内容和信息流向的 综合性系统科学【l ，2 l 。美国人类基因组计划实施五年后的报告中，对生物信息学作 了如下定义【3 】：生物信息学是一门交叉学科，它综合运用分子生物学( 如生物化 学、遗传学、结构生物学等) 、数学( 算法、建模、概率论、统计学等) 、计算 机科学( 计算机理论、人工只能、机器学习、动态程序设计等) 和物理化学( 热力 学、分子建模等) ，来解释资料和编码信息、预测意义深远的生物学特征，逐渐 深入的了解生物化学的复杂生命过程。而生物信息学当中的一项新技术：基因芯 片给生物信息学带来了空前的变化。它是一种物理学、微电子学与分子生物学等 学科综合交叉形成的高新技术。这种技术日趋完善，快速的成为大规模探索与研 究生物分子信息的强有力的手段。在当前成为了基因组信息学研究的主要支撑技 术，为在基因组水平上进行癌症研究提供了最基本和最必要的信息及依据【4 5 j 。 疾病是由外因：环境因素和内因：机体相互作用而形成的。人类的疾病除外 伤外，几乎都与基因有直接或间接的相关性。其中癌症是一种致命的疾病。它通 常表现出复杂且多样，同时有极强的隐蔽性和高复发率等特征。严重影响了临床 诊断与分类成功率。据世界卫生组织的数据，目前全球平均每8 个死亡病例中就有 1 人死于癌症，比艾滋病、结核病和疟疾导致的死记人总数的和还要高。因此，关 键基因的识别和癌症诊断与分类成为了目前癌症分析研究的重点。目前利用基于 微阵列的基因表达谱数据在肿瘤与正常组织中的差异及规律，阐明造成这些差异 和规律的原因或者发现一些有待进一步研究的命题，从而对肿瘤进行判别、分类 与诊断已形成共识。当前的肿瘤分类技术通常依赖于病理学和医学工作者对肿瘤 组织的主观判断或者跟据以往的经验。而基因芯片技术，即使在一些组织上没有 显著变化，利用基因表达数据也可以做出早期诊断，这样就给疾病的冶疗争取了 宝贵的时间；另外，特别重要的一点是可以根据基因表达数据的变化来区分形态 学上相似的肿瘤，这样对肿瘤类型的精确识别利于制定出最佳方案，以达到增加 疗效的目的【6 】。然而，对于这种肿瘤基因芯片数据分析的数值方法是一个n p 难题。 最有效的解决方法有识别疾病相关基因和排除噪音特征，降低特征基因的维数等。 利用特征基因选择方法可以剔除与疾病无关的噪声基因，降低机器学习的时间及 空间复杂度，从而避免维数灾难( c u r s eo f d i m e n s i o n a l i t y ) ，提高分类器的效率。所 谓的维数灾难问题是指虽然能建立可用的数据模型由于系统的复杂性，出现因变 量数目太多而导致所得模型的维数过高，或者由于存在非线性、变系数、变结构、 分布参数、非平稳特性等复杂因素，导致优化计算的工作量急剧上升【7 j 。 基于启发式聚类的混合特征基冈选择方法研究 1 1基因芯片 将大量的具有生物识别功能的分子按特定的方式有序的排列在面积不大的基 因芯片上并与标记的检体分子同时反应或杂交。通过放射自显影、荧光扫描、化 学发光可获得大量有用的生物信息，这一技术统称为生物芯片技术。生物芯片包 括基因芯片，蛋白质芯片和芯片实验室三大领域。基因芯片，又称为d n a 微阵列， 是专门用于核酸检测的生物芯片。基因芯片按应用主要分为两大类，第一类是用 于研究基因型，第二类是用于分析基因表达。从本质上讲，前者实际上是利用基 因芯片进行序列分析，其中包括识别d n a 序列的突变和研究基因的多态性；而后 者则是利用基因芯片研究基因的功能【8 】。按技术来分主要分为两大类：c d n a 微点 阵列和寡核苷酸微阵列。 基因芯片技术的制作过程包括四个主要步骤：芯片制备( 有光引导原位合成 法、化学喷射法、接角式点涂法、原位d n a 控制合成等方法) 、样品制备、基因 探针的固定化( 聚赖氨酸法、醛基氨基法) 、杂交反应和信号检测与结果分析【9 】。 基因芯片的杂交原理是利用核苷酸的两两配对互补特性( a t c g ) ，使两条在序列 上互补的单核苷酸链上形成一个双链。固定在玻片上的c d n a 探针是已知的可以 通过测序得到序列或者其它来源。c d n a 芯片具备高通量的优势，目前它已经被 越来越多的研究人员应用于基因表达检测。c d n a 的制作过程有以下几个步骤0 1 ， 首先提取组织或细胞系中的m r n a 样本，逆转录成c d n a 并用荧光素标记；然后把 标记混合物加到c d n a 微阵列上，与探针杂交，完成后清洗微阵列；最后用激光 扫描仪扫描并获取荧光图像，对图像进行分析，得到c d n a 芯片上每一个点的荧 光强度值。荧光强度值定量反映了样本中与探针互补的m r n a 的丰度，即探针所 对应基因的表达水平。那么什么是基因表达水平? 首先“基因表达 是指细胞在 生命过程中，把储存在d n a 顺序中遗传信息经过转录和翻译，转变成具有生物活 性的蛋白质分子。生物体内的各种功能蛋白质和酶都有相应的结构基因编码的。 “基因表达水平”可以理解为是指某个基因在一定时间内控制产生的蛋白质的量。 这些基因表达谱数据说明了细胞中基因表达的状况，为我们提供了实验的源材料。 通过比较肿瘤细胞和相应正常组织细胞的基因表达谱中获得的信息，就可获得在 肿瘤和正常细胞中差异表达的基因，进一步研究这些基因的结构和功能，就可以 对这些数据展开疾病表达谱的构建研究，从而在探索疾病原因的同时给遗传研究、 新药发现和环境保护等生命科学相关领域带来革命性的发展。基因芯片确实已取 得长足发展，但仍有很多问题难以解决，如技术成本高，检测灵敏度较低及分析 范围较窄等问题。 基因芯片技术已经被应用于多种领域，以下是它的一些主要的应用： ( 1 ) 在基因表达分析和基因功能分析中的应用。 2 硕士学位论文 ( 2 ) 在基因突变检测和多态性分析中的应用基因芯片检测基因突变的方法， 快速而又高效。 ( 3 ) 遗传性疾病、传染性疾病的诊断检测基因芯片技术在疾病的诊断方面发 挥了重要作用，它与传统杂交法相比，具有操作简单、自动化程度高、检测靶分 子种类多、成本低、效率高、结果客观性强等突出优点。从正常人基因组分离出 d n a 与基因芯片杂交，得标准图谱，从患者基因组中分离d n a 与芯片杂交得病变 图谱，比较分析两种图谱，即可得出病变的d n a 信息。 ( 4 ) 在法医学、人口学中的个体身份的识别与判定。 ( 5 ) 在药物研究与开发中的应用。 1 1 1基因微阵列数据源 目前，最具影响力的数据库g e o 、a r r a y e x p r e s s 和s m d 这三个网站收集、存 贮了许多微阵列基因表达数据。这些数据还在以极快的速度增长，给研究人员提 供了丰富的实验源材料。 g e o ( g e n ee x p r e s s i o no m n i b u s ) ( h t t p ：w w w n c b i n l m n i h g o v g e o ) 高通量基因 表达数据库是由n c b i ( 美国国立生物技术信息中心) 于2 0 0 0 年开发的一个基因表 j 达和杂交微阵列数据仓库。截止至2 0 1 0 年5 月2 4 日，该数据库有平台( p l a t f o r m ) ： 7 3 6 9 个，样本( s a m p l e ) ：4 3 4 9 1 6 个系列：1 6 9 6 2 个。还有补充文件、数据集和表 达谱等等数据。 a r r a y e x p r e s s ( h t t p ：w w w e b i a c u l ( a r r a y e x p r e s s ) 是欧洲生物信息学研究( e b i ) 所发布的。是基于基因表达数据的微阵列公共知识库，目的是存储被注释的数据， 当前包含多个基因表达数据集和与实验相关的原始图像集。 s m d ( s t a n d f o r dm i c r o a r r a yd a t a b a s e ) ( h t t p ：儋e n o m e w w w 5 s t a n f o r d e d u ) 即斯坦 福微阵列数据库是一个使用o r a c l e 作为数据库管理软件的关系数据库。s m d 来自 微阵列实验的原始和均一化了的数据。 1 1 2 数据预处理 对基因表达数据进行聚类、分类等数据分析之前，由于数据中难免存在不完 整的和不一致的数据，引起系统误差。所以需要进行预处理，包括对填补丢失数 据、剔除极端数据、根据不同的目的过滤数据以及针对分析方法选择合适的数据 转换和标准化等等1 4 1 。在处理基因芯片的过程中，每一步都得具有一定生物学意 义，否则再精确的计算也是徒劳。 ( 1 ) 数据的填补 在d n a 微阵列数据中，数据的丢失有很多原因导致许多数据分析方法不能正 常使用。比如载玻片上由于各种原因信号过弱、样本被污染和图像的分辨率不够 高等都可能造成数据的丢失。需要完整的基因表达矩阵的独立分量分析和主分量 基丁启发式聚类的混合特征基冈选择方法研究 分析等来填写空缺和平滑噪声。不能够简单将这些包含数据丢失的基因删除，否 则将可能造成丢失许多有用信息，这样做还会明显削弱许多聚类算法的分类效果。 ( 2 ) 极端数据的剔除 极端数据是指那些偏离群体分布的数据。它包括两种情况：单个微阵列上的 某个基因点的表达异质和整个微阵列异质。微阵列异质是指同一类型的微阵列中 有一些微阵列由于产生太大的变异性而不能使用。因此要注意，在这种缺乏重复 点的情况下，微阵列上最高和最低的数值常常被当做极端数据修正。另外，极端 数据也可以通过设置判断阈值行识别，该阈值可以根据整个表达数据分布百分位 点或一定的标准差范围来设置。极端数据的剔除过程需要不断重复直至不再有极 端数据发现为止。在有重复点的情况下，极端数值的识别通常在重复点内进行， 识别和剔除方法类似上述没有重复点时的情况。 ( 3 ) 数据的标准化归一化处理 分类一般可以直接使用基因表达的实际数据，但聚类时表达数据的标准化是 必要的。原始d n a 微阵列数据往往同时包含大量的实验随机误差和系统偏差。各 种微阵列数据的归一化方法由于都有其相应的假设前提，因此也都有各自的缺陷 和不足。探索和改进微阵列数据的标准处理方法也是微阵列数据处理中的重要研 究内容，有许多的研究人员致力于这项内容的研究。归一化其实是将所有的数据 转换到同一个范围内，这样做的好处是方便比较和计算相关系数，这也是首先要 进行数据过滤的一个重要理由。 经过这些处理后的数据，把所有因实验过程中出现的误差降到最小的程度， 更有利于下面我们应用表达谱数据来选择特征基因。 1 2 本文特征基因选择研究路线 l i uh 和y ul i 提出了一个基本的特征选择算法框架，认为一个基因的特征 选择过程必须确定如图1 1 所示的四个方面。 图1 1 特征选择算法框架 按照此模型，结合特征基因选择的特点，我们按图1 2 的研究路线来选择特征 4 硕上学位论文 基因。 图1 2 研究路线图 步骤如下：首先第一步清除冗余数据，从而剔除大量的噪声数据，降低维度。 否则高维度数据将给我们带来的是维数灾难，它将会使有用的信息淹没在噪声中， 而且高维的数据将大大增加算法的复杂度。然后，我们拿在第一步当中选择出的 基因用聚类算法特征基因的选择，这也是实验中最为关键的一步。此过程中要应 用支持向量机和分类预测评估方法，结合预测的结果调整参数以达到最佳的聚类 效果。对聚类结果再按一定的方法精选特征基因子集。 1 3特征基因选择方法研究现状 特征基因选择是专门针对基因表达谱数据的一种特征选择。1 9 9 9 年癌症研究 所基因组研究中心g o l u b 博士领导的研究小组【1 3 】利用d n a 芯片测定的急性白血病 基因表达谱数据集，发表了针对急性白血病亚型识别与信息基因选取问题的研究 结果，以“信噪比”指标作为衡量基因对样本分类贡献大小的量度，采用加权投 票的方法进行亚型的识别，并从7 1 2 9 个基因中选出了5 0 个可能与亚型分类相关的 信息基因。成功地对两种亚型a l l 和a m l 进行了分类。自从此篇文章发表后，大 量有关d n a 芯片的特征基因选择算法开始涌现，为d n a 芯片技术的研究应用开拓 发展做出了重要的贡献。研究者们已经研究了基因选择的各个方面。从最早期的 主要基于统计测试的方法，到近年来机器学习和数据挖掘等多个领域的方法，尤 其是属性选择技术被广泛用于微阵列数据的基因选择。而对于特定的基因芯片数 据集，不同的特征选择算法的所表现出的性能优势也各不相同。有的算法能得到 很高的分类正确率，但是所选择的特征基因数却比较多；有的算法能得到较少的 基因，但是时间复杂度又过大；而有些时间复杂度小的方法，其分类正确率却不 令人满意；有些方法即使能有较高的分类正确率和较少的特征基因，但是其选择 基于启发武聚类的混合特征基冈选择方法研究 的特征基因与疾病的机理相关性不大i5 1 。因此，对于特定的基因芯片数据集，我 们应该考虑多个算法的混合，综合其优势将其各方面优点有效地结合起来使得性 能在各个方面都令人满意。 1 4 本文主要工作及结构安排 本文以生物信息学为背景，对基因表达谱进行深入研究。以基因微阵列矩阵 作为数据，提出两种基于聚类的特征基因选择算法，并以支持向量机分类器测试 选出的特征基因的分类能力，目的是使得到的特征基因数量最小化而准确率最大 化，同时还要考虑其泛化能力。主要工作内容分为如下五章： 第一章，绪论，我们简单介绍基因芯片的相关背景知识，着重介绍了基因选 择的前期准备工作。并简要说明了本文所做的主要研究路线、工作内容以及本文 结构的安排。 第二章，对特征基因选择方法进行了详细的阐述，包括常见的分类器的介绍 以及目前特征基因选取的研究现状。 第三章，提出一种基于最小生成树聚类的特征基因选择算法。 第四章，提出一种基于分步聚类的特征基因选择算法。实验结果表明，本文 的方法能有效的降低特征基因的维数并有很好的分类效果和泛化性能。 最后是对全文的一个总结。 6 硕士学位论文 第2 章特征基因选择方法基础 特征选择的概念被很多学者从不同的角度定义过。m a n o r a n j a nds 和h u a n l 【1 2 】总结出理想化、经典、提高分类准确率及逼近原始类别分布四种不同的定义。 理想化定义：特征选择就是找数目最小的特征子集，同时这个特征子集包含 了目标任务需要的信息。 经典定义：从n 个特征中选出m 个特征组成特征子集s ( m n ) ，使得在所有大 小为m 的特征子集中，s 使得目标函数值最优。 提高分类准确率定义：特征选择是要选出一个特征子集提高分类准确率，或 者在不降低分类准确率的前提下大大降低数据集的维度。 逼近原始类别分布定义：特征选择的目的是选出一个特征子集，使得特征子 集表示的数据类别分布和原始数据集上的类别分布尽量接近。 这四种定义汇总起来可以描述为从原始特征空间中选择最小的特征子集，使 得对该子集的操作可以很好地代替在原始特征空间的操作，在特征子集表示的数 据上做分类等学习任务可以减少存储空间、加快算法运行速度、提高学习算法的 效率，但不降低分类准确率。 2 1特征基因选择方法 目前，特征基因选择方法归为以下四类：( 1 ) 过滤法( f i l t e r ) 【1 4 2 8 】；( 2 ) 绕法 ( w r a p p e r ) 1 2 9 3 6 】；( 3 ) 过滤法与缠绕法混合方法( h y b r i d ) 【3 7 】；( 4 ) 嵌入法。 2 1 1过滤法 过滤法即传统的基于单个基因的选择方法，根据判别标准值来对基因属性进 行排序、选择。所以该方法比较简单，并且已被广泛运用在基因表达数据分析中。 过滤法采用不同的判别标准来排列每个基因属性的重要性( 即该属性在对疾病诊 断过程中所起作用的程度) 。首先基于某种评估方法针对每个基因进行单个评估 以反映该基因与相关样本的关联度；然后根据每个基因的评估值进行排序，选择 排序靠前的基因。目前常用的过滤式评价策略有：基于距离、基于信息、基于独 立性和基于连续性【1 4 ，1 5 】的评价策略。 ( 1 ) 基于距离的方法也叫做基于分散度、基于分辨度的方法，典型的距离有 欧式距离、马氏距离、曼哈顿距离和b h a t t a c h a r y y a 等。 ( 2 ) 基于信息的验证方法是指从一个特征自身获取信息，信息定义为特征得 到的先验概率与后验概率之差。如信息增益、互信息或关联度。 7 基于启发式聚类的混合特征基因选择方法研究 ( 3 ) 基于独立性的检验方法是指它检验一个变量预测另一个变量的方法效 果。例如以分类错误率为学习算法指导，对一个选中的特征集合我们可以比较它 对学习算法分类错误率的贡献与特征全集相应贡献来评价特征选择算法的优劣。 ( 4 ) 基于连续性的检验方法，和其它方法不同之处在于它依赖类别信息和最 小特征偏差来选择特征。 对于特征基因的选择，常会结合两种或两种以上的过滤法来完成特征的选择。 如基于距离的方法可以应用独立性检验方法来分析结果的好坏。下面介绍一些特 征基因选择过滤法： j o s eb 【1 6 】等的文章用r e l i e f 算法是在训练集中以两个样本间的距离为标准搜 索某一样本的近邻的过程。在距离计算过程中所有属性均参与计算。另一篇文章 【1 7 1 提出了基于r e l i e f 的组合式特征选择算法：r e c o r r e 和r e s b s w 。这两种算法先利 用r e l i e 挝滤掉无关特征，然后采用相关分析以及顺序向后搜索的缠绕法算法去除 冗余特征。后者的方法虽然准确率高于j o s eb 等的r e l i e f 算法，但是运行效率降低 了。 信息增益( i n f o r m a t i o ng a i n ) 法是基于信息验证的方法在数据挖掘中1 1 8 】这样引 用信息增益法，对任意样本分类的期望信息： j ( s l ，s 2 ，k ，s 研) = 一只l 0 9 2 ( 仍) ( i = l m )( 2 1 ) s 是s 个数据样本的集合。类别属性具有m 个不同值c 。s 是类c 中的样本数。 阢是任意样本属于c 的概率，并用墨s 估计。 由非类别属性a 划分为子集的熵： e ( a ) 2 ( 而+ k + j 彬) s 宰，( 墨，k ，s 耐) ( 2 2 ) 非类别属性a 具有v 个不同值他，口2 ，l ，q ) 。利用a 将s 划分为v 个子集 “，s ：，l ，& ；其中s ，表示包含在s 中且在a 上具有值口，的样本。是子集s ，中类q 的样本数。信息增益用式2 3 表示： g 白加( 彳) = ，( 墨，s 2 ，l ，s 。) 一e ( 彳) ( 2 3 ) 任江涛【1 9 1 在他们的文章中采用信息增益作为特征之间的相似性度量，并采用 一种基于密度的分组方法进行特征分组，实现特征的精简。首先令x 为随机变量， 则x 的信息熵定义为： 日( y ) = 一p ( _ ) l o g ( p ( t ) ) ( 2 4 ) f 通过观测在随机变量y 的情况下，则随机变量x 的信息熵变为： 日( x i 】，) = 一尸( 乃) p ( l 乃) 1 0 9 ：( 尸( 薯i 乃) ) ( 2 5 ) 其中尸( 薯) 代表随机变量x 的先验概率，尸( 薯i 乃) 代表观测到随机变量乃后随机 8 硕j j 学位论文 变量善的后验概率。引入随机变量y 的信息后，随机变量x 的信息熵满足 h ( x l 】，) h ( x ) ，即引入y 后x 的不确定程度会变小或保持不变。若y 与x 不相关， 则日( x i y ) = 日( x ) ；如果y 与x 相关，则日( x | y ) h ( x ) ，而差值日( x | y ) 一日( x ) 越 大，表示y 与x 的相关性越强。因此，式2 6 定义信息增益反映了y 与x 的相关程度， 佑( x i 】，) 越大，则变量y 与x 的相关性越强。 佑( x l 】，) = h ( ) 一日( xl y ) ( 2 6 ) 可以证明，信息增益具有对称性，即粥( x i 】，) = 佑( y i x ) 。另外，为了对信息 增益进行归一化，可采用公式2 7 ，同理有s u ( x ，y ) = s u ( 】，x ) 舳( 埘) _ 2 【器】 ( 2 7 ) 文献【2 0 】引入了一个新的平衡的信息增益的方法来评估每个属性的作用，这 是考虑了特征属性对分类所起的作用和特征属性之间的相互关系。 “信噪比”指标是特征基因选择中常用到的一种过滤法，是g o l u b 等【1 3 1 作者 对样本信息所做的度量公式，如下： s 2 ( g f ) ：幽 ( 2 8 ) o l o i 正负表示基因的两种样本，p ? 、p f 表示每个基因的两种样本表达值的均值， 仃? 、仃_ 表示每个基因的两种样本表达值的方差。作者李颖新，阮晓钢【2 1 1 修改了 该方法。不仅如“信噪比 一样考虑了衡量基因含有样本分类信息多少的度量信 息的问题，一还考虑到方差不同所带来的对样本分类的贡献，这样可以更加全面地 评价基因含有的分类信息量。对g 0 1 u b 等提出的“信噪比”指标进行了修正后的指 标为： ，崛) ：崞掣“( 粤半里) ( 2 9 ) o ，十仃fz o ，o f 它由两部分构成，第一部分实际上是g o l u b 等人定义的“信噪比 指标；第二 部分体现了表达水平分布方差的不同对样本分类的贡献。依据该公式，即使基因 在硒类不同样本中表达水平的均值相同，只要分布方差出现大的差别，仍可以获 得较大的分类信息指数值。 更进一步，如果假设两类样本的分布都服从高斯分布，则可根据基因g ，采用 b h a t t a c h a r y y a 距离作为两类样本的可分性判据，称之为b h a t t a c h a r y y a 特征记分准 贝0 ( b h a t t a c h a r y y af e a t u r es c o r ec r i t e r i o n ，b f s c ) 【2 2 1 ，即以式 剧粥( g ，) = ( ( 一) 2 2 + 町2 ) ) + 去l i l ( ( 仃? 2 + 町2 ) ( 2 吖仃f ) ) ( 2 1 0 ) 来度量基因的分类能力。与式上一个公式对比发现，二者虽然在形式上比 较相似，但该方法是有依据的：朱云华等【2 3 】采用b h a t t a c h a r y y a 距离度量基因的分 9 基于肩发式聚类的混合特征堆冈选择方法研究 类能力并在小圆蓝细胞瘤( s m a l lr o u n db i u ec e l l st u m o r ，s r b c t ) 数据集上进行 实验获得了较好的实验结果。具体方法是首先通过式2 1o 为每一个基因 岛g ，1 f 刀计算b f s c 值，然后按照b f s c 值大小对全部基因进行降序排列并选 择前p 个基因作为初选信息基因集合g + ，通常p p ( c ，i x ) ，1 聊，f 。根据贝叶斯 定理，最大化后验概率可转化为最大化先验概率。据此，对一个未知的类别样本 x ，可以先用公式计算出x 属于每一个类别e 的概率尸( 石i g ) 尸( g ) ，然后选择其中 概率最大的类别作为它的类别。 朴素贝叶斯分类器的分类能力由于其结构简单并且迅速，目前已得到大量应 用。但是由于朴素贝叶斯分类器属性之间条件的假设约束，很多现实世界的数据 并不符合，因此它的应用受到了限制。近年来，许多研究人员致力于放松特征独 立性的限制，以使其适用于更大的范围。贝叶斯网络又称为信度网络，是贝叶斯 公式的扩展。贝叶斯网络分类器便能很好的描述变量属性间的因果关系，摆脱属 性条件的限制。它结合图论和概率理论方面的知识，表达随机变量之间复杂的不 确定性关系，并提供了一种自然的表示因果关联的方法，可以用于发现数据间的 潜在关系【5 。 2 3 4 支持向量机 支持向量机( s v m ) 是数据挖掘中的一种新方法，能非常成功地处理回归问题 1 9 基于启发式聚类的混合特征基因选择方法研究 ( 时间序列分析) 和模式识别( 分类问题、判别分析) 等诸多不同领域的问题， 并可推广于预测和综合评价等领域【52 1 。所谓支持向量是指那些在间隔区边缘的训 练样本点。这里的“机”这里理解为机器，实际上是一个算法。在机器学习领域， 常把一些算法看做是一个机器。支持向量机是由v a p n i k 等人【5 3 】基于统计学习理 论，采用结构风险最小化原理提出的一种机器学习算法。支持向量机较适合处理 基因芯片数据这种样本少、非线性和高冗余的数据集分类和特征选取问题。目前 国际上支持向量机在理论研究和实际应用两方面都正处于飞速发展阶段。 图2 5 最优分类面不慝图 支持向量机方法基本原理简述如下： 有未知类别的向量x ，s v m 分类为一l 或l ，令分类线方程w x + 6 = o ，可以对其 进行归一化使得线性可分的样本集( 葺，此) ，江l ，2 ，3 l ”，x 尺d ，y + 1 ，一1 满足 乃 w 。薯+ 6 卜l o ，f = l ，2 ，l 聍。此时分类间隔等于2 | l 叫l ，使间隔最大等价于使0 叫1 2 最 小，满足上述条件且使妻0 w 0 2 最小的分类面就是最优分类面。如图2 5 ，实心点和 空心点分别代表两类样本，h ，为分类线，h 、见分别为过各类中离分类线最近 的样本且平行于分类线的直线，它们之间的距离叫做分类间隔( m a r g i n ) 。所谓的 最优分类线不仅要求分类线能将两类正确分开( 训练样本的错误率为0 ) ，而且使 分类间隔最大。 在最优分类面中采用适当的内积函数 ，x ，) 就可以实现某一非线性变换后的 线性分类而计算复杂度却没有增加，此时目标函数变为： q ( 口) = q 一去口巳 乃k o ，_ ) ( 2 18 ) 持l ，= l 相应的分类函数转化为： 2 0 硕+ 学位论文 厂( 工) = s 馏 彳咒k ( 薯，x ) + 6 ( 2 1 9 ) 扛l 其中n 为支持向量机的个数，k ( j c f ，x ) 为核函数，它的作用是平滑( 低通滤波) 相似性度量。支持向量机由训练样本与核函数确定5 4 ，5 5 1 ，而关键在于核函数。低 维空间向量集通常难于划分，解决的方法是将它们映射到高维空间。但这个办法 带来的困难就是计算复杂度的增加，而核函数正好巧妙地解决了这个问题。也就 是说，只要选用适当的核函数，就可以得到高维空间的分类函数。在s v m 理论中， 采用不同的核函数将导致不同的s v m 算法。 表2 1核函数 核函数名称 k ( 薯，工) = o 。葺) 口 k ( 玉，工) = ( x r 毛+ c ) d k ( ) = e x p ( 一刍卜薯| 1 2 ) k ( 薯，工) = 切n ( 成z r 毛+ 肛) k ( 薯，工) = i 卜一薯1 1 2 肿1 k ，x ) = 忙一t pi n ( 忙一薯l i ) 齐次多项式核函数 非齐次多项式核函数 径向基核函数 s i g m o i d 核函数 薄板核函数 样条核函数 支持向量机方法的优点在于其目标是得到现有信息下的最优解而不仅仅是样 本数趋于无穷大时的最优值。算法最终将转化成为一个二次型的寻优问题。从理 论上说，得到的将是全局最优点，解决了在神经网络方法中无法避免的局部极值 问题。当它一旦得到了正确的参数，这种分类器的执行效果，与其它分类方法相 比，有可能会不相上下或更胜一筹。该算法将实际问题通过非线性变换转换到高 维的特征空间，在高维空间中构造线性判别函数来实现原空间中的非线性判别函 数，特殊性质能保证机器有较好的推广能力，同时它巧妙地解决了维数灾问题， 在接受训练之后，它们在对新的观测数据进行分类时速度极快，这是因为分类时 只须判断坐标点位于分界线的哪一侧即可。通过将分类输入转换成数值输入，可 以令支持向量机同时支持分类数据和数值数据。 支持向量机的缺点在于，针对每个数据集的最佳核变换函数及其相应的参数 都是不一样的，这就要求每当遇到新的数据集时都必须重新确定这些函数及其参 数。在可能的取值范围内进行循环遍历会有助于这一问题的解决，但是这要求我 们有足够大的数据集来完成可靠的交叉检验。所以，s v m 更适合于那些包含大量 2 l 耩于启发式聚类的混合特征基因选择方法研究 数据的问题。而且和神经网络一样，s v m 也是一种黑盒技术。由于存在向高维空 间的变换，s v m 的分类过程甚至更加难于解释。s v m 也许会给出很好的答案，但 是我们永远都无法得知找到答案的真正原因。而其他方法，如决策树，则更适合 于小规模的数据集，并且这些方法还能从数据集中得到一些很有价值的信息。 2 4小结 本章按照过滤法、缠绕法、过滤法与缠绕法混合和嵌入式方法分成四大类来 详细的介绍了以往的特征基因选择算法。同时，详细的介绍了基于聚类的微阵列 数据处理方法。另外，对常应于特征基因选择算法当中分类器的原理进行了详细 叙述，包括人工神经网络、决策树、贝叶斯和支持向量机。 硕上学位论文 第3 章基于最小生成树聚类的特征基因选择方法 3 1最小生成树原理 最小生成树( m i n i m u ns p a n n i n gt r e e ) ，简称为m s t 。它是贪心算法的一个典 型应用，贪心算法又叫启发式算法。一个无向图的生成树不是唯一的，同样的， 一个赋权图的最小生成树也不一定是唯一的。求无向赋权图的最小生成树的方法 很多，下面介绍两种经典算法【5 6 1 。 ( 1 ) k r u s k a l 算法基本思想如下：设无向网络g = ( v ，e ，w ) 有n 个顶点，m 条边 将m 条边按权从小到大的顺序排列，设为q ，吃，l ，。先选择权重最小的边q ，把 它放进树t ，然后依次检查q ，乞，l ，若p ，与t 中的边不能构成圈，