基于谱嵌入与粒度球划分的聚类方法和应用

本发明属于图像处理、数据挖掘与机器学习，具体的未一种基于谱嵌入与粒度球划分的聚类方法和应用，尤其适用于对大规模、高维且具有非线性结构的数据集进行高效、鲁棒的无监督聚类分析，可广泛应用于图像分割、文本挖掘、生物信息学、推荐系统及视频监控等场景。

背景技术：

1、聚类分析是无监督学习的核心任务，旨在将数据样本划分为若干组，使得组内样本高度相似、组间样本差异显著。随着信息技术的发展，图像、文本、生物信息等高维数据呈指数级增长，对聚类算法的可扩展性、准确性和鲁棒性提出了更高要求。

2、谱聚类（spectral clustering）是一类经典的聚类方法，其通过构建数据点的相似度图并对其拉普拉斯矩阵进行特征分解，将原始高维数据投影到低维谱嵌入空间，从而能够有效捕捉数据中的非线性流形结构。相比于k-means等传统方法，谱聚类在处理复杂形状的数据分布时具有明显优势。

3、然而，传统谱聚类方法在大规模数据场景下面临严峻挑战。首先，其核矩阵构建与特征分解的计算复杂度通常高达甚至，使得算法难以实际部署于包含数十万乃至百万级样本的数据集。其次，高维空间中距离度量易发生性能退化，基于欧氏距离的相似性矩阵难以准确刻画样本间的真实关联。此外，谱聚类对核函数类型、带宽参数和近邻数目等超参数极为敏感，而不同数据集的最优参数区间差异较大，缺乏统一的配置准则，且聚类数目通常需预先指定，在缺乏先验知识的场景下主观设定会直接导致性能偏差。最后，谱聚类在完成嵌入后仍依赖k-means等硬划分方法进行最终聚类，缺乏对边界点和噪声点的显式拒识机制，影响了聚类结果的鲁棒性和可解释性。为克服上述缺陷，近年来研究者提出了多种改进方案。例如，现有方法将粒球生成与谱聚类相结合，但该方法首先在原始特征空间中对数据进行粒球划分，然后将粒球作为节点进行谱聚类。该技术路线旨在利用粒球来简化谱聚类的输入规模，但未能解决谱聚类对超参数敏感和需预设聚类数的问题，且粒球在原始空间中生成，难以充分反映数据的非线性流形结构。

4、综上，现有技术中尚缺乏一种能够将谱嵌入对非线性流形结构的识别能力与粒球计算的自适应覆盖和噪声拒识能力进行有机融合的聚类方案。具体而言，现有方案均遵循“先粒球划分、后谱聚类”的技术路线，即粒球在原始空间生成，谱聚类仅作为最终聚类工具，二者功能分离且顺序固定，未能实现从数据空间优化到粒球结构学习的协同增强。因此，亟需一种新的聚类方法，能够在不依赖预设聚类数的前提下，利用谱嵌入优化粒球生成的空间，同时保持对大规模数据的计算效率和鲁棒性，以有效解决上述现有技术中存在的诸多问题。

技术实现思路

1、有鉴于此，本发明的目的在于提供一种基于谱嵌入与粒度球划分的聚类方法和应用，通过先谱嵌入后粒球覆盖的两阶段架构，解决了现有谱聚类计算复杂度高、依赖预设聚类数、对超参数敏感且缺乏噪声拒识机制的问题，在保持非线性结构识别能力的同时，实现了大规模数据聚类的高效性、自适应性与鲁棒性。

2、为达到上述目的，本发明提供如下技术方案：

3、本发明首先提出了一种基于谱嵌入与粒度球划分的聚类方法，包括如下步骤：

4、s1，随机子集采样：获取包含个样本的输入数据集；判断数据集中的样本数是否超过预设阈值：若是，则通过随机采样从所述输入数据集中选取个代表点构成拟合子集，并将剩余样本归入剩余子集；若否，则直接将全部样本作为拟合子集；

5、s2，谱嵌入：对所述拟合子集执行谱嵌入操作，将原始高维空间中的数据投影至低维谱嵌入空间，得到谱嵌入矩阵；

6、s3，初始聚类与粒度球优化：在所述谱嵌入空间中执行kmeans聚类，获得初始聚类标签；对每个簇执行自适应粒球覆盖，以簇中心为球心，遍历候选半径，基于特异性、覆盖度与同质性三个准则的加权几何平均确定各簇的最优粒球半径；根据各簇的所述最优粒球半径对样本进行覆盖并分类标记，将仅被单个粒球覆盖的样本标记为核心点并赋予对应簇标签，将被多个粒球同时覆盖的样本标记为边界点，将未被任何粒球覆盖的样本标记为噪声点；由此在所述谱嵌入空间中构建有标签数据集与无标签数据集；

7、s4，knn标签扩展：采用k近邻分类器，将标签从所述核心点传播至所有未标记样本，所述未标记样本包括所述边界点、所述噪声点及所述剩余子集中的全部数据，获得全量数据的最终聚类结果。

8、进一步，步骤s2中，所述谱嵌入的方法步骤为：

9、s21：构建相似度矩阵：

10、

11、其中：为样本和之间的相似度；为核函数；和分别为拟合子集中的任意两个样本；

12、s22：计算度矩阵：

13、

14、其中：为度矩阵的第个对角元素；

15、s23：计算拉普拉斯矩阵，进而计算归一化拉普拉斯矩阵：

16、

17、其中：为单位矩阵；

18、s24：求解所述归一化拉普拉斯矩阵的前个最小特征值对应的特征向量，拼接为谱嵌入矩阵，其中：为聚类数目。

19、进一步，步骤s3中，所述特异性、覆盖度与同质性分别表示为：

20、

21、

22、

23、其中：表示特异性；表示覆盖度；表示同质性；为候选半径；为当前粒球覆盖的样本数；为当前簇的样本总数；为粒球内样本标签分布的香农熵；为聚类数目。

24、进一步，通过加权几何平均将三个准则融合为综合评分：

25、

26、其中：表示综合评分；、和分别为特异性、覆盖度与同质性的权重系数；

27、取综合评分最高的半径作为各簇的最优粒球半径。

28、进一步，步骤s3中，所述边界点和所述噪声点被标记为-1，形成显式拒识机制，使得聚类结果能够区分核心簇结构与不确定样本。

29、进一步，步骤s4中，对于待分类样本，其预测标签由个最近邻的加权投票决定，每个临近样本的投票权重与该临近样本到所述待分类样本的欧氏距离成反比；所述临近样本数默认取，其中：为所述有标签数据集的样本数量。

30、进一步，在步骤s1至步骤s4被执行之前或期间，还执行三阶段参数扫描，以确定所述谱嵌入、所述粒球优化和/或所述knn标签扩展中涉及的至少一个超参数；所述三阶段参数扫描包括：

31、第一阶段，粗扫描：在预设大步长范围内扫描参数空间，定位候选参数区间；

32、第二阶段，精扫描：在所述候选参数区间内以小步长进行扫描，确定最优参数值附近区域；

33、第三阶段，边界延展收敛：沿所述最优参数值两侧逐步延展扫描范围，直至聚类性能停止提升，以确定最终最优参数。

34、本发明还提出了一种如上所述基于谱嵌入与粒度球划分的聚类方法的应用，所述方法在以下至少一种实际应用场景中执行聚类任务：

35、图像分割场景：对高分辨率遥感影像或医学影像进行像素级聚类分割；

36、文本挖掘场景：对互联网文档、新闻、专利文献或科学文献进行主题聚类；

37、生物信息学场景：对单细胞rna测序数据进行细胞类型识别与聚类分析；

38、推荐系统场景：对用户行为数据进行用户画像构建和群体划分；

39、视频监控场景：对海量视频帧图像进行场景聚类和行为模式识别；

40、网络安全场景：对网络流量数据进行异常检测与分类；

41、工业物联网场景：对传感器数据进行设备状态划分与聚类分析；

42、社交网络场景：对社交网络用户进行社区发现与群体识别。

43、本发明的有益效果在于：

44、本发明基于谱嵌入与粒度球划分的聚类方法，通过随机子集采样、谱嵌入、粒球覆盖和knn标签扩展的四步流程，取得了以下技术效果.

45、（1）计算效率显著提升。传统谱聚类在全量数据上需构建相似度矩阵并进行特征分解，计算成本极高。本发明通过随机子集采样将谱分解约束在个代表点上，谱分解复杂度降至；knn标签扩展阶段复杂度为。整体复杂度为；当远小于时退化为，呈近似线性增长，使算法能够高效处理百万级大规模数据集。

46、（2）聚类精度高，尤其擅长非线性结构。实验结果表明，本发明gsc算法在twocircles非线性合成数据集上达到100%的完美聚类准确率，而k-means、gmm、层次聚类、dpc、torqueclustering等五种对比算法的ari均接近0，完全失效。这直接证明了“先谱嵌入后粒球覆盖”的技术路线能够有效揭示数据的非线性流形结构，使粒球在优化的嵌入空间中进行自适应覆盖。

47、（3）自适应聚类，无需预设聚类数。传统谱聚类需预先指定聚类数目，在无先验知识时主观设定会直接导致性能偏差。本发明通过特异性、覆盖度与同质性三个准则的加权几何平均自适应确定各簇的最优粒球半径，粒球覆盖过程自动确定簇结构，无需预设聚类数，对超参数的鲁棒性显著增强。

48、（4）显式拒识机制，提升鲁棒性。本发明通过粒球覆盖将样本显式分为核心点、边界点和噪声点三类，边界点和噪声点不参与后续聚类，有效解决了传统谱聚类缺乏对边界点和噪声点显式拒识机制的问题。

49、（5）泛化性能优异。在15个公开基准数据集上，本发明gsc算法在9个数据集上取得最优ari结果；friedman检验确认其平均排名（1.47），显著优于k-means、gmm、层次聚类、dpc、torqueclustering等五种对比算法，证明了本发明在多样化数据类型上的通用性和稳定性。