子空间聚类

姓名：贺文琪

学号：19021210758

【嵌牛导读】聚类分析是数据挖掘领域中的关键技术之一。高维数据聚类是聚类分析技术的难点和重点，子空间聚类是实现高维数据集聚类的有效途径，它是在高维数据空间中对传统聚类算法的一种扩展，其思想是将搜索局部化在相关维中进行。

【嵌牛鼻子】子空间聚类

【嵌牛提问】子空间聚类有哪些方法？各自的特点是什么？

【嵌牛正文】 

目前存在的子空间聚类算法主要分成四大类：基于迭代的方法，基于代数的方法，基于统计的方法和基于谱聚类的方法。

基于迭代的方法。主要有两个步骤。第一步是将样本点分配到对应的子空间中以及第二步是将每个子空间适配到对应的聚类。这两步交替迭代进行直到收敛。这种方法不仅对初始化要求敏感而且很容易得到的是一个局部解。此外，这些方法通常需要知道子空间的维数和数量。基于迭代统计的方法，作为一种迭代方法，也包含这两步。这些算法假设每个子空间中的数据样本分布符合高斯分布并且在上述两个步骤中通过使用最大期望方法交替执行。同样地，基于迭代统计的方法也具有一般的基于迭代的方法的缺点。

基于代数的方法。基于因式分解的代数方法尝试着寻找两个矩阵，这两个矩阵的积接近于给定的数据矩阵，使得其中一个系数矩阵的支持模式提供样本的分割。当子空间是独立的时候，这些方法能够正确地聚类数据样本，但是当子空间是独立的这一条件违反的时候，就不能够得到正确的聚类结果。而且，他们对数据里面的噪声和异常值非常敏感。为了处理这些噪声和异常值，将额外的正则项被加进来改进这些算法。

基于统计的方法。基于统计的方法能够进一步地被分成一些种类，例如基于迭代统计的方法，鲁棒的统计方法以及基于信息理论的统计方法。基于迭代统计的方法也可以看作是基于迭代的方法并且已经被讨论过。结块的有损压缩算法（ALC），作为一种基于信息理论的统计方法，假定数据来自退化的高斯的混合。能够自然地处理数据中的噪声和异常值。并且它不需要知道子空间的数量和维度。然而，通过算法得到的子空间的数量与变形参数密切相关。随机样本一致算法(RANSAC)能够明确地处理噪声和异常值。此外，RANSAC并不需要提前知道子空间的数量。然而，子空间的维数必须是知道的。同时，算法的复杂度随着子空间的数量和维度呈指数增长。

基于谱聚类的方法。基于谱聚类的方法首先构建一个数据样本间的相似度矩阵，然后对这个相似度矩阵使用谱聚类从而得到数据的聚类结果。基于谱聚类的方法一般分成两种类型：基于局部谱聚类的方法和基于全局的谱聚类的方法。基于局部谱聚类的方法如局部子空间邻接矩阵(LSA)，局部线性流形聚类(LMMC)以及局部最佳适合平面(SLBF)，使用每个点附近的局部信息来构建数据点对之间的相似矩阵。基于全局谱聚类的方法尝试通过使用全局信息来构建数据点之间的更加合理的相似度矩阵从而克服这些困难。