·博士论坛·高维数据降维方法研究余肖生,周　宁(武汉大学信息资源研究中心,湖北武汉430072)摘　要:本文介绍了MDS 、Isomap 等三种主要的高维数据降维方法,同时对这些降维方法的作用进行了探讨。

关键词:高维数据;降维;MDS ;Isomap ;LLE中图分类号:G354 文献标识码:A 文章编号:1007-7634(2007)08-1248-04Research on Methods of Dimensionality Reduction in High -dimensional DataYU Xiao -s heng ,ZH OU Ning(Research Center for Information Resourc es of Wuhan University ,W uhan 430072,China )A bstract :In the paper the authors introduce three ke y methods of dimensionality r eduction in high -dimen -sional dataset ,such as MDS ,Isomap .At the same time the authors discuss applications of those methods .Key words :high -dimensional data ;dimensionality reduction ;MDS ;Isomap ;LLE收稿日期:2006-12-20基金项目:国家自科基金资助项目(70473068)作者简介:余肖生(1973-),男,湖北监利人,博士研究生,从事信息管理与电子商务研究;周　宁(1943-),男,湖北钟祥人,教授,博士生导师,从事信息组织与检索、信息系统工程、电子商务与电子政务研究.1　引 言随着计算机技术、多媒体技术的发展,在实际应用中经常会碰到高维数据,如文档词频数据、交易数据及多媒体数据等。

随着数据维数的升高,高维索引结构的性能迅速下降,在低维空间中,我们经常采用Lp 距离(当p =1时,Lp 距离称为Man -hattan 距离;当p =2时,Lp 距离称为Euclidean 距离)作为数据之间的相似性度量,在高维空间中很多情况下这种相似性的概念不复存在,这就给基于高维数据的知识挖掘带来了严峻的考验【1】。

而这些高维数据通常包含许多冗余,其本质维往往比原始的数据维要小得多,因此高维数据的处理问题可以归结为通过相关的降维方法减少一些不太相关的数据而降低它的维数,然后用低维数据的处理办法进行处理【2-3】。

高维数据成功处理的关键在于降维方法的选择,因此笔者拟先介绍三种主要降维方法,接着讨论高维数据降维方法的一些应用。

2　高维数据的主要降维方法高维数据的降维方法有多种,本文主要讨论有代表性的几种方法。

2.1　MDS (multidimensional scaling )方法MDS 是数据分析技术的集合,不仅在这个空间上忠实地表达数据之间联系,而且还要降低数据集的维数,以便人们对数据集的观察。

这种方法实质是一种加入矩阵转换的统计模式,它将多维信息通过矩阵运算转换到低维空间中,并保持原始信息之间的相互关系【4】。

每个对象或事件在多维空间上都可以通过一个点表示。

在这个空间上点与点之间的距离和对象与对象之间的相似性密切相关。

即两个相似的对象通过空间临近的两个点来表示,且两个不相似的对象第25卷第8期2007年8月情　报　科　学Vol .25,No .8August ,2007通过相距很远的两个点来表示。

这个空间通常是一个二维或三维欧氏空间,但也可能是高维的非欧空间。

根据MDS 是定性的还是定量的,MDS 可分为计量MDS (metric MDS )和非计量MDS (nonmetric MDS )。

计量MDS 方法的关键思想,将原先空间中的数据项采用投影的方法映射到欧氏空间中,再在欧氏空间内用符合点布局的点距来近似表示原先空间中这些数据项之间的距离。

例如:如果每个项目X K 先用一个二维的数据向量XK 来表示再投影到欧氏空间中,此时投射的目标是优化这个表示以至于此二维欧氏空间各项目之间的距离将尽可能接近那些原先距离。

如果用d (k ,l )表示点X K 与X L 之间距离,用d (k ,l )表示点X K 与XL 之间距离,则计量MDS 试图用d (k ,l )来近似地表示d (k ,l )。

如果误差用[d (k ,l )-d ′(k ,l )]2来表示,则取最小值的目标函数可写成:E M =∑k ≠l[d (k ,l )-d ′(k ,l )]2(1)欧氏距离的完美映射不一定总是最佳的目标,特别是当数据向量的组成部分按距离的大小顺序加以表示时。

没有距离的精确值,只有数据向量之间距离排序。

此时映射应该努力使二维输出空间距离的排名与原始空间距离排名相匹配。

通过引入一个单调递增函数f 来保证映射后的距离排名与原来的距离排名一致,非计量MDS 就采用了如下这样一个误差函数:E N =1∑k ≠l [d ′(k ,l )]2∑k ≠l[f (d (k ,l ))-d ′(k ,l )]2(2)对映射点Xk 的任何给定的结构,总能选择适当的函数f 使E N 最小。

由于处理顺序排列数据的需要,而常采用非计量MDS 。

通过选择适当的点和函数能使E M 、E N 取得最小值,这样在信息损失最小的情况下,降低了原始数据空间的维数。

2.2　Isomap 方法Isomap 方法是建立在经典MDS 基础上,结合PC A 和MDS 主要的算法特征,且试图保护数据的本质几何特征,就象在大地测量流形中获得所有对取值点之间的距离那样。

假设仅有输入空间的距离,问题的难点是估计在遥远的两点之间的大地测量距离。

对相邻的点来说,大地测量距离可由输入空间的距离近似地表示。

对遥远的点来说,大地测量距离可以近似地通过相邻的点之间的一连串的“短跳”相加来表示。

用边连结相邻的取值点而组成一张图,在这张图中找到最短路径,从而高效地计算出这些近似值【5-6】。

Isomap 方法实现主要有3个步骤。

第一步构建邻居图G ,即在输入空间X 基于一对点i ,j 之间距离的流形M ,确定哪些点是邻居。

有两种简单方法来确定,其一是在某一固定的半径ε范围内用一点连结其它所有点,其二是某一固定的半径ε范围内用一点连结它的所有的K 最近邻点。

这些邻居关系表示成数据点上的一张加权图G ,用dx (i ,j )表示相邻的点之间边的权重(如图1所示)。

图1　构建邻居图G 【5】第二步是计算最短路径,即Isomap 通过计算图G 中他们的最短路径距离d G (i ,j )来估算出流形M 上所有对点之间的大地测量距离d M (i ,j )。

发现最短路径的一简单算法如下: d X (i ,j )　当i ,j 相连时,开始:d G (i ,j )=∞ 当i ,j 不相连时。

然后,对K (=1,2,3,……,N )的每个值,用min {d G (i ,j ),d G (i ,k )+d G (k ,j )}来替代所有输入d G (i ,j )。

最终值D G ={d G (i ,j )}的矩阵包含图G 所有对点之间的最短距离。

第三步是构建d 维嵌入,即将CMDS (classical MDS )方法应用于图距矩阵D G ={d G (i ,j )},在d 维欧几里得空间Y 里,此空间Y 能最大限度地保持流形的估计的本质几何特征,建造这些数据的一个嵌入,如图2所示。

在Y 的坐标向量y i 中选择点来使误差函数减到最小E =‖τ(D G )-τ(D Y )‖L2(3)其中D Y 表示欧几里得距离{d Y (i ,j )=‖y i -y j ‖的矩阵,‖A ‖L 2表示L 2阵模∑i ,j A 2i ,j ,τ运算符将距离转化成内积,在形式上,保持了效率12498期 高维数据降维方法研究图2　维嵌入【4】最优化的数据的几何特性。

通过设置矩阵τ(D G )的d 维单位向量的坐标y i 而得到公式(3)的全局最小值。

2.3LLE (locally linear embedding )方法LLE 方法可以归结为三步【6-8】:(1)寻找每个样本点的k 个近邻点;(2)由每个样本点的近邻点计算出该样本点的局部重建权值矩阵;(3)由该样本点的局部重建权值矩阵和其近邻点计算出该样本点的输出值。

具体的算法流程如图3所示。

图3　LLE 方法的步骤【7】算法的第一步是计算出每个样本点 X i 的k 个近邻点,把相对于所求样本点距离最近的k 个样本点规定为所求样本点的k 个近邻点。

k 是一个预先给定值。

距离的计算既可采用欧氏距离也可采用Dijkstra 距离。

Dijkstra 距离是一种测地距离,它能够保持样本点之间的曲面特性。

LLE 算法的第二步是计算出样本点的局部重建权值矩阵。

这里定义一个成本函数(cost function ),如(4)式所示,来测量重建误差:ε(W )=∑iX i -∑j W ij 2(4)即全部样本点和他们的重建之间的距离平方和。

W ij 表示第j 个数据点到第i 个重建点之间的权重。

为了计算权重W ij ,我们设置两限制条件而使成本函数取最小值:首先,那每个数据点 X i 仅从它的邻居那里被重建,如果 X j 不属于 X i 的邻居的集合,则W ij =0;其次,矩阵中每行的权重和为1:∑j W ij =1。

为了使重建误差最小化,权重W ij 服从一种重要的对称性,即对所有特定数据点来说,它们和它们邻居点之间经过旋转、重排、转换等变换后,它们之间的对称性是不变的。

由此可见重建权重能够描述每个邻居本质的几何特性。

因此可以认为原始数据空间内的局部几何特征同在流形局部块上的几何特征是完全等效的。

LLE 算法的最后一步是将所有的样本点 X i 映射到在流形中表示内部全局坐标的低维向量 Y j 上。

映射条件满足如下成本函数,如(5)式所示:(Y )=∑iY i -∑j W ij Y j 2(5)其中, (Y )为成本函数值, Y j 是 X i 的输出向量, Y j 是 Y i 的k 个近邻点,且要满足两个条件,即:∑ Y i =0(i =1,2,…,N )(6)(1 N )∑ Y i Y Ti =I (i =1,2,…,N )(7)其中I 是m ×m 单位矩阵。

要使成本函数值达到最小,则取 Y j 为M 的最小m 个非零特征值所对应的特征向量。

在处理过程中,将M 的特征值从小到大排列,第一个特征值几乎接近于零,那么舍去第一个特征值。