谱聚类Spectral clustering(SC)
在之前的文章里，介绍了比较传统的K-Means聚类、Affinity Propagation(AP)聚类、比K-Means更快的Mini Batch K-Means聚类以及混合高斯模型Gaussian Mixture Model(GMM)等聚类算法，今天介绍一个比较近代的一类算法——Spectral Clustering 中文通常称为“谱聚类”。
Spectral Clustering（谱聚类，有时也简称SC），其实是一类算法的统称。它是一种基于图论的聚类方法（这点上跟AP类似，而K-Means是基于点与点的距离计算），它能够识别任意形状的样本空间且收敛于全局最有解，其基本思想是利用样本数据的相似矩阵进行特征分解后得到的特征向量进行聚类。
为什么上文称谱聚类是“一类”算法？广义上来说，任何在演算法中用到SVD/特征值分解的，都叫Spectral Algorithm。
谱聚类和传统的聚类方法（如 K-means）相比有不少优点：
- Spectral Clustering 只需要数据之间的相似度矩阵就可以了，而不必像 K-Means 那样要求数据必须是 N 维欧氏空间中的向量。
- 由于抓住了主要矛盾，忽略了次要的东西，因此比传统的聚类算法更加健壮一些，对于不规则的误差数据不是那么敏感，而且结果也要好一些。事实上，在各种现代聚类算法的比较中，K-means 通常都是作为一个基准而存在的。
- 计算复杂度比 K-means 要小，特别是在像文本数据或者平凡的图像数据这样维度非常高的数据上运行的时候，理论上应该比K-Means更快速。（是这样吗？下文实验中有解答！）
K-Means一直以来都是距离算法中的经典算法，尤其通过minibatch“改良”后的K-Means在大数据应用中的效率瓶颈也得到极大改善。谱聚类这个相对的“晚生”是否真的如上述优点，接下来看实验数据。
实验一 关于准确度的较量
在此引用 Document clustering using locality preserving indexing 中关于K-means 和 Spectral Clustering 应用到TDT2 和 Reuters-21578这两组数据的准确率对比结果：
| k | TDT2 | Reuters-21578 | ||
| K-Means | 谱聚类 | K-Means | 谱聚类 | |
| 2 | 0.989 | 0.998 | 0.871 | 0.923 |
| 3 | 0.974 | 0.996 | 0.775 | 0.816 |
| 4 | 0.959 | 0.996 | 0.732 | 0.793 |
| … | ||||
| 9 | 0.852 | 0.984 | 0.553 | 0.625 |
| 10 | 0.835 | 0.979 | 0.545 | 0.615 |
从准确率结果可以看出，在不同的类别数量下，谱聚类的准确率都要高于K-Means。
实验二 关于运行时间的较量
在此使用Python机器学习库SKlearn中的spectral_clustering进行模拟实验，实验数据为随机生成的维度和样本量相同的矩阵，分别为10维、20维、30维。40维、50维、60维，对应到图中就是从0到5。其实我试着用更大的数据量去实验，但增加到70维的时候，spectral_clustering已经由于内存错误而崩掉了，所以足以看来他对于大数据量的应用还是不适合的。
另外，对于上文提到的spectral_clustering的计算复杂度要低于K-Means，因此理论上的运算时间要快，但实验结果却不能证明这个问题。大家可以点击原始程序查看 sc_kemans.py。
谱聚类应用
以下使用Python机器学习库SKlearn中的spectral_clustering进行聚类，目标是从一个图片中区分出人为构造出的图像边缘。
- #coding:utf-8
- import numpy as np
- import matplotlib.pyplot as plt
- from sklearn.feature_extraction import image
- from sklearn.cluster import spectral_clustering
- # 生成原始图片信息
- l = 100
- x, y = np.indices((l, l))
- center1 = (28, 24)
- center2 = (40, 50)
- center3 = (77, 58)
- radius1, radius2, radius3 = 16, 14, 15
- circle1 = (x - center1[0]) ** 2 + (y - center1[1]) ** 2 < radius1 ** 2
- circle2 = (x - center2[0]) ** 2 + (y - center2[1]) ** 2 < radius2 ** 2
- circle3 = (x - center3[0]) ** 2 + (y - center3[1]) ** 2 < radius3 ** 2
- # 生成包括3个圆的图片
- img = circle1 + circle2 + circle3
- mask = img.astype(bool)
- img = img.astype(float)
- img += 1 + 0.2 * np.random.randn(*img.shape)
- graph = image.img_to_graph(img, mask=mask)
- graph.data = np.exp(-graph.data / graph.data.std())
- # 聚类输出
- labels = spectral_clustering(graph, n_clusters=3)
- label_im = -np.ones(mask.shape)
- label_im[mask] = labels
- plt.matshow(img)
- plt.matshow(label_im)
- plt.show()
以下是运行结果：
左边的图形是人为生成的原始图片，右边是识别图形边缘后的处理图片。
spectral_clustering可配置的参数如下，其中最主要的参数是affinity（数据集）, n_clusters（聚类数）和assign_labels（聚类方法可选kmeans[默认], discretize）：
- sklearn.cluster.spectral_clustering(affinity, n_clusters=8, n_components=None, eigen_solver=None, random_state=None, n_init=10, eigen_tol=0.0, assign_labels='kmeans')
谱聚类的应用场景：
- 图像切割；
- 数据聚类
尾巴
谱聚类适用的数据集有几个特点：
- 不适合聚类类别数特别多的数据；
- 对于特殊数据集具有比较好的适应性，例如环形数据、非凸数据、交叉数据等非正常或规则下的数据，如下图：
====================【好书推荐，我为自己代言】====================
《Python数据分析与数据化运营》上市啦！
本书主要基于Python实现，其中主要用到的计算库是numpy、pandas和sklearn，其他相关库还包括：
- 标准库：re、time、datetime、json、 base64、os、sys、cPickle、tarfile
- 统计分析：Statsmodels
- 中文处理：结巴分词
- 文本挖掘：Gensim
- 爬虫和解析：requests、Beautiful Soup、xml
- 图像处理：OpenCV和PIL
- 数据读取：xlrd、pymongo、mysql.connector
- 数据预处理：imblearn
- 展示美化类：Matplotlib、graphviz、prettytable、wordcloud、mpl_toolkits、pydotplus
- KMeans聚类的自动K均值的确立方法
- 基于软方法的多分类模型组合评估模型的应用
- 基于自动下探（下钻、细分）的应用
- 基于增量学习的多项式贝叶斯分类
- pipeline管道技术的应用
- 基于超参数的自动参数值的优化方法
- 特征自动选择
- 文本分类、文本主题挖掘
- 基于自动时间序列ARIMA的P、D、Q的调整
- python决策树规则输出
- 基于自定义图像的文本标签云
- 非结构化数据，例如图像、音频、文本等处理
- 对象持久化处理
