基于上界單純形投影圖張量學(xué)習(xí)的多核聚類算法

雷皓云，任珍文，汪彥龍，薛 爽，李浩然

（1.西南科技大學(xué)國防科技學(xué)院，四川綿陽 621010；2.電子科技大學(xué)信息與通信工程學(xué)院，成都 611731；3.計(jì)算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室（南京大學(xué)），南京 210023；4.浙江傳媒學(xué)院媒體工程學(xué)院，浙江杭州 310018）

（?通信作者電子郵箱rzw@njust.edu.cn）

0 引言

聚類致力于將一組無標(biāo)簽數(shù)據(jù)劃分為多個(gè)類簇，是一種在機(jī)器學(xué)習(xí)與人工智能領(lǐng)域被廣泛研究的基礎(chǔ)科學(xué)問題［1-2］，特別地，針對(duì)復(fù)雜非線性數(shù)據(jù)的聚類極具挑戰(zhàn)性。

核方法能將原始空間中的非線性數(shù)據(jù)映射到可再生核希爾伯特空間（Reproducing Kernel Hilbert Space，RKHS），使數(shù)據(jù)線性可分。因此，核方法在非線性數(shù)據(jù)處理問題上被廣泛地應(yīng)用。近年來，盡管傳統(tǒng)的單核學(xué)習(xí)取得了長(zhǎng)足的進(jìn)步，但其面臨著核函數(shù)與核參數(shù)選擇的難題，而多核學(xué)習(xí)能很好地克服單核學(xué)習(xí)這一缺陷，同時(shí)能充分利用基核之間互補(bǔ)與一致信息，這使得多核學(xué)習(xí)在復(fù)雜數(shù)據(jù)聚類任務(wù)中變得非常流行。此外，圖學(xué)習(xí)具有很強(qiáng)的挖掘數(shù)據(jù)復(fù)雜結(jié)構(gòu)信息的能力，被特征提取、聚類分析、半監(jiān)督學(xué)習(xí)和深度學(xué)習(xí)等研究廣泛使用。基于上述討論，將多核學(xué)習(xí)與圖學(xué)習(xí)相結(jié)合，形成了新的多核聚類研究范式，即多核圖聚類。

多核圖聚類的核心問題是從多個(gè)預(yù)定義的基核中，利用圖學(xué)習(xí)方法學(xué)習(xí)聚類用的關(guān)系圖（Affinity Graph，AG）［3-6］。其典型的工作方式包括：1）通過多個(gè)基核函數(shù)構(gòu)造多個(gè)核格拉姆矩陣，簡(jiǎn)稱為基核；2）利用基核學(xué)習(xí)一個(gè)共識(shí)核與一個(gè)關(guān)系圖；3）在關(guān)系圖的基礎(chǔ)上，使用圖聚類算法得到最終聚類結(jié)果。

基于多核學(xué)習(xí)和圖學(xué)習(xí)的優(yōu)越性，近年來，涌現(xiàn)出了大量多核圖聚類方法：例如，自保持結(jié)構(gòu)的多核聚類（Structure-Preserving Multiple Kernel Clustering，SPMKC）算法分別引入了核組自表示項(xiàng)（Kernel Group Self-Expressiveness，KGS）和自適應(yīng)局部結(jié)構(gòu)學(xué)習(xí)項(xiàng)（Adaptive Local Structure Learning，ALSL），保留了數(shù)據(jù)的全局和局部結(jié)構(gòu)信息［7］，提高了關(guān)系圖的質(zhì)量；基于鄰核子空間分割的多核聚類（Multiple Kernel Clustering with Neighbor-Kernel Subspace Segmentation，KSMKC）算法定義了近鄰核概念，在線性加權(quán)核的鄰域內(nèi)搜索最佳共識(shí)核，并引入拉普拉斯秩約束規(guī)范圖結(jié)構(gòu)［8］。雖然上述方法已具備良好的性能，但將研究重心放在學(xué)習(xí)共識(shí)核上，這違反了基于圖聚類過程中任務(wù)核心在于圖的事實(shí)。因此，基于純圖學(xué)習(xí)的多核聚類（Multiple Kernel Clustering with Pure Graph learning，PGMKC）算法利用核空間中全局低維的流行結(jié)構(gòu)獲得多個(gè)候選關(guān)系圖，隨后通過自加權(quán)圖融合策略和一個(gè)塊對(duì)角性質(zhì)直接完成類簇分割；基于共識(shí)關(guān)系圖的多核聚類算法（Consensus Affinity Graph Learning，CAGL）保留了核空間中數(shù)據(jù)的局部流形結(jié)構(gòu)，利用多個(gè)基核學(xué)習(xí)多個(gè)候選關(guān)系圖，再直接通過一種自適應(yīng)權(quán)重的圖融合模型得到一個(gè)共識(shí)關(guān)系圖，避免了同時(shí)學(xué)習(xí)共識(shí)核和關(guān)系圖帶來的巨大計(jì)算復(fù)雜度［9］；同樣的候選圖學(xué)習(xí)方式在基于局部一致性和多樣性圖（Locally Consistent and Selfish Graph，LCSG）的多核聚類算法中被使用，與CAGL 不同，LCSG 通過施加圖形連通性約束將數(shù)據(jù)自然地劃分為所需的簇?cái)?shù)，而不需要執(zhí)行額外的聚類算法來生成最終的聚類標(biāo)簽［10］。

雖然現(xiàn)有的多核圖聚類方法具有優(yōu)秀的聚類性能，但仍面臨三個(gè)問題：1）復(fù)雜的圖學(xué)習(xí)技術(shù)將弱化聚類模型的可讀性，并帶來較高的計(jì)算代價(jià)；2）數(shù)據(jù)集樣本的個(gè)數(shù)n遠(yuǎn)大于簇的個(gè)數(shù)c，導(dǎo)致圖拉普拉斯矩陣的高秩特性，使得對(duì)聚類結(jié)果起到關(guān)鍵作用的塊對(duì)角性質(zhì)很難滿足，削弱了聚類性能；3）大部分方法局限于二維矩陣層面的低階信息挖掘，而忽略了候選關(guān)系圖之間的高階結(jié)構(gòu)信息。

針對(duì)上述問題，本文提出一種新穎的多核圖聚類方法，即基于上界單純形投影圖張量學(xué)習(xí)的多核聚類算法（Multiple Kernel Clustering algorithm based on Capped Simplex projection Graph Tensor learning，CSGTMKC）。如圖1 所示，該方法的主要步驟包括：1）CSGTMKC利用核技巧將原始數(shù)據(jù)映射到希爾伯特核空間中得到多個(gè)基核；2）將每個(gè)基核直接投影到上界單純形上形成候選關(guān)系圖，同時(shí)，在此空間上提出了一種精確的塊對(duì)角約束，使關(guān)系圖在上界單純形上具有良好的塊對(duì)角性質(zhì)；3）引入低秩張量學(xué)習(xí)，充分挖掘多個(gè)候選關(guān)系圖間的高階結(jié)構(gòu)信息。

圖1 CSGTMKC的框圖Fig.1 Block diagram of CSGTMKC

本文主要的工作如下：

1）提出了一種新的圖學(xué)習(xí)范式，利用投影技術(shù)將基核直接投影到上界單純形上形成候選關(guān)系圖，降低了圖學(xué)習(xí)的計(jì)算復(fù)雜度；

2）提出一種新的塊對(duì)角約束，使關(guān)系圖具有更好的聚類結(jié)構(gòu)；

3）引入三階圖張量學(xué)習(xí)，充分挖掘候選關(guān)系圖間的高階結(jié)構(gòu)信息；

4）設(shè)計(jì)了一種基于ADMM 的優(yōu)化算法來求解CSGTMKC，與最先進(jìn)的多核圖聚類方法相比，所提方法的聚類性能得到了顯著提升。

1 相關(guān)工作

本章主要介紹本文提出的基于上界單純形投影圖張量學(xué)習(xí)的多核聚類模型。

1.1 符號(hào)定義

為了方便介紹，半正定的矩陣如M，表示為M-?0。使用Q表示張量，對(duì)于一個(gè)三階張量，它包含了兩個(gè)重要的定義，即纖維和切片：纖維定義為三階張量任意一階為可變而剩余兩階為固定的狀態(tài)，分別表示為：模式-1，Q(：，j，k)，模式-2，Q(i，：，k)和模式-3，Q(i，j，：)；切片定義為張量任意兩階為可變而剩余一階為固定的狀態(tài)，如水平切片Q(i，：，：)，側(cè)切片Q(：，j，：)和前切片Q(：，：，k)。為方便表示，將Q(：，：，k)表示為Q(k)。Qf=fft(Q，[]，3)和Q=ifft(Qf，[]，3)分別表示三階張量Q的傅里葉變換和傅里葉逆變換。定義和fold(bvec(Q))=Q表示三階張量的塊向量化操作和塊向量化操作的逆運(yùn)算。使用分別表示塊對(duì)角和分組循環(huán)矩陣。

1.2 三階張量術(shù)語

為了幫助理解張量，本節(jié)介紹三階張量相關(guān)的主要定義。

定義1兩個(gè)維數(shù)相匹配的張量，如和，對(duì)應(yīng)的乘積表示為，如：

定義2若一個(gè)張量的所有前切片都為對(duì)角矩陣，則稱該張量為f?對(duì)角張量。

定義3本文將張量的奇異值分解（tensor Singular Value Decomposition，t-SVD）定義為：

定義4本文使用‖Q‖?表示張量Q基于t-SVD 的核范數(shù)（t-SVD based Tensor Nuclear Norm，t-TNN）。等價(jià)于Qf所有前切片的奇異值之和，即表示為下式：

與基于展開的張量核范數(shù)相比，t-TNN 能更好地利用張量的結(jié)構(gòu)信息［5］。

2 本文方法

在文獻(xiàn)［23］中，通過大量基核來學(xué)習(xí)共識(shí)核，提升了關(guān)系圖的質(zhì)量。為避免復(fù)雜的圖學(xué)習(xí)過程，本文將基核投影到上界單純形（即可行單純集與上限的組合）上直接形成關(guān)系圖，因此預(yù)定義的m個(gè)基核投影后可得到m個(gè)候選關(guān)系圖。在基于圖的方法中，塊對(duì)角性質(zhì)是用于類簇分割的重要性質(zhì)，由文獻(xiàn)［4］可知：任意關(guān)系圖對(duì)應(yīng)的拉普拉斯矩陣中特征值0 的個(gè)數(shù)n應(yīng)等于連通分量個(gè)數(shù)c。基于此，許多方法都使用了圖拉普拉斯秩約束rank(L)=n-c來獲得精確的塊對(duì)角數(shù)［6］，但由于實(shí)際情況中n的數(shù)量遠(yuǎn)大于c，導(dǎo)致L具有很高的秩，使得該約束很難滿足。基于上述討論，本文提出如下的目標(biāo)函數(shù)：

其中：H(k)和S(k)分別表示第k個(gè)基核和第k個(gè)候選關(guān)系圖，α為平衡參數(shù)。在上界單純形中投影得到S(k)后，使用F 范數(shù)正則化項(xiàng)來避免產(chǎn)生平凡解，同時(shí)避免S(k)中的某些元素值太大造成偏袒部分樣本。此外，是單純形上的塊對(duì)角約束，來保持學(xué)習(xí)的圖S具有精確的c個(gè)連通子圖。由于篇幅限制，詳細(xì)證明可在實(shí)驗(yàn)室主頁（http：//unix8.net）下載。

另一方面，由于張量能從高維角度出發(fā)，挖掘多個(gè)候選關(guān)系圖之間的高階結(jié)構(gòu)信息來提高聚類性能［11］，本文將獲得的m個(gè)關(guān)系圖堆疊成三階張量S*∈Rn×n×m，然后旋轉(zhuǎn)S*變?yōu)镾∈Rn×m×n，即rotate(S*)。此外，由于圖張量中的樣本數(shù)n和特征數(shù)d遠(yuǎn)大于關(guān)系圖的個(gè)數(shù)m，即n?m和d?m，因此給圖張量S施加秩約束能捕獲視圖-視圖、樣本-樣本之間的低秩結(jié)構(gòu)信息。隨后，通過對(duì)關(guān)系圖的堆疊和旋轉(zhuǎn)，并引入‖S‖?作為正則項(xiàng)，能充分捕獲候選關(guān)系圖間的高階結(jié)構(gòu)信息，如圖2所示。至此，最終目標(biāo)函數(shù)可以寫成：

圖2 CSGTMKC中張量的堆疊與旋轉(zhuǎn)Fig.2 Tensor stacking and rotation in CSGTMKC

3 模型優(yōu)化

本章提出了一種基于交替迭代方向乘子法（Alternating Direction Method of Multipliers，ADMM）的優(yōu)化算法對(duì)式（5）進(jìn)行優(yōu)化求解。根據(jù)ADMM 的原理，首先引入一個(gè)輔助變量A，得到如下優(yōu)化問題：

接著，式（6）的增廣拉格朗日函數(shù)定義如下：

國際網(wǎng)間互聯(lián)：DDoS統(tǒng)一管理平臺(tái)通過骨干網(wǎng)運(yùn)維系統(tǒng)對(duì)國際出口路由器或海外 POP 路由器發(fā)送黑洞路由，實(shí)現(xiàn)對(duì)特定方向流量、特定區(qū)域流量或全部流量的封堵。

其中Y為拉格朗日乘子，μ＞0 為懲罰參數(shù)。接著，通過交替迭代的方法逐個(gè)更新每個(gè)變量。

3.1 固定其他變量，更新S

其中：A(k)和Y(k)分別為張量rotate(A)和rotate(Y)的第k個(gè)前切片。式（8）可以被改寫為：

其中，B(k)為引入的輔助變量，定義為

接著，優(yōu)化問題（9）可利用定理1進(jìn)行快速求解。

定理1對(duì)于任意一個(gè)對(duì)稱的關(guān)系矩陣S∈Rn×n，其SVD分解為B=UDiag(δ)UT，則下述問題：

的最優(yōu)解可通過S*=UDiag(ρ*)UT得到，其中ρ*由下式計(jì)算得到：

3.2 固定其他變量，更新A

關(guān)于A的優(yōu)化問題如下：

定理2對(duì)于任意標(biāo)量ρ＞0 以及兩個(gè)三階張量，以下問題：

的全局最優(yōu)解可由奇異值收縮算子計(jì)算得到［12］，即

當(dāng)B=U*G*VT且Cn3ρ=G*Q時(shí)，則表示一個(gè)f?對(duì)角張量，Q的每一個(gè)對(duì)角元素定義為：

3.3 ADMM變量更新

本文通過以下方式更新ADMM的變量：

其中ρ和μmax是ADMM所涉及的標(biāo)量。在每次迭代中，通過下述等式檢查算法的收斂性：

其中，ε為閾值參數(shù)。在得到大小為n×m×n維度的張量S后，通過張量逆旋轉(zhuǎn)操作S*=irotate(S)，將S旋轉(zhuǎn)為為n×n×m維度。隨后，通過下式計(jì)算S*所有前切片的均值作為最終關(guān)系圖，即-S：

綜上，CSGTMKC 的偽代碼如算法1 所示。有關(guān)聚類結(jié)果ACC、NMI的詳細(xì)介紹參見實(shí)驗(yàn)部分4.2節(jié)。

算法1 CSGTMKC算法。

3.4 計(jì)算復(fù)雜度

4 實(shí)驗(yàn)與分析

本章通過6個(gè)公共基準(zhǔn)數(shù)據(jù)集對(duì)CSGTMKC 進(jìn)行評(píng)估，實(shí)驗(yàn)均在Matlab2016 上進(jìn)行，電腦配置為3.2 GHz CPU 和16 GB RAM的Mac mini 2018。

4.1 實(shí)驗(yàn)準(zhǔn)備

實(shí)驗(yàn)數(shù)據(jù)集包括：4 個(gè)人臉圖像數(shù)據(jù)集Yale、Jaffe、AR 和ORL，一個(gè)物體數(shù)據(jù)集COIL20 和一個(gè)字符圖像數(shù)據(jù)集（Binary Alphadigits，BA）。這些數(shù)據(jù)集被廣泛用于評(píng)估聚類算法的性能。關(guān)于數(shù)據(jù)集的類數(shù)、樣本數(shù)和特征數(shù)如表1 所示，6 個(gè)數(shù)據(jù)集的示例圖像如圖3 所示，讀者可查閱文獻(xiàn)［13-14］獲得這些數(shù)據(jù)集更詳細(xì)的描述。

圖3 六個(gè)數(shù)據(jù)集的樣本圖像Fig.3 Sample images of six datasets

表1 數(shù)據(jù)集詳細(xì)信息Tab.1 Details of datasets

本節(jié)選取6 個(gè)具有代表性的聚類方法包括：基于魯棒多核k均值的聚類算法（Robust Multiple Kernelk-Means，RMKKM）［15］、基于多核k均值的聚類算法（Multiple Kernelk-Means，MKKM）［16］、基于圖的低秩核學(xué)習(xí)聚類算法（Low-rank Kernel learning Graph-based clustering，LKGr）［17］、多核譜聚類算法（Spectral Clustering with Multiple Kernels，SCMK）［18］、基于自加權(quán)多核學(xué)習(xí)的聚類算法（Self-weighted Multiple Kernel Learning，SMKL）［19］和基于歐氏距離的權(quán)重策略（Euclidean Distance-based Weight Strategy，EDWS）檢測(cè)的自保持全局和局部結(jié)構(gòu)的多核聚類（Simultaneous Global and Local Graph Structure Preserving in EDWS，SPMKC-E）算法［20］進(jìn)行對(duì)比分析。為了公平，這些對(duì)比方法分別遵循作者推薦的實(shí)驗(yàn)設(shè)置進(jìn)行了仔細(xì)調(diào)整。

4.2 評(píng)價(jià)標(biāo)準(zhǔn)

聚類精度（ACCuracy，ACC）、標(biāo)準(zhǔn)互信息（NormalizedMutual Information，NMI）和純度（Purity）是多核聚類任務(wù)用來衡量聚類精度普遍使用的指標(biāo)［21］，本文采用前2 個(gè)指標(biāo)來評(píng)價(jià)所有多核聚類方法的聚類性能。若指標(biāo)的值越大則表明聚類效果越好。有關(guān)這些指標(biāo)的詳細(xì)信息請(qǐng)參閱文獻(xiàn)［22-23］。

4.3 聚類性能比較

實(shí)驗(yàn)分別對(duì)CSGTMKC 和6 個(gè)對(duì)比方法進(jìn)行了20 次獨(dú)立實(shí)驗(yàn)，結(jié)果如表2 所示，高優(yōu)值用加粗字體表示，次優(yōu)值加下劃線表示。實(shí)驗(yàn)結(jié)果表明：

表2 基于ACC與NMI的聚類性能比較Tab.2 Clustering performance comparison in term of ACC and NMI

1）本文CSGTMKC 明顯優(yōu)于對(duì)比方法，在Yale、ORL、AR、COIL20、BA 數(shù)據(jù)集上，與MKKM、RMKKM、LKGr、SCMK、SMKL和SPMKC-E中獲得的最高精度相比，CSGTMKC 的ACC分別提高了17.2、22.5、15.2、14.7 和44.1 個(gè)百分點(diǎn)，NMI 分別提高了18.8、13、8.2、7.9和33.4個(gè)百分點(diǎn)。

在Jaffe數(shù)據(jù)集上CSGTMKC 與SPMKC-E 的ACC 與NMI值都達(dá)到了1，但CSGTMKC的計(jì)算復(fù)雜度更低。

2）基于圖的方法優(yōu)于基于核k均值的方法，因?yàn)楹薻均值是在核空間中處理原始數(shù)據(jù)，而基于圖的方法是通過在核空間中捕獲數(shù)據(jù)的連通性來完成聚類。

3）與基于圖的方法相比，CSGTMKC具有更好的塊對(duì)角性質(zhì)和稀疏性，且CSGTMKC 打破了低維關(guān)系的限制，通過構(gòu)造三階圖張量獲得高階結(jié)構(gòu)信息，提高了聚類精度。

4.4 參數(shù)敏感性

本文目標(biāo)函數(shù)包括兩個(gè)參數(shù)，其中：α用于平衡候選圖S(k)的稀疏性（如，1≤k≤m）；β平衡高階張量S的低秩屬性（如‖S‖?）。為驗(yàn)證CSGTMKC參數(shù)的敏感性，在ORL、COIL20 和AR 數(shù)據(jù)集上使用網(wǎng)格搜索法，分別在[10-6，10-5，10-4，10-3，10-2，10-1，1] 和 [10-3，10-2，10-1，1，101，102，103]范圍內(nèi)調(diào)諧α和β。實(shí)驗(yàn)結(jié)果如圖4 所示：在AR、ORL 和COIL20 數(shù)據(jù)集上，當(dāng)兩個(gè)參數(shù)的范圍分別為：α≥10-3，β≤10；α≥10-1，10-2≤β≤102和α≥10-3，β≤10時(shí)，CSGTMKC 能獲得較好的聚類精度。實(shí)驗(yàn)結(jié)果表明，CSGTMKC的參數(shù)易調(diào)諧，對(duì)于較大范圍內(nèi)的參數(shù)都不敏感。

圖4 AR、ORL和COIL20數(shù)據(jù)集上關(guān)于α和β的聚類性能Fig.4 Clustering performance in terms of α and β on AR、ORL and COIL20 datasets

4.5 收斂性和計(jì)算時(shí)間

本節(jié)通過記錄每次迭代中收斂標(biāo)準(zhǔn)的值（即‖A-S‖∞）來分析算法1 的收斂性，在ORL 和COIL20 數(shù)據(jù)集上得到的收斂曲線如圖5 所示：在經(jīng)過20 次左右的迭代后收斂曲線趨于穩(wěn)定，表明CSGTMKC具有良好的收斂性質(zhì)。

圖5 CSGTMKC在ORL和COIL20數(shù)據(jù)集上的收斂性能Fig.5 Convergence of CSGTMKC on ORL and COIL20 datasets

此外，本節(jié)評(píng)估了不同對(duì)比方法的運(yùn)行時(shí)間，在Yale 和ORL 數(shù)據(jù)集上計(jì)算所有多核聚類方法的聚類時(shí)間（以秒為單位）。為提高方法之間的可比性，在實(shí)驗(yàn)過程中對(duì)每種方法設(shè)置相同的收斂條件。實(shí)驗(yàn)結(jié)果如表3 所示，結(jié)果表明：本文CSGTMKC 的運(yùn)行時(shí)間低于MKKM、RMKKM、LKGr、SCMK、SMKL和SPMKC-E，且CSGTMKC 的聚類性能也是最好；此外，雖然MKKM 和LKGr 等方法的計(jì)算成本低于CSGTMKC，但它們的聚類性能較差。因此，從收斂性和計(jì)算成本兩個(gè)方面考慮，本文提出的CSGTMKC是一種高效的多核聚類方法。

表3 不同多核圖聚類方法的計(jì)算時(shí)間比較 單位：sTab.3 Computational time comparison of different MKGC methods unit：s

5 結(jié)語

本文提出了一種新的多核圖學(xué)習(xí)方法，即基于上界單純形投影圖張量學(xué)習(xí)的多核聚類算法CSGTMKC，該方法通過將每個(gè)基核直接投影到上界單純形上形成候選關(guān)系圖，使其具有精確的塊對(duì)角性質(zhì)，同時(shí)引入張量學(xué)習(xí)來挖掘圖中的高階結(jié)構(gòu)信息進(jìn)而完成聚類。理論上，CSGTMKC能夠解決圖學(xué)習(xí)技術(shù)復(fù)雜、塊對(duì)角性質(zhì)難以滿足和高階結(jié)構(gòu)信息缺失的問題。實(shí)驗(yàn)表明，與目前最先進(jìn)的方法相比，CSGTMKC 在聚類性能與聚類時(shí)間上更有優(yōu)勢(shì)。