Ultra-Scalable Spectral Clustering and Ensemble Clustering

来源： TKDE
作者：Dong Huang, Chang-Dong Wang,等

疑问

二部图
transfer cut

摘要

提出两个算法：

• ultra-scalable spectral clustering (U-SPEC)
• ultra-scalable ensemble clustering (U-SENC)

在U-SPEC中，为了构造稀疏关联子矩阵，提出了一种混合代表选择策略和K近邻代表的快速逼近方法。将稀疏子矩阵解释为二部图，利用转移割（transfer cut）对图进行有效划分，得到聚类结果。

在U-SENC中，多个U-SPEC聚类器被进一步集成到一个集成聚类框架中，以增强U-SPEC的鲁棒性，同时保持较高的效率。基于多U-SEPC的集成生成，在目标和基簇之间构造一个新的二部图，并对其进行有效划分，以达到一致的聚类结果。

Introduction

• 问题：传统谱聚类需要 $O(N^2 d)$的时间复杂度和$O(N^2)$ 的空间复杂度来建立关联矩阵、需要$O(N^3)$的时间复杂度和$O(N^2)$的空间复杂度来解决特征值分解问题。
• 减轻谱聚类的巨大计算负担的方法：
  • 策略一：稀疏化关联矩阵。利用稀疏特征值求解器[2]来解决特征值分解问题。
    • 存在问题：矩阵稀疏化策略可以降低存储关联矩阵的内存成本，促进特征值分解，但仍需要计算原关联矩阵中的所有项。
  • 另一个策略：子矩阵构造
    • [3] Nyström method：随机选出p个代表构造$N \times p$的关联子矩阵
    • [4] landmark based spectral clustering：在数据集上执行k-means以获得p个聚类中心作为这P个代表点。
      • 存在问题：
        • 复杂度为$O(N \times p)$，但是当处理极大的数据集时，为了实现更好的近似，p也会很大。
        • 聚类结果严重依赖于通过子矩阵的一次近似(one-shot approximation)，聚类的鲁棒性有不稳定因素。

因此如何使谱聚类能够在相当有限的计算资源下高效、鲁棒地聚类非常大的数据集(甚至可能是非线性可分的)仍然是一个极具挑战性的问题。

本文提出两种方法：

• U-SPEC：混合代表点选择策略来选择p个代表点。将基于k均值的选择策略的时间复杂度从$O(Npdt)$降到$O(p^2dt)$。

  • 在此基础上，设计了一种K最近邻的快速逼近方法，有效地构造了一个具有$O(Np^{\frac{1}{2}}d)$时间和$O(Np^{\frac{1}{2}})$内存的稀疏子矩阵。
  • 利用稀疏子矩阵作为交叉关联矩阵，在数据集和代表点集之间建立二部图。
  • 通过二部图结构，用transfer cut[6]来求解特征值分解问题，时间复杂度为$O(NK(K + k) + p^3 )$，其中k为簇的个数，K为最接近的代表数。
  • 最后，采用k-均值离散化方法构造了一组k个特征向量的聚类结果，花费了$O(Nk^2t)$时间。
  • 一般认为，k, k <p <N(远小于)，我们的U-SPEC算法的时间和空间复杂度分别为$O(Np^{\frac{1}{2}}d)$和$O(Np^{\frac{1}{2}})$。
  • 此外，为了改进U-SPEC的一次性近似，提供更好的聚类鲁棒性，U-SENC算法将多个U-SPEC聚类结果集成到一个统一的集成聚类框架中，其时间和空间复杂度分别为$O(Nmp^{\frac{1}{2}}d)$和$O(Np ^{\frac{1}{2}})$。

• 贡献：

  • 1)混合代表点选择策略，在随机选择的效率和基于k均值的选择的有效性之间取得平衡。
  • 2)设计了一种K -最近邻表示的快速逼近方法，该方法对于构造对象与代表点之间的稀疏关联子矩阵，在时间和空间上都非常有效率。
  • 3)提出了一种基于有效关联子矩阵构造和二部图的大规模谱聚类算法U-SPEC。其时间复杂度和空间复杂度分别为$O(Np^{\frac{1}{2}}d)$和$O(Np^{\frac{1}{2}})$。
  • 4)通过集成多个U-SPEC聚类器，提出一种新的大规模集成聚类算法U-SENC，该算法在保持高可扩展性的同时，显著提高了U-SPEC的鲁棒性。它的时间和空间复杂度分别为$O(Nmp^{\frac{1}{2}}d)$和$O(Np ^{\frac{1}{2}})$。

Related work

2.1 spectral clustering

• 传统谱聚类
  • 时间复杂度：$O(N^3)$，空间复杂度：$O(N^2)$
• 稀疏关联矩阵，通过K-近邻，然后使用sparse eign-solver求特征值分解。
  • 
  • 
  • 问题：但是仍然需要计算原始关联矩阵中的所有项。
• sub-matrix based approximation 避免计算整个的affinity matrix
  • Nystrom ：
    • 随机选择p个锚点，构造$N \times p$的子矩阵
    • 子矩阵构造：时间复杂度$O(Npd)$ 空间复杂度$O(Np)$