謝 挺,劉瑞華,魏正元
(1.重慶理工大學理學院,重慶 400054; 2.重慶理工大學人工智能學院,重慶 400054)
隨著計算機和互聯(lián)網技術的迅猛發(fā)展和快速普及,特別是信息數(shù)字化、移動終端和云計算等應用領域的不斷擴大,各行業(yè)所采集的數(shù)據(jù)量都呈爆炸式增長,時時刻刻都產生著高維的海量數(shù)據(jù),人們正進入一個以“大數(shù)據(jù)”為代表的人工智能新時代。這意味著傳統(tǒng)的計算和分析極限不斷受到挑戰(zhàn),這也意味著亟需探索新的數(shù)據(jù)處理技術和方法,這更意味著數(shù)據(jù)和信息科學發(fā)展的新機遇。聚類作為一種非監(jiān)督學習方法,是數(shù)據(jù)分析領域的重要研究內容之一。聚類分析是指利用相似性度量將數(shù)據(jù)劃分為不同的類以發(fā)現(xiàn)其中隱藏的結構特征并提取有效信息的過程,其中同一類數(shù)據(jù)點具有最大相似性,不同類數(shù)據(jù)點具有最小相似性[1]。聚類分析被廣泛應用于模式識別、機器學習、圖像處理和人工智能等領域。
K-means算法是一類基于劃分的聚類算法,以歐氏距離作為相似性度量,其主要思想是最小化類內數(shù)據(jù)點到聚類中心的歐氏距離的平方和。從本質上講,K-means 是一個組合優(yōu)化問題,具有NP復雜度,主要適用于服從Gauss分布的數(shù)據(jù)集的聚類。因其簡潔性和有效性,K-means仍是當前廣泛使用的聚類算法,是十大經典數(shù)據(jù)挖掘算法之一[2]。具體模型可以描述為:對于給定原始數(shù)據(jù)X={x1,x2,…,xn}∈Rm×n,其中n是樣本點數(shù),m是樣本點維數(shù),模型如式(1)所示:
(1)
為使K-means能夠應用于大數(shù)據(jù)聚類分析,本文結合大數(shù)據(jù)問題中普遍存在的稀疏性要求,從聚類問題的本質出發(fā),設計了一種與K-means等價的連續(xù)的聚類模型;同時利用交替方向乘子算法ADMM(Alternating Direction Method of Multipliers)[8]框架構造了其優(yōu)化算法,分析了算法的收斂性問題并通過數(shù)值算例進行了驗證。
論文的組織結構如下:第2節(jié)將從聚類矩陣出發(fā),設計一種與K-means等價的連續(xù)聚類模型;第3節(jié)討論了該模型的性質及其改進;第4節(jié)給出了該連續(xù)模型的ADMM 算法框架及收斂性分析;第5節(jié)利用數(shù)值算例來驗證模型的高效性和可行性;最后進行了總結。
聚類問題由指派問題演變發(fā)展而來。指派問題是指:有n項任務要由n個人來承擔,每項任務只能由1人承擔且每個人只能承擔1項任務,dij表示第i個人承擔第j項任務的成本,Lij=1或0表示第i個人承擔或不承擔第j項任務,i,j∈{1,2,…,n},具體描述為:
(2)
(3)
分析聚類矩陣L不難發(fā)現(xiàn)其具有以下屬性:(1)非負性,即Lij≥0;(2)稀疏性,即‖Lj‖0≤N,其中N為給定正整數(shù);(3)正交性,即當i≠j時,2列向量內積〈Li,Lj〉=0;(4)隨機性,即∑iLij=|Cj|=nj,∑jLij=1。
根據(jù)K-means聚類算法的模型(式(1))及Lloyd迭代算法,可得聚類中心點為(j=1,2,…,k):
(4)
XLD=(c1,c2,…,ck)
(5)
利用向量2-范數(shù)和矩陣F-范數(shù)間的關系,K-means模型基于歐氏距離時可等價表示為式(6):
(6)
其中,‖·‖F(xiàn)表示矩陣的F-范數(shù),為矩陣各元素平方和的二次方根。又由于矩陣L和D之間的關系,可設M=LD1/2,則有LDLT=LD1/2D1/2LT=LD1/2(LD1/2)T=MMT,將其代入式(6)中有:
(7)
由矩陣M的定義、式(7)及聚類矩陣的非負、隨機和正交性,可設計模型(1)或模型(7)中K-means問題的等價連續(xù)形式,如式(8)所示:
s.t.MMT1n=1n,MTM=Ik,M≥0
(8)
其中,M≥0表示M中所有元素不小于0。
由于稀疏是大數(shù)據(jù)聚類問題的本質屬性,為進一步突出稀疏性以提高聚類效果,還可以構造如式(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是關于矩陣變量M連續(xù)的四次函數(shù),隨機約束和非負約束集為凸,而正交約束集非凸。在此需要特別指出的是,我們注意到有許多文獻討論了K-means算法模型的變換形式,包括其與矩陣分解[9,10]、SVD(Singular Value Decomposition) 分解[11]、非負矩陣分解[12,13]等之間的聯(lián)系,但這些討論都僅僅停留在通過數(shù)學推導在模型的數(shù)學表達式上給出一種解釋,其所得到的變換模型既求解困難也沒有良好的聚類性質。例如,文獻[9]中所給出的K-means等價模型,不論是目標函數(shù)還是約束條件都極其復雜,根本無法求解和應用。
根據(jù)模型的目標函數(shù)形式,K-means聚類問題可以看成原始數(shù)據(jù)X的低秩逼近,也可以看成原始數(shù)據(jù)X的降維自表示。本節(jié)將利用3個定理描述模型(8) 和模型(9) 的良好聚類特性和等價性問題。
定理1等價聚類模型中的矩陣變量M具有如下性質:
(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互為轉置,則2個矩陣有相同的非零特征值,從而MMT的特征值為:λ(MMT)∈{1,0}。
(3)根據(jù)模型約束條件MMT1n=1n,以及1-范數(shù)的性質,有:‖MMT‖1=‖MMT1n‖1=‖1n‖1=n。
□
定理2若記類Ci中的數(shù)據(jù)點和聚類中心分別為XCi和ci,則對于任意數(shù)據(jù)點x∈X都有如下等式成立:
(10)
證明由F-范數(shù)性質有:
(11)
又由于聚類中心點的定義有:
|XCi-ci1ni|=
(12)
故等式成立。
□
定理3若矩陣M∈Rn×k滿足模型(8)中的約束條件,當且僅當M為聚類矩陣。即非凸的連續(xù)優(yōu)化模型(8)與K-means模型等價。
證明充分性。由于M=LD1/2,可知M滿足MMT1n=1n,MTM=Ik,M≥0 此3個約束條件,即充分性成立。
必要性。當M滿足MTM=Ik,表明M為列單位正交矩陣,即其任意不同2列內積〈Mi,Mj〉=0。由M≤0,可得矩陣M的每一行至多只有1個非零元素。此外又由于MMT1n=1n,可得矩陣M的每一行至少有1個非零元素。綜合以上2方面可得,M的每一行有且僅有1個非零元素。為方便描述,設矩陣M不同列上的非零元素依次為α1,…,αn1,β1,…,βn2,…,γ1,…,γnk,即(相似)矩陣M如式(13)所示:
(13)
將M表達式代入MMT1n=1n,可得如下關于參數(shù)αi方程組:
(14)
□
從定理1和定理3可以看出,聚類矩陣的隨機性、非負性和正交性是其基本屬性。聚類的過程不僅是降維的過程,也是數(shù)據(jù)的線性表示過程。因此,從聚類矩陣出發(fā)而構造的連續(xù)、非凸的K-means聚類算法的模型和原始K-means 聚類算法的模型是一致的,具有相同的聚類結構和聚類效果。定理2表明在聚類矩陣上,三角不等式的等號成立,進一步解釋了聚類矩陣的空間結構。
當前大數(shù)據(jù)聚類問題是大數(shù)據(jù)分析的主要手段,其快速算法的研究是一個非常重要的課題[5,14,15]。前文已經指出:與相關文獻中的等價模型不同的是,本文給出的等價模型不僅是離散問題的連續(xù)化而且具有快速解法。在此,本節(jié)主要利用ADMM的迭代格式針對聚類等價模型討論其優(yōu)化算法。因為模型(8)可以類似于模型(9)導出算法格式,下文僅就模型(9)的算法形式進行推導。
按照常用的罰函數(shù)法,可以將模型(9)中的3個約束條件松弛到目標函數(shù)中。對于其中的稀疏約束,即求解困難的L0范數(shù)問題一般將其松弛為L1或L2范數(shù)。不失一般性,本文將稀疏約束松弛為L1,可得模型(9)的罰函數(shù)為:
(15)
其中α,β,γ0為對應的罰參數(shù)。若令:
(16)
(17)
其中,α1T為在矩陣X下方添加一行元素全為α的n維行向量,則式(15)可以轉化為:
(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)
其中需要求解關于M和Z的2個子優(yōu)化問題。
首先求解關于M的子問題。若記:
(24)
(25)
則:
(26)
將f(M)在M=S點進行二次近似展開,則有:
(27)
其中,θ=λmax(YTY+ZZT)。利用鄰近點梯度法,M的子問題可轉化為如式(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次迭代值。
接下來求解關于Z的子問題。由式(21)~式(23)可以看出關于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。
另一方面,對于非凸的優(yōu)化問題需要有針對性地設計不同算法,一般情況下難于找到其全局最優(yōu)解,大部分情況都是局部最優(yōu)解甚至是可行解。對于本文中給出的算法1也可以得到類似結論[5,7,8]。
證明如果Q=(W,Z,Λ)為模型(6)的KKT點,則其應滿足式(35):
M-Z=0
(35)
由于Qk→Q,即Wk→W,Zk→Z,Λk→Λ。由算法1,當Λk→Λ時可得M-Z→0,即M-Z=0。 又由式(28)和式(33)中的一階條件,可得:
Z(ZT-Ik)+μ(M-Z)+Λ+?‖M‖1,
M(MTZ-Ik)+μ(Z-M)-Λ,
(36)
□
為比較本文的連續(xù)等價模型的優(yōu)化算法和經典的K-means算法在數(shù)據(jù)聚類上的表現(xiàn),將在人造數(shù)據(jù)和Yale Face Database[16]上開展數(shù)值實驗。人造數(shù)據(jù)為:隨機選取m維空間中的k個點作為聚類中心點,分別以這些聚類中心點構造方差均為σ的高斯點,并使得這些所有的點的總數(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é)所得的結論都是在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個元素的真實指標和聚類指標。當x=y時,δ(x,y)=1;當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ù)值作為該次的計算結果。詳細結果如表1和表2所示。通過表格對比可以看出,本文所提出的等價連續(xù)模型的優(yōu)化算法不論在聚類時間還是聚類效果上都明顯優(yōu)于經典的K-means聚類算法。
Table 1 Results of numerical experiments on artificial data表1 人造數(shù)據(jù)上的數(shù)值實驗結果
Table 2 Results of numerical experiments on Yale Face Database表2 Yale Face Database上的數(shù)值實驗結果
本文將經典K-means模型進行矩陣化處理,并結合聚類的本質屬性提出了一類非凸的連續(xù)優(yōu)化模型?;贏DMM算法給出了該模型的迭代算法,并從理論上討論了解的收斂性問題。通過人造數(shù)據(jù)和人臉數(shù)據(jù)驗證了該算法相比經典的K-means算法在聚類時間和聚類效果上的極大提升。所提模型和算法克服了傳統(tǒng)K-means的計算瓶頸,為解決大數(shù)據(jù)聚類中的相關問題提供了一個途徑。但是,本文給出的算法參數(shù)較多,針對不同的問題需要調試參數(shù),這需要進一步進行研究簡化。