构造邻接图的流形学习方法

在这一节中将采用ISOMAP算法对多特征观测空间中不同类型的多媒体数据进行非线性降维，具体如下:

假设多媒体数据集位于流形结构M上，M嵌入在一个高维观测空间I中。则需要找到一个从高维观测空间I到低维内嵌空间Y的映射:f:I→Y，并要求此映射尽可能保持观测空间的本征(Intrinsic)度量结构性信息。完整的ISOMAP算法包含了三个主要步骤，其中第一步就是以多媒体数据为顶点，构造一个邻接图。下面将介绍如何连接多媒体数据顶点，建立边和权重。

图9-2中多特征观测空间由三个不同类型的特征空间S1，S2，S3构成，其中任意两个多媒体数据点i，j之间的距离设定为d(i，j)；采用Rm⊂Sm×Sm表示同一个特征空间中的距离，Rmn⊂Sm×Sn(m≠n)表示不同特征空间之间的距离关系。那么，可以用对称矩阵Lmm表示所有的Rm值，矩阵中的元素值Lmm(x，y)表示特征空间Sm中多媒体数据x与多媒体数据y之间的距离值；同理，距离值Rmn可以用对称矩阵Lmm(m≠n)来量化，其中的元素值Lmn(x，y)表示特征空间Sm中多媒体数据x和特征空间Sn中多媒体数据y之间的跨媒体距离。

那么，给定文本、图像和音频三种类型的多媒体数据作为训练集，我们按照上述思想计算相同类型多媒体数据之间的距离矩阵Lmm，以及不同类型多媒体数据之间的距离矩阵Lmn，然后组合成一个综合距离矩阵A，如下所示:

分别令m＝t，m＝i，m＝a可以得到文本、图像和音频数据的内部距离矩阵Ltt、Lii、Laa；相应地，可以得到子矩阵Lti、Lta、Lia记录文本-图像、文本-音频以及图像-音频之间的跨媒体距离。采用第八章中的方法计算跨媒体距离，归一化后得到子矩阵Lti、Lta、Lia中的元素值。如果数据库中有第四种类型的多媒体数据，如:视频数据，则可以把综合距离矩阵A进一步扩充，加入子矩阵Lvv、Lvt、Lvi、Lva。(www.xing528.com)

在计算子矩阵Ltt、Lii、Laa时，首先提取多媒体数据的底层内容特征，然后根据一定的距离度量函数进行计算，底层特征和距离函数如表11-1所示:

表11-1　底层特征选择和相似度计算函数

表11-1中，参数σ是空间近似度测量的范围控制参数，‖‖表示在多媒体数据的底层内容特征空间中，样本点间的欧氏距离。

根据综合距离矩阵A构造加权无向图G，方法如下:图中的顶点为训练集中的所有媒体对象集合，用U表示；对于U中任意两个多媒体样本xi和xj，如果两者在综合距离矩阵A中的距离小于某一阈值，即:A(xi，xj)＜ε(其中参数ε为常量)，则在无向图G中的顶点xi和xj之间加一条边，且边的权重为矩阵A中的元素值A(xi，xj)。