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中惠勒，為了構造稀疏關聯(lián)子矩陣，提出了一種混合代表選擇策略和K近鄰代表的快速逼近方法。將稀疏子矩陣解釋為二部圖，利用轉移割（transfer cut）對圖進行有效劃分，得到聚類結果阱飘。

在U-SENC中，多個U-SPEC聚類器被進一步集成到一個集成聚類框架中，以增強U-SPEC的魯棒性剖煌，同時保持較高的效率材鹦。基于多U-SEPC的集成生成耕姊，在目標和基簇之間構造一個新的二部圖桶唐，并對其進行有效劃分，以達到一致的聚類結果茉兰。

Introduction

問題：傳統(tǒng)譜聚類需要 $O(N^2 d)$ 的時間復雜度和 $O(N^2)$ 的空間復雜度來建立關聯(lián)矩陣尤泽、需要 $O(N^3)$ 的時間復雜度和 $O(N^2)$ 的空間復雜度來解決特征值分解問題。
減輕譜聚類的巨大計算負擔的方法：
- 策略一：稀疏化關聯(lián)矩陣规脸。利用稀疏特征值求解器[2]來解決特征值分解問題坯约。
  - 存在問題：矩陣稀疏化策略可以降低存儲關聯(lián)矩陣的內存成本，促進特征值分解莫鸭，但仍需要計算原關聯(lián)矩陣中的所有項闹丐。
- 另一個策略：子矩陣構造
  - [3] Nystr?m method：隨機選出p個代表構造 $N \times p$ 的關聯(lián)子矩陣
  - [4] landmark based spectral clustering：在數(shù)據(jù)集上執(zhí)行k-means以獲得p個聚類中心作為這P個代表點。
    - 存在問題：
      - 復雜度為 $O(N \times p)$ 黔龟，但是當處理極大的數(shù)據(jù)集時妇智，為了實現(xiàn)更好的近似，p也會很大氏身。
      - 聚類結果嚴重依賴于通過子矩陣的一次近似(one-shot approximation)巍棱，聚類的魯棒性有不穩(wěn)定因素。

因此如何使譜聚類能夠在相當有限的計算資源下高效蛋欣、魯棒地聚類非常大的數(shù)據(jù)集(甚至可能是非線性可分的)仍然是一個極具挑戰(zhàn)性的問題航徙。

本文提出兩種方法：

U-SPEC：混合代表點選擇策略來選擇p個代表點。將基于k均值的選擇策略的時間復雜度從 $O(Npdt)$ 降到 $O(p^2dt)$ 陷虎。
- 在此基礎上到踏，設計了一種K最近鄰的快速逼近方法，有效地構造了一個具有 $O(Np^{\frac{1}{2}}d)$ 時間和 $O(Np^{\frac{1}{2}})$ 內存的稀疏子矩陣尚猿。
- 利用稀疏子矩陣作為交叉關聯(lián)矩陣窝稿，在數(shù)據(jù)集和代表點集之間建立二部圖。
- 通過二部圖結構凿掂，用transfer cut[6]來求解特征值分解問題伴榔，時間復雜度為 $O(NK(K + k) + p^3 )$ ，其中k為簇的個數(shù)庄萎，K為最接近的代表數(shù)踪少。
- 最后，采用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聚類結果集成到一個統(tǒng)一的集成聚類框架中绕娘，其時間和空間復雜度分別為 $O(Nmp^{\frac{1}{2}}d)$ 和 $O(Np ^{\frac{1}{2}})$ 脓规。
貢獻：
- 1)混合代表點選擇策略栽连，在隨機選擇的效率和基于k均值的選擇的有效性之間取得平衡。
- 2)設計了一種K -最近鄰表示的快速逼近方法侨舆，該方法對于構造對象與代表點之間的稀疏關聯(lián)子矩陣秒紧，在時間和空間上都非常有效率。
- 3)提出了一種基于有效關聯(lián)子矩陣構造和二部圖的大規(guī)模譜聚類算法U-SPEC挨下。其時間復雜度和空間復雜度分別為 $O(Np^{\frac{1}{2}}d)$ 和 $O(Np^{\frac{1}{2}})$ 熔恢。
- 4)通過集成多個U-SPEC聚類器，提出一種新的大規(guī)模集成聚類算法U-SENC臭笆，該算法在保持高可擴展性的同時叙淌，顯著提高了U-SPEC的魯棒性。它的時間和空間復雜度分別為 $O(Nmp^{\frac{1}{2}}d)$ 和 $O(Np ^{\frac{1}{2}})$ 愁铺。

Related work

2.1 spectral clustering

傳統(tǒng)譜聚類
- 時間復雜度： $O(N^3)$ 鹰霍，空間復雜度： $O(N^2)$
稀疏關聯(lián)矩陣，通過K-近鄰茵乱，然后使用sparse eign-solver求特征值分解茂洒。
- 在這里插入圖片描述
- 在這里插入圖片描述
- 問題：但是仍然需要計算原始關聯(lián)矩陣中的所有項。
sub-matrix based approximation 避免計算整個的affinity matrix
- Nystrom ：
  - 隨機選擇p個錨點瓶竭，構造 $N \times p$ 的子矩陣
  - 子矩陣構造：時間復雜度 $O(Npd)$ 空間復雜度 $O(Np)$

[PED04]Ultra-Scalable Spectral Clustering and Ensemble Clustering

[PED04]Ultra-Scalable Spectral Clustering and Ensemble Clustering

Ultra-Scalable Spectral Clustering and Ensemble Clustering

疑問

摘要

Introduction

Related work

2.1 spectral clustering