发布时间 : 星期三 文章数据的多流形结构分析 - 图文更新完毕开始阅读bea57c7fa58da0116d174935
一、问题的重述
1.1 问题的背景
我们已经进入了一个信息爆炸的时代，海量的数据不断产生，迫切需要对这些大数据进行有效的分析，以至数据的分析和处理方法成为了诸多问题成功解决的关键，涌现出了大量的数据分析方法。几何结构分析是进行数据处理的重要基础,已经被广泛应用在人脸识别、手写体数字识别、图像分类、等模式识别和数据分类问题，以及图象分割、运动分割等计算机视觉问题（人脸识别、图像分类、运动分割等实例见下文）中。更一般地，对于高维数据的相关性分析、聚类分析等基本问题，结构分析也格外重要。 1.2 问题的提出
有些实际问题的数据并不符合混合子空间结构的假设，所以假设数据的结构为混合多流形更具有一般性。由于混合流形不全是子空间的情况，数据往往具有更复杂的结构，分析这种数据具有更大的挑战性。基于谱聚类的方法仍然是处理该类问题的流行方法。 1.3 本文所需解决的问题
(1) 当子空间独立时，子空间聚类问题相对容易。附件一中1.mat中有一组高维数据（.mat所存矩阵的每列为一个数据点，以下各题均如此），它采样于两个独立的子空间。我们需要将该组数据分成两类。
(2) 附件二中是四个低维空间中的子空间聚类问题和多流形聚类问题，如图1所示。图1(a)为两条交点不在原点且互相垂直的两条直线，需要将其分为两类；图1(b)为一个平面和两条直线，这是一个不满足独立子空间的关系的例子，要求我们将其分为三类。图1(c)为两条不相交的二次曲线，需将其分为两类。图1(d)为两条相交的螺旋线，也是需要将其分为两类。
(3) 问题三需要我们解决以下三个实际应用中的子空间聚类问题，数据见附件三 (a) 受实际条件的制约，在工业测量中往往需要非接触测量的方式，视觉重建是一类重要的非接触测量方法。特征提取是视觉重建的一个关键环节，如图2(a)所示，其中十字便是特征提取环节中处理得到的，十字上的点的位置信息已经提取出来，为了确定十字的中心位置，一个可行的方法是先将十字中的点按照 “横”和“竖”分两类。要求我们使用适当的方法将图2(a)中十字上的点分成两类。
(b) 运动分割是将视频中有着不同运动的物体分开，是动态场景的理解和重构中是不可缺少的一步。基于特征点轨迹的方法是重要的一类运动分割方法，该方法首先利用标准的追踪方法提取视频中不同运动物体的特征点轨迹，之后把场景中不同运动对应的不同特征点轨迹分割出来。已经有文献指出同一运动的特征点轨迹在同一个线性流形上。图2(b)显示了视频中的一帧，有三个不同运动的特征点轨迹被提取出来保存在了3b.mat文件中，我们所需要做的就是，使用适当方法将这些特征点轨迹分成三类。
(c) 3c.mat中的数据为两个人在不同光照下的人脸图像共20幅（X变量的每一列为拉成向量的一幅人脸图像），需要将这20幅图像分成两类。
(4) 请作答如下两个实际应用中的多流形聚类问题
图3(a)分别显示了圆台的点云，要求我们将这些点按照其所在的面分开（即圆台按照圆台的顶、底、侧面分成三类）。
图3(b)是机器工件外部边缘轮廓的图像，我们需要将轮廓线中不同的直线和圆弧分类。
4
二、符号说明
符号 d xi1 xi2
符号说明
两点之间欧氏距离
xi1表示第一个点的第i维坐标
xi2表示第二个点的第i维坐标
?
伸缩因子
节点xi和xj之间的最短路径距离
连接顶点
顶点i和j之间的相关性
Minkowski度量来定义两个数据向量的距离
dsp?xi,xj?
e?i,j? w(i,j) dp(xi,xj)
三、问题分析
3.1 问题一
独立子空间的聚类问题相对容易，采用k-means算法对附件一中的数据进行聚类，这组多维数据是属于两个独立的子空间，我们利用MATLAB软件将这组高维数据分成了两类，并用表格的形式表示出第一类用1表示，第二类用2表示。 3.2 问题二
问题二的数据为四个二维数据，涉及到的问题是子空间聚类问题和多流形子空间聚类问题，采用稀疏子空间聚类的方法对(a)图和(b)图进行聚类，用稀疏矩阵表示，然后建立邻接矩阵，最后进行谱聚类分析，然后通过改变稀疏矩阵的正则参数，来调整分类的效果，利用聚类错误率来辨别聚类效果的优劣，最终将其分为两类，每条直线分别表示一类。对于图(c)，(d)，因为欧氏距离的相似性度量不能完全反映数据聚类复杂的空间分布特性的问题。(c)图为两条不相交的二次曲线，因欧氏距离的相似性度量不能完全反映这种空间分布特性，通过欧式距离求得流形距离，根椐流形距离核的相似性度量构造相似性矩阵，再求得拉普拉斯矩阵，继而得到拉普拉斯矩阵的最大特征值对应的特征向量，对其构建矩阵并单位化，最后采用K-means算法将其分为2类。图(d)为两条相交的螺旋线，同样采用(c)的算法，将其分为两类。 3.3 问题三
解决以下三个实际应用中的子空间聚类问题，对于图(a)采用低秩稀疏子空间聚类方法，将数据映射到一个低维的隐空间中，同时在这个低维空间中寻求数据的低秩稀疏系数，优化线性变换矩阵得到最优解，最后利用谱聚类算法，将其分为了“横”和“竖”两类。对于图(b)与(c)，数据的维度较高，考虑到计算的复杂度与时间，以及数据不丢失的情况下，对数据进行降低维数。对于图(b)运动分割，基于特征点的轨迹，使用拉普拉斯特征映射降低维数的方法，将场景中不同运动对应的不同特征点轨迹分割出来，使得同一运动的特征点轨迹在同一个线性流形上，之后采用(a)中的算法，将此特征点轨迹分成三类，并用表格表示分类结果。对于(c)问题，也采用(b)的方法，降低维数到100维，将这20幅图像分成两类。 3.4 问题四
针对问题四，采取基于拓扑距离度量的流形聚类的方法，对图(a)进行聚类，使数据
5
集中的每个数据点产生符合正态分布函数的信号，将所有数据点产生的信号叠加起来，形成一条信号曲面，借助流形曲线来计算两两数据点间的流形距离，即点与点的流形距离为曲线的的弧长和平均曲率之和，基于拓扑距离构造数据集合的相似度矩阵，再使用规范化分割聚类算法(Neut)进行流形聚类，根据图像数据构造一个带权重的无向图，计算最小的几个特征值及其对应的特征向量。利用已经得到的谱的信息将图一分为二。判断分割后的图像是否还需要再次分割，如需要分割，再对分割后的两部分图像分别重复上述过程进行分割。最后将圆台分成了三类，分别是圆台的顶、底、侧面。(b)是机器工件外部边缘轮廓的图像，采用(a)中方法，将轮廓线分别聚类成两类、三类与四类，并计算每种分类的类间偏差平方和和类内偏差平方和之间的差的绝对值，用来评价分类结果的优劣，绝对值越小分类效果越好。
四、模型的建立与求解
4.1 问题一模型的建立与求解 4.1.1 K-means算法
K-means算法是最简单的一种聚类算法。算法的目的是使各个样本与所在类均值的误差平方和达到最小（这也是评价K-means算法最后聚类效果的评价标准）。
K-means算法的一般步骤：
1) 初始化。先随机选取K个对象作为初始的聚类中心。然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。
2) 进行迭代。聚类中心以及分配给它们的对象就代表一个聚类。一旦全部对象都被分配了，每个聚类的聚类中心会根据聚类中现有的对象被重新计算。
3) 更新聚类中心。这个过程将不断重复直到满足某个终止条件。终止条件可以是以下任何一个：
i) 没有（或最小数目）对象被重新分配给不同的聚类。 ii) 没有（或最小数目）聚类中心再发生变化。 iii) 误差平方和局部最小。
在这里我们用的是欧式距离来描述这两个点之间的远近，通过距离来反映他们的相似程度，距离越近，相似程度越高[1]。
d?sqrt(?(xi1?xi2)2) i?1,2,?,n (1) 4.1.2 模型的求解
我们使用了K-means聚类算法对附件一中的高维数据进行分类，得出如下的结果：
6
表1 独立子空间聚类结果
编号 类别 编号 类别 编号 类别 编号 类别 编号 类别 编号 类别 编号 类别 编号 类别 编号 类别 编号 类别 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 11 12 13 14 15 16 17 18 19 20 1 1 1 1 1 1 1 1 1 1 1 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 100 2 120 2 140 2 160 1 180 1 200 1 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 2 101 2 121 2 141 1 161 1 181 1
2 102 2 122 2 142 1 162 1 182 1 2 103 2 123 2 143 1 163 1 183 1 2 104 2 124 2 144 1 164 1 184 1 2 105 2 125 2 145 1 165 1 185 1 2 106 2 126 2 146 1 166 1 186 1 2 107 2 127 2 147 1 167 1 187 1 2 108 2 128 2 148 1 168 1 188 1 2 109 2 129 2 149 1 169 1 189 1 2 110 2 130 2 150 1 170 1 190 1 2 111 2 131 2 151 1 171 1 191 1 2 112 2 132 2 152 1 172 1 192 1 2 113 2 133 2 153 1 173 1 193 1 2 114 2 134 2 154 1 174 1 194 1 2 115 2 135 2 155 1 175 1 195 1 2 116 2 136 2 156 1 176 1 196 1 2 117 2 137 2 157 1 177 1 197 1 2 118 2 138 2 158 1 178 1 198 1 2 119 2 139 2 159 1 179 1 199 1 注：图中的类别1表示第一类，2表示第二类。 7