用机器学习做靠谱的聚类——谱聚类(Spectral clustering)

前段时间,在参与一个项目的过程中无意间接触到了谱聚类(Spectral clustering)。大神说:这种聚类区别于“系统聚类”和“k-means聚类”等传统聚类方法,它的计算量小、对数据分布的适应性强、聚类效果好,并且通过MATLAB或者sklearn的机器学习算法都能够实现。这么高大上的聚类算法岂是我等线代学渣所能驾驭的?但是,孔子曰:“学渣也要有春天!”,于是我便查阅了大量和谱聚类相关的文章和资料,跋山涉水、翻山越岭之后,还是觉得——孔子说得对啊!

一、谱聚类是啥概念?

谱聚类:是一种基于图论的聚类方法,通过对样本数据的拉普拉斯矩阵的特征向量进行聚类。即把所有的数据看做空间中的点,这些点之间可以用边连接起来。距离较远的两个点之间的边权重值较低,而距离较近的两个点之间的边权重值较高,通过对所有数据点组成的图进行切图,让切图后不同的子图间边权重和尽可能的低,而子图内的边权重和尽可能的高,从而达到聚类的目的。

图论:对于一个图G,一般用点的集合V和边的集合E来描述,即为G(V,E)。其中V即为数据集里面所有的点(v1,v2,...vn)。对于V中的任意两个点,可以有边连接,也可以没有边连接。如下图所示:

拉普拉斯(Laplacian)矩阵:定义拉普拉斯矩阵L=D−W。D为度矩阵,W是邻接矩阵。

那么,度矩阵D是啥?

对于有边连接的两个点Vi和Vj,Wij>0,对于没有边连接的两个点Vi和Vj,Wij=0。对于图中的任意一个点Vi,它的度di定义为和它相连的所有边的权重之和,即:

那么,邻接矩阵又是啥?

由任意两点之间的权重值Wij组成的矩阵。即距离较远的两个点之间的边权重值较低,而距离较近的两个点之间的边权重值较高,因此可以通过样本点距离度量的相似矩阵S来获得邻接矩阵W。构建邻接矩阵W的方法有三类。ϵ-邻近法,K邻近法和全连接法。

  • ϵ-邻近法:即设定一个距离阈值,小于阈值的权重为0,大于阈值的权重为ϵ;

  • K邻近法:取样本点中的k个最邻近点计算权重(又分为单邻近和互邻近)。

  • 全连接法:样本中一个点与其他所有点都连接,并计算相应权重。

最后,上一张L,D,W全家福:

二、切图

当前面的工作都做好了以后,接下来就是做分类,谱聚类分类的方式为“切图”,如图:

切图的原则:同子图内的点相似度高,不同子图的点相似度低。与传统聚类组内离差平方和最小、组间离差平方和最大类似。切图的效果可用损失函数来评价,即划分时子图之间被“截断”的边的权重和:

切图的方法有多种,这里主要介绍Ratio cut和Ncut(Normalized Cut)两种:

n1和n2为划分到子图1和子图2中的顶点个数。

d1和d2分别为子图1和子图2的权重和。
由以上两个公式,结合切图的原则可知,Ncut的方法较好。

综上所述,谱聚类可以理解为:降维过程+其他聚类方法,常用的聚类方法为K-means,需要注意的关键点是邻接矩阵的生成方式、切图的方式和最后的聚类方法

三、实例

本次谱聚类主要使用了python机器学习sklearn里的方法,需要注意的是sklearn库的版本必须在0.18.1以上,否则无法调用metrics调参。由于sklearn的SpectralClustering方法已经把谱聚类的相关算法封装好,所以我们在通晓了以上谱聚类的基本原理之后,再结合sklearn的官方文档调整并设定好SpectralClustering方法中的参数即可。

import pandas as pd  
from sklearn.cluster import SpectralClustering  
from sklearn import metrics  
from sklearn import preprocessing  

输入数据:北京大型商场“均价比较指数”、“户数比较指数”、“母婴店铺比较系数”等8个特征的数据,样本容量为81。

目标:对商场进行聚类。

步骤:
1.先对数据进行标准化处理。
2.调整参数:
此处结合数据分布特点选取了K邻近法来构建邻接矩阵(即affinity=’nearestneighbors’,默认为高斯函数’rbf’),因此需要调整的参数为“nclusters”和“n_neighbors”。做循环之后结果如下:

通过调参,可以看出在nneighbors=11且nclusters=4时,Calinski-Harabasz Score最大,因此nneighbors设为11,nclusters设为4,其他参数为默认即可(默认聚类方式为k-means,切图方式为N-cut)。

y_pred=SpectralClustering(affinity='nearest_neighbors',n_clusters=4, n_neighbors=11).fit_predict(X)  

3.分类结果:

注意:每次运行程序,可能分类的标签不一样(即0-3的标签是随机的),但是聚类结果都是一样的。

GeoHey上图:

参考资料:

http://www.cnblogs.com/pinard/p/6235920.html

http://scikit-learn.org/stable/index.html

zhuxh

继续阅读此作者的更多文章