基于乘法更新规则的k-means与谱聚类的联合学习

陈 迪,刘惊雷

（烟台大学计算机与控制工程学院，烟台，264005）

聚类算法作为机器学习和数据挖掘中最基本的数据分析技术之一，受到各个领域的广泛关注.聚类的目的是将数据集合分成若干簇，使得同一簇内数据点的相似度尽可能大，而不同簇间数据点的相似度尽可能小.在过去的几十年里，大量的聚类方法得到了广泛的发展，并取得了令人瞩目的性能.由于其高效性和简单性，k⁃means聚类方法得到了广泛的研究.为了可视化数据的聚类结构，研究者开发了自组织映射方法［1］，还提出了谱聚类［2］、支持向量聚类［3］和基于核的聚类［4］等聚类算法来研究非线性聚类结构.

k均值型（硬或软）算法在聚类任务和子空间学习中得到了广泛的应用，目前仍是研究的热点.k⁃means聚类［5-6］（又称硬聚类）是一种基于划分的聚类算法，首先通过一定的距离或相似性度量将每个数据样本分配到最近的聚类中，然后更新每个聚类的质心来重新分配数据点.基于划分的聚类算法对在小规模的数据库中发现球状类别很有效，但它本质上属于“爬山”算法，“爬山”算法是一种局部择优的方法，容易收敛到局部最优.k⁃means聚类又是一种基于矩阵分解的聚类方法［7］，Bauckhage［8］证明传统的k⁃means聚类算法的目标函数可以被表达成数据矩阵与其低阶数据矩阵之间差异的Frobenius范数.

基于图的聚类方法［9］通常有三个缺陷.首先，对后处理的要求，例如谱聚类结果需要用k⁃means进行聚类，这会不可避免地引入初值选择带来的不确定性.其次，参数选择的敏感性，现有的大多数基于图的方法都引入了一些额外的参数，而参数选择是一项无监督的任务，对聚类来说不容易.是计算成本高，例如谱聚类的计算复杂度为O()n3.谱聚类［10-11］作为一种广泛应用的基于图的方法，带来了最新的聚类性能.谱聚类算法的目的是通过挖掘数据的非线性结构的相似矩阵来寻找聚类隶属度，包括两个阶段：首先建立一个相似图，然后利用多个准则对图进行划分.

基于矩阵分解的聚类方法的时间成本通常比基于图的聚类方法有很大优势，但这些方法不能处理非线性结构的数据.简单说，基于图的聚类方法性能较好，但受到计算成本高的限制；另一方面，基于矩阵分解的聚类方法比较简便，但不能给出满意的聚类结果.k⁃means是一种基于矩阵分解的聚类方法，虽然速度很快但不能处理非线性数据；谱聚类可以处理非线性数据，但时间成本较高.本文提出基于k⁃means和谱聚类的联合聚类算法（k⁃Means and Spectral Clustering，KMSC），将它们的优点结合起来，并用乘法更新规则［12］来对算法进行优化，KMSC使这两个学习过程能够无缝地集成.在不同类型的数据集上（图像、文本、UCI）做了实验，并与现有的经典聚类方法（k⁃means聚类、谱聚类、非负矩阵分解、k⁃means++、主成分分析法（Principal Components Analysis，PCA）、奇异值分解（Singular Value Decomposi⁃tion，SVD））进行比较，KMSC在聚类精度和标准互信息上有所提高，可以实现更好的聚类效果.

本研究的特点和贡献如下：

（1）针对图像和数据聚类问题，提出一个k⁃means和谱聚类的联合优化框架，将k⁃means和谱聚类的目标函数集成到一个统一的框架中，它包含了k⁃means聚类和谱聚类的优点.

（2）引用乘法更新规则（Multiplication Up⁃date Rule，MUR）来优化KMSC算法，通过不断迭代最终收敛到一个值，它在解决问题的速度以及易于聚类问题的实现方面有良好的表现.

（3）给出算法的理论分析，通过提出的更新规则满足不动点方程和KKT不动点条件证明了KMSC的正确性.具体地，将k⁃means和谱聚类同时进行，避免了谱聚类后处理带来的不确定性.

（4）进行相应的实验.给出k⁃means与KMSC在图像和文本数据集上的收敛曲线，收敛速度非常快，通常在100次迭代内即可收敛；其次，分别在图像数据集（COIL20）、文本数据集（TDT2）和UCI数据集上与现有的经典聚类方法进行比较.实验结果表明，不管什么类型的数据集，该方法都具有较高的聚类精度和标准互信息.

1 相关工作

k⁃means聚类是在欧几里得空间中划分n个数据对象，通过初始中心策略实现k个对象的选择，使其成为聚类中心.对于其他对象，计算每个质心距离，使用最近的归类，再次对每个类簇数据平均值进行计算，得到新的聚类中心；对此过程反复进行迭代计算，直到全部聚类收敛，使类内对象的相似性最大，类间对象的相似性最小.k⁃means聚类算法快速、简单，时间复杂度为O()nkt，n代表数据集中对象的数量，t代表算法迭代的次数，k代表簇的数目，时间复杂度近于线性，适合挖掘大规模数据集，有可扩展性.k⁃means的初始聚类中心是随机选取的，因此可能使同一类别的样本被强行当作两个类的初始聚类中心，则聚类结果最终只能收敛于局部最优解，因此k⁃means算法的聚类效果在很大程度上依赖于初始聚类中心的选择.Duda and Hart［13］在实现k⁃means算法时进行多次初始聚类中心的选择并聚类，从中找到最优解，这个办法很简单，但在数据量较大时实用价值不大.k⁃means聚类算法使用欧式距离作为相似性度量和距离矩阵，计算各数据点到其类别中心的距离平方和，因此k⁃means聚类算法划分的类别都是类球形的，更适用于识别凸形分布、聚类密集的情况.Mao and Jain［14］使用的是Mahalanobis距离，但计算代价太大.k⁃means聚类算法是一个NP难优化问题，无法获得全局最优.Likas et al［15］提出的全局k⁃means聚类算法是基于递增思想的聚类算法，它将k个簇的聚类问题转换成一系列的子聚类问题，同时还提出了快速全局k⁃means聚类算法，对全局k⁃means聚类算法选择下一个簇最佳初始中心的方法进行了改进，但只给出了初始聚类中心选取的算法步骤，缺乏理论证明.Hansen et al［16］提出的全局k⁃means聚类算法是一个启发式增量算法，但不能保证得到全局最优.

谱聚类是一种基于图论的聚类方法，也是一种基于两点间相似关系的聚类方法.由于谱聚类与数据点的维数无关，仅与数据点的个数有关，因而可以避免由特征向量的维数过高所造成的奇异性问题.谱聚类算法又是一个判别式方法，不用对数据的全局结构作假设，而是首先收集局部信息来表示两点属于同一类的可能性，然后根据某一聚类准则作全局决策，将所有数据点划分到不同的数据集合中.通常这样的准则可以在一个特征空间中得到解释，该特征空间由数据矩阵的前k个特征值对应的特征向量组成.谱聚类的本质是通过特征分解将原始的高维数据空间映射到特征的向量空间，然后对低维向量空间中的数据点进行聚类.谱聚类对类的形状、密度等不做过多假设，可以解决比较复杂的聚类问题.相似矩阵和相似图构建的好坏决定谱聚类性能，目前有很多构建方法，例如可以通过ε近邻法、k近邻法、全连接法等来构造相似矩阵，通过最小切（Mincut）、比率切（RatioCut）、归一化分割（Ncut）［17］来构造相似图.但这些方法即使可以取得好的聚类结果，也还是需要更准确地反映数据点之间的近似关系，使相近点之间的相似度更高，相异点之间的相似度更低.谱聚类的优点在于直接通过求解拉普拉斯矩阵的特征向量进行划分，能够识别非凸类型的簇，且该算法建立在谱图理论上，能在任意形状的样本空间上聚类并收敛于全局最优解.但聚类结果通常是通过k⁃means聚类得到的，由于k⁃means对初值敏感，会不可避免地引入初始化带来的不确定性，且聚类效果依赖于相似矩阵，不同的相似矩阵得到的最终聚类效果可能很不同.

本研究将k⁃means和谱聚类联合到一个框架中，利用乘法更新规则进行优化，这样既避免k⁃means收敛于局部最优，也避免谱聚类给后处理带来的麻烦，在一次优化过程中满足各自的约束条件.通过实验与现有的经典聚类算法比较，该算法在聚类精度和标准互信息上都有所提高.

2 相关定义及方法

表1给出下面工作中的符号.

2.1k-means目标函数k⁃means聚类使用k个集群对数据集进行分类，目标函数是最小化误差平方和：

其中，X=[x1，…，xn]为数据矩阵，mk=是簇Ck中的点的个数.特别的，Ding et al［18］已经说明k⁃means聚类的运行结果可以写成矩阵分解的形式，即X=MGT.M包含聚类中心点，G是聚类指示器矩阵.因此，求解以下优化问题可以得到聚类中心矩阵M和聚类指示器矩阵G，即式（1）可以写为：

M∈Rd×c是原始数据空间的聚类中心矩阵，G∈Rn×c是聚类指示器矩阵，G的每一列表示每个样本的聚类指示向量，如果第i个样本属于c类，则为Gic=1(i=1，…，n；c=1，…，c)，否则Gic=0.因此，可以定义G∈Ind，它表示具有上述约束的一组矩阵.

表1 本研究中使用的符号Table 1 Notations used in this paper

2.2 谱聚类目标函数给定具有m个数据点的数据集，X={x1，x2，…，xm}，根据其中任意两点间的相似度建立相似度矩阵W∈Rm×m，任意两点间的相似度如下：

σ为尺度参数.令D为度矩阵，将W的每行元素相加得到度矩阵D.L∈Rm×m为拉普拉斯矩阵，L=D-W.假定{x1，x2，…，xm} 可以分成两类，分别记为A和B，设：

比例割（Ratio cut）函数为：

其中，|A|为A类数据点数目，|B|为B类数据点数目.显然最小比例割对应着一个最佳的二分类问题.假定有m维向量f={f1，f2，…，fm}，它的每个元素代表当前数据点的类别归属，Ng et al［19］证明向量f满足下列等式：

其中，|V|表示数据样本点数量.对于k类问题，比例割优化模型为：

该模型即为谱聚类的目标函数，式（6）是一个求解迹最小化问题，根据拉普拉斯矩阵的性质，该优化问题可转为求L矩阵最小的k-1个特征值对应的特征向量.

2.3 乘法更新规则非负矩阵分解（Nonnega⁃tive Matrix Factorization，NMF）［20］是一种矩阵分解算法，主要用于分析元素非负的数据矩阵.它最初被提议用于部分整体分解［21］，后来扩展到数据聚类的通用框架，将非负数据矩阵分解为多个非负因子，包括后面的簇.理论上NMF已被证明等同于（核）k⁃means聚类［22-23］、概率潜在语义索引［24］和基于拉普拉斯算子的谱聚类［22］.

给定一个数据矩阵X=[x1，…，xN]∈RM×N，X的每一列都是一个样本向量.NMF的目标是找到两个非负矩阵U=[uik]∈RM×K和V=[vjk]∈RN×K，其乘积能很好地逼近原矩阵X：X≈UVT.

在上面的表示中，U可以认为是一组基向量，V是每个样本关于这些基向量的表示，则基于欧氏距离的目标函数表示为：

现在考虑这样一个问题：

问题1在约束条件下，求出X关于U和V的最小值.

乘法更新规则是解决问题1的速度以及容易实现的一个很好的方法.

定理1欧几里得距离‖‖X-UV在以下更新规则下不增加：

在迭代规则（8）下，欧几里得距离不变的充分必要条件是U和V是其稳定点.

Lee and Seung［12］已经给出了详细证明过程.根据定理1，用乘法更新规则解决问题1，则最小化目标函数式（7）的解如下：

3 k-means和谱聚类的联合聚类算法

3.1 KMSC框架KMSC的目标函数为：

数据矩阵X=[x1，…，xn]∈Rm×n，X的每一列是一个样本向量，C的列是簇的质心，c1，…，ck是k个中心点.Y是聚类指示器矩阵.1c∈Rc×1和1n∈Rn×1是元素都是1的列向量.Tr(·)计算矩阵的迹，L∈Rn×c是拉普拉斯矩阵.注意YTY∈Rc×c是一个对角矩阵.拉普拉斯矩阵定义为L=DZ，D是一个对角矩阵，Z=(Zij)i，j=1，…，n是一个带权邻接矩阵，Zij＞0表示xi和xj是相邻的，Zij=0表示它们不是由一条边连接起来的.λ为正则化参数，λ≥0控制新表示的平滑度.

3.2 乘法更新规则求解式（10）中KMSC的目标函数中C和Y中都不是凸的，因此，期望算法找到全局最小值是不现实的.下面介绍用乘法更新规则实现局部极小值的迭代算法.

为了最小化目标函数，式（10）可以重写为：

由于矩阵具有以下性质：Tr(AB)=Tr(BA)，Tr(A)=Tr(AT)，所以可以得到第二个等式.ψik和φjk分别约束cik≥0和yjk≥0的拉格朗日乘子，并且Ψ=[ψik]，Φ=[φjk]，拉格朗日L是：

L关于C和Y的偏导是：

使用KKT条件ψikcik=0和φjk yjk=0，得到关于cik和yjk的如下方程：

对于这两个更新规则，有定理2：

定理2目标函数式（10）在更新规则式（17）和式（18）下是不增加的.

定理2的详细证明过程见4.1，其证明基本遵循Lee and Seung［12］的思想.Lin［25］的研究表明Lee and Seung的乘法算法不能保证收敛到平稳点，并特别建议对其进行一些小修改，修改后算法可以收敛.式（17）和式（18）的更新规则与NMF的更新规则相似，因此，Lin的修改也可以应用.

对于NMF的目标函数，很容易检查U和V是否为解，那么UD，VD-1也将形成任何正对角矩阵D的解.为了消除这种不确定性，实际上需要进一步要求矩阵U（或V）中每个列向量的欧氏长度为1［26］，矩阵V（或U）进行相应的调整使UVT不变.这可以通过式（19）完成：

KMSC算法也采用了这种策略.在乘法更新过程收敛后，将矩阵C中每个列向量的欧氏长度设置为1，并调整矩阵Y使CYT不变.KMSC算法的整个过程概述见算法1.

算法1 KMSC算法

4 算法的理论分析

首先证明KMSC算法是正确的，并在式（17）和式（18）给出的更新规则下收敛；还给出了KM⁃SC的计算复杂度，证明了KMSC的有效性.

4.1 KMSC的正确性和收敛性证明为了证明KMSC的正确性，首先引入满足KKT互补条件的拉格朗日函数.通过将梯度设为零得到不动点方程，其解必须收敛于一个不动点.如果可以证明式（17）和式（18）的更新规则满足这些不动点方程以及KKT不动点条件，则证明KMSC的正确性.具体地，KMSC的正确性可以表述为：

定理3 KMSC的正确性给定式（10）的目标函数，约束解满足式（17）和式（18）更新规则下的KKT互补条件.

证 明为解决优化问题，引入拉格朗日函数：

其中，β1和β2是非负的拉格朗日乘子，分别是C和Y的非负性约束.式（20）满足KKT互补松弛条件.通过设置梯度为零，得到以下方程：

由互补条件可得：

式（23）和式（24）是不动点方程，最终的解必须收敛到一个不动点.由上述两个方程，又推出两个相等的方程：

随着Ct+1=Ct和Yt+1=Yt收敛（t是迭代次数），式（17）和式（18）中有更新规则的约束解满足式（25）和式（26）及KKT不动点条件，证明完成.

接下来证明迭代更新算法的收敛性.这里首先介绍引入辅助函数［12］来证明收敛性.

定义1G(y,y′)是F(y)的辅助函数，满足：

引理1如果G是一个辅助函数，那么F在更新时是不增加的：

证 明

证明式（18）中Y的更新步骤正好是式（28）中的更新，并且有一个合适的辅助函数.将式（10）中的KMSC的目标函数重写如下：

考虑到Y中的任意元素yab，用Fab表示L的部分，它只与yab相关.很容易检验：

由于更新本质上是按元素顺序进行的，因此有足够的证明表示在式（18）的更新步骤中，每个Fab都没有增加.

引理2

此函数是Fab的辅助函数L的一部分，只与yab相关.

下面介绍定理2的收敛性.

由于式（33）是一个辅助函数，所以Fab在这个更新规则下是不增加的.

最小化KMSC目标函数的更新规则本质上是迭代的，且已经证明这些规则是收敛的.下面研究并比较k⁃means和KMSC的收敛的速度.

k⁃means和KMSC在两个数据集上的收敛曲线如图1和图2所示.可以看出，k⁃means和KM⁃SC的乘法更新规则收敛非常快，通常在100次迭代内即可达成.

图1 k-means和KMSC在COIL20上的收敛曲线Fig.1 Convergence curves of k-means and KMSC on COIL20 database

图2 k-means和KMSC在TDT2上的收敛曲线Fig.2 Convergence curves of k-means and KMSC on TDT2 database

4.2 计算复杂性分析根据更新规则计算k⁃means中每一次迭代的运算量并不困难.对于KMSC，需要注意的是Z是一个稀疏矩阵.如果使用p最近邻图，Z的每一行上的非零元素的平均值是p，因此只需要NpK（一种浮点加法和乘法）来计算ZY.除了乘法更新，KMSC还需要O(N2M)构建p最近邻图，N为样本点数，M为特征数，K为簇的数目.假设乘法更新在t次迭代后停止，k⁃means的时间复杂度为O(tMNK)，则KMSC的时间复杂度为O(tMNK+N2M).

5 实 验

在真实数据集上进行实验，验证KMSC的有效性.采用六种经典的相关聚类方法作为比较方法.在多个基准数据集上的实验表明，k⁃means与谱聚类的联合聚类算法实现了良好的性能.

5.1 实验环境所有算法均用Matlab R2014a实现.在一台3.2 GHz Intel Core CPU 4.0 GB RAM和Windows 7操作系统的计算机上进行.

5.2 评价指标使用聚类精度（ACC）和归一化互信息（NMI）这两个常用的评价指标来评价所有聚类算法的性能.

ri表示xi的伪簇标签，li代表真正的类标签，n是数据样本的个数，map(·)是最佳映射函数.注意，在δ(x，y)函数中，如果x=y，则δ(x，y)=1；否则δ(x，y)=0.Map函数map(·)将每个集群标签投射到真正的标签.较大的ACC意味着更好的集群性能.

n是数据集样本数量，ni和nj分别表示实际类别i与聚类类别j中的样本数量，nij代表同时在实际类别i与聚类类别j中的样本数量.当NMI=1时，聚类与实际类别完全匹配；NMI=0时，表明样本完全随机散布，NMI越高表明聚类效果越好.

5.3 KMSC在实际中的应用将KMSC方法分别在COIL20图像数据集、TDT2文本数据集以及UCI数据集上进行实验，并与一些经典方法进行比较.为了使实验随机化，采用不同的样本数量进行评价.对于每个给定的样本个数P，在随机选择的不同样本上测试运行20次（整个数据集除外），并对结果取均值.

5.3.1 KMSC在图像聚类中的应用使用COIL20图像库，其中每个物体有72幅图像，另外还包含从不同角度观看的20个物体的32张灰度人脸图像.表2总结了COIL20数据集的重要统计信息，图3给出了COIL20数据集的图像样本.

表2 COIL20数据集的重要统计信息Table 2 Important statistics of COIL20 database

图3 来自COIL20数据库的图像样本Fig.3 Sample images from COIL20 database

将KMSC聚类算法与以下五种流行的聚类算法在选择样本数量P为4，6，8，10，12，14，16，18，20时生成的数据集进行比较.对每一种比较方法进行参数配置比的测试，得出最佳性能.

（1）k⁃means聚类：将给定的数据样本分配到簇中，使数据点只分配到一个簇中.

（2）谱聚类（Spectral Clustering，SC）：谱聚类算法建立在谱图理论基础上，它能在任意形状的样本空间上进行聚类.本次实验使用的是归一化的拉普拉斯矩阵.

（3）主成分分析法（Principal Component Analysis，PCA）和奇异值分解（Singular Value De⁃composition，SVD）：主成分子空间中的k⁃means聚类.PCA［27］是常用的无监督降维算法之一.在主成分子空间中，聚类效果更加明显.在数学上，PCA相当于对中心数据矩阵执行SVD.在TDT2数据集上，由于中心数据矩阵太大，无法存储，所以简单地使用SVD而不是PCA.实际上，SVD已经非常成功地用于文档表示（潜在语义索引［28］）.Zha et al［29］证明SVD子空间中的k⁃means聚类与平均关联［17］有密切的联系，平均关联是一种流行的谱聚类算法.结果表明，如果用内积度量相似性构造图，SVD后的k⁃means等价于平均关联.

（4）非负矩阵分解（Nonnegative Matrix Fac⁃torization，NMF）：使用F范数公式并实现了NMF的归一化割加权版本，Xu et al［26］已做出详细证明.

（5）k⁃means++：与k⁃means聚类的不同之处在于初始的聚类中心之间的相互距离要尽可能地远.

（6）KMSC：本文提出的算法.正则化参数λ设置为100.参数选择将在后面的章节中讨论.

通过比较每个样本获得的标签和数据集提供的标签来评估聚类性能.使用ACC和NMI两个指标来衡量聚类结果.

在COIL20数据集上使用不同方法的ACC和NMI如表3所示，表中黑体字为KMSC的实验结果，可见结果高于其他方法.

表3 COIL20数据集上的聚类结果：精度和标准互信息Table 3 Clustering performance on COIL20 database:ACC and NMI

5.3.2 KMSC在文本聚类中的应用使用

5.3.1 的比较方法和5.2的评价指标来验证KM⁃SC的有效性，选择样本数P为5，10，15，20，25，30时生成的数据集进行比较.

使用TDT2文本库，包括1998年上半年收集的数据，有六个来源，包括两家通讯社（APW，NYT）、两家电台（VOA，PRI）和两家电视台（CNN，ABC）.它由11201个主题文档组成，被分为96个语义类别.实验中出现在两个或两个以上类别中的文件被删除，只保留最大的30个类别，共有9394个文件.表4总结了TDT2数据集的重要统计信息，在TDT2数据集上使用不同方法的ACC和NMI如表5所示，表中黑体字为KMSC的实验结果，可见结果高于其他方法.

表4 TDT2数据集的重要统计信息Table 4 Important statistics of TDT2 database

5.3.3 KMSC在UCI数据集上的应用使用

5.3.1 的比较方法和5.2的评价指标来验证KM⁃SC的有效性.

UCI是加州大学欧文分校的一种适用于模式识别和机器学习的方向开源数据集，现有数据集已超过488个，主要有二元分类问题、分类和回归拟合问题，并提供每个数据集的主要特性.本实验选取鸢尾花数据集（Iris）和车辆数据集（Vehi⁃cle），这两个数据集的重要统计数据如表6所示.

在UCI两种数据集上使用不同方法的ACC和NMI如表7所示，表中黑体字为KMSC的实验结果，可见结果高于其他方法.

表5 TDT2数据集聚类结果：精度和标准互信息Table 5 Clustering performance on the TDT2 database：ACC and NMI

表6 UCI中的两种数据集统计Table 6 Statistics of the two datasets in UCI

5.4 聚类结果分析对来自COIL20，TDT2和

UCI的数据集进行测试，使用KMSC都能得到更好的结果（见表3、表5和表7）.原因可能是KM⁃SC是一种无监督学习方法，它不仅考虑数据的几何结构，还考虑样本的判别信息，所以和其他只考虑非负性、图嵌入或判别特征提取的方法相比，性能更优.KMSC聚类框架是两种经典聚类方法k⁃means聚类和谱聚类的结合，参数λ选择合适值时KMSC就继承了这两种方法的优点，因此无论是在COIL20图像数据集、TDT2文本数据集还是UCI数据集上，KMSC的性能都优于其他方法.

表7 UCI数据集聚类结果：精度和标准互信息Table 7 Clustering performance on the UCI datasets：ACC and NMI

5.4.1 KMSC与k-means的联系在KMSC中，当λ=0，目标函数式（10）可退化为：

这正是k⁃means的目标函数.因此，KMSC隐式地执行了一个k⁃means聚类.

5.4.2 KMSC与谱聚类的联系谱聚类是一种基于拉普拉斯图的聚类方法，它寻找图的一个划分，使不同组之间的权值非常低（这意味着不同簇中的点彼此不相似）.当λ→∞时，目标函数式（10）可近似为：

这正是谱聚类的目标函数.根据L是否归一化，Shi and Malik［17］和Ng et al［19］提出归一化谱聚类的两种不同版本.von Luxburg［30］还分别从图割理论和微扰理论的角度对这些方法进行详细讨论.

5.5 参数选择KMSC算法有一个正则化参数λ，图4说明了KMSC算法在COIL20数据集和TDT2数据集上的性能如何随参数λ变化.

可以看出，KMSC算法的性能相对于参数λ是非常稳定的.在COIL20数据集和TDT2数据集上，当λ在10到1000之间变化时，KMSC始终能获得良好的性能.另外，KMSC在构造p最近邻图时需要定义权矩阵Z，本次实验使用0⁃1加权矩阵.但由于Zij仅用于度量相似度，所以没有对不同的加权方案进行单独处理.

图4 COIL20 (a)和TDT2 (b)数据集上KMSC算法随参数λ 的性能变化Fig.4 Performance of KMSC algorithm on COIL20 (a)and TDT2 (b)databases with the change of parameter λ

6 结论和展望

本文提出基于乘法更新规则的k⁃means和谱聚类的联合聚类算法（KMSC），将k⁃means和谱聚类结合成一个统一的聚类模型，该模型在单次优化中同时优化k⁃means和谱聚类的目标.目标函数采用乘法更新规则求解，算法的收敛性明显，还在理论上证明了该算法的正确性和收敛性.KM⁃SC是一种无监督学习方法，它继承了k⁃means和谱聚类的优点.在图像、文本及UCI数据集上进行实验，并和现有的经典聚类方法进行比较，证明KMSC的性能优于其他方法，在聚类精度和标准互信息上较其他方法都有所提高，聚类效果更好.

在未来工作中，将进一步提高KMSC的鲁棒性和准确性.此外，还将扩展所提出的优化框架，以处理更复杂的数据，如有噪声、有错误或遗漏的数据，并研究其在半监督学习框架下的性能.