Discriminative fuzzy 𝐾-meansclustering withlocalstructure preservation for high-dimensional data

Discriminative fuzzy 𝐾-meansclustering withlocalstructure preservation for high-dimensional data

Yu-Feng Yu,a,∗， Peiwen Wei,a， Xiaoling Wu,a， Qiying Feng,b， Chuanbin Zhang,c

a广州大学统计学系
b广州大学网络空间先进技术研究院
c肇庆大学计算机科学与软件学院

摘要

​  𝐾均值聚类通过将数据点分配到𝐾个不同簇中，是数据挖掘和机器学习领域的重要技术。然而在实际应用中，多个因素会影响其聚类效果。其中，高维数据中冗余特征的混杂问题尤为突出。传统硬核或模糊型𝐾均值聚类方法往往难以有效处理这类高维数据。本文提出了一种创新模型——判别式模糊𝐾均值聚类，该模型将判别投影与𝑝-拉普拉斯图正则化整合到统一框架中。具体而言，该模型在将原始数据投影至低维空间时，既能有效抑制冗余特征的负面影响，又能显著提升判别能力。该方法通过在隶属度矩阵上应用𝑝-拉普拉斯图正则化，同时保留了数据的结构局部性特征。因此，对于高维数据，聚类性能得到显著提升。最后，我们提出了一种有效算法来解决所构建的优化问题。在基准数据集上获得的实验结果令人鼓舞，充分证明了所提方法的优越性。

1.引言

​  聚类是数据挖掘与机器学习领域的重要课题，作为通用性强、效果显著的技术手段，已在人脸识别[1,2]、车辆识别[3]、特征选择/降维[4,5]及图像分割[6-8]等多个领域得到广泛应用。其核心目标在于揭示数据的内在结构，并将样本智能地分配到不同类别[9]。过去数十年间，各类聚类算法在学术界和工业界持续引发广泛关注，涌现出多种改进方案：包括经典𝐾均值聚类（KM）[10]、模糊𝐾均值聚类（FKM）[11]、最大间隔聚类[12]以及谱聚类[13]等。其中，KM算法通过最小化数据点与质心之间的距离，实现对数据的𝐾聚类划分。模糊𝐾均值聚类是KM算法的改进版本，通过学习隶属度将每个数据点分配到特定聚类中。尽管KM和FKM算法简单实用，但传统硬核或模糊版的𝐾均值聚类对离群值和噪声具有较差的鲁棒性[14]。因此，学界针对这一问题提出了多种相关研究方法。例如，Zhang et al. [15]在岭回归聚类框架中引入了非相关约束条件，以避免可能出现的简单解。Guo et al. [16]则在模糊聚类模型中添加了隶属度亲和套索项，从而显著提升了聚类效果。Rezaee et al. [17]将聚类问题视为博弈论中的讨价还价过程，并提出了一种基于博弈的𝐾均值聚类算法。这些算法在处理含异常值和噪声的数据聚类时展现出显著优势。然而，该方法在聚类过程中未能有效区分高维数据中的判别性特征与冗余特征。
​  随着科技发展，现实世界中的数据往往以高维特征呈现。来自不同领域的高维数据集包含大量属性，其中部分特征存在冗余。如何对具有冗余特征的高维数据进行聚类分析，始终是业界面临的重大挑战。Borlea et al. [18]提出了一种统一算法，将FCM和KM聚类方法相结合，并通过BigTim平台的分布式计算技术，在处理大规模数据时显著提升性能。Song et al. [19]则开发出一种混合特征选择算法，巧妙融合了相关性引导聚类与粒子群优化技术，为高维数据分析提供了更有效的解决方案。Pehiven et al. [20]提出了一种乘性模糊回归函数（MFRF），该函数采用一种新的乘性模糊聚类算法，用于改进模糊系统建模。Reformat et al. [21]提出了一种针对知识图谱实体的聚类方法，这些实体以带有不确定性等级的命题形式呈现，并采用余弦相似度来确定实体间的相似性。此外，许多算法通过联合应用聚类与降维技术，有效应对高维数据问题并降低冗余特征的影响。一种直观的方法是先对高维数据进行降维处理，再在低维子空间中开展聚类分析。PCAKM是一个典型代表，它首先采用主成分分析（PCA）[22]来降低数据维度，并在低维空间中进行KM聚类。Ding等人[23]提出了LDA-KM方法，该方法首先使用𝐾均值聚类生成类别标签，然后通过线性判别分析（LDA）[24]来学习子空间。与文献[23]不同，Yin et al. [25]在模糊𝐾均值聚类中引入最大熵方法进行类别标签学习，随后采用广义LDA进行投影操作。Hou et al. [26]则通过模式收缩技术先学习子空间再进行数据聚类。这些方法将降维和聚类处理割裂为独立步骤，即降维过程与后续聚类环节互不关联[27]。
​  近年来，针对高维数据处理，学界提出了多种将降维与聚类相结合的创新方法。这些研究突破了传统方法的局限，通过构建联合框架实现降维与聚类的协同优化。例如，Hou et al. [27]提出了一种统一优化目标函数，该函数通过最大化主成分分析模型与𝐾均值聚类之间的差异来实现，并开发出迭代算法，可同步优化投影矩阵、指示矩阵和质心参数。类似地，Nie等人[9]采用主成分分析（PCA）学习子空间，并提出了一种名为模糊𝐾均值聚类与判别性嵌入（EFKM）的聚类框架。EFKM通过最小化模糊𝐾均值聚类与PCA之间的比率来实现子空间学习和聚类。局部保持投影（LPP）[28]能够保留低维空间中的局部邻域特征。为此，Zhou et al. [29]提出了一种投影模糊𝐾均值聚类算法，该算法结合了局部保持投影与模糊𝐾均值聚类方法来处理高维数据。Chen et al. [30]则将数据集划分为若干子集以学习降维器，并提出了一种投影最小二乘回归子空间聚类方法。Zhou et al. [31]提出了自适应多重聚类集成方法（CEAM），这是一种通过扩散增强算法提升性能的创新技术。Oskouei et al. [32]开发了一种新型半监督模糊聚类算法，通过特征融合与聚类权重优化显著提升了聚类效果。Chen et al. [33]则运用核心块识别技术和快速密度可达性评估机制，有效增强了DBSCAN算法在大规模数据集上的表现。Ding et al. [35] 提出了一种创新的高维流数据聚类算法。该算法通过将基于窗口的主成分分析与反馈控制相结合，能够自适应调整参数并最小化概念漂移，从而提升聚类准确性和效率。此外，部分研究者还提出了基于特征选择的子空间聚类算法。Long et al. [36]将特征选择与𝐾均值聚类整合到统一框架中，提出了一种灵活的子空间聚类算法，并采用\(l_{2,p}\)范数来获得稳健性能。Wang et al. [37]则引入特殊选择矩阵而非特征值分解进行特征选择，提出了一种快速自适应𝐾均值子空间聚类方法，能有效筛选最具代表性的子空间。这些方法虽然将子空间学习与聚类整合到联合框架中，但未能充分考虑数据的局部信息特征。
​  在本文中，我们提出了一种称为判别性模糊𝐾均值聚类（DFKC）的新型模型，该模型将判别性投影和模糊𝐾均值聚类整合到一个联合框架中。
​  具体而言，DFKC在将原始数据投影到低维空间时，能够有效抑制冗余特征的负面影响并增强判别能力。同时，在学习投影矩阵过程中还能实现聚类分析。近年来，基于图的正则化技术作为保留数据结构局部性特征的有效手段已得到广泛应用[38,39]。例如，Guo et al. [16]提出了一种模糊聚类模型，通过在通用目标函数中引入基于隶属度亲和性的正则化项来保持局部信息；Wang et al. [40]则构建了基于随机傅里叶特征的模糊聚类框架，并在模型中加入𝑝-拉普拉斯正则化项[41]以维持局部性特征。受这些研究启发，我们在提出的联合框架中嵌入了𝑝-拉普拉斯图正则化项，从而有效保留数据的局部特性。本研究的主要贡献包括：

• 我们直接将判别投影技术嵌入模糊𝐾均值聚类框架，有效抑制冗余特征的负面影响，同时增强对高维数据的判别能力。此外，在联合框架中引入了𝑝-拉普拉斯图正则化项，有助于保留局部信息。
• 在本文提出的框架中，将降维、模糊𝐾均值聚类和局部性保持等思想有机地结合在一起。
• 开发一种有效的算法来解决所提出的框架，并讨论所提出方法在参数敏感性方面的效率。
• 在各种聚类任务上的实验表明，与最先进的方法相比，提出的方法可以实现有竞争力的性能。

​  本文结构安排如下：第二章将定义本文使用的符号体系并综述相关研究；第三章提出DFKC模型及其高效求解算法；第四章通过实验验证方法的有效性并分析参数敏感性；最后在第五章对全文进行总结。

2.准备工作

​  本节将回顾相关研究。向量用粗体小写字母表示，例如𝐱。矩阵用粗体大写字母表示，例如𝐗，其中矩阵𝐗的第𝑖th列记作\({\mathbf x}_i\)，第𝑖th行第𝑗th列元素记作\({x}_{i,j}\)。符号\({\mathbf X}^T\)表示矩阵𝐗的转置矩阵。

2.1. K-means聚类

​  给定一个包含𝑁个样本的数据集\({\mathbf X}=[{\mathrm x}_1,{\mathrm x}_2,\cdot\cdot\cdot,{\mathrm x}_N]\in R^{D\times N}\)，其中特征数量为𝐷，样本数为\({\mathrm x}_i\in R^D\)。聚类算法的目标是通过最小化以下目标函数，将数据集𝐗划分为𝐾个互不相交的簇： \[J(\mathbf{C},\mathbf{F})=\sum_{i=1}^{N}\sum_{k=1}^{K}c_{i k}\|\mathbf{x}_{i}-\mathbf{f}_{k}\|_{2}^{2}.\] ​  其中\(\mathbf{C}=[c_{i k}]_{N\times k}\)是聚类指示矩阵，其元素表示为：当且仅当\({\mathrm x}_i\)属于第𝑘个聚类时，\(c_{i k}=1\)，否则\(c_{i k}=0\)。\(\mathbf{F}=[\mathbf{f}_{1},\mathbf{f}_{2},\ldots,\mathbf{f}_{K}]\in R^{D\times K}\)是聚类中心矩阵，而\(\mathbf{f}_{k}\in R^{D}\)则是第𝑘个聚类的质心。

2.2. 模糊K-means聚类

​  模糊𝐾均值聚类[11]旨在通过学习隶属度将每个样本分配到特定的聚类中。其目标函数可表述如下： \[\begin{aligned}\operatorname*{min}J(\mathbf{U},\mathbf{F})&=\sum_{i=1}^{N}\sum_{k=1}^{K}u_{i k}^{m}\|\mathbf{x}_{i}-\mathbf{f}_{k}\|_{2}^{2}\\&s.t.\quad\sum_{k=1}^{K}u_{i k}=1,0\leq u_{i k}\leq1,i=1,\dots,N\end{aligned}\] ​  其中\(\mathrm{U}=\left[u_{i k}\right]_{N\times K}\)是隶属度矩阵，\(𝑢_{𝑖𝑘}\)表示样本属于第𝑘个聚类的隶属度。参数𝑚（取值范围大于1）是模糊化参数，用于控制模糊程度的高低。
​  通过使用拉格朗日乘数，簇中心\(\mathbf{f}_{K}\)和隶属度\(𝑢_{𝑖𝑘}\)根据以下方程交替更新： \[u_{i k}=\left[\sum_{j=1}^{K}\left({\frac{d_{i k}}{d_{j k}}}\right)^{\frac{2}{m-1}}\right]^{-1}\] ​  和 \[\mathbf{f}_{k}={\frac{\sum_{i=1}^{N}u_{i k}^{m}\mathbf{x}_{i}}{\sum_{i=1}^{N}u_{i k}^{m}}},\] ​  其中\(d_{i k}=\|\mathbf{x}_{i}-\mathbf{f}_{k}\|_{2}^{2}\)。

2.3.判别式嵌入式聚类

​  判别式嵌入聚类（Discriminative embedded clustering，简称DEC）[27]是一种将主成分分析（PCA）与𝐾均值算法相结合的联合框架，专门用于高维数据聚类。假设投影矩阵为\({\textbf{P}}\in{\mathit{R}}^{D\times d}\)，低维样本可表示为\(\mathbf{y}_{i}=\mathbf{P}^{T}\mathbf{x}_{i}\)。在低维空间中，𝐾均值聚类的数学表达式可表示为 \[J(\mathbf{C},{\tilde{\mathbf{F}}})=\sum_{i=1}^{N}\sum_{k=1}^{K}c_{i k}\Vert\mathbf{y}_{i}-{\tilde{\mathbf{f}}}_{k}\Vert_{2}^{2},\] ​  其中\(\mathbf{\tilde F}=[\mathbf{\tilde f}_{1},\mathbf{\tilde f}_{2},\ldots,\mathbf{\tilde f}_{K}]\in R^{d\times K}\)是聚类中心矩阵。
​  通过将(5)与PCA相结合并进行简单的代数运算，DEC的目标函数可表示为： \[\begin{aligned}\operatorname*{max}J(\mathbf{P},\mathbf{C},{\bar{\mathbf{F}}})&=T r(\mathbf{P}^{I}\mathbf{S}_{t}\mathbf{P})-\lambda||\mathbf{P}^{I}\mathbf{X}-{\bar{\mathbf{F}}}\mathbf{C}^{I}||_{F}^{2}\\&s.t.\quad \mathbf{P}^{T}\mathbf{P}=\mathbf{I}\end{aligned}\] ​  其中\({\bf S}_{t}=\textstyle{\sum_{i=1}^{N}({\bf x}_{i}-{\overline{\bf x}})({\bf x}_{i}-{\overline{\bf x}})^{T}}\)表示总方差矩阵，样本均值为\(\overline{\bf x}\)。由于式(6)中的优化问题不具备联合凸性，因此需要采用迭代算法交替优化投影矩阵、指示矩阵和质心。

（PS：拉普拉斯算子到𝑝-拉普拉斯算子：\(\Delta_{2}f=\nabla\cdot(\nabla f)\)到\(\Delta_{p}f=\,\nabla\cdot(|\nabla f|^{p-2}\nabla f)\)）

3.所提出的模型

3.1. 动机

​  如前所述，某些因素会降低现实应用中的聚类效果，而包含冗余特征的高维数据正是聚类过程中的关键问题。虽然多数传统聚类方法在低维数据中表现良好，但高维数据因特征冗余会导致性能下降。为解决这一难题，部分算法采用降维与聚类分离的策略[23,26]，但所得子空间可能无法满足后续聚类任务的需求[27]。因此，有研究将子空间学习与聚类整合到联合框架中[36,37]。然而这些算法存在两大局限：其一，部分方法仅对样本点进行投影操作，忽视了簇中心的作用；其二，在保持局部信息方面存在不足。
​  由于数据的复杂性和结构特性，保留局部信息是聚类任务的核心要素。这有助于捕捉样本的局部结构特征，并在聚类结果中保留相关信息。基于图的正则化技术是保留局部信息的有效手段，已在聚类[42]和模式识别[41,43]领域得到应用。𝑝-拉普拉斯算子作为图拉普拉斯算子的非线性推广形式，为更好地保留局部结构提供了强有力的理论支撑[41]。实验表明，𝑝-拉普拉斯图正则化项能显著提升机器学习和聚类任务中的模型性能。
​  针对上述缺陷，我们提出了一种名为判别式模糊𝐾均值聚类（DFKC）的创新模型。首先，我们将判别式投影与模糊𝐾均值聚类整合到联合框架中，对样本点和聚类中心同时进行投影操作。其次，通过将𝑝-拉普拉斯图正则化项嵌入该联合框架，有效保留了数据的局部性特征。

3.2. 目标函数构造

​  受DEC [27]的启发，我们在模糊𝐾均值聚类框架中嵌入投影矩阵，以在低维子空间中进行聚类。目标函数定义如下： \[\begin{aligned}\operatorname*{min}J(\mathbf{P},\mathbf{U},\mathbf{F})&=\sum_{i=1}^{N}\sum_{k=1}^{K}u_{i k}^{m}\|\mathbf{P}^{T}\mathbf{x}_{i}-\mathbf{P}^{T}\mathbf{f}_{k}\|_{2}^{2}\\&s.t.\quad\sum_{k=1}^{K}u_{i k}=1,0\leq u_{i k}\leq1,i=1,\dots,N\end{aligned}\] ​  沿用文献[16]的设定，我们在后续讨论中固定模糊化参数𝑚=2。如公式(7)所示，投影操作同时作用于样本点和聚类中心。通过映射公式\(\mathbf{P}^{T}\mathbf{x}_{i}\)将样本点从原始空间\(𝑅^𝐷\)映射到降维空间\(𝑅^𝑑\)，通常满足条件：当投影到低维空间时，样本点与对应聚类中心的距离更接近。这种设计有效降低了特征冗余对数据降维的负面影响，同时确保样本在低维空间中的分布更加集中。
​  接下来，我们探讨如何在聚类过程中实现降维。主成分分析（PCA）作为经典降维技术，在图像分类[44]、面部表情识别[45]和高维数据聚类[9,27]等领域得到广泛应用。该方法通过将原始变量重组为一组相互独立的综合变量，同时利用优化变量尽可能完整地反映原始数据信息。从数学角度出发，我们将PCA与模糊𝐾均值聚类相结合，构建如下模型： \[\begin{aligned}J(\mathbf{P},\mathbf{U},\mathbf{F})&=\sum_{i=1}^{N}\sum_{k=1}^{K}u_{i k}^{2}\|\mathbf{P}^{T}\mathbf{x}_{i}-\mathbf{P}^{T}\mathbf{f}_{k}\|_{2}^{2}-\mu\mathrm{Tr}(\mathbf{P}^{T}\,\mathrm{S}_{t}\mathbf{P})\\&s.t.\quad\sum_{k=1}^{K}u_{i k}=1,0\leq u_{i k}\leq1,i=1,\dots,N\end{aligned}\] ​  从公式(8)可以看出，本文提出的模型是一个用于聚类和降维的统一框架。

3.3.具有局部结构保留的判别性模糊𝐾均值聚类

​  通过应用图正则化技术，前一节提出的聚类与降维统一框架得到了进一步优化。该方法能确保样本点之间相互关联时，其相似性隶属度的学习过程得到有效保障。同时，该方法能够保留数据的局部特性。受文献[40]的启发，我们在提出的统一框架中引入了𝑝-拉普拉斯图正则化技术。
​  我们首先定义一个最近邻图。对于该图，设相似度矩阵为𝐖=[𝑤𝑖𝑗]𝑁×𝑁。其中第𝑖th行第𝑗th列的元素表示样本𝐱𝑖和样本𝐱𝑗之间的距离。本文采用热核相似度方案[46]，相似度矩阵𝑤𝑖𝑗的计算公式如下： \[w_{ij}=\begin{cases}e^{-{\frac{|\mathbf{x}_{i}-\mathbf{x}_{j}|}{\sigma}}} &j\in N\,B_{i}\\0 &otherwise\end{cases}\] ​  其中𝜎用于调节相似度衰减速度，我们将其设定为0.5。𝑁𝐵𝑖是𝑖th样本的邻域集合。随后我们得到对称相似度矩阵\(\mathbf{W}=(\mathbf{W}+\mathbf{W}^T)/2\)。最后，我们构建了一个具有局部结构保留功能的判别式模糊𝐾均值聚类框架，具体如下： \[\begin{aligned}J(\mathbf{P},\mathbf{U},\mathbf{F})&=\sum_{i=1}^{N}\sum_{k=1}^{K}u_{i k}^{2}\|\mathbf{P}^{T}\mathbf{x}_{i}-\mathbf{P}^{T}\mathbf{f}_{k}\|_{2}^{2}-\mu\mathrm{Tr}(\mathbf{P}^{T}\,\mathrm{S}_{t}\mathbf{P})\\&+\lambda\sum_{k=1}^{K}\sum_{i=1}^{N}\sum_{j\in NB_{i}}\omega_{i j}(u_{i k}-u_{j k})^{p}\\\&s.t.\quad\sum_{k=1}^{K}u_{i k}=1,0\leq u_{i k}\leq1,i=1,\dots,N\end{aligned}\] ​  其中𝜆和𝜇是两个正的权衡参数，而𝑝是一个不小于1的标量。我们在实验部分讨论了这些参数在方法中的作用。公式（10）右侧包含三个组成部分：第一项旨在最小化由样本点与低维空间中聚类中心构成的聚类误差；第二项是主成分分析，用于学习投影矩阵𝐏。通过约束条件\(\mathbf{P}^{T}\mathbf{P}=\mathbf{I}\)，数据结构在投影过程中得以保持不变；第三项则确保邻近样本点的隶属度保持相近。

3.4.优化算法

4.实验结果与分析

5.结论

​  本文提出了一种名为判别式模糊𝐾均值聚类（DFKC）的新框架，用于学习投影矩阵并实现模糊聚类。我们摒弃了在原始数据上直接进行聚类的传统做法，而是将原始高维数据映射到低维空间，从而减少冗余特征的负面影响并提升判别能力。此外，我们将𝑝-拉普拉斯图正则化方法融入该统一框架，以保持数据的局部性特征。针对该框架，我们推导出了一种高效的优化算法。通过在真实数据库中开展多种聚类任务的实验验证，我们获得了令人信服的结果，充分证明了所提出的DFKC方法具有显著优势。