多视角核K-means聚类算法的收敛性证明

邱保志， 贺艳芳

(1.郑州大学 信息工程学院 河南 郑州 450001； 2.广东理工学院 信息工程系 广东 肇庆 526100)

多视角核K-means聚类算法的收敛性证明

邱保志1， 贺艳芳2

(1.郑州大学 信息工程学院 河南 郑州 450001； 2.广东理工学院 信息工程系 广东 肇庆 526100)

用Zangwill收敛性定理对多视角核K-means(MVKKM)的收敛性进行了分析.结果表明，当满足一定的条件时，MVKKM生成的迭代序列收敛或至少存在一个子序列收敛于算法目标函数的局部极小值或鞍点，并在Matlab环境下，通过实验验证了算法在不同视角和不同的权重指数下的收敛性.

多视角聚类；K-means； 核函数； 收敛性

0 引言

聚类是数据分析的基础，目前已经提出了许多聚类算法，这些算法可以分为单视角聚类算法和多视角聚类算法两类.如K-means、基于谱函数的聚类算法、基于密度的聚类算法等都是单视角聚类算法[1-2]，而在实际的生活中，数据的表示可以有多种形式，例如一个文本可以用多种语言表示，一张图片可以用文字、颜色和形状等来表示.依据数据多方面的特征对数据进行聚类的方法称为多视角聚类.和单视角聚类算法相比，多视角聚类具有聚类精度高的优势[3-6].

聚类算法的收敛性是基于迭代技术的聚类算法的基础.文献[7]利用反例理论证明了模糊聚类算法(FCM)的收敛性；文献[8]利用Zangwill定理证明了PCA(possibilistic clustering algorithms)算法的收敛性，指出该算法产生迭代序列收敛或至少存在一个子序列收敛于PCA聚类目标函数的局部极小值点或鞍点；文献[9]讨论了多目标演化算法的收敛性问题；文献[10-12]分别研究了均值漂移、极大熵聚类、谱聚类等聚类算法的收敛性.这些收敛性证明都是针对单视角聚类算法，而多视角聚类算法MVKKM[13]将多特征样本点的不同视角映射到对应的高维特征空间，在特征空间内通过算法核K-means完成聚类.多视角聚类算法还没有理论证明算法的收敛性.针对这一问题，借鉴现有的单视角聚类算法收敛性证明方法，考虑通过迭代法优化其目标函数，而Zangwill定理是证明迭代算法收敛性的一个有效工具，本文使用Zangwill收敛性定理证明了多视角MVKKM的收敛性.

1 多视角核K-means算法的收敛性

1.1 多视角核

其中：cr∈R，r=1,2,…,N，v=1,2,…，K(v)称为多视角正定核.

对任意多视角正定核都存在映射

其中H(v)表示多视角的特征空间.

1.2 多视角核K-means聚类算法

(1)

(2)

uik∈{0,1},1≤k≤C,1≤i≤N,

(3)

(4)

(5)

所有多视角数据集的硬k划分集合用Mk表示：

Mk={u∈RCNu满足式(3)～(5)}.

(6)

所有多视角权重集合用Mfc表示：

Mfc={zz∈Rv;z满足公式(2)},

(7)

(8)

(9)

多视角权重迭代：

(10)

多视角数据集的硬k划分迭代：

(11)

定义3 若T:Y→P(Z)，则称映射T是从集合Y到集合Z的点到集映射.其中P(Z)表示Z的幂集，即T把Y中的每个点映射为Z的一个子集.

定义4[14]设Y和p(z)分别是空间Rp和Rq中的非空闭集，T:Y→P(Z)为点到集的映射.如果{y(k)}⊂Y,y(k)→y,z(k)∈T(y(k)),z(k)→z，蕴含z∈T(y)，则称映射T在z(v)=(z1,z2,…,zv)处是闭的.

定理1 (Zangwill收敛性定理)[15-16]设V是距离空间，点z(1)∈V,T:V→P(V)是V上点到集合的映射，由T定义的算法以z(1)为初始点产生的序列{z(k)}k=1,2,…，令Ω⊂V表示解集，如果：

1) 所有的点z(k)都属于V中的一个紧子集.

2) 存在连续函数J:V→R，使得：

① 若z∉Ω，对任何y∈T(z)，有J(y)

② 若z∈Ω，则或算法终止，或对任何y∈T(z)，有J(y)≤J(z).

3) 若z∉Ω，则映射T在z点是闭的.

满足上述条件则算法停止于某个解上，或任何一个收敛子序列的极限是一个解.

定义函数G1:Mfc×Mk→Hcv：

(12)

G2(w(v),u)=z(v)=(z1,z2,…,zv)T，

(13)

向量z(v)=(z1,z2,…,zv)，1≤v≤V，由式(10)定义.定义点到集的映射G3:Mfc×Hcv→P(Mk)，

(14)

式中 1≤v≤V.

MVKKM算法的迭代序列可以用点到集的映射T:Mfc×Hcv×Mk→P(Mfc×Hcv×Mk)表示，其定义的映射为T=A3∘A2∘A1，其中：

A1:Mfc×Hcv×Mk→Hcv×Mk,A1(z(v),w(v),u)=(G1(z(v),u),u)，

(15)

A2:Hcv×Mk→Mfc×Hcv,A2(w(v),u)=(G2(w(v),u),w(v))，

(16)

(17)

证明 充分性：如果u∈Mk满足式(11)，对于1≤v≤V时，JH是最小的.

引理2 令Θ:Mfc→R定义为

证明 当p>1时，函数Θ(zv)是严格的凸函数，上述问题是一个凸优化问题.引入Lagrange乘子，

当Qv>0时，式(1)的最优解等价于式(18)、(19)的解：

∂L/∂z(v)=0,1≤v≤V，

(18)

∂L/∂λ=0.

(19)

式(18)、(19)等价变换化简可得式(10),又由式(10)易见，它也是加强约束条件优化问题：minΘ(z(v))，z(v)∈Mfc的唯一全局最优解.

引理3 令Ψ:Hcv→R由

证明 因为Ψ(w(v))是关于w(v)的严格凸函数，它取全局唯一极小值的充要条件是满足式(9),即得证.

定理2 设

权重系数p>1， 若χ至少包含C(C

(20)

(21)

(22)

(23)

(24)

(25)

(26)

式(26)和假设相矛盾.

引理5 给定多视角数据集

设χ至少包含C(C1，则由式(16)定义的映射A2(w(v),u)=(G2(w(v),u),w(v))在Hcv×Mk是连续的.

证明 由A2定义知，A2(w(v),u)=(G2(w(v),u),w(v)),G2是根据式(10)计算得到，

(27)

推论1[16]C:M→V是一个函数,T:V→P(V)是点到集的映射.如果C在w0点是连续的且T在C(w0)是闭的,那么点到集的映射T∘C:M→P(V)在w0处是闭的.

引理6 设χ至少包含C(C1，则定义在式(17)的映射A3:Mfc×Hcv→P(Mfc×Hcv×Mk)在Mfc×Hcv×Mk是闭的.

证明 因为

要证明G3是一个点到集的闭映射,设

(28)

(29)

(30)

定理3 设χ至少包含C(C1，则映射T:Mfc×Hcv×Mk→P(Mfc×Hcv×Mk)在Mfc×Hcv×Mk是闭的.

证明 由引理4～6和推论1得到定理3的结论.

Mk，k=1,2，…，Mfc×[conv(χ)]C×Mk,包含于Mfc×Hcv×Mk的紧子集中.

从式(2)和(7)得到Mfc是闭的,并且是有界限的，由于[conv(χ)]是有限的凸包，所以它是闭的，因此[conv(χ)]C也是闭的和有界限的.因为Mk集合是χ集合的k划分，所以Mk是闭的、有限的，因而它们都是紧的，因此Mfc×[conv(χ)]C×Mk是Mfc×Hcv×Mk的紧子集.

2 收敛速率

下面通过实验分析MVKKM算法的收敛速率.实验环境：CPU为Intel(R)Core(TM)i3-2130，3.40 GHz，内存为4 G，操作系统为32位Win7旗舰版操作系统.算法编写环境：Matlab R2010a.

MVKKM算法的收敛速率取决于很多的因素：聚类的初始值；多视角的数目v；聚类的数目C；权重的指数p的值.本文采用了两个真实的UCI数据集进行实验，其中A1和A2代表数据集A(多特征数据集)中的不同的数据，B1和B2代表数据集B(Corel数据集)中的不同数据，实验中根据不同的p值，测试实验在不同视角下的运行收敛速率，其中A为5个视角，B为7个视角.图1是数据集A和B在不同p值下的运行速率，图2是数据集A和B在不同p值下的迭代次数.

图1 收敛速率Fig.1 Rate of convergence

图2 迭代次数Fig.2 Iteration number

实验的结果受数据集、参数v和p值的影响，在数据集A或者B中，相同的视角v,不同的p,运行速度不相同.在A1和A2中，相同的v,运行速度不一样，迭代次数不相同.从实验中可以看到B数据集的运行速度比A数据集的快，因为B中数据的数量比A数据的小，其中B的数据量为2 800个数据，而A为4 000个数据.B数据集的迭代次数比A多，是因为B的数据结构更复杂,视角数更大,实验说明算法的收敛速率受不同因素的影响.

3 结束语

本文利用Zangwill收敛定理证明了多视角聚类算法MVKKM的收敛性.当权重系数p>1时，且数据集χ中至少包含C(C

[1] 李欣雨,袁方,刘宇,等.面向中文新闻话题检测的多向量文本聚类方法[J].郑州大学学报(理学版),2016,48(2):47-52.

[2] 陶佰睿, 李青龙, 苗凤娟,等. 码本聚类矢量量化算法在说话人识别中的应用[J]. 河南科技大学学报(自然科学版),2016，37(1):35-39.

[3] ZHAO X, EVANS N, DUGELAY J. A subspace co-training framework for multi-view clustering[J]. Pattern recognition letters, 2014, 41(1):73-82.

[4] HUSSAIN S F, MUSHTAQ M, HALIM Z. Multi-view document clustering via ensemble method[J]. Journal of intelligent information systems, 2014, 43(1):81-99.

[5] EATON E, DESJARDINS M, JACOB S. Multi-view constrained clustering with an incomplete mapping between views[J]. Knowledge & information systems, 2014, 38(1):231-257.

[6] YIN Q, WU S, HE R, et al. Multi-view clustering via pairwise sparse subspace representation[J]. Neurocomputing, 2015,156(25):12-21.

[7] BEZDEK J C, HATHAWAY R J, SABIN M J, et al. Convergence theory for fuzzyc-means: count erexamples and repairs[J]. IEEE transactions on systems and cybernetics, 1987, 17(5): 873-877.

[8] ZHOU J, CAO L, YANG N. On the convergence of some possibilistic clustering algorithms[J]. Fuzzy optimization & decision making, 2013, 12(4):415-432.

[9] 周育人, 闵华清, 许孝元，等. 多目标演化算法的收敛性研究[J]. 计算机学报, 2004, 27(10):1415-1421.

[10]李乡儒, 吴福朝, 胡占义. 均值漂移算法的收敛性 [J]. 软件学报, 2005, 16(3)：365-374.

[11]任世军, 王亚东. 极大熵聚类算法的收敛性定理证明[J]. 中国科学: 信息科学, 2010,40(4)：583-590.

[12]高炜, 周定轩. 与一般相似度函数相关的谱聚类的收敛性[J]. 中国科学: 数学, 2012, 42(10): 985-994.

[13]TZORTZIS G, LIKAS A. Kernel-based weighted multi-view clustering[C]//Proceedings of the IEEE 12th International Conference on Data Mining.Washington,2012: 675-684.

[14]陈宝林.最优化理论与算法[M].北京：清华大学出版社，1989：411-432.

[15]ZANGWILL W I, MOND B. Nonlinear programming: a unified approach[M].New Jersey:Prentice-Hall Englewood Cliffs, 1969.

[16]HATHAWAY R, BEZDEK J, TUCKER W. An improved convergence theory for the fuzzy isodata clustering algorithms[J]. Analysis of fuzzy information, 1987, 3: 123-132.

[17]张志华, 郑南宁, 史罡. 极大熵聚类算法及其全局收敛性分析[J].中国科学:技术科学， 2001,31(1):59-70.

(责任编辑：王浩毅)

A Convergence Proof of Multi-view KernelK-means
Clustering Algorithm

QIU Baozhi1， HE Yanfang2

(1.SchoolofInformationEngineering，ZhengzhouUniversity，Zhengzhou450001,China; 2.DepartmentofInformationEngineering,GuangdongPolytechnicCollege,Zhaoqing526100,China)

The Zangwill convergence theorem was utilized to analyze the convergence of the multi-view kernelK-means (MVKKM). The study results showed that, under certain conditions, the iterative sequence generated by MVKKM converges, or there existed at least one subsequence converged to a local minimum or a saddle point of the objective function of the algorithm. And in Matlab, the convergence of the algorithm under different views and different index weight was verified.

multi-view clustering;K-means; kernel functions; convergence

2017-03-08

河南省基础与前沿技术研究项目(152300410191).

邱保志(1964—)，男，河南驻马店人，教授，主要从事数据挖掘、人工智能研究，E-mail: qbzzzu@163.com；通信作者：贺艳芳(1988—)，女，河南漯河人，主要从事数据挖掘研究，E-mail:hhyyfflst@163.com.

TP301.6

A

1671-6841(2017)03-0032-07

10.13705/j.issn.1671-6841.2017020