（计算机软件与理论专业论文）维数约减技术及应用.pdf

摘要 摘要 随着网络的快速发展，科研工作者在研究过程中不可避免地会遇到大量的高 维数据，如文本数据、生物数据、网络数据以及金融交易数据等，经常会面临 维数约简的伺题。其处理涉及到两个方面：一是维数灾难问题，维数膨胀给高维 数据中模式识别和规则发现带来极大挑战：二是维数的增长又带来“维数福 音 ，从高维数据中蕴藏的丰富信息中可产生解决问题的新的可能性。如何将高 维数据表示在低维空间中，并由此发现其内在结构是高维信息处理研究的关键 问题之一降维方法作为克服“维数灾难 的有效手段，己经引起了人们广泛 的注意，相应研究方兴未艾。 本文围绕维数约减的研究逐步展开，对线性和非线性维数约减的理论进行 了深入的剖析，并研究了其在信息检索和图像处理方面的应用。 首先，本文提出了一种在潜在语义空间中基于词相似度的文本检索方法， 使得查询结果在一定程度上去除了噪声特征的影响。该方法相对于直接计算相 似度有一定的提高，且通过控制一定的参数，使得其查询时间不会随着文本集 规模的变大增加很大。 其次，针对非线性维数约减的问题，本文提出了一种保留流形非线性结构 的维数约减算法，并通过模拟的流形和图像流形验证了提出算法的效果。 第三，提出了一种新颖的流形学习算法。首先将样本数据映射到高位的希 尔伯特空间，然后，利用谱图理论建立流形的局部逼近并构造一种新的准则 函数，将流形映射到低维空间中。最后通过数字可视化以及人脸识别等实验验 证了算法的有效性及健壮性。 第四，成功地将f i s h e r 线性判别准则与局部保存投影结合起来，构造出 一种全新的维数约减算法，即保持了数据的局部几何特征又达到了使数据在低 维空间中类内紧密，类间分散的目的。 关键词模式识别；维数约减；流形学习 a b s t r a c t a b s t r a c t w i t ht h es w i f td e v e l o p m e n to fi n t e r n e t ，r e s e a r c h e r sw i l lf a c el o r so fh i g h d i m e n s i o nd a t ad u r i n gt h e i rr e s e a r c h e s ，s u c ha st e x td a t a , b i o l o g yd a t a , i n t e r n e td a t a a n dc o m m e r c i a lb u s i n e s sd a t a , e t c ，s oh o wt or e d u c et h ed i m e n s i o nt os m a l l e ro n ei sa b i gp r o b l e mi nf r o n to ft h e m d i m e n s i o nr e d u c t i o nr e s o l v e st w oa s p e c t s ：o n ei st h e d i m e n s i o nd i s a s t e rp r o b l e m ，t h eh i 曲d i m e n s i o nw i l lb r i n gv e r yh a r dd i f f i c u l t i e st o f i n dt h ep a t t e r n sa n dt h er u l e sf r o mt h eo r i g i n a ld a t a ；t h eo t h e ra s p e c ti st h a tt h eh i g h d i m e n s i o nc a ng i v eb i r t ht ot h e “d i m e n s i o ne v a n g e l ”，w h i c hm e a n st h a tt h eh i 醢 d i m e n s i o nd a t am a yc o n t a i nm o r ei n f o r m a t i o nt h a nt h el o wd i m e n s i o nt oe n l a r g et h e l i k e l i h o o do fs o l v i n gap r o b l e m s oh o wt op r e s e n tt h eh i g hd i m e n s i o nd a t ai nt h el o w d i m e n s i o ns p a c ea n df i n di t si n t e m a ls t r u c t u r ei st h ek e yp r o b l e mi nt h ed i s p o s a lo f t h eh i g hd i m e n s i o nd a t a 砥sp a p e rs t u d i e st h ep r o b l e mo fd i m e n s i o nr e d u c t i o ng o e ss t e pb ys t e p ，a n d a n a t o m i z e st h el i n e a ra n dt h en o n l i n e a rt h e o r y 埘t l la d e 印d e g r e e f i r s t l y , at e r ms i m i l a r i t yb a s e dr e t r i e v a lm o d e li sp r o p o s e d t h en o i s e sc a nb e w i p e do f fa tac e r t a i ne x t e n ta n di tc a ng e tab e t t e rr e s u l tt h a nt h et r a d i t i o n a lw a y s 砀e t i m ec o s to fo u rm e t h o di sm u c hl e s st h a nt h es t a n d a r dr e t r i e v a lm e t h o d s e c o n d l y , a i m i n g a tt h en o n l i n e a rd i m e n s i o nr e d u c t i o np r o b l e m ，an o n l i n e a r s t r u c t u r ep r e s e r v i n gd i m e n s i o nr e d u c t i o na l g o r i t h mi sp r o p o s e d s i m u l a t e dm a n i f o l d s a n df a c em a n i f o l d sa r eu s e dt ov a l i d a t et h ee f f e c t i v e n e s so ft h ep r o p o s e da l g o r i t h m t h i r d l y , an o v e lm a n i f o l dl e a r n i n gm e t h o di sp r o p o s e d ，w h i c hn o n l i n e a r l ym a p s t h eo r i g i n a ld a t ai n t oah i 曲d i m e n s i o nk e m e ls p a c ei nw h i c ht h el o c a ls i m i l a r i t yo f t h em a n i f o l di sb u i l tb yu s i n gt h es p e c t r a lg r a p ht h e o r y d i g i tv i s u a l i z a t i o na n df a c e r e c o g n i t i o ne x p e r i m e n t s a r ec o n d u c t e dt od e m o n s t r a t et h ee f f e c t i v e n e s sa n d r o b u s t n e s so fo u rm e t h o d f o u r t h l y , b yc o m b i n i n gt h e f i s h e rd i s c r i m i n a n t a n a l y s i sa n dt h el o c a l i t y p r e s e r v i n gp r o j e c t i o nan o v e ld i m e n s i o nr e d u c t i o na l g o r i t h mi sp r o p o s e d ，w h i c hn o t o n l yp r e s e r v i n gt h el o c a lg e o m e t r yf e a t u r eb u tm a k et h ed a t a 、析t l lt h es a m el a b e l s c l o s e da n dt h ed a t aw i t hd i f f e r e n tl a b e l sf a ra w a yi nt h el o wd i m e n s i o ns p a c e k e yw o r d sp a t t e r nr e c o g n i t i o n ；d i m e n s i o nr e d u c t i o n ；m a n i f o l dl e a r n i n g i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：立止日期：芈 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此 签名：盘塑导师签名 日期：邋：墨： 第l 章绪论 第1 章绪论 1 1 背景 随着信息时代的到来，科研工作者在研究过程中不可避免地会遇到大量的高 维数据，如航天遥感数据、生物数据、网络数据以及金融市场交易数据等，经 常会面临维数约简的问题。其处理面临两个问题：一是维数灾难问题，维数膨胀 给高维数据中模式识别和规则发现带来极大挑战：二是维数的增长又带来“维数 福音 ，高维数据中蕴藏的丰富信息中可产生解决问题的新的可能性。如何将高 维数据表示在低维空间中，并由此发现其内在结构是高维信息处理研究的关键 问题之一。降维方法 1 作为克服“维数灾难 的有效手段，己经引起了人们广 泛的注意，相应研究方兴未艾。 在文本分析中，一篇文档关于某些词条的影响度可以用一个高维向量表 示，向量的维数便是这些词条的个数，而向量元素则表示该篇文档中某个词条 出现的频度。于是多个文档便构成了一个矩阵，我们称之为词条矩阵。由于文 本中出现的词条数量众多，文本词条矩阵总是表现出成千上万甚至更大的维 数，使得直接的文本挖掘成为几乎不可能的工作。因此同样的，我们不希望保 留对于所有词条的频度，即首先要对文本词条矩阵进行降维。 又如在一些人脸识别的图像处理中，- - i , 图像可以表示成一个向量，其维 数等于它的全部象素个数，比如2 5 6 x 2 5 6 ，向量中的每个元素可以取为对应象 素点的灰度值，这样一个向量便可以完整的保存一副图像。然而在某些目下， 这样的存储是不必要的，比如我们只关心图像中人脸的姿态区别，那么一般来 说图像的实际维数只由光照以及人脸的动作姿态等因素决定，通常远远低于图 像的象素总数。因此我们希望将图像数据进行降维，同时能够保留各图像之间 的姿态区别。 一方面由于高维数据分析十分困难，另一方面高维数据中的信息往往主要 包含在一个或几个低维结构中，因此降维是分析高维数据的一个重要手段。降 维是在尽可能保留其原有信息量的前提下，将原来的高维向量表示成低维向 量，即减少了数据的复杂程度，又简化了后续的处理过程。 1 2 研究现状 基于降维技术的广泛应用及其实现的众多难点，很多科学家都对降维算法 的研究产生了广泛的兴趣，寻求发现嵌入在高维数据中的有意义的低维结构的 方法。现在己经有了一些高维数据低维表示的方法，它们总的说来分为两大类： 北京工业大学工学硕士学位论文 线性和非线性。比如主成分分析( p c a ) 乜3 、因子分析法和经典多维标度变换法 叫、立分量分析( i c a ) h 1 、f i s h e r 判别分析( f d a ) 嫡1 等都是被广泛应用的线性降维 方法，而l l e 嘲吖刀和i s o m a p 叫是两种有代表性的非线性降维方法。这些算法在 各自领域中都取得了很好的效果，成为人们处理数据、挖掘数据本质和特征的 有力工具。 一般来说，不管是线性方法还是非线性方法，需要保留的性质通常通过某 个目标函数的最优来刻画，因此降维问题就转化为最优化问题。比如，经典线 性降维方法主成份分析( p r i n e i p a l c o m p o n e n t s a n a l y s i s ，p c a ) 的目标是保留全局 性质，即用分量的几个线性组合来最大程度地概括原所有分量，这样就以较小 的维数保留了原来所有维数所包含的信息，最终通过求解样本点协方差矩阵的 特征值问题得到结果。局部线性嵌入( l o c a l l y l i n e a r e m b e d d i n g ，l l e ) 通过局部 邻域重构的方法，让重构过程误差极小化来保留每个样本点附近的几何结构， 即它们与其邻域点的距离位置关系，它是一种非线性降维方法。 通过对线性方法与非线性方法的比较，我们发现虽然线性降维方法形式简 单，操作方便，但对于那些具有非线性结构的数据往往无能为力。而非线性降 维技术在这方面能产生较好的结果，但它们也有个明显的缺点就是降维变换相 对比较隐式，没有直接的变换函数，有时只能应用在训练数据上。因此人们开 始研究能否找到一种方法能将两者的好处相结合。 1 3 研究内容及本文结构 针对上面两个小节提到的各种维数约减算法，以及它们与之俱来的一些缺 点，本文设计并实现了四个新颖的维数约减算法，这几个算法在一定程度上克 服了一些经典算法的缺点，并且通过实验分析，验证了提出算法的有效性，与 强壮性。本文的具体组织结构如下： 首先，在第一章中介绍了维数约减的应用背景。针对现有维数约减算法的 特点，总结了目前的维数约减算法的原理以及存在的主要问题并由此提出了 一些研究思路。 随后在第二章中介绍了维数约减方法的分类，并根据不同种类的维数约减 方法介绍了相应的典型方法，包括特征选择以及特征抽取中的主要算法，为下 面章节的引入做了一些必要的基础知识的准备。 第三章中针对现有基于向量空间模型的检索方法对噪声敏感以及时间复杂 度大的问题，提出了种在潜在语义空间中基于词相似度的文本检索方法，通过 使用线性维数约减算法主成分分析，将样本数据线性投影到线性子空间中，并 建立索引矩阵的检索模型，使得查询结果在一定程度上去除了噪声特征的影 响，相对于直接计算相似度有一定的提高，且通过控制一定的参数，其查询时 2 第1 苹绪论 间不会随着文本集规模的变大增加很大。 第四章，针对非线性维数约减的问题，提出了种保留流形非线性结构的维 数约减算法，并通过模拟的流形和图像流形验证了提出算法的效果。 第五章，提出了一种流形学习算法。首先将样本数据映射到高维的核空 间，然后，利用图理论建立流形的局部逼近，并构造一种新的准则函数将流形 映射到低维空间中。最后数字可视化以及人脸识别等实验验证了算法的有效性 及健壮性。 第六章，将f i s h e r 线性判别准则与局部保存投影相结合，构造出一种全 新的维数约减算法。它即保持了数据的局部几何特征又达到了使数据在低维空 间中类内紧密，类间分散的目的。 最后总结了全文，并对进一步的工作进行了展望。 3 第2 章常用降维方法 第2 章常用降维方法 降维方法是用来克服“维数灾难”和模型化高维数据的一种典型数据处理 技术，是用来解决这一问题的有效手段之一。它可通过对离散数据集合的分析 来探求嵌入在高维数据空间中本征低维流形的不同样式，寻求事物的本质规律 性。 维数( 特征) 约减包括两类常用的方法，即特征选择和特征抽取。 2 1 特征选择技术 特征选择技术队嘲方法是根据某种信息度量方法，对每一个特征给出一个量 化其所携带信息的量，然后，保留这个数值高于某一个阀值的那些特征的方 法。常用的特征选择技术有： 2 1 1 信息增益( i g ，i n f o r m a t i o ng a i n ) 信息增益在机器学习中经常被用作特征词评判的标准，它是一个基于熵 的评估方法，涉及较多的数学理论和复杂的熵理论公式，定义为某特征在文档 中出现前后的信息熵之差。 公式如下： i g c t ) = 一p , ( c 。) l o g ( p ，( q ) ) + b ( ，) 所( q t ) l o g ( p , ( q | ) ) + 一卫 一 所( f ) p ，( qit ) l o g ( p , ( c ti ，) ) i g ( t ) 代表特征t 的信息增益值。i g ( t ) 反映了特征t 对分类混乱程度的降低，也 就是对分类的信息量的计算。 2 1 2 互信息( m i ，m u t u a li n f o r m a t i o n ) m i 采用下面的方法来计算某个特征项t 和类别c 之间的相关性： m ，c ) = l 。g 面而a n 其中，a 为t 和c 同时出现的次数；b 为t 出现而c 没有出现的次数；c 为c 出现 而t 没有出现的次数。n 为所有文档数。如果t 和c 不相关，则i ( t ，c ) 值为o 。 如果有n 个类，则对于每个t 会有m 个值，取它们的平均值。大的i 平均值的特征 被选取的可能性大。 北京工业大学工学硕士学位论文 2 1 3 c h i ( x 统计) 类似m i ，c h i 度量的也是t 和c 之间的独立性。直观地看，x 2 ( ，c ) 的值越小， 说明特征词t 关于类c 的独立程度越高，因此我们选择那些x 2 ( ，c ) 值最大的特征 项。 ) c 2 ( f ，c ) = 百面石n ( 面a d 石- b c 两) 2 丽了 其中a 是特征t 和类别c 共现的文档数，b 为特征t 出现但不属于类别c 的文档 数。c 为属于类别c 且特征t 未出现的文档数，d 为特征t 不出现，并且不属于类 别c 的文档数。 2 1 4 期望交叉熵( e c e ，e x p e c t e dc r o s se n t r o p h y ) e c e 反映的是类概率分布与在给定某一特征值下的类概率分布的k u l l b a c k l e i b l e r 距离( k l d ) 相似性 c e ( 归删喜眺l o g 黜 以上是几种常用的特征选择方法，它们总是将特征的重要程度量化之后再 进行选择，而如何量化特征的重要性，就成了各种方法间最大的不同。 2 2 特征抽取技术 这种方法是将原始特征空间中的原始数据根据一些统计理论或者其他一 些相关的理论投影到原始空间的子空间上的降维方法。常用的特征抽取技术包 括： 2 2 1 线性维数约减技术 2 2 1 - l 主成分分析( p c a ) 主成分分析法n 幢1 是一种数学变换的方法它把给定的一组相关变量通 过线性变换转成另一组不相关的变量。这些新的变量按照方差依次递减的 顺序排列。在数学变换中保持变量的总方差不变，使第一变量具有最大的 方差，称为第一主成分，第二变量的方差次大，并且和第一变量不相关， 称为第二主成分。依次类推，i 个变量就有i 个主成分。 从代数角度，即将原变量的协方差矩阵转换成对角矩阵。从几何角度，将 原变量系统变换成新的正交系统，使之指向样本点散布最开的正交方向，进而 对多维变量系统进行降维处理。按照特征提取的观点，主成分分析相当于一种 基于最小均方误差的提取方法。下面给出主成分分析的详细介绍： 设n 维空间的随机向量用伊，c , o r ”表示，将伊进行零均值处理， 6 第2 荦常用降维万法 z = 伊一e ( 力，则e ( x ) = o 。如果对x 用一组完备正交基“，j = 1 , 2 ，n 展开，可 得 x = 口，“， i l 假设只用前k 项进行重构，则 七 一 工脚2 乙g i u l 一l 其均方误差为 孝= e 【( x x 肼) r ( x - - x r 。c ) 】 因为 “= 彤1 j - i且口= “歹x 所以 孝= 皿“歹搿r “，】= 甜歹国- ， ；+ lj - k + l 其中c = e 【材r 】= e 印一e ( 伊) 】忉一e ( 妒) 】r 是x 和伊的总体协方差矩阵。为 了使重构的均方误差最小，并满足正交条件的约束，采用拉格朗日乘子法，将 函数 j ( u ，) = “歹仇，一乃( 材歹“，- 1 ) j - k + lj = k + l 对“，j = k + l ，力求导，得 ( c 一乃i ) u = o ，j = 七+ 1 ，刀 令k = - i ，此时“”，u 。为总体协方差矩阵c 的本征向量， ，以分别是它 们对应的本征值，这些本征向量经过正交化处理所张成的空间称为本征空间。 将本征向量m ，弘。按照它们的本征值进行降序排列，则得到结论： 对于任一随机向量x ，如果采用总体协方差矩阵c 的前k 个最大且非零本 征值所对应的本征向量作为坐标轴展开，可在相等截断长度下获得所有正交展 开中最小的截断均方误差孝曲： = j - k + l 上述的变换称为k l 展开，可用于任意随机变量。随机向量x 的第i 主成分 分量可表示为 z = u 2 2 1 2 f i s h e r 线性判别分析 线性判别分析n 羽是一个典型的考虑样本类别信息的降维方法，它的主要思 7 北京工业大学工学硕士学位论文 想就是适当地选择投影方向，将原始数据投影到子空间上，使得不同类的数据 能够尽量的分开，而同类数据能够尽量集中到一起，从而为后面使用分类算法 提供了基础。它是现今流行的特征提取、模式分类方法之一，已广泛应用于模 式识别、数据分析等诸多领域。 现设有两类d 维样本x l = x ：，x i ，x 0 ) ，f _ 1 , 2 ，n i 表示第i 类样本数，样 本总数n = n 。+ n ：。我们希望找到一个投影方向矽，且具有最大判别能力，使 得异类样本在此方向上的投影能尽可能分开，同类样本尽可能紧凑。f l d a 是 通过最大化下式 删) ：磐 尹s 。伊 来求取具有最大判别能力的投影向量，实现样本分类。其中类间离散度 矩阵定义为： s 6 = ( ，卯l m 2 ) ( ，竹l m 2 ) 。 类内离散度矩阵定义为： 2n t r s 。= ( x ；一m ，) ( x ；一m ，) i - i ，一l m ，是相应的第i 类均值。 最大化，( ) 等价于求解以下广义特征值问题： s 6 = ；i s 如果s 。非奇异( 当n d ，瓯通常非奇异) ，可得最佳( 唯一) 投影方向 = s ：1 ( 朋l m 2 ) 在此方向上，不同类样本的投影分离程度达到最大。 2 2 2 非线性维数约减技术 基于流形的非线性降维方法“h 们从几何的观点来看，可以看成是挖掘嵌入 在高维数据中的低维非线性流形，这种嵌入保持了原始数据的几何特性，即在 高维空间中靠近的点在低维空间中也相互靠近。其基本观点是：高维空间中的 点由少数独立变量的共同作用在观测空间张成一个流形，如果能有效的展开观 测空间卷曲的流形或发现内在的主要变量，就可以对该数据进行降维。典型的 流形降维算法有局部线性嵌入( l l e ) ，等距映射算法( i s o m a p ) 等。 2 2 2 1 等距映射算法i s o m a p i s o m a p n 怕1 是一种全局优化算法，建立在c m d s 基础之上，试图保持数据的 内在的几何特性，获得流形上数据点之间的测地线距离。算法的关键是估计远 点( 非邻域点) 之间的测地线距离。对于邻域点，由输入空间直接得到其测地 线距离；对于非邻域点，其测地线距离可近似为一系列邻域点的测地线距离之 8 第2 章常用降维方法 和。 i s o m a p 的算法m h 踟有兰个步骤： 第一个步骤是确定在流形m 上，那些点是邻域。对于输入空间x 中的点i ，j ， 其欧式距离为d x ( i ，j ) 。将每一个点与所有的点进行比较，当两点之间的距离小 于固定的半径e ( 或i 是j 的k 一邻域) 就认为它们是相邻的，将其连接起来，边 长为d x ( i ，j ) ，得到有权图g 第二个步骤是通过计算最短路径d g ( i ，j ) 的方法估计流形m 上的测地线距 离d m ( i ，j ) 。初始时当i ，j 之间有一条边，则d g ( i ，j ) = d x ( i ，j ) ；否则d g ( i ，j ) = 。对所有的k = i ，2 ，n ，d g ( i ，j ) = m i n d g ( i ，j ) ，d g ( i ，k ) + d g ( k ，j ) ，这样得到 矩阵d g = d g ( i ，j ) ，它是图g 中所有点对的最短路径组成的。 第三个步骤是应用c m d s 构造d 维嵌入。 2 2 2 2 局部线性嵌入算法l l e 与i s o m a p 算法中计算点间的测地线距离不同，l l e 算法泓卜啪1 将全局非线性 转化为局部线性。其基本假设是每个数据点和它的邻居点位于流形的一个线性 或几乎线性区域中，维数约减的目标就是保持邻居点的局部关系。实际上，l l e 算法并没有利用距离较远的点之间的关系。 l l e 算法包括三个步骤：确定每个点的邻域，计算重构权值矩阵w ，利用 矩阵w 寻找低维嵌入。设x 是d 维空间中包含n 个样本的集合， l l e 算法如下： a ) 在数据集x 中确定每个数据点的邻域。可以像i s o m a p 算法中的那样， 或者选择与每个数据点距离最近的k 个样本，或者将指定半径的球域中包含的所 有数据点作为邻域。 b ) 利用邻域关系计算重构权值矩阵w 。对于每个样本x i ，用它的k 个最近 邻的线性组合来重构，即x 。= e w 。，x ，。当x ，不属于x 。的邻域时，w 。为o 。最小化重 构误差和函数g ( w ) = ii x , - e w 。，x ，i | 2 ，便可得到权值矩阵w 。权值w 。，可以看作 是近邻点x ，对x 。的重构贡献，为了保证重构与坐标旋转和缩放无关，强制权值矩 阵每一行的重构权值w 。，的和是1 ，即w 。j = 1 c ) 利用权值矩阵w 寻找样本集的低维嵌入y ，这通过最小化重构误差和函 数g ( y ) = | i y t - e w yl l2 ，来实现。这与前面的重构误差和函数具有相同的形 式，只是这里权值w 。，固定。 l l e 和i s o m a p 算法效率高、参数少，是非迭代的全局优化算法，具有揭示 非线性数据流形的内在特性的能力。 2 2 2 3 自组织等距嵌入s i e 前面介绍的非线性维数约减算法，查n l l e 和i s o m a p ，面临一些共同的问题： 9 北京工业大学工学硕士学位论文 首先，上述算法需要求解大尺度特征值问题或特征值问题的变形。由于特 征值问题至少二次的计算复杂性，算法在大样本集情形下的应用较受限制。其 次，上述算法的优化机制是全局的，在某些情形下对于噪声极为敏感，且需要 考虑“病态矩阵 的计算精度问题。侯越先等提出了基于自组织的非线性维数 约减方法：自组织等距嵌入嘲( s i e ，s e l f o r g a n i z i n gi s o m e t r i c e m b e d d i n g ) 。 s i e 的出发点基于如下的几何的观点：一个全局等距的嵌入必然也是局域等 距的；同样，适当选定一组局域等距约束条件，可以蕴含全局等距。具体地，考 虑利用由点集的距离分布作为等距约束条件。b o u t i n 和k e m p e r 的结果表明，在 概率意义上，由点集的距离分布可以等距地恢复出点集。在此基础上，作者注 意到通过适当选取保持局域距离分布的局域等距映象，可以在概率意义上强迫 出全局等距嵌入映象。 s i e 算法包括两个阶段：第一个阶段是求锚点集到所有样本点的测地线距离 第二阶段，s i e 算法需要由各个样本点到锚点集的测地线距离，重构出全局等距 嵌入。算法描述如下： 算法输入：原空间中n 点设置p 。，p 。，p a 的点到点欧氏距离( d ( i ，j ) ) ，1 i ，j n ；嵌入维m 、学习步数s t e p s 和学习率入。 算法输出：嵌入空间r - 中的n 点设置q 。，q ：，q a 。 s t e p1 由嵌入维m ，设定锚点数n 。，n a 应至少大于等于m + 2 ： s t e p2 在p 。，p 。，p 。中随机选择n 。个点作为锚点，记为 a l ，i = i ，2 ，r l ： s t e p3 利用类似i s o m a p 的过程，计算出锚点集中的各点到p bp p 。 的测地线距 离【d ( i ，j ) ，l i n 。，1 j n ： s t e p4 随机初始化一个r 。的n 点设置“q 0 2 ，q 0 。： s t e p5 利用自组织恢复算法，由点到点测地线距离设置，在r i 中恢复出 锚点集 a t ) 的全局等距嵌入 b 。 ： s t e p6 循环执行i = o ：l ：s t e p s x = m o d ( i ，n ) 循环执行y = l ：l ：n 计算q 。和b 1 ，之间的欧氏距离d 1 ( q 。，b 1 ，) 计算距离误差e x y = d ( x ，y ) 一d ( q 1 。，b d 计算偏移向量q ，= 入t a n h ( e 。，) ( b ”q 1 。) q p 。= q 1 。+ q 1 。 结束循环 l o 第2 章常用降维方法 结束循环 s t e p7q x = q 3 t o p s + i x , 1 x n s t e p8 返回 这里t a n h ( x ) - - 1 e - x l + e x ，用于约束偏移向量的长度；算法的具体实现通常采 用线性衰减的可变学习率入。 s i e 综合了全局算法和自组织算法的优势，利用局域等距的约束条件，以自 组织的方式，强迫出全局等距嵌入。在处理大样本时优于全局算法，s l e 的主要 计算过程是局域的，回避了特征值问题的计算，可以直接分布式实现，并且可 提高算法的鲁棒性。7 2 3 本章小结 本章重点介绍了典型的维数约减技术，为后续的章节做一些基础知识的准 备。本章从两个大方面深入地讨论了这一主题。首先，是特征选择技术。特征 选择技术通过一定的统计描述，给每一个特征然后计算一个评分，并设定一个 阀值，保留评分超过阀值的特征。其次，是特征抽取技术，这其中又分为线性 的方法以及非线性的方法，在线性的方法中，着重介绍了后续章节中要用到的 主成分分析( p c a ) ，以及f i s h e r 线性判别分析等( l d a ) 算法，在非线性方 法中，则重点介绍了经典的方法，例如局部线性嵌a ( l l e ) ，等距映射算法 ( i s o m a p ) 等。 第3 章基于索引矩阵的检索模型 第3 章基于索引矩阵的检索模型 在这一章中，通过使用线性维数约减方法一主成分分析，针对现有基于向 量空间模型的检索方法对噪声敏感以及时间复杂度大的问题，提出了一种在潜 在语义空间中基于词相似度的文本检索方法。这种方法通过在潜在语义空间中 建立一个索引矩阵来快速地对检索做出响应，查询结果在一定程度上去除了噪 声特征的影响，相对于直接计算相似度有一定的提高，且通过控制一定的参 数，其查询时间不会随着文本集规模的变大增加很大。 3 1 概述 随着i n t e m e t 的迅猛发展，网络上的信息成几何级数增长，面对浩如烟海的 而又纷繁复杂的信息资源，信息检索技术成为人们不可缺少的工具。 传统的基于文本关键字的向量空间模型( v s m ) 用n 个特征关键子构成一 个文档向量：皿= 吃t ，z z ，叱) ，其中吒，21 ，2 ”m 表示第j 个词的权重【2 8 】。这 样就将原本非结构化的文本数据表示成向量空间中的向量的形式，使得各种数 学处理成为可能。这种表示方法具有逻辑上和形式上简单，易于计算等优点。 但是，它在计算两个文本的相似度的时候依据的是词频信息，两个文本的相似 度依赖于它们共同拥有的词的数量，所以，就丢失了自然语言中的语义关系。 同时，向量空间模型是基于这样一种假设，即：不同的特征之间是相互独立 的。在实际中，这种假设条件很难得到满足，因为，不同的词之间或多或少都 会存在一定的关联。 鉴于向量空间模型的缺点，人们提出了一种称为潜在语义索引( l a t e n t s e m a n t i ci n d e x i n g ) 的技术啪1 。潜在语义索引认为，文档集合中出现的所有词语 之间存在着一定的语义结构，这种潜在的语义结构隐含在其所在的上下文环境 中，通过对文档集合做统计分析，l s i 可以很容易的捕获到这种潜在的词与词 之间的语义关系，从而，在检索的时候可以充分考虑到文本之间的语义层次的 关联。同时，在面对一词多义和多词一义的问题时，传统的基于向量空间模型 的方法无能为力，然而，通过潜在语义索引技术，这种潜在的关系可以很容易 的被发现，并使得检索结果较之向量空间模型方法大大改善。 3 2 潜在语义索引与标准查询 对于文档来说，它所包含的词与词之间通常存在着一定程度的语义关联。 1 3 北京工业大学工学硕士学位论文 在文档中词语的共现关系是分析这种语义关联的一个十分重要的信息资源。如 果在同一个文档集中两个词语在不同的文档中多次同时出现，那么它们就可以 被认为是语义相关的。然而，通过在一个学习系统中分析词语的共现信息来挖 掘语义关联是一项费时费力的工作，潜在语义索引技术就是一项用来自动发现 这种潜在的语义关系的技术。 潜在语义索引( l a t e ms e m a n t i ci n d e x i n g ) 将所有的文档投影到一个子空间 中，在这个子空中，向量的每一维都表示一个潜在的语义。同时，在原始文档 中共现的那些词被投影到语义空间中相似的方向上，而那些非共现词则被投影 到差别较大的方向上。在这个语义空间中，只要两篇文档包含一些频繁地同时 出现在文本集中的词语，那么，这两篇文档就会有很高的相似度，即使这两篇 文档没有包含相同的词语啪1 。因此，问题的关键在于刻画特征词与文档的关 系。一般地，可以用文档一词矩阵m 1 实现描述。对m 个文档、n 个特征词，取 它的行对应文档，列对应特征词，当q i = 矿( t ，嘭) 时，就是用第i 个特征词t l 在文档嘭中出现的频率粗略地表达一个特征词对相应文档的重要程度a 通过采 用适当的加权方法，可以更加合理的表达出特征词与文档的关系。显然加权方 法的不同得到的结果通常是有一定差别的b 铂吖捌。将c 转置，可以得到词一文档 矩阵c 7 。对c 7 做奇异值分解( s i n g u l a rv a l u ed e c o m p o s i t i o n ) d 4 1j 有 c t = ( 3 - 1 ) 其中，u 和y 是两个正交矩阵，它们的列向量分别称为左右奇异向量。q 是一 个对角矩阵，其对角线元素就是所得的奇异值，它们按q l q 2 q f q 什l = = q n = o 的顺序排列，r 为矩阵c r 的秩。通常根据具体需要确定一个k ， o k sr ，取c r 的k 阶近似矩阵： g r = u k q 七v ： ( 3 2 ) 其中仇由【厂的前k 列组成，幺由q 的前k 行前k 列组成，攻由y 的前k 列组 成。q r 为在语义空间中的近似表示。将原始空间中的文档投影到由巩张 成的子空间中，得到每个文档在语义空间中的表示形式。在这种表示形式下， 注意到语义空间中的文本的协方差矩阵是一个对角矩阵，即 ! u f c r c u 七：! u ；c ，r u 。= 三q 。 以力力 1 4 ( 3 3 ) 抽 。 m八 k 八a 霸吼八g 。，l = c 第3 章基于索引矩阵的检索模型 所以其每一个潜在语义维是近似线性无关的。 通过进行奇异值分解，可以在原始文档空间的基础上构造出语义空间，并 且将文档投影到这个语义空间中。 把每一个词看成只包含该词的文档，利用同样的加权机制将其投影到语义 空间中，使得所有的词和文档处于同一个语义空间中。在这个语义空间中，语 义上相关的词或者在相关的文档中出现的词将会比较接近，即使它们没有在同 一个文档中出现过。这意味着，即使一些文档没有包含某些用户查询中的关键 词，它们也会在一定程度上出现在语义空间中比较接近的位置。 当用户查询时，首先将查询向量表示成原始空间中的向量，用和构造语义 空间时同样的方法加权，将其投影到语义空间，顺序计算它与空间中每一篇文 档语义的相似度，按相似度排序，把大于某二个阀值的文档作为检索结果返 回。 标准的查询方法具有计算简单，容易理解等优点。但是，对于一篇固定的 文档来说，并不是特征集合中的每一个特征都具有同样的重要性。而且，对于 仅出现在某一篇文档中的特征来说，也有一些噪声，这样，使得原始文档在投 影到语义空间中后会出现与其本来主题方向的偏斜，造成查询的不准确。 3 3 基于索引矩阵的查询 针对上面的问题，本文使用了一种基于索引矩阵的查询方法，在这里把它 命名为i m b p ( i n d e x i n gm a t r i xb a s e dr e t r i e v a l ) 。其基本思想是根据词的语义相似 度，来确定与相应查询语义相关的文档。 首先将原始的词一文档矩阵c 7 按列进行中心化，以便将坐标原点移动到文 档集的质心，本文仍然用c 7 。表示按照列中心化处理后的矩阵。经过奇异值分解 得到其k 阶近似矩阵c k r = u 硷k v k r 。将原始特征空间中的每一个特征词按上述方 法投影到语义空间。计算这些特征词在语义空间中的两两相似度，存于矩阵脚 中。将文档表示成它所包含的主题特征的质心，即它所包含的主题特征向量的 均值。 对于一个用户查询，将其所含的查询词投影到语义空间中，找到各个查询 词语义最相似的文档，再按照这些文档对这些查询词响应的综合指标进行排 序，并提交给用户。具体的计算过程如下。 特征词i 、j 分别表示成向量i = ( 0 ，0 ，0 ，f ，o ，0 ) 和d = ( 0 ，0 ，0 ，j ，0 ，o ) ， ，力时，f 和，不在同一维上，唯一的非0 元代表特征词关于这篇“文档 的权 重。这样，可以得到特征词l ，在语义空间中的表示形式如( 3 4 ) 和( 3 5 ) ： i 豫帆田幢i c = i u k 厶m 撇巩 ( 3 4 ) ( 3 5 ) 北京工业大学工学硕士学位论文 其中l m 毗和厶一f f c 都是七维行向量。 的内积 ( i s c 帅踟哺c j s e 帆啪t t 0 = i u k * u k r * j t = i * h * d t = i * j 卑h 口 从而，特征词，与，在语义空间中的相似度为： c o s o 她嗽n c i c j s e 憾n t c ) = g n t b 以e i 瓶= = 忑= 而= = 口 = f 7 锄护下瓦丐两 = h q7 丽 令 s i 口= h 0 h l i hl l ( 3 6 ) 从而得到特征词在语义空间中的两两相似度矩阵s i 。 把矩阵脚的每一行看成一个特征词的向量表示，每个向量的每一维都是相 应特征词和其他特征词的相似度。 下面再将每一个文档表示成它和每一个特征词的相似度的形式。注意到并 不是文档中的每一个特征词对这篇文档都起到积极的作用，有些特征很可能是 噪声。本文认为只有在一篇文档中出现两次以上的特征才是一个对文档起到支 持主题作用的特征，并将其称之为主题特征，而认为那些仅出现一次的特征是 噪声。这样，就可以把文档表示成它所包含的主题特征的质心向量。 假设文档d 包含r 个主题特征“、t z ，t h ，它们在d 中出现俐次，那 么这篇文档表示为 d o c = ( f ( t i ) 事s i ( t i ) ) t ( t i ) ( 3 7 ) i m !i = l d o c 称为文档d 关于主题特征的质心向量。式中跚p 表示特征词t i 在矩阵 口中对应的行向量。在这种表示下，向量d o c 的每一维是文档d 和相应特征词 的语义相似度。显然，d 的主题特征对应维的值要大于d 的噪声特征对应维的 值。 按上面的方法计算出所有1 1 1 个文档的向量，构成t a x l l 矩阵b 。它的每一 行表示一篇文档，元素尽，表示第i 篇文档和第，个特征的语义相似度。取 1 6 第3 章基于索引矩阵的检索模型 a = b 丁( 3 8 ) 很明显，矩阵a 的每一个元素4 是特征词f 和文档，的语义相关程度，而 4 的第f 行就是特征词i 和每一篇文档的语义相关程度。对矩阵a 的每一行分 别排序，得到和每一个特征词相关的文档的先后次序。 根据上面的讨论