君，已阅读到文档的结尾了呢~~
非线性主成分分析方法及其在医学中的应用,非线性分析,非线性回归分析,spss非线性回归分析,一元非线性回归分析,非线性时间序列分析,非线性泛函分析,多元非线性回归分析,ansys非线性分析,应用非线性动力学,应用非线性控制
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
非线性主成分分析方法及其在医学中的应用
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
人脸识别中基于子空间的特征提取方法探究.pdf 44页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
需要金币：300 &&
人脸识别中基于子空间的特征提取方法探究
你可能关注的文档：
··········
··········
--------------------------Page1------------------------------重庆大学硕士学位论文人脸识别中基于子空间的特征提取方法研究姓名：华桃桃申请学位级别：硕士专业：应用数学指导教师：龚劬--------------------------Page2------------------------------重庆人学硕士学位论文中文摘要摘要人脸识别作为近年来生物特征识别技术领域的热门研究课题，具有非常重要的研究意义和实用价值。一个完善的人脸识别系统包括四个主要环节：人脸检测、预处理、特征提取、分类识别。其中，能否提取有效的鉴别特征是人脸识别能够准确识别的一个关键因素，影响了整个人脸识别系统的性能。在众多的特征提取方法中，基于子空间的特征提取方法具有计算代价小、描述能力强、可分性好等优点，得到大量的研究与应用。本文对基于子空间思想的主成分分析方法和局部保持投影算法进行了详细的分析、研究和实现，针对实验中遇到的问题，对算法进行了一定的改进，在一定程度上提高算法的性能。论文的主要工作和贡献体现在以下几个方面：①本文实验采用的人脸图像来自于现存的人脸数据库，人脸检测过程可以省略。预处理环节主要对人脸数据库的图像进行剪裁，去掉多余的部分，保留图像的本质区别。在实验前就将图像像素维数降低，减少了计算复杂度，并且去掉了图像的干扰因素。②在人脸识别过程中针对人脸图像的采用形式不同，形成了将图像矩阵转化成向量表示的一维算法和直接用图像矩阵进行运算的二维算法。在第二章中对一维主成分分析方法和二维主成分分析方法进行分析说明，通过实验验证一维算法与二维算法的优劣点。一维算法中是将二维人脸矩阵转化为一维向量进行运算，忽略了图像的内部结构特征，从而降低识别率。直接应用二维人脸矩阵计算，保留了图像的内部结构特征，但是二维矩阵的计算复杂度较高。③局部保持投影算法是基于流形学习的典型方法。在人脸识别过程中会遭遇奇异值问题，影响识别效果。在第三章中提出一种利用奇异值分解的方法。在模型中，先将样本数据投影到一个非奇异正交矩阵中，解决了奇异值问题，然后再根据局部保持投影算法求出新样本空间的低维投影子空间。将训练样本和测试样本分别投影到低维子空间中，再利用最近邻分类器进行分类识别。在实验中验证该算法的有效性和鲁棒性。④将基于列的二维局部保持投影算法应用于人脸识别，即将人脸图像矩阵中的每一列作为样本点，构造包括所有样本点的最近邻图，目的在保留图像空间内部的局部流形信息，能够较好反应出图像内部结构的关系，提高识别精度。在计算中，为了有效降低计算复杂度和邻接矩阵的维数，提高识别率，先对图像进行缩小处理，减少图像矩阵维数。--------------------------Page3------------------------------重庆人学硕士学位论文中文摘要的特征提取算法并借助最近邻分类方法构建了一个完整的人脸识别程序。通过实验效果对比，验证算法的有效性和稳定性。关键词：特征提取；流形学习；子空间；人脸识别；--------------------------Page4------------------------------ABSTRACTFaceisahotrecognltionresearchfieldinbiometricsidentificationandtechnologMhasaveryresearchimportantandsignificancevalue．practicalAfacecompIeterecognltlonconsistsofsystemfourmainparts：faceieatureextractionandofseparationclasses．Among，ExtractingelyectivelVdiscriminatedfeaturesisacriticalfactorforfaceanda虢ctstherecognitionpemmlanceofthewholefacerecognitionallthesystem．And锄ongfeatureproposedextrac‘10nmethodsmemods，subspacehavealotofgotresearchand叩plicationow诹totnelrsuchappealingproperties，aslowwelltime—cons啪ing，perfo珊anceonanddescriptlonthisseparation·Inselectpaper,wetheprincipala11dcomponentanalysisthelocalectionpreservingprojbasedonalg
正在加载中，请稍后...您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
高维复杂数据的有监督特征提取方法.pdf49页
本文档一共被下载：
次 ,您可免费全文在线阅读后下载本文档
文档加载中...广告还剩秒
需要金币：120 &&
你可能关注的文档：
··········
··········
中国农业大学
硕士学位论文
高维复杂数据的有监督特征提取方法
姓名：胡晓琴
申请学位级别：硕士
专业：应用数学
指导教师：经玲
当前数据维效的大幅增长给数据处理带来了前所未有的挑战，如何从这些高维复杂的数据中
发现事物的本质规律成为了迫切需要解决的问题．作为处理高维数据中非常重要的前处理步骤一
效据降维一也就越来越受到人们重视．对高维复杂数据降维方法的研究，是一个非常有挑战性
的问题，有着重要的理论价值，并在模式识别，生物信息学、数字图像处理等领域有着广瑟的应
用．本文研究以数据的分类、可视化为目标的高维复杂数据降维的理论与方法，提出如下针对不
同情形的降维算法t
在基于可分性准则的前提下。针对且前缺乏有效降维算法的高维小样本数据集，提出了一种新
multidimensional
的有监督的特征提取算法一判别多维尺度映射 discriminate mapping，DMM ．
它是在结合了经典的多维尺度变换 classicedMDS 和线性判别分析 LDA 优点的基础上提出来
的．DMM算法能有效地处理维数远大于样本数的数据集，并且还有着很多良好的性质；计算量
小，无任何参数的设置，具有解析解．文中给出了算法的理论支持，并通过大量的数值实验验证了
算法的有效性．
当DMM算法应甩于大样本数据集时，会出现计算量过大的问题．本文引入landmark思想，
提出了适合高维大样本数据集的改进的DMM算法一landmark判别多维尺度映射 LDM
正在加载中，请稍后...高维数据的特征选择与特征提取研究
西安电子科技大学博士研究生学位论文高维数据的特征选择与特征提取研究作者：蒋胜利 导师：张军英教授学科：计算机科学与技术中国 西安 ２ ０１ １年０４月―１●ＲｅｓｅａｒｃｈｏｎＦｅａｔｕｒｅ Ｓｅｌｅｃｔｉｏｎ ａｎｄ Ｆｅａｔｕｒｅ Ｅｘｔｒａｃｔｉｏｎ ｆｏｒＨｉｇｈ―Ｄｉｍｅｎｓｉｏｎａｌ ＤａｔａＡ Ｄｉｓｓｅｒｔａｔｉｏｎ Ｓｕｂｍｉｔｔｅｄ ｔｏＸｉｄｉａｎ Ｕｎｉｖｅｒｓｉｔｙｉｎ Ｃａｎｄｉｄａｃｙ ｆｏｒ ｔｈｅ Ｄｅｇｒｅｅ ｏｆ Ｄｏｃｔｏｒ ｏｆ ＰｈｉｌｏｓｏｐｈｙｌｎＣ ｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙｂｙ Ｊｉａｎｇ ＳｈｅｎｇｌｉＸｉ’ａｎ，Ｐ．Ｒ．Ｃｈｉｎａ Ａｐｒｉｌ ２０１１
本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了本文中特别加以标注和致谢中所罗列的内容外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同＿Ｔ－作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。本人签名：日期：沙ｔ ｆ．乡．≥关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：学校 有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或 部分内容；可以允许采用影印、缩印或其它复制手段保存论文。（保密的论文在解 密后遵守此规定）本人签名：删越至日期：２。ｌ１．石．多导师签名：日期：加小∥．岁
摘要摘要随着科技的发展，模式识别或模式分类在越来越多的社会生活中得到了应用。 模式识别领域中，存在大量针对高维数据的识别问题，如生物信息数据识别、人 脸识别、数字手写体识别等。高维数据的出现为模式识别提出了新的挑战，其不 仅难以被人们直观理解，而且为模式识别中的特征选择与特征提取环节带来了新 的“维数灾难”。如何从高维数据中选择或提取对识别或分类有效的特征已成为当 前的研究热点和难点。本文对模式识别中高维数据的特征选择与特征提取算法进 行了研究，主要工作包括以下几个方面：．１．提出了一种多重遗传算法，用于疾病相关的单核苷酸多态性的选择。运用 统计机器学习方法研究大规模单核苷酸多态性与复杂疾病的关联关系，首要的工 作是把大规模单核苷酸多态性缩减为较小集合，从中提取出包含冗余信息较少的 特征单核苷酸多态性。为此，提出了用互信息衡量单核苷酸多态性与疾病问关联 的紧密程度并将其作为遗传算法的适应值，通过多次运用遗传算法并合并相应的 寻优结果得到候选的特征单核苷酸多态性集合。在单核苷酸多态性仿真数据上的 实验及与最大熵方法性能比较表明，该方法最大可能丢弃了与疾病无关的单核苷 酸多态性，保留了与疾病相关的单核苷酸多态性，为进一步研究提供了合适规模 的单核苷酸多态性，本方法可用于中等或较大规模的单核苷酸多态性数据。 ２．提出了二次投影识别蛋白质谱数据的新方法。作为一种蛋白质组学工具， 质谱法的使用对疾病的早期诊断和治疗带来了革命性的变化。然而，由于蛋白质 谱数据高达上万维，现有的机器学习方法不能直接用于识别蛋白质谱数据，同时 也面临着识别性能较低的问题。借鉴具有良好降维性能的主成分分析与局部线性 判别嵌入两种方法，提出了用于蛋白质谱数据识别的二次投影法。该方法对高维 数据先进行去噪与Ｔ检验降维，再用主成分分析获取第一次投影的低维特征向量， 随后用局部线性判别嵌入获取可分性最好的第二次投影特征向量。此外，还对局 部线性判别嵌入方法进行修改，得到一种改进的二次投影法。二种方法在卵巢癌 蛋白质谱数据上的实验表明识别性能较好。 ３．为了发现高维样本的非线性流形结构，对人脸识别与数字手写体识别问题， 提出了基于流形学习的新的特征提取算法。 （１）结合现有数据局部几何结构保持方法，并使类内散度最小和类间散度最 大，达到提取最优分类特征信息的目的，提出了两种集成最大边界准则的人脸图 像特征提取算法，分别是保局判别分析算法与线性局部切空间判别分析算法。实 验表明，提出的算法可以发现数据集中的非线性流形结构并在降维的同时尽可能摘要地保持这些结构信息，还能使数据的分类边界最大化，提取到了最优的分类特征 信息。 （２）最大差异伸展是一种最近提出的流形学习算法，将其用于模式识别领域还 存在不能处理新样本等限制。利用线性变换的思想，在最大差异伸展的基础上，提出了一种新的线性特征提取算法――线性最大差异伸展。该算法利用提取的特征信息把新的测试样本直接线性变换到低维子空间，并能较好地保留局部近邻的 信息。 （３）为了解决局部线性嵌入方法不能处理新样本等局限，把一幅人脸图像或数 字手写体图像直接作为一个二维数据矩阵处理，不再转换为列向量，提出了基于二维图像的特征提取算法――二维局部线性嵌入算法。二维处理的思想通过直接在图像矩阵上运算有效地降低了局部线性嵌入算法的复杂度，同时，在降维中又 保持了原方法把高维流形嵌入到低维空间的优点，而且具有处理新测试样本的能 力。从实验结果来看，局部线性嵌入对近邻个数敏感的特性也有效的得Ｎ－ｒ改善。 本文提出的特征选择或特征提取算法，主要用于模式分类任务，在各自的应 用领域做了相应的仿真实验，与现有相应算法相比，取得了较好的性能。特征选择，特征提取，高维数据，维度约减ＡｂｓｔｒａｃｔＩＩＩＡｂｓｔｒａｃｔＷｉｔｈｔｈｅ ｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ｓｃｉｅｎｃｅ ａｎｄ ｔｅｃｈｎｏｌｏｇｙ，ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ ｈａｓ ｂｅｅｎｌｉｆｅ．Ｉｎ ｔｈｅ ｆｉｅｌｄ ｏｆ ａｐｐｌｉｅｄ ｉｎ ｍｏｒｅ ａｎｄ ｍｏｒｅ ｓｏｃｉａｌ ｏｆ ｐｒｏｂｌｅｍｓ，ｓｕｃｈ ｄｉｇｉｔａｌａｓｐａｔｔｅｒｎｒｅｃｏｇｎｉｔｉｏｎ，ａ ｌａｒｇｅ ｎｕｍｂｅｒｔｈｅｒｅｃｏｇｎｉｔｉｏｎｏｆ ｂｉｏｌｏｇｉｃａｌ ｉｎｆｏｒｍａｔｉｏｎ ｄａｔａ，ｆａｃｅｒｅｃｏｇｎｉｔｉｏｎ，ｈｉｇｈｈａｎｄｗｒｉｔｉｎｇｒｅｃｏｇｎｉｔｉｏｎ，Ｃａｌｌ ｂｅｏｃｃｕｒｒｅｎｃｅｓｕｍｍａｒｉｚｅｄｔｏｔｈｅｒｅｃｏｇｎｉｔｉｏｎ ｏｆｄｉｍｅｎｓｉｏｎａｌｃｈａｌｌｅｎｇｅｓ ｔｏｄａｔａ．Ｔｈｅｏｆｈｉｇｈｄｉｍｅｎｓｉｏｎａｌ ｄａｔａ，ｈｏｗｅｖｅｒ，ｐｒｅｓｅｎｔｓ ｎｅｗｒｅｃｏｇｎｉｔｉｏｎｐｒｏｂｌｅｍ．Ｉｔｉｓ ｎｏｔ ｏｎｌｙｄｉｆｆｉｃｕｌｔｔｏ ｂｅ ｉｎｔｕｉｔｉｖｅｕｎｄｅｒｓｔａｎｄｉｎｇ，ｂｕｔ ａｌｓｏ ｂｒｉｎｇｓ ｔｈｅ“ｃｕｒｓｅ ｏｆ ｄｉｍｅｎｓｉｏｎａｌｉｔｙ＇’ｐｒｏｂｌｅｍ ｔｏ ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ ｅｘｔｒａｃｔｉｏｎ ｉｎ ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ．Ｈｏｗ ｔｏ ｓｅｌｅｃｔｏｒ ｏｒａｎｄ ｆｅａｔｕｒｅｆｅａｔｕｒｅｓ ｆｏｒｅｘｔｒａｃｔｅｆｆｅｃｔｉｖｅｈｉｇｈ．ｄｉｍｅｎｓｉｏｎａｌ ｄａｔａ ｃｌａｓｓｉｆｉｃａｔｉｏｎｒｅｃｏｇｎｉｔｉｏｎｉｓｏｎｅｏｆ ｔｈｅｃｕｒｒｅｎｔｒｅｓｅａｒｃｈ ｆｏｃｕｓｅｓａｎｄ ｃｈａｌｌｅｎｇｅｓ．Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｔｈｅ ａｌｇｏｒｉｔｈｍｓｆｏｒｏｆ ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ ａｎｄ ｆｅａｔｕｒｅ ｅｘｔｒａｃｔｉｏｎａｓｈｉｇｈ．ｄｉｍｅｎｓｉｏｎａｌｄａｔａｒｅｃｏｇｎｉｔｉｏｎａｒｅ ｄｅｖｅｌｏｐｅｄ，ｗｉｔｈ ｔｈｅ ｍａｉｎ ｗｏｒｋｓ ｌｉｓｔｅｄｆｏｌｌｏｗｓ．１．Ｍｕｌｔｉ―ｇｒｏｕｐＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ（ＭＧＡ）ｉｓ ｐｒｏｐｏｓｅｄ ｆｏｒ ｔｈｅ ｐｏｌｙｍｏｒｐｈｉｓｍｓ（ＳＮＰｓ）．Ｆｏｒ ｌａｒｇｅ―ｓｃａｌｅ ｃｏｍｐｌｅｘｄｉｓｅａｓｅ ｕｓｉｎｇ ｓｔａｔｉｓｔｉｃｓｓｅｌｅｃｔｉｏｎｏｆｄｉｓｅａｓｅ．ｒｅｌａｔｅｄ ｓｉｎｇｌｅ ｎｕｃｌｅｏｔｉｄｅ ａｓｓｏｃｉａｔｉｏｎ ｓｔｕｄｉｅｓＳＮＰ ｄａｔａｓｅｔｓ，ｂｅｔｗｅｅｎ ｂｅｅｎＳＮＰｓ ａｎｄａｎｄ ｍａｃｈｉｎｅｌｅａｒｎｉｎｇ ｍｅｔｈｏｄｓ ｈａｖｅｆａｃｉｎｇ ｓｅｒｉｏｕｓｃｕｒｓｅ ｏｆ ｄｉｍｅｎｓｉｏｎａｌｉｔｙｐｒｏｂｌｅｍ．Ｒｅｄｕｃｉｎｇ ａｌａｒｇｅ．ｓｃａｌｅ ＳＮＰｓｅｔ ｔｏ ａｓｍａｌｌｅｒ ｏｎｅ ｗｉｔｈ ｌｅｓｓ ｒｅｄｕｎｄａｎｔ ｉｎｆｏｒｍａｔｉｏｎ ｂｅｔｗｅｅｎ ＳＮＰｓ ｉｎ ｉｔｉｓ ｔｈｅ ｋｅｙ ａｎｄ ｔｈｅ ｐｒｉｍａｒｙｏｂｊｅｃｔｔｏｔｈｅ ｐｒｏｂｌｅｍ．Ｔｏ ａｃｈｉｅｖｅ ｔｈｉｓ，ｍｕｔｕａｌ ｉｎｆｏｒｍａｔｉｏｎ（ＭＩ）ｉｓｅｍｐｌｏｙｅｄｔｏｍｅａｓｕｒｅｔｈｅ ａｓｓｏｃｉａｔｉｏｎ ｒｅｌａｔｉｏｎｓｈｉｐｂｅｔｗｅｅｎａＳＮＰａｎｄｄｉｓｅａｓｅａｎｄ ｆｕｒｔｈｅｒ ｕｓｅｄ ａｓ ｔｈｅ ｆｉｔｎｅｓｓ ｏｆ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ．Ｏｐｔｉｍａｌ ＳＮＰ ｓｕｂｓｅｔｓ ｓｅａｒｃｈｅｄ ｂｙＭＧＡ ｍｅｔｈｏｄａｒｅｔｈｅｎ ｃｏｍｂｉｎｅｄｔｏｆｏｒｍａｎｅｗ ＳＮＰ ｆｅａｔｕｒｅ ｓｅｔ．ＩｎｃａｎｃｏｎｔｒａｓｔｔｏＭａｘｉｍｕｍ Ｅｎｔｒｏｐｙ（ＭＥ）ｍｅｔｈｏｄ，ｔｈｅｐｒｅｓｅｎｔｅｄ ｍｅｔｈｏｄｅｘｃｌｕｄｅａｎｕｍｂｅｒ ｏｆｒｅｄｕｎｄａｎｔ ＳＮＰｓ，ａｎｄ ｒｅｔａｉｎ ｔｈｏｓｅ ｄｉｓｅａｓｅ－ｒｅｌａｔｅｄ ＳＮＰ ｓｉｍｕｌｔａｎｅｏｕｓｌｙ．ＥｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｏｎｓｉｍｕｌａｔｅｄＳＮＰ ｄａｔａｓｅｔｓ ｈａｖｅ ｓｈｏｗｎｔｈａｔ ｔｈｅＭＧＡ ｍｅｔｈｏｄ ｐｒｏｖｉｄｅｄｔｏａｐｐｒｏｐｒｉａｔｅ ｓｉｚｅｓ ｏｆ ＳＮＰ ｓｅｔｓｆｏｒ ｔｈｅ ｆｕｔｕｒｅ ｒｅｓｅａｒｃｈ，ａｎｄ ｃｏｕｌｄ ｂｅ ａｐｐｌｉｅｄｍｅｄｉｕｍ―ｓｃａｌｅｏｒｌａｒｇｅ―ｓｃａｌｅ ＳＮＰ ｄａｔａｓｅｔｓ．２．Ｄｏｕｂｌｅ．Ｔｉｍｅ Ｐｒｏｊｅｃｔｉｏｎｓ（ＤＴＰ）ｍｅｔｈｏｄ ｉｓ ｐｒｏｐｏｓｅｄ ｆｏｒ ｔｈｅ ｐｒｏｔｅｏｍｉｃ ｍａｓｓｒｅｃｏｇｎｉｔｉｏｎｏｆｓｐｅｃｔｒｏｍｅｔｒｙ（ＭＳ）ｄａｔａ．Ａｓａｋｉｎｄｏｆ ｐｒｏｔｅｏｍｉｃｓｔｏｏｌ，ｍａｓｓａｎｄ ｓｐｅｃｔｒｏｍｅｔｒｙ ｈａｓ ｂｒｏｕｇｈｔ ｒｅｖｏｌｕｔｉｏｎａｒｙ ｃｈａｎｇｅ ｆｏｒ ｅａｒｌｙ－ｓｔａｇｅ ｄｉａｇｎｏｓｉｓ ｏｆ ｄｉｓｅａｓｅｓ．Ｈｏｗｅｖｅｒ，ｄｕｅｔｏ ｕｐ ｔｏｔｒｅａｔｍｅｎｔｔｈｏｕｓａｎｄｓ ｏｆ ｄｉｍｅｎｓｉｏｎｓ ｏｆ ＭＳ ｄａｔａ，ｍｏｓｔ ｓｔａｎｄａｒｄ ｂｅ ｄｉｒｅｃｔｌｙｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ｔｅｃｈｎｉｑｕｅｓｃａｎｎｏｔａｐｐｌｉｅｄｔｏ ｉｔ，ｓｉｎｃｅ ｐｏｏｒ ｒｅｃｏｇｎｉｔｉｏｎｌＶＡｂｓｔｒａｃｔｐｅｒｆｏｒｍａｎｃｅ ｗｉｌｌ ｂｅ ｏｂｔａｉｎｅｄ．Ｉｎ ｔｈｅ ｖｉｅｗ ｏｆ ｔｈｅ ｇｏｏｄ ｄｉｍｅｎｓｉｏｎ－ｒｅｄｕｃｔｉｏｎ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｂｏｔｈ ｐｒｉｎｃｉｐａｌ ｃｏｍｐｏｎｅｎｔ ａｎａｌｙｓｉｓ（ＰＣＡ）ａｎｄ ｌｏｃａｌｌｙ ｌｉｎｅａｒ ｄｉｓｃｒｉｍｉｎａｎｔ ｅｍｂｅｄｄｉｎｇ（ＬＬＤＥ），ｗｅ ｄｅｖｅｌｏｐ ｔｈｅＤＴＰ ｍｅｔｈｏｄ ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅｍ．Ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈｏｄ ｆｔｒｓｔｕｓｅｓｄｅ．ｎｏｉｓｅｓ ｔｈｅ ｅｘａｍｉｎｅｄ ｄａｔａ ａｎｄ ｆｉｒｓｔＴ－ｔｅｓｔ ｔｏ ｄｏｄｉｍｅｎｓｉｏｎ ｒｅｄｕｃｔｉｏｎ．Ａｎｄ ｔｈｅｎ ｔｈｅｓｐａｃｅ ｂｙ ＰＣＡ．Ｌａｓｔ，ｐｒｏｊｅｃｔｉｏｎｆｅａｔｕｒｅ ｖｅｃｔｏｒ ｉｓ ｏｂｔａｉｎｅｄ ｉｎ ｔｈｅｖｅｃｔｏｒｌｏｗ―ｄｉｍｅｎｓｉｏｎａｌｔｈｅ ｓｅｃｏｎｄ ｐｒｏｊｅｃｔｉｏｎ ｆｅａｔｕｒｅｗｈｉｃｈ ｍａｘｉｍｉｚｅｓ ｔｈｅ ｓｅｐａｒａｂｉｌｉｔｙ ｂｅｔｗｅｅｎ ｃｌａｓｓｅｓａｉｓ ｆｏｕｎｄ ｂｙ ＬＬＤＥ．Ｉｎ ａｄｄｉｔｉｏｎ，ｗｅ ｉｍｐｒｏｖｅ ｔｈｅ ＬＬＤＥ ｍｅｔｈｏｄ，ａｎｄ ｏｂｔａｉｎ ＤＴＥ Ｅｘｐｅｒｉｍｅｎｔｓｏｎｍｏｄｉｆｉｅｄｔｈｅ ｄａｔａｓｅｔ ｏｆ ｏｖａｒｉａｎ ｃａｎｃｅｌ＂ｐｒｏｔｅｏｍｉｃ ｍａｓｓ ｓｐｅｃｔｒｏｍｅｔｒｙｉｎｄｉｃａｔｅ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈｏｄｓ ａｃｈｉｅｖｅ ｈｉｇｈｅｒ ａｃｃｕｒａｃｉｅｓ ３．Ｆｏｒ ｆａｃｅｔｈａｎｃｕｒｒｅｎｔｍｅｔｈｏｄｓ．ｒｅｃｏｇｎｉｔｉｏｎ ａｎｄ ｄｉｇｉｔａｌ ｈａｎｄｗｒｉｔｉｎｇ ｒｅｃｏｇｎｉｔｉｏｎ，ｔｈｅ ｎｅｗ ｆｅａｔｕｒｅｏｎｅｘｔｒａｃｔｉｏｎ ｍｅｔｈｏｄｓ ｂａｓｅｄｍａｎｉｆｏｌｄ ｌｅａｒｎｉｎｇ ａｒｅ ｐｒｏｐｏｓｅｄ．（１）Ｂａｓｅｄｏｎｔｈｅ ｉｄｅａｓ ｏｆ ｐｒｅｓｅｒｖｉｎｇ ｌｏｃａｌ ｇｅｏｍｅｔｒｙ ｏｆ ｄａｔａ ａｎｄ ｍａｘｉｍｉｚｉｎｇ ｔｈｅｃｌａｓｓｉｆｉｃａｔｉｏｎ ｍａｒｇｉｎ ｏｆ ｄａｔａ，ｔｗｏ ｆｅａｔｕｒｅ ｅｘｔｒａｃｔｉｏｎ ｍｅｔｈｏｄｓ ｗｈｉｃｈ ｉｎｔｅｇｒａｔｅ ｍａｘｉｍｕｍｍａｒｇｉｎｃｒｉｔｅｒｉｏｎａｒｅｐｒｏｐｏｓｅｄ ｆｏｒｆａｃｅｒｅｃｏｇｎｉｔｉｏｎ，ｃａｌｌｅｄｌｏｃａｌｉｔｙｐｒｅｓｅｒｖｉｎｇｄｉｓｃｒｉｍｉｎａｎｔａｎａｌｙｓｉｓ（ＬＰＤＡ）ａｎｄｌｉｎｅａｒ ｌｏｃａｌ ｔａｎｇｅｎｔ ｓｐａｃｅ ｄｉｓｃｒｉｍｉｎａｎｔ ａｎａｌｙｓｉｓｃｏｕｌｄ ｂｅ ｅｍｂｅｄｄｅｄ ｉｎ ｌｏｗ ｄｉｍｅｎｓｉｏｎａｌ（ＬＬＴＳＤＡ），ｒｅｓｐｅｃｔｉｖｅｌｙ．Ａｃｃｏｒｄｉｎｇｌｙ，ｓａｍｐｌｅｓｓｐａｃｅ，ｗｈｉｌｅ ｇｅｏｍｅｔｒｙ ｏｆ ｔｈｅｓａｍｐｌｅｓｓｃａｒｅｒｉｓ ｐｒｅｓｅｒｖｅｄ．Ｔｈｅ ｓｃａｔｔｅｒ ｍａｔｒｉｘ ｉｎ ｂｏｔｈ ｍｅｔｈｏｄｓｅｎｓｕｒｅｓｔｈｅｗｉｔｈｉｎ．ｃｌａｓｓｍｉｎｉｍｉｚａｔｉｏｎａｎｄｔｈｅｂｅｔｗｅｅｎ．ｃｌａｓｓｓｃａｔｔｅｒｍａｘｉｍｉｚａｔｉｏｎ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｃｏｇｎｉｔｉｏｎｒｅｓｕｌｔｓ ｈａｖｅ ｓｈｏｗｎ ｔｈａｔ ｗｈｅｎ ａｐｐｌｙｉｎｇ ｔｈｅ ｍｅｔｈｏｄｓ ｔｏ ｆａｃｅｐｒｏｂｌｅｍ，ｏｐｔｉｍａｌｖａｒｉａｎｃｅｄｉｓｃｒｉｍｉｎａｔｉｖｅ ｆｅａｔｕｒｅｓ ａｒｅ ｅｘｔｒａｃｔｅｄ ａｎｄ ａｌｓｏ ｉｍｐｒｏｖｅｄｐｅｒｆｏｒｍａｎｃｅ ａｒｅｏｂｔａｉｎｅｄ ｃｏｍｐａｒｅｄ ｗｉｔｈ ｏｔｈｅｒ ｍｅｔｈｏｄｓ．（２）Ｍａｘｉｍｕｍｕｎｆｏｌｄｉｎｇ（ＭＶＵ）ｉｓａｎｅｗｌｙ－ａｐｐｅａｒｅｄｗｈｅｎｍａｎｉｆｏｌｄ ｌｅａｒｎｉｎｇ ｆｏｒ ｐａｔｔｅｍａｌｇｏｒｉｔｈｍ．Ｉｔ，ｈｏｗｅｖｅｒ，ｃａｎｎｏｔｈａｎｄｌｅｎｅｗ ｓａｍｐｌｅｓｅｍｐｌｏｙｅｄｒｅｃｏｇｎｉｔｉｏｎ．Ｕｓｉｎｇ ｔｈｅ ｉｄｅａ ｏｆ ｌｉｎｅａｒｔｒａｎｓｆｏｒｍａｔｉｏｎ，ａｎｅｗ ｌｉｎｅａｒ ｆｅａｔｕｒｅ ｅｘｔｒａｃｔｉｏｎｔｏｍｅｔｈｏｄ ｎａｍｅｄ ｔｈｅ ｌｉｎｅａｒ ｍａｘｉｍｕｍ ｖａｒｉａｎｃｅ ｕｎｆｏｌｄｉｎｇ（ＬＭＶＵ）ｉｓ ｐｒｏｐｏｓｅｄ ｔｈｅ ｐｒｏｂｌｅｍ．Ｎｅｗｓｐａｃｅ ｗｉｔｈ ｔｈｅｔｅｓｔｓｏｌｖｅｓａｍｐｌｅｓｃａｎｂｅ ｄｉｒｅｃｔｌｙｔｒａｎｓｆｏｒｍｅｄｉｎｔｏ ｔｈｅ ｌｏｗ ｄｉｍｅｎｓｉｏｎａｌ ｌｏｃａｌ ｎｅｉｇｈｂｏｒｈｏｏｄｌｉｎｅａｒｔｒａｎｓｆｏｒｍａｔｉｏｎｏｐｔｉｍａｌｌｙｐｒｅｓｅｒｖｉｎｇｉｎｆｏｒｍａｔｉｏｎ．（３）Ｌｏｃａｌｌｙ ｌｉｎｅａｒｅｍｂｅｄｄｉｎｇ（ＬＬＥ）ｍｅｔｈｏｄｏｒ ａ ａｓｉｓ ｎｏｔ ａｂｌｅ ｔｏ ｐｒｏｃｅｓｓ ｎｅｗ ｓａｍｐｌｅｓ．Ｔｏｏｖｅｒｃｏｍｅ ｔｈｉｓ ｌｉｍｉｔａｔｉｏｎ，ａ ｆａｃｅ ｉｍａｇｅｔｏ ａｄｉｇｉｔ ｈａｎｄｗｒｉｔｉｎｇｉｍａｇｅ，ｂｅｎｏｔｔｒａｎｓｆｏｒｍｅｄｃｏｌｏｍｕｎ ｖｅｃｔｏｒ，ｉｓ ｄｉｒｅｃｔｌｙ ｐｒｏｃｅｓｓｅｄｔｗｏ―ｄｉｍｅｎｓｉｏｎａｌｄａｔａ ｍａｔｒｉｘ．Ａ ｎｏｖｅｌｔｗｏ－ｄｉｍｅｎｓｉｏｎ ｌｏｃａｌｌｙ ｌｉｎｅａｒｅｍｂｅｄｄｉｎｇ（２ＤＬＬＥ）ａｌｇｏｒｉｔｈｍｉｓ ｐｒｏｐｏｓｅｄ ｆｏｒ ｉｍａｇｅｆｅａｔｕｒｅ ｅｘｔｒａｃｔｉｏｎ．Ｔｈｅ ｎｅｗ ｍｅｔｈｏｄ ｈａｓ ｓｅｖｅｒａｌ ａｄｖａｎｔａｇｅｓ：（ａ）ｌｏｗｅｒ ｃｏｍｐｕｔａｔｉｏｎｃｏｍｐｌｅｘｉｔｙ ｃｏｍｐａｒｅｄ ｗｉｔｈＬＬＥｍｅｔｈｏｄ；（ｂ）ｍａｉｎｔａｉｎｉｎｇ ｔｈｅ ｍａｎｉｆｏｌｄ ｓｔｒｕｃｔｕｒｅｏｆｓａｍｐｌｅｓｉｎ ｌｏｗ―ｄｉｍｅｎｓｉｏｎａｌ ｓｐａｃｅ，ａｓ ｉｓ ｄｏｎｅ ｉｎ ＬＬＥ ｍｅｔｈｏｄ；（ｃ）ｔｈｅ ａｂｉｌｉｔｙ ｏｆ ｄｅａｌｉｎｇＡｂｓｔｒａｃｔＶｗｉｔｈｎｅｗｓａｍｐｌｅｓ；（ｄ）ｅｆｆｉｃｉｅｎｔｌｙ ｉｍｐｒｏｖｉｎｇＬＬＥ ｉｎｔｈｅ ａｓｐｅｃｔ ｏｆ ｓｈｏｗｉｎｇ ｌｅｓｓｓｅｎｓｉｔｉｖｉｔｙ ｔｏ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ ｐｏｉｎｔｓ． Ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍｓ ｏｆ ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ ａｎｄ ｆｅａｔｕｒｅ ｅｘｔｒａｃｔｉｏｎ，ｆｌｅｅ ｍａｉｎｌｙｅｍｐｌｏｙｅｄｔｏ ｔｈｅ ｔａｓｋ ｏｆ ｐａｔｔｅｒｎ ｃｌａｓｓｉｆｉｃａｔｉｏｎ，ａｎｄａｒｅ ｓｉｍｕｌａｔｅｄ ｉｎ ａｐｐｌｉｃａｔｏｎ ｆｉｅｌｄｓ ｂｙａｖａｉｌａｂｌｅｅｘｐｅｒｉｍｅｎｔｓ，ｒｅｓｐｅｃｔｉｖｅｌｙ．Ｃｏｍｐａｒｅｄ ｐｅｒｆｏｒｍａｎｃｅｓ ａｒｅｏｂｔａｉｎｅｄ．ｗｉｔｈｔｈｅａｌｇｏｒｉｔｈｍｓ，ｉｍｐｒｏｖｅｄＫｅｙｗｏｒｄｓ：ｐａｔｔｅｒｎｒｅｃｏｇｎｉｔｉｏｎ，ｆｅａｔｕｒｅｓｅｌｅｃｔｉｏｎ，ｆｅａｔｕｒｅｅｘｔｒａｃｔｉｏｎ，Ｋｇｈ―ｄｉｍｅｎｓｉｏｎａｌ ｄａｔａ，ｄｉｍｅｎｓｉｏｎａｌｉｔｙ ｒｅｄｕｃｔｉｏｎＡｂｓｔｒａｃｔ目录ＶＩＩ目录～ ～ＩＳ ａＪ ＨＩ摘舳目要瓯录ｖ ｎＴ＿＿第一章绪论……． １．１论文的研究背景与意义…………………………………………………．１ １．２高维数据处理概述………………………………………………………．３ １．２．１处理过程………………………：．ｊ………．．：……………………．３ １．２．２处理方法………………………………………………………一４ １．２．３特征选择与特征提取…………………………………………．．６ １．３研究现状与关键问题分析………………………………－………………７ １．３．１研究现状………………………………………………………一７ １．３．２高维数据处理关键问题分析…………………………………．１１ １．４论文主要内容及章节安排………………………………………………１２ １．４．１主要内容………………………………………………………ｌ ２ １．４．２章节安排………………………………………………………１ ３ 第二章典型相关算法分析………………………………………………………………．１５ ２．１遗传算法……………．：…………………………………………………．１ ５ ２．２主成分分析………………………………………………………………１ ７ ２．３线性判别分析……………………………………………………………２０ ２．４局部线性嵌入……………………………………………………………２１ ２．５小结……………………………………………………………………………………………．．２３ 第三章基于多重遗传算法的疾病相关单核苷酸多态性选择……………………．２５ ３．１单核苷酸多态性简介……………………………………………………２５ ３．１．１单核苷酸多态性的概念………………………………………２５ ３．１．２单核苷酸多态性的特性………………………………………２５ ３．２疾病相关单核苷酸多态性选择面临的问题……………………………２６ ３．３单核苷酸多态性与疾病的关联分析……………………………………．２７ ３．３．１关联性测度……………………………………………………２７ ３．３．２关联性的传播特性分析………………………………………２９ ３．４多重遗传算法设计与分析………………………………………………３０ ３．４．１多重遗传算法的设计…………………………………………３ｌＶＩＩＩ目录３．４．２算法的时问复杂度分析………………………………………３３ ３．５实验结果…………………………………………………………………３３ ３．５．１实验数据说明…………………………………………………３３ ３．５．２实验参数设置…………………………………………………．３４ ３．５．３实验结果和算法性能评价……………………………………３４ ３．６小结……………………………………………………………………………………………．．３８ 第四章二次投影识别蛋白质谱数据的新方法…………………………………………３９ ４．１蛋白质谱数据简介………………………………………………………３９ ４．２蛋白质谱数据识别问题分析……………………………………………３９ ４．３数据识别的现有投影方法………………………………………………４ｌ ４．３．１最大边界准则…………………………………………………４１ ４．３．２局部线性判别嵌入……………………………………………４３ ４．４基于二次投影方法的蛋白质谱数据识别………………………………４４ ４．４．１数据预处理……………………………………………………．４４ ４．４．２二次投影方法…………………………………………………．４５ ４．４．３改进的二次投影方法…………………………………………４６ ４．５实验……………………………………………………………………………………………．．４７ ４．５．１实验数据………………………………………………………４７ ４．５．２实验结果与分析………………………………………………４７ ４．６小结……………………………………………………………………………………………．．５２ 第五章基于最大边界准则的特征提取研究…………………………………………。５３ ５．１问题描述…………………………………………………………………５３ ５．２特征提取相关算法简介…………………………………………………５４ ５．２．１保局投影………………………………………………………５４ ５．２．２线性局部切空间排列算法……………………………………５５ ５．３保局判别分析特征提取算法…………………………………：…………５６ ５．３．１保局判别分析算法……………………………………………５６ ５．３．２实验………………………………………………………………………………．．５７ ５．４线性局部切空间判别分析特征提取算法………………………………６１ ５．４．１线性局部切空间判别分析算法………………………………６１ ５．４．２实验……………………………………………………………………………．．６２ ５．５小结……………………………………………………………………………………………．．６５ 第六章基于线性最大差异伸展的特征提取研究………………………………………．６７ ６．１问题描述…………………………………………………………………６７ ６．２最大差异伸展算法………………………………………………………６８７．２．２二维局部线性嵌入算法………………………………………７８ ７．３实验结果与分析…………………………………………………………８ １ ７．３．１流形学习能力实验……………………………………………８１ ７．３．２人脸图像分类实验……………………………………………８２ ７．３．３数字手写体图像分类实验……………………………………８４７．４小结……………………………………………………………………………………………．．８５第八章总结与展望…………………………………………………………………………８７ ８．１总结……………………………………………………………………………………………一８７ ８．２后继工作与展望…………………………………………………………８９ ｊ｝Ｃ谢………………………………………………………………………………………………………………．．９ １ 参考文献…………………………………………………………………………………………９３ 攻读博士学位期间发表的论文和科研工作…………………………………………。１０５
第一章绪论第一章绪论随着科学技术的发展，人们获取的数据维数越来越高，高维数据的特征选择 与特征提取作为模式识别的一项关键环节，从上个世纪中叶起，许多研究人员就 开始这方面的研究，提出了各种理论和方法，积累了大量研究成果。今天，模式 识别广泛应用于生物特征识别、生物信息分类等任务中，展现了广阔的发展前景。１．１论文的研究背景与意义长久以来，人们总是希望揭示隐藏在纷繁复杂表象下的事物与现象的客观 规律，为了能提供观察对象更多方面的、更完整的信息，人们不断的研制新的 观察工具，发展新的观察技术，产生出越来越多的大规模高维数据。例如，人 类基因组计划（ＨｕｍａｎＧｅｎｏｍｅＰｒｏｊｅｃｔ，ＨＧＰ）是由美国科学家于１ ９８５年率先提出，于１９９０年正式启动。美国、英国、法国、德国、日本和我国的科学家共同参与了 这一预算达３０亿美元的人类基因组计划。为此，测出人类基因组ＤＮＡ的３０亿 个碱基对的序列，发现所有人类基因，找出它们在染色体上的位置，破译人类 全部遗传信息。ＨＧＰ的目的是解码生命、了解生命的起源、了解生命体生长发 育的规律、认识种属之间和个体之间存在差异的起因、认识疾病产生的机制以 及长寿与衰老等生命现象、为疾病的诊治提供科学依据‘１?１】【Ｉ．２】【１３】【１４１。单核苷酸 多态性（ＳｉｎｇｌｅＮｕｃｌｅｏｔｉｄｅＰｏｌｙｍｏｒｐｈｉｓｍ，ＳＮＰ），主要是指在基因组水平上由单个核苷酸的变异所引起的ＤＮＡ序列多态性。它是人类可遗传的变异中最常见的 一种，占所有已知多态性的９０％以上。ＳＮＰ在人类基因组中广泛存在，平均每 ５００～１０００个碱基对中就有１个，估计其总数可达３００万个甚至更多。ＳＮＰ与 其它基因数据是一种典型的大规模高维度数据【Ｉ‘５Ｊ。 再比如，蛋白质在生物体内占有特殊的地位，它和核酸是构成原生质的主 要成分。作为生命的物质基础之一，蛋白质在催化生命体内各种反应进行、调 节代谢、抵御外来物质入侵及控制遗传信息等方面都起着至关重要的作用。蛋 白质的分离与定性、定量分析是生物化学和其他生物学科、食品检验、临床检 验、疾病诊断、生物药物分离提纯和质量检验中最重要的工作。质谱分析法是 目前测定蛋白质含量的一种常见方法。人体的卵巢蛋白质谱数据也是一种高维 数据【１６】【１．７】【１．８】【ｌ?９１，高达１５１５４维。 以人脸识别为代表的图像识别数据是高维数据的另一个例子…ｏ】【１．１１１。随着 图像采集技术的发展，现在一幅图像高达上千万像素，最简单的证件照片图像高维数据的特征选择与特征提取研究也有几万像素。假如一幅人脸图像的大小为ｍｘｎ像素，通过行堆叠的方式可将 其转换为ｍｘｎ维的向量，一般情况下，即使ｍ＝ｎ＝２５６，图像数据也会转变成 ６５５３６维的向量，因此，人脸图像数据也是真正的高维数据。 人类基因与人脸图像都可通过上述向量表示的数据束进行细致的综合描 述。这些描述“某一现象’’的多变量数据，即为高维数据。显然，随着数据维 数的不断提高，数据提供的客观现象的有关信息更加丰富、细致。但同时数据 维数的大幅度提高又会给随后的数据处理工作带来前所未有的困难。 人类疾病相关的基因是人类基因组中结构和功能完整性至关重要的信息。 对于单基因病，采用“定位克隆”和“定位候选克隆”的全新思路，才能发现 亨廷顿舞蹈病、遗传性结肠癌和乳腺癌等一大批单基因遗传病的致病基因，为 这些疾病的基因诊断和基因治疗奠定了基础。对于心血管疾病、肿瘤、糖尿病、 神经精神类疾病（老年性痴呆、精神分裂症）、自身免疫性疾病等多基因疾病是 目前疾病基因研究的重点。发展中国家和发达国家越来越重视疾病的预防，特 别是基于基因组信息的疾病预防。我国一贯提倡“预防为主”。如果能够在一个 人刚出生的时候进行疾病易感基因的识别，在早期把风险人群挑选出来，然后 在环境因子、生活方式上实施干预，就可以避免或减少人类患此类疾病的风险。 另外，人脸识别技术在国家安全、军事安全和公共安全领域的应用前景十 分广阔，例如智能门禁、智能视频监控、公安布控、出入境管理、司机驾照验 证等都是典型的应用。在民事经济领域和信息安全领域，身份识别与验证是人 类社会日常生活中的基本活动之一。目前，我们大多数情况下仍然依赖于传统 的身份验证手段来完成身份识别过程，这些手段包括身份证、卡等各类标识物 （如身份证、学生证等各类证件）与钥匙、密钥（如密码、口令）等，然而这 些方式不方便、不安全、不可靠的缺点已经越来越不能适应社会发展的需求， 而生物特征识别系统可以从根本上杜绝伪造和窃取，而且是人类自身拥有的， 因而具有更高的可靠性、安全性和可用性。在国家公共安全方面，保障国家公 共安全是社会发展的基础，社会安定更是国家持续发展的必备条件，对危险分 子进行及时、有效的监控和抓捕至关重要，而生物特征识别技术，特别是人脸、 指纹和声音识别技术，为此提供了强有力的技术保障。在家庭娱乐等领域，它 的潜力也相当大，比如人机交互、能够识别主人身份的智能玩具、家政机器人、 真实感虚拟游戏等，这些都能极大提高学习、工作效率，降低操作强度，丰富 人们的精神生活。 然而，如何从这些高维数据中识别出那些致病基因，如何根据人脸图像对 人身份进行有效的识别，这取决于对这些高维数据进行的处理是否有效。对基 因数据与人脸图像数据的特征选择或特征提取是处理过程中非常关键的一步， 将这些数据的维数降低（特征选择或特征提取）到合适的大小，同时尽可能多绪论据送入数据处理系统，在很多情形下， 系统也被称作模式识别系统。 特别有效的方法，传统的数据分析方法 在处理这些高维数据时，往往收效不大甚至失效，蕴含在数据中的信息或规律 无法被探索和理解，导致“数据资源”变成“数据灾难”。将现代计算机的高性 能与人的高智能相结合是处理这些数据最有希望的选择，是当今处理高维数据 最有效、最核心的技术与途径，其中机器学习已经被证明是行之有效的数据分 析和处理方法。然而信息技术的发展迫切需要去探索和揭示存在于这些数据之 间的奥秘。因此，如何有效地从高维数据中提取或选择出有用的特征信息或规 律并将其分类识别已成为当今信息科学与技术所面临的基本问题，这也是本文所探讨的问题。１．２高维数据处理概述１．２．１处理过程一般而言，高维数据的模式识别系统是由两个过程组成，即设计和实现…２】【１．１３】【１．１４】【１．１５】【１．１６】【ｌ?１７】【ｌ?１ ８１。高维数据的设计过程是指用一定数量的样本进行分类器设计，高维数据的实现过程是指用所设计的分类器对待识别的样本进行 分类决策。图１．１为一个高维数据的模式识别系统的简单框图，它主要由信息 获取、预处理、特征提取与选择、分类器设计以及分类决策五大部分组成。图１－１模式识别系统Ｆｉｇ．１―１ Ｔｈｅ ｓｙｓｔｅｍ ｏｆ ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ下面对这五个部分分别作简要说明。 １．信息获取 信息获取是指利用各种传感器把被研究对象的各种信息转换为计算机可以 接受的数值或符号（串）。习惯上，称这种数值或符号（串）所组成的空间为模 式空间。４高维数据的特征选择！ｊ特ｆ：『Ｆ提取研究２．预处理预处理的目的是去除信息获取中掺入的干扰和噪声，人为的加强有用的信 息，并对种种因素造成的退化现象进行复原。 ３．特征选择与提取 由信息获取部分获得的原始数据量一般是相当大的。为了有效的实现分类 识别，要对原始数据进行选择或映射，得到最能反映分类本质的特征，把这些 特征组成一个向量，称为特征向量。上述过程即为特征特取与选择过程。通过 特征提取与选择，不但减少了处理时间，而且也减少了分类错误。 ４．分类器设计 为了把待识别的模式分配到各自的模式类中，必须设计出一套分类判别规 则。基本做法是：用一定量的训练样本确定某个判别规则，使得按照这种判别 规则对被识别对象进行分类所造成的错误识别率最小或引起的损失最小。 ５．分类决策 。分类器按已确定的判别规则对待识别模式进行判别，输出分类结果，这就 是模式分类的实现过程，也称为分类决策。 上述每一阶段设计的好坏都会对整个系统的性能产生严重的影响，所以每 个阶段都应该争取尽可能完美。在模式识别系统中，第一部分和第二部分一般 属于数字信号处理和图像处理领域所研究的课题，而且一般与所研究的具体问 题有关。 本文重点讨论生物信息、人脸图像和数字手写体图像这三类高维数据的特 征选择与特征提取及识别方法研究，这部分工作主要集中在模式识别系统的第 三部分、第四部分和第五部分。‘１．２．２处理方法按照模式识别所使用的原理和方法划分，高维数据的模式识别（模式分类） 方法可以归结为如下几类： １．统计模式识别 统计模式识别是模式的统计分类方法，把模式类看成是用某个随机向量实现 的集合。又称决策理论识别方法。 目前，统计模式识别的理论体系已经相当完善，方法也很多，如Ｂａｙｅｓｉａｎ 方法、Ｆｉｓｈｅｒ方法、Ｋ．近邻方法等。从根本上，统计模式分类都是利用各类的 分布特征，即直接利用各类的概率密度函数、后验概率等，或隐含的利用上述 概念进行分类识别。如Ｆｉｓｈｅｒ方法，首先用已知类别的ｉＪｌＩ练样本产生判别函数， 然后根据待分类模式代入判别函数后所得值的情况判定其类别。判别函数所提第一章绪论供的相邻两类判决域的界面，实质上相应于在一些设定下两类概率密度函数之差。２．结构模式识别 结构模式识别是用模式的基本组成元素（基元）及其相互间的结构关系对 模式进行描述和识别的方法。在多数情况下，可以有效地用形式语言理论中的 文法表示模式的结构信息，因此也常称为句法模式识别。 结构模式识别主要立足于分析模式的结构信息。该技术将对象分解为若干 个基本单元，即基元；用这些基元以及它们的结构关系来描述对象，基元以及 这些基元的结构关系可以用字符串或图来表示；然后运用形式语言理论进行句 法分析，依据其是否符合某一类的文法而决定其类别。 ３．模糊模式识别 模糊模式识别是基于模糊数学的识别方法。现实世界中存在许多界限不分 明、难以精确描述的事物或现象，而模糊数学则可以用数学的方法研究和处理 这类具有“模糊性”的事物或现象。模糊数学的出现使得人们可以模拟人类神经 系统的活动，描述模式属于某类的程度，因此，模糊数学在模式分类中得到了 很好的应用。目前，模糊模式识别方法较多，比如模糊．近邻、模糊最小最大神 经网络等。该类方法的有效性主要在于对象类的隶属函数是否良好。 ４．神经网络模式识别 神经网络模式识别利用神经元网络中出现的神经计算模式进行。大部分神 经元网络都有某种训练规则，如基于现有模式调节连接权重。换句话说，神经 元网络直接对例子进行学习，得出其结构特征进行推广，就像孩子从狗的例子 中认识狗一样。人工神经元网络可以超越传统基于计算机的模式分类系统的能 力。人们可以利用计算机或神经元网络进行模式分类。计算机利用传统的数学 算法来检测给定的模式是否与现有模式相匹配。这是一个简单易懂的方法。但 是，该方法只能进行是或非的判断，且不允许模式有噪声。另一方面，神经元 网络允许模式可以有噪声，而且如果训练得当，神经元网络会对未知模式的类 别做出正确的响应。虽然神经元网络不能创造奇迹，但是如果采用合适的结构， 对好的数据进行正确的训练，神经元网络都可以给出令人惊异的结果。比如， ＢＰ神经网络直接从观测数据（训练样本）学习，非常简便有效，因而获得了广泛应用。上述分类方法中，统计模式识别与结构模式识别是模式识别中的经典性和 基础性技术；而模糊识别与神经网络识别则是最近发展起来的新方法，是信息 科学与人工智能的重要组成部分。另外，上述几种分类方法各有自己的特点与 应用范围，它们不能相互取代，只能相互共存，相互促进、借鉴、渗透与融合。 一个好的分类方法可能综合利用了上述各类识别方法的观点、概念和技术而形６高维数据的特征选择Ｌ＿特征提取研究成。比如本文涉及的特征选择方法，从本质上讲应该属于统计模式分类，但具 体的实现过程也涉及信息熵等一些有关内容。总之，模式识别作为一门学科， 尽管它已经经历了几十年的历史，建立了丰富的理论体系，但由于问题的复杂 性以及其应用领域范围的不断扩大，决定了它应该是开放的、发展的学科。随着相关学科新成果的不断涌现，模式分类的新方法与新理论不断涌现。如基于流形学习、基于小波分析的图像分类技术等都是典型的例子。 １．２．３特征选择与特征提取１．特征选择 一般来说模式识别系统的输入是传感器对实物或过程进行测量所得到的一 些数据，其中有些数据直接可以作为特征，有些数据经过处理之后可以作为特 征，这样的一组特征一般称为原始特征。在原始特征中并不一定每个特征都是 有用的，比如有的人吸烟喝酒却长寿，也有人自幼就病痛缠身，是因为他们基 因组中存在差异，而人类基因组上的单核苷酸多态性总量大概是３００万个，究 竟是哪些单核苷酸多态性对其起作用，可能只是其中的极少一部分特征单核苷 酸多态性与其有关联，其它单核苷酸多态性对识别基因中的分类特征意义不大， 应该去除掉。寻找这些起作用的关联单核苷酸多态性特征的过程称为特征选择， 也可以称为特征压缩。 特征选择可以描述成这样一个过程，原始特征为Ⅳ维特征Ｘ＝（ｘｉ，ｘ２，…，ｈ）。，从中选择出Ｍ个特征构成新的特征矢量Ｙ＝（ｘｌ，恐，…，％）１，其中Ｍ＜Ｎ。 ２．特征提取 然而，对有些数据来讲，特征矢量的每一个分量不一定是独立的，它们之 间可能具有一定的相关性，比如说某种物体的高度和宽度，高度值越大，宽度 值也越大，它们之间具有相关性，我们可以通过一定的变换消除掉这种相关性， 取出一个变换后的值代表该物体的特征，这种过程称为特征提取。特征提取可以描述为这样一个过程，对特征矢量ｘ＝（‘，ｘ２，…，ｈ）１施行变 换：乃＝鬼（Ｘ），江１，２，…，Ｍ，Ｍ＜Ｎ，产生出降维的特征矢量Ｙ＝（Ｍ，Ｙ２，…，％）７。３．两者的关系 在一个实际系统的设计过程中，特征的选择和特征提取过程既可以单独进 行，有时也可能两者都要进行，比如首先进行特征选择，去除掉无关特征，这 些特征实际上根本就不需要抽取出来，相关特征的传感器根本不需要安装，这 样可以减小系统的的成本。然后再进行特征提取，降低特征的维数。最后利用第一章绪论７提取之后的样本特征来设计分类器。 特征选择与特征提取的具体作用体现在三个方面：①提高泛化能力，即对 未知样本的预测能力；②决定相关特征，即与学习任务相关的特征；③特征空 间的维数约简。当训练样本的类别已知，即监督的特征选择或特征提取来说， 实际工作中有三种特征选择与特征提取问题：①是从原始特征集中选出或提取 出固定数目的特征，使得分类器的错误率最小；②是对于给定的允许错误率， 求维数最小的特征子集，这是一种有约束的最优化问题；③是在错误率和特征 子集的维数之间进行折中。对特征选择来说，上述三种特征选择都属于ＮＰ难 的问题，除了穷尽搜索之外，不能保证得到最优解，在原始特征维数Ⅳ较小时， 尚可用穷举法求解，对稍大些的Ｎ，如Ｎ＞２０，穷尽搜索实际上己经不可行。 对特征提取来说，在保证较高识别率的前提下，原始特征的维数越高可能提取 的特征维数也越高。本文所做的特征选择与特征提取工作基本上属于后两种。１．３研究现状与关键问题分析１．３．１研究现状 １．特征选择的研究现状 特征选择是统计学领域的经典问题，自上个世纪６０年代起就有学者对特征 选择问题进行研究，但当时主要是从统计学以及信息处理的角度进行研究，而且所涉及的问题通常特征数目不岁１?１９】【１．２０】【１．２１１。特征选择也是机器学习领域的重要问题，对机器学习领域的所有问题都有 重大意义，包括文本分类，数据挖掘，生物信息学，计算机视觉，信息检索， 时间序列预测等。在一个学习算法通过训练样本对未知样本进行预测之前，必 须决定哪些特征应该采用，哪些特征应该忽略。在机器学习领域，已经开展了 大量的研究，但特征选择方面的研究则相对较少。 在评价准则对应的目标函数满足单调性的前提下，Ｎａｒｅｎｄｒａ和Ｆｕｋｕｎａｇａ［１‘２２】 引入分枝限界法（ＢＢ）来求解最优特征子集，但单调性前提在实际问题中往往不 能满足。另外，即使ＢＢ算法减少了９９．９％的工作量，算法的复杂度与Ｎ仍是 指数关系，当Ｎ较大时，ＢＢ算法仍不可行。’由于求最优解的计算量太大，人们一直致力于寻找能得到较好次优解的算 法。６０年代早期的方法是，在特征间相互独立的假设下，单独研究每一特征的 类可分性或熵，然后取单独使用效果最好的组合在一起。这类方法没有考虑到 特征之间的相互作用，结果自然不理想。Ｃｏｖｅｒｔｌ．２３】指出即使满足相互独立的条 件，两个单独使用最好的特征组合起来，也不能保证是最好的组合，极端情况高维数据的特征选择与特征提取研究下，甚至可能成为最差的组合。实际上，本文研究的单核苷酸多念性就具有这 种特性。此后出现的顺序前进法、顺序后退法，以及其改进方法等实际上都属 于贪心算法。这些算法考虑到了特征的相互作用，但也存在明显的缺点，特征 一旦被加入或者被剔除，以后将不再改变，即所谓“筑巢”（ｎｅｓｔｉｎｇ）效应。为 了克服这些缺陷，出现了增Ｊ『减厂法，另外由Ｂａｃｋｅｒ和Ｓａｈｌｐｐｅ［１。２４】提出的极大 极小算法是一种速度较快的算法，但实验结果表明，当Ⅳ较大时．这种算法的 解的质量很差【１‘２５】。到了上世纪九十年代，Ｓｉｅｄｌｅｃｋｉ和Ｓｋｌａｎｓｋｙ［１舶】【１．２７】把遗传 算法应用到特征选择中，获得了较好的结果，但遗传算法常出现过早收敛的问 题。Ｐｕｄｉｌ［１．２８】等提出了顺序浮动前进法和顺序浮动后退法。这两种算法可以理 解为增Ｊ减ｘ法和减』增Ｘ法，石根据搜索情况动态地变化。算法对增Ｊ减，． 法的改进是，变固定的』和，．为浮动的，减少了不必要的回溯及在需要时增加 回溯的深度，解决了参数Ｊ和，．取值难于确定的问题。根据文献［１．２９１的实验， 顺序浮动前进法和顺序浮动后退法的解接近于最优解，而计算速度要快于分枝 限界法。 早期的研究主要集中于监督的特征选择研究，但是，最近的进展表明上面 所提到的一些算法通过一定的改造后，可以有效地用于非监督特征的选择，即 样本的类别是未知的情况【ｌ‘３０１。直到１９９７年，很少有领域所使用的特征维数超 过４０ｔ１．３１１１１３２１。然而近几年，情况发生了很大的变化，许多领域所涉及的特征 维数都非常高，如基因选择，疾病ＳＮＰ的关联性研究【Ｉ’３３１，文本检索等。对于 这种高维特征选择，还没有特别有效的方法，目前仍是研究热点。 我国特征选择的研究主要从九十年代开始。其中，具有代表意义的是陈彬、 洪家荣等人于１９９７年在计算机学报上发表了《最优特征子集选择问题》１１．３４】， 该文证明了最优特征子集选择是ＮＰ难题，并给出了一个启发式算法，另外， 张鸿宾等人利用Ｔａｂｕ搜索来进行特征选择，在维数较高时，也能收到不错的效 果。还有其它一些论文出现【Ｉｊ川。 特征选择算法有两种主要框架，即Ｆｉｌｔｅｒ和Ｗｒａｐｐｅｒ。在研究早期，算法主 要为Ｆｉｌｔｅｒ类，自Ｋｏｈａｖｉ系统提出Ｗｒａｐｐｅｒ框架后【１３６１，两类算法研究都很多。 这两类算法具有很强的互补性，表现在Ｆｉｌｔｅｒ运行速度快但相对于后续学习算 法评估偏差较大，而Ｗｒａｐｐｅｒ相对于后续学习算法评估准确但运行速度慢，关 于两者组合的研究较少【１３¨。 本文研究的重点之一就是大规模单核苷酸多态性疾病相关数据的组合式特 征选择问题，目的是设计一种适用于大规模ＳＮＰ数据的特征选择算法，以降低 后续学习算法的时间和空间复杂度，同时保持甚至提高学习算法的泛化性能。 ２．特征提取的研究现状 在模式识别的整个过程中，特征提取（有时又称为维数约减或降维）是研第一章绪论９究的重点。多年来，通过数学、信息学和计算机科学等领域的专家和学者的不 懈努力，模式识别研究特别是对数据的特征提取或维数约简的研究已经取得很 大的进展，提出了很多特征提取方法。 依据是否利用了样本的类别信息，这些方法可划分为有监督（或称为外监督） 和无监督两种特征提取方法。近年来，有些特征提取方法只是部分地用到数据 的类别信息，因此半监督特征提取方法也越来越受到人们的关注［１．３７１。 根据特征提取方法的变换方式是否是线性的，这些方法也可以分为线性和 非线性的。长期以来，线性模型一直是机器学习的主要模型。典型的线性方法 有：Ｆｉｓｈｅｒ线性判别分析（ＦｉｓｈｅｒＬｉｎｅａｒ ＤｉｓｃｒｉｍｉｎａｎｔＡｎａｌｙｓｉｓ，ＦＬＤＡ）和主成分分析（Ｐｒｉｎｃｉｐａｌ ＣｏｍｐｏｎｅｎｔＡｎａｌｙｓｉｓ，ＰＣＡ）［１－３８】等，它们在很多应用领域取得了许多成果∽９１。然而，在现实应用中很多数据并不是全局线性的。人们常常在数据的采样 过程中发现，现实世界的一些模式往往服从一定形式的非线性分布规律。这些 分布规律使样本点互相影响、互相制约，因此也就形成了一种模式在不同外界 环境作用下的多种形态。例如，同一人脸的不同图像可以由光照、姿态和表情 等关键条件决定，这些关键条件中的每一种发生变化时都会引起人脸图像中的 像素发生变化，而且这些关键条件同时变化所引起的像素的共同变化也不是由．， 每一种关键条件变化所引起的像素变化的线性叠加，也就是说光照、姿态和表 情条件变化下的人脸数据是高度非线性相关的。从几何角度来看，这样的人脸 数据是位于一个嵌入高维空间的低维流形上。在现实世界中，除了人脸数据外，， 服从低维流形分布的数据是大量存在的。比如手写数字、步态和手势等，这些 数据常常具有低维内在流形结构。 基于研究非线性分布数据的需要，很多研究者提出了大量的非线性特征提 取方法。这些方法按照其计算方式可分为基于循环迭代求解和基于（广义）特 征值分解的方法。其中人工神经网络（ＡｔｉｆｉｃｉａｌＮｅｕｒａｌＮｅｔｗｏｒｋ，ＡＮＮ）方法【１’４０】【Ｉ＿４１】【１．４２】为这些非线性数据的处理提供了一种途径，其代表性的算法是自组 织映射算法（Ｓｅｌｆ－Ｏｒｇｏｎｉｚｉｎｇ Ｍａｐｉｎｇ，ＳＯＭ）［１。４３１。基于人工神经网络的方法是基 于输入信号能够由神经网络映射到低维空间，并使其在低维空间中仍然保持高 维空间点之间的近邻关系。另一种有代表性的通过循环迭代来求解的非线性特 征提取方法是主曲线方法（Ｐｒｉｎｃｉｐａｌ Ｃｕｒｖｅｓ，ＰＣ）ｔ１州】，该方法是线性主成分的非 线性推广。这些方法的提出能够比较有效地解决非线性数据的处理需求。但是 它们毫无例外地采用循环迭代的思想，不可避免地产生下列缺陷：①使得在循 环求优的过程中容易产生局部极值而不是全局最优值；②容易产生积累误差； ③需要付出昂贵的计算代价，特别是样本数很大的情况下。目前，一些基于特 征值或广义特征值分解的方法己经被有效地应用到数据处理过程中。其中代表ｌＯ岛维数据的特征选择与特征提取研究性的方法是核变换方法和流形学习方法。核变换方法是通过核变换将具有非线 性结构的数据投影到核空间，使其在核空间线性可分。因此原有的线性方法通 过核变换扩展就变成了一种非线性方法，这也为非线性数据的处理提供了一种 有效的途径。例如，核主成分分析（Ｋｅｍｅｌ ＫＰＣＡ）［１。４５】和核Ｆｉｓｈｅｒ判别分析（ＫｅｒｎｅｌＰｒｉｃｉｎｐａｌＦｉｓｈｅｒ Ｃｏｍｐｏｎｅｎｔ Ａｎａｌｙｓｉｓ，ＤｉｓｃｒｉｍｉｎａｎｔＡｎａｌｙｓｉｓ，ＫＦＤＡ）ｔＬ４６１。由于在核变换算法中引进了核函数，在提高算法性能的同时，却 在一定程度上升高了样本的维数，而且算法的性能与核函数的选择及参数的设 定密切相关。对于不同的数据，如何选择核函数和设定最理想的参数是迫切需 要解决的问题。但是到目前为止，还没有发现一种通用的准则，多数情况下核 模型和参数的选取仍然需要经验指导。 流形学习方法是近年来才发展起来的一类新的非线性特征提取方法。流形 学习方法的应用对象是嵌入在高维空问的非线性低维流形上的数据。在认知过 程中，人们往往是通过这种非线性低维流形来识别事物的。正如前面所述，高 维空间中的人脸图像可以看作是分布在以姿态、表情和光照条件为本征特征或 自由度的低维流形上的。人们能够很快地识别这些图像正是取决于他们能够识 别这些本征特征。流形学习方法能够自动地探测出低维流形的本征特征，这说 明应用流形学习方法进行数据处理是合理和可行的。但是，流形分布数据的非 线性给流形维数约简方法的建模带来了很大的困难。为了解决这个问题， Ｔｅｎｅｎｂａｕｍ和Ｒｏｗｅｉｓ提出了一种基于局部线性、全局非线性的解决方案，在此 基础上构建了两种流形学习算法：等度规映射算法（Ｉｓｏｍａｔｒｉｃ Ｍａｐｉｎｇ， ＩＳＯＭａｐ）［１?４７１和局部线性嵌入算＂法（ＬｏｃａｌｌｙＬｉｎｅａｒＥｍｂｅｄｄｉｎｇ，ＬＬＥ）ｔ１?４８】【ｌ?４９１。这两种方法的提出，在机器学习领域中开创了流形学习的新流派。随后一批代表 性的流形学习算法纷纷涌现出来。Ｂｅｌｋｉｎ等提出了一种拉普拉斯特征谱方法（Ｌａｐｌａｃｉａｎ Ｅｉｇｅｎｍａｐ，ＬＥ）【１。５０】【１．５１１。为了解决数据不均匀采样或者数据样本点存在孔洞的问题，Ｄｏｎｏｈ等提出了一种海森特征谱方法（Ｈｅｓｓｉａｎ ＬＥ）【１．５２】。Ｚｈａｎｇ等提出了一种局部切空间排列算法（ＬｏｃａｌＥｉｇｅｎｍａｐ，Ｔａｎｇｅｎｔ ＳｐａｃｅＡｌｉｇｎｍｅｎｔ，ＬＴＳＡ）［１’５３１。随后，又有研究者提出了一种半正定嵌入算法（Ｓｅｍｉ．ＤｅｆｉｎｉｔｅＥｍｂｅｄｄｉｎｇ，ＳＤＥ）［卜５４Ｊ，并且将该算法发展成为最大差异伸展算法 Ｕｎｆｏｌｄｉｎｇ，ＭＶＵ）¨ｊ纠，该算法的一个很大的特点就是在算法（Ｍａｘｉｍｕｍ Ｖａｒｉａｎｃｅ中引入核矩阵，通过对核矩阵的半正定约束来实现对数据的凸优化（Ｃｏｎｖｅｘ Ｏｐｔｉｍｉｚａｔｉｏｎ，ｃｏ）¨‘５酬，因此ＭＶＵ在一定程度上也可以看作是一种基于核的学 习算法。Ｌｉｎ等成功地提出了一种基于Ｒｉｅｍａｎｎ局部切空间的几何流形学习方 法（Ｒｉｅｍａｎｎ Ｍａｎｉｆｏｌｄ Ｌｅａｒｎｉｎｇ，ＲＭＬ）ｔ１‘５７】【１ｊ引。随着研究的不断深入和推广，流 形学习方法也从原来的无监督学习推广到了有监督学习和半监督学习，从非线 性化扩展到线性化、张量化和核化【ｌ‘５ｗ，在机器学习领域受到了越来越多的关第一章绪论注和重视。１．３．２高维数据处理关键问题分析 高维数据由于维数过高，在特征选择与特征提取的处理过程中遇到了许多 问题，现将问题分析如下： １．特征选择的“维数灾难”问题。目前，许多应用领域所产生的源数据维 数非常高，甚至成千上万，如此高维的数据进行特征选择会导致两个方面的问 题。一个是“维数灾难”问题，由于目前大部分的特征选择算法的时间复杂度 是特征维数的二次甚至更高次，使得它们无法对高维特征进行选择或提取；另 一个是样本数远远小于特征维数，则将容易导致过学习问题。因此如何有效地 进行高维数据的特征选择与提取，是模式分类要迫切解决的。 ２．新的数据类型问题。当出现新的数据类型时，如何设计特定的特征选择 算法。随着特征选择的应用领域的不断扩大，所遇到的数据类型也将不断变化， 如随着现代科技的发展，人们发现人类个体间有９９％的基因序列是一样的，剩 下的１％序列差异构成了个体间的不同。这些序列差异有９０％都可归因于单核 苷酸多态性（ＳＮＰ）。ＳＮＰ指的是ＤＮＡ序列上发生的单个核苷酸碱基之间的变异。 ＳＮＰ可作为疾病标记，国内外科学家使用大样本的人群数量寻找能够标记疾病 的ＳＮＰ位点。他们将患病人群和健康人群的ＤＮＡ进行比较，会发现若干个ＳＮＰ 标记在患病人群中出现的更多。如果人体携带这些ＳＮＰ标记，就意味着其患某 特定疾病的风险性增加。象ＳＮＰ这种数据就是一种新的数据类型，以前提出的 特征选择算法很难通过修改来适用于这些规模庞大的新数据类型，这就要求研 究针对新的数据类型的特征选择算法。 ３．非监督算法问题。目前主要是通过对监督的特征选择算法进行改造来获 得非监督特征选择算法，非监督特征选择需要进行更深入的研究。 ４．特征选择的小样本问题。目前讨论的算法大都是建立在大样本的前提 下，基于传统的统计理论。如果相对于特征维数来说，训练样本太少时，如何 设计特征选择算法也是值得关注的问题。 ５．特征提取的“维数灾难”问题。在模式识别领域中，有大量的识别问题 可以归结为高维数据的识别问题。例如，语音识别、人脸识别、基因分类、遥 感图象分析、医学图象识别等。这些问题又因为各类训练样本的数量小于模式 特征子空间的维数，或者训练样本的数量虽然大于模式特征子空间的维数，但 两者相差不多，这被称为高维小样本问题。对于前一种情况，小样本问题会造 成某些特征提取及分类器算法的参数无法进行估计。如会造成类内协方差矩阵 奇异，使得如何抽取Ｆｉｓｈｅｒｔｌ舯１最优鉴别特征成为了一个公认的难题【１。６１】【１．６２１。１２高维数据的特征选择与特征提取研究另外，小样本问题还会引起各类协方差矩阵奇异，导致不能直接使用基于贝叶 斯理论的二次判别分析方法。对于后一种情况，虽然模式的训练样本数量可以 满足协方差矩阵非奇异性的要求，但如果训练样本数较少会引起协方差矩阵的 逆阵不稳定。 ６．高维人脸数据的特征提取问题。如何从高维人脸数据中有效地提取特征 是人脸识别中的难点。人脸图像的识别是一个复杂的具有挑战性的模式识别问 题，其主要的难点有两方面，一方面是由于人脸内在的变化所引起：①人脸具 有相当复杂的细节变化，不同的外貌如脸形、肤色等，不同的表情如眼、嘴的 开与闭等；②人脸的遮挡，如眼镜、头发和头部饰物以及其他外部物体等；另 外一方面由于外在条件变化所引起：①由于成像角度的不同造成人脸的多姿态， 如平面内旋转、深度旋转以及上下旋转，其中深度旋转影响较大；②光照的影 响，如图像中的亮度、对比度的变化和阴影等。③图像的成像条件，如摄像设 备的焦距、成像距离，图像获得的途径等等。 ７．流形学习方法的特征提取问题。现有的流形学习方法，如经典的ＬＬＥ 方法，不能提取特征，还存在不能有效处理新样本并对近邻个数敏感的问题。 这些方法处理新样本的方法是把新样本放入到已知类别的训练样本中，重新进 行ＬＬＥ方法。这种方法算法复杂度高，对大量的新样本处理不适合。１．４论文主要内容及章节安排１．４．１主要内容 从样本数据来说，本文针对二类数据的特征选择与特征提取以及识别分类 进行了探索。一是大规模生物信息数据，包括单核苷酸多态性与蛋白质谱数据。 二是高维图像数据，包括人脸图像与数字手写体图像。从机器学习的算法来说， 本文对高维数据主要做了两方面的工作：一是针对单核苷多态性的特征选择， 二是对高维数据有效的特征提取。 本文的研究内容和主要创新点如下：ｔ１．提出了多重遗传算法用于疾病相关的单核苷酸多态性的特征粗选择。应用统计机器学习方法研究大规模单核苷酸多态性（ＳＮＰ）与复杂疾病的关联关系 面临着“维数灾难”，首要的工作是把大规模ＳＮＰ缩减为较小集合，从中提取 出包含冗余信息较少的特征ＳＮＰ。为此，提出了用互信息衡量ＳＮＰ与疾病间关 联的紧密程度并作为遗传算法（ＧＡ）的适应值，通过多次运用遗传算法并合并寻 优的结果得到候选的特征ＳＮＰ集合。在ＳＮＰ仿真数据上的实验及与最大熵（ＭＥ） 方法性能比较表明，该方法最大可能丢弃了ＳＮＰ集合中与疾病无关的ＳＮＰ，同第一章绪论１３时保留了与疾病相关的ＳＮＰ，为进一步研究提供了合适规模的ＳＮＰ数据，本方 法可用于规模中等或较大的ＳＮＰ集合。 ２．提出了蛋白质谱数据特征提取的新方法。作为一种蛋白质组学工具，质 谱法的使用对疾病的早期诊断和治疗带来了革命性的变化。然而，由于面临“维 数灾难”问题，大部分机器学习方法不能直接用于识别蛋白质谱数据，同时也 面临着识别性能较低的问题。借鉴具有良好降维性能的主成分分析与局部线性判 别嵌入两种方法，提出了用于蛋白质谱数据识别的二次投影法。该方法对高维数 据先进行去噪与Ｔ检验降维，再用主成分分析获取第一次投影的低维特征向量， 随后用局部线性判别嵌入获取可分性最好的第二次投影特征向量。此外，还对局 部线性判别嵌入方法进行修改，得到一种改进的二次投影法（ＭＤＴＰ）。二种方法在 卵巢癌蛋白质谱数据上的实验表明识别性能较好。?３．为了发现高维样本的非线性流形结构，对人脸识别与数字手写体识别问题， 提出了基于流形学习的新的特征提取算法。 在保持数据局部几何结构不变的同时使数据分类边界最大化，基于这样的 思想，提出了集成最大边界准则的人脸图像特征提取算法，即保局判别分析 （ＬＰＤＡ）算法与线性局部切空问判别分析（ＬＬＴＳＤＡ）算法。该算法在确保样本低 维嵌入的局部几何结构不变的同时，确保数据分类的类内散度最小和类间散度 最大，提取到最优的分类特征信息，用于人脸图像的识别取得较好效果。 最大差异伸展（ＭＶＵ）是一种新的降维流形学习算法，将其用于模式识别领 域还存在不能处理新的测试样本等限制。利用线性变换的思想，提出了一种新的线性维度约减算法――线性最大差异伸展（ＬＭＶＵ）。该算法提取的特征信息使新的测试样本直接线性变换到低维子空间，并能最优地保留局部近邻的信息。 为了解决局部线性嵌入（ＬＬＥ）方法不能处理新样本等局限，把一幅人脸图像 或数字手写体图像直接作为一个二维数据矩阵处理，不再转换为列向量，提出了基于二维图像的特征提取算法――二维局部线性嵌入（２ＤＬＬＥ）算法。二维处理的思想有效地降低了ＬＬＥ算法的复杂度。同时，在降维中又保持了原方法发 现嵌入在高维空间的低维流形的优点，而且具有处理新测试样本的能力。实验 显示ＬＬＥ对近邻个数敏感的特性也得了有效的改善。 １．４．２章节安排 本文内容共分八章展开。 第一章，绪论。介绍了高维数据的特征选择与特征提取的研究背景意义与 研究现状及存在的问题。 第二章，典型相关算法分析。对本文后续几章中用到的几种经典算法做了１４高维数据的特征选择与特征提取研究简单介绍与分析。 第三章，基于多重遗传算法的疾病相关单核苷酸多态性选择。单核苷酸多 态性是一种大规模的生物信息数据，只有先抛弃对研究完全无用的ＳＮＰ，降低 ＳＮＰ规模，才能进行后绪的研究。文中使用多重遗传算法，对不同规模的ＳＮＰ 进行了试验，选择出的较少的疾病相关ＳＮＰ，大大降低了源ＳＮＰ的规模。 第四章，二次投影识别蛋白质谱数据的新方法。提出了二次投影法对卵巢 蛋白质谱数据进行特征提取，并有效识别分类。 第五章，基于最大边界准则的特征提取研究。利用最大边界准则与流形学 习算法的集成提出了两种新的特征提取算法：保局判别分析（ＬＰＤＡ）特征提取算 法与线性局部切空间判别分析（ＬＬＴＳＤＡ）特征提取算法。 第六章，基于线性最大差异伸展的特征提取研究。利用线性变换的思想， 将最大差异伸展算法改进为线性的特征提取算法。 第七章，基于二维局部线性嵌入的特征提取研究。基于直接在一幅二维图 像构成的数据矩阵上实施ＬＬＥ算法的思想提出一种新算法，有效降低了数据运 算的维度与计算复杂度。第二章典型相关算法分析１５第二章典型相关算法分析本章分四节介绍了遗传算法、主成分分析、线性判别分析与局部线性嵌入 四种典型特征选择与特征提取算法，并对其做了分析，这些特征选择与特征提取算法在本文后续章节使用。２．１遗传算法。遗传算法（Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ，ＧＡ）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最 优解的方法，它最初由美国Ｍｉｃｈｉｇａｎ大学Ｊ．Ｈｏｌｌａｎｄ教授于１９７５年首先提出来 的，并出版了颇有影响的专著（（Ａｄａｐｔａｔｉｏｎｉｎ Ｎａｔｕｒａｌ ａｎｄ Ａｒｔｉｆｉｃｉａｌ Ｓｙｓｔｅｍｓ）），ＧＡ这个名称才逐渐为人所知，Ｊ．Ｈｏｌｌａｎｄ教授所提出的ＧＡ通常为简单遗传算法【２．１】。遗传算法是生物遗传学与计算机科学相结合的产物。它根据适者生存，优 胜劣汰等自然进化规则来进行搜索计算和问题求解。对许多用传统数学难以解 决或明显失效的复杂问题，特别是优化问题，ＧＡ提供了一个行之有效的新途 径。随着遗传算法逐步成熟，ＧＡ已在组合优化问题求解、自适应控制、程序 自动生成、生物信息学１２‘２】、经济预测等领域取得了令人瞩目的应用成果，显示出了诱人的前景。遗传算法的主要特点是直接对结构对象进行操作，不存在求导和函数连续 性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方 法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定 的规则。它是现代有关智能计算中的关键技术。 １．遗传算法的基本流程 遗传算法是模拟自然进化的一种机器学习的模型，对采用染色体表征的个 体所组成的群体进行研究【２’３】。遗传算法采用类似进化行为的算子对这些个体进 行操作，产生新一代群体将旧群体全部替换，直至得到比较理想的群体。虽然 这个全部替换的过程与自然界并不一致，但是由于这种算法更易于实现从而得 到了广泛的采用。要将遗传算法运用于实际问题，必须将问题编码为染色体， 构成个体，参与进化过程。常用的进化算子有选择、交叉和变异等，它们发生 的概率基于各个个体的适应度函数值，这个适应度函数值表征了个体的生存能 力，从而使得具有随机性的遗传算法能朝着群体水平更好的方向发展，其结果１６高维数据的特征选择与特征提取研究比一般随机算法要好。 基本遗传算法的主要步骤为： （１）建立初始种群； （２）评价个体：计算初始种群中每个个体的适应度值； （３）利用一组遗传算子：选择（Ｓｅｌｅｃｔｉｏｎ）、交叉（Ｃｒｏｓｓｏｖｅｒ）、变异（Ｍｕｔａｔｉｏｎ）’或倒向（Ｉｎｖｅｒｓｉｏｎ）。创建新一代群体，保持个体总数不变； （４）评价新个体：计算新种群中每个个体的适应度值； （５）如果超过时间界限，或个体产生的迭代次数超过预设常数ｎ，则输出评 价值最高的个体，否则转（３）。 遗传算法的基本流程如图２．１所示。图２－１遗传算法的基本流程Ｆｉｇ．２－１ Ｔｈｅ ｓｔａｎｄａｒｄ ｐｒｏｃｅｓｓ ｏｆ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ２．适应度函数 适应度较高的个体遗传到下一代的概率较大；而适应度较低的个体遗传到 下一代的概率就相对小一些。度量个体适应度的函数称为适应度函数。遗传算第一：章典型相关算法分析１７法在进化搜索中基本不利用外部信息，仅以适应度函数为依据，利用种群中每 个个体的适应度值来进行搜索。因此适应度函数的设计至关重要，直接影响到 遗传算法的收敛速度以及能否找到最优解。 适应度函数的设计主要应满足以下条件【２‘４】： （１）单值、连续、非负、最大化； （２）合理、一致性。要求适应度值反映对应解的优劣程度； （３）计算量小。适应度函数设计应尽可能简单，这样可以减少计算时间和 空间上的复杂度，降低计算成本； （４）通用性强。 ３．遗传算子 （１）．选择算子（Ｓｅｌｅｃｔｉｏｎ ｏｐｅｒａｔｏｒ）．在生物的遗传和自然进化过程中，适者生存。遗传算法使用选择算子来对 群体中的个体进行优胜劣汰操作：适应度较高的个体被遗传到下一代群体中的 概率较大；适应度较低的个体被遗传到下一代群体中的概率较小。 常用的选择算子有轮盘赌选择、随机遍历抽样、局部选择、截断选择和锦 标赛选择等。 （２）交叉算子（Ｃｒｏｓｓｏｖｅｒ ｏｐｅｒａｔｏｒ） 交叉运算是指对两个父代个体按某种方式相互交换其部分结构而形成两个 新个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法 中起着关键作用，是产生新个体的主要方法。 最常用的交叉算子是单点交叉算子。单点交叉算子是指在两个个体串中随 机设置一个交叉点，然后以交叉概率在交叉点处相互交换两个个体的部分结构， 从而产生两个新个体。 （３）变异算子（Ｍｕｔａｔｉｏｎ ｏｐｅｒａｔｏｒ） 变异运算是指将个体编码串中的某些基因座上的基因值用该基因座的其他 等位基因来替换而形成一个新个体。 从遗传运算过程中产生新个体的能力方面来说，交叉运算是产生新个体的 主要方法，它决定了遗传算法的全局搜索能力；而变异运算只是产生新个体的 辅助方法，但它也是必不可少的，因为它决定了遗传算法的局部搜索能力。交 叉算子与变异算子的相互配合，共同完成对搜索空间的全局搜索和局部搜索， 从而使得遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。２．２主成分分析主成分分析（ＰＣＡ）是多元统计分析和数据挖掘中最广为人知的数据降维方高维数据的特征选择与特征提取研究法。早在１９０１年，Ｐｅａｒｓｏｎ就对ＰＣＡ的主要思想做出阐述【２?５１，此后，Ｈｏｔｅｌｌｉｎｇ又进一步发展了这一算法并将其应用于心理学数据的研列乙６１。另外，Ｋａｒｈｕｎｅｎ和Ｌｏｅｖｅ也在随机过程的框架下提出了ＰＣＡ算法【２?７】【２‘８】。因此，在一些文献中， ＰＣＡ算法也被称为Ｋａｒｈｕｎｅｎ．Ｌｏｅｖｅ变换。主成分分析法利用维数约减的思想， 把多指标转化为几个综合指标的多元统计分析方法。由于各评价指标之间有一 定的相关性，必然存在着起支配作用的共同因素，因此，通过主成分分析法对 原始指标变量相关矩阵内部结构关系进行研究，找出影响过程的几个综合指标， 使综合指标变为原来指标变量的线性组合，它们不仅保留了原始变量的主要信 息，彼此之间又不相关，更有助于抓住主要矛盾。 假设存在一组高维数据Ｘ＝｛ｘｉ，Ｚ＝ｌ，…，Ⅳ｝∈ＲＤ，且均值为０，ＰＣＡ的目的 就是通过线性变换的方式找到数据集的低维描述Ｙ＝舨，江ｌ，…，Ⅳ）∈Ｒ４（ｄ＜＜Ｄ），即：Ｙ＝ＷｒＸ。对于ＰＣＡ中矩阵ｗ的求解，主要有最小化重构误差和最大方差变化这两种方式，虽然这两种方式从不同的 角度出发，但最终得到的结果却是一致的。 （１）从最小重构误差的角度，ＰＣＡ的目标函数可以被表示为：ｒａｉｎ［［Ｅ｜ｌ＿ｍｉｎｓ．ｔ．∥ｒ∥＝ＩＩｘ－孵ｒｘＩｌ２（２．１）其中，Ｗ是Ｘ在高维空间中所张成的子空间的部分正交基，Ｅ为重构误差。 换句话说，ＰＣＡ的目标就是在最ｄ，－－乘的意义下，寻找一组使重构误差达到最 小的Ｗ。通过简单的数学推导，式（２－１）可以转化为：ｍｉｎ㈣＝ｍ２ｎ忙一唧７ｘｌｌ２＝呼护｛（ｘ一唧７嗣７Ⅸ一聊７ｘ）｝ＩＦ、 ，＝呼ｆｒ｛ｘｒＸ一２Ｘ７删７Ｘ＋Ｘ７删７Ｘ｝＝ｍ如ｔｒ｛Ｘ７Ｘ．ＸｒＩＶＩＶ７Ｘ｝ｗ、（２―２），式（２．２）中，ＸｒＸ为常量，因此，最小化式（２－２）就变为最大化Ｘ ７’≯聊７’Ｘ的 问题。通过推导，可以将式（２．２）转化为关于Ｗ的二次型最大化问题，因此可以通过特征值分解的方式求解，即：求样本协方差矩阵厨ｒ前ｄ个最大特征值所对应的特征向量。 （２）从另一个角度来说，ＰＣＡ算法的目的是找到高维数据集中彼此正交且数 据方差变化最大的几个方向。设高维数据的协方差矩阵为：第二章典犁相关算法分析１９巳＝ｅ｛ｘｘ７｝则根据低维数据与高维数据之间的线性变换关系，低维空间中样本的协方 差矩阵可表示为：巳＝ｅ｛ｒｒ７｝＿即ｙ７ｘｘ７∥｝＿Ｗ７ｃ＝ｗ（２．３）通过式（２．３）可以看出，在这里对矩阵Ｗ的求解同样可以转化为对高维空间 样本的协方差矩阵的特征值分解问题。 ＰＣＡ算法将数据方差的大小作为对信息衡量的标准，认为方差越大，它所 能够提供的信息就越多，反之提供的信息就越少。因此，ＰＣＡ的降维实际上就 是一个坐标变换过程，即：将数据从高维观测坐标系投影至由一组彼此正交且 数据方差变化最大方向所组成的坐标系（如图２．２所示）。． 虽然ＰＣＡ具有计算简单解释性强等优点，但它还存在着以下的不足： （１）当样本数据集具有非线性结构时，ＰＣＡ所得到的降维结果不能有效地反 映数据的本质特征。．图２－２ ＰＣＡ的不例图Ｆｉｇ．２－２ Ａｎ ｅｘａｍｐｌｅ ｏｆ ＰＣＡ（２）ＰＣＡ能够找到数据方差变化最大的方向，但这些方向对于分类和识别问 题未必是最有利的。 （３）对于ＰＣＡ中所要保持的主分量的个数比较难以估计。虽然在某些情况 下，我们可以通过数据协方差矩阵相邻特征值之间的比值对主分量的个数进行 估计，但当特征值变化比较平缓时，则难以对主分量进行取舍。 （４）在某些问题中，难以对ＰＣＡ所求得的主分量进行解释。例如：在图像 处理问题中，图像中的像素值都是非负的，当利用ＰＣＡ对一组图像进行降维处 理后，主分量中的负值难以进行语义上的解释。高维数据的特征选择与特征提驭研究２．３线性判别分析线性判别式分析（Ｌｉｎｅａｒ Ｄｉｓｃｒｉｍｉｎａｎｔ Ａｎａｌｙｓｉｓ，ＬＤＡ）是模式识别的经典算法 【２’９Ｊ，它是在１９９６年由Ｂｅｌｈｕｍｅｕｒ引入模式识别和人工智能领域的。线性鉴别 分析的基本思想是将高维的模式样本投影到最佳鉴别矢量空间，以达到抽取分 类信息和压缩特征空间维数的效果，投影后保证模式样本在新的子空间有最大 的类间距离和最小的类内距离，即模式在该空间中有最佳的可分离性。如图２．３， 右边斜线为三类特征数据投影到可分性最好的子空间。因此，它是一种有效的 特征抽取方法。使用这种方法能够使投影后模式样本的类间散布矩阵最大，并 且同时类内散布矩阵最小。就是说，它能够保证投影后模式样本在新的空间中 有最小的类内距离和最大的类间距离，即模式在该空间中有最佳的可分离性。３－ｃ ｌａｓｓ ｆｅａｔｕ ｒｅ ｄａｔａ１图２―３线性判别分析Ｆｉｇ．２－３ Ｌｉｎｅａｒｄｉｓｃｒｉｍｉｎａｎｔａｎａｌｙｓｉｓ经典的线性判别分析中使用的是Ｆｉｓｈｅｒ准则函数，所以线性判别分析又被 称为Ｆｉｓｈｅｒ线性判别分析（Ｆｉｓｈｅｒ ＬＤＡ／ＦＬＤＡ）． 线性判别分析算法通过最大化Ｆｉｓｈｅｒ准则函数，（∥）＝ａｒｇ峄矧（２－４）来求解优化的线性变换向量Ｗ。式（２－４）中最与乱分别为类问散度矩阵与类 内离散度矩阵，表示为式（２－５）第二章典型相关算法分析最５专害‘ｆ，鸭一肌。夕细一一掰。尸瓯＝万１刍ｃ吾Ｉｆ，ＸＪｊ－ｍｉ）（ｘｉｉ－ｍｉ厂（２?５）式中：Ｎ是训练样本的总数；‘是第ｉ类训练样本的数量；《表示第ｉ类的 第＿，个训练样本；ｍ，是第ｉＸ样本的均值向量；ｍ。是所有样本的均值向量． 式（２．４）在数学物理中是经常使用的，通常被称为广义的瑞利商。容易证 明，使得准则函数Ｊ（ｗ）最大化的ｗ必须满足式（２―６）ＳｂＷ＝＿；Ｌｓ．Ｗ（２?６）这是一个广义特征值问题。也可以这样不严格的来理解，在Ｊ（ｗ）的极值处， Ｗ发生微小变动，并不使得式（２―４）中的分子分母比例产生变化。如果品是非奇 异的，我们就能得到通常的特征值问题 ｓ？黾∥＝五∥（２－７）也就是说，寻找一个用于分类的优化线性子空间意味着式（２．８）的优化函数 最大化： Ｊ（Ａ）＝ｔｒ｛Ａ７谬？墨∥｝（２―８）根据Ｒａｙｌｅｉｇｈ－Ｒｉｔｚ原理，使式（２―４）的目标函数最大化可以通过求矩阵 岱：１岛）的最大特征值相应的特征向量来完成。实际应用中，经常会出现样本数 量小于样本的维数，这样可能导致矩阵奇异，无法求得特征值。后人也提出多 种改进算法避免这个问题发生。２．４局部线性嵌入局部线性嵌入（ＬＬＥ）方法是由Ｒｏｗｅｓｉ和Ｓｕａｌ［２‘ⅢＪ于２０００年提出的一种新的 非线性降维方式。它的提出极大的拓展了关于降维的认识，引起了人们广泛的 注意。一个最直接的结果就是，．人们开始更加关注数据集所蕴含的内蕴特征， 通过内蕴特征的探讨来研究关于降维的问题。所以ＬＬＥ的提出对于降维问题的 发展来讲具有重大意义。下面我们简单的介绍一下ＬＬＥ方法从直观上来看是如 何工作的，它的合理性在哪里。 根据泰勒定理我们知道，可微函数具有良好的局部线性性，即每点的微小 邻域总可以用线性模型来较好的近似。同样的对任意光滑流形而言，它的微小 局部一定程度上也应该具有线性的特征，只要我们可以清晰的描述这一局部线 性特征，那么我们就在一定程度上抓住了数据流形的根本所在。形象的来看， 就相当于将一个“足球”看作是用一块块的“球皮＂拼接而成的，若我们有了 “球皮”及其相互之间的连接方式，便可完整的了解“足球”的形成方式。所高维数据的特征选择与特征提取研究以如果数据集合可以认为是来自于某一连续可微流形的离散采样，那么只要我 们能够抓住数据集合的局部线性性也就等于抓住了数据集合的根本特征ＬＬＥ 降维便是基于这种考虑即数据流形的局部线性性，的一种非线性降维方法，如 图２．４所示，（Ａ）为原图，（Ｂ）为从中抽取的点，（Ｃ）为ＬＬＥ降维后的结果。（Ａ） 《Ｂ》豳瞳⑦＠邑协图２４局部线性嵌入Ｆｉｇ．２－４ Ｌｏｃａｌｌｙ ｌｉｎｅａｒ ｅｍｂｅｄｄｉｎｇＬＬＥ假设数据点薯∈Ｒ”和它的近邻分布在流形的一个局部线性区域，其基 本思想是认为能最佳重构高维空间中的数据点的权值能把流形的局部几何信息 从高维空间携带到低维空间。 设给定尺ｍ中的Ⅳ个数据点Ｘ＝｛五，ｘ２，…，ｈ｝∈Ｒ…Ⅳ，寻找目标空间尺ｄ中