肿瘤特征基因提取方法研究.pdf

电 子 科 技 大 学 university of electronic science and technology of china 硕士学位论文 master dissertation （电子科技大学图标） 论 文 题 目： 肿瘤特征基因提取方法研究 学 科 专 业： 生物医学工程 指 导 教 师： 饶妮妮 作 者 姓 名： 张娅 班 学 号： 200520901010 分类号 密级 udc 学 位 论 文 肿瘤肿瘤特征基因提取方法研究特征基因提取方法研究 （题名和副题名） 张娅张娅 （作者姓名） 指导教师姓名 饶妮妮饶妮妮 教授教授 电子科技大学电子科技大学 成都成都 （职务、职称、学位、单位名称及地址） 申请学位级别 硕士硕士 专业名称 生物医学工程生物医学工程 论文提交日期 2008.5.62008.5.6 论文答辩日期 2008.5.242008.5.24 学位授予单位和日期 电子科技大学电子科技大学 答辩委员会主席 评阅人 年 月 日 注 1 注明国际十进分类法 udc的类号 独 创 性 声 明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名： 日期： 年 月 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 （保密的学位论文在解密后应遵守此规定） 签名： 导师签名： 日期： 年 月 日 摘要 i 摘 要 肿瘤的发生和发展是一个复杂的多阶段过程。它通常是由于某些基因突变和 异常表达所致，或者进一步影响另外一些基因的表达，从而导致细胞内一些蛋白 质分子发生改变，并由此产生肿瘤病理学上的差异，因而形成了临床诊断中的不 同分类。所以肿瘤治疗的挑战在于不同病理的肿瘤类型需要相应的治疗方案，从 而获得最大的功效并使患者受到最小的伤害。而对于肿瘤基因表达数据集进行分 类是治疗中的一个关键的问题。 本文研究了肿瘤基因表达谱数据，根据其数据特性和生物机理，提出了两种 特征基因选择的方法。本文主要做了以下几方面工作：第一，提出了 kmeans_iic 方法。将此算法应用到结肠癌表达谱数据中，提取到 22 个特征基因并且正确率达 到 86.4%。继续推广到前列腺癌、混合系白血病表达谱数据的特征基因选择中，其 正确率分别达到 92.29%和 93%，并且获得重要的特征基因。从而说明该方法能从 庞大的基因表达谱数据中提取重要的特征基因，并且所提取的特征基因对疾病的 临床诊断和生物医学研究有重要的参考和借鉴作用。 第二， 提出 relief_ aga _svm 方法 。此方法是结合算法，主要使用自适应算法并结合模式识别的方法来提取特 征基因。它弥补了遗传算法易于陷入局部收敛的缺点。将其应用于肿瘤基因的特 征提取，不仅较好地提高了算法的效率，也识别出重要的特征基因。 关键词：关键词：数据挖掘，分类信息指数，支持向量机，relief 算法，自适应遗传算法 abstract ii abstract the occurrence and development of tumor is a complex and multi-stage process. usually its because of some gene mutation and abnormal expression or further affecting other genes expression, which results in the change of protein molecules within cells and produces the tumor differences in the pathology and different classification in the clinical diagnosis. therefore, the challenge of treatment in tumors is providing different patients with appropriate treatment methods, in order to get the best efficiency and do the least harm to patients. however, classification is a key question to tumor gene expression data sets. the tumor gene expressing datasets are researched in this paper. two new methods of feature genes selection are proposed according to the data characters and biology mechanism. the main work is as follows: firstly, kmeans_iic method is proposed, and applied to the datasets of colon cancer, prostate cancer and mll to select feature genes .this method gets a better result and important feature genes from a great number datasets of gene chips, and it has important reference to the clinic diagnosis and biomedical research of disease. secondly, relief_aga_svm is proposed. it combines adaptive genetic algorithm with pattern recognition together to extract feature genes and retrieves the convergence fault of ga. the results showed that it can get a better effect for selecting feature genes. keywords: data mining, ici, support vector machine (svm), relief algorithm, adaptive genetic algorithm 目录 iii 目 录 第一章第一章 绪论绪论 . 1 1.1 基因表达数据的概念 . 1 1.2 基于基因表达数据提取肿瘤特征的研究现状 . 2 1.3 本课题的研究目的和意义 . 4 1.4 主要内容与创新点 . 6 1.5 论文结构与安排 . 7 第二章第二章 相关算法的理论基础相关算法的理论基础 . 8 2.1 数据挖掘 . 8 2.1.1 数据挖掘的定义 . 8 2.1.2 数据挖掘的功能 . 9 2.2 特征选择方法综述 . 10 2.2.1 特征选择的基本概念 . 10 2.2.2 典型特征选择算法 . 11 2.3 支持向量机 . 12 2.3.1 用于两类分类的支持向量机 . 12 2.3.2 用于基因表达数据的支持向量机 . 15 2.4 遗传算法 . 16 2.4.1 机理 . 16 2.4.2 遗传算法的特点 . 16 2.4.2.1 遗传算法的优点 . 17 2.4.3 实现步骤 . 18 第三章第三章 基于基于 k kmeamean ns_iics_iic 特征选择算法特征选择算法 . 20 3.1 相关算法 . 20 3.1.1 kmeans_iic 算法 . 20 3.1.1.1 kmeans 算法思想 . 20 3.1.1.2 分类信息指数 . 22 3.1.2 基于支持向量机的样本分类 . 23 3.2 实验 . 23 目录 iv 3.2.1 实验数据描述 . 23 3.2.2 实验参数与步骤 . 24 3.3 试验结果与分析 . 24 3.3.1 试验结果 . 24 3.3.2 对照试验 . 25 3.3.3 比较研究 . 26 3.3.4 生物学意义解释 . 26 3.4 算法应用推广 . 28 3.5 小结 . 35 第四章第四章 基于基于 relief_aga_svmrelief_aga_svm 特征选择算法特征选择算法 . 36 4.1 算法提出的动机 . 36 4.1.1 relief 评估算法 . 37 4.1.2 k最邻近方法 . 38 4.1.3 自适应遗传算法 . 39 4.2 relief_aga_svm 算法描述 . 40 4.3 统计分析 . 43 4.4 试验数据 . 44 4.4.1 数据集 . 44 4.4.3 实验步骤 . 44 4.5 试验结果与分析 . 45 4.5.1 选主基因 . 45 4.5.2 分类预测 . 47 4.5.3 比较分析 . 47 4.5.4 生物意义分析 . 47 4.6 小结 . 48 第五章第五章 结论和展望结论和展望 . 50 致致 谢谢 . 51 参考文献参考文献 . 52 攻硕期间取得的研究成果攻硕期间取得的研究成果 . 55 第一章 绪论 1 第一章 绪论 基因调控研究表明，人体每一细胞、每一组织，在不同的发育、分化阶段， 不同的生理条件和病理状态下，其表达的基因种类以及每一基因的表达丰度都是 各不相同的，且此差别存在严格调控的时空特异性。生命过程的精确机制很大程 度上正是基于这类基因的精细调控。许多生命现象的深层次问题都集中于此，使 基因组研究的焦点从结构基因组研究转到后基因组的研究，其研究的重点是基因 功能的研究，并结合基因功能解决生物医学中的基础和应用问题，对基因水平上 的疾病治疗和新药开发等具有重要意义。 1.1 基因表达数据的概念 基因表达谱是通过构建处于某一特定状态下的细胞或组织的非偏性 cdna 文 库，大规模 cdna 测序，收集 cdna 序列片段，定性、定量分析其 mrna 群体组 成，从而描绘该特定细胞或组织在特定状态下的基因表达种类和丰度信息，编制 成的数据。该谱实际上从 mrna 水平反映了细胞或组织特异性表型和表达模式。 如果收集各类组织和细胞的基因表达谱，将每一个表达的基因标记到其表达的组 织，就能组成一张人体基因图；抑或对这些各不相同的基因表达数据作两两或多 重比较，就能筛选出细胞特异性或发育阶段特异性的基因，这项工作无疑将对阐 释基因表达调控机制十分有益。 基因表达数据反映的是直接或间接测量得到的基因转录产物 mrna 在细胞中 的丰度。这些数据可以用于分析哪些基因的表达发生了改变，基因之间有何相关 性，在不同条件下基因的活动是如何受影响的。目前，对基因表达数据的分析主 要在三个层次上进行：分析单个基因的表达水平，根据在不同实验条件下，基因 表达水平的变化，来判断它的功能。例如，可以根据表达差异的显著性来确定与 肿瘤分型相关的特异基因；考虑基因组合，将基因分组，研究基因的共同功能、 相互作用以及协同调控等。 基因表达数据是本文研究所采用的样本数据，它主要由基因芯片技术获得。 在 smd 数据库中，一次实验的数据就是一个nm的矩阵，表示m个基因在n个 实验条件 （n张芯片） 下的表达水平。 ji o , 表示第i个基因在第j张芯片上的表达值。 电子科技大学硕士学位论文 2 i o为矩阵o的第i行，表示基因i，任何两个基因 i o和 j o之间的相似性，可以通过 矩阵o中第i行与第j行的相似程度来表示； i o为矩阵o的第i列， 表示第i个实验， 任何两个变量 i o与 j o之间的相似性可以通过第i列与第j列的相似程度来表示。微 阵列数据的表达如下所示： nmmm n n m n ooo ooo ooo o o o ooo o ,2,1 , , 22, 21 , 2 , 12, 11 , 1 2 1 21 （1-1） 1.2 基于基因表达数据提取肿瘤特征的研究现状 从临床病因学的角度上，基因表达的改变和疾病的关系比基因结构或序列的 改变与疾病的关系更加直接，因此对基因表达数据的分析，有助于寻找肿瘤细胞 和正常组织细胞之间的差异表达基因，识别肿瘤发生、发展的相关细胞通路，观 察肿瘤治疗所引起的基因表达变化，探究肿瘤细胞对临床治疗反应的决定性因素 以及预后分析。 为了从表达数据中挖掘出重要的基因，需要借助于模式识别，数据挖掘等方 法。目前常用的国内外的研究方法主要由有监督聚类分析和无监督聚类（分类） 方法。 1聚类分析1 聚类分析就是把p维空间中的n个观测个体 n21 x,.,x,x分到k个组中，这种过程 可以描述为使用某函数c实现数据从高维观测空间到低维分类空间的投影，观测i 投影到类)(ic中的值。聚类算法的任务就是寻找这种最优的函数c，使得类内的非 相似性达到最小。聚类算法常被分为两大类：分割方法（partitioning methods）和 系统方法（hierarchical methods）。分割方法把观测个体最优地分割到固定数目的 类中，系统方法将产生类的嵌套式的分类序列。 2分类方法 分类方法就是利用一个训练集，其中包含属于某个功能类和不属于该功能类 的若干基因样本，以此来训练模型，帮助识别哪些样本应该划分为一类。常用的 分类方法主要有最近邻分类器（knn）2，决策树（dt），神经网络（ann）3， 支持向量机（svm）4等。 第一章 绪论 3 通过阅读大量的文献，可以了解到在基因芯片特征基因选择上，所用到的特征 选择方法主要有：xiong等人在特征wrappers的基础上，通过分类误差来选择鉴别 基因5 。guyon等人提出了递归特征减少法(recursive feature elimination，rfe)，借 助支持向量机(support vector machines，svm)递归去除分类函数中关联权重对中值 最小的基因，得到基因集合的排序来选择鉴别基因6。然而，该方法需要很大的计 算量。ben-dor等人在一维空间为每个基因搜索一个最优判别点，然后根据此判别 点进行样本分类，借助分类误差和tnom数(threshold number of misclassification)来 选择特征基因7。这种方法的缺点是搜索最优判别点的计算复杂性大。上述方法均 使用具体分类器或分类误差来选择特征基因，得到的基因选择结果容易受到具体 分类方法的影响。lee等人基于分层bayesian线性模型，结合马尔可夫链蒙特卡罗 方法和gibbs抽样来估计每个基因在模型中出现的概率，根据概率的大小来选择特 征基因8。基因表达数据通常含有噪声，而且不同数据间的差异很大，因此，很难 构造一个适用于所有基因表达数据的数据模型，基于数据模型的基因选择方法的 适用性较差。golub等人使用均值和方差构造的统计量作为鉴别基因的选择测度 。 也有的文献直接使用两样本t统计量(two sampled-statistic)来选择基因9。ba和 jonassen提出了一种成对基因选择方法，该方法把每个样本在一对基因上的表达数 据(二维空间中的点)投影到样本点的线性判别界面的垂直线上， 然后用投影点的两 样本t统计量为测度来选择基因10。 由于非参数方法不需要假定一个具体的数据分布，因此比较适于用分析基因 表达数据。针对两个类别的情况，park等人首先有序地组织样本，使得类别1的样 本位于基因表达矩阵的左边，类别2的样本在右边，并为类别1和类别2的样本分别 分配标签0和1；然后，在每个基因上对所有样本的表达值按大小排序，此时，有 序的标签序列可能被破坏；接着两两交换样本，使得所有标签有序，以最小的交 换数目作为这个基因的得分来排序和选择基因。dudoit等人用between-group和 within-group的差别平方和之比bw来排序和选择基因。cho等人用样本到某一类质 心距离的平均值和标准差来选择基因11。 feng等人用遗传算法来进行选择基因12。 由于基因芯片数据样本数量少（以十或百计）、特征基因维数高（以千或万 计）及芯片数据高信噪比的特点，最佳的芯片数据分析策略应是通过识别相关基 因，排除不相关基因，噪声基因以及冗余基因来降低特征基因的维数。 但是目前特征选择算法的着眼点主要放在选择优化特征集合所需要的两个步 骤上。要确定关键的变量，即优化的特征子集。首先必须确定进行搜索所需要的 策略；其次，必须确定一些评价准则，根据准则来评价所选择的特征子集的好坏 电子科技大学硕士学位论文 4 程度。因此，可以把特征选择方法从这两个角度分类:一是按搜索策略划分,如穷 举法、启发式搜索(向前、向后)法、随机化搜索法(遗传算法) 等;二是按照评价 策略划分,如过滤(filter)法(秩、信息增益和马尔可夫链等)，缠绕(wrapper)法。 filter 和 wrapper 的组合式特征选择算法是主要的路线。因为组合式算法集合了它 们各自的优点。从下面几点分别具体介绍近几年国内外用得比较多的特征选择方 法： 统计学理论中的方法：假设检验（t-test）,t-统计量，方差分析(anova）, 非参数检验法，wilcoxon符号秩检验，mann-whitney检验，以及利用均值和方差构 造的信噪比指标等。根据其对基因的排秩次序来选择特征基因。 信息论中的信息熵： 信息增益 （information gain） 、 最小描述长度(minimum description length method)、 互信息 （mutual information， mi） 和关联度 （correlation） 等来进行特征基因选择；这些方法的优点是适用于大规模的数据集，具有较强的 理论基础；但是不适用于特征相关性较强的领域，且只适用于离散型特征。如， 互信息（mi）13-14与粗糙集（rough set）结合用来对特征基因的选择。 利用支持向量机（support vector machine, svm）15-16进行特征选择，一 般都把它和递归特征消除法（recursive feature eliminate, rfe）结合起来，通常还 进一步的与模糊 c 均值聚类结合成为 fcm-svm-rfe 算法 17-18，遗传算法结合成 ga-svm-rferelief-rfe-svm 等，使之特征基因选择的准确率提高。然而由于 递归特征消除法的运行速度慢，每次仅能去除一个基因，在大多数文献中，为了 提高速度，就采用的经验方法，每次消除排在后面的一些基因，为了有更强的理 论依据，就又提出了 a-svm-rfe 的算法。 其他的方法，如决策树（decision tree method, dtm）、随机森林和决策森 林法。这几种算法都是基于决策树决策树是以实例为基础的归纳学习算法。它 通常利用已知类别的样本信息,采用自顶向下的递归方式，在决策树的内部结点进 行属性值的比较并根据不同的属性值判断从该结点向下的分支，即分类，直到各 个叶子结点中包含的样本达到一定的纯度或满足某个终止条件为止。这样，当一 个决策树生成时，它的每一个内部结点的分割都对应着选出的一个特征属性。 1.3 本课题的研究目的和意义 通过生物信息学分析，可以了解基因与疾病的关系，了解疾病产生的机理， 为疾病的诊断和治疗提供依据。研究生物分子结构与功能的关系将是研制新药的 第一章 绪论 5 基础，可以帮助确定新药作用的目标和作用的方式，从而为设计新药提供依据。 揭示人类及重要动植物种类的基因的信息，继而开展生物大分子结构模拟和药物 设计，是当今国际上正在迅速发展的自然科学领域最重大的课题之一，这方面的 研究不仅对认识生物的起源、对认识生物遗传、发育与进化的本质有重要意义， 而且将为人类疾病的科学诊断和合理治疗开辟全新的途径。 然而肿瘤的发生和发展是一个复杂的多阶段过程。它通常是由于某些基因突 变和异常表达所致，或者进一步引起另外一些基因的表达发生变化，从而导致细 胞内一些蛋白质分子发生改变，并由此产生肿瘤病理学上的差异，因而形成临床 诊断中的不同分类。所以肿瘤治疗的挑战在于为不同病理类型提供相应的治疗方 案，从而获得最大的功效并使患者受到最小的伤害，而对肿瘤基因表达数据集进 行分类是治疗中的一个关键的问题。 我们知道传统的肿瘤识别主要基于肿瘤组织的外部形态，但该方法的有效性 是不可靠的。具有相似外部形态结构的肿瘤可能在临床诊治过程中有很大变化。 患者对于相同诊疗方案的临床反应也可能有很大区别，这亦说明基于肿瘤组织外 部形态的诊断结果并不十分可靠，具有相似外部形态结构的肿瘤可能分属差别很 大的不同的类型。微阵列技术具有高通量、自动化、平行化、微量化和低成本的 特点。它的出现使得人们可获得全面的肿瘤基因表达数据集，通过对这些数据在 基因层面进行分析从而获得可靠的诊断结果，这也使得分析的灵敏度和准确性大 大地提高了。 基因芯片是功能基因组、肿瘤、药物基因学研究中的重要监测手段。基因表 达水平是衡量基因功能发挥作用的重要指标，通过基因表达水平的高低，可以揭 示生物体的状态和基因在生物体内的活性例如，利用基因芯片可以检测疾病样 本的基因表达，并进行疾病的识别和分类。肿瘤基因表达谱是指利用dna 芯片所 测定的肿瘤或正常组织样本中基因的表达水平值。它的出现，为肿瘤学的研究提 供了一种全新、系统的研究手段,并在肿瘤学的基础研究和临床应用等领域备受关 注。如何对肿瘤基因表达谱进行有效分析,挖掘和发现其中蕴含的信息和知识,是 当前生物信息学研究的重点课题。然而由于样本的来源和实验经费的限制，使得 基因表达数据具有一个独特的特点维数灾难，即样本数目少(通常是数十个)， 而基因数目多(通常是数千到几万个)。由于大部分基因与具体的生理状态、实验 条件无关，因此我们从众多基因中寻找特征基因模式识别中的特征选择，就 显得尤其重要。然而样本少和超高维的特点使得基因选择成为了一个十分困难的 问题，也引起了人们极大的关注，并使得特征基因选择成为了目前基因芯片数据 电子科技大学硕士学位论文 6 处理和分析的热点研究问题5。 1.4 主要内容与创新点 本文的研究内容是：在生物信息学和数据挖掘的研究背景下，针对基因表达 谱数据，利用模式识别，数据挖掘以及统计学等方法从肿瘤基因芯片中提取重要 的基因，以比较肿瘤组织与正常组织之间的基因表达差异, 从中发掘出在肿瘤组 织中特异表达的基因和药物治疗的靶序列, 找出影响样本类别的特征基因, 准确 识别肿瘤类型, 并结合临床医学从生物学意义上对所选择的特征基因进行分析研 究，以对肿瘤的诊断和治疗提供参考和借鉴。 具体来说，本文的工作是研究正常组织与病理组织基因表达之间的差异。正 常组织在病变的过程中，往往伴随着基因表达模式的变化。基因芯片在医学诊断 中最直接的应用就是检测与疾病相关的基因。这样，不仅可以提高疾病诊断的科 学性，而且对于治疗疾病也有着指导意义，我们可以根据与疾病相关基因的检测 结果，制订有针对性的治疗方案。基因表达水平的升高或降低，可能是病变的原 因，也可能是病变的结果。若基因表达的变化是病变的原因，则以此基因为靶点 的药物就可能逆转病变；若基因表达的变化是病变的结果，则以此基因为靶点的 药物就可能减轻病变的症状。并且可以在病理组织与正常组织之间一次比较成千 上万基因的表达变化，找到一些与疾病相关的特征基因。 本文的创新点主要在于算法的改进以及对所提取的重要的特征基因从生物学 意义进行分析，为临床上的研究和治疗提供参考和借鉴的作用。 1. kmeans_iic 算法。 此算法的创新性：(1)对原有计算基因信噪比方法的不足进行了改进，而提出 用分类信息指数来计算每个基因的信噪比。(2)以支持向量机(svm)为分类工具进 行样本类型的判别，以其在训练集和测试集上的总的错误分类率为依据进行特征 基因的选择，而不是直接把 svm 在训练集上的正确率作为特征基因选取的依据。 （3） 新方法能较好地完成肿瘤特征基因的选取,能在庞大的基因表达数据集中提取 出有用信息。 学术价值：将此方法运用到结肠癌肿瘤基因表达数据中，其挑选出的特征基 因中包含了一些已被实验证实的与癌症分类相关的重要基因，这些基因在癌症基 因调控网络中起关键作用。 2relief_aga_svm算法。 第一章 绪论 7 创新性在于：此算法在进行自适应遗传算法之前，先对数据使用 relief 算法， 目的是借助于 relief 算法对每个基因进行加权，赋予每个基因先验信息，即赋予 每个基因信息含量。 学术价值：将此方法运用到白血病基因表达数据中，其挑选出的特征基因中 包含了一些已被实验证实的与癌症分类相关的重要基因，这些基因在癌症基因调 控网络中起关键作用，比如，基因 cybb,il8。从而对白血病的诊断和治疗起到了 一定的参考和借鉴作用。 1.5 论文结构与安排 本文的结构安排如下： 第一章是绪论部分，介绍了课题的研究背景与意义，并引出了本文所要研究 的问题：肿瘤特征基因的提取。 第二章介绍了相关算法的理论基础，包括数据挖掘部分、特征选择部分、支持 向量机(svm)部分和遗传算法(ga)部分。在数据挖掘部分主要阐述了数据挖掘的 定义以及它的功能；在特征选择部分介绍了类别可分离性判据和特征选择的一些算 法；在支持向量机部分描述了支持向量机的推导以及将支持向量机用于基因表达数 据所解决的问题；在遗传算法部分介绍了遗传算法的机理和实现步骤。 第三章介绍了基于 kmeans_iic 算法。对于经典的结肠癌数据进行试验，并对 其结果从分类正确率和生物学意义进行详细的分析和阐述。再将此方法运用于其 它基因表达谱数据进行试验，结果表明此方法具有一定的推广性。 第四章介绍了基于 relief_aga_svm 算法。 对于经典的白血病数据进行试验， 并对其结果从分类正确率和生物学意义进行详细的分析和阐述。 第五章对本文的工作进行了总结和展望。 最后为致谢、参考文献和论文成果。 电子科技大学硕士学位论文 8 第二章 相关算法的理论基础 2.1 数据挖掘 2.1.1 数据挖掘的定义 数据挖掘19-20 (data mining)就是从大量的数据中挖掘出有用的信息，即从大 量的、不完全的、有噪声的、模糊的、随机的实际应用数据中发现隐含的、规律 性的、人们事先未知的，但有时潜在有用的并且最终可理解的信息和知识的非平 凡过程。事先未知的信息是指该信息是预先未曾预料到的，或称新颖性。新颖性 要求发现的模式应该是从前未知的，该信息是预先未曾预料到的。数据挖掘就是 要发现那些不能靠直觉发现的信息或知识，甚至是违背直觉的信息或知识。挖掘 出的信息越是出乎意料，就可能越有价值。潜在有用性是指发现的知识将来有实 际效用，即这些信息或知识对于所讨论的业务或研究领域是有效的、有实用价值 和能被理解。最终可理解性要求发现的模式能被用户理解，目前它主要体现在简 洁性上。非平凡通常是指数据挖掘过程不是线性的，在挖掘过程中有反复，有循 环，所挖掘的知识往往不易通过简单的分析就能够得到，这些知识可能隐含在表 面现象的内部，需要经过大量数据的比较分析，应用一些专门处理大数据量的数 据挖掘工具。 数据挖掘是一个利用各种分析工具在海量数据中发现模型和数据间关系的过 程，使用这些模型和关系可以进行预测，它帮助决策者寻找数据间潜在的关联， 发现被忽略的因素，因而被认为是解决当今时代所面临的数据爆炸而信息贫乏问 题 的 一 种 有 效 方 法 。 数 据 挖 掘 通 常 也 称 kdd(knowledge discovery in database)数据库中的知识发现。精确地说，在 kdd 中进行知识学习的阶段称 为数据挖掘，数据挖掘是 kdd 中一个非常重要的处理步骤。 数据挖掘是一门交叉学科，它融合了数据库(database)、人工智能(artificial intelligence)、机器学习(machine learning)、统计学(statistics)、知识工程 (knowledge engineering)、面向对象方法(object-oriented method)、信息检索 (information retrieval)、 高性能计算(high-performance computing)以及数据可视化 (data visualization)等多个领域的理论和技术。数据库、人工智能和数理统计是数 据挖掘研究的三根强大的技术支柱。 第二章 相关算法的理论基础 9 2.1.2 数据挖掘的功能 通过预测未来趋势及行为，作为前瞻的，基于知识的决策。数据挖掘的目标 是从数据中发现隐含的，有意义的知识。具体功能有以下 7 个方面： （1）概念描述 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。具 体的描述分为特征性描述和区别性描述。 特征性描述。特征性描述用于描述某类对象的共同特征。 区别性描述。区别性描述用于描述不同类对象之间的区别。 描述数据允许数据在多个抽象层进行概化，便于用户考察数据的一般行为。 （2）关联分析 数据关联分析是数据中存在的一类重要的可被发现的知识，若两个或多个变 量间存在着某种规律性，就成为关联。关联分析的目的就是找出数据中隐藏的关 联网。关联分析发现关联规则，这些规则展示属性值频繁地在给定数据集中一起 发现的条件。 它是用来发现描述数据中强关联特征的模式。所发现的模式通常用蕴涵规则 或特征子集的形式表示。关联分析的应用包括找出具有相关功能的基因组、识别 一起访问的网页、理解地球气候系统不同因素之间的联系等。 （3）分类与预测 分类。所谓分类，就是依照所分析对象的属性分门别类，加以定义，建立 类组。分类的关键是确定对书卷找什么标准或什么规则进行分类。因此，分类时 首先根据属性特征，为每一种类别找到一个合理的描述或模型，即确定分类规则； 再根据规则对数据进行分类。 预测。所谓预测，就是利用历史数据建立模型，再运用最新数据作为输入 值，获得未来变化的趋势或者评估给定样本可能具有的属性值或值的范围。预测 建模可以用来确定顾客对产品促销活动的反应，预测地球生态系统的扰动，或根 据检查结果判断病人是否患有某种特定的疾病。 （4）聚类分析 聚类分析又称为无监督学习，其目的在于客观的按被处理对象的特征分类， 将有相同特征的对象归为一类。聚类可用来对相关的顾客分组、找出显著影响地 球气候的海洋区域以及压缩数据等。 聚类与分类的区别是：分类规则需要预先定义类别和训练样本；而聚类分析 直接面向源数据，没有预先定义好的类别和训练样本存在，所有记录都根据彼此 电子科技大学硕士学位论文 10 相识的程度来加以归类。聚类分析将数据按本身的相似性聚在一起，然后对聚集 状况进行分析解释。 （5）趋势分析 趋势分析又称为时间序列分析，它是从相当长的时间的发展中发现规律和趋 势。趋势分析是时序数据挖掘最基本的内容。趋势分析和关联分析相似，其目的 也是为了挖掘出数据之间的联系，但趋势分析的侧重点在于分析数据间的前后因 果关系。 （6）孤立点分析 孤立点是指数据库中包含的一些与数据的一般行为或模型不一致的数据。大 部分的数据挖掘方法将孤立点视为噪声或异常丢弃，而对某些应用，如欺骗检测， 孤立点数据可能更有价值。 （7）偏差分析 偏差分析又称为比较分析，它是对差异和极端特例的描述，用于解释事物偏 离常规的异常现象，如标准类外的特例，数据聚类外的离群值等。偏差检测的基 本方法：寻找观测结果与参照值之间有意义的差别。偏差包括很多潜在的知识， 如分类中的反常实例、不满足规则的特例、观测结果与模型预测值的偏差量值随 时间的变化等。寻找出偏差的数据并分析对其进行分析是很有意义的。 2.2 特征选择方法综述 2.2.1 特征选择的基本概念 特征选择21是模式识别中的一个关键问题。由于在很多实际问题中常常不容 易找到那些最重要的特征，或受条件限制而不能对它们进行测量，这就使特征选 择和提取的任务复杂化而成为构造模式识别系统最困难的任务之一。 特征选择就是在特征形成过程中得到的原始特征可能很多，如果把所有的原 始特征都作为分类特征送往分类器，不仅使得分类器复杂，分类计算判别量大， 而且分类错误概率也不一定小。因此需要减少特征数目。从一组特征中挑选出一 些最有效的特征以达到降低空间维数的目的。 特征选择的任务是从一组数量为 d 的特征中选择出数量为 d(dd)的一组最优 特征。由于各个特征之间存在复杂的相互关系，在大多数情况下，如果仅对每个 单独的特征按照一定的统计或者可分性判据来进行排队，而后取排在前面的 d 个 特征，这种方法所取得的结果在大多数情况下并非最优特征组，甚至在仿真状况 第二章 相关算法的理论基础 11 下还有可能取到最差的特征组。 从 d 个特征中选择出 d 个最优的特征，在这两个参数都已知的状况下，所有 可能的组合数为 )!/(!ddddcq d d 如果 d=100，d=10,则 q 的数量级是 1013，若 d=20，d=10,则 q=184756。如 果把各种可能的特征组合都算出来再用各项指标参数加以比较，这样的计算量就 非常之大了。 而且在实际问题的研究过程当中， d 的维数往往远远高于 100， 例如， 在利用基因芯片来进行药物设计和癌症诊断时，其产生的有效特征的维数往往在 10000 左右。而实际需要选取的优化特征组的特征数量 d 是未知的。因而，寻找可 行的特征选择算法已逐渐成为国际上研究的热点所在，它也是数据挖掘的主要理 论课题之一。 2.2.2 典型特征选择算法 特征选取一般通过两种途径实现：在建立分类器之前，可以将特征选取加以 明确；或者作为分类器建立过程的后续部分，使之更为精确，例如，使用校正后 的距离函数。在机器学习中，又把这两种方法称为过滤方法（filter method）和缠 绕方法（wrapper method）22。 1过滤方法 最简单的基因扫描过滤过程是 one-gene-at-a-time 方法，其中，基因根据单变 量检测统计量的值，如 t 统计量或 f 统计量、信噪比统计量、非参数 wilcoxon 统 计量以及 p 值等进行排序。对于特征选择，可能的分析参数包括基因的数量 g 或 者 p 值的截断值。更精确的特征选取方法考虑基因表达测量值的联合分布。近期， 有研究者研究了扫描用于分类的基因对（gene pairs）的子集的选取过程可能具有 的优势。结果显示比单变量方法拥有较少变量的双变量方法能得到较好的结果。 其它的方法包括根据变量在随机森林（random forest）中定义的重要性来对变量排 序。由于同时考虑了所有的特征，因此允许检测那些具有较弱主效应、较强交互 作用的基因。这里，随机森林是指决策树分类器的联合，其中每棵树依赖于随机 向量的值，该随机向量独立抽样且与森林中所有树是具有相同的分布。 2缠绕算法 特征选取还可以通过分类法则本身的调整变得精确。在这种情况下，用于特 征选取的不同方法将被用于不同的分类器中。在决策树 cart 算法中，每一步都 根据混杂的减少对特征进行选取，所用特征的数