多視角核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