Sparse subspace clustering:Algorithm,theory,and Application
稀疏子空间聚类（SSC）的算法，理论和应用
参考文献：
1、E. Elhamifar and R. Vidal. Sparse subspace clustering: Algorithm,theory,and Application. IEEE Transactions on Pattern Analysis and Machine Intelligence,2013
2、E. Elhamifar and R. Vidal. Sparse subspace clustering. In CVPR, 2009
2013年的这篇论文写得比09年那篇容易懂一些，讨论和实验也更详细。2013年的这篇可以看成是09那篇会议的扩展版。
一、算法
数据没有损坏，求解模型（5）获得矩阵C：
数据有损坏（noise and sparse outlying entries)，求解模型（13）获得矩阵C：
仿射子空间模型：
二、理论
1、independent子空间
设rank(Yi)=di，Yi表示从第i个子空间Si抽取的Ni个样本构成的矩阵，di 表示Si的维数。论文的定理1表明，模型（5）的解C*是一个块对角矩阵，属于同一个子空间的数据间的cij可能非零，不属于同一个子空间的数据间的cij=0.
2、disjoint子空间
对于disjoint子空间，除了满足条件rank(Yi)=di外，还需要满足公式（21）：
则可获得与independent子空间下类似的结论：
三、应用
segmenting multiple motionsin videos: Hopkins 155 dataset
clustering images of human faces: Extended Yale B dataset
通过计算每对子空间的最小主角(principal angle）小于一给定值的比例，每对子空间中的数据的k近邻至少有一个在其他子空间的比例，可以帮助我们更好地知道两个数据库子空间聚类的挑战和各个算法的性能差别。Hopkins 155 dataset：各个子空间间的主角很小；Extended Yale B dataset：不但主角小，而且一个子空间的数据点跟其他的子空间很靠近。
思考：
1、论文提到，SSC算法不需要知道每个子空间的基，事先也不知道每个数据属于哪个子空间，甚至每个子空间的数据个数可以是任意的。
2、对于independent子空间和disjoint子空间，由于模型的最优解是块对角矩阵，可以保证不同子空间没有联系，因此可以通过计算拉普拉斯矩阵的eigenspectrum 来确定子空间的个数。从实验来看，对于子空间存在噪声等更复杂的实际情况，计算实际数据的非零奇异值个数，也能大概知道子空间的内在低维数。
《空间分析与应用》复习题 一、名词解释 1、空间分析：是以地理事物的空间位置和形态特征为基础，以空间数据运算、空间数据与属性数据的综合运算为特征，提取与产生新的空间信息的技术和过程。 2、空间聚类分析：是将地理空间实体或地理单元集合依照某种相似性度量原则划分为若干个类似地理空间实体或地理单元组成的多个类或簇的过程。类中实体或单元彼此间具有较高相似性，类间实体或单元具有较大差异性。 3、坡长：是指在地面上一点沿水流方向到其流向起点间的最大地面距离在水平面上的投影长度，是水土保持的重要因子，水力侵蚀的强度依据坡长来决定，坡面越长，汇集的流量越大，侵蚀力就越强。 4、平面曲率：是过地面上某点的水平面沿水平方向切地形表面所得到曲线在该点的曲率值，它描述的是地表曲面沿水平方向的弯曲、变化情况。 5、地表粗糙度：反映地表的起伏变化和侵蚀程度的指标, 一般定义为地表单元的曲面面积与其在水平面上的投影面积之比，公式: R = S曲面/S水平，实际应用中, 当分析窗口为3*3时, 可采用近似公式求解: R = 1/cos(S)，其中 S-坡度。 6、地理空间分析：是以地理事物的空间位置和形态特征为基础，以空间数据运算、空间数据与属性数据的综合运算为特征，提取与产生新的空间信息的技术和过程。 7、地理空间认知：是指在在日常生活中，人类如何逐步理解地理空间，进行地理分析和决策，主要包括地理信息的知觉、编码、存储、以及和解码等一系列心理过程。 8、图论中的路径：一个图的路径是顶点vi和边ei的交替序列μ= v0e1v1e2…vn-1envn如果v0 = vn，称路径是闭合的，否则称为开的；路径中边的数据称为路径的长；若路径μ的边e1，e2…en均不同，则μ称为链；若它的所有顶点都不同，称为路；一条闭合的路称为回路。 9、增广链：设f是一个可行流，μ是从vs到vt的一条链，若μ满足前向弧都是非饱和弧,反向弧都是都是非零流弧,则称μ是（可行流f的）一条增广链。 10、坡度变率：是地面坡度在微分空间的变化率，是依据坡度的求算原理，在所提取的坡度值的基础上对地面每一点再求一次坡度，即坡度之坡度（Slope of Slope,简称SOS）。坡度是地面高程的变化率的求解，因此，坡度变率表征了地面高程相对于水平面变化的二阶导数，在一定程度上可以很好的反映剖面曲率信息。 11、地表切割深度：地面某点的邻域范围的平均高程与该点邻域范围内的最小高程的差。公式:Di = Hmean –Hmin 。其作用是反映地表被侵蚀切割的情况, 是研究水土流失及地表侵蚀发育状况的重要参考指标。 12、空间聚类分析的概念：是将地理空间实体或地理单元集合依照某种相似性度量原则划分为若干个类似地理空间实体或地理单元组成的多个类或簇的过程。类中实体或单元彼此间具有较高相似性，类间实体或单元具有较大差异性。 13、图论中的树：设T是一个（p,q）图，若T是一个树，则q=p-1；设T是一棵树，如在T中的任何两个不相邻的顶点连一条边e，则T+e恰有一条回路；设G是一个（p,q）图，若G是联通的，且q=p-1，则G 是一棵树 14、图论中的生成树：如果T是连通图G的一个生成子图而且是一棵树，则称T是G的一颗生成树，或称支撑树；一个图的生成树是联通这个图全部顶点的最少边的集合，是极小连通图。
空间聚类的研究现状及其应用＊ 戴晓燕1 过仲阳1 李勤奋2 吴健平1 (1华东师范大学教育部地球信息科学实验室 上海 200062) (2上海市地质调查研究院 上海 200072) 摘 要 作为空间数据挖掘的一种重要手段,空间聚类目前已在许多领域得到了应用。文章在对已有空间聚类分析方法概括和总结的基础上,结合国家卫星气象中心高分辨率有限区域分析预报系统产品中的数值格点预报(HLAFS)值,运用K-均值法对影响青藏高原上中尺度对流系统(MCS)移动的散度场进行了研究,得到了一些有意义的结论。 关键词 空间聚类 K-均值法 散度 1 前言 随着GPS、GI S和遥感技术的应用和发展,大量的与空间有关的数据正在快速增长。然而,尽管数据库技术可以实现对空间数据的输入、编辑、统计分析以及查询处理,但是无法发现隐藏在这些大型数据库中有价值的模式和模型。而空间数据挖掘可以提取空间数据库中隐含的知识、空间关系或其他有意义的模式等[1]。这些模式的挖掘主要包括特征规则、差异规则、关联规则、分类规则及聚类规则等,特别是聚类规则,在空间数据的特征提取中起到了极其重要的作用。 空间聚类是指将数据对象集分组成为由类似的对象组成的簇,这样在同一簇中的对象之间具有较高的相似度,而不同簇中的对象差别较大,即相异度较大。作为一种非监督学习方法,空间聚类不依赖于预先定义的类和带类标号的训练实例。由于空间数据库中包含了大量与空间有关的数据,这些数据来自不同的应用领域。例如,土地利用、居住类型的空间分布、商业区位分布等。因此,根据数据库中的数据,运用空间聚类来提取不同领域的分布特征,是空间数据挖掘的一个重要部分。 空间聚类方法通常可以分为四大类:划分法、层次法、基于密度的方法和基于网格的方法。算法的选择取决于应用目的,例如商业区位分析要求距离总和最小,通常用K-均值法或K-中心点法;而对于栅格数据分析和图像识别,基于密度的算法更合适。此外,算法的速度、聚类质量以及数据的特征,包括数据的维数、噪声的数量等因素都影响到算法的选择[2]。 本文在对已有空间聚类分析方法概括和总结的基础上,结合国家卫星气象中心高分辨率有限区域分析预报系统产品中的数值格点预报(HLAFS)值,运用K-均值法对影响青藏高原上中尺度对流系统(MCS)移动的散度场进行了研究,得到了一些有意义的结论。 2 划分法 设在d维空间中,给定n个数据对象的集合D 和参数K,运用划分法进行聚类时,首先将数据对象分成K个簇,使得每个对象对于簇中心或簇分布的偏离总和最小[2]。聚类过程中,通常用相似度函数来计算某个点的偏离。常用的划分方法有K-均值(K-means)法和K-中心(K-medoids)法,但它们仅适合中、小型数据库的情形。为了获取大型数据库中数据的聚类体,人们对上述方法进行了改进,提出了K-原型法(K-prototypes method)、期望最大法EM(Expectation Maximization)、基于随机搜索的方法(ClAR ANS)等。 K-均值法[3]根据簇中数据对象的平均值来计算 ——————————————— ＊基金项目:国家自然科学基金资助。(资助号: 40371080) 收稿日期:2003-7-11 第一作者简介:戴晓燕,女,1979年生,华东师范大学 地理系硕士研究生,主要从事空间数 据挖掘的研究。 · 41 · 2003年第4期 上海地质 Shanghai Geology
【子空间聚类】Sparse Subspace Clustering(SSC) Algorithm Symbol definition： is n linear subspace of . is the dimentsion of . is N noise-free data points. is a rank- matrix, represent (>) points that lie in . is a unknown permutation matrix. SSC Algorithm: Step 1: Solve the sparse optimization program ①Uncorrupted data ②Corrupted data ps: E corresponds to a matrix of sparse outlying entries, and Z is a noise matrix. Step 2: Normalize the columns of C as . ps: max norm : .
Step 3: Form a similarity grahp with N nodes wegiths on the edges between the nodes by . ps: Step: Use spectral clustering to the similarity graph. Output: . Subspace-Sparse Recovery Theory Definition: ① ps: is said to be independent. ② ③Principle angle between and
肤色在各颜色空间的聚类分析 摘要肤色是人体表面最显著的特征之一。对不同肤色在RGB、YCbCr颜色空间内和同一肤色在不同亮度环境下的聚类情况进行深入的分析研究,发现肤色在YCbCr空间内聚类效果更好,更适合做肤色分割。然后在此基础上对黑色肤色、黄色肤色及白色肤色在YCbCr空间内进行肤色分割,达到较好的分割效果。 关键词肤色;颜色空间;肤色分割;YCbCr空间 肤色是人体表面最显著的特征之一,由于它对姿势、旋转、表情等变化不敏感,因此将人体的肤色特征应用于人脸检测与识别、表情识别、手势识别具有很大的优势,所以肤色特征是人脸识别、表情识别、与手势识别中最为常用的分割方法。然而,若要利用肤色进行分割,我们首先应该对肤色以及肤色的聚类情况进行分析。 世界上的人种主要有三种,即尼格罗—澳大利亚人种(黑色皮肤),蒙古人种(黄色皮肤),欧罗巴人种(白色皮肤)。尽管人的肤色因人种的不同而不同,呈现出不同的颜色,但是有学者指出:排除亮度、周围环境等对肤色的影响后,皮肤的色调基本一致。本文对在不同环境下的不同肤色进行取样,然后分别在RGB、YCbCr颜色空间进行统计,从而对比分析肤色在各颜色空间聚类的情况。 1肤色在各颜色空间的聚类比较 1.1不同肤色在RGB和YCbCr颜色空间上的分布 图1—图2给出了黄色、黑色和白色肤色分别在RGB、YCbcr空间的分布情况。 由图1—图2可以得出,不同肤色在RGB、YCbCr空间的分布有如下特征: 1)不同肤色在不同颜色空间均分布在很小的范围内。 2)不同肤色在不同颜色空间内不是随机分布,而是在某固定区域呈聚类分布。 3)不同肤色在YCbCr空间内分布的聚类状态要好于在RGB空间内分布的聚类状态。 4)不同肤色在亮度上的差异远远高于在色度上的差异。 1.2肤色在不同亮度下的分布 图3—图4给出了不同亮度下的同一肤色分别在RGB、YCbCr空间的分布情况。图(a)至图(d)的肤色来源于同一人在不同亮度下的照片。
数据的多流形结构分析 我们已经进入了一个信息爆炸的时代，海量的数据不断产生，迫切需要对这些大数据进行有效的分析，以至数据的分析和处理方法成为了诸多问题成功解决的关键，涌现出了大量的数据分析方法。几何结构分析是进行数据处理的重要基础,已经被广泛应用在人脸识别、手写体数字识别、图像分类、等模式识别和数据分类问题，以及图象分割、运动分割等计算机视觉问题（人脸识别、图像分类、运动分割等实例见下文）中。更一般地，对于高维数据的相关性分析、聚类分析等基本问题，结构分析也格外重要。 文献[1]指出一个人在不同光照下的人脸图像可以被一个低维子空间近似，由此产生大量的数据降维方法被用来挖掘数据集的低维线性子空间结构，这类方法假设数据集采样于一个线性的欧氏空间。但是，在实际问题中很多数据具备更加复杂的结构。例如，文献[2]中指出，运动分割（motion segmentation）中的特征点数据具有多个混合子空间的结构，判断哪些特征点属于同一子空间是这个问题能否有效解决的关键。 针对单一子空间结构假设的后续讨论主要是两个方面，首先是从线性到非线性的扩展，主要的代表性工作包括流形（流形是局部具有欧氏空间性质的空间，欧氏空间就是流形最简单的实例）学习等。流形学习于2000年在著名杂志Science上被首次提出，之后逐渐成为了研究热点。基于数据均匀采样于一个高维欧氏空间中的低维流形的假设，流形学习试图学习出高维数据样本空间中嵌入的低维子流形，并求出相应的嵌入映射。流形学习的出现，很好地解决了具有非线性结构的样本集的特征提取问题。然而流形学习方法通常计算复杂度较大，对
噪声和算法参数都比较敏感，并且存在所谓的样本溢出问题，例如，当增加新的样本点时，不能快速地提取新特征。 其次是流形或子空间从一个到多个的扩展，即假设数据集采样于多个欧氏空间的混合。子空间聚类（又称为子空间分割，假设数据分布于若干个低维子空间的并）是将数据按某种方式分类到其所属的子空间的过程。通过子空间聚类，可以将来自同一子空间中的数据归为一类，由同类数据又可以提取对应子空间的相关性质。根据综述[2]，子空间聚类的求解方法有代数方法、迭代方法、统计学方法和基于谱聚类的方法。其中基于谱聚类的方法在近几年较为流行，这类方法首先定义一个关于样本点相互关系的图，然后利用Normalized Cut[3]等谱聚类方法（其输入是一个反应样本关系的相似度矩阵，矩阵的第i行j列的数值越大说明第i个样本和第j个样本的关系越密切，如果能将同类样本的相似度构造的较大，不同类的较小，这类方法一般都能得到正确的分类结果）得到分割结果。代表性的基于谱聚类的子空间分割方法包括低秩表示[4]和稀疏表示[5]等，下面对这两种方法的做个简单介绍。 稀疏子空间聚类： 稀疏子空间聚类方法，是对子空间表示系数进行稀疏约束的一类子空间聚类方法。子空间聚类的最终结果是将同一子空间的数据归为一类。在子空间相互独立的情况下，属于某一子空间的数据只由这个子空间的基的线性组合生成，而在其他子空间中的表示系数为零。这样高维数据的表示系数就具有稀疏的特性。同一子空间中的数据，因为都仅在这一子空间中有非零的表示系数，表现为相同的稀疏特性，通过对表示系数稀疏约束的求解，突出了数据表示系数的这种稀疏特性，进而为数据的正确聚类提供支持。
Sparse subspace clustering:Algorithm,theory,and Application 稀疏子空间聚类（SSC）的算法，理论和应用 参考文献： 1、E. Elhamifar and R. Vidal. Sparse subspace clustering: Algorithm,theory,and Application. IEEE Transactions on Pattern Analysis and Machine Intelligence,2013 2、E. Elhamifar and R. Vidal. Sparse subspace clustering. In CVPR, 2009 2013年的这篇论文写得比09年那篇容易懂一些，讨论和实验也更详细。2013年的这篇可以看成是09那篇会议的扩展版。 一、算法 数据没有损坏，求解模型（5）获得矩阵C：
数据有损坏（noise and sparse outlying entries)，求解模型（13）获得矩阵C： 仿射子空间模型： 二、理论 1、independent子空间 设rank(Yi)=di，Yi表示从第i个子空间Si抽取的Ni个样本构成的矩阵，di 表示Si的维数。论文的定理1表明，模型（5）的解C*是一个块对角矩阵，属于同一个子空间的数据间的cij可能非零，不属于同一个子空间的数据间的cij=0.
2、disjoint子空间 对于disjoint子空间，除了满足条件rank(Yi)=di外，还需要满足公式（21）： 则可获得与independent子空间下类似的结论：
稀疏子空间聚类算法与模型建立 稀疏子空间聚类是一种基于谱聚类的子空间聚类方法， 基本思想：假设高位空间中的数据本质上属于低维子空间，能够在低维子空间中进行线性表示,能够揭示数据所在的本质子空间, 有利于数据聚类. 基 本方法是, 对给定的一组数据建立子空间表示模型,寻找数据在低维子空间中的表示系数, 然后根据表示系数矩阵构造相似度矩阵, 最后利用谱聚类方法如规范化割(Normalized cut, Ncut)[22] 获得数据的聚类结果。 基本原理 稀疏子空间聚类[32] 的基本思想是: 将数据 αS x i ∈表示为所有其他数据的线性组合, j i j ij i x Z x ∑≠= （1） 并对表示系数施加一定的约束使得在一定条件下对所有的αS x j ?, 对应的0=ij Z 。将所有数据及其表示系数按一定方式排成矩阵 ，则式（1）等价于 XZ X = （2） 且系数矩阵N N R Z ?∈ 满足: 当i x 和j x 属于不同的子空间时, 有0=ij Z . 不同于用一组基或字典表示数据, 式（2）用数据集本身表示数据, 称为数据的自表示. 若已知数据的子空间结构, 并将数据按类别逐列排放, 则在一定条件下可使系数矩阵Z 具有块对角结构, 即 ????? ???????=k Z Z Z Z 00000021 （3） 这里),,1(k Z =αα 表示子空间αS 中数据的表示系数矩阵; 反之, 若Z 具有块对角结构, 这种结构揭示了数据的子空间结构. 稀疏子空间聚类就是通过对系数矩阵Z 采用不同的稀疏约束, 使其尽可能具有理想结构, 从而实现子空间聚类. Elhamifar 等[32] 基于一维稀疏性提出了稀疏子空间聚类(Sparse subspace clustering,SSC) 方法, 其子空间表示模型为 1min Z Z 0,..==ii Z XZ X t s （4）
计算机研究与发展ＤＯＩ：１０．７５４４桙ｉｓｓｎ１０００‐１２３９．２０１６．２０１４８３６２ＪｏｕｒｎａｌｏｆＣｏｍｐｕｔｅｒＲｅｓｅａｒｃｈａｎｄＤｅｖｅｌｏｐｍｅｎｔ５３（７）：１６０５１６１１，２０１６ 收稿日期：２０１４－１２－０９；修回日期：２０１５－０６－０９ 基金项目：国家自然科学基金项目（６１３７３０５５）；江苏省自然科学基金项目（ＢＫ２０１４０４１９）；江苏省高校自然科学研究计划重大项目 （１４ＫＪＢ５２０００１） ＴｈｉｓｗｏｒｋｗａｓｓｕｐｐｏｒｔｅｄｂｙｔｈｅＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａ（６１３７３０５５），ｔｈｅＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＪｉａｎｇｓｕＰｒｏｖｉｎｃｅｏｆＣｈｉｎａ（ＢＫ２０１４０４１９），ａｎｄｔｈｅＭａｊｏｒＰｒｏｇｒａｍｏｆＲｅｓｅａｒｃｈＰｌａｎｏｆｔｈｅＮａｔｕｒａｌＳｃｉｅｎｃｅｉｎＨｉｇｈｅｒＥｄｕｃａｔｉｏｎｏｆＪｉａｎｇｓｕＰｒｏｖｉｎｃｅｏｆＣｈｉｎａ（１４ＫＪＢ５２０００１）． 通信作者：吴小俊（ｗｕ＿ｘｉａｏｊｕｎ＠ｊｉａｎｇｎａｎ．ｅｄｕ．ｃｎ）基于分布式低秩表示的子空间聚类算法 许 凯 吴小俊 尹贺峰 （江南大学物联网工程学院 江苏无锡 ２１４１２２） （ｘｕｋａｉ３４７＠ｓｉｎａ．ｃｏｍ） ＤｉｓｔｒｉｂｕｔｅｄＬｏｗＲａｎｋＲｅｐｒｅｓｅｎｔａｔｉｏｎ‐ＢａｓｅｄＳｕｂｓｐａｃｅＣｌｕｓｔｅｒｉｎｇＡｌｇｏｒｉｔｈｍＸｕＫａｉ，ＷｕＸｉａｏｊｕｎ，ａｎｄＹｉｎＨｅｆｅｎｇ（ＳｃｈｏｏｌｏｆＩｎｔｅｒｎｅｔｏｆＴｈｉｎｇｓＥｎｇｉｎｅｅｒｉｎｇ，ＪｉａｎｇｎａｎＵｎｉｖｅｒｓｉｔｙ，Ｗｕｘｉ，Ｊｉａｎｇｓｕ２１４１２２） Ａｂｓｔｒａｃｔ Ｖｉｓｉｏｎｐｒｏｂｌｅｍｒａｎｇｉｎｇｆｒｏｍｉｍａｇｅｃｌｕｓｔｅｒｉｎｇｔｏｍｏｔｉｏｎｓｅｇｍｅｎｔａｔｉｏｎｃａｎｎａｔｕｒａｌｌｙｂｅｆｒａｍｅｄａｓｓｕｂｓｐａｃｅｓｅｇｍｅｎｔａｔｉｏｎｐｒｏｂｌｅｍ，ｉｎｗｈｉｃｈｏｎｅａｉｍｓｔｏｒｅｃｏｖｅｒｍｕｌｔｉｐｌｅｌｏｗｄｉｍｅｎｓｉｏｎａｌｓｕｂｓｐａｃｅｓｆｒｏｍｎｏｉｓｙａｎｄｃｏｒｒｕｐｔｅｄｉｎｐｕｔｄａｔａ．Ｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ‐ｂａｓｅｄｓｕｂｓｐａｃｅｓｅｇｍｅｎｔａｔｉｏｎａｌｇｏｒｉｔｈｍ（ＬＲＲ）ｆｏｒｍｕｌａｔｅｓｔｈｅｐｒｏｂｌｅｍａｓａｃｏｎｖｅｘｏｐｔｉｍｉｚａｔｉｏｎａｎｄａｃｈｉｅｖｅｓｉｍｐｒｅｓｓｉｖｅｒｅｓｕｌｔｓ．Ｈｏｗｅｖｅｒ，ｉｔｎｅｅｄｓｔｏｔａｋｅａｌｏｎｇｔｉｍｅｔｏｓｏｌｖｅｔｈｅｃｏｎｖｅｘｐｒｏｂｌｅｍ，ａｎｄｔｈｅｃｌｕｓｔｅｒｉｎｇａｃｃｕｒａｃｙｉｓｎｏｔｈｉｇｈｅｎｏｕｇｈ．Ｔｈｅｒｅｆｏｒｅ，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｓａｄｉｓｔｒｉｂｕｔｅｄｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ‐ｂａｓｅｄｓｐａｒｓｅｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ（ＤＬＲＲＳ）．ＤＬＲＲＳａｄｏｐｔｓｔｈｅｄｉｓｔｒｉｂｕｔｅｄｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇｔｏｇｅｔｔｈｅｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘ，ｔｈｅｎｔａｋｅｔｈｅａｂｓｏｌｕｔｅｖａｌｕｅｏｆｅａｃｈｅｌｅｍｅｎｔｏｆｔｈｅｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘ，ａｎｄｒｅｔａｉｎｔｈｅｋｌａｒｇｅｓｔｃｏｅｆｆｉｃｉｅｎｔｓｐｅｒｃｏｌｕｍｎａｎｄｓｅｔｔｈｅｏｔｈｅｒｅｌｅｍｅｎｔｓｔｏ０ｔｏｇｅｔａｎｅｗｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘ．Ｆｉｎａｌｌｙ，ＤＬＲＲＳｐｅｒｆｏｒｍｓｓｐｅｃｔｒａｌｃｌｕｓｔｅｒｉｎｇｏｖｅｒｔｈｅｎｅｗｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘ．Ｂｕｔｉｔｄｏｅｓｎ摧ｔｈａｖｅｉｎｃｒｅｍｅｎｔａｌｌｅａｒｎｉｎｇｆｕｎｃｔｉｏｎ，ｓｏｔｈｅｒｅｉｓａｓｃａｌａｂｌｅｄｉｓｔｒｉｂｕｔｅｄｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ‐ｂａｓｅｄｓｐａｒｓｅｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ（ＳＤＬＲＲＳ）ｈｅｒｅ．Ｉｆｎｅｗｓａｍｐｌｅｓａｒｅｂｒｏｕｇｈｔｉｎ，ＳＤＬＲＲＳｃａｎｕｓｅｔｈｅｆｏｒｍｅｒｃｌｕｓｔｅｒｉｎｇｒｅｓｕｌｔｔｏｃｌａｓｓｉｆｙｔｈｅｎｅｗｓａｍｐｌｅｓｔｏｇｅｔｔｈｅｆｉｎａｌｒｅｓｕｌｔ．ＥｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｏｎＡＲａｎｄＥｘｔｅｎｄｅｄＹａｌｅＢｄａｔａｓｅｔｓｓｈｏｗｔｈａｔｔｈｅｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｓｃａｎｎｏｔｏｎｌｙｏｂｖｉｏｕｓｌｙｒｅｄｕｃｅｔｈｅｒｕｎｎｉｎｇｔｉｍｅ，ｂｕｔａｌｓｏａｃｈｉｅｖｅｈｉｇｈｅｒａｃｃｕｒａｃｙ，ｗｈｉｃｈｖｅｒｉｆｉｅｓｔｈａｔｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｓａｒｅｅｆｆｉｃｉｅｎｔａｎｄｆｅａｓｉｂｌｅ．Ｋｅｙｗｏｒｄｓ ｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ；ｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇ；ｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇ；ｉｎｃｒｅｍｅｎｔａｌｌｅａｒｎｉｎｇ；ｃｏｅｆｆｉｃｉｅｎｔｓｒｅｃｏｎｓｔｒｕｃｔｉｏｎ 摘 要 针对基于低秩表示的子空间分割算法运算时间较长、 聚类的准确率也不够高，提出一种基于分布式低秩表示的稀疏子空间聚类算法（ｄｉｓｔｒｉｂｕｔｅｄｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ‐ｂａｓｅｄｓｐａｒｓｅｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ，ＤＬＲＲＳ），该算法采用分布式并行计算来得到低秩表示的系数矩阵，然后保留系数矩阵每列的前ｋ个绝对值最大系数，其他系数置为０，用此系数矩阵构造一个稀疏的样本关系更突出的相似度矩阵，接着用谱聚类得到聚类结果．但是其不具备增量学习功能，为此再提出一种基于分布式低秩表示的增量式稀疏子空间聚类算法（ｓｃａｌａｂｌｅｄｉｓｔｒｉｂｕｔｅｄｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎｂａｓｅｄｓｐａｒｓｅｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ，ＳＤＬＲＲＳ），如果有新增样本，可以利用前面的聚类结果对新增样本进行
空间聚类概念 空间聚类作为聚类分析的一个研究方向，是指将空间数据集中的对象分成由相似对象组成的类。同类中的对象间具有较高的相似度，而不同类中的对象间差异较大。作为一种无监督的学习方法，空间聚类不需要任何先验知识，比如预先定义的类或带类的标号等。由于空间聚类方法能根据空间对象的属性对空间对象进行分类划分，其已经被广泛应用在城市规划、环境监测、地震预报等领域，发挥着较大的作用。同时，空间聚类也一直都是空间数据挖掘研究领域中的一个重要研究分支。目前，己有许多文献资料提出了针对不同数据类型的多种空间聚类算法，一些著名的软件，如WEAK、SPSS、SAS等软件中已经集成了各种聚类分析软件包。 1 空间数据的复杂性 空间聚类分析的对象是空间数据。由于空间数据具有空间实体的位置、大小、形状、方位及几何拓扑关系等信息，使得空间数据的存储结构和表现形式比传统事务型数据更为复杂，空间数据的复杂特性表现： (1)空间属性间的非线性关系。由于空问数据中蕴含着复杂的拓扑关系，因此，空间属性间呈现出一种非线性关系。这种非线性关系不仅是空间数据挖掘中需要进一步研究的问题，也是空问聚类所面临的难点之一。 (2)空间数据的尺度特征。空间数据的尺度特征足指在不同的层次上，空间数据所表现出来的特征和规律都不尽相同。虽然在空间信息的概化和细化过程中可以利用此特征发现整体和局部的不同特点，但对空间聚类任务来说，实际上是增加了空间聚类的难度。 (3) 间信息的模糊性。空间信息的模糊性足指各种类型的窄问信息中，包含大量的模糊信息，如空问位置、间关系的模糊性，这种特性最终会导致空间聚类结果的不确定性。 (4)空间数据的高维度。空问数据的高维度性是指空间数据的属性(包括空间属性和非空间属性)个数迅速增加，比如在遥感领域，获取的空间数据的维度已经快速增加到几十甚至上百个，这会给空间聚类的研究增加很大的困难。 2 空间聚类算法 目前，研究人员已经对空间聚类问题进行了较为深入的研究，提出了多种算法。根据空间聚类采用的不同思想，空间聚类算法主要可归纳为以下几种：基于划分的聚类算法、基于层次的聚类算法、基于密度的聚类算法、基于网格的聚类算法、基于模型的聚类算法以及其它形式的聚类算法，如图l所示。 (1)基于划分的聚类 基于划分的聚类方法是最早出现并被经常使用的经典聚类算法。其基本思想是：在给定的数据集随机抽取n个元组作为n个聚类的初始中心点，然后通过不断计算其它数据与这几个中心点的距离(比如欧几里得距离)，将每个元组划分到其距离最近的分组中，从而完成聚类的划分。由于基于划分的聚类方法比较容易理解，且易实现，目前其已被广泛的弓l入到空间聚类中，用于空间数据的分类。其中最为常用的几种算法是：k一平均(k-means)算法、kl中心点(k—medoids)算法和EM(expectation maximization)算法。k一平均算法’使
2006年 8月第42卷 第4期北京师范大学学报(自然科学版) Jour nal of Beijing N ormal U niver sity (N atural Science )A ug.2006 V ol.42 N o.4 应用空间聚类进行点数据分布研究* 林冬云1) 刘慧平1,2,3)? (1)北京师范大学地理学与遥感科学学院;2)北京师范大学遥感科学国家重点实验室; 3)北京师范大学环境遥感与数字城市北京市重点实验室:100875,北京) 摘要 空间数据挖掘是寻找大数据量空间分布的重要方法,应用地理信息系统(G IS )进行空间数据挖掘是目前进行海量数据分析的重要手段之一.应用空间聚类方法对北京市海淀区54325个企业点数据进行量化分析研究,通过空间位置聚类,进行属性指标量化,从而进行属性指标分层聚类,得到企业空间分布特征.研究表明,空间聚类方法是进行点数据空间分布研究的有效方法. 关键词 空间聚类;企业分布;地理信息系统;量化 *国家自然科学基金资助项目(40271035);国家“十五”科技攻关课题资助项目(2003BA808A16-6) ?通讯作者 收稿日期:2005-11-23 随着数据获取和处理技术的迅速发展及数据库管 理系统的广泛应用,人们积累的数据越来越多,但在激增的数据背后隐藏着许多重要的信息,由于缺乏有效的方法,导致了一种“数据爆炸但知识贫乏”的现象[1],面对这一挑战,数据挖掘(data mining ,DM )和知识发现(know ledge discovery in database s ,KDD )技术应运而生并得到迅速发展,它的出现为自动和智能地把海量的数据转化成为有用的信息和知识提供了手段. 作为DM 技术一个新的分支,空间DM 也称基于空间数据库的数据挖掘和知识发现(spatial data mining and know ledge disco very ),是指从空间数据库中提取隐含的、用户感兴趣的空间和非空间的模式、普遍特征、规则和知识的过程[2]. 空间聚类方法是空间数据挖掘中的主要方法之一,是在一个比较大的多维数据集中根据距离的度量找出簇或稠密区域.聚类算法无需背景知识,能直接从空间数据库中发现有意义的空间聚类结构[3].在无先验知识的情况下,聚类分析技术是进行数据挖掘时的首选[4],因而运用空间数据聚类方法来处理海量数据,对于提取大型空间数据库中有用的信息和知识具有十分重要的现实意义. 目前,对于空间聚类的研究主要集中在算法研究和应用研究上,存在2种偏向,一是从事GIS 理论方法和技术工具研究的工作者大多根据空间对象的地理坐标进行聚类,即只考虑对象的空间邻近性,而不考虑对象属性特征的相似性[2,5];另一种是从事GIS 应用和地学研究的工作者,直接套用传统聚类分析方法,根据属性特征集进行分析,忽视了对象的空间邻近性[6]. 而空间对象本质上具有地理位置和属性特征双重含 义,二者结合才能完整地描述空间特征和空间差异.将地理位置和属性特征纳入统一的空间距离测度和空间聚类分析系统,将会改善空间分析和空间DM 的信息 质量[7-9] . 本文主要应用GIS 分析技术,采用空间DM 中的空间聚类方法,通过将空间位置与属性相结合的聚类方法,对北京市海淀区5万多个企事业单位的点分布数据进行分析,探讨对于属性是定性描述的点分布数据的量化方法. 1 研究区和数据来源 海淀区是北京市重要近郊区,占地面积大,人口众多,交通发达,存在着大量的居民和村民混居现象,是中心城市自上而下的扩散能力最强、城乡一体化程度最高、城乡联系最密切的地区,也是大都市空间扩展的主要地区[10]. 研究使用的数据来源是2001年北京市企业数据的统计表,经数字化处理生成企业单位点位分布图,按照数据文件中企业注册地址信息,结合参考北京市电子地图、北京市街道胡同地图集、北京市地图、网上北京市地图以及有关企事业单位的网站,将海淀区共计54325条记录生成5万多个企业的点分布图. 2 研究方法 应用GIS 提取企事业单位分布空间坐标,进行按位置距离聚类分析,获得位置聚类小区,然后进行属性指标的量化,应用聚类分析进行属性聚类,分析企事业
2017年度广东省科学技术奖项目公示 项目名称高维复杂数据的子空间挖掘方法研究 主要完成单位单位1: 哈尔滨工业大学深圳研究生院单位2: 无 单位3: 无 主要完成人（职称、完成单位、工作单位）1. 叶允明 职称：教授 工作单位：哈尔滨工业大学深圳研究生院 完成单位：哈尔滨工业大学深圳研究生院 主要贡献：提出本项目的关键学术思想和研究思路，全面规划组织并研究了本项目的研究内容，对项目四个主要创新点均做出了贡献： （1）提出了属性加权的子空间聚类方法，有效解决了高维数据的聚类问题。 （2）提出了基于分层子空间抽样的随机森林方法，减小了泛化误差界，提升了高维数据的分类性能。 （3）揭示了聚类问题中多模态子空间的规律，为关系型高维数据的子空间分类奠定了基础。 （4）建立了多模态子空间数据分类的关键技术，为解决复杂关系型数据的分类奠定了基础。 应用贡献：将项目成果应用于深圳出入境检验检疫局“智慧口岸”建设中的信息自动获取与智能信息服务、深圳市地税局、中油瑞飞信息技术有限公司等单位的互联网信息获取与挖掘服务等。
2. 李旭涛 职称：副教授 工作单位：哈尔滨工业大学深圳研究生院 完成单位：哈尔滨工业大学深圳研究生院 主要贡献：对本项目的主要创新点（1）（2）和（3）做出了贡献： （1）提出了层次子空间聚类算法，有效解决了高维数据的多粒度子空间聚类问题。 （2）揭示了分层抽样子空间的规律，分析了其基本特性，明确了分层抽样随机森林算法的适用范围。 （3）提出了基于张量积的马尔科夫链，并基于其建立了多模态聚类模型，有效解决了复杂关系型数据的聚类问题；提出了基于全变分约束张量分解的聚类算法，解决高维多模态数据的子空间聚类问题。 3. 张海军 职称：副教授 工作单位：哈尔滨工业大学深圳研究生院 完成单位：哈尔滨工业大学深圳研究生院 主要贡献：对本项目的主要创新点（1）和（4）做出了贡献：（1）揭示了判别信息在高维数据子空间聚类中的作用，提出了结合簇内紧致性和簇间分离性的聚类优化目标函数。 （4）提出了面向多模态文本数据的子空间分析算法，通过多维度浅层语义分析提升了子空间分类的性能；揭示了高维多类标数据的层次特性，为了其分类模型的建立奠定了基础。 4. 吴庆耀
聚类分析中几种算法的比较 2009-04-13 23:12 将数据库中的对象进行聚类是聚类分析的基本操作，其准则是使属于同一类的个体间距离尽可能小，而不同类个体间距离尽可能大，为了找到效率高、通用性强的聚类方法人们从不同角度提出了近百种聚类方法，典型的有K-means 方法、K-medoids方法、CLARANS方法,BIRCH方法等，这些算法适用于特定的问题及用户。本文综合提出了评价聚类算法好坏的5个标准，基于这5个标准，对数据挖掘中常用聚类方法作了比较分析，以便于人们更容易、更快捷地找到一种适用于特定问题及用户的聚类算法。 聚类算法研究及比较框架 聚类算法一般有五种方法，最主要的是划分方法和层次方法两种。划分聚类算法通过优化评价函数把数据集分割为K个部分，它需要K作为输人参数。典型的分割聚类算法有K-means算法, K-medoids算法、CLARANS算法。层次聚类由不同层次的分割聚类组成，层次之间的分割具有嵌套的关系。它不需要输入参数，这是它优于分割聚类算法的一个明显的优点，其缺点是终止条件必须具体指定。典型的分层聚类算法有BIRCH算法、DBSCAN算法和CURE算法等。 对各聚类算法的比较研究基于以下5个标准： ①是否适用于大数据量，算法的效率是否满足大数据量高复杂性的要求; ②是否能应付不同的数据类型，能否处理符号属性; ③是否能发现不同类型的聚类; ④是否能应付脏数据或异常数据; ⑤是否对数据的输入顺序不敏感。 下面将在该框架下对各聚类算法作分析比较。 数据挖掘常用聚类算法比较分析 3.1 K-pototypes算法 K-pototypes算法结合了K-means方法和根据K-means方法改进的能够处理符号属性的K-modes方法，同K-means 方法相比，K-pototypes 算法能够处理符号属性。 3.2 CLARANS算法（划分方法） CLARANS算法即随机搜索聚类算法，是一种分割聚类方法。它首先随机选择一个点作为当前点，然后随机检查它周围不超过参数Maxneighbor个的一些邻接点，假如找到一个比它更好的邻接点，则把它移人该邻接点，否则把该点作为局部最小量。然后再随机选择一个点来寻找另一个局部最小量，直至所找到的局部最小量数目达到用户要求为止。该算法要求聚类的对象必须都预先调人内存，并且需多次扫描数据集，这对大数据量而言，无论时间复杂度还是空间复杂度都相当大。虽通过引人R-树结构对其性能进行改善，使之能够处理基于磁盘的大型数据库，但R*-树的构造和维护代价太大。该算法对脏数据和异常数据不敏感，但对数据物人顺序异常敏感，且只能处理凸形或球形边界聚类。 3.3 BIRCH算法（层次方法） BIRCH算法即平衡迭代削减聚类法，其核心是用一个聚类特征3元组表示一个簇的有关信息，从而使一簇点的表示可用对应的聚类特征，而不必用具体的一组点来表示。它通过构造满足分支因子和簇直径限制的聚类特征树来求聚类。BIRCH算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。算法的聚类特征树是一个具有两个参数分枝因子B和类直径T的高度平衡树。分枝因子规定了树的每个节点子女的最多个数，而类直径体现了对一类点的直径大小的限制即这些点在多大范围内可以聚为一类，非叶子结点为它的子女的最大关键字，可以根据这些关键字进行插人索引，它总结了其子女的信息。 聚类特征树可以动态构造，因此不要求所有数据读人内存，而可以在外存上逐个读人。新的数据项总是插人到树中与该数据距离最近的叶子中。如果插人后使得该叶子的直径大于类直径T，则把该叶子节点分裂。其它叶子结点也需要检查是否超过分枝因子来判断其分裂与否，直至该数据插入到叶子中，并且满足不超过类直径，而每个非叶子节点的子女个数不大于分枝因子。算法还可以通过改变类直径修改特征树大小，控制其占内存容量。 BIRCH算法通过一次扫描就可以进行较好的聚类，由此可见，该算法适合于大数据量。对于给定的M兆内存空间，其空间复杂度为O(M)，时间间复杂度为O(dNBlnB(M/P)).其中d为维数,N为节点数,P为内存页的大小，B为由P决定的分枝因子。I/O花费与数据量成线性关系。BIRCH算法只适用于类的分布呈凸形及球形的情况，并且由于BIRCH算法需提供正确的聚类个数和簇直径限制，对不可视的高维数据不可行。 3.4 CURE算法（层次方法） CURE算法即使用代表点的聚类方法。该算法先把每个数据点看成一类，然后合并距离最近的类直至类个数为所要求的个数为止。CURE算法将传统对类的表示方法进行了改进，回避了用所有点或用中心和半径来表示一个类，而