一种适合于非线性高维数据的谱聚类算法

王鸿菲 杜洪波* 林凯迪 姚云飞 朱立军

1(沈阳工业大学理学院 辽宁 沈阳 110870)

2(天津大学计算机科学与技术学院 天津 300050)

3(北方民族大学信息与计算科学学院 宁夏 银川 750021)

0 引 言

随着信息技术、移动互联网的快速发展，数据呈爆炸式增长。聚类算法作为数据挖掘中一种无监督学习方法，在图像识别、生物学和统计学等领域中赢得广泛应用[1]。谱聚类是聚类算法中研究热点之一。一般算法只能解决凸优化问题，在非凸优化问题中容易陷入局部最优，而谱聚类能在任意形状分布的数据中正确聚类。谱聚类是基于谱图划分理论[2]，构造相似矩阵，从而构造拉普拉斯矩阵，进而求特征值和特征向量，根据特征向量内在的关系进行重聚类。

谱聚类中一般利用高斯核函数度量相似性。高斯核参数σ和聚类个数需要人工确定。何家玉[3]提出利用局部尺度高斯核函数替代传统的高斯核函数，避免尺度参数的人为确定；王超[4]提出用和第k近邻的距离代替σ。对于聚类个数的确定，李金泽等[5]提出基于本征间隙自动确定聚类个数，在本征间隙序列中第一极大值对应下标即为聚类数。本文拟对高斯核函数中的σ参数及聚类个数进行优化，建立自适应谱聚类算法。

近年以来，许多学者对非线性高维聚类算法进行研究。传统的非线性高维聚类问题一般是先通过非线性降维约简方法将非线性高维数据映射到线性低维空间中，在低维空间进行聚类。对于非线性数据，文献[6]提出了一种新的无监督非参数型的聚类算法支持向量聚类；……