王 超 潘正高 路红梅 李雪竹

（宿州学院信息工程学院 安徽宿州 234000）

基于拉普拉斯矩阵的K-mean聚类

王 超 潘正高 路红梅 李雪竹

（宿州学院信息工程学院 安徽宿州 234000）

谱聚类的方法被广泛用在模式识别各个领域。文章运用K-mean聚类方法，主要阐述了如何由样本的相似度矩阵构造的拉普拉斯矩阵来求解样本的低维映射谱，根据低维映射谱进行谱聚类。

拉普拉斯矩阵；谱聚类；K-means

样本聚类是无监督学习的一种重要分类方法。对于无标签的样本，要实现分类只能根据样本本身的相似度进行分类，度量样本相似度就是相似度聚类[1]。传统聚类方法要知道样本在N维空间的矢量[2]。但是拉普拉斯谱聚类的方法只需要知道样本的相似度矩阵就能进行聚类。

一、图谱理论到拉普拉斯矩阵

拉普拉斯矩阵式表示图的一种矩阵，给定一个n个顶点的图，则拉普拉斯矩阵被定义为：L=D-W

其中D为图的度矩阵，W为图的邻接矩阵。

举个例子，给定一个简单图，如下:

图1 一个邻接图

把该图转化成邻接矩阵的形式记为W则：

把W的每一列元素加起来得到n个数，然后把这个数放在对角线上其余位置都是零，组成一个n×n的对角矩阵，记为度矩阵D，如下所示：

根据拉普拉斯定义L=D-W可得拉普拉斯矩阵如下所示：

通过上面这个简单例子，我们明白了拉普拉斯矩阵在连接图上的定义。下面我们对于更一般的情况的数学描述如下：对于一个图中定义A子图和B子图[3]，它们之间的所有边的权值之和可以由邻接矩阵W的一般形式求解如下：