（电路与系统专业论文）主成分分析算法的FPGA实现[电路与系统专业优秀论文].pdf

摘要 随着信息技术的不断发展，人们不得不面对越来越多的高维数据。高维数据 包含了很多冗余信息，使得研究人员难以掌握数据之间的关系，同时也给数据的 存储、传输和处理造成资源的极大浪费。 数据降维技术研究如何在保证数据信息丢失尽可能小的前提下，降维数据维 数，提取那些隐含的、有用的信息。主成分分析是数据降维技术的典型算法，它 通过矩阵的特征分析把原始数据投影到包含了大部分数据信息的线性子空间中 达到数据降维的目的，它的优点在于计算过程简单，数据信息丢失很少。 本文第一章介绍课题的研究背景和研究意义，明确课题的研究内容和目标， 并对本文的结构安排进行说明。 第二章从分析数据降维技术的产生和发展现状入手，介绍和回顾了目前几种 常见的数据降维方法 第三章首先明确主成分分析在二维空间的几何意义，然后从理论上推导主成 分分析算法，归纳计算步骤和性质，并介绍它在不同领域中的应用。 第四章重点介绍主成分分析算法的f p g a 实现结构。实验数据表明，系统灵 活性强，可实现对于不同数据个数和不同数据维数下数据矩阵的主成分分析，误 差率较小，计算速度较快，时钟频率稳定，占用资源较少。 最后第五章阐述了本文的意义，并展望未来的工作。 关键词：数据降维，主成分分析，矩阵的特征分析，f p g a i l a b s t r a c t a l o n gw i t hc o n s t a n t l yp r o g r e s s e so fi n f o r m a t i o nt e c h n o l o g i e s ，p e o p l eh a v e t o c o n f r o n th i g hd i m e n s i o n a ld a t ai nm u l t i t u d e ，w h i c hi n c l u d em u c hr e d u n d a n t i n f o n n a t i o ns ot h a tr e s e a r c h e r sa r ed i f f i c u l tt oo b t a i nr e l a t i o n s h i p sb e t w e e n t h ed a t a m e a n w h i l e ，i t sab i gw a s t eo fr e s o u r c e sw h e n t h eh i g hd i m e n s i o n a ld a t aa r es t o r e d ， t r a n s m i t t e da n dp r o c e s s e d d a t ad i m e n s i o n a l i t yr e d u c t i o nt e c h n o l o g yr e s e a r c h e sh o wt or e d u c et h ed a t a d i m e n s i o na n de x t r a c tt h ei m p l i c i ta n dh e l p f u li n f o r m a t i o nw i t hl o s i n gi n f o r m a t i o n a s l i t t l ea sp o s s i b l e p r i n c i p a lc o m p o n e n ta n a l y s i s ( p c a ) i sat y p i c a la l g o r i t h mo f d a t a d i m e n s i o n a l i t yr e d u c t i o n ，w h i c hr e a l i z e st h ea i mb ye i g e n a n a l y s i s o fm a t r i xa n d m a p p i n gt h eo r i g i n a ld a t a t oal i n e a rs u b s p a e et h a tc o n t a i n sm o s ti n f o r m a t i o n t h e r e f o r e ，t h es t r o n g p o i n to fp c a i ss i m p l ec o m p u t a t i o n ，a n dt h e r e sl i t t l eo f i n f o r m a t i o nl o s i n g c h a p t e r1p r e s e n t e dr e s e a r c hb a c k g r o u n da n d r e s e a r c hs i g n i f i c a n c ef i r s t ，t h e n d e t e r m i n e dt h ec o n t e n ta n da i mo ft h er e s e a r c h ，i l l u m i n a t e dt h ep a p e r sc o n f i g u r a t i o n a tl a s t c h a p t e r2s t a r t e dw i t ha n a l y s i st ot h eb i r t ha n dd e v e l o p m e n t s t a t u so fd a t a d i m e n s i o n a l i t yr e d u c t i o nt e c h n o l o g y , t h e np r e s e n t e da n dr e v i e w e ds e v e r a lm e t h o d s o f d a t ad i m e n s i o n a l i t yr e d u c t i o ni nc o m m o n u s e c h a p t e r3c l e a r l yp u t f o r w a r dt h eg e o m e t r i cs i g n i f i c a n c eo fp c ai n2 ds p a c e ，t h e n d e d u c t e dp c ai nt h e o r y , c o n c l u d e dt h ec a l c u l a t e ds t e p sa n dp r o p e r t i e so f p c a f i n a l l y , t h r e ea p p l i c a t i o n so fp c a w e r ei n t r o d u c e di nd i f f e r e n tf i e l d s c h a p t e r4f o c u s e d o nt h ea r c h i t e c t u r eo fi m p l e m e n t a t i o ni nf p g a so fp c a t h e e x p e r i m e n tr e s u l t si n d i c a t et h a tt h es y s t e mc o u l di m p l e m e n tp c a a l g o r i t h mt o d i 疏r e n tn u m b e ro rd i m e n s i o no fd a t aw i t hs m a l le r r o rr a t e ，h i g h e rc o m p u t i n gs p e e d ， s t a b l ec l o c kf r e q u e n c ya n ds m a l la m o u n to fr e s o u r c e s i nm ee n d ，c h a p t e r5i l l u m i n a t e dt h es i g n i f i c a n c eo ft h ep a p e r , a n dm a d ea p r o s p e c to f t h ef u t u r er e s e a r c h k e y w o r d s ：d a t ad i m e n s i o n a l i t yr e d u c t i o n ，p c a ，e i g e n a n a l y s i so f m a t r i x ，f p g a i l l 图3 1 图3 2 图3 3 图3 4 图3 5 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图4 1 0 图4 1 l 图4 1 2 图4 1 3 插图清单 主成分分析在二维空间的几何意义1 l 不同的主成分数量下入侵检测正确率和误报率的变化2 l 文献 1 8 】中特征脸算法前4 0 个主成分对应特征值的分布情况2 2 文献 1 0 】中实验所得的前7 个“特征脸”2 2 特征脸算法的主要步骤2 3 主成分分析算法的f p g a 实现结构框图2 6 系统数据格式：1 8 b i t 定点数一2 7 串行处理数据的计算协方差矩阵模块2 8 并行处理数据的计算协方差矩阵模块2 9 向量旋转一3 1 对角线元素的c o r d i c 算法硬件结构图3 8 非对角线元素的c o r d i c 算法硬件结构图3 9 g i v e n s 算法实现矩阵特征分析的硬件结构图4 0 线性空间投影的硬件结构图4 l p o s tp r o c e s s 模块4 2 重用p o s tp r o c e s s 构成计算协方差的模块。4 3 重用p o s tp r o c e s s 模块构成主成分加权平均的硬件结构图4 4 不同数据维数r 下系统性能的变化4 5 v 1 表4 1 表4 2 表4 3 表4 4 表4 5 表4 6 表4 7 表4 8 表4 9 表4 1 0 表4 1 1 表4 1 2 表4 1 3 表清单 不同的c o r d i c 迭代次数与对应的比例因子3 8 m = 1 3 ，不同数据维数下的系统数据4 5 n = 8 ，不同数据个数下的系统数据4 5 主成分分析算法f p g a 实现的误差分析表( n = 8 ) 4 6 原始数据矩阵( m = 1 3 ，n = 8 ) 4 7 m a t l a b 计算的协方差矩阵( m = 1 3 ，n = 8 ) 4 7 主成分分析f p g a 实现计算的协方差矩阵( m = 1 3 ，n = 8 ) 4 8 m a t l a b 计算的主成分( m = 1 3 ，n = 8 ) 4 8 主成分分析f p g a 实现计算的主成分( m = 1 3 ，n = 8 ) 4 9 m a t l a b 计算的综合得分( m = 1 3 ，n = 8 ) 4 9 主成分分析f p g a 实现计算的综合得分( m = 1 3 ，n = 8 ) 4 9 8 个2 维数据矩阵5 0 经主成分分析后的8 个2 维数据矩阵5 0 v i i 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得逝至三盘堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名：签字日期： 年月日 学位论文版权使用授权书 本学位论文作者完全了解逝鎏盘堂有权保留并向国家有关部门或机 构送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝婆盘鲎 可以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字日期：年月日 导师签名： 签字日期：年月日 致谢 回想两年的硕士研究生生活，在老师指导、同学帮助以及自己不懈努力下， 我的专业理论素养和科研能力得到明显提高，培养了自己作为一名优秀集成电路 设计工程师所必需的素质：团结协作，开拓创新、踏实认真、积极进取。 首先要感谢电气工程学院院长、v l s i 设计研究所所长严晓浪教授和我的研 究生导师沈海斌副教授。严老师以他渊博的学识、对集成电路专业领域的理解与 专注、平易近人的态度和独特的个人魅力对我们进行谆谆教诲，研究所因此始终 保持着一种相互学习、积极向上的科研氛围，这给我们提供了良好的学习环境。 在课题研究期间，沈老师一直以严谨，认真的科研作风指导我，对我严格要求， 耐心解答疑问并与我讨论问题，帮助我克服了许多困难，顺利完成课题研究。同 时在这两年时间里，沈老师给予我足够的关心和信任，让我参与到研究所的科研 项目和日常事务管理中，他踏实的治学态度、创新的科研理念、职业的管理思维 一直深深影响着我，让我受益匪浅。 其次还要感谢研究所的吴晓波老师、史峥老师、何乐年老师、竺红卫老师、 王国雄老师、罗晓华老师、赵梦恋老师和我的班主任王维维老师，他们在我的学 习和科研工作中同样给予我很多帮助和指导。 另外，也要感谢董文箫博士、周喜川博士和袁生光同学，在我遇到难题时， 总是非常耐心地同我一起讨论，并热心地帮助我解决问题。感谢和我一起度过两 年美好时光的李刘林、刘洪庆、金轶安、王嗣平、周功待、朱禹、张倩、袁生光、 梁田、杨宇、胡欣幸和张昀同学，在平时学习、工作和生活中我们都是一个团结 和睦的集体! 最后，特别感谢我的父母和家人! 他们一直在背后默默地关心我，支持我， 鼓励我，给我足够的勇气和信心去面对人生。无论是痛苦的挫折，还是收获的喜 悦，我的每一份努力、每一份成绩都和他们是分不开的! 我将永远铭记这份最珍 贵的感情! 侯咏佳 2 0 0 8 年6 月于浙大求是园 第1 章绪论 第1 章绪论 在现代科学和工程领域，随着多媒体、w e b 等信息技术的不断发展，让越来 越多的海量数据呈现在科学人员面前【。海量数据通常都是高维数据，这些数据 之间包含了很多冗余信息，不仅使得科学人员难以掌握数据之间的规律和关系， 更会给数据的存储、传输、处理造成很多资源浪费。如何对这些数据进行处理， 找到数据之间的内在联系，从而有效地降低数据量，提取出那些隐含的、有用的 信息，就成为很多研究领域( 如机器学习、模式识别、数据挖掘、信息检索等) 的热门话题。 数据降维技术就是在这样的背景下得以发展的。目前，数据降维技术已经得 到长足发展，一些典型的数据降维技术包括线性判别分析( l i n e a rd i s c r i m i n a n t a n a l y s i s ，l d a ) 、多维缩放( m u l t i d i m e n s i o n a ls c a l i n g ，m d s ) 、局部线性嵌入 ( l o c a l l yl i n e a re m b e d d i n g ，l l e ) 、主成分分析( p r i n c i p a lc o m p o n e n ta n a l y s i s ， p c a ) 【2 】等。这些方法具有不同的特点和应用场合，其中主成分分析的方法是通 过矩阵的特征分析来对原始数据进行线性空间投影，从而达到降低数据维数的目 的，它的优点在于只要求取出各主成分就能进行数据降维，而且数据包含的信息 丢失很少【3 1 。主成分分析既保留了原数据的大部分信息，又去除了原始数据的相 关性，很好地实现了数据的降维。 1 1 研究背景及意义 在科学技术领域中，随着数据复杂程度的提高，随着计算机计算能力的日趋 强大，硬件和网络技术的日益发达，以及科学研究范围的扩大，人们的学习和工 作中面对越来越多的海量数据。海量数据通常都具有高维性。高维数据使人难以 掌握数据之间的规律和关系，也给存储、传输、处理造成很多资源的浪费，大大 降低了工作效率。因此高维数据的处理变得越来越重要。数据降维技术是处理高 维数据的一种通用方法，在现代科学领域，特别是在网络入侵检测，图像处理、 第l 章绪论 多元统计分析、生物医学等应用场合，因为数据量极为庞大，数据降维显得尤其 重要。 数据降维的方法有很多，包括线性判别分析、多维缩放、局部线性嵌入、主 成分分析等，这些方法具有不同的特点和应用场合。主成分分析是一种典型的数 据降维方法，也称作主分量分析，它通过对原始数据矩阵的协方差矩阵进行特征 分析，然后再进行线性空间投影达到数据降维的目的。主成分分析的主要思想是 以某些线性组合来表示原始数据，再从这些线性组合中尽快提取原始数据的信 息当第一个线性组合不能提取更多的信息时，再考虑用第二或更多的线性组合 继续提取【4 j 。这些线性组合依次被称为第一主成分( 主分量) 、第二主成分( 主 分量) 通过主成分分析得到的数据仍然保留了原始数据的大部分信息，同时 去除了数据之间的大量冗余信息，减少了数据量，很好的实现了数据降维。主成 分分析得到的数据还可以通过逆变换对原始数据进行重建，但因为主成分分析过 程中损失了小部分数据信息，所以通常会存在一定误差。 利用软件如m a t l a b 、c 等，可以很容易地实现主成分分析算法。然而利用软 件实现的主成分分析算法在速度方面与硬件实现的系统具有较大的差距，对于一 些特定的应用环境，需要计算速度更快的系统，这就必须在实现方式上改用硬件， 同时在结构上进行优化，从而达到用户满意的工作速度同时，因为主成分分析 的输入是高维数据，且每次的输入数据在个数和维数上都不相同，甚至相差很大， 所以我们设计的主成分分析算法f p g a 实现在结构上应该是灵活多变的，因此我 们采用了f p g a 的实现方法，因为f p g a 能够根据用户需要而改变结构和资源 使用情况，使得系统通用性强，资源利用率高。 在设计f p g a 实现时，关键在于三个方面：l 、计算协方差矩阵；2 、矩阵的 特征分析；3 、线性空间投影。只要结构的设计与优化得当，f p g a 实现就能在 保证精度要求的前提下，比软件系统速度更快。 1 2 研究内容和目标 本课题主要研究主成分分析算法的f p g a 实现，涉及到协方差矩阵、矩阵特 征分析、线性空间投影等统计学和线性代数的理论知识，需要考虑数据存储结构 2 第1 章绪论 的选择、数据进制转换与显示、加减乘除平方开方等数学运算的实现、矩阵特征 分析的实现、线性空间投影的实现等；同时，因为是f p g a 实现，所以还要考虑 系统的可参数化设计，即通过某些输入变量来控制对不同个数或不同维数下的主 成分分析算法实现；此外，在设计时还要考虑如何从结构优化的角度来提高时钟 频率、减少资源占用面积等，以获得系统的最优性能。 本课题的研究目标是：用f p g a 实现数据的主成分分析算法，达到数据降维 的目的，且经主成分分析算法降维后的数据保留原始数据大部分信息。同时，用 软件实现主成分分析算法，以软件系统的结果为标准，将f p g a 实现的结果与之 对比，具有较小的误差率。系统在运行速度上比软件系统具有一定优势，同时在 结构上进行优化以获得较高的时钟频率和较小的资源占用面积。 1 3 论文安排 本文第二章首先阐述了数据降维技术出现的背景和意义，然后分别介绍了数 据降维技术的发展现状和常用的数据降维方法。 第三章着重介绍主成分分析算法的理论知识，包括主成分分析在二维空间的 几何意义、主成分分析的数学描述和计算步骤以及主成分分析的性质和应用等。 第四章分三个部分重点介绍f p g a 实现主成分分析算法的结构：第一部分介 绍了当前主成分分析算法研究中取得的成果和遇到的瓶颈及技术困难；第二部分 针对上述技术上的瓶颈，把系统分成三个模块进行硬件设计和结构上的优化；最 后，第三部分通过实验数据验证设计的正确性，并对系统的性能进行评估。 最后第五章对论文的意义进行了总结，并展望了未来的研究工作。 第2 章数据降维技术综述 第2 章数据降维技术综述 2 1数据降维技术的产生和意义 在现代科学计算和工程应用中，人们需要研究越来越多的高维数据，例如某 地区经济发展各行业的经济贡献评估系统、生物医学领域的基因研究都面对1 0 维以上空间的数据，而在国防、军事的科研项目中，一个系统甚至需要处理更多 维数的数据。 这些高维数据中包含的信息并不完全是研究人员需要的，在每维数据之间还 存在很多冗余信息，这些冗余的关联不仅使得人们难以通过经验和观察来做出某 些初步判断，或者通过一些简单的计算机程序对有用的数据进行筛选，还使得数 据量变得十分庞大，占用了更多的存储空间，给系统资源带来严重浪费，也会降 低数据处理和传输的效率，甚至带来误差和计算结果的错误。 因此，如何降低数据维数，让高维数据通过某些方法转变为维数较少的数据， 而且还能包含原始数据中大部分的信息，就成为了人们非常关心和亟待解决的问 题。 数据降维技术就是在这样的背景下产生的 2 2 数据降维技术的发展现状 数据降维技术发展至今已经相当成熟，可以看到，在研究领域的各个方面， 各种数据降维技术，包括线性判别分析l d a 、多维缩放m d s 、局部线性嵌入l l e 、 主成分分析p c a 等算法都得到了广泛应用，它们各自具有不同的特点。 因为数据降维本身就是通过高维数据矩阵的各种运算或变换来达到数据降 维的目的，所以在这些数据降维算法中涉及到很多矩阵论和数理统计的知识。这 些运算对于软件来说非常容易实现，但对于硬件实现来讲却并非容易，这是因为 硬件系统中对复杂运算如乘法、除法、乘方、开方的设计非常讲究，否则就会影 4 第2 章数据降维技术综述 响系统运行速度，还会占用更大的面积，甚至功耗过高，这就丧失了硬件系统相 对软件系统的根本优势。同时，数据降维中的数据流通常是串行处理数据的，即 下一模块的输入数据需要在上一级模块的输出数据计算完毕后才能获得，这使得 硬件系统在计算速度上受到一定限制。 同时，因为数据降维的高维数据通常具有不同的数据个数和数据维数，矩阵 大小的不确定性也给硬件设计带来了不小麻烦，而这对于软件来讲易如反掌。 基于以上一些原因，现在对于数据降维算法的研究大多通过软件平台来实 现，软件平台具有成本低，灵活性强，运算能力强，函数库强大，功能完善的特 点但软件平台也有计算速度较慢的弱点，这对于科学技术不断发展、高速计算 需求是相悖的。 2 3数据降维技术常用算法 常用的数据降维算法包括线性判别分析l d a 、多维缩放m d s 、局部线性嵌 入l l e 、主成分分析p c a 等，下面对前三种算法的原理进行简单介绍，主成分 分析算法作为本研究的重点，在第三章中详细介绍。 2 3 1 线性判别分析l d a 判别分析( d i s c f i m i n a n ta n a l y s i s ，d a ) 是一种相依方法，准则变量为事先 给定的类别或者组别。银行对客户的分类就是一个典型的判别分析应用。客户向 银行贷款时，银行通常会在自己的电脑数据库中查询已存储的客户资料，包含姓 名、性别、年龄、学历、职业、收入、借贷记录等条目然后银行根据这些资料 进行判别分析，计算出每个客户的信用度，然后将客户分为“具有信用的客户” 和“不具有信用的客户”两类，并且当有新的客户资料输入数据库时，可以将这个 新的客户资料与那些已存在的客户资料作对比，得出是否应该贷款给这位新客户 的结论。 1 9 3 6 年著名的统计学家f i s h e r 提出了f i s h e r 准则【5 1 ，对于二类( 分别称为正 类和负类) 问题，希望投影后得到的y = 形r x 能够使得，仞最大 第2 章数据降维技术综述 删：蝗粤 ( 式2 1 ) o ：七g ： 其中m l 、m 2 分别是正、负类样本在投影方向上的均值，o l 、a 2 是正、负类 样本在投影方向上的方差。扩展到多类别问题，我们的目的是要寻找一个合适的 投影方向，使数据的类别内部紧聚、类别之间散布，从而保留数据之间明显的鉴 别信息，使得投影后的数据具有最大的可分性。因此在研究多类别问题时，式 2 1 可转化为 j o e ) 2 丽w r s 万b w ( 式2 2 ) 其中 s b = c ( 心一；) ( 雎一- ) r = ( 薯一以) ( 薯一。) r ( 式2 3 ) ( 式2 4 ) 矩阵称为“类别之间的散射矩阵”( b e t w e e nc l a s s e ss c a t t e rm a t r i x ) ，矩阵 s 称为“类别内部的散射矩阵”( w i t h i nc l a s s e ss c a t t e rm a t r i x ) 定义以为类别c 中样本0 8 - y - 均值，即 段= 袁萋_ ( 式2 5 ) 而所有样本的平均值定义为 ；= 专军薯= 专；m 以 ( 式2 6 ) 当s 形为正定矩阵时，可以将其化为r a y l e i g h 商【6 】。对s 矿进行c h o l k e s y 分解， 即品= b b r ，则式2 2 变为 删= 器器 ( 舰7 ) 在此基础上定义新的投影方程 巩= 丑r w ( 式2 8 ) 则有 w = b 坷呢 ( 式2 9 ) 第2 章数据降维技术综述 代入式2 7 ，可得 1 0 r ) = 业铲 ( 旭 所以使印叨最大化的呵以通过对b j 俾j 尸的特征值分解得到。 2 3 2 多维缩放m d s 多维缩放是数据分析技术的集合，它在空间上完整地表达了数据之间的关 系，而且还降低了数据的维数。多维缩放的实质是在统计模式中加入矩阵变换， 它将高维数据通过矩阵运算投影到低维空间中，并保持原始数据之间的相互关系 【刀 每个对象( 或事件) 对应着一个多维数据，而每个数据与多维空间上的点一 一对应，多维缩放用这个空间上点与点之间的距离表示数据与数据之间的相似关 系，或者说是对象( 或事件) 之间的相似性。也就是说，两个相似的对象对应于 多维空间中临近的两个点，而两个不相似的对象则对应于多维空间中相距很远的 两个点。在实际应用中，这个多维空间通常是一个二维或三维欧氏空间，但也可 能是维数更高的非欧氏空间。多维缩放可分为定量的或定性的，分别称做计量多 维缩放( m e t r i cm d s ) 和非计量多维缩放( n o n m e t r i cm d s ) 。 计量多维缩放的主要思想是将原多维空间中的点投影到另一个欧氏空间，再 在该欧氏空间内用符合点布局的点距近似表示原多维空间中这些点之间的距离。 例如先用一个二维数据向量鼍来表示一组数据点，再把瓦投影到一个合 适的欧氏空间，投影的目标是优化鼍使得在该欧氏空i ；1 中各个点之间的距离与 它们在原多维空间中的距离尽可能相等。如果用d ( m ，门) 表示点和之间距 离，用d ( 聊，聆) 表示点l 与鼍之间距离，则计量多维缩放的目的就是用 d t ( 聊，1 ) 近似表示d ( m ，刀) 如果用a = d ( m ，刀) 一d ( 朋，1 ) 来表示计算误差，则问题 转化为假设一个目标函数为 甲= a 2 = 【j ( m ，n ) - d ( 所，以) 】2 ( 式2 1 1 ) 7 第2 章数据降维技术综述 使目标函数取值最小。 通过选择适当的点和函数d t 能使目标函数甲取得最小值，这样在信息损失 最小的情况下，降低了原始数据的维数 2 3 3 局部线性嵌入l l e 2 0 0 0 年r o w e i s 和s a u l 提出了一种非线性降维方法局部线性嵌入算法 【引。这种算法的主要思想是利用局部的线性来无限逼近全局的非线性，保持局部 的几何结构不变，通过相互重叠的局部邻域来提供整体信息，从而达到保持整体 的几何性质不变的目的。 局部线性嵌入算法和数据降维的普遍思想一致，把原始数据 x = 而，屯，) ，而r d 映射到一个低维空间中的数据y = 乃，儿，以) ， 咒r ”( m d ) 。计算步骤包括： 1 、计算原高维空间中的每个点麓( i = 1 ，2 ，力) 和其它点之间的距离，根据 距离的大小，选择前后个与x ，最近的点作为其近邻点通常采用欧氏距离来度量 两个点之间的距离，即 吒= i 为- x j l ( 式2 1 2 ) 2 、计算每个劫( 扛l ，2 ，刀) 和它的每个近邻点之间的权重国，n ，即最小化 玎i 量 l q ( ) = l 而一哆o 吩i f = li = li 如果叼是却的近邻点，则哆= l ；否则哆o = 0 。 3 、根据高维空间中均和它的近邻点叼之间的权重哆d 来计算投影到低维空 间中的肋和j ：。由于在低维空间中要尽量保持高维空间中的局部线性结构，而权 重哆。代表局部信息，所以保持权重q o 不变，目标是最小化损失函数 hi七 1 2 唧( y ) = l 所一q o 乃i = ，( y r m y ) ( 式2 1 4 ) i - li 户l l 8 第2 章数据降维技术综述 保证乃= o 且圭乃乃r = j ，这样能够使平移、旋转和伸缩对损失函数 扭i，= l c r ( y ) 都没有影响。当l r 取矩阵肘的最小几个特征值所对应的特征向量时，唧( y ) 最小化。所以把矩阵m 的特征向量按照对应特征值由大到小的顺序进行排序， 取最后的m + 1 个特征向量，再去掉最后一个特征向量，由剩余的m 个特征向量 组成的矩阵就是低维空间中所得的特征向量矩阵。 9 第3 章主成分分析算法的理论 第3 章主成分分析算法的理论 在实际工程领域的研究中，为了全面、系统地分析问题，我们必须考虑众多 的影响因素。这些涉及的因素通常我们称之为指标，在多元统计分析中也称为变 量。每个变量都在不同程度上反映了所研究问题的某些信息，并且变量之间彼此 有一定的相关性，因而使得统计后的数据反映的信息在一定程度上存在重叠。在 用统计方法研究多变量问题时，变量太多会大大增加计算量和问题的复杂度，会 耗费很多硬件、网络资源，所以人们希望在进行定量分析的过程中，通过较少的 变量得到较多的信息量。主成分分析算法正是适应这一要求产生的。 主成分分析( p r i n c i p a lc o m p o n e n t a n a l y s i s ) 首先是由k p e a r s o n 在1 9 0 1 年 的生物学理论研究中引入的【9 】，之后h h o t e l l i n g 将此方法推广到心理学中随机 向量的情形f 1 0 1 ，使主成分分析得到进一步发展。1 9 4 7 年，k a r h u n e n 独立地用概 率论的形式再次描述了主成分分析算法【l l j ，其后，l o e v e 将该理论进一步扩充 和完善。因此主成分分析也有其它名称，又叫做k l t ( k a r h u n e n l o e v et r a n s f o r m ) 或者h o t e l l i n g 变换。 主成分分析的主要思想是以某些线性组合来表示原始数据，再从这些线性组 合中尽可能快地提取原始数据的信患。当第一个线性组合不能提取更多的信息 时，再考虑用第二或更多的线性组合继续快速提取的过程直到所提取的信息 与原始数据包含的信息相差不多或者满足用户精度要求【娩】。这些线性组合依次 被称为第一主成分( 主分量) 、第二主成分( 主分量) 3 1 主成分分析在二维空间的几何意义 主成分分析在二维空间的几何意义相当于坐标旋转。可以描述如下： 假设有聊个数据，每个数据都有两个变量( 或指标) 曷、局，如果将这些 数据( 散点) 描绘在以x j 、砣为坐标轴的坐标系里，它们大致分布在一个椭圆内， 如图3 1 所示。通常在实际应用中，散点的分布总有可能沿着某一方向略显扩张， 1 0 第3 章主成分分析算法的理论 我们可以把这个方向看作是椭圆的长轴，而且椭圆的长轴和短轴与坐标轴x j 、x 2 存在一个夹角0 。可以看到，在坐标系x ，o x 2 中，如果单独看这m 个散点的变量 曷或恐，无论沿着z ，方向还是勋方向，散点都具有较大的离散性，其离散的程 度可以分别用曷的方差和恐的方差来表征，方差越小表示离散程度越大。所以， 如果仅考虑为或恐中的任何一个变量，那么包含在另一个分量中的数据信息将 会损失。因此，必须找到一个新的坐标系，使得某个分量上包含的数据信息很少， 就能直接舍弃那个分量，达到降维的目的。 x 2 10、 7 图3 1 主成分分析在二维空间的几何意义 假设我们把原坐标系x t o x 2 以原点为轴逆时针旋转一个角度0 变成新坐标系 y i o y 2 ，让坐标轴y l 、y 2 分别表示椭圆的长轴方向和短轴方向。旋转后的坐标与 旋转前的坐标关系如下： j e = 墨c o s 秒+ 鼍s n 秒 ( 式3 1 ) 【匕= 一五s i n 0 + 鼍c o s 0 这样，曷和玛就转化成原变量局和而的线性组合，可以用矩阵形式表示 为： 乏 = 一c o s o s i n o 三：弓 羔 = r x c 式3 2 ， 【_ 匕jl c o s 秒儿置j 第3 章主成分分析算法的理论 其中矿= l 篇c s 酬i n o 称作旋转矩阵，容易验卸r - 矿1 ，所以它是正 交矩阵 经过坐标变换可以看到，在新坐标系y ，嘞下m 个散点的坐标巧和匕几乎 不相关。散点总是沿着y ，和肋方向分布，它们在y ，轴上的方差达到最大，在如 轴上的方差次之，所以在这两个方向上散点的离散程度很小换言之，y j 轴方向 上包含了数据的最大量信息，肋轴方向上包含的数据信息次之。如果要将这些二 维空间里的点投影到某个一维方向上，则选择y ，轴方向能使信息损失最小。在 这里，我们把巧称为第一主成分，b 称为第二主成分 第一主成分概括信息的能力大小与图中椭圆的形状有很大关系：椭圆越扁 平，m 个点在y j 轴方向上的方差越大，在肋轴方向上的方差就越小，所以第一 主成分包含的信息越多，用它来代替原数据的信息损失就越小可考虑两种极值 的情况： i 、当椭圆的长轴与短轴长度相等，即椭圆变成正圆时，第一主成分和第二 主成分各自包含了二维空间数据约一半的信息，如果只用一个主成分来表示数据 就会有约5 0 的信息损失。通常这样的信息损失率是不可取的，造成这种现象的 原因是原始变量和恐几乎不相关，即它们所包含的信息几乎不重叠，因此用 一个一维变量来表示是不合适的。 2 、椭圆越来越扁平，当椭圆的长轴在长度上远远大于短轴，短轴变为0 时， 椭圆就变成了y j 轴上的一条线段。这时第一主成分b 包含了二维空间数据的全 部信息，而第二主成分配不包含数据的任何信息，所以仅用巧来表示原始数据 不会带来任何的信息损失，可以直接舍弃掉兄。这时主成分分析的效果非常理 想。 3 2 主成分分析的数学描述与推导 3 2 1 主成分分析的数据描述 通过上面的分析，简言之，主成分分析就是针对原始数据，要寻求那些主成 1 2 第3 章主成分分析算法的理论 分并以它们为坐标轴构建一个新的坐标系，使得原始数据在新坐标轴上的投影的 方差最大。 主成分分析可用数学语言描述为：给定刀维空间中的m 个数据( 如图像信 息、工业参数、基因指标等) ，寻求一个t l x n 维的变换矩阵职使得y - y t ，y 2 ， y , 1 = w r x 而且满足新坐标系下各维之间数据的相关性最小，或者说一个去相关 性的过程【1 3 1 3 2 2 主成分分析的数学推导 在下列所有运算中均有f 、后【1 ，川，【1 ，m 】。 假设有m 个刀维数据组成的矩阵 x 删- z 体l ，x 2 ，x l = 一l五2 而l屯2 x ix 2 ( 式3 3 ) 其串x 出| i ，x i 2 ，x i 五。 x 的均值矩阵和协方差矩阵分别记为 = e ( x ) ，三= d ( x ) ( 式3 4 ) 另外，假设转换矩阵 形= 【q ，o j z ，q 】- 其中o h = 【哆。，哆：，】r 。 考虑如下的线性变换： q l哆l q 20 ) 2 2 q 。c 0 2 一 ( 式3 5 ) 巧= q l 置+ q 2 五+ + q 。鼍= q r x 艺：锡五+ a , 2 z 五+ + n 鼍2 鸭r x ( 式3 6 ) y i = c o l x l + n 2 x 2 + + 。x t = ? x 用矩阵形式表示为 坍 卅 研； l 2 哝； 一 第3 章主成分分析算法的理论 y = 【匕，e ，r 1 r = r x ( 式3 7 ) 我们需要寻求一组新的变量匕，e ，- - p 匕( d 刀) ，这组新的变量要求能 充分地反映原变量墨，鼍，鼍的信息，而且相互独立。 对于e ，艺，匕有 d ( k ) = d ( q r x ) = 鸭r d ( x ) q = 鸭r 她 ( 式3 8 ) c o y ( r , ，k ) = c o v ( 鸭r x r x ) = q r c o v ( x , x ) t o , = q r 五( 式3 9 ) 这样我们所要解决的问题就转化为，在新的变量e ，艺，匕相互独立 的条件下寻求q ，使得d ( e ) = q r 她达到最大。 由式3 8 易知，当q 未单位化时，相当于在等式右边乘以一个常数，这使 d ( k ) 也增大。为了消除这种影响，我们先假设q r 畔= 1 或者i q i _ 1 。 按照上面的分析，第一主成分就是e = 屿r x ，它满足屿r q = 1 ，使得 d ( e ) = q r 地达到最大值。 同理， 第二主成分是匕= 吐r x ，它满足r = 1 ， 且 c o v ( r 2 ，e ) = c o v ( m 2 r x q r x ) = o ，使得d ( 艺) = r 五达到最大值。 一般情形下，第k 主成分是k = r x ，它满足r = l ，且 c o v ( r , ，e ) = c o v ( r x q r x ) = o ( f 后) ，使得d ( 耳) = 噜r 五达到最大值。 下面依次求取各主成分。 构造目标函数 仍( 哆，名) = q r x o h 一名( q r - 1 ) ( 式3 1 0 ) 并对目标函数仍微分，有 即 要= 2 x m , 一2 见鸭= o a ， 1 1 4 第3 章主成分分析算法的理论 ( 三一旯j ) q = 0 ( 式3 1 2 ) 由式3 1 2 两边分别左乘，r ，可得 0 ) 1 r 她= 名 ( 式3 1 3 ) 式3 1 2 是x 的协方差矩阵三的特征方程，因为三是非负定的，所以特征根 均大于0 ，假设丑五丸o 。由式3 1 3 可知i 1 的方差为允，也就是说， 玎的最大方差为a ，其相应的单位化特征向量是q 。 在求第二主成分之前，由式3 1 1 可知 c o v ( r 2 ，e ) = 鸭r 她= 名呜r q ( 式3 1 4 ) 因为匕和巧相互独立，所以令式3 1 4 等于0 ，则有 哆r o h = 0 蜊f m l r o j 2 = 0 ( 式3 1 5 ) 再次构造求取第二主成分的目标函数 讫( 哆，a ，p ) = 吐r x o j z a ( 鸭r 鸭一1 ) 一2 p q r 吐 ( 式3 1 6 ) 对目标函数仍进行微分，有 孕= 2 石6 0 z 一2 2 屯o z 一2 p 颤0 j = o 0 2 0 2 用q r 左乘式3 1 7 ，得到 m ：t 一：m t p ；m l = 0 因为鸭r 地= o ，q r 哆= 0 且q r q = l ，代入式3 1 8 可得p = 0 。所以再 由式3 1 7 得到 ( 三一旯，) = 0 ( 式3 1 9 ) 再左乘r ，则有 0 9 2 r 地= 旯 ( 式3 2 0 ) 这样说明，如果x 的协方差矩阵三的特征根为 五 o ，由式3 2 0 可知，场的最大方差为第二大特征根五，其相应的单位化特征向量是。 第3 章主成分分析算法的理论 针对一般情况，在鸭r = l 且q r 哆= 0 或哆r q = 0 ( 心) 的条件下，使 得d ( k ) = r 占达到最大值，这时的匕= r x 即为第k 主成分为此构造 目标函数 饩( ，旯，肛) = q r 臣一旯( q r q - 1 ) - 2 y 只鸭r q i = i 对目标函数求微分，得到 要：2 x 屯o k 一2 旯q 一2 k - ip q ：o o k五 用鸭r 左乘式3 2 2 ，有 q r 地一a q r q 一p 鸭r q = o 同理，因为哆r 地= o ，哆r 魄= o 且哗r 鸭= 1 ，代入式3 2 3 可得 岛= o ( f = l ，2 ，k - 1 ) 。再由式3 2 2 可知 ( 三一五j ) = 0 式3 2 4 两边左乘鸭r ，则有 f 三= 九 由此说明如果x 的协方差矩阵三的特