谱聚类(Spectral Clustering)算法介绍 |
您所在的位置:网站首页 › kmeans归一化 › 谱聚类(Spectral Clustering)算法介绍 |
一. 前言
本来想写关于聚类系列算法的介绍,但是聚类系列的其它几个算法原理比较简单,网上有大量的教程可以查阅。这里主要是介绍一下谱聚类算法,做一个学习笔记,同时也希望对想要了解该算法的朋友有一个帮助。关于聚类的其他系列算法,这里推荐一个写的很不错的博客。 谱聚类在最近几年变得受欢迎起来,主要原因就是它实现简单,聚类效果经常优于传统的聚类算法(如K-Means算法)。刚开始学习谱聚类的时候,给人的感觉就是这个算法看上去很难,但是当真正的深入了解这个算法的时候,其实它的原理并不难,但是理解该算法还是需要一定的数学基础的。如果掌握了谱聚类算法,会对矩阵分析,图论和降维中的主成分分析等有更加深入的理解。 本文首先会简单介绍一下谱聚类的简单过程,然后再一步步的分解这些过程中的细节以及再这些过程中谱聚类是如何实现的,接着总结一下谱聚类的几个算法,再接着介绍谱聚类算法是如何用图论知识来描述,最后对本文做一个总结。下面我们就来介绍一下谱聚类的基本原理。 二. 谱聚类的基本原理介绍 2.1 谱和谱聚类2.1.1 谱 方阵作为线性算子,它的所有特征值的全体统称为方阵的谱。方阵的谱半径为最大的特征值。矩阵A的谱半径是矩阵 2.1.2 谱聚类 谱聚类是一种基于图论的聚类方法,通过对样本数据的拉普拉斯矩阵的特征向量进行聚类,从而达到对样本数据聚类的目的。谱聚类可以理解为将高维空间的数据映射到低维,然后在低维空间用其它聚类算法(如KMeans)进行聚类。 2.2 谱聚类算法简单描述输入:n个样本点 输出:聚类簇 (1)使用下面公式计算 W为 (2)使用下面公式计算度矩阵D; D为 (3)计算拉普拉斯矩阵 (4)计算L的特征值,将特征值从小到大排序,取前k个特征值,并计算前k个特征值的特征向量 (5)将上面的k个列向量组成矩阵 (6)令 (7)使用k-means算法将新样本点 (8)输出簇 上面就是未标准化的谱聚类算法的描述。也就是先根据样本点计算相似度矩阵,然后计算度矩阵和拉普拉斯矩阵,接着计算拉普拉斯矩阵前k个特征值对应的特征向量,最后将这k个特征值对应的特征向量组成 相似度矩阵就是样本点中的任意两个点之间的距离度量,在聚类算法中可以表示为距离近的点它们之间的相似度比较高,而距离较远的点它们的相似度比较低,甚至可以忽略。这里用三种方式表示相似度矩阵:一是 (1)-neighborhood graph: 用此方法构造的相似度矩阵表示如下: 该相似度矩阵由于距离近的点的距离表示为 (2)k-nearest nerghbor graph: 由于每个样本点的k个近邻可能不是完全相同的,所以用此方法构造的相似度矩阵并不是对称的。因此,这里使用两种方式表示对称的knn相似度矩阵,第一种方式是如果 第一种方式: 第二种方式: (3)fully connected graph: 该方法就是在算法描述中的高斯相似度方法,公式如下: 该方法也是最常用的方法,在sklearn中默认的也是该方法,表示任意两个样本点都有相似度,但是距离较远的样本点之间相似度较低,甚至可以忽略。这里面的参数控制着样本点的邻域宽度,即越大表示样本点与距离较远的样本点的相似度越大,反之亦然。 2.3.2 拉普拉斯矩阵介绍对于谱聚类来说最重要的工具就是拉普拉斯矩阵了,下面我们来介绍拉普拉斯矩阵的三种表示方法。 (1)未标准化的拉普拉斯矩阵: 未标准化的拉普拉斯矩阵定义如下: 其中W是上节所说的相似度矩阵,D是度矩阵,在算法描述中有介绍。很显然,W与D都是对称矩阵。 未标准化的拉普拉斯矩阵L满足下面几个性质: (a)对任意一个向量 证明如下: (b)L是对称的和半正定的,证明如下: 因为 (c)L最小的特征值为0,且特征值0所对应的特征向量为全1向量,证明如下: 令 由D和W的定义可以得出上式。 (d)L有n个非负的实数特征值: (2)标准化拉普拉斯矩阵 标准化拉普拉斯矩阵有两种表示方法,一是基于随机游走(Random Walk)的标准化拉普拉斯矩阵 标准化的拉普拉斯矩阵满足如下性质: (a)对任意一个向量 (b)当且仅当 (c)当且仅当 (d)0是 (e) 关于各个版本的谱聚类算法的不同之处,就是在于相似度矩阵的计算方式不同和拉普拉斯矩阵的表示方法不同,其它步骤基本相同。下面就来介绍关于谱聚类的两个比较流行的标准化算法。 2.4 标准化谱聚类算法介绍 2.4.1 随机游走拉普拉斯矩阵的谱聚类算法描述输入:n个样本点 输出:聚类簇 (1)计算 (2)计算度矩阵D; (3)计算拉普拉斯矩阵 (4)计算 (5)将上面的k个列向量组成矩阵 (6)令 (7)使用k-means算法将新样本点 (8)输出簇 输入:n个样本点 输出:聚类簇 (1)计算 (2)计算度矩阵D; (3)计算拉普拉斯矩阵 (4)计算 (5)将上面的k个列向量组成矩阵 (6)令 (7)对于 (8)使用k-means算法将新样本点 (9)输出簇 上面两个标准化拉普拉斯算法加上未标准化拉普拉斯算法这三个算法中,主要用到的技巧是将原始样本点 聚类算法给我们的直观上的感觉就是根据样本点的相似性将他们划分成不同的组,使得在相同组内的数据点是相似的,不同组之间的数据点是不相似的。对于给定的样本点计算相似度,形成相似度图,因而谱聚类的问题可以被重新描述如下:我们想要找到图形的一个分区,使得不同分区之间的边具有非常低的权重(这意味着不同分区中的点彼此不相似)并且分区内的边具有高权重(这意味着其中的点彼此相似)。在这个小节我们将讨论如何推导谱聚类为近似的图分区的问题。 3.1 最小切(mincut)对于无向图G,我们的目标是将图 对于任意两个子图点的集合 对于k个子图集合 其中, 我们可以想到的切图方法就是最小化上式,也就是使各个组之间的权重尽可能的小,但是在许多情况下mincut只是简单的将图中的一个定点与其余的顶点分开,在并不是我们想要的结果,合理的切分结果应该是组内的样本点尽可能的多。所以mincut在实际中并不常用。下面我们介绍另外两个切图方式RatioCut和Ncut。 3.2 RatioCut切图在RatioCut切图中,不仅要考虑使不同组之间的权重最小化,也考虑了使每个组中的样本点尽量多。 定义 将图中顶点V分成k个分区 我们令 结合上面可以得到: 其中Tr(A)表示矩阵A的迹,也就是矩阵A的对角线之和。 所以我们此时的目标函数成为: 注意到我们H矩阵里面的每一个指示向量都是n维的,向量中每个变量的取值为0或者 注意观察 对于 通过找到L的最小的k个特征值,可以得到对应的k个特征向量,这k个特征向量组成一个nxk维度的矩阵,即为我们的H。一般需要对H矩阵按行做标准化,即 由于我们在使用维度规约的时候损失了少量信息,导致得到的优化后的指示向量h对应的H现在不能完全指示各样本的归属,因此一般在得到nxk维度的矩阵H后还需要对每一行进行一次传统的聚类,比如使用K-Means聚类。 3.3 Ncut切图Ncut在最小化损失函数之外,还考虑了子图之间的权重大小。Ncut切图与Ratiocut类似,只是把RatioCut分母中 由于子图样本的个数多并不一定权重就大,我们切图时基于权重也更合我们的目标,因此一般来说Ncut切图优于RatioCut切图。所以Ncut的目标函数如下: 在Ncut中使用子图权重 我们的优化目标函数是: 但是此时我们的 也就是说,此时我们的优化目标最终为: 令 可以发现这个式子和RatioCut基本一致,只是中间的L变成了 一般来说, (1)当聚类的类别个数较小的时候,谱聚类的效果会很好,但是当聚类的类别个数较大的时候,则不建议使用谱聚类; (2)谱聚类算法使用了降维的技术,所以更加适用于高维数据的聚类; (3)谱聚类只需要数据之间的相似度矩阵,因此对于处理稀疏数据的聚类很有效。这点传统聚类算法(比如K-Means)很难做到 (4)谱聚类算法建立在谱图理论基础上,与传统的聚类算法相比,它具有能在任意形状的样本空间上聚类且收敛于全局最优解 4.2 缺点 (1)谱聚类对相似度图的改变和聚类参数的选择非常的敏感; (2)谱聚类适用于均衡分类问题,即各簇之间点的个数相差不大,对于簇之间点个数相差悬殊的聚类问题,谱聚类则不适用; 五. 参考文献/博文 (1)A Tutorial on Spectral Clustering (2)比较不错的博客 --------------------- 原文:https://blog.csdn.net/qq_24519677/article/details/82291867 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |