基于核協方差矩陣的無監督數據聚類

程 寧 戴遠泉

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

0 引 言

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

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

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

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

1 相關方法

1.1 問題描述

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

(1)

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

(2)

1.2 誘導稀疏

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

(3)

s.t.M≥0,N≥0

1.3 核化框架與核選擇

(4)

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

(5)

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

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

(a) σ2=103.5

(b) σ2=1010

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

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

(6)

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

1.4 基于特征向量的核選擇

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

(7)

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

(8)

s.t.VVT=IQ

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

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

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

(9)

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

(10)

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

(11)

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

2 本文算法

2.1 非凸性

2.2 凸函數的差分算法

(12)

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

(13)

松弛目標函數可以表示為:

(14)

(15)

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

(16)

(17)

因此,在第p+1次迭代中迭代地重新評估式(13)中的仿射優化。總體算法在算法1中進行概述。

算法1基于核協方差矩陣的無監督數據聚類算法

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 實驗與結果分析

3.1 綜合示例

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

(18)

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

(a) 6個輸入核

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

3.2 對比設置

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

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

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

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

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

3.3 活動檢測

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

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

圖3 UniMiB數據集的準確率比較的箱形圖

3.4 高光譜圖像

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

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

(a) P=100

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

3.5 文檔聚類

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

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

圖5 文件聚類數據集的準確率箱形圖

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

3.6 計算成本分析

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

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

4 結 語

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

(1) 本文算法針對不同的數據集均能表現出較好的聚類性能,驗證了算法對于數據集具有較強的泛化性能。針對非線性數據類之間相關性較弱等問題,本文方法能夠實現較好的聚類效果。

(2) 本文方法的聚類性能不僅較優于有監督以及其他幾種無監督算法的聚類性能,而且能夠解決監督訓練依賴性以及無監督參數選擇難的問題。在數據量稀疏或者先驗知識不足條件下,依舊能夠實現良好的聚類效果。

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