Python 谱聚类算法从零开始

喜欢就点关注吧!

谱聚类算法是一种常用的无监督机器学习算法，其性能优于其他聚类方法。此外，谱聚类实现起来非常简单，并且可以通过标准线性代数方法有效地求解。在谱聚类算法中，根据数据点之间的相似性而不是k-均值中的绝对位置来确定数据点属于哪个类别下。具体区别可通过下图直观看出：

谱聚类算法实现

谱聚类算法的基本思想是先根据样本点计算相似度矩阵，然后计算度矩阵和拉普拉斯矩阵，接着计算拉普拉斯矩阵前k个特征值对应的特征向量，最后将这k个特征值对应的特征向量组成的矩阵U，U的每一行成为一个新生成的样本点，对这些新生成的样本点进行k-means聚类，聚成k类，最后输出聚类的结果。即该算法可分为4个基本步骤：

构造相似性图

确定邻接矩阵W，度矩阵D和拉普拉斯矩阵L

计算矩阵L的特征向量

训练k均值模型并使用它来对数据进行分类

Python实现

下面就开始通过代码实现谱聚类算法。首先加载必要的库：

通常我们的数据集是由样本(行)及其特征(列)组成的， 但是谱聚类算法只能应用于下图所示的节点连接的图形。

因此，我们必须对数据进行转换，以便从行和列转换为图形。假设我们有以下数据集。我们可以清楚地看到数据可以分为三个集群。

首先，我们构造NxN的相似性矩阵，其中N是样本数。矩阵的每一个点为每对点之间的欧氏距离。然后我们通过相似性矩阵来创建邻接矩阵，通过设置一个阈值，比较相似性矩阵与阈值的大小关系，如果距离大于阈值就设置为0，否则为1。然后可以使用邻接矩阵来构建图。如果邻接矩阵的单元格中有1，那么我们在列和行的节点之间绘制一条边。创建的邻接矩阵如下：

接下来我们通过networkx来可视化节点图形。定义绘图函数draw_graph():

下面我们随机创建一个图并输出其邻接矩阵。

当我们构建好邻接矩阵，我们就可以开始构造度矩阵。对于度矩阵的每一行，我们通过对邻接矩阵中相应行的所有元素求和来表示度矩阵的对角线。然后，我们通过从度矩阵中减去邻接矩阵来计算拉普拉斯矩阵。计算代码和计算结果如下：

根据得到拉普拉斯矩阵，我们就可以利用它的一个特殊属性来分类我们的数据。即如果图（W）具有K个连通分量，则L具有特征值为0的K个特征向量。因此，因为在我们当前的例子中我们只有一个分量，所以只有一个特征值等于0。计算特征值与特征向量代码如下:

可以看到，计算的特征值中只有一个为0。与我们的结论完全吻合。下边我们再来验证一个有两个连通分量的示例。

计算得到的特征值和特征向量如下，可以看到特征值中有两个0.

接下来我们就根据特征向量对数据进行聚类分析。

得到聚类标签如下：

到此，我们已经基本实现了谱聚类算法，总的来说，谱聚类算法的原理并不复杂，实现起来也比较容易，文中代码比较散乱，大家可以根据文中的思路将代码组合起来，这将更有助于学习理解谱聚类算法原理。

参考

https://towardsdatascience.com/unsupervised-machine-learning-spectral-clustering-algorithm-implemented-from-scratch-in-python-205c87271045