多視角核K-means聚類算法的收斂性證明

邱保志， 賀艷芳

(1.鄭州大學(xué) 信息工程學(xué)院 河南 鄭州 450001； 2.廣東理工學(xué)院 信息工程系 廣東 肇慶 526100)

多視角核K-means聚類算法的收斂性證明

邱保志1， 賀艷芳2

(1.鄭州大學(xué) 信息工程學(xué)院 河南 鄭州 450001； 2.廣東理工學(xué)院 信息工程系 廣東 肇慶 526100)

用Zangwill收斂性定理對多視角核K-means(MVKKM)的收斂性進行了分析.結(jié)果表明，當滿足一定的條件時，MVKKM生成的迭代序列收斂或至少存在一個子序列收斂于算法目標函數(shù)的局部極小值或鞍點，并在Matlab環(huán)境下，通過實驗驗證了算法在不同視角和不同的權(quán)重指數(shù)下的收斂性.

多視角聚類；K-means； 核函數(shù)； 收斂性

0 引言

聚類是數(shù)據(jù)分析的基礎(chǔ)，目前已經(jīng)提出了許多聚類算法，這些算法可以分為單視角聚類算法和多視角聚類算法兩類.如K-means、基于譜函數(shù)的聚類算法、基于密度的聚類算法等都是單視角聚類算法[1-2]，而在實際的生活中，數(shù)據(jù)的表示可以有多種形式，例如一個文本可以用多種語言表示，一張圖片可以用文字、顏色和形狀等來表示.依據(jù)數(shù)據(jù)多方面的特征對數(shù)據(jù)進行聚類的方法稱為多視角聚類.和單視角聚類算法相比，多視角聚類具有聚類精度高的優(yōu)勢[3-6].

聚類算法的收斂性是基于迭代技術(shù)的聚類算法的基礎(chǔ).文獻[7]利用反例理論證明了模糊聚類算法(FCM)的收斂性；文獻[8]利用Zangwill定理證明了PCA(possibilistic clustering algorithms)算法的收斂性，指出該算法產(chǎn)生迭代序列收斂或至少存在一個子序列收斂于PCA聚類目標函數(shù)的局部極小值點或鞍點；文獻[9]討論了多目標演化算法的收斂性問題；文獻[10-12]分別研究了均值漂移、極大熵聚類、譜聚類等聚類算法的收斂性.這些收斂性證明都是針對單視角聚類算法，而多視角聚類算法MVKKM[13]將多特征樣本點的不同視角映射到對應(yīng)的高維特征空間，在特征空間內(nèi)通過算法核K-means完成聚類.多視角聚類算法還沒有理論證明算法的收斂性.針對這一問題，借鑒現(xiàn)有的單視角聚類算法收斂性證明方法，考慮通過迭代法優(yōu)化其目標函數(shù)，而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)

所有多視角數(shù)據(jù)集的硬k劃分集合用Mk表示：

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

(6)

所有多視角權(quán)重集合用Mfc表示：

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

(7)

(8)

(9)

多視角權(quán)重迭代：

(10)

多視角數(shù)據(jù)集的硬k劃分迭代：

(11)

定義3 若T:Y→P(Z)，則稱映射T是從集合Y到集合Z的點到集映射.其中P(Z)表示Z的冪集，即T把Y中的每個點映射為Z的一個子集.

定義4[14]設(shè)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]設(shè)V是距離空間，點z(1)∈V,T:V→P(V)是V上點到集合的映射，由T定義的算法以z(1)為初始點產(chǎn)生的序列{z(k)}k=1,2,…，令Ω?V表示解集，如果：

1) 所有的點z(k)都屬于V中的一個緊子集.

2) 存在連續(xù)函數(shù)J:V→R，使得：

① 若z?Ω，對任何y∈T(z)，有J(y)

② 若z∈Ω，則或算法終止，或?qū)θ魏蝭∈T(z)，有J(y)≤J(z).

3) 若z?Ω，則映射T在z點是閉的.

滿足上述條件則算法停止于某個解上，或任何一個收斂子序列的極限是一個解.

定義函數(shù)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時，函數(shù)Θ(zv)是嚴格的凸函數(shù)，上述問題是一個凸優(yōu)化問題.引入Lagrange乘子，

當Qv>0時，式(1)的最優(yōu)解等價于式(18)、(19)的解：

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

(18)

?L/?λ=0.

(19)

式(18)、(19)等價變換化簡可得式(10),又由式(10)易見，它也是加強約束條件優(yōu)化問題：minΘ(z(v))，z(v)∈Mfc的唯一全局最優(yōu)解.

引理3 令Ψ:Hcv→R由

證明 因為Ψ(w(v))是關(guān)于w(v)的嚴格凸函數(shù)，它取全局唯一極小值的充要條件是滿足式(9),即得證.

定理2 設(shè)

權(quán)重系數(shù)p>1， 若χ至少包含C(C

(20)

(21)

(22)

(23)

(24)

(25)

(26)

式(26)和假設(shè)相矛盾.

引理5 給定多視角數(shù)據(jù)集

設(shè)χ至少包含C(C1，則由式(16)定義的映射A2(w(v),u)=(G2(w(v),u),w(v))在Hcv×Mk是連續(xù)的.

證明 由A2定義知，A2(w(v),u)=(G2(w(v),u),w(v)),G2是根據(jù)式(10)計算得到，

(27)

推論1[16]C:M→V是一個函數(shù),T:V→P(V)是點到集的映射.如果C在w0點是連續(xù)的且T在C(w0)是閉的,那么點到集的映射T°C:M→P(V)在w0處是閉的.

引理6 設(shè)χ至少包含C(C1，則定義在式(17)的映射A3:Mfc×Hcv→P(Mfc×Hcv×Mk)在Mfc×Hcv×Mk是閉的.

證明 因為

要證明G3是一個點到集的閉映射,設(shè)

(28)

(29)

(30)

定理3 設(shè)χ至少包含C(C1，則映射T:Mfc×Hcv×Mk→P(Mfc×Hcv×Mk)在Mfc×Hcv×Mk是閉的.

證明 由引理4～6和推論1得到定理3的結(jié)論.

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算法的收斂速率.實驗環(huán)境：CPU為Intel(R)Core(TM)i3-2130，3.40 GHz，內(nèi)存為4 G，操作系統(tǒng)為32位Win7旗艦版操作系統(tǒng).算法編寫環(huán)境：Matlab R2010a.

MVKKM算法的收斂速率取決于很多的因素：聚類的初始值；多視角的數(shù)目v；聚類的數(shù)目C；權(quán)重的指數(shù)p的值.本文采用了兩個真實的UCI數(shù)據(jù)集進行實驗，其中A1和A2代表數(shù)據(jù)集A(多特征數(shù)據(jù)集)中的不同的數(shù)據(jù)，B1和B2代表數(shù)據(jù)集B(Corel數(shù)據(jù)集)中的不同數(shù)據(jù)，實驗中根據(jù)不同的p值，測試實驗在不同視角下的運行收斂速率，其中A為5個視角，B為7個視角.圖1是數(shù)據(jù)集A和B在不同p值下的運行速率，圖2是數(shù)據(jù)集A和B在不同p值下的迭代次數(shù).

圖1 收斂速率Fig.1 Rate of convergence

圖2 迭代次數(shù)Fig.2 Iteration number

實驗的結(jié)果受數(shù)據(jù)集、參數(shù)v和p值的影響，在數(shù)據(jù)集A或者B中，相同的視角v,不同的p,運行速度不相同.在A1和A2中，相同的v,運行速度不一樣，迭代次數(shù)不相同.從實驗中可以看到B數(shù)據(jù)集的運行速度比A數(shù)據(jù)集的快，因為B中數(shù)據(jù)的數(shù)量比A數(shù)據(jù)的小，其中B的數(shù)據(jù)量為2 800個數(shù)據(jù)，而A為4 000個數(shù)據(jù).B數(shù)據(jù)集的迭代次數(shù)比A多，是因為B的數(shù)據(jù)結(jié)構(gòu)更復(fù)雜,視角數(shù)更大,實驗說明算法的收斂速率受不同因素的影響.

3 結(jié)束語

本文利用Zangwill收斂定理證明了多視角聚類算法MVKKM的收斂性.當權(quán)重系數(shù)p>1時，且數(shù)據(jù)集χ中至少包含C(C

[1] 李欣雨,袁方,劉宇,等.面向中文新聞話題檢測的多向量文本聚類方法[J].鄭州大學(xué)學(xué)報(理學(xué)版),2016,48(2):47-52.

[2] 陶佰睿, 李青龍, 苗鳳娟,等. 碼本聚類矢量量化算法在說話人識別中的應(yīng)用[J]. 河南科技大學(xué)學(xué)報(自然科學(xué)版),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]. 計算機學(xué)報, 2004, 27(10):1415-1421.

[10]李鄉(xiāng)儒, 吳福朝, 胡占義. 均值漂移算法的收斂性 [J]. 軟件學(xué)報, 2005, 16(3)：365-374.

[11]任世軍, 王亞東. 極大熵聚類算法的收斂性定理證明[J]. 中國科學(xué): 信息科學(xué), 2010,40(4)：583-590.

[12]高煒, 周定軒. 與一般相似度函數(shù)相關(guān)的譜聚類的收斂性[J]. 中國科學(xué): 數(shù)學(xué), 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]陳寶林.最優(yōu)化理論與算法[M].北京：清華大學(xué)出版社，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].中國科學(xué):技術(shù)科學(xué)， 2001,31(1):59-70.

(責(zé)任編輯：王浩毅)

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

河南省基礎(chǔ)與前沿技術(shù)研究項目(152300410191).

邱保志(1964—)，男，河南駐馬店人，教授，主要從事數(shù)據(jù)挖掘、人工智能研究，E-mail: qbzzzu@163.com；通信作者：賀艷芳(1988—)，女，河南漯河人，主要從事數(shù)據(jù)挖掘研究，E-mail:hhyyfflst@163.com.

TP301.6

A

1671-6841(2017)03-0032-07

10.13705/j.issn.1671-6841.2017020