作者：Neerja Doshi

编译：ronghuaiyang导读谱聚类，了解直觉以及背后的数学原理

什么是聚类？

聚类是一种广泛使用的无监督学习方法。聚类是这样分组的：集群中的点彼此相似，而与其他集群中的点不太相似。因此，如何在数据中寻找模式并为我们分组取决于算法，根据使用的算法，我们可能最终得到不同的集群。

有两种广泛使用的聚类方法：

紧密性——相互靠近的点落在同一个集群中，并且在紧密聚集在集群中心周围。这种密切的关系可以用观测值之间的距离来衡量。比如：k—means聚类连接性——相互连接或相邻的点放在同一个集群中。即使两点之间的距离更小，如果它们不相连，它们也不会聚集在一起。谱聚类是遵循这种方法的一种技术。

两者之间的区别可以很容易地通过这个例子来说明：

谱聚类如何工作？

在谱聚类中，数据点被视为图的节点。因此，集群被视为一个图的分割问题。然后将节点映射到一个低维空间，该空间可以很容易地进行隔离，从而形成集群。需要注意的重要一点是，没有对集群的形状/形式做任何假设。

谱聚类的步骤有哪些？

谱聚类包括三个步骤：计算相似图将数据投影到低维空间创建集群

步骤1—计算相似图

我们首先创建一个无向图G = (V, E)，顶点集V = {v1, v2，…，vn} = 1,2，…，n个数据中的观察值。这可以用一个邻接矩阵来表示，该矩阵将每个顶点之间的相似性作为其元素。要做到这一点，我们可以计算：

ε-neighborhood图：这里我们连接所有两两距离小于ε的点。所有连接的点之间的距离大致都是相同的尺度（最多是ε)，对边进行加权不会包含进图中数据的更多的信息，因此，ε-neighborhood图通常被认为是一个无权重的图。KNN图：这里我们使用K最近邻来连接顶点vi和顶点vj，如果vj在vi的K个最近邻中，我们就把vi和vj连接起来。但是有个问题，最近邻可能不是对称的，也就是说如果有一个顶点vi以vj为最近邻，那么vi不一定是vj的最近邻。因此，我们最终得到一个有向图，这是一个问题，因为我们不知道在这种情况下，两点之间的相似性意味着什么。有两种方法可以使这个图变成无向图。第一种方法是直接忽略边缘的方向，即如果vi在vj的k近邻中，或者如果vj在vi的k近邻中，我们用无向边连接vi和vj。得到的图通常称为k近邻图。第二个选择是连接vi和vj互为k近邻点的情况，得到的图称为相互k近邻图。在这两种情况下，在连接适当的顶点后，我们通过相邻点的相似性对边进行加权。全连接图：为了构造这个图，我们简单地将所有点连接起来，并通过相似性sij对所有边进行加权。该图应该对局部邻域关系进行建模，因此使用了高斯相似函数等相似函数。

这里的参数σ控制邻域的宽度，类似于ε-neighborhood图中的参数ε。

因此，当我们为这些图中的任意一个创建邻接矩阵时，当点很近时Aij ~ 1，当点很远时Aij→0。

考虑一下拥有1~4节点的图，权值(或相似度)wij及其邻接矩阵：

步骤2—将数据投影到低维空间

正如我们在图1中所看到的，相同集群中的数据点可能也很远—甚至比不同集群中的数据点还要远。我们的目标是空间转换，当这两个点很近的时候，它们总是在同一个集群中，当它们很远的时候，它们是在不同的集群中。我们需要把观测结果投射到低维空间。为此，我们计算图的拉普拉斯矩阵，这只是图的另一种矩阵表示形式，对于查找图的有趣的属性非常有用。这可以计算为：

计算图的拉普拉斯矩阵

我们上面例子的图的拉普拉斯矩阵

计算图的拉普拉斯矩阵L的全部目的是找到它的特征值和特征向量，以便将数据点嵌入低维空间。现在，我们可以继续查找特征值。我们知道：

我们考虑下面的例子：

我们计算L的特征值和特征向量。

步骤3—创建集群

对于这一步，我们使用对应于第二个特征值的特征向量来为每个节点赋值。计算时，第二个特征值为0.189，对应的特征向量v2 =[0.41, 0.44, 0.37， -0.4， -0.45， -0.37]。

为了得到2聚类(2个不同的聚类)，我们首先将v2的每个元素分配给节点，例如{node1:0.41, node2:0.44，…node6: -0.37}。然后，我们对节点进行拆分，使值为> 0的所有节点都位于一个集群中，而所有其他节点都位于另一个集群中。因此，在本例中，我们在一个集群中得到节点1、2和3，在第二个集群中得到节点4、5和6。

需要注意的是，第二个特征值表示图中节点的紧密连接程度。对于好的、干净的划分，降低第2个特征值，让聚类变得更好。

特征向量v2给出一个2分聚类

对于k聚类，我们需要修改拉普拉斯矩阵，对它进行归一化

我们得到：

归一化的拉普拉斯矩阵

谱聚类的优缺点

优点：

没有对聚类的统计数据做出强有力的假设——聚类技术(如K-Means聚类)假设分配给聚类的点围绕聚类中心是球形的。这是一个强有力的假设，可能并不总是相关的。在这种情况下，谱聚类有助于创建更精确的聚类。易于实现，聚类效果好。它可以正确地将实际属于同一簇但由于维数减少而比其他簇中的观测值更远的观测值进行聚类。对于几千个元素的稀疏数据集，速度相当快。

缺点:

在最后一步中使用K-Means聚类意味着聚类并不总是相同的。它们可能随初始中心的选择而变化。对于大型数据集来说，计算开销很大——这是因为需要计算特征值和特征向量，然后我们必须对这些向量进行聚类。对于大型、密集的数据集，这可能会大大增加时间复杂度。

英文原文：

请长按或扫描二维码关注本公众号