文档章节

谱聚类(spectral clustering)及其实现详解

 当当当当蛋糕
发布于 2016/11/15 13:25
字数 896
阅读 232
收藏 0

 

       谱聚类(spectral clustering)的思想最早可以追溯到一个古老的希腊传说,话说当时有一个公主,由于其父王去世后,长兄上位,想独揽大权,便杀害了她的丈夫,而为逃命,公主来到了一个部落,想与当地的酋长买一块地,于是将身上的金银财宝与酋长换了一块牛皮,且与酋长约定只要这块牛皮所占之地即可。聪明的酋长觉得这买卖可行,于是乎便应了。殊不知,公主把牛皮撕成一条条,沿着海岸线,足足围出了一个城市。 
       故事到这里就结束了,但是我们要说的才刚刚开始,狄多公主圈地传说,是目前知道的最早涉及Isoperimetric problem(等周长问题)的,具体为如何在给定长度的线条下围出一个最大的面积,也可理解为,在给定面积下如何使用更短的线条,而这,也正是谱图聚类想法的端倪,如何在给定一张图,拿出“更短”的边来将其“更好”地切分。而这个“更短”的边,正是对应了spectral clustering中的极小化问题,“更好”地切分,则是对应了spectral clustering中的簇聚类效果。 
       谱聚类最早于1973年被提出,当时Donath 和 Hoffman第一次提出利用特征向量来解决谱聚类中的f向量选取问题,而同年,Fieder发现利用倒数第二小的特征向量,显然更加符合f向量的选取,同比之下,Fieder当时发表的东西更受大家认可,因为其很好地解决了谱聚类极小化问题里的NP-hard问题,这是不可估量的成就,虽然后来有研究发现,这种方法带来的误差,也是无法估量的,下图是Fielder老爷子,于去年15年离世,缅怀。 
SC
 

二、谱聚类的演算

(一)、演算

 

1、谱聚类概览

       谱聚类演化于图论,后由于其表现出优秀的性能被广泛应用于聚类中,对比其他无监督聚类(如kmeans),spectral clustering的优点主要有以下:

1.过程对数据结构并没有太多的假设要求,如kmeans则要求数据为凸集。
2.可以通过构造稀疏similarity graph,使得对于更大的数据集表现出明显优于其他算法的计算速度。
3.由于spectral clustering是对图切割处理,不会存在像kmesns聚类时将离散的小簇聚合在一起的情况。
4.无需像GMM一样对数据的概率分布做假设。

       同样,spectral clustering也有自己的缺点,主要存在于构图步骤,有如下:

1.对于选择不同的similarity graph比较敏感(如 epsilon-neighborhood, k-nearest neighborhood,fully connected等)。
2.对于参数的选择也比较敏感(如 epsilon-neighborhood的epsilon,k-nearest neighborhood的k,fully connected的 )。

       谱聚类过程主要有两步,第一步是构图,将采样点数据构造成一张网图,表示为G(V,E),V表示图中的点,E表示点与点之间的边,如下图: 
              谱聚类构图 
                            图1 谱聚类构图(来源wiki) 
       第二步是切图,即将第一步构造出来的按照一定的切边准则,切分成不同的图,而不同的子图,即我们对应的聚类结果,举例如下: 
              切图4 
                            图2 谱聚类切图 
       初看似乎并不难,但是…,下面详细说明推导。 

本文转载自:

粉丝 0
博文 38
码字总数 13194
作品 0
南京
私信 提问
Apache Mahout中的机器学习算法集

Apache Mahout中的机器学习算法集 Apache Mahout 是 ApacheSoftware Foundation (ASF) 旗下的一个开源项目,提供一些可扩展的机器学习领域经典算法的实现,旨在帮助开发人员更加方便快捷地创...

yuzh
2012/12/27
0
0
Spectral Clustering(学习Free Mind知识整理)

阅读http://blog.pluskid.org/?p=287文章中的一些知识整理:学习的知识点谱聚类。也可以学习一下http://blog.csdn.net/vjuly_v/article/details/40738211里面的介绍和链接中的参考链接,...

langb2014
2015/08/27
0
0
浅谈Spectral Clustering

Spectral Clustering,中文通常称为“谱聚类”。由于使用的矩阵的细微差别,谱聚类实际上可以说是一“类”算法。 Spectral Clustering 和传统的聚类方法(例如 K-means)比起来有不少优点: ...

嗯哼9925
2018/01/07
0
0
机器学习-聚类Clustering

简介 前面介绍的线性回归,SVM等模型都是基于数据有标签的监督学习方法,本文介绍的聚类方法是属于无标签的无监督学习方法。其他常见的无监督学习还有密度估计,异常检测等。 聚类就是对大量...

hiyoung
2018/10/20
0
0
谱聚类简明教程(前言)

原文:A Tutorial on Spectral Clustering https://arxiv.org/pdf/0711.0189 作者:U von Luxburg - ‎2007 - ‎被引用次数:5313 摘要:     近年来,谱聚类已发展成为最流行的现代聚类算...

reasonW
2018/01/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

texlive安装

Installing to: D:/bin/texlive/texlive/2019Installing [001/307, time/total: ??:??/??:??]: adobemapping [2130k]Installing [002/307, time/total: 00:03/08:57]: ae [84k]Installing......

MtrS
今天
2
0
运维规范

命名规范 发布流程 监控告警 故障定位 状态 日志 监控

以谁为师
今天
2
0
约瑟夫环(报数游戏)java实现

开端 公司组织考试,一拿到考题,就是算法里说的约瑟夫环,仔细想想 以前老师将的都忘了,还是自己琢磨把~ package basic.gzy;import java.util.Iterator;import java.util.LinkedList;...

无极之岚
今天
3
0
Kernel字符设备驱动框架

Linux设备分为三大类:字符设备,块设备和网络设备,这三种设备基于不同的设备框架。相较于块设备和网络设备,字符设备在kernel中是最简单的,也是唯一没有基于设备基础框架(device结构)的...

yepanl
今天
3
0
Jenkins 中文本地化的重大进展

本文首发于:Jenkins 中文社区 我从2017年开始,参与 Jenkins 社区贡献。作为一名新成员,翻译可能是帮助社区项目最简单的方法。 本地化的优化通常是较小的改动,你无需了解项目完整的上下文...

Jenkins中文社区
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部