发布时间 : 星期六 文章数据的多流形结构分析 - 图文更新完毕开始阅读bea57c7fa58da0116d174935
对于图1(b)的聚类结果，用同样的计算方法，得到该组数据的聚类缺失率为0.087，这说明用稀疏子空间聚类的方法对数据进行分类的效果比较好。
对于图1(c)的聚类结果，聚类缺失率为0.073，这说明用基于多流形的聚类方法对这组数据进行分类达到的效果比较好。
对于图1(d)的聚类结果，聚类缺失率为0.071，这说明用稀疏子空间聚类的方法对数据进行分类的效果比较好。 4.3 问题三模型的建立与求解 4.3.1 问题三模型的建立
4.3.1.1 低秩稀疏子空间聚类方法
针对问题三图2(a)提出了低秩稀疏子空间聚类算法。本算法是在稀疏子空间聚类和低秩表示的基础上，在聚类的过程中可以对高维数据进行降维，同时在低维空间中利用稀疏表示和低秩表示对数据进行聚类．在运动分割和人脸聚类上，该算法都具有很好的聚类性能。
稀疏子空间聚类算法和低秩表示，文中将数据映射到一个低维的空间中，同时在这个低维空间中寻求数据的低秩稀疏系数。令P?Rt?D为一个线性变换矩阵，它将数据从原始空间RD映射到一个维数为t的空间中．通过目标函数的最小化，可以同时得到变换矩阵和数据集的低秩稀疏系数：
P*,C*?minJ(P,C,Y)
??P,Cs.t. PPT?I,diag(C)?0 (9)
其中，J(P,C,Y)??1C*??2C1??1PY?PYCF??2Y?PTPY22F (10)
(10)式的第一项为求取数据集的低秩系数；第二项为求取数据集的稀疏系数；第三项的主要目的是去除噪声影响；最后一项是似于PCA的正则项，主要目的是保证映射变换不能过多丢失一些原始空间的信息；?1和?2为非负常数。另外，要求P正交并且归一化,这样就避免了解的退化，并且保证优化方法的计算效率。以注意到，(10)式是能够进行扩展的，这样就可以对位于仿射子空间中的数据进行处理．可以对优化问题(9)增加一个约束条件得到：
P*,C*?minJ(P,C,Y)
??P,Cs.t. PPT?I,CT1?1,diag(C)?0 (11)
由于是实际应用中的子空间的聚类，受实际条件的制约，图(a)是视觉重建，所以关键环节是特征的提取，我们通过低秩稀疏子空间聚类的算法可以将十字分为两类，分别为“横”和“竖”两类。
针对问题三图2(b)，我们使用拉普拉斯特征映射(Laplacian Eigenmaps)降维的方法，LE假设每一点只与它距离最近的一些点相似，再远一些的数据相似程度为0，降维后相近的点尽可能保持相近。
4.3.1.2 Laplacian Eigenmaps降维法
Laplacian Eigenmaps降维的方法，首先要构建图的权值矩阵。构建方法为： 步骤1
1) 通过设置一个阈值，相似度在阈值以下的都直接置为零，这相当于在一个领域内考虑局部性；
2) 对每个点选取k个最接近的点作为邻居，与其他的点的相似性则置为零。 3) 全连通。 步骤2
12
LE把降维考虑为一种高维到低维的映射，则一个好的映射应该使连通的点靠的更近。设xi映射后的点为yi，则LE的目标就是最小化以下函数：
?(y?y)W2ijiji,ji,jiij (12)
对目标函数进行整理
?(yi?yj)2Wij??(yi2?y2j?2yiyj)Wij??yi2Dii??y2jDjj?2?yiyjWij?2yTLy (13)
ji,j其中，L=D-W，L就叫做Laplacian Matrix。
Dii??Wij (14)
j于是，最小化问题等效为：
argminyTLy (15) yTDy?1 (16)
因此，对于y，我们将特征值从小到大排序后，选择第二小的特征值到第m+1小的特征值对应的特征向量（共m个），组成一个n?m的矩阵，矩阵的每一行就是原来的数据降维后得到的m维特征。原本我们只知道数据与数据之间的相似程度，结果把降维后的特征求出来这里的特征值。如果仅有一个特征值为0，那么这个图一定是全通的。
通过降维的方法把(b)图的297维降到100维，这个维度是在不失去很多数据，又可以简化算法复杂度的基础上，得到的最终维度，降维后得到稀疏矩阵，然后接下来的处理的方法和问题二的一样。
针对问题三图2(c)，同样使用拉普拉斯特征映射降维的方法将3c.mat中的数据20幅两个人在不同光照下的人脸图像分成两类（X变量的每一列为拉成向量的一幅人脸图像），使用相同的降维方法，将2000维数据降到100维，再通过谱聚类的算法将这20幅人脸分成两类，通过降维的方法我们能够得到很好的结果。 4.3.2 运行结果
通过运行程序，图(a)的数据分成了两类，分类结果如下图所示：
图4 (a)的分类结果图
注：其中红色的“横”为一类，蓝色的“竖”为一类。
通过MATLAB软件，运行程序，图(b)的数据分成了三类，分类结果如下表所示：
13
表2 问题三图（b)的分类结果
编号 1 2 3 4 5 6 7 8 9 类别 2 2 2 2 2 2 2 2 2 编号 21 22 23 24 25 26 27 28 29 类别 2 2 2 2 2 2 2 2 2 编号 41 42 43 44 45 46 47 48 49 类别 2 2 2 2 2 2 2 2 2 编号 61 62 63 64 65 66 67 68 69 类别 2 2 2 2 2 2 2 2 2 编号 81 类别 编号 类别 编号 类别 编号 类别 编号 类别 编号 类别 编号 类别 编号 类别 编号 类别 编号 类别 编号 类别 2 101 2 121 3 141 3 161 3 181 3 201 3 221 1 241 1 261 1 281 1 20 2 40 2 60 2 80 2 1082 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 101010101010101011111111111111111111122 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 121212121212121213131313131313131313142 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 141414141414141415151515151515151515162 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 3 3 3 3 3 3 3 3 3 3 3 3 3 1 3 3 3 3 3 161616161616161617171717171717171717182 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 181818181818181819191919191919191919202 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 202020202020202021212121212121212121222 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 3 3 3 3 3 3 3 3 3 3 3 3 3 1 1 1 1 1 1 222222222222222223232323232323232323242 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1 1 1 1 1 1 1 3 1 3 1 1 1 1 3 1 3 1 242424242424242425252525252525252525262 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1 1 1 1 1 1 1 1 3 3 1 1 1 1 1 1 1 1 262626262626262627272727272727272727282 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1 1 1 1 1 3 1 3 1 3 1 1 1 1 1 1 1 1 28282828282828282929292929292929 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 注：表2中共分为三类，其中1表示第一类，2表示第二类，3表示第三类。
14
10 2 30 2 50 2 70 2 11 2 31 2 51 2 71 2 12 2 32 2 52 2 72 2 13 2 33 2 53 2 73 2 14 2 34 2 54 2 74 2 15 2 35 2 55 2 75 2 16 2 36 2 56 2 76 2 17 2 37 2 57 2 77 2 18 2 38 2 58 2 78 2 19 2 39 2 59 2 79 2
图(c)的数据分成了两类，分类结果如下表所示：
表3 问题三图(c)的分类结果
编号 类别 1 1 2 1 3 1 4 1 5 1 6 2 7 2 8 2 9 2 10 11 12 13 14 15 16 17 18 19 20 2 1 1 1 1 1 2 2 2 1 2 注：表3中数据共分为2类，其中1表示第一类，2表示第二类。
4.4 问题四模型的建立与求解 4.4.1问题四模型的建立 4.4.1.1规范化分割聚类算法
许多机器学习和模式识别方法都依赖于距离度量。用于聚类的K-means方法等的性能都需要一个合适的距离度量。距离度量的选取必须要与数据特征的差异和不同尺度相对应，不同的距离函数可能使得距离结果差距很大。通常使用Minkowski度量来定义两个数据向量的距离为：
dp(xi,xj)?(?||xi,s?xj,s||p)1/p (17)
s?1dim特别的，p=1意味着乌距离或者马氏距离，p=2意味着几距离或者欧式距离。理论上，距离函数必须满足一下条件：
d(x,x)?0,?x?X0?d(x,x),?x?X (18) d(x,y)?d(y,x)距离度量还需要满足三角不等式：
d(x,z)?d(x,y)?d(y,z) (19)
p??的MinkoWSki不等式就是最大度量：d(xi,xj)?max|xi,s?xj,s|以上距离度量
1?s?dim是传递不变的，但是对于尺度变化不能保持不变。达到尺度不变的一般策略是对数据集进行预处理归一化。尺度不变的距离度量有：
Canberra度量：
dim|x?xi,sj,s| (20) d(xi,xj)??|x|?|x|s?1i,sj,s余弦相似性：
d(xi,xj)?xixj||xi||?|xj,s| (21)
另一个修正欧式距离使其保持尺度不变的方式是Mahalanobis距离：
d(xi,xj)?(xi?xj)T??1(xi?xj) (22) 其中是整个数据集的协方差矩阵：
1N(xi?x)(xi?x)T (23) ?(X)?N?i?1或者某个数据类别的协方差矩阵：
1j(xi?x)(xi?x)T (24) ?(Gj)?|G|?ji?1
N15