发布时间 : 星期三 文章数据的多流形结构分析 - 图文更新完毕开始阅读bea57c7fa58da0116d174935
马氏距离度量通常应用于基于模型的聚类算法中(比如EM聚类算法)，高斯混合模型的最大似然估计使用马氏距离近似描述后验概率P(Gi|x)[6]。
规范化分割聚类算法(Normalized Cut，Neut)是由Shi和Malik提出的一种图像分割方法，该方法的基本思想是把图像中的每个像素点看作图中的一个顶点，以图像象素点的颜色信息、空间信息和纹理信息来定义其相似度作为顶点间的权重，来构造一个带权重的无向图，在图上建立一个稀疏的关系矩阵，并利用该矩阵的谱信息对图或图像进行划分。具体步骤如下：
步骤l：对含有n个像素的图像，构造一个带权重的无向图G?(V,E,W)。V是图中顶点的集合，E是图中连接顶点i和j的边e(i,j)的集合；W是一个n阶对称矩阵，矩阵中的元素w(i,j)表示边e(i,j)上的权值，它表示顶点i和j之间的相关性。
步骤2：解广义特征值方程：
(D?W)X??DX (25)
这里只需要计算最小的几个特征值及其对应的特征向量；D是对角矩阵，对角线上的元素d(i,j)等于权重矩阵第i行上所有元素的和。
步骤3：利用已经得到的谱的信息将图一分为二。
步骤4：判断分割后的图像是否还需要再次分割，如需要分割，再对分割后的两部分图像分别重复上述过程进行分割。
n阶权重矩阵W中元素w(i,j)，表示顶点i和j之间的相关性。权w(i,j)越大，顶点i和j的相关性越强，分在同一个子集中的可能性越大。任一顶点与自己的相关性最大。权w(i,j)的取值中应包含图像的重要特征信息，可以用高斯核定义权：w(i,j)?exp(?||Q(i)?Q(j)||/2?2)；其中Q(i)是顶点i的空间坐标或其它特征信息。由于图像一般只是局部相关的，为计算方便，当顶点i和j间距离大于r(r< 规范化分割问题最终可以转化为谱问题：(D?W)X??DX 这里，X表示特征向量，该向量中隐含了图像分割的信息。第二小特征值对应的特征向量也称作Fielder向量，经常用来表示像素的类型隶属度信息。这种利用关系矩阵的谱信息进行图像分割的方法，通常也叫做谱分割。规范化分割方法的主要特点有：图像在大多数情况下仅仅是局部相关的，所以最后得到的矩阵牙都是稀疏矩阵。通常只需要几个最小的特征向量就可以对图像进行很好分割，不必求出矩阵的全部特征向量。分割对特征向量的精确度要求不高。大多数情况下，只需要其分量的正、负号就可以分割图像。 通过挖掘流形数据集的局部的和全局的信息，构造高维流形信号曲面，提出了一种基于数据拓扑结构的拓扑距离度量，该距离度量更好的描述了流形的结构，使得同类别数据更加紧凑，不同类别的数据更加疏远。最后基于这种距离度量给出了一种新的流形聚类的算法框架。 4.4.1.2 基于数据拓扑结构的拓扑距离 (A)一维数据的情况 对于两类一维流形数其基于数据拓扑结构的拓扑距离计算如下： (1)数据集中的每个数据点依据其周围的邻居信息，产生不同大小的符合正态分布函数的信号： 1x2p(x)?*exp(?2) (26) ?2??其中，?是由点的k近邻的平均距离决定的，平均距离越大，?就越大，反之 16 亦然。 (2)将所有数据点产生的信号叠加起来，形成一条信号曲线。该信号曲线可以反映数据集合中的拓扑结构信息，纵坐标高的位置对应数据密集的区域，纵坐标低的位置对应数据稀疏的区域，通常稀疏区域也就是数据不同类别的分界区域。 (3)、两两数据点的流形距离表示为两点间信号曲线的几何能量。 (B)二维数据的情况 对于二维数据的情况，以两个同心圆数据集合的聚类为例，来给出我们的拓扑距离算法： (1)数据集中的每个数据点根据其周围的邻域信息，产生了不同大小的符合正态分布函数的信号，信号函数为： 1x2?y2?p(x)?2exp(?) (27) 22?2??其中，?是由点的k近邻的平均距离决定的，平均距离越大，?就越大，反之亦然。系数2?是为了避免局部密度较大而导致信号曲面局部过高的现象。 (2)将所有数据点产生的信号叠加起来，形成一条信号曲面。该信号曲面可以更好的反映数据间的流形特征，纵坐标高的位置对应数据密集的区域，纵坐标低的位置对应数据稀疏的区域，通常稀疏区域也就是数据不同类别的分界区域。 (3)得到数据点间的信号曲线。 (4)两两数据点的流形距离表示为两点间信号曲线的几何能量。两点间的流形距离定义为两点间对应曲线的弧长和平均曲率之和： MainDist(A,B)?Arc(A,B)?Curv(A,B) (28) 同类别数据点B和C间的距离基本没变，而不同类别数据点A和B的距离被表示为一条曲率较大的曲线段，其距离明显变大。 (C)高维数据情况 对于高维数据集合X?{xi|xi?Rm,i?1,2,?,n}，可按照下面的步骤定义点xi与点xj之间的流形距离： (1)首先定义点xi与点xj之间对应的信号曲线Cij是以从点xi到点xj的射线为横轴， k以周围点对曲线Cij横轴的信号影响为纵轴。比如，对于点xi到xj的射线上的点xij，其k纵轴值为xi和xj周围的点产生的符合正态分布的信号在xij处的叠加值。 (2)其次定义点xi与点xj的流形距离为曲线Cij的的弧长和平均曲率之和为： MainDist(xi,xj)?Arc(Cij)?Curv(Cij) (29) 常用的欧式距离只涉及到两个点的空间位置关系，马氏距离在计算两点间距离时使用了数据集的协方差矩阵，考虑了数据集的整体分布。本章节提出的拓扑距离则更多的考虑了数据局部的拓扑结构，在计算两点间距离时加入了局部的拓扑结构信息。 4.4.1.3 基于拓扑距离度量的流形聚类 流形聚类方法主要是寻找数据间的全局或局部的相关性，寻找潜在的流形结构，再根据数据相对流形结构的相似性进行聚类。本文提出的拓扑距离度量很好的描述了流形的结构，使得同类别数据更加紧凑，不同类别的数据更加疏远。 基于拓扑距离，使用Sim(A,B)?exp(?ManiDist(A,B))来定义点A和B的相似度。使用拓扑距离定义的相似度矩阵和欧式距离定义的相似度矩阵。欧式距离定义的右图不同类别数据间的相似度很大，而拓扑距离定义的相似度使得不同类别数据间的相似度变得很小，从中可以看出本章节的距离度量更好的描述了流形的结构，使得同类别数据的距离紧凑，不同类别的数据的距离疏远[8]。 17 本章节基于前一小节提出的拓扑距离，给出一个基于拓扑结构的流形聚类算法框架： 步骤1：数据集中的每个数据点产生符合正态分布函数的信号，将所有数据点产生的信号叠加起来，形成一条信号曲面。 步骤2：借助流形曲线来计算两两数据点间的流形距离： ManiDist(xi,xj)?Arc(Cij)?Curv(Cij) (30) 步骤3：基于拓扑距离构造数据集合的相似度矩阵 再使用规范化分割聚类算法(Neut)进行流形聚类。 Sim(A,B)?exp(?ManiDist(A,B))， 4.4.2运行结果 图中显示了圆台的点云，图中所存在的点构成曲面与平面，平面与曲面之间的点距离近，按问题三中低秩稀疏子空间聚类的方法来分类，分类的结果聚类错误率较高，分类不明显且效果不好，采取基于拓扑距离度量的流形聚类这一方法，能很好的描述了流形的结构，使得同类别数据更加紧凑，不同类别的数据更加疏远，图5为分类结果，点按照其所在的面分开，即圆台按照圆台的顶、底、侧面分成三类，红色部分代表一类，蓝色部分代表一类，绿色部分代表一类。 图5 (a)的分类结果图 对于图(b)，问题给出是机器工件外部边缘轮廓的图像，需根据轮廓线中不同的直线和圆弧分类。根据上节算法，对所给图像分别分成两类、三类、四类，结果如下： 18 图6 (b)的分为两类结果图 图6 (b)的分为三类结果图 图6 (b)的分为四类结果图 注：不同颜色代表不同的类。 19