程 寧 戴遠泉

(湖北輕工職業(yè)技術(shù)學院計算機學院 湖北 武漢 430070)

0 引 言

當來自同一類的數(shù)據(jù)向量彼此線性相關(guān)時,可以利用數(shù)據(jù)向量之間的相似性或距離度量進行聚類[1]。這樣的模型已經(jīng)在遙感信息、人類行為分類等領(lǐng)域得到了廣泛的應(yīng)用[2-3]。聚類效果的好壞對于分類以及識別精度等都會產(chǎn)生較大的影響,因此如何盡可能地提升聚類效果是大數(shù)據(jù)時代研究的熱點[4]。

針對來自不同來源的信號或來自不同類別的不相關(guān)數(shù)據(jù)向量,已經(jīng)有文獻很好地探討了使用線性相關(guān)來解決聚類問題。文獻[5]提出了一種適用于線性數(shù)據(jù)模型的基于典型相關(guān)分析(Canonical Correlation Analysis,CCA)的聚類框架,將工作擴展到基于卷積神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)模型中。文獻[6]討論了一種半監(jiān)督方法,在多視圖環(huán)境中利用類間和類內(nèi)的相關(guān)性實現(xiàn)聚類。文獻[7]提出了一種基于旋轉(zhuǎn)和投影的對稱正交非負矩陣分解(Nonnegative Matrix Factorization,NMF)交替方法。

但是上述方法均是針對考慮數(shù)據(jù)中的線性相關(guān)性,針對數(shù)據(jù)中的非線性問題未提出解決方法。在過去幾年中,許多不同的方法已經(jīng)被提出來處理非線性傳感器-源關(guān)系。深度NMF方法將矩陣分解為兩個以上的因子,從而得到更適合聚類的低維模型[8]。核化或基于圖的方法通過將數(shù)據(jù)映射到更高維空間或通過使用圖正則化器懲罰代價函數(shù)來處理非線性數(shù)據(jù)模型[9]。在基于核CCA的聚類算法中,數(shù)據(jù)協(xié)方差矩陣被RBF核協(xié)方差矩陣代替[10]。文獻[11]探討了一種利用非線性數(shù)據(jù)關(guān)系進行聚類的基于圖的方法,其中標準NMF代價函數(shù)由一個圖正則化器補充。雖然上述方法考慮到了數(shù)據(jù)相關(guān)性中的非線性,但是方法十分依賴有監(jiān)督訓練來尋找合適的核或圖,并且需要先驗知識選擇與數(shù)據(jù)相關(guān)的多個可調(diào)參數(shù)。

針對上述問題,提出一種基于核協(xié)方差矩陣的無監(jiān)督數(shù)據(jù)聚類方法,通過數(shù)據(jù)集實驗驗證本文方法能夠有效解決無監(jiān)督聚類問題。

1 相關(guān)方法

1.1 問題描述

考慮從總共Q個類中獲得的一組P個信號或數(shù)據(jù)向量。假定來自特定類的信號受相同的源信號影響。給定Q個源或類的總數(shù),第i個信號向量為xi(n),存在

(1)

在不同的應(yīng)用場景下,未知函數(shù)fj(·)可以是線性的或非線性的。在線性情況下,假設(shè)源信號sj(n)?j∈{1,2,…,Q}是互不相關(guān)的,信號間的互相關(guān)可以作為相似性度量用于識別是否來自同一個源的或者屬于同一類的信號。因此線性情況下的協(xié)方差矩陣可以表示為:

(2)

1.2 誘導稀疏

稀疏正則化矩陣分解可以表示為:

(3)

s.t.M≥0,N≥0

1.3 核化框架與核選擇

(4)

核化矩陣分解的目標可以表述為:

(5)

基于矩陣分解的聚類方法的主要優(yōu)點在于它們是無監(jiān)督的,并且不需要任何訓練數(shù)據(jù)。然而式(5)中所述的矩陣分解框架需要一個合適的核協(xié)方差矩陣,其性能在很大程度上取決于一個核的適當選擇或多個核的線性組合。在文獻中,核選擇/學習任務(wù)主要是在有監(jiān)督的環(huán)境下完成的,因此總體方案并非真正的無監(jiān)督。

為了鞏固塊對角協(xié)方差矩陣的重要性,考慮Salinas數(shù)據(jù)集中來自4個不同類的高光譜圖像像素的例子。每個高光譜像素是一個224維向量,其中每個維度代表特定頻段的能量。像素是根據(jù)類標簽排序的,因此來自同一類的像素一起出現(xiàn)?？紤]在不同方差值上為這些像素計算的高斯核協(xié)方差矩陣族。在圖1(a)-圖1(c)中,有方差值分別為103.5、10-1.5和1010的核協(xié)方差矩陣。可以看出,對于高斯方差參數(shù)的高值和低值,高光譜像素之間的關(guān)系完全喪失,因為低方差表示所有像素都是獨立的,而對于高方差則表示所有像素似乎都是相關(guān)的。但是,當方差設(shè)置得當時,如圖1(a)所示,可以觀察到塊對角線行為,其中每個塊代表來自同一類的像素之間的高度相關(guān)性以及屬于不同類的像素之間的不相關(guān)性。

(a) σ2=103.5

(b) σ2=1010

(c) σ2=10-1.5圖1 在核協(xié)方差結(jié)構(gòu)中選擇不同的核方差σ2的影響

命題1在由式(1)和式(2)描述的線性設(shè)置中,可以假定相關(guān)矩陣是塊對角的。表示來自同一類的信號之間的高相關(guān)性的每個塊對角可以被視為秩-1塊,并且在具有Q類的數(shù)據(jù)集中,存在Q個這樣的秩-1對角塊。

(6)

因此,在具有Q個可能類的數(shù)據(jù)中,有效的核學習的目標是尋找具有基礎(chǔ)映射φ(·)的核,該映射可以線性化高維空間中的相關(guān)性,使得對角線上有Q個秩-1的塊,從而得到秩為Q的核協(xié)方差矩陣。

1.4 基于特征向量的核選擇

對于實際應(yīng)用,數(shù)據(jù)總是會受到某些噪聲的破壞,而且數(shù)據(jù)向量的長度是有限的,因此只能評估實際協(xié)方差的估計值。因此,評估的協(xié)方差矩陣的秩幾乎總是大于Q。為了在實際應(yīng)用中施加秩Q約束,可以對Q個最大特征值的大小施加約束。但是最大化Q個特征值之和是不夠的,因為圖1(b)中考慮的形式的矩陣在所有項中的大小都是恒定的,并且會導致可行矩陣的強特征值小于Q。因此,重要的是不僅要最大化Q個特征值之和,而且要確保矩陣具有Q個強特征值。為此,提出可最大化第Q個最大特征值,以確保矩陣的秩至少為Q。

(7)

式中:函數(shù)Λi(.):RP×P→R表示輸入自變量矩陣的第i個最大特征值。對于給定矩陣K,其定義為:

(8)

s.t.VVT=IQ

式中:IQ是Q×Q的單位矩陣;矩陣V的列是K的特征向量;V是一個P×Q的矩陣。

因此,第Q特征值最大的核協(xié)方差矩陣最適合于基于矩陣分解的聚類。鑒于核矩陣對于每個核參數(shù)的縮放比例可能不同,因此在找到特征值之前適當?shù)貙ζ溥M行歸一化至關(guān)重要。由于本文方法著重于提高第Q個特征值的大小,因此適當?shù)臍w一化策略是按所有特征值的總和縮放每個矩陣。因此,在歸一化后,最大化第Q個特征值等效于最大化第Q個特征值相對于所有特征值之和的百分比份額。

式(8)中的特征值最大化問題也可以替代地用不同的形式表示為特征值和的差,即:

(9)

式(9)給出的凸函數(shù)公式的一個差為優(yōu)化提供了一定的優(yōu)勢。然后,可以將基于第Q個特征值最大化的核學習目標表示為:

(10)

因此,總體聚類問題的目標可以這樣表述:

(11)

如果存在B個字典核的線性組合,使得整個核協(xié)方差矩陣具有秩Q,則式(11)在其最小值處達到期望的解。

2 本文算法

2.1 非凸性

2.2 凸函數(shù)的差分算法

(12)

式中:?H(Xk)是H(X)在Xk處的次梯度,上標k代表DCA的第k次迭代。

(13)

松弛目標函數(shù)可以表示為:

(14)

(15)

索引k是最外面的循環(huán)迭代索引,它計算所有三個參數(shù)M、N和α的更新。每個迭代k包含兩個更新循環(huán):(1) 在保持N=Nk-1恒定的同時更新M、α;(2) 更新N,保持M、α恒定。內(nèi)循環(huán)根據(jù)索引p進行。在迭代p期間,評估基于式(13)的仿射優(yōu)化器。然后,使用簡單的基于次梯度下降或基于內(nèi)部點的方法來解決具有主化近似的松弛問題。次梯度下降的迭代次數(shù)可以進一步由索引q表示。對于投影的次梯度下降情況,有關(guān)于M和α的次梯度為:

(16)

(17)

因此,在第p+1次迭代中迭代地重新評估式(13)中的仿射優(yōu)化?？傮w算法在算法1中進行概述。

算法1基于核協(xié)方差矩陣的無監(jiān)督數(shù)據(jù)聚類算法

1.初始化M和αj;

3.while

4.while|Mk,p-Mk,p-1|>thresh1do

5.N=Nk-1,p*;

7.使用式(16)更新M和αj直到收斂。

8.endwhile

9.while|Nk,p-Nk,p-1|>thresh1do

10.M=Mk-1,p*;

12.使用式(16)更新N直到收斂;

13.endwhile

14.endwhile

3 實驗與結(jié)果分析

3.1 綜合示例

作為核化框架的一部分,這里使用從兩個最常用的核家族,高斯徑向基函數(shù)(RBF)核和多項式核派生的不同的核矩陣。實際上,該字典可以由超出RBF和多項式的不同核族構(gòu)建而成。高斯核和多項式核的表達式如下:

(18)

為了進一步解釋本文算法,考慮了一個Q=4類的綜合示例。來自4類的每一類都有15個向量,因此核矩陣的大小為60×60。為了提高可視化效果,在評估核協(xié)方差之前,應(yīng)將來自同一類的向量視為有序/分組在一起。從圖2(a)中可以看出,總共考慮了B=6個人工生成的核。從圖2(a)的左上角開始,順時針旋轉(zhuǎn),第一個核的值全部為零。下一個對類1和3的元素具有較高的協(xié)方差。下一個僅對類2具有較高的協(xié)方差。接下來的兩個核表示不合適的信息,因為對角矩陣表示所有數(shù)據(jù)向量都是獨立的,而常值核表示所有數(shù)據(jù)向量都來自同一類。圖2(a)中的最后一個核表示來自類4的高度相關(guān)的向量。對于此設(shè)置,希望核學習對核矩陣2、3和6具有非零的αj值(從圖2(a)中的左上角開始順時針編號)。

(a) 6個輸入核

請注意,用于聚類的基于稀疏性的矩陣分解框架依賴于不同類之間的不相關(guān)性。映射的特征空間中的轉(zhuǎn)換數(shù)據(jù)必須滿足此屬性,而原始數(shù)據(jù)空間中的類并不一定是不相關(guān)的。確定非線性映射φ(·),以便在映射的特征空間中,來自不同類的變換后的數(shù)據(jù)元素可以不相關(guān)。因此,所提出的基于特征值最大化的框架可以用于識別映射,即具有塊對角結(jié)構(gòu)的適當?shù)暮藵M足映射特征空間中的不相關(guān)假設(shè)。

3.2 對比設(shè)置

在本節(jié)中,將使用多個數(shù)據(jù)集顯示數(shù)值結(jié)果,以證明本文算法的有效性。在3種不同的設(shè)置下驗證整個核學習和聚類框架的性能:(1) 高光譜圖像數(shù)據(jù)集;(2) 基于智能手機的人類活動檢測和文檔分類數(shù)據(jù)集。

將本文方案的性能與5種不同的無監(jiān)督算法進行比較:(1) 標準非負矩陣分解(NMF)[6];(2)
圖非負矩陣分解(GNMF)[7];(3) Deep NMF(DNMF)[11];(4) 核典型相關(guān)分析(CCA)[10];(5) K-Means[9]。還展示了在10%和25%訓練數(shù)據(jù)下的核支持向量機的結(jié)果,該核支持向量機方法為SVM與K-means結(jié)合的聚類算法(SK-Means)[15],從而對類似仿真環(huán)境下監(jiān)督方法的性能進行對比。

對于GNMF和Deep NMF,對200多個不同的參數(shù)集進行了重復(fù)模擬,以確定適合每個數(shù)據(jù)集的參數(shù)。在GNMF情況下,進行了這200次參數(shù)選擇重復(fù)以識別2個實體:(1) 權(quán)重圖拉普拉斯相關(guān)項的alpha因子,其值在0.001～200之間變化;(2) 最佳關(guān)聯(lián)圖。對于每個參數(shù)組合,將結(jié)果平均10次重復(fù)。在Deep NMF情況下,本文在分析中使用了多達4個層,大小各異。對于不同的組合,分解層的數(shù)量在2至4之間變化,每層的大小在4至200范圍內(nèi)變化。每種組合在10次重復(fù)中再次取平均值。此處展示的結(jié)果是每個單獨數(shù)據(jù)集的參數(shù)的最佳組合。

對于本文方法,確定了高光譜圖像數(shù)據(jù)集的λ和μ值。首先,選擇μ的值。為了使矩陣分解達到理想的結(jié)果,必須選擇塊對角核。因此,為了表示基于特征值的核學習任務(wù)的優(yōu)先級,參數(shù)μ被賦予一個較大的值。這里嘗試了100、25、10和1的值。從這10個中選出了一個。接下來,選擇稀疏性參數(shù)λ。根據(jù)文獻[3]選擇了該參數(shù)的值。這些值以0.1的乘法步驟從1減少,即1、0.1、0.01和0.001等。由于會產(chǎn)生非零支持的稀疏矩陣因子,因此發(fā)現(xiàn)0.001的值就足夠了,因此只需要4次迭代。所有數(shù)據(jù)集都使用相同的參數(shù)值,說明了所選參數(shù)和算法對不同數(shù)據(jù)集的魯棒性,以及類數(shù)Q和數(shù)據(jù)向量數(shù)P的變化。

對于GNMF和Deep NMF的仿真,使用了相應(yīng)論文作者提供的代碼。對于核SVM,使用了MATLAB中具有自動縮放功能的內(nèi)置實現(xiàn),其中,使用訓練數(shù)據(jù)自動選擇了核參數(shù)。對于K-Means,也使用了MATLAB的內(nèi)置實現(xiàn),提出基于SVM的K-means聚類算法,該機制主要是首先對數(shù)據(jù)集節(jié)點進行初次聚類,找到聚類中心和簇群,然后對每個簇群內(nèi)運用支持向量機算法使簇群內(nèi)的不同類節(jié)點間距離最大化以減少分簇的風險,再對兩兩分類后的簇群重新劃分簇并判斷聚類中心是否改變,最后通過不停迭代直至達到最優(yōu)的效果。聚類精度作為比較方法性能的度量。

3.3 活動檢測

第一個數(shù)據(jù)集是基于米蘭比可卡大學智能手機的人類活動識別(UniMiB)數(shù)據(jù)集。該數(shù)據(jù)集包含來自安裝在30個不同用戶上的智能手機的加速度計讀數(shù),這些用戶執(zhí)行一系列活動,包括步行、跑步和爬樓梯。信號被預(yù)分割為各個時期,每個時期的長度為51個樣本,并以該時期的峰值為中心。沿著加速度計的每個XYZ軸考慮信號,因此,連接的信號長153個樣本。目的是根據(jù)信號/向量所代表的活動類別對其進行聚類。

從步行、跑步和爬樓梯這3個活動來考慮各個時期。結(jié)果在所有30個用戶上取平均值,并在圖3中以箱形圖的形式顯示,方框中的標記是指中值準確度,而方框的邊緣標記了所有實驗中準確度的25%和75%?？梢钥闯?所提出的框架的性能優(yōu)于6個方案。對于Deep NMF情況,具有2個分別有50和4個特征的隱藏層的配置,對于GNMF情況,α=1.2,產(chǎn)生了最佳準確度。結(jié)果表明,相對于其他幾種無監(jiān)督算法,在數(shù)據(jù)集向量弱相關(guān)或者不相關(guān)條件下,本文方法能夠保證較高的聚類精度,并且無須依賴先驗知識調(diào)整參數(shù)。相對于有監(jiān)督算法,本文方法無須依賴有監(jiān)督訓練就能夠?qū)崿F(xiàn)較高的聚類精度。

圖3 UniMiB數(shù)據(jù)集的準確率比較的箱形圖

3.4 高光譜圖像

高光譜圖像數(shù)據(jù)集代表了本文方法在遙感環(huán)境中的應(yīng)用。此處考慮的圖像已由位于加利福尼亞州薩利納斯山谷的AVIRIS傳感系統(tǒng)捕獲,并具有224個維度,分別代表不同頻段的能量。圖像主要由農(nóng)田組成,其中圖像的不同部分存在不同的農(nóng)作物/材料。每個像素觀察到16種不同類型的材料/作物之一。目的是獨立考慮每個像素,并根據(jù)它們觀察到的材料將基于224維向量的像素聚類為不同的類?；炯僭O(shè)是:觀察相同類的像素將具有相似的光譜反射率值。對于仿真,在每次迭代過程中,考慮一組Q=4種不同的隨機選擇材料,并選擇15個隨機像素表示這4類。在總共100個隨機材料和像素選擇上重復(fù)了該實驗。

總體聚類精度可以在圖4中看到。圖4顯示了100次實驗的準確率的箱形圖,在圖4(b)中,在P=500像素的更大數(shù)據(jù)設(shè)置中,還展示了不同方法的準確度。從這些數(shù)字可以推斷出,GNMF和本文方法在性能上彼此相似,并且都比經(jīng)過10%訓練的Deep NMF、CCA、K-Means和SK-Means聚類方法更好。在GNMF情況下,使用α=1的值。由于高光譜圖像數(shù)據(jù)量較大,因此幾乎所有方法的聚類精度都較高,隨著像素的增大,數(shù)據(jù)量也隨之增大,可以發(fā)現(xiàn)無論數(shù)據(jù)量的大小,本文方法的聚類精度均能保持較高的水平,而傳統(tǒng)的SK-means聚類方法在訓練數(shù)據(jù)大小不同時,聚類精度差距較大,說明有監(jiān)督方法對于數(shù)據(jù)樣本大小依賴性較強,而無監(jiān)督算法對數(shù)據(jù)的依賴程度明顯較低。相對于其他幾種無監(jiān)督算法,本文方法能夠保證較高的聚類精度,驗證了本文算法不僅不需要先驗知識調(diào)整參數(shù),而且在聚類精度能夠得到保證。

(a) P=100

(b) P=500圖4 Salinas高光譜圖像數(shù)據(jù)集的準確率箱形圖

3.5 文檔聚類

第三個數(shù)據(jù)集是la2數(shù)據(jù)集,該數(shù)據(jù)集是使用《洛杉磯時報》的文章編譯而成的,并已在TREC中使用。數(shù)據(jù)集包含6個類的3 075個文件,所考慮的文件至少有100個單詞,因此考慮的文件總數(shù)減少到2 030。在此評估中,考慮了一組來自4個不同類的100個文件,從每個類中隨機選擇25個。與其他案例研究類似,這里的目標是將屬于同一類的文檔進行聚類。一個文檔由一個向量表示,其中它的維數(shù)表示某個特定單詞的出現(xiàn)頻率。

在圖5中給出了文檔數(shù)據(jù)集聚類精度的箱形圖。收斂時,α值對于對應(yīng)于σ2=107、σ2=106和σ2=105的RBF核和度為2的多項式核的核矩陣具有顯著的權(quán)重。對于Deep NMF情況,分別具有2個有200和4個特征的隱藏層的配置,對于GNMF情況,α=0.05,產(chǎn)生了最高的準確度。

圖5 文件聚類數(shù)據(jù)集的準確率箱形圖

由于該數(shù)據(jù)量較少,聚類結(jié)果表明在數(shù)據(jù)量較少的情況下,SK-Means聚類方法聚類性能明顯下降,其他幾種無監(jiān)督算法的聚類精度相比之下也不夠理想,而本文方法依舊能夠保持相對較高的聚類精度?？傮w而言,由于核學習組件可確保來自不同類的元素之間具有弱相關(guān)性,而類內(nèi)數(shù)據(jù)則具有強相關(guān)性,而l1-l2懲罰矩陣分解框架可實現(xiàn)無監(jiān)督的準確聚類,因此該新型框架具有更好的聚類性能。說明即使在數(shù)據(jù)匱乏的情況下,新框架也可以實現(xiàn)更好的聚類性能,即提出的框架在不依賴于數(shù)據(jù)訓練以及參數(shù)先驗調(diào)整的條件下,能夠在無監(jiān)督條件下實現(xiàn)良好的聚類性能。

3.6 計算成本分析

進一步分析各個數(shù)據(jù)集上相應(yīng)方法的計算時間,如表1所示,本文方法雖然較其他以先驗知識為基礎(chǔ)的無監(jiān)督算法的計算時間要長,但是其計算時間整體上與有監(jiān)督算法相差不大,主要因為有監(jiān)督方法需要大量的時間進行訓練,這進一步證明了本文方法在計算時間上具有實用性。

表1 算法計算時間對比 單位:s

4 結(jié) 語

為解決數(shù)據(jù)向量聚類模型過于依賴先驗知識以及有監(jiān)督訓練問題,提出一種基于核協(xié)方差矩陣的無監(jiān)督數(shù)據(jù)聚類方法。通過高光譜圖像、人類活動、文檔分類三個數(shù)據(jù)集的驗證表明:

(1) 本文算法針對不同的數(shù)據(jù)集均能表現(xiàn)出較好的聚類性能,驗證了算法對于數(shù)據(jù)集具有較強的泛化性能。針對非線性數(shù)據(jù)類之間相關(guān)性較弱等問題,本文方法能夠?qū)崿F(xiàn)較好的聚類效果。

(2) 本文方法的聚類性能不僅較優(yōu)于有監(jiān)督以及其他幾種無監(jiān)督算法的聚類性能,而且能夠解決監(jiān)督訓練依賴性以及無監(jiān)督參數(shù)選擇難的問題。在數(shù)據(jù)量稀疏或者先驗知識不足條件下,依舊能夠?qū)崿F(xiàn)良好的聚類效果。

(3) 本文方法計算成本相較于其他方法并無增加,進一步說明本文方法具有較好的實用性能。