本论文依托湖南省杰出青年基金项目“DNA微阵列基因选择及肿瘤检测方法研究”,以基因微阵列数据为主要研究对象,对特征选择及分类算法展开研究。20世纪90年代末,生物芯片技术随着人类基因组的研究应运而生。它是一种融微电子学、生物学、物理学、化学、计算机科学于一体的高度交叉的新技术,具有重大的研究价值。DNA微阵列(DNA Microarray),又称基因芯片,是基于核酸探针互补杂交技术原理开发的。由于基因芯片能够检测细胞基因表达水平,并且具有高速度、高通量、集约化的特点,所以可以一次性对大量序列进行检测和基因分析,从而得到高维的DNA微阵列基因表达数据。DNA微阵列数据为通过数据挖掘在基因水平进行疾病诊断、基因治疗等提供了前提和可能性。在当前的肿瘤分类诊断中,肿瘤的诊断高度依赖于病理学工作者对肿瘤组织的主观判断,缺乏准确的诊断依据。众所周知,肿瘤的产生是由于病变组织的相关的基因发生了基因突变,而突变基因的表达水平与正常基因的表达水平是不一样的。因此即使疑似病变组织没有显著变化(即缺乏常规的病理学外观特征),利用基因表达谱也可以对之做出早期诊断,从而可以提高肿瘤诊断的精度。另外,利用基因芯片,还可以根据基因表达谱的变化来区分形态上相似的肿瘤,这样有助于精确识别肿瘤类型,并根据相应的病变基因对不同类型的肿瘤开发不同的药物(如基因靶向药物),有助于提出准确的治疗手段,从而增大治愈肿瘤的机会。但是由于DNA微阵列是某组织或细胞中所有基因的表达数据,维数通常达到几千或上万维,而在实际临床治疗中病例样本一般较少,对于一些比较罕见的疾病,样本数更少,从而导致基因微阵列数据维数远高于样本数目。这是模式识别领域中典型的高维小样本问题(Small Sample Size, SSS)。高维小样本数据的学习和分类一直是模式识别中难点问题。主要原因在于:(1)超高维数容易导致维数灾难(Curse of Dimensionality),从而导致学习性能严重下降;(2)DNA微阵列数据一般样本数极少,使得传统的基于概率的学习方法(如贝叶斯学习理论)失去效能,无法进行有效的分类识别;(3)在高维数据中,大多数特征是噪声特征,容易掩盖数据本身的结构(如类间差别信息等),从而造成分类学习性能严重下降。因此在基因微阵列数据分析中,(1)采用适合小样本高维数据的学习算法并提高其学习和分类的性能;(2)对高维数据进行特征选择以降低其数据维数或者准确确定相关致病基因是基因微阵列数据分析的两个核心任务。无论是肿瘤检测还是基因选择,分类都是最核心的问题。近年来,研究人员提出了多种分类学习算法,如k-NN, C4.5,多层感知器,KFDA(Kernel FisherDiscriminant Analysis)等。90年代中期,Vapnik等人提出了基于统计学习理论的支持向量机(SVM)算法。SVM通过最大化不同类数据之间的间隔(Margin)确定最优分类超平面,实现了结构风险最小化原则,有效克服了过学习(Overfitting)问题,具有良好的泛化性能。同时,由于SVM的分类超平面通过最大化间隔得到,因而消除了对数据正态分布的要求,因而特别适合DNA微阵列等小样本高维数据的学习和分类。SVM的另外一大优势是通过采用核函数(Kernel Function),将线性不可分数据隐式映射到高维线性特征空间中,然后利用线性分类技术进行分类,很好地解决了非线性数据的分类问题。基于这些优点,SVM在基因表达数据分类问题上得到了广泛的应用。尽管支持向量机在小样本问题上表现出了良好的性能,但是如何有效确定支持向量机的模型是一个挑战性问题。支持向量机是核方法(Kernel Method)的典型算法,然而对于同一数据,核函数以及核函数参数的选择,对支持向量机的分类性能有很大影响,因而需要对SVM参数进行调整,以选择最优的SVM参数。参数选择又称为模型选择(Model Selection),是模式识别研究的重要内容。由于支持向量机的模型选择本质上是一个非凸(Non-convexity)的多模(Multimodal)问题,一般存在多个局部极值,因而难以确定全局最优模型。传统的网格法(Grid Search)利用交叉验证(Cross Validation)在整个参数空间进行网格搜索,该方法简单,能够确定一个较好的模型,但是对于较多参数的模型选择问题,计算代价较高。梯度搜索法(Gradient Search)通过最小化SVM泛化性能界获得最优的SVM模型,该方法具有计算代价小,适合多参数优化的场合。但是鉴于模型选择的非凸性,以及梯度算法对初值的敏感性,基于梯度算法的模型选择容易陷入局部极值问题。更为严重的是,如果初始参数点没有得到正确的设置,可能根本无法得到一个合适的模型。针对多模优化问题,运用进化算法(Evolutionary Algorithms)求解是一个有效的解决途径,然而进化算法一般都具有早熟和收敛速度慢的缺点,而且通常只能收敛到一个局部最优点,因而无法有效解决SVM的模型优化问题。针对多模优化中存在的这些问题,本文首先提出了一种混合PSO-BFGS(Broyden-Fletcher-Goldfarb-Shanno)的进化策略,能够有效改善传统进化算法的瓶颈问题。作为一种典型的进化算法,粒子群优化算法( Particle Swarm Optimization,PSO)最近得到了大量的研究,并在模式识别、电力、博弈论等领域得到了广泛的应用。通过模拟鸟类觅食行为,PSO算法具有良好的全局搜索能力和一定的收敛速率。但是在PSO中,粒子只是通过简单的规则进行随机搜索,没有考虑到目标函数的梯度信息,因此收敛速度较数值优化算法要慢得多,并且容易陷入早熟问题。PSO-BFGS结合了PSO算法的全局优化能力以及BFGS算法的局部快速收敛能力,能够克服传统PSO算法早熟、局部收敛速度慢以及只能收敛到一个极值的缺点。为了更好的结合两者的优点,在本文算法中,通过引入领域(Territory)概念以及竞争排抑(Repulsion)机制,充分利用了粒子的全局搜索能力,并利用局部多样性指数(Local Diversity Index)动态启动粒子的局部搜索过程,加快算法的局部收敛速度。通过在多个标准测试函数的实验表明,本文所提出的算法能够大幅提高PSO算法的性能,加快了PSO算法的收敛速度,改善了传统进化算法的早熟问题,并且能够发现多个局部值点,非常适合于求解SVM的模型选择问题。基于混合PSO-BFGS的上述优点,我们利用该算法对SVM模型进行优化。在SVM模型选择中,通常需要优化一个描述模型泛化性能的函数。泛化性能函数对模型选择有着很大的影响,由于留一法(Leave-one-out)错误率能够对泛化性能进行无偏估计,一般采用留一法泛化性能界对模型泛化性能进行估计。在已有的各种泛化性能界中,半径-间隔界(Radius-margin Bound)具有较好的性能,因此在本文中我们采用半径-间隔界描述模型的泛化性能。在多个标准数据集上的实验表明,通过最小化SVM留一法泛化性能界,本文所提出的算法能够得到比基于单一梯度法或者PSO算法更为稳定SVM模型。特征选择是一种有效的数据降维技术,在微阵列数据分析中,又称为基因选择。与特征提取方法(如PCA)不同,特征选择将数据投影到输入空间的少数坐标轴上,而不是投影到某个变换子空间中,本质上属于一个组合优化问题。在本文中,考虑同时进行基因选择与模型优化,我们提出了基于遗传算法的基因选择与SVM模型优化算法。在该方法中,首先利用Wilcoxon-test对微阵列数据进行预选择,以去除大量的无关基因,从而得到一个维数减少的基因子集。然后按照留一法将新得到的基因子集分为训练集和测试集,即依次将子集中的一个数据作为测试集,余下数据作为训练集。在训练集上,运用留一法错误率来检测单个基因的分类能力,并据此对基因进行精选,即分类能力高的基因优先选择,并将其加入到最终的基因子集中。最后,在新的基因子集上,运用遗传算法来选择最优的SVM参数,以构造最优的SVM分类模型。在两个标准数据集上的实验表明,运用该算法,在保证其留一法分类效率为100%的条件下,可以将白血病的相关致病基因降低到2个,而乳腺癌的相关致病基因则可以降低到3个,并且算法是鲁棒的。该算法的缺点是只能选择线性特征,并且计算量较大。只能选择线性特征是目前大多数特征选择算法的缺点,此外,多类数据的特征选择也是目前特征选择算法的难点之一。针对上述两个问题,本文提出了基于流形学习的特征评价分数,有效解决了上述两个问题。流形学习是本世纪初发展起来的新型学习算法,主要应用特征提取,其核心思想是将数据从高维空间投影到低维子空间时,保持数据的局部领域结构不变。流形学习可以涵盖非监督学习,监督学习以及半监督学习,因而本文所提出的特征评价分数能够扩展到监督、非监督以及半监督的特征选择问题。本文第五章首先证明了最近新提出的特征评价分数(Feature Score)是一种图嵌入准则(Graph Embedding Criterion)的特殊应用。然后,针对监督问题,我们提出了基于Marginal Fisher Analysis的特征评价分数,能够很好地完成非线性特征及多类特征选择任务。在人工数据和标准数据集上的实验表明,本文所提出的算法能够高效地完成最优特征子集的确定。