谱聚类概述

作者 | 荔枝boy

编辑 | 磐石

出品 | 磐创AI技术团队

【磐创AI导读】:本文主要介绍了谱聚类的相关概念。欢迎大家点击上方蓝字关注我们的公众号:磐创AI

目录:

一.简述

二.图相关的符号符号

三.相似度矩阵S

四.拉普拉斯矩阵L性质

五.谱聚类算法

六.总结

一.简述

聚类是对探索性数据分析最广泛使用的技术,在现在各个科学领域中处理没有类标的数据时,人们总是想通过确定数据中不同样本的归类,来获取对数据的直观印象。传统的聚类方法有很多,像K-means,single linkage等,但是k-means算法有些缺点,比如当样本维度特别大的时候,k-means的计算量是很大的。最近几年时间,谱聚类成为了最受欢迎的聚类算法,它很容易执行,能够用标准的线代软件高效地解决,而且比传统的聚类算法比如k-means表现效果要好很多。不管怎样,初次一瞥谱聚类时看起来很神秘,不太能弄透为什么谱聚类能够用于聚类。为了介绍谱聚类到底如何能够作聚类,我们需要先了解相似度矩阵,拉普拉斯矩阵的概念,然后才能最终理解谱聚类原理。

二.图相关的符号标记

现有给定样本x_1,......x_n,想要用谱聚类来给这些样本集进行聚类的话,需要将这些样本之间的联系用图的形式来表示。在这里介绍下图的相关符号。假设有若干个样本x_i被归为一类,该集合为A。这里先给出相关需要的概念,刚看到不理解不用担心,先记住他们是做什么的就行。

设定:

1)谱聚类中,我们需要描述样本与样本间的联系,这时候需要构建一个图。G=(V,E)是一个无向图,其中V={v_1,...,v_n}代表这些样本点,E是代表不同点之间相似度,其中e_ij代表v_i与v_j之间的权值(有多种方式构建此相似度),用w_ij表示,其中w_ij>=0,构成了邻接矩阵W(两样本v_i与v_j之间有连接则w_ij>0,无连接则w_ij=0),因为G是无向图,所以可知道w_ij=w_ji。

2)度矩阵D,其中

,代表v_i样本与其他v_j样本的权重之和。

三.相似度矩阵S

谱聚类算法需要的输入是一个图,该图包含了所有样本与样本之间的相似度,该图为一个矩阵,大小是n*n。这样通过某种标准定义了样本之间联系构建出来的矩阵,我们叫做它相似度矩阵。有很多种构建相似度矩阵的方式,比如K近邻构建的相似度矩阵,高斯相似度矩阵等,eg:用高斯相似度S(x,y)计算两样本间的联系时:

公式一

其他相似度构造标准在此不再详细阐述,你需要知道,这些不同的构建相似度矩阵的方式,他们有各自对样本间相似度的构建标准,通过他们,给定的样本就能变成一个相似度矩阵S,S_ij代表样本v_i与v_j之间相似度,这里的出的S_ij矩阵其实就是用作于后边的W_ij邻接矩阵。这里需要指出的是,目前还没有理论结果指明在不同的数据训练中使用哪种方案构建相似度矩阵最合适。

四.拉普拉斯矩阵L性质

谱聚类中最重要的工具就是拉普拉斯矩阵,在这里我们给出拉普拉斯矩阵的定义和一些他的重要性质。之前上文已经给出了一些相关符号的定义,我们已经根据不同的相似度标准求出了样本与样本之间的相似度,构建了邻接矩阵W。这里我们也知道了度矩阵D

:。而谱聚类中所需要的最重要的拉普拉斯矩阵L:

L=D-W

拉普拉斯矩阵有如下的一些重要性质:

1)对于任意一个向量

,我们都有如下的等式恒成立:

2)拉普拉斯L矩阵是对称半正定矩阵(特征值非负数)

3)L最小的特征值为0,对应的特征向量为全1向量。

4)L有多少个0特征值,样本构成的图G中就存在多少个连通分量(最大连通子图)

以上就是拉普拉斯矩阵L所具有的一些重要的性质,证明比较多,本次讲解就不详细展开,以后会将其单独罗列出来并讲下谱聚类更深入的细节,体会下当初发明人多么巧妙的用拉普拉斯矩阵去解决样本的均匀聚类问题。

五.谱聚类算法

将所有的样本构建成一个图,x_i与x_j之间的关联程度构建了图对应的边。那现在我们就得到了一个图,图上有所有样本和样本间的联系。谱聚类算法是对这个图进行合理的切分,分成几类,这样切分得到的每类都比较均匀。

输入:样本x_i,需要聚类的个数k

  • 构建相似度矩阵S,样本间x_i已经通过高斯相似度构建出了相似度矩阵S, 也就是邻接矩阵W。
  • 计算出度矩阵D
  • 计算出拉普拉斯矩阵L=D-W
  • 计算出L前k个最小的特征向量v_1,...,v_k
  • 将前k个特征向量组合成一个矩阵V,其中第i列对应v_i列向量。
  • 该矩阵V的每一行对应代表x_i的低维度的表示y_i。
  • 对所有y_i进行k-means聚类,聚成k类

输出:k个类,每个样本标记聚成的类别。

谱聚类切割出来的图的特点,他会让所切分的样本构建的图比较均匀。

六.总结

本次只是简单的阐述了下谱聚类所需要的一些相关和算法流程。想要对样本进行合理的切割,用谱聚类算法相对于传统的k-means算法会更高效,聚类的效果会均匀。谱聚类需要先将样本通过某种标准计算出样本间的相似度构建成相似度矩阵,也就是邻接矩阵。然后计算拉普拉斯矩阵,求出拉普拉斯矩阵对应的前k个最小的特征值,得到对应的特征向量组成的矩阵V后,用V来给样本在低维度上进行聚类,相比k-means直接对样本聚类会更快。刚开始你需要先了解谱聚类的整个运作流程。然后再带着这个流程去分析每一部分会更好理解些。本次讲解并没有涉及深层次的原理,比如为什么用拉普拉斯矩阵能够解决图的均匀分割问题,拉普拉斯矩阵的这些性质怎么得来的,并且直观上这些性质意味着什么。我会在下次详细讲解这些性质的由来,并讲解通过拉普拉斯矩阵如何去巧妙地解决聚类问题。

你也许还想看:

● 一文彻底搞懂BP算法:原理推导+数据演示+项目实战(上篇)

● TensorFlow + Keras 实战 YOLO v3 目标检测图文并茂教程(文末有惊喜)

● 入门 | Tensorflow实战讲解神经网络搭建详细过程


Tips:欢迎大家点击最下方二维码关注我们的公众号,点击干货资源专栏或发送关键字“资源”获取更多资源推荐。关注我们的历史文章,一起畅游在深度学习的世界中。我们期待你的留言和投稿,共建交流平台。来稿请寄:voice1235@163.com

原文发布于微信公众号 - 磐创AI(xunixs)

原文发表时间:2018-05-24

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI研习社

不均衡数据怎么破?对付它的七种武器!

先问大家一个问题: 银行欺诈识别、市场实时交易、网络入侵检测等领域的数据集,有哪些共通点? 答案是:“关键”事件在数据中的占比经常少于1%(例如:信用卡行骗者、...

37870
来自专栏AI科技评论

语义分割领域开山之作:Google提出用神经网络搜索实现语义分割

AI 科技评论按:本文作者陈泰红,邮箱 ahong007@yeah.net,他为 AI 科技评论撰写了 Google 利用神经网络搜索实现语义分割的独家解读。

11210
来自专栏人工智能LeadAI

从零开始用Python搭建超级简单的点击率预估模型

本篇是一个基础机器学习入门篇文章,帮助我们熟悉机器学习中的神经网络结构与使用。 日常中习惯于使用Python各种成熟的机器学习工具包,例如sklearn、Ten...

13210
来自专栏数据科学与人工智能

朴素贝叶斯分类算法|机器学习

贝叶斯分类是一类分类算法的总称,这类算法均以贝叶斯定理为基础,故统称为贝叶斯分类。本文作为分类算法的第一篇,将首先介绍分类问题,对分类问题进行一个正式的定义。然...

29690
来自专栏大数据文摘

重磅长文|提高深度学习性能的四种方式

32670
来自专栏数据科学与人工智能

【机器学习】机器学习算法预览

在这篇文章中,我要带大家预览一下机器学习中最热门的算法。预览主要的机器学习算法可在某种程度上给你这样的一种感觉,让你知道什么样的方法是可靠的。 这里有很多算法都...

27150
来自专栏人工智能

带你通俗易懂的理解人工智能算法一

我们所谓的人工智能算法就是一个机器嵌入了这个算法后,这个机器就拥有了人所具有的基本能力,比如观察、思考、学习、创造等,本文要说的就是这个算法。 人工智能算法主要...

31290
来自专栏AI科技评论

视频 | 英伟达发布新算法,可以重建缺失像素

AI 科技评论按:本文由雷锋字幕组编译,原标题 New AI Imaging Technique Reconstructs Photos with Realis...

13020
来自专栏书山有路勤为径

改善深层神经网络-设置机器学习应用

这有一个常见的误区,在机器学习发展的小数据时代,常见做法是将所有数据三七分,70%训练集,30%测试集或者60%训练集,20%验证集,20%测试集,这是机器学习...

7520
来自专栏大数据文摘

干货 | Active Learning: 一个降低深度学习时间,空间,经济成本的解决方案

23620

扫码关注云+社区

领取腾讯云代金券