Data Mining Course Paper Reading

DataMining

1. Robust Spectral Clustering

• 出发点
  谱聚类对输入的数据噪声非常敏感
  提出Robust Spectral Clustering

• 主要思想
  观察到的相似矩阵并不是足够好的，被误差所影响了其本身的性质。
  假设相似矩阵由两个隐藏部分组成：clean data成分 和 腐败成分(corruption)。
  实际中，腐败成分的分布是稀疏的。基于此，目标是优化Laplacian矩阵的特征向量空间。
  首次提出这个论点的工作。

• 相关工作
  很多方法以前都被提出过，用以增强谱聚类在各方面的稳定性。但是这些方法大多是基于全连接的图来实现的。
  这些方法有，对数据进行局部相似度缩放；对数据作拉普拉斯平滑；数据截断，设法将噪声检测出来并去除(与本文相似)；对特征进行权重分配。
  上述这些方法都分成了两步：先构造一个性质更好的相似矩阵，然后利用传统的谱聚类的方法进行聚类。

2. FUSE：Full Spectral Clustering

• abstract
  多尺度的数据分类由于其本身数据尺度和密度的不同，对于谱聚类而言，是很难的一种任务。这篇文章是基于幂迭代和独立成分分析(Independent Components Analysis)来试图解决这个问题的。
  幂迭代的方法是将所有的特征向量融合、转化为一个伪逆(pseduo-eigenvector),并在这个过程中保证数据类别信息的完整性。
  论文大致的方法是产生充足数量的伪逆，然后利用ICA变换使其两两独立，为了使ICA克服局部最小值的困扰，采用一个可以自我调节和自我学习的贪婪搜索算法来寻找最优解。这也是首次将ICA应用到谱聚类中。
  Full是指这个算法使用了相似矩阵的所有特征向量。

• related works

  • 谱聚类
    可以按照使用的Laplacian Matrix种类来分类
    unnormalized谱聚类
    normalized谱聚类 (2000年，Ncut)
    另一种谱聚类(2002年，NJW)
    得到Laplacian矩阵之后，计算前k个特征向量，然后利用k-means来进行聚类。得到最后的聚类结果。
    谱聚类算法的实现中，我们相信这前k个特征向量较为完整的包含了样本的分类信息。这也是算法的推导过程告诉我们的。这促使很多研究人员在合适的特征向量个数(越多计算成本越)与它们所携带的分类信息的最大化之间寻找一个平衡。

3. Spectral Ensemble Clustering(SEC)

• Abstract
  组合聚类，就是利用多个不同来源的聚类结果组合得出最后的聚类结果。基于相似矩阵的方法，将组合聚类问题转化为了一个经典的图切问题，是划时代的一个方法。

• Introduction
  基于相似矩阵的聚类方法，虽然有很多优点，但是也有一些限制，比如，在处理大尺度的数据时所产生的高额运算量和空间开销，而且这种方法往往也没有明确的目标函数去监督学习的过程。
  为了解决以上提到的两个限制，我们提出了谱聚合聚类，能够有效的较小时间复杂度和空间复杂度，粗略的计算，能够减少两个量级。

• 算法贡献
  提出了谱聚合聚类。揭示了这种算法和权重lk-means之间的关系，推导出了其内在的目标函数。

4. Locally-Scaled Spectral Clustering using Empty Region Graphs

• Abstract
  介绍了一种新的方法来预测样本点的邻居和样本数据集的尺度以提高谱聚类算法的稳定性。

• Introduction

  • 谱聚类被广泛应用，但还是存在一些问题
    1) 如何定义样本点的邻居以获得较好的相似矩阵
    2) 如何使得算法适应数据局部尺度或者密度的变化
    3) 如何自动的选择最后聚类的类的数目
    这篇文章集中在前两个问题。
    最常用的构图方法

  • k近邻(K nearest neighbor graph)或者$\varepsilon-graph$，都利用了数据的密度信息。
    聚类结果可能会随着k或者$\varepsilon$的改变而剧烈变化。当样本点太过于稀疏的时候，聚类的结果可能会演化为单个的个体样本点。
    全连接图，可以视为$\varepsilon-graph$的一个特例。

  • 这篇论文的方法
    通过探索空的区域图(Empty Region Graphs，ERGs)来找寻样本点的邻居，不同于KNN图没有考虑样本点的空间分布关系，ERGs考虑到了样本点之间的空间分布，这种方法有效的提升了谱聚类的精度(accuracy)。

• Related Work

  • Empty Region Graphs
    有很多种构图方法，相关研究也说明构图的质量对最终的分类结果有很大影响。
    relative neighborhood graph，the Gabriel graph，$\beta$-skeleton，$\sigma$-local graph等。
    ERGs定义了一个近邻图，这个图中，当一些点构成的封闭几何区域中，除了两个近邻点外并不包含其他的点，那么这两个点就是连接的(connected)。