谱聚类概述

作者 | 荔枝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 条评论
登录 后参与评论

相关文章

来自专栏https://www.cnblogs.com/L

【机器学习】--鲁棒性调优之L1正则,L2正则

第一个更好,因为当把测试集带入到这个模型里去。如果测试集本来是100,带入的时候变成101,则第二个模型结果偏差很大,而第一个模型偏差不是很大。

593
来自专栏解飞的专栏

实习生的监控算法: 利用机器学习方法进行曲线分类

本篇文章主要采用机器学习的方法来实现曲线分类,基本思路是对训练集先用聚类方法(如Kmeans和Birch等进行聚类,对数据打上标签),然后在对测试集采用分类方法...

9191
来自专栏大数据文摘

解决机器学习问题有通法!看这一篇就够了!

1774
来自专栏ATYUN订阅号

【学术】Ferenc Huszár:剪枝神经网络两篇最新论文的解读

我想简要地介绍两篇关于修剪神经网络的论文: Learning Sparse Neural Networks through L0 Regularization...

3947
来自专栏机器学习算法原理与实践

支持向量机高斯核调参小结

    在支持向量机(以下简称SVM)的核函数中,高斯核(以下简称RBF)是最常用的,从理论上讲, RBF一定不比线性核函数差,但是在实际应用中,却面临着几个重...

763
来自专栏人工智能头条

Keras/Python深度学习中的网格搜索超参数调优(下)

2123
来自专栏算法channel

高斯混合模型:不掉包实现多维数据聚类分析

《实例》阐述算法,通俗易懂,助您对算法的理解达到一个新高度。包含但不限于:经典算法,机器学习,深度学习,LeetCode 题解,Kaggle 实战。期待您的到来...

3486
来自专栏人工智能

6种机器学习算法要点

本文旨在为人们提供一些机器学习算法,这些算法的目标是获取关于重要机器学习概念的知识,同时使用免费提供的材料和资源。当然选择有很多,但哪一个是最好的?哪两个互相补...

2039
来自专栏SIGAI学习与实践平台

OCR技术简介

光学字符识别(Optical Character Recognition, OCR)是指对文本资料的图像文件进行分析识别处理,获取文字及版面信息的过程。亦即将图...

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

四大机器学习降维算法:PCA、LDA、LLE、Laplacian Eigenmaps

机器学习领域中所谓的降维就是指采用某种映射方法,将原高维空间中的数据点映射到低维度的空间中。降维的本质是学习一个映射函数 f : x->y,其中x是原始数据点的...

3576

扫码关注云+社区