[PED04]Ultra-Scalable Spectral C

2020-06-01 本文已影响0人张小甜甜

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)$

[PED04]Ultra-Scalable Spectral C

Ultra-Scalable Spectral Clustering and Ensemble Clustering

疑问

摘要

Introduction

Related work

2.1 spectral clustering

猜你喜欢

热点阅读