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

謝 挺,劉瑞華,魏正元

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

1 引言

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

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

(1)

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

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

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

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

(2)

(3)

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

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

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

(4)

XLD=(c1,c2,…,ck)

(5)

利用向量2-范數(shù)和矩陣F-范數(shù)間的關(guān)系,K-means模型基于歐氏距離時可等價表示為式(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)及聚類矩陣的非負、隨機和正交性，可設(shè)計模型(1)或模型(7)中K-means問題的等價連續(xù)形式，如式(8)所示：

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

(8)

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

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

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

(9)

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

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

2.2 等價模型的性質(zhì)與特點

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

定理1等價聚類模型中的矩陣變量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個特征值且都為1。又由矩陣MTM與MMT互為轉(zhuǎn)置，則2個矩陣有相同的非零特征值，從而MMT的特征值為：λ(MMT)∈{1,0}。

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

□

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

(10)

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

(11)

又由于聚類中心點的定義有：

|XCi-ci1ni|=

(12)

故等式成立。

□

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

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

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

(13)

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

(14)

□

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

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

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

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

按照常用的罰函數(shù)法，可以將模型(9)中的3個約束條件松弛到目標函數(shù)中。對于其中的稀疏約束，即求解困難的L0范數(shù)問題一般將其松弛為L1或L2范數(shù)。不失一般性，本文將稀疏約束松弛為L1，可得模型(9)的罰函數(shù)為：

(15)

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

(16)

(17)

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

(18)

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

s.t.M-Z=0

(19)

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

(20)

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

(21)

(22)

Λ←Λ+μ(M-Z)

(23)

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

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

(24)

(25)

則：

(26)

將f(M)在M=S點進行二次近似展開，則有：

(27)

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

(28)

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

(29)

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

(30)

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

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

(31)

(32)

(33)

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

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

(34)

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

算法1基于ADMM的連續(xù)等價優(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 算法的收斂性分析

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

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

M-Z=0

(35)

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

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

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

(36)

□

4 數(shù)值算例

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

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

(37)

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

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

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

5 結(jié)束語

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