谱聚类

前面, 我们介绍了Laplace图算子 (参考 “Love Plus 矩阵” ),谱聚类spectral clustering 基本思想已经成立了,我们再概述一下算法本身, 基于翻译 Charles H Martin, PhD 的 Spectral Clustering: A quick overview 。

谱聚类 Spectral Clustering 概述

我的很多关于机器学习的想法都源于量子力学微扰理论(Quantum Mechanical Perturbation Theory),因此在介绍它们之前,我们有必要先回顾一下机器学习中的相关概念。例如机器学习中的谱聚类技术,本质上与量子力学光谱学是一致的。同往常一样,我会用几篇博客来阐述这个话题。

或许不久, 我将会对这部分内容重写,在其中加入对 Robust andScalable Graph-Based Semisupervised Learning http://www.ee.columbia.edu/ln/dvmm/publications/12/IEEE_Semisupervise.pdf 这一文章的的综述。

谱聚类(又称子空间聚类)

谱聚类作为一种聚类方法,目的是聚类空间分布上连通(connected), 但并不要求数据具有紧密聚集(compact)或者具有凸边界的聚集(clustered)的特征。

基本思想如下:

1. 将数据映射到n维空间

2. 定义关联矩阵(affinity matrix)A , 可以使用高斯核 K, 或直接使用邻接矩阵(例如, Aij = δij )

3. 基于邻接矩阵A, 构造图拉普拉斯算子(例如, 是否要选择归一化)

4. 求解特征值问题 , 例如Lv = λv (或广义特征值问题Lv = λDv )

5. 选择最小(或最大)的k个特征值(λ 1...k)所对应的特征向量 (v 1...k) , 从而定义出k维的子空间P^T L P

6. 在这个k维子空间上进行聚类,例如使用k-means算法

关联affinities 和相似 similarities

关联是衡量空间中两点间距离的指标,我们必须猜测相应尺度, 或者学习相应尺度。下面, 我们需要猜测相应尺度。注意,这里使用的并不是标准的欧氏距离,另一个最简单的选择,自然就是高斯核。

给定空间中的2个点 xi 和 xj (在Rn空间里投影),可以定义它们的关联度Aij 。这一指标具有正值和对称性,其数值大小依赖于两点的欧氏距离|| xi - xj ||。

可以进一步设定硬切的阈值R,将相似度变为0, 如果超过R,即:

在一些具体应用中,会对相似度矩阵左乘一个特征亲密度核feature affinity kernal (参见Shi 和 Malik的图像分割工作)。

(也可直接从数据中自动学习 出相似度矩阵。例如Bach和Jordan的Learning Spectral Clustering http://www.di.ens.fr/~fbach/nips03_cluster.pdf )。

显然,

当两个数据点在Rn空间中,十分靠近时 。反之,

, 当它们相距很远时。距离近的点应聚在同一类中,而不同类间的点应有较远的距离。然而,同一类中两数据点间的距离也可能很远,有时甚至比不同类的两个数据点间更远。我们的目标就是对空间进行变换,使得任意两点距离很近时,它们总是属于同一个类,而相距很远的点, 要属于不同的类。

一般情况下我们可以直接使用高斯核K ,或者构造图拉普拉斯算子A。在物理学中,通常将图拉普拉斯算子视为对物理上的拉普拉斯算子Laplacian或拉普拉斯-贝尔特拉米操作符Laplace-Beltrami operator的离散化近似。

在这里,我想指出的是高斯核K与邻接矩阵A的关系。对高斯核进行最低阶泰勒展开可得到:

非归一化图拉普拉斯算子被定义为两个矩阵的差:

其中D是一个对角阵,每个对角元素Dij,记录图中各个顶点的度数, W是一个非负矩阵,Wij记录图中各条边的权重。求L与向量x的期望值(命题1, von Luxburg)

当使用邻接矩阵A时,各条边的权重均为1:

可以看到,忽略对角线元素和某些归一化的话,图拉普拉斯算子就是一个邻接矩阵, 那就是对高斯核的一个低阶近似。而当xi和xj属于同一类时,那就是一个很好的近似。

真实世界中,为了应付数据中的不规则部分, 通常使用高斯核Gaussian kernel或热核heat kernel,这可以参见 SciKit learn package中的实现方法

(http://scikit‑learn.org/stable/modules/clustering.html) 。

拉普拉斯图算子

就字面而言, 拉普拉斯算子多种多样, 归一化的normalized, 广义的generalized, 松弛的relaxed, 等等。

他们都共有一个度数矩阵D, 这是一个对角阵, 描述每个顶点的度数。

作为一个年长的物理化学家, 我认为这是一个亲密度的本地(最近邻)平均场(mean-field)的均值。 D是一个归一因子, 来对邻接矩阵A进行修正, 使得聚类的亲密度, 在不同聚类之间达到均衡。 如果从后续的拆分图来看, 会更加容易理解。

下面,我们对它进行定义,并且给定一些扩展。 核心是, 如何进行归一化, 来设定邻接矩阵的对角线。

  1. 简易拉普拉斯算子 L = D - A
  2. 归一化的普拉斯算子
  1. 广义的普拉斯算子
  1. 松弛的普拉斯算子
  1. Ng,Jordan,和Weiss 定义的普拉斯算子

, 其中

  1. 针对k均值核聚类(k-means kernel clustering)光滑的核,

他们之间的主要差异是?左乘一个对角阵是对行的缩放的系列, 而右乘一个对角阵是对列缩放的系列。 所以, 广义普拉斯算子得到一个右边随机的马尔科夫矩阵, 但是归一化的普拉斯算子不是。

或许,我还忽略的一些扩展变体, 因为定义一个聚类的拉普拉斯算子的误差余地和创造性实在广泛。 在以后的博客中, 我会这些算子是如何和物理上的拉普拉斯算子结合起来的。 Von Luxburg的综述对此有说明, 我或许会重写一下。

聚类的特征空间问题

如果好的聚类被识别出来了, 那么拉普拉斯算子L就能近似的对角分块化, 而每个块对应一个聚类。 例如, 我们有三个主要类别的话,

, 那么我们期望的矩阵:

其中,

对应到C1聚类对应的子分块, 而这种分块得以让我们能够识别出在非凸的数据边界情况下的聚类。 例如:

我们期望的3个最小的特征值,和对应的特征向量, 是对应到不同的聚类的。每个特征向量,会对应子分块

的最小的特征向量。 也就是说,如果

是最小的特征值和对应的特征向量, 这是在全空间内。 那么

就是C1分区里面的最小特征值和对应的特征向量。 也就是说,

就是3个

中的某个的很好的近似。 同样对应C2和C3也成立。

更重要的是, 对于L的特征值谱而言也是严格上正确的, 所以全域的特征值是由对应子空间的特征值构成的:

=

这样要确定k个聚类, L的特征值谱就需要有个空隙, 就如下所示(不好意思, 这里显示了4个而不是3个特征值):

通常情况下, 这个明显的隔间gap是比较难以找到的, 并且把找k个过程叫做“凑整 rounding”。

在子空间下跑K-Means算法和找到并确认每个特征向量和对应聚类,严格上说并不一致。 实际上, 人们会想象利用一个比必须情况下稍微大一点的子空间, 并且仅仅抽取出k个想要的聚类。 但是这里说的比较晦涩的,具体如何选择适合的关联关系(对应的截断矩阵R等), 如何选择适合大小的子空间, 如何选择适合的正则化(包括拉普拉斯算子, 特征向量等, 在正则化之前或者之后), 这些细节, 你需要参考原始论文,综述, 以及你应用的源码。

2008,有篇文章对这些想法进行了整理:L. ROSASCO, M. BELKIN, E. DE VITOA NOTE ON PERTURBATION RESULTS FOR LEARNING, EMPIRICAL OPERATORS。

在子空间下跑K-Means算法和找到并确认每个特征向量和对应聚类,严格上说并不一致。 实际上, 人们会想象利用一个比必须情况下稍微大一点的子空间, 并且仅仅抽取出k个想要的聚类。

利用前面介绍的一些扰动理论和分解算子, 这些在这个背景下都会显得非常有趣。 在量子扰动理论里面, 在模型空间的子块里面的特征向量,用来近似表示图拉普拉斯算子矩阵L的真实低洼Low Lying, 或者高卧High Lying的部分。

真实数据的限制

下面我们描述了下对于好的或者坏的相似矩阵对应的仿射矩阵的块结构。 对于好的相似/关联矩阵,能确认为2个清晰的聚类的情况, 的确显示为对角块。

开源实现

Python Scikit对谱聚类是有实现的 http://scikit-learn.org/stable/modules/clustering.html#spectral-clustering 。

并且给出了2个例子:

第一个例子: 图片分割 http://scikit-learn.org/stable/auto_examples/cluster/plot_segmentation_toy.html#example-cluster-plot-segmentation-toy-py 区分出4个重叠圆的部分。 这里,就算是普通的K-Means也是能实现的, 因为这些部分都比较紧致。 例子里面说, 能把聚类和背景区分开来。 但是总体来说,并不很难。

第二个例子, http://scikit-learn.org/0.15/auto_examples/cluster/plot_lena_segmentation.html 是Lena图片分割。 这里方法并没有好太多, 因为谱聚类并不能学习分割。 这里某种意义上需要监督或者半监督的学习, 譬如: SemiSupervised Learning using Laplacian / Manifold Regularization http://cs.nyu.edu/~fergus/papers/fwt_ssl.pdf 甚至深度学习能很好的进行人脸识别。

需要强调的是, 谱聚类强大的地方是在一个数据集中发现非紧致的聚类。

优化调整

谱聚类的限制, 至少从本文来看, 谱聚类要求数据集相对符合均匀的情况, 数据集有N个均匀大小的聚类( Von Luxburg 提议使用广义拉普拉斯算子 Generalized Laplacian )。 否则,不能保证, 全空间和子块的特征谱会较好的排列着。

或许大家可以看一下Andrew Ng的矩阵扰动理论matrix perturbation theory, 来看一下这个理论是如何处理不好的相似关系的情况。

有兴趣的同志,依然可以深入了解Shi, Belkin, and Yu的2012年的工作:数据光谱 Data Spectroscopy

(https://calculatedcontent.com/2012/10/18/data-spectroscopy/), 从中,可以看到带有RBF核的谱聚类,和量子扰动光谱学(Quantum Mechanical Spectroscopy)很相似, 只是数据点是量子机械谐波振荡(Quantum Mechanical Harmonic Oscillators)而已。

当然, 我们知道泛化谱聚类可以通过图拉普拉斯算子进行半监督的流行学习(using the Graph Laplacian as a Regularizer for SemiSupervised Manifold Learning)

小结

本文通过对谱聚类, 把图拉普拉斯算子模型 和 谱聚类进行了联系, 并且和特征向量,K-Means的关系进行了解释, 和量子扰动光谱学进行了关联 。

参考:

https://charlesmartin14.wordpress.com/2012/10/09/spectral-clustering/

原文发布于微信公众号 - AI2ML人工智能to机器学习(mloptimization)

原文发表时间:2017-05-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CVer

[计算机视觉论文速递] 2018-04-19

[1]《Hierarchical Novelty Detection for Visual Object Recognition》

1572
来自专栏新智元

【NIPS'16 】Bengio 报告 | 大脑与比特:当神经科学遇上深度学习

【新智元导读】本年度的 NIPS 接近尾声,Yoshua Bengio 的报告终于出炉。Bengio这次报告主要介绍神经科学与深度学习之间的关系,逐一介绍了在神...

3625
来自专栏BestSDK

无论人工智能发展到什么地步,都离不开这6段代码

从代码中追溯深度学习的历史 深度学习发展到如今的地位,离不开下面这 6 段代码。本文介绍了这些代码的创作者及其完成这些突破性成就的故事背景。每个故事都有简单的代...

36614
来自专栏奇点大数据

游戏AI小试牛刀(2)

上次我们说到用深度学习来做斗地主游戏AI的一个实验项目,这次我们来说说技术实现层面的一些问题。 对于这样一个应用场景来说,我们是可以把它当做类似于图片分类的场...

3725
来自专栏机器学习算法与Python学习

Machine Learning -- Bayesian network

链接地址:http://www.dataguru.cn/thread-508373-1-1.html 0 引言 事实上,介绍贝叶斯定理、贝叶斯方法、贝叶斯推断的...

4616
来自专栏PPV课数据科学社区

以撩妹为例,5分钟让你秒懂深度学习!

爱在七夕 七夕,农历七月初七, 人们说它是中国的情人节, 可最初它是中国少女的乞巧节, 而现在,这些都不重要, 重要的是, 它是属于所有心中有“爱”之人的节日...

3194
来自专栏AI科技评论

干货 | 谷歌 AI:语义文本相似度研究进展

本文为雷锋字幕组编译的技术博客,原标题 Advances in Semantic Textual Similarity。

2134
来自专栏大数据挖掘DT机器学习

达观数据NLP技术的应用实践和案例分析

达观文本挖掘系统整体方案 达观文本挖掘系统整体方案包含了NLP处理的各个环节,从处理的文本粒度上来分,可以分为篇章级应用、短串级应用和词汇级应用。 篇章级应用有...

47711
来自专栏机器之心

可视化语音分析:深度对比Wavenet、t-SNE和PCA等算法

选自Medium 作者:Leon Fedden 机器之心编译 参与:Nurhachu Null、刘晓坤 这篇文章基于 GitHub 中探索音频数据集的项目。本文...

74413
来自专栏AI科技评论

洞见 | 生成对抗网络GAN最近在NLP领域有哪些应用?

AI科技评论按:本文作者莫驚蟄,原文载于知乎,获授权转载。 我来答一答自然语言处理方面GAN的应用 直接把GAN应用到NLP领域(主要是生成序列),有两方面的问...

4784

扫码关注云+社区

领取腾讯云代金券