稀疏子空间聚类的惩罚参数自调整交替方向法_姚刚
收稿日期：2013－12－03修回日期：2014－03－13
网络出版时间：2014－07－28
基金项目：江苏省自然科学基金（BK2011758）；南京邮电大学攀登计划（NY212066）
作者简介：姚
刚（1988－），男，江苏宝应人，硕士研究生，研究方向为图像处理与模式分类；杨敏，副教授，从事计算机视觉和图像理解的研
究工作。
网络出版地址：http ：//www．cnki．net /kcms /detail /61．1450．TP．20140728．1224．030．html
稀疏子空间聚类的惩罚参数自调整交替方向法
姚
刚，杨
敏
（南京邮电大学自动化学院，江苏南京210023）
摘
要：稀疏子空间聚类是利用子空间并集中数据向量的稀疏表示，从而将数据划分到各自子空间，该类方法关键是求出
最优稀疏解。文中采用交替方向法求稀疏解，
交替方向法把复杂问题分解成简单的、有效求解的子问题，达到最优速度。在交替方向法求解过程中，通常惩罚因子是恒定不变的。文中提出一种惩罚因子参数自调整策略，根据每次迭代信息，调整惩罚因子参数。基于运动分割数据和Hopkins 数据库实验，结果表明在迭代次数和运算时间上，稀疏子空间聚类的交替方向法及其惩罚参数自调整策略比传统算法有很大提高，而且对噪声数据也非常有效。关键词：子空间聚类；稀疏表示；L1范数正则化；交替方向法中图分类号：TP301
文献标识码：A
文章编号：1673－629X （2014）11－0131－04
doi ：10．3969/j．issn．1673－629X．2014．11．033
Alternating Direction Method of Self －adjusting Penalty Parameters of
Sparse Subspace Clustering
YAO Gang ，YANG Min
（College of Automation ，Nanjing University of Posts and Telecommunications ，
Nanjing 210023，China ）
Abstract ：Sparse subspace clustering uses the sparse representation of vectors lying on a union of subspace to cluster the data into separate subspaces．The key of this algorithm is to find the optimal sparse solution．Alternating Direction Method （ADM ）is applied to solve sparse problem in this paper．ADM divides the complex problem into simple and effectively solving sub －problem to achieve optimal speed．In the process of the ADM solving ，the penalty factor is constant．In this paper ，a penalty factor self －adjusting strategy is proposed ，according to the each iterative information ，adjust the penalty factor parameters．The experiment based on motion division data and Hop-kins database shows that the proposed method has great improvement in iteration times and computing time compared with traditional al-gorithms ，is also valid for noisy data．
Key words ：subspace clustering ；sparse representation ；L1norm regularization ；alternating direction method
0引言
在聚类分析中，高维数据聚类是聚类分析技术的难点和重点，子空间聚类［1］
是实现高维数据集聚类的
有效途径。子空间聚类常见算法有基于谱聚类算
法
［2］
，谱聚类的关键是相似矩阵构造；而近年来，随着稀疏学习的流行，相似矩阵构造常有基于稀疏表示的
［3］
和基于低秩描述的
［4］
。稀疏表示的子空间聚类算
法利用稀疏表示对低维子空间的数据进行聚类。子空间并集里每个点，可用空间里所有点构成的字典来稀疏表示。因此关键是找到子空间里每个特征点的最优
稀疏表示。然后在谱聚类框架下，对数据进行划分。这种方法能有效克服数据噪声。文中主要研究稀疏子空间聚类算法。
近年来，压缩感知中稀疏优化［5－6］
越来越流行，交替方向法
［7－8］
也备受关注。交替方向法常用于求解具有可分离结构的目标函数凸优化问题。文中采用交替方向法处理稀疏子空间聚类
［9］
问题。稀疏子空间聚类
的关键是最优稀疏求解，一般转化为L1范数问题，常用内点算法CVX 优化工具包求解。但是内点算法在处理一定规模的问题时，会花费很大的计算量。文中采用交替方向法求解L1范数，
在求解中，一般惩罚因第24卷第11期2014年11月
计算机技术与发展
COMPUTEＲTECHNOLOGY AND DEVELOPMENT
Vol．24No．11Nov．2014
子是常数不变的。文中研究了一种惩罚因子参数自调整策略，
其根据一种更新规则，惩罚因子参数可以自适应改变，这样加快了收敛速度。
文中主要先对稀疏子空间模型进行介绍，然后提出解决模型中最稀疏解的交替方向法及惩罚因子参数自调整策略，最后基于运动分割数据仿真实验与Hop-kins 数据库［10］，给出了改进算法与原算法实验结果对比。
1稀疏子空间聚类模型稀疏子空间聚类是一种基于稀疏表示的子空间聚
类算法。假设数据集Y =［
y 1，y 2，…，y N ］∈ＲM ?
N 对于每个数据样本y i 而言，直接使用原始数据集作为冗余字典，得每个数据点的稀疏表示c i ：
min 〈C ，Z 〉
‖C ‖0+
λz 2
‖Z ‖2F （1）
s．t．Y =YC +Z
C ii =0
i =1，2，…，N
其中，
C 是样本y i 基于数据集Y 的稀疏表示；‖·‖0表示l 0范数，即表示矩阵中非零元个数；‖·‖F 为Frobenius 范数。
式（1）是非凸的并且是一个NP －hard 问题，常使用凸松弛方式（用l 1范数替代原有的l 0范数），将上述非凸优化转变如下：
min 〈C ，Z 〉‖C ‖1+λz
2‖Z ‖2F （2）
s．t．Y =YC +Z
C ii =0
i =1，2，…，N
求解上式得到每个数据点的稀疏表示，构造相似度矩阵W =［w 1，w 2，…，w N ］∈W N ?
N 。为了使W 对称，定义如下：
W =C +C
T
（3）
从另一方面说，节点i 和j 之间边的权重等于c ij +c ji 。这里W 由n 个独立子空间生成，每个样本y i 可以由属于同一个子空间的其他样本进行稀疏重构，属于不同子空间的样本的稀疏表示系数为零。
在相似度矩阵W 上用谱聚类算法
［2］
进行划分。
算法1：谱聚类算法（Spectral Clustering ）。
输入：n 个线性子空间S i {}n
i =1组成的数据点
y i {}N i =1。
（1）构造基于数据集Y 的相似矩阵W ；
（2）计算相似矩阵W 的Laplacian 矩阵，其中矩
阵L =I －D －1/2WD 1/2，D ∈W N ?
N 为对角矩阵，对角元素D ii =
∑j
W
ij
；
（3）求出L 的前n 个特征值，以及其对应的特征向量u i {}k
i =1；
（4）把k 个特征（列）向量排列在一起组成一个N ?k 的矩阵；
（5）把生成矩阵每一行看作k 维空间中的一个向
量，使用k －means 算法聚类成n 类。
输出：数据集Y 的n 子集划分y 1，
y 2，…，y n 。2稀疏子空间模型求解
稀疏子空间模型一般常用内点算法CVX 优化工
具包求解，文中用交替方向及其改进算法对其求解。2．1
交替方向法
首先根据式（2）的等式约束，可以消除目标函数的Z ，并引入辅助矩阵A ∈ＲN ?N
，那么公式（2）可以重
写成如下形式：
min （C ，A ）
‖C ‖1+
λz 2
‖Y －YA ‖2
F （4）
s．t．A =C
C ii =0
i =1，2，…，N
引进矩阵Δ∈ＲN ?N
拉格朗日乘子，可以得到增广
拉格朗日函数：
L （C ，A ，Δ）=‖C ‖1+
λz 2
‖Y －YA ‖2
F +〈Δ，A －C 〉+ρ2
‖A －C ‖2F
（5）
其中，ρ为惩罚因子；〈
·〉表示标准内积。通过固定（C k ，Δk
），对L 关于A 求导可得：
－λz Y T （Y －YA （k +1））[]+Δk +
ρA
k +1
－C k []=0（6）化简可得：
（λz Y T Y +ρI ）A k +
1=λz Y T Y +ρC k －Δk
（7）
一般情况下，Y T Y 为对角阵时，可以得到A
k
+1
的
封闭解：
A k
+1
=（λz Y T Y +ρI ）
－1
·（λz Y T Y +ρC k －Δk ）
（8）
固定（A k +
1，Δk ），对L 关于C 求导得到C
k +1［5］
，可
以得到其封闭解：C k +1
=J －diag （J ），其中
J =Τ1
ρ
（A
k +1
+Δk
ρ
）（9）
其中，Τη（·）是收缩阈值操作符，其可以定义成如下形式：
Τη（x ）=x －η，x ＞η
x +η，
x ＜－η0，others
{
（10）
这里的x 可以是数字，向量或是一个矩阵。
当得到（C k +
1
，A k +
1）时，可以更新拉格朗日乘子，
如下：
·231·计算机技术与发展第24卷
Δk+1=Δk+ρ（A k+1－C k+1）（11）
这三步不断重复执行直到收敛完成或达到设定的迭代次数。迭代停止标准为‖A k－C k‖
#
≤
ε，‖A k－A k－1‖
#
≤ε。其中ε表示容错率，一般取ε∈10－3，10－4
{}，下面算法展示了交替方向法执行式子（2）的过程。
算法2：稀疏求解的ADM算法。
初始化：k=0，C0，A0，Δ0为0。
while‖A k－C k‖
#≥ε，‖A k－A k－1‖
#
≥ε做
下面操作：
（1）通过求解下列等式更新A k+1
（λ
z Y T Y+ρI）A k+1=λ
z
Y T Y+ρC k－Δk
（2）更新C k+1：C k+1=J－diag（J），其中J=
Τ1
ρ（A k+1+Δ
k
ρ
）
（3）更新Δk+1：Δk+1=Δk+ρ（A k+1－C k+1）（4）k=K+1
end while
输出：最优稀疏系数矩阵C*=C k。
2．2惩罚参数自调整策略
在交替方向算法中，惩罚因子ρ是固定不变的。但是可以观察到固定的惩罚因子的交替方向法收敛很慢，而且选择一个最优的惩罚因子很困难。所以文中研究了对于惩罚因子ρ的自调整策略［11］。
ρk+1=min（ρ
max
，βρ
k
）（12）
其中，ρ
max 是ρ
k
{}的上限，β的值定义如下：
β=
β0，当ρ
k
max（‖C k+1－C k‖，‖A k+1－A k‖）＜ε
2
1，其他
{
（13）
其中，β
≥1是常数。实际应用中变化的β是首
选；ε
2为常数，文中此处取ε
2
=10－4。
这种方法根据迭代停止标准来平衡误差并且引进几个参数。
算法3：稀疏求解的惩罚参数自调整交替方向法。
初始化：k=0，C0，A0，Δ0和ρ
。
while‖A k－C k‖
#≥ε，‖A k－A k－1‖
#
≥ε做下
面操作：
（1）通过求解下列等式更新A k+1
（λ
z Y T Y+ρ
k
I）A k+1=λ
z
Y T Y+ρ
k
C k－Δk
（2）更新C k+1：C k+1=J－diag（J），其中J=
Τ1
ρ（A k+1+Δ
k
ρ
k
）
（3）更新Δk+1：Δk+1=Δk+ρ
k
（A k+1－C k+1）
（4）ρ
k+1
=min（ρ
max
，βρ
k
）
（5）k=K+1
end while
输出：最优稀疏系数矩阵C*=C k。
3实验仿真与分析
为了测试交替方向法及其改进算法与传统算法对
比效果，将稀疏子空间聚类应用于视频点特征运动分
割［12－13］中。假设F帧图像中有N个特征点，运动分割
问题可以通过提取跟踪视频序列中f=1，2，…，F帧的
N个特征点x
fi
∈Ｒ2
{}N
i=1
来解决。每个数据点y
i
也被
称为一个特征轨迹［14］，与视频里F帧特征点x
fi
组成的
2F维向量相对应，定义如下：
y
i
=x T
1i
，x T
2i
，…，x T
Fi
[]
所以，所有帧的特征点组合成一个2F?N的矩阵
Y=y
1
，y
2
，…，y
N
[]，在稀疏子空间聚类算法中，Y作
为一个字典，求出每个特征点的稀疏表示C，于是形
成（2）的凸优化问题。
实验软件平台为Matlab7．10，硬件平台为Intel
Pentium双核CPU，2．3GHz，2GB内存，Windows XP
系统的笔记本。如图1所示，给出了三个测试视频点
特征序列［15］中的3帧
。
图1三个视频点特征序列分割聚类效果图
（只显示其中三帧）
表1列出了3个视频中每个视频的帧和特征点的
数量。对于每个视频系列，用稀疏子空间算法来对跟
踪每个帧中的特征点进行分割聚类。用不同颜色标记
‘+’区分。
表1三个视频序列的帧数与特征点数
视频序列1视频序列2视频序列3
帧数3017100
特征点数1366373
·
331
·
第11期姚刚等：稀疏子空间聚类的惩罚参数自调整交替方向法
表2为三种算法在聚类误差，迭代次数和迭代时间上的对比。子空间聚类的误差定义如下：
子空间聚类误差=错分类点的数特征点的总数
表2三种算法平均子空间误差率、平均迭代次数和平均运行时间对比（1）
算法名称平均子空间
聚类误差率
平均迭
代次数
平均运
行时间
CVX工具内点优化算法0．2569160．323交替方向法01180．484参数自调整交替方向法0340．135
如表2所示，交替方向法及其改进算法，无论在子空间聚类误差率、迭代次数还是运算时间，都比传统的内点优化算法有较大的改进提高。这里CVX内点优化算法的迭代次数小于交替方向法，是因为内点算法每次迭代都要经过两次求导，所以精度上会相对提高点，但是缺点就是每次迭代花费时间比较长，而改进的算法在迭代时间和每次迭代效率都比CVX内点算法和交替方向法有较大提升。
为了进一步验证文中提出的方法，使用公共的运动分割测评库—Hopkins数据库［10］进行对比实验分析，验证文中提出的方法的鲁棒性和有效性。Hopkins 包含了155个运动视频序列，其中有120个视频序列包含两个运动物体，35个视频序列包含三个刚性运动物体。包含两个运动物体的视频序列有256个特征点和30帧。包含三个运动物体视频序列有398个特征点和29帧。将文中提出的方法与传统方法应用于此数据库，如表3所示。
表3三种算法平均子空间误差率、平均迭代
次数和平均运行时间对比（2）
算法名称
两个运动物体三个运动物体
平均子空
间聚类误
差率
平均迭
代次数
平均运
行时间
平均子
空间聚类
误差率
平均迭
代次数
平均运
行时间
CVX工具内
点优化算法
0．18162152．730．32244267．47
交替方向法0．031071．30．061283．85
参数自调整
交替方向法
0．03330．380．05360．90实验进一步表明，文中提出的改进算法在平均聚类误差率、迭代次数和平均运行时间都比交替方向法和传统的内点算法有较大的改进。
4结束语
文中针对交替方向法进行改进，从实验结果得出，交替方向法是目前较好求解稀疏系数的优化算法，相对于传统的内点优化算法，在算法效率上有很大的提高。文中在交替方向法基础上提出惩罚参数自调整策略，使迭代次数相应减少并使运行时间有较大的降低，说明该策略有较好的改进效果。稀疏子空间聚类的交替方向法的快速和并行计算方法，有待进一步研究。
参考文献：
［1］VidalＲ．Subspace clustering［J］．IEEE Signal Processing Ma －gazine，2011，28（2）：52－68．
［2］von Luxburg U．A tutorial on spectral clustering［J］．Statistics and Computing，2007，17（4）：395－416．
［3］Elhamifar E，VidalＲ．Sparse subspace clustering［C］//Proc of IEEE conference on computer vision and pattern recogni-
tion．［s．l．］：IEEE，2009：2790－2797．
［4］Liu Guangcan，Lin Zhouchen，Yong Yu．Ｒobust subspace seg-mentation by low－rank representation［C］//Proc of27th in-
ternational conference on machine learning．Haifa：National
Science Foundation，2010：663－670．
［5］文再文，印卧涛，刘歆，等．压缩感知和稀疏优化简介［J］．运筹学学报，2012，16（3）：49－64．
［6］Tropp J A，Wright S J．Computational methods for sparse solu-tion of linear inverse problems［J］．Proceedings of the IEEE，
2010，98（6）：948－958．
［7］Yang Junfeng，Zhang Yin．Alternating direction algorithms for L1－problems in compressive sensing［J］．IEEE Signal Pro-
cessing Letters，2012，20（1）：63－66．
［8］Yuan Xiaoming．Alternating direction method for covariance selection models［J］．Journal of Scientific Computing，2012，51
（2）：261－273．
［9］Elhamifar E，VidalＲ．Sparse subspace clustering：algorithm，theory，and applications［J］．IEEE Transactions on Pattern A-
nalysis and Machine Intelligence，2013，35（11）：2765－2781．［10］TronＲ，VidalＲ．A benchmark for the comparison of3－D mo-tion segmentation algorithms［C］//Proc of conference on com-
puter vision and pattern recognition．［s．l．］：IEEE，2007．［11］Lin Zhouchen，LiuＲisheng，Su Zhixun．Linearized alternating direction method with adaptive penalty for low－rank represen-
tation［C］//Proceedings of advances in neural information
processing systems．［s．l．］：［s．n．］，2011：612－620．
［12］Lauer F，Schnorr C．Spectral clustering of linear subspaces for motion segmentation［C］//Proc of IEEE12th international
conference on computer vision．Kyoto：IEEE，2009：678－685．［13］青波，杨晨辉，陈涛．基于分割的复杂运动跟踪的研究［J］．计算机技术与发展，2009，19（4）：157－159．
［14］王洪斌，李华．基于运动轨迹聚类的运动分割［J］．计算机应用，2003，23（10）：1－3．
［15］Sugaya Y，Kanatani K．Multi－stage optimization for multi－body motion segmentation［J］，IEICE Transactions on Informa-
tion and Systems，2004，E－87D（7）：1935－1942．
·
431
·计算机技术与发展第24卷
空间分析与应用复习题
《空间分析与应用》复习题 一、名词解释 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
【子空间聚类】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
大数据一词在近年来被广泛提及,它不仅越来越频繁的出现在
数据的多流形结构分析 我们已经进入了一个信息爆炸的时代，海量的数据不断产生，迫切需要对这些大数据进行有效的分析，以至数据的分析和处理方法成为了诸多问题成功解决的关键，涌现出了大量的数据分析方法。几何结构分析是进行数据处理的重要基础,已经被广泛应用在人脸识别、手写体数字识别、图像分类、等模式识别和数据分类问题，以及图象分割、运动分割等计算机视觉问题（人脸识别、图像分类、运动分割等实例见下文）中。更一般地，对于高维数据的相关性分析、聚类分析等基本问题，结构分析也格外重要。 文献[1]指出一个人在不同光照下的人脸图像可以被一个低维子空间近似，由此产生大量的数据降维方法被用来挖掘数据集的低维线性子空间结构，这类方法假设数据集采样于一个线性的欧氏空间。但是，在实际问题中很多数据具备更加复杂的结构。例如，文献[2]中指出，运动分割（motion segmentation）中的特征点数据具有多个混合子空间的结构，判断哪些特征点属于同一子空间是这个问题能否有效解决的关键。 针对单一子空间结构假设的后续讨论主要是两个方面，首先是从线性到非线性的扩展，主要的代表性工作包括流形（流形是局部具有欧氏空间性质的空间，欧氏空间就是流形最简单的实例）学习等。流形学习于2000年在著名杂志Science上被首次提出，之后逐渐成为了研究热点。基于数据均匀采样于一个高维欧氏空间中的低维流形的假设，流形学习试图学习出高维数据样本空间中嵌入的低维子流形，并求出相应的嵌入映射。流形学习的出现，很好地解决了具有非线性结构的样本集的特征提取问题。然而流形学习方法通常计算复杂度较大，对
噪声和算法参数都比较敏感，并且存在所谓的样本溢出问题，例如，当增加新的样本点时，不能快速地提取新特征。 其次是流形或子空间从一个到多个的扩展，即假设数据集采样于多个欧氏空间的混合。子空间聚类（又称为子空间分割，假设数据分布于若干个低维子空间的并）是将数据按某种方式分类到其所属的子空间的过程。通过子空间聚类，可以将来自同一子空间中的数据归为一类，由同类数据又可以提取对应子空间的相关性质。根据综述[2]，子空间聚类的求解方法有代数方法、迭代方法、统计学方法和基于谱聚类的方法。其中基于谱聚类的方法在近几年较为流行，这类方法首先定义一个关于样本点相互关系的图，然后利用Normalized Cut[3]等谱聚类方法（其输入是一个反应样本关系的相似度矩阵，矩阵的第i行j列的数值越大说明第i个样本和第j个样本的关系越密切，如果能将同类样本的相似度构造的较大，不同类的较小，这类方法一般都能得到正确的分类结果）得到分割结果。代表性的基于谱聚类的子空间分割方法包括低秩表示[4]和稀疏表示[5]等，下面对这两种方法的做个简单介绍。 稀疏子空间聚类： 稀疏子空间聚类方法，是对子空间表示系数进行稀疏约束的一类子空间聚类方法。子空间聚类的最终结果是将同一子空间的数据归为一类。在子空间相互独立的情况下，属于某一子空间的数据只由这个子空间的基的线性组合生成，而在其他子空间中的表示系数为零。这样高维数据的表示系数就具有稀疏的特性。同一子空间中的数据，因为都仅在这一子空间中有非零的表示系数，表现为相同的稀疏特性，通过对表示系数稀疏约束的求解，突出了数据表示系数的这种稀疏特性，进而为数据的正确聚类提供支持。
【子空间聚类】Sparse Subspace Clustering(SSC) Algorithm=
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）
基于分布式低秩表示的子空间聚类算法
计算机研究与发展ＤＯＩ：１０．７５４４桙ｉｓｓｎ１０００‐１２３９．２０１６．２０１４８３６２ＪｏｕｒｎａｌｏｆＣｏｍｐｕｔｅｒＲｅｓｅａｒｃｈａｎｄＤｅｖｅｌｏｐｍｅｎｔ５３（７）：１６０５１６１１，２０１６ 收稿日期：２０１４－１２－０９；修回日期：２０１５－０６－０９ 基金项目：国家自然科学基金项目（６１３７３０５５）；江苏省自然科学基金项目（ＢＫ２０１４０４１９）；江苏省高校自然科学研究计划重大项目 （１４ＫＪＢ５２０００１） ＴｈｉｓｗｏｒｋｗａｓｓｕｐｐｏｒｔｅｄｂｙｔｈｅＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａ（６１３７３０５５），ｔｈｅＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＪｉａｎｇｓｕＰｒｏｖｉｎｃｅｏｆＣｈｉｎａ（ＢＫ２０１４０４１９），ａｎｄｔｈｅＭａｊｏｒＰｒｏｇｒａｍｏｆＲｅｓｅａｒｃｈＰｌａｎｏｆｔｈｅＮａｔｕｒａｌＳｃｉｅｎｃｅｉｎＨｉｇｈｅｒＥｄｕｃａｔｉｏｎｏｆＪｉａｎｇｓｕＰｒｏｖｉｎｃｅｏｆＣｈｉｎａ（１４ＫＪＢ５２０００１）． 通信作者：吴小俊（ｗｕ＿ｘｉａｏｊｕｎ＠ｊｉａｎｇｎａｎ．ｅｄｕ．ｃｎ）基于分布式低秩表示的子空间聚类算法 许 凯 吴小俊 尹贺峰 （江南大学物联网工程学院 江苏无锡 ２１４１２２） （ｘｕｋａｉ３４７＠ｓｉｎａ．ｃｏｍ） ＤｉｓｔｒｉｂｕｔｅｄＬｏｗＲａｎｋＲｅｐｒｅｓｅｎｔａｔｉｏｎ‐ＢａｓｅｄＳｕｂｓｐａｃｅＣｌｕｓｔｅｒｉｎｇＡｌｇｏｒｉｔｈｍＸｕＫａｉ，ＷｕＸｉａｏｊｕｎ，ａｎｄＹｉｎＨｅｆｅｎｇ（ＳｃｈｏｏｌｏｆＩｎｔｅｒｎｅｔｏｆＴｈｉｎｇｓＥｎｇｉｎｅｅｒｉｎｇ，ＪｉａｎｇｎａｎＵｎｉｖｅｒｓｉｔｙ，Ｗｕｘｉ，Ｊｉａｎｇｓｕ２１４１２２） Ａｂｓｔｒａｃｔ Ｖｉｓｉｏｎｐｒｏｂｌｅｍｒａｎｇｉｎｇｆｒｏｍｉｍａｇｅｃｌｕｓｔｅｒｉｎｇｔｏｍｏｔｉｏｎｓｅｇｍｅｎｔａｔｉｏｎｃａｎｎａｔｕｒａｌｌｙｂｅｆｒａｍｅｄａｓｓｕｂｓｐａｃｅｓｅｇｍｅｎｔａｔｉｏｎｐｒｏｂｌｅｍ，ｉｎｗｈｉｃｈｏｎｅａｉｍｓｔｏｒｅｃｏｖｅｒｍｕｌｔｉｐｌｅｌｏｗｄｉｍｅｎｓｉｏｎａｌｓｕｂｓｐａｃｅｓｆｒｏｍｎｏｉｓｙａｎｄｃｏｒｒｕｐｔｅｄｉｎｐｕｔｄａｔａ．Ｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ‐ｂａｓｅｄｓｕｂｓｐａｃｅｓｅｇｍｅｎｔａｔｉｏｎａｌｇｏｒｉｔｈｍ（ＬＲＲ）ｆｏｒｍｕｌａｔｅｓｔｈｅｐｒｏｂｌｅｍａｓａｃｏｎｖｅｘｏｐｔｉｍｉｚａｔｉｏｎａｎｄａｃｈｉｅｖｅｓｉｍｐｒｅｓｓｉｖｅｒｅｓｕｌｔｓ．Ｈｏｗｅｖｅｒ，ｉｔｎｅｅｄｓｔｏｔａｋｅａｌｏｎｇｔｉｍｅｔｏｓｏｌｖｅｔｈｅｃｏｎｖｅｘｐｒｏｂｌｅｍ，ａｎｄｔｈｅｃｌｕｓｔｅｒｉｎｇａｃｃｕｒａｃｙｉｓｎｏｔｈｉｇｈｅｎｏｕｇｈ．Ｔｈｅｒｅｆｏｒｅ，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｓａｄｉｓｔｒｉｂｕｔｅｄｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ‐ｂａｓｅｄｓｐａｒｓｅｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ（ＤＬＲＲＳ）．ＤＬＲＲＳａｄｏｐｔｓｔｈｅｄｉｓｔｒｉｂｕｔｅｄｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇｔｏｇｅｔｔｈｅｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘ，ｔｈｅｎｔａｋｅｔｈｅａｂｓｏｌｕｔｅｖａｌｕｅｏｆｅａｃｈｅｌｅｍｅｎｔｏｆｔｈｅｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘ，ａｎｄｒｅｔａｉｎｔｈｅｋｌａｒｇｅｓｔｃｏｅｆｆｉｃｉｅｎｔｓｐｅｒｃｏｌｕｍｎａｎｄｓｅｔｔｈｅｏｔｈｅｒｅｌｅｍｅｎｔｓｔｏ０ｔｏｇｅｔａｎｅｗｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘ．Ｆｉｎａｌｌｙ，ＤＬＲＲＳｐｅｒｆｏｒｍｓｓｐｅｃｔｒａｌｃｌｕｓｔｅｒｉｎｇｏｖｅｒｔｈｅｎｅｗｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘ．Ｂｕｔｉｔｄｏｅｓｎ摧ｔｈａｖｅｉｎｃｒｅｍｅｎｔａｌｌｅａｒｎｉｎｇｆｕｎｃｔｉｏｎ，ｓｏｔｈｅｒｅｉｓａｓｃａｌａｂｌｅｄｉｓｔｒｉｂｕｔｅｄｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ‐ｂａｓｅｄｓｐａｒｓｅｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ（ＳＤＬＲＲＳ）ｈｅｒｅ．Ｉｆｎｅｗｓａｍｐｌｅｓａｒｅｂｒｏｕｇｈｔｉｎ，ＳＤＬＲＲＳｃａｎｕｓｅｔｈｅｆｏｒｍｅｒｃｌｕｓｔｅｒｉｎｇｒｅｓｕｌｔｔｏｃｌａｓｓｉｆｙｔｈｅｎｅｗｓａｍｐｌｅｓｔｏｇｅｔｔｈｅｆｉｎａｌｒｅｓｕｌｔ．ＥｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｏｎＡＲａｎｄＥｘｔｅｎｄｅｄＹａｌｅＢｄａｔａｓｅｔｓｓｈｏｗｔｈａｔｔｈｅｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｓｃａｎｎｏｔｏｎｌｙｏｂｖｉｏｕｓｌｙｒｅｄｕｃｅｔｈｅｒｕｎｎｉｎｇｔｉｍｅ，ｂｕｔａｌｓｏａｃｈｉｅｖｅｈｉｇｈｅｒａｃｃｕｒａｃｙ，ｗｈｉｃｈｖｅｒｉｆｉｅｓｔｈａｔｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｓａｒｅｅｆｆｉｃｉｅｎｔａｎｄｆｅａｓｉｂｌｅ．Ｋｅｙｗｏｒｄｓ ｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ；ｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇ；ｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇ；ｉｎｃｒｅｍｅｎｔａｌｌｅａｒｎｉｎｇ；ｃｏｅｆｆｉｃｉｅｎｔｓｒｅｃｏｎｓｔｒｕｃｔｉｏｎ 摘 要 针对基于低秩表示的子空间分割算法运算时间较长、 聚类的准确率也不够高，提出一种基于分布式低秩表示的稀疏子空间聚类算法（ｄｉｓｔｒｉｂｕｔｅｄｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ‐ｂａｓｅｄｓｐａｒｓｅｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ，ＤＬＲＲＳ），该算法采用分布式并行计算来得到低秩表示的系数矩阵，然后保留系数矩阵每列的前ｋ个绝对值最大系数，其他系数置为０，用此系数矩阵构造一个稀疏的样本关系更突出的相似度矩阵，接着用谱聚类得到聚类结果．但是其不具备增量学习功能，为此再提出一种基于分布式低秩表示的增量式稀疏子空间聚类算法（ｓｃａｌａｂｌｅｄｉｓｔｒｉｂｕｔｅｄｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎｂａｓｅｄｓｐａｒｓｅｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ，ＳＤＬＲＲＳ），如果有新增样本，可以利用前面的聚类结果对新增样本进行
高维复杂数据的子空间挖掘方法研究
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算法将传统对类的表示方法进行了改进，回避了用所有点或用中心和半径来表示一个类，而