小白入门谱聚类算法原理与实现

• • 小白入门谱聚类算法原理与实现
• 1. 谱聚类是什么li>
• 2.谱聚类步骤
• • 2.1 谱聚类构图
  • 2.2 谱聚类切图
  • • 2.2.1RatioCut
    • 2.2.2Ncut
• 3谱聚类实现

小白入门谱聚类算法原理与实现

文章结构主要分为下面三个部分
①谱聚类是什么
②谱聚类怎么进行聚类
③谱聚类应用例子

1. 谱聚类是什么h1>

首先回顾一下聚类的概念：

1. 聚类：对大量未知标注的数据集，按数据的内在相似性将数据集划分为多个类别，使类别内的数据相似度较大而类别间的数据相似度较小

2. 谱聚类：是一种基于图论的聚类方法，通过对样本数据的拉普拉斯矩阵的特征向量进行聚类，从而达到对样本数据聚类的目的。

    直观的解释就是将聚类问题转化为一个无向图的多路划分问题，数据点看成无向图G(V,E)中的顶点V，加权边的集合E={Sij}表示基于某一点相似性度量的两点间的相似度，用S表示待聚类数据点之间的相似性矩阵，图G中把聚类问题转变为在图G上的图划分问题，即将图G(V,E)划分为K个互不相交的子集Ｖ１，Ｖ２，．．．Ｖｋ，划分后每个子集Ｖｉ和Ｖｊ之间的相似程度较低，每个子集内部相似度较高。
    所以谱聚类的思想就是要转化为图分割的问题，因此下面从图的概念进行引入。
简单回顾一下图的基本概念

2.谱聚类步骤

有了图的概念之后，下面进入谱聚类的步骤。
下面以简单的6个样本为例，如下图所示

此时，得到邻接矩阵W后，需要计算度矩阵D：

如上图所示，用这种方法且会造成将V切成很多歌单点离散的图，显然这样是最快且最能满足最小化操作的，但是明显不是想要的结果，所以下面引出了RatioCut和Ncut两种优化的切图方式。

2.2.1RatioCut

    Ratio切图考虑了子图的大小，避免了单个样本点作为一个簇的情况发生，平衡了各子图的大小，即

• 谱聚类优点：
  ①对数据结构并没有太多的假设要求，如kmeans则要求数据为凸集。
  ②可以构造稀疏similarity graph，使得对于更大的数据集相对来说也能有较好的计算速度
  ③由于谱聚类是对图切割处理，不会像kmesns聚类时将离散的小簇聚合在一起的情况。
• 缺点：
  ①对于选择不同的构图方式比较敏感
  ②求解过程主要时间在与矩阵的转换上，同时也需要较大的内存空间

参考资料
【论文】A Short Theory of the Rayleigh–Ritz Method
【博客】https://blog.csdn.net/yc_1993/article/details/52997074
【博客】https://blog.csdn.net/songbinxu/article/details/80838865
【博客】https://blog.csdn.net/pr310762957/article/details/53103709
【博客】https://www.cnblogs.com/pinard/p/6221564.html
【博客】https://www.cnblogs.com/pinard/p/6235920.html

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览34601 人正在系统学习中