X =
∪
k =1
C
X
kn k
,
N =
∪ nk
k =1
C
输出： Y ，其中 Y 以元胞数组形式存放，每一个 Yi 表示降到 i 维时的嵌入值。 算法步骤(见参考文献 5)： 步骤 1：基于公式(5)计算类间散度矩阵，其中 u k 表示第 k 类样本均值， u 为 总体样本均值；
C
SB =
∑n
k =1
−3
D = D + α max ( D)Λ
其余步骤与 LLE 算法相同。
（ 11 ）
3.6 Isomap 实验
输入： X ， X D× N = [ X 1 , X 2 ,⋯ X N ] ,其中 D 为数据维数， N 为样本点数。 参数： K ，其中 K 为邻域值大小，这里取 10。 输出： Y ，其中 Y 以元胞数组形式存放，每一个 Yi 表示降到 i 维时的嵌入值。 算法步骤(见参考文献 8)： 步骤 1：基于欧式距离构造矩阵 D ，其中 Dij 表示 X i 和 X j 的距离； 步骤 2：计算每一个样本点的 K 邻域； 步骤 3：若样本 j 是样本 i 的 K 邻域，则 Dij = d ij ，否则置为无穷大，计算 dijkstra 距离。 其余步骤与 MDS 算法相同。
−d ( x − x ) ⎧ β ⎪ ⎪ 1− e D( xi , x j ) = ⎨ ⎪ d ( xβ− x ) ⎪ −α ⎩ e
2
i
j
label(i ) = label( j ) label(i) ≠ label ( j )
2
(12)
i
j
其余步骤与 Isomap 算法相同。
3.8 LE 实验
输入： X ， X D× N = [ X 1 , X 2 ,⋯ X N ] ,其中 D 为数据维数， N 为样本点数。 参数： K ，其中 K 为邻域值大小，这里取 10。 输出： Y ，其中 Y 以元胞数组形式存放，每一个 Yi 表示降到 i 维时的嵌入值。 算法步骤(见参考文献 10)： 步骤 1：基于欧式距离构造矩阵 D ，其中 Dij 表示 X i 和 X j 的距离； 步骤 2：计算每一个样本点的 K 邻域； 步骤 3：若样本 j 是样本 i 的 K 邻域，则W ij = e 步骤 4：对公式(13)做 ⎪ 1− e D ( xi , x j ) = ⎨ d (x −x ) ⎪ β −α ⎩ e
2
i
j
label (i ) = label ( j ) label (i ) ≠ label ( j )
2
(14)
i
j
其余步骤与 LE 相同。
4、分类测试算法
4.1 参数设置 测试分类效果的方法采用 SVM，算法实现使用程序包 LibSVM。所有算 例的模型选择和参数设置方法如下： 采用高斯（RBF）核函数
基于降维分类实验报告 1、 初始数据
实验采用 Glass、Wine、Colon-cancer、Heart、Swiss-roll 五组数据集， 详见表 1。
数据集(表 1) 数据集
glass wine swiss roll heart_scale colon-cancer
样本点数
214 178 500 270 62
最大特征值的特征向量(由于 SW 一般为奇异矩阵，故在此进行了正则化， 即
S W = S W + ones ( n , n ) × tol × tr ( S W ) )；
W T S BW Wopt = arg max T = [ w1 , w2 ,⋯ wm ] W SW W
步骤 4：基于公式(8)做低维嵌入数据。
3、实验步骤(基于 matlab) 3.1 PCA 实验
输入： X ， X D× N = [ X 1 , X 2 ,⋯ X N ] ,其中 D 为数据维数， N 为样本点数。 输出： Y ，其中 Y 以元胞数组形式存放，每一个 Yi 表示降到 i 维时的嵌入值。 算法步骤(见参考文献 3)： 步骤 1：基于公式(1)计算协方差矩阵, 其中X 为样本均值 ；
3.7 Sisomap 实验
输入： X 和 label ， X D× N = [ X 1 , X 2 ,⋯ X N ] ,其中 D 为数据维数， N 为样本点数，
label 为类标签。
参数： K 和 α ，其中 K 为邻域值大小，这里取 10， α 为公式（12）的参数， 这里取 0.5。 输出： Y ，其中 Y 以元胞数组形式存放，每一个 Yi 表示降到 i 维时的嵌入值。 算法步骤(见参考文献 9)： 步骤 1：根据欧式距离构造矩阵 D ，其中 Dij 表示 X i 和 X j 的距离； 步骤 2：基于公式(12)更新矩阵 D ，其中 β 为所有样本点的平均距离。
label 为类标签。
参数： K 和 α ，其中 K 为邻域值大小，这里取 10， α 为公式（14）的参数， 这里取 0.5。 输出： Y ，其中 Y 以元胞数组形式存放，每一个 Yi 表示降到 i 维时的嵌入值。 算法步骤(见参考文献 11)： 步骤 1：根据欧式距离构造矩阵 D ，其中 Dij 表示 X i 和 X j 的距离； 步骤 2：基于公式(12)更新矩阵 D ，其中 β 为所有样本点平均距离的平方。
维数
9 13 3 13 2000
分类数目
6 3 5 2 2
各个数据集描述如下： Wine 数据集采自 UCI 数据库(见文献【1】)。包括 13 个特征的 3 类 葡萄酒共 178 个样本，大量的文献采自此数据库。数据集没有缺失值，样 本经过归一化处理，即取值在[-1,1]之间。 Colon-cancer 数据集，用于二分类的数据集。文献【2】中实验所采用 的数据集， 包含结肠癌基因表达以及正常基因表达数据共 62 个，2000 个基 因。所有样本都经过中心化，和方差标准化处理。
Y = X TU
3.2 MDS 实验
输入： X ， X D× N = [ X 1 , X 2 ,⋯ X N ] ,其中 D 为数据维数， N 为样本点数， 参数： tol ，其中 tol 为正则化参数，这里取10 −3 。
（3）
输出： Y ，其中 Y 以元胞数组形式存放，每一个 Yi 表示降到 i 维时的嵌入值。 算法步骤(见参考文献 4)： 步骤 1：基于欧式距离构造矩阵 D ，其中 Dij 表示 X i 和 X j 的距离； 步骤 2：计算矩阵 S 和 H ,其中 S ij = Dij 2 ， H = I − 步骤 3：基于公式(4)L=-H*S*H 做特征分解；
−−
d ij 2 t2
，否则置为 0；
L = D −W
（ 13 ）
步骤 5：对特征值从小到大排序，选取第 2 到 d + 1 个特征对应的特征向量 即为 d 维嵌入值。(注：由于最小特征值为 0，此时特征向量全为 1，故不 选取)
3.9 SLE 实验
输入： X 和 label ， X D× N = [ X 1 , X 2 ,⋯ X N ] ,其中 D 为数据维数， N 为样本点数，
带有类标签的 Swiss roll 曲线(图 1)
表2
数据集
glass(214 个) Swiss roll(1000 个)
Isomap
0.6163 0.5339
S-isomap
0.7141 0.8318
K-NN
0.6897 0.8268
SVM
0.6309 0.8376
2、降维方法
用线性和非线性的降维方法处理五组高维数据， 并同时考虑 有监督和无监督的情况(见表3)，基于 SVM 分类器，分析降到不 同维数时的分类精度。 表3 非线性降维 线性降维 无监督 PCA principal component analysis MDS multidimensional scaling LDA(有监督) linear discriminant analysis LLE locally linear embedding Isomap isometric mapping LE laplacian eigenmaps 有监督 SLLE supervised LLE SIsomap supervised Isomap SLE supervised LE
步骤 3：基于公式(9)求解每一个样本点 X i 的权值Wi ，其中Wij 表示第 j 个样 本点在第 i 个样本点中的权重，其中样本 j 是样本 i 的 K 邻域，否则取值为； (注：由于求解过程中矩阵可能为奇异值，故进行了正则化，类似于 LDA 方 法)
2
arg min X i − ∑Wij X j
j →i
(9)
步骤 4：对公式(10)进行特征值分解；
M = (I - W) T (I - W)
（10）
步骤 5：对特征值从小到大排序，选取第 2 到 d + 1 个特征对应的特征向量 即为 d 维嵌入值。(注：由于最小特征值为 0，此时特征向量全为 1，故不 选取)
3.5 SLLE 实验
输入： X 和 label ， X D× N = [ X 1 , X 2 ,⋯ X N ] ,其中 D 为数据维数， N 为样本点数，
1 Sij=Dij2； N
τ (D) = -HSH
（4）
步骤 4：对特征值从大到小排序，选取相应的特征向量作为嵌入数据。
3.3 LDA 实验
输入： X 和 label ， X D× N = [ X 1 , X 2 ,⋯ X N ] ,其中 D 为数据维数， N 为样本点数，
label 为类标签，共有 C 类。即：
C = ( X − X )( X − X ) T
步骤 2：对协方差矩阵做特征分解，对特征值从大到小排序；
（1）
步骤 3：基于公式(2)计算特征值累积贡献率，其中 p 为特征值总数， m 表 示前 m 个最大特征值；