发布时间 : 星期三 文章数据的多流形结构分析 - 图文更新完毕开始阅读bea57c7fa58da0116d174935
4.2 问题二模型的建立与求解
4.2.1 稀疏子空间聚类与低秩子空间聚类
过去的几十年人们见证了数据的爆炸式增长，这对于数据的处理工作提出了巨大的挑战，特别是这些数据集通常都是高维数据．数据的高维特性不仅增加了计算时间，而且由于噪声和环境空间降低了算法的性能．实际上，这些数据的内在尺度往往比实际空间中小得多，这就促使人们运用一些技术发现高维数据的低维表示，比如低秩近似和稀疏表示等．实际上，在许多问题中，高维空间中的数据往往可以用低维子空间进行表示。
计算过程是，首先通过对角稀疏矩阵，求得其相似矩阵，然后对这个相似矩阵进行归一化，然后通过谱聚类的三种聚类方法Unnormalized method、Random walk、Normalized symmetric进行聚类，最后再用K-means的方法对其进行最终的聚类，聚类结束后再对分类结果的好坏进行判断，用聚类错误率作为评判聚类好坏的标准。
稀疏子空间聚类(SSC)[2]，每一个数据点可以表示为其他数据点的稀疏线性组合，通过这些稀疏系数构造亲和矩阵进行子空间聚类。也就是说，给定一个数据集X，希望找到一个系数矩阵C，满足X=XC并且diag(c)=0。可以通过求解(2)式得到解。
minc1
s.t.X?XC,diag(c)?0 (2)
当数据集被噪声G污染时，SSC算法假设每个数据点可以表示为X=XC+G，可以通过求解凸优化问题(3)得到解。
minc1??2GF
2s.t.X?XC?G,diag(c)?0 (3)
低秩表示(LRR)算法[3]和稀疏子空间聚类算法非常类似，区别在于LRR算法的目标是寻找数据的低秩表示，而SSC算法在于寻找数据的稀疏表示。LRR通过求解凸优化问题(4)得到解。
minC*
s.t.X?XC (4)
当数据集被噪声G污染时，LRR通过求解凸优化问题(5)得到解．
minC*??G
s.t.X?XC?G (5)
最后，通过得到的稀疏矩阵（利用SSC或者LRR），构造亲和矩阵C+CT，在这个亲和矩阵上利用谱聚类算法，就可以得到最终的聚类结果[4]。 4.2.2 问题二模型的建立
MATLAB程序流程
读取附件中的数据 开始 构造稀疏矩阵 构建点的邻接距离向量矩阵
谱聚类 8
图1(a)为两条交点不在原点且互相垂直的两条直线，将其分为两类，通过上面的方法，用MATLAB进行编程得到很好的分类结果，将两条线各自分为一类。图1(b)为一个平面和两条直线，这是一个不满足独立子空间的关系的例子，将其分为三类。在MATLAB程序中，(a)、(b)图都是通过改变正则化参数，改变稀疏矩阵，从而来得到更好的分类效果，同类样本的相似度构造的较大，不同类的较小，这类方法一般能得到正确分类结果。
针对问题二图(c)和(d)，因为图(c)是从图(a)的两条直线变为了两条不相交的二次曲线，图(d)是两条螺旋线，基于欧氏距离的相似性度量不能完全反映数据聚类复杂的空间分布特性的问题，提出了一种基于流形距离核的谱聚类算法．它能充分挖掘数据集中的内在结构信息，较好地反映局部和全局一致性，并且可以很好地防止噪声点的影响。它可以增大位于同一流形结构的数据对间的相似度，并且减小位于不同流形结构的数据对间的相似度，从而解决了复杂数据的空间分布特性。
流形上的线段长度用下面的公式(6)来计算：
L(x,y)?e?d?x,y??1 (6)
其中，d(x,y)为数据点x和y间的欧氏距离；?称为伸缩因子，可以用来描述聚类的全局一致性，通过调节伸缩因子?来放大或缩短两点间线段长度。
V,E?中的顶点V，边集合E流形距离测度：将数据点看作是一个加权无向图G??表示的是在每一对数据点间定义的连接权值。令p?Vl表示图上长度为l?p?1的连接点p1与pp之间的路径，其中边(pk,pk?1)?E，1?k?l。令pi,j表示连接数据点对?xi,xj?的所有路径的集合(1?i,j?n)，xi与xj之间的流形距离为：
Di?,j?1?2ln(1?d(x,x)) (7) spij2dsp(xi,xj)?minp?pij??e?k?1p?1d(pk,pk?1)?1 (8)
?其中，dsp?xi,xj?是图G上节点xi和xj之间的最短路径距离。d?pk,pk?1?是图G上节点xi到xj最短路径上任意相邻两点的欧氏距离。不难看出，该距离的定义满足距离测度定义的4个约束条件：
自反性：Di?,j?0，当且仅当xi?xj；
?对称性：Di??D,jj,i；
非负性：Di?,j?0；
??三角不等式：Di??D?D,ji,kk,j．
该距离测度可以度量流形上的最短路径，能够很好地反映数据集内在的流形结构，使得位于同一流形上的2点可以用许多短边相连，而位于不同流形上的2点则需要用穿过低密度区域的长边相连，最终达到放大位于不同流形上的数据点间距离，缩短位于同一流形上的数据点间距离的目的．从上面的定义可以看出，该距离测度可以反映数据的局部密度特征。 4.2.3 运行结果
图1(a)分类结果如下图所示：
9
3.532.521.510.50-0.5-1-1-0.500.511.52图1 (a)的分类结果图
注：其中红色的线为一类，蓝色的线为一类。 图1(b)分类结果如下图所示：
10.50-0.5-110.50-0.5-1-1-0.50.501图2 (b)的分类结果图
注：其中红色的线为一类，蓝色的线为一类，绿色的平面为一类。
图1(c)为两条不相交的二次曲线，它是属于多流形聚类的问题，通过MATLAB编程，我们将其分为两类，分类结果如图3所示：
10
0.80.70.60.50.40.30.20.10-0.1-0.8-0.6-0.4-0.200.20.40.6图3 (c)的分类结果图
注：其中红色的曲线为一类，蓝色的曲线为一类。
图1(d)为两条相交的螺旋线，这两条螺旋线也是属于多流形聚类的问题，将其分为两类，结果如图4所示：
图3 (d)的分类结果图
注：其中红色的螺旋线为一类，蓝色的螺旋线为一类。 4.2.4 结果分析
我们采用聚类错误率来评价聚类算法的性能：
聚类缺失的样本数聚类缺失率?
总样本数对于图1(a)的聚类结果，通过计算，得到数据的聚类缺失率为0.053，错误率比较低，这说明用稀疏子空间聚类的方法对数据进行分类是有效的。
11