基于非负约束的谱聚类方法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于非负约束的谱聚类方法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：聚类问题一直是模式识别和机器学习领域一个比较活跃而且极负挑战性的研究方向。谱聚类是近年来兴起的一类较流行的聚类方法。该文将非负约束引入到传统的谱聚类方法中，提出了一种基于非负约束的谱聚类方法。非负约束已在许多应用领域被证明是一种有用的性质。文中对比实验表明，基于非负约束的谱聚类方法在整体上明显优于传统的谱聚类方法。

关键词：谱聚类；非负约束；聚类；非负矩阵分解

中图分类号：TP311文献标识码：A文章编号：1009-3044(2011)17-4165-03

A Spectral Clustering Method with the Nonnegative Constraint

WANG Chun-teng1, FU Chuan-yi2, Xing Jie-qing2

(1.College of Electronic Information Engineering of Qiongzhou university, Sanya 572022, China; 2.Department of Modern education technology, Qiongtai teachers college, HaikoU 571100,China)

Abstract: Clustering is a challenging and active research topic in pattern recognition and machine learning. Spectral clustering is a new method for clustering. In this paper, the nonnegative constraint is introduced into the traditional spectral clustering. The NMF-based is proposed. The advantage of the nonnegative constrain has been conformed in many application fields. The results of the experiments in the paper evaluate the proposed method.

Key words: spectral clustering; nonnegative constraint; clustering; nonnegative matrix factorization

聚类分析是模式识别和机器学习中重要研究课题之一。所谓聚类(clustering)就是将给定数据对象集合划分为多个类或簇(cluster)，使得在同一簇中的对象之间具有较高的相似度，而不同簇中的对象差异较大。在现有的聚类方法中，k-均值聚类是最简单、使用最普遍的方法之一。类似于K-均值，这些传统的聚类算法大多是基于中心的方法，是建立在凸球形的样本空间上。当样本空间不满足凸形时，算法容易陷入局部最优。谱聚类算法(spectral clustering algorithm)避免了这个问题。该算法建立在图论中的谱图理论基础上，其本质是将聚类问题转换为图的最优划分问题。与传统的聚类算法相比，谱聚类算法将聚类转换为一个代数上的矩阵求解问题，具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点[1]。

在现实世界中，许多信号数据是分非的，例如，图像、文本等。由这些现实领域收集的样本组成的数据矩阵是非负数据 矩阵。进过一般的谱运算，例如SVD、PCA等，得到的目标特征向量中通常含有许多负值。在许多应用中，非负约束被引入。我们希望得到的目标特征向量中仅含有非负的数据。这个约束在许多情况下是很有意义的。一方面，使得到的样本特征具有现实的物理意义；另一方面，这种约束的引入更有利于在目标映射中保持样本的局部特征。非负矩阵分解（Non-negative Matrix Factorization，简称NMF）正是为解决这个问题而提出的[2-3]。自提出以来，许多文献对其进行了研究。一些文献是基于算法和模型变形的[2-6]，而另一些是基于应用的，非负矩阵分解已经被成功地应用于许多领域，包括生物信息学[7-8]，物理学[9]，多媒体数据[10]，文本挖掘[11-12]等。其中最成功的应用是数据聚类[13]。

本文就NMF的这种优势引入到传统的谱聚类方法中，提出了一种基于非负约束的谱聚类方法NMFSC。

1 非负矩阵分解

给定一个n×m的非负矩阵V，其中n＜m。

目标问题：希望得到V的近似分解表示，即V≈WH。其中W和H分别为n×r和r×m的非负矩阵（W，H中所有元素均非负）。r是事先预定的参数并且通常应该满足r

算法1非负矩阵分解算法

步骤1初始化W和H使其元素是[0，1]间的随机数。

步骤2在EM框架下，采用梯度下降法优化目标函数||V-WH||2。固定W，更新H，然后固定更新后的H来更新W，不断重复这个过程直到收敛。

其中，H和W的计算规则如下：

(1)

(2)

文献[2]给出了该算法的更多细节和理论结果。

2 非负数据的谱聚类

本节研究基于非负约束的谱聚类方法。在NMF的基础上，结合K-均值算法，设计了一种满足非负约束的谱聚类算法――NMF based Spectral Clustering (NMFSC)。

假设给定一个样本集合，包含n个样本，每个样本用一个m维向量表示。这个样本集合表示为样本矩阵Xn×m={x1,x2,…,xn}。

传统的谱聚类算法（SC）简要框架如下：

1）构建邻接图（同NMFSC）

2）构建相似矩阵（同NMFSC）

3）计算归一化拉普拉斯矩阵：，其中D为对角阵，

4）计算L的最小的r个特征值对应的特征向量

5）对矩阵V进行归一化处理得到矩阵，

6）令yi∈Rk对应矩阵U的第i个行向量（i=1,…,n）

7）对于数据点y1,y2,…,yn，利用K-均值算法聚成s个类。

为使最终得到的数据点只包含非负数据，本文提出一种基于非负约束的谱聚类算法（NMFSC）。将非负矩阵分解过程引入到数据映射过程中，具体步骤如下：

1）构建邻接图：令G表示由n个节点组成的图。在节点i和j之间连一条边，如果i是j的k个最近邻之一，或者j是i的k个最近邻之一。

2）构造相似矩阵：由边的权构成的相似度矩阵W是一个通过高斯核函数计算得到的稀疏矩阵。如果节点i和j相连，则令：

3）在W矩阵上施行NMF算法，得到W的近似分解表示：W=VH。其中，V，H均为非负矩阵，V∈Rn×r，H∈Rr×n。

4）对矩阵V进行归一化处理得到矩阵，

5）令yi∈Rk对应矩阵U的第i个行向量（i=1,2,…,n）

6）对于数据点y1,y2,…,yn，利用K-均值算法聚成s个类。