Skip to content

Spectral Clustering(谱聚类)

Abstract

This article isn't finished yet...

Graph Partitioning

Bi-partitioning task

Minmal-cut

Normalized-cut

Criterion: Normalized-cut [Shi-Malik, '97]

Define: Connectivity between groups relative to the density of each group

ncut(A,B)=cut(A,B)vol(A)+cut(A,B)vol(B)

vol(A) : total weight of the edges with at least one endpoint in A :

vol(A)=iAki

The purpose of this criterion is to produce more balanced partitions.

Spectral Graph Theory:

Analyze the "spectrum" of matrix(s) representing G

Spectrum: Eigenvectors xi of a graph, ordered by the magnitude(strength) of their corresponding eigenvalues λi :

Λ={λ1,λ2,,λn}λ1λ2λn

Abstract

d-regular : the degree of each vertex in the graph is d

If G is not connected, for example, G has 2 components, each d-regular.

Abstract

每一个特征向量表现了图的划分方式

What are some eigenvectors?

Spectral Partitioning Algorithm

算法流程

Pre-processing

根据图构建拉普拉斯矩阵 L

Decomposition

*分解

L 的第 2 小的特征值 λ1 (λ0=0) 和特征向量 q1

Grouping

n 维向量 q1n 个参数对应到 n 个顶点,可以画图,将参数作为纵坐标,顶点标号作为横坐标,结合图像进行分组(grouping)