查看“︁谱聚类”︁的源代码

{{expand english|time=2022-01-01}}
在[[多元变量统计]]中，'''谱聚类'''（{{lang-en|spectral clustering}}）技术利用数据[[相似矩陣|相似矩阵]]的[[矩阵的谱|谱]]（[[特征值和特征向量|特征值]]），在对数据进行[[降维]]后，以较少的维度进行聚类。相似矩阵作为输入，提供了对数据集中每一对点相对相似性的定量评估。

在图像分割中，谱聚类被称为基于分割的物体分类。

== 算法 ==

; 基本算法

# 计算[[拉普拉斯矩阵]] <math>L</math> （或归一化的拉普拉斯矩阵）
# 计算前 <math>k</math> 个特征向量（这些特征向量对应 <math>L</math> 的 <math>k</math> 个最小的特征值）
# 考虑由这 <math>k</math> 个特征向量组成的矩阵，矩阵的第 <math>l</math> 行定义了图节点 <math>l</math> 的特征
# 根据这些特征对图节点进行聚类（例如使用[[k-均值聚类]]）

大型图的（归一化）拉普拉斯矩阵通常是病态的（ill-conditioned，即高[[条件数]]），这会减缓迭代求解的收敛速度。{{Link-en|预处理|Preconditioner#Preconditioning_for_eigenvalue_problems}}（Preconditioning）可以加速收敛。通过首先确定结构，然后对群落进行聚类，谱聚类可以成功应用于大型图。<ref>{{cite journal |last=Zare |first=Habil |author2=P. Shooshtari |author3=A. Gupta |author4=R. Brinkman |date=2010 |title=Data reduction for spectral clustering to analyze high throughput flow cytometry data |journal=BMC Bioinformatics |volume=11 |pages=403 |doi=10.1186/1471-2105-11-403 |pmc=2923634 |pmid=20667133}}</ref>

谱聚类与[[非线性降维]]密切相关，[[非线性降维#局部线性嵌入|局部线性嵌入]]（Locally-linear embedding）等降维技术可用于减少噪声或异常值的误差。<ref>{{Citation|author=Arias-Castro, E. and Chen, G. and Lerman, G.|title=Spectral clustering based on local linear approximations.|journal=Electronic Journal of Statistics|volume=5|pages=1537–1587|year=2011|doi=10.1214/11-ejs651|arxiv=1001.1323|s2cid=88518155}}</ref>

== 软件 ==
有不少大型开源项目实现谱聚类，包括Scikit-learn<ref>{{Cite web |title=2.3. Clustering |url=http://scikit-learn.org/stable/modules/clustering.html#spectral-clustering |access-date=2022-08-07 |archive-date=2015-05-15 |archive-url=https://web.archive.org/web/20150515083951/http://scikit-learn.org/stable/modules/clustering.html#spectral-clustering |dead-url=no }}</ref>（使用带有多网格预处理（multigrid method）或ARPACK的LOBPCG算法），[[Apache Spark|MLlib]]（使用幂迭代法，Power iteration method）进行伪特征向量聚类<ref>{{Cite web |title=Clustering - RDD-based API - Spark 3.2.0 Documentation |url=http://spark.apache.org/docs/latest/mllib-clustering.html#power-iteration-clustering-pic |access-date=2022-08-07 |archive-date=2017-07-03 |archive-url=https://web.archive.org/web/20170703043350/http://spark.apache.org/docs/latest/mllib-clustering.html#power-iteration-clustering-pic |dead-url=no }}</ref>，以及[[R语言|R]]<ref>{{Cite web |date=12 November 2019 |title=Kernlab: Kernel-Based Machine Learning Lab |url=https://cran.r-project.org/web/packages/kernlab |access-date=2022-08-07 |archive-date=2017-06-27 |archive-url=https://web.archive.org/web/20170627104701/https://cran.r-project.org/web/packages/kernlab/ |dead-url=no }}</ref>。

== 和其它聚类算法的关系 ==
谱聚类算法它可以在核聚类方法的背景下进行描述，这顯示了它与其他方法的相似之处。<ref name="filippone2008survey">{{cite journal |author=Filippone M., Camastra F., Masulli, F., Rovetta, S. |date=January 2008 |year=2008 |title=A survey of kernel and spectral methods for clustering |url=http://eprints.whiterose.ac.uk/8536/2/Filippone_spectral_methodspr08.pdf |journal=Pattern Recognition |volume=41 |issue=1 |pages=176–190 |bibcode=2008PatRe..41..176F |doi=10.1016/j.patcog.2007.05.018 |access-date=2022-08-07 |archive-date=2022-08-16 |archive-url=https://web.archive.org/web/20220816064929/https://eprints.whiterose.ac.uk/8536/2/Filippone_spectral_methodspr08.pdf |dead-url=no }}</ref>

=== 和k-means聚类算法的关系 ===
加权核K-means问题与谱聚类问题的目标函数相同，可以通过多级方法直接优化。

== 参考资料 ==
{{Reflist}}


[[Category:代数图论]]
[[Category:聚类分析]]