一類連續(xù)的K-means 等價(jià)聚類模型及其優(yōu)化算法*

謝 挺,劉瑞華,魏正元

(1.重慶理工大學(xué)理學(xué)院，重慶 400054； 2.重慶理工大學(xué)人工智能學(xué)院，重慶 400054)

1 引言

隨著計(jì)算機(jī)和互聯(lián)網(wǎng)技術(shù)的迅猛發(fā)展和快速普及，特別是信息數(shù)字化、移動(dòng)終端和云計(jì)算等應(yīng)用領(lǐng)域的不斷擴(kuò)大，各行業(yè)所采集的數(shù)據(jù)量都呈爆炸式增長(zhǎng)，時(shí)時(shí)刻刻都產(chǎn)生著高維的海量數(shù)據(jù)，人們正進(jìn)入一個(gè)以“大數(shù)據(jù)”為代表的人工智能新時(shí)代。這意味著傳統(tǒng)的計(jì)算和分析極限不斷受到挑戰(zhàn)，這也意味著亟需探索新的數(shù)據(jù)處理技術(shù)和方法，這更意味著數(shù)據(jù)和信息科學(xué)發(fā)展的新機(jī)遇。聚類作為一種非監(jiān)督學(xué)習(xí)方法，是數(shù)據(jù)分析領(lǐng)域的重要研究?jī)?nèi)容之一。聚類分析是指利用相似性度量將數(shù)據(jù)劃分為不同的類以發(fā)現(xiàn)其中隱藏的結(jié)構(gòu)特征并提取有效信息的過(guò)程，其中同一類數(shù)據(jù)點(diǎn)具有最大相似性，不同類數(shù)據(jù)點(diǎn)具有最小相似性[1]。聚類分析被廣泛應(yīng)用于模式識(shí)別、機(jī)器學(xué)習(xí)、圖像處理和人工智能等領(lǐng)域。

K-means算法是一類基于劃分的聚類算法，以歐氏距離作為相似性度量，其主要思想是最小化類內(nèi)數(shù)據(jù)點(diǎn)到聚類中心的歐氏距離的平方和。從本質(zhì)上講，K-means 是一個(gè)組合優(yōu)化問(wèn)題，具有NP復(fù)雜度，主要適用于服從Gauss分布的數(shù)據(jù)集的聚類。因其簡(jiǎn)潔性和有效性，K-means仍是當(dāng)前廣泛使用的聚類算法，是十大經(jīng)典數(shù)據(jù)挖掘算法之一[2]。具體模型可以描述為：對(duì)于給定原始數(shù)據(jù)X={x1,x2,…,xn}∈Rm×n，其中n是樣本點(diǎn)數(shù)，m是樣本點(diǎn)維數(shù)，模型如式(1)所示：

(1)

為使K-means能夠應(yīng)用于大數(shù)據(jù)聚類分析，本文結(jié)合大數(shù)據(jù)問(wèn)題中普遍存在的稀疏性要求，從聚類問(wèn)題的本質(zhì)出發(fā)，設(shè)計(jì)了一種與K-means等價(jià)的連續(xù)的聚類模型；同時(shí)利用交替方向乘子算法ADMM(Alternating Direction Method of Multipliers)[8]框架構(gòu)造了其優(yōu)化算法，分析了算法的收斂性問(wèn)題并通過(guò)數(shù)值算例進(jìn)行了驗(yàn)證。

論文的組織結(jié)構(gòu)如下：第2節(jié)將從聚類矩陣出發(fā)，設(shè)計(jì)一種與K-means等價(jià)的連續(xù)聚類模型；第3節(jié)討論了該模型的性質(zhì)及其改進(jìn)；第4節(jié)給出了該連續(xù)模型的ADMM 算法框架及收斂性分析；第5節(jié)利用數(shù)值算例來(lái)驗(yàn)證模型的高效性和可行性；最后進(jìn)行了總結(jié)。

2 非凸連續(xù)的K-means等價(jià)聚類模型

聚類問(wèn)題由指派問(wèn)題演變發(fā)展而來(lái)。指派問(wèn)題是指：有n項(xiàng)任務(wù)要由n個(gè)人來(lái)承擔(dān)，每項(xiàng)任務(wù)只能由1人承擔(dān)且每個(gè)人只能承擔(dān)1項(xiàng)任務(wù)，dij表示第i個(gè)人承擔(dān)第j項(xiàng)任務(wù)的成本，Lij=1或0表示第i個(gè)人承擔(dān)或不承擔(dān)第j項(xiàng)任務(wù)，i,j∈{1,2,…,n}，具體描述為:

(2)

(3)

分析聚類矩陣L不難發(fā)現(xiàn)其具有以下屬性：(1)非負(fù)性，即Lij≥0；(2)稀疏性，即‖Lj‖0≤N,其中N為給定正整數(shù)；(3)正交性，即當(dāng)i≠j時(shí)，2列向量?jī)?nèi)積〈Li,Lj〉=0；(4)隨機(jī)性，即∑iLij=|Cj|=nj，∑jLij=1。

2.1 非凸連續(xù)的等價(jià)優(yōu)化模型

根據(jù)K-means聚類算法的模型(式(1))及Lloyd迭代算法，可得聚類中心點(diǎn)為(j=1,2,…,k)：

(4)

XLD=(c1,c2,…,ck)

(5)

利用向量2-范數(shù)和矩陣F-范數(shù)間的關(guān)系,K-means模型基于歐氏距離時(shí)可等價(jià)表示為式(6)：

(6)

其中，‖·‖F(xiàn)表示矩陣的F-范數(shù)，為矩陣各元素平方和的二次方根。又由于矩陣L和D之間的關(guān)系，可設(shè)M=LD1/2，則有LDLT=LD1/2D1/2LT=LD1/2(LD1/2)T=MMT，將其代入式(6)中有：

(7)

由矩陣M的定義、式(7)及聚類矩陣的非負(fù)、隨機(jī)和正交性，可設(shè)計(jì)模型(1)或模型(7)中K-means問(wèn)題的等價(jià)連續(xù)形式，如式(8)所示：

s.t.MMT1n=1n,MTM=Ik,M≥0

(8)

其中，M≥0表示M中所有元素不小于0。

由于稀疏是大數(shù)據(jù)聚類問(wèn)題的本質(zhì)屬性，為進(jìn)一步突出稀疏性以提高聚類效果，還可以構(gòu)造如式(9)所示的等價(jià)連續(xù)形式：

s.t.MMT1n=1n,MTM=Ik,‖M‖0≤N

(9)

其中，M∈Rn×k，1n表示含有n個(gè)1元素的n維列向量，Ik為k階單位矩陣，N為稀疏約束常數(shù)。

可以看出，模型(8)中的目標(biāo)函數(shù)F是關(guān)于矩陣變量M連續(xù)的四次函數(shù)，隨機(jī)約束和非負(fù)約束集為凸，而正交約束集非凸。在此需要特別指出的是，我們注意到有許多文獻(xiàn)討論了K-means算法模型的變換形式，包括其與矩陣分解[9,10]、SVD(Singular Value Decomposition) 分解[11]、非負(fù)矩陣分解[12,13]等之間的聯(lián)系，但這些討論都僅僅停留在通過(guò)數(shù)學(xué)推導(dǎo)在模型的數(shù)學(xué)表達(dá)式上給出一種解釋，其所得到的變換模型既求解困難也沒(méi)有良好的聚類性質(zhì)。例如，文獻(xiàn)[9]中所給出的K-means等價(jià)模型，不論是目標(biāo)函數(shù)還是約束條件都極其復(fù)雜，根本無(wú)法求解和應(yīng)用。

2.2 等價(jià)模型的性質(zhì)與特點(diǎn)

根據(jù)模型的目標(biāo)函數(shù)形式，K-means聚類問(wèn)題可以看成原始數(shù)據(jù)X的低秩逼近，也可以看成原始數(shù)據(jù)X的降維自表示。本節(jié)將利用3個(gè)定理描述模型(8) 和模型(9) 的良好聚類特性和等價(jià)性問(wèn)題。

定理1等價(jià)聚類模型中的矩陣變量M具有如下性質(zhì)：

(1)Rank(MMT)=k;

(2)λ(MMT)∈{1,0};

(3)‖MMT‖1=n。

證明(1)由于MTM=Ik，則Rank(MTM)=k。又由Rank(MTM)=Rank(MMT)，則有：Rank(MMT)=k。

(2)由于MTM=Ik，即矩陣MTM有k個(gè)特征值且都為1。又由矩陣MTM與MMT互為轉(zhuǎn)置，則2個(gè)矩陣有相同的非零特征值，從而MMT的特征值為：λ(MMT)∈{1,0}。

(3)根據(jù)模型約束條件MMT1n=1n，以及1-范數(shù)的性質(zhì)，有：‖MMT‖1=‖MMT1n‖1=‖1n‖1=n。

□

定理2若記類Ci中的數(shù)據(jù)點(diǎn)和聚類中心分別為XCi和ci，則對(duì)于任意數(shù)據(jù)點(diǎn)x∈X都有如下等式成立：

(10)

證明由F-范數(shù)性質(zhì)有：

(11)

又由于聚類中心點(diǎn)的定義有：

|XCi-ci1ni|=

(12)

故等式成立。

□

定理3若矩陣M∈Rn×k滿足模型(8)中的約束條件，當(dāng)且僅當(dāng)M為聚類矩陣。即非凸的連續(xù)優(yōu)化模型(8)與K-means模型等價(jià)。

證明充分性。由于M=LD1/2，可知M滿足MMT1n=1n,MTM=Ik,M≥0 此3個(gè)約束條件，即充分性成立。

必要性。當(dāng)M滿足MTM=Ik，表明M為列單位正交矩陣，即其任意不同2列內(nèi)積〈Mi,Mj〉=0。由M≤0，可得矩陣M的每一行至多只有1個(gè)非零元素。此外又由于MMT1n=1n，可得矩陣M的每一行至少有1個(gè)非零元素。綜合以上2方面可得，M的每一行有且僅有1個(gè)非零元素。為方便描述，設(shè)矩陣M不同列上的非零元素依次為α1,…,αn1,β1,…,βn2,…,γ1,…,γnk，即(相似)矩陣M如式(13)所示：

(13)

將M表達(dá)式代入MMT1n=1n，可得如下關(guān)于參數(shù)αi方程組：

(14)

□

從定理1和定理3可以看出，聚類矩陣的隨機(jī)性、非負(fù)性和正交性是其基本屬性。聚類的過(guò)程不僅是降維的過(guò)程，也是數(shù)據(jù)的線性表示過(guò)程。因此，從聚類矩陣出發(fā)而構(gòu)造的連續(xù)、非凸的K-means聚類算法的模型和原始K-means 聚類算法的模型是一致的，具有相同的聚類結(jié)構(gòu)和聚類效果。定理2表明在聚類矩陣上，三角不等式的等號(hào)成立，進(jìn)一步解釋了聚類矩陣的空間結(jié)構(gòu)。

3 非凸連續(xù)等價(jià)模型的優(yōu)化算法

當(dāng)前大數(shù)據(jù)聚類問(wèn)題是大數(shù)據(jù)分析的主要手段，其快速算法的研究是一個(gè)非常重要的課題[5,14,15]。前文已經(jīng)指出：與相關(guān)文獻(xiàn)中的等價(jià)模型不同的是，本文給出的等價(jià)模型不僅是離散問(wèn)題的連續(xù)化而且具有快速解法。在此，本節(jié)主要利用ADMM的迭代格式針對(duì)聚類等價(jià)模型討論其優(yōu)化算法。因?yàn)槟Ｐ?8)可以類似于模型(9)導(dǎo)出算法格式，下文僅就模型(9)的算法形式進(jìn)行推導(dǎo)。

3.1 基于ADMM的優(yōu)化算法

按照常用的罰函數(shù)法，可以將模型(9)中的3個(gè)約束條件松弛到目標(biāo)函數(shù)中。對(duì)于其中的稀疏約束，即求解困難的L0范數(shù)問(wèn)題一般將其松弛為L(zhǎng)1或L2范數(shù)。不失一般性，本文將稀疏約束松弛為L(zhǎng)1，可得模型(9)的罰函數(shù)為：

(15)

其中α,β,γ0為對(duì)應(yīng)的罰參數(shù)。若令:

(16)

(17)

其中,α1T為在矩陣X下方添加一行元素全為α的n維行向量，則式(15)可以轉(zhuǎn)化為：

(18)

將變量分裂，令Z=M，則式(18)可寫(xiě)為：

s.t.M-Z=0

(19)

其中有2個(gè)變量M和Z，可以利用ADMM算法[8]框架求解模型(19)。該問(wèn)題的增廣拉格朗日函數(shù)如式(20)所示：

(20)

其中,Λ為對(duì)偶變量。由式(20)可得ADMM的迭代格式如式(21)～式(23)所示：

(21)

(22)

Λ←Λ+μ(M-Z)

(23)

其中需要求解關(guān)于M和Z的2個(gè)子優(yōu)化問(wèn)題。

首先求解關(guān)于M的子問(wèn)題。若記：

(24)

(25)

則：

(26)

將f(M)在M=S點(diǎn)進(jìn)行二次近似展開(kāi)，則有：

(27)

其中,θ=λmax(YTY+ZZT)。利用鄰近點(diǎn)梯度法，M的子問(wèn)題可轉(zhuǎn)化為如式(28)所示形式：

(28)

利用快速迭代收縮閾值算法FISTA(Fast Iterative Shrinkage Threshold Algorithm)計(jì)算式(28)有：

(29)

其中，shrink{U,v}=sign(U)max(|U|-v,0)，|U|表示U中每個(gè)元素的絕對(duì)值。具體迭代形式可以展開(kāi)如式(30)所示：

(30)

其中，Mk和Sk分別是M和S的第k次迭代值。

接下來(lái)求解關(guān)于Z的子問(wèn)題。由式(21)～式(23)可以看出關(guān)于Z的子問(wèn)題:

(31)

(32)

(33)

由式(33)可得Z的解為:

Z=(MMT+(τ+μ)In)-1((1+μ)M+

(34)

綜上可得非凸連續(xù)等價(jià)優(yōu)化模型的快速優(yōu)化算法如算法1所示。

算法1基于ADMM的連續(xù)等價(jià)優(yōu)化模型的快速優(yōu)化算法

輸入：X∈Rm×n,k=0,α,β,θ,μ,τ,γ>0;t1=1,M1=0,Λ1=0,S1=0。

輸出：M,Z,Λ∈Rn×k。

步驟2While不收斂do

k←k+1;

Λk+1←Λk+μ(Mk+1-Zk+1);

Endwhile

步驟3輸出Mk+1,Zk+1和Λk+1。

3.2 算法的收斂性分析

另一方面，對(duì)于非凸的優(yōu)化問(wèn)題需要有針對(duì)性地設(shè)計(jì)不同算法，一般情況下難于找到其全局最優(yōu)解，大部分情況都是局部最優(yōu)解甚至是可行解。對(duì)于本文中給出的算法1也可以得到類似結(jié)論[5,7,8]。

證明如果Q=(W,Z,Λ)為模型(6)的KKT點(diǎn)，則其應(yīng)滿足式(35)：

M-Z=0

(35)

由于Qk→Q，即Wk→W,Zk→Z,Λk→Λ。由算法1，當(dāng)Λk→Λ時(shí)可得M-Z→0，即M-Z=0。 又由式(28)和式(33)中的一階條件，可得:

Z(ZT-Ik)+μ(M-Z)+Λ+?‖M‖1,

M(MTZ-Ik)+μ(Z-M)-Λ,

(36)

□

4 數(shù)值算例

為比較本文的連續(xù)等價(jià)模型的優(yōu)化算法和經(jīng)典的K-means算法在數(shù)據(jù)聚類上的表現(xiàn)，將在人造數(shù)據(jù)和Yale Face Database[16]上開(kāi)展數(shù)值實(shí)驗(yàn)。人造數(shù)據(jù)為：隨機(jī)選取m維空間中的k個(gè)點(diǎn)作為聚類中心點(diǎn)，分別以這些聚類中心點(diǎn)構(gòu)造方差均為σ的高斯點(diǎn)，并使得這些所有的點(diǎn)的總數(shù)為n，在算例中選取(m,k,n)=(325,10,3000)，方差依次選取σ=(2.7,2.8,3.0,3.2,3.3)。Yale Face Database包含11個(gè)不同個(gè)體的不同面部表情和神態(tài)圖像，每人15幅，共165種灰度圖；在人造數(shù)據(jù)算例實(shí)驗(yàn)中選取的聚類數(shù)依次為k=(6,8,10,12)。本節(jié)所得的結(jié)論都是在Intel Core i7-3770 CPU 3.40 GHz, 8 GB RAM，Matlab R2017b的環(huán)境下運(yùn)行得到。

本節(jié)主要是從運(yùn)行時(shí)間和聚類精度來(lái)比較2類算法。運(yùn)行時(shí)間以秒(s)為單位；聚類精度則選擇常用的聚類精度函數(shù)AC，通過(guò)比較聚類指標(biāo)集L和真實(shí)指標(biāo)集T之間的差距得到，其定義如式(37)所示：

(37)

其中，Ti∈T,Li∈L分別表示第i個(gè)元素的真實(shí)指標(biāo)和聚類指標(biāo)。當(dāng)x=y時(shí)，δ(x,y)=1；當(dāng)x≠y時(shí)，δ(x,y)=0。一般利用百分比表示AC函數(shù)，詳見(jiàn)參考文獻(xiàn)[4,5,15]。傳統(tǒng)的K-means算法利用Matlab工具箱中的嵌入函數(shù)，連續(xù)等價(jià)模型利用基于ADMM的迭代算法，其中參數(shù)的選取參照文獻(xiàn)[8]。因?yàn)镵-means對(duì)初始值極其敏感，為使得對(duì)比更加公平，取20次計(jì)算的平均時(shí)間和平均聚類精度進(jìn)行對(duì)比。此外，在每次計(jì)算時(shí)選取30個(gè)不同的初始值進(jìn)行運(yùn)算，并將最小目標(biāo)函數(shù)值作為該次的計(jì)算結(jié)果。詳細(xì)結(jié)果如表1和表2所示。通過(guò)表格對(duì)比可以看出，本文所提出的等價(jià)連續(xù)模型的優(yōu)化算法不論在聚類時(shí)間還是聚類效果上都明顯優(yōu)于經(jīng)典的K-means聚類算法。

Table 1 Results of numerical experiments on artificial data表1 人造數(shù)據(jù)上的數(shù)值實(shí)驗(yàn)結(jié)果

Table 2 Results of numerical experiments on Yale Face Database表2 Yale Face Database上的數(shù)值實(shí)驗(yàn)結(jié)果

5 結(jié)束語(yǔ)

本文將經(jīng)典K-means模型進(jìn)行矩陣化處理，并結(jié)合聚類的本質(zhì)屬性提出了一類非凸的連續(xù)優(yōu)化模型?；贏DMM算法給出了該模型的迭代算法，并從理論上討論了解的收斂性問(wèn)題。通過(guò)人造數(shù)據(jù)和人臉數(shù)據(jù)驗(yàn)證了該算法相比經(jīng)典的K-means算法在聚類時(shí)間和聚類效果上的極大提升。所提模型和算法克服了傳統(tǒng)K-means的計(jì)算瓶頸，為解決大數(shù)據(jù)聚類中的相關(guān)問(wèn)題提供了一個(gè)途徑。但是，本文給出的算法參數(shù)較多，針對(duì)不同的問(wèn)題需要調(diào)試參數(shù)，這需要進(jìn)一步進(jìn)行研究簡(jiǎn)化。