結合譜聚類的標記分布學習

王一賓，李田力，程玉勝

（1. 安慶師范大學 計算機與信息學院，安徽 安慶 246011; 2. 安徽省高校智能感知與計算重點實驗室，安徽 安慶 246011）

標記多義性學習作為機器學習領域中一個熱門方向，目前單標記學習與多標記學習已經較為成熟[1-2]。其中多標記學習是單標記學習的拓展，許多已有的研究成果也證實了多標記學習是一種有效的學習范式[3]。傳統的多標記學習雖然可以有效地處理實例和標記之間的關系，但卻將標記進行了簡單的定義，即存在為“1”不存在為“-1”，忽略了標記對實例的描述有著不同重要程度這一問題，因此并不適用于真實世界中某些實例，例如人的情感分析。人的情感可以通過面部表情來表達，而面部表情往往是一種混合了多種基本情緒的綜合表情，例如：驚訝和恐懼可能會同時出現，高興和感動可能會在同一時刻表現出來；這些基本情緒共同組成了一種情緒分布，在表達的情感中各自占有不同的比重。針對這類實例，Geng等[4]提出了一種標記分布學習范式(label distribution learning, LDL)。

基于此，為了更好地研究標記分布學習，研究者們提出了許多預測標記分布的算法。目前已有的算法主要分為3類：1)為了使用現有學習范式的相關公式定義，提出了將標記分布學習退化成單標記學習的PT-Bayes(problem transformation bayes)算法和PT-SVM(problem transformation support vector machine)算法[5]；2)將機器學習領域相關算法引入到標記分布學習中，以提高預測精度，如AA-KNN算法(algorithm adaptation k nearest neighbors)和AA-BP算法 (algorithm adaptation back propagation)[6]；3)為了切合標記分布學習自身的特性，而專門設計的CPNN(conditional probability neural network)算法[7]、SA-IIS(specialized algorithms improved iterative scaling)和SA-BFGS算法(specialized algorithms broyden fletcher goldfarb shanno)[8]。然而上述算法均未考慮樣本之間聯系，導致樣本數目過多，計算時間過長，甚至受異常樣本數據的影響使得預測精度下降。為了解決這種問題，本文考慮引入聚類方法處理。

聚類是一種無監督的處理數據并尋找內部關聯的分類方式[9]。目前聚類算法以及改進算法很多，如K-means和模糊聚類等[10-11]。聚類對簡化訓練模型效果優秀，其中，張敏靈[12]在多標記學習中對輸入空間進行K-means聚類，構建類屬屬性，然后訓練對應的分類模型；邵東恒等[13]將K-means引入標記分布學習，取得了較好的效果。但是這些傳統聚類算法依托于凸球形樣本空間，并且由于采取迭代更新，算法容易陷入局部最優，同時對數據適應性也不夠[14]。為了避免傳統聚類這些弊端導致算法可能不具備一般性[15]，故而引入譜聚類方法。譜聚類近年被引入了機器學習領域，并迅速成為熱點之一[16]。譜聚類算法中最經典的算法是Ng等[17]提出的NJW (Ng Jordan Weiss) 算法，NJW算法聚類效果也較為理想。

因此，為了解決以上傳統聚類的問題，將譜聚類中NJW算法引入到標記分布學習中，提出了一種結合譜聚類的標記分布學習算法(label distribution learning with spectral clustering，SC-LDL)。特征相似的樣本對應的標記分布理論上也是相似的，將這些聚類中心作為新的輸入空間，可以得到新的預測標記分布。相比于已有算法，本算法考慮了樣本之間的聯系，并且通過譜聚類預處理后的樣本數據有效減少了相似數據和異常數據對模型復雜度及預測精度的影響，相比于其他聚類算法既不限定樣本空間，也不需要迭代更新，同時本文通過在12個數據集上和5個經典算法進行對比實驗，證明了本文所提算法的有效性。

1 相關知識

1.1 譜聚類算法

譜聚類(spectral clustering)[18]是一種基于譜圖理論的算法，該算法是將數據聚類問題轉換成尋求圖的最優分割，它是一種點對聚類算法，并且適用于非凸數據[19]。譜聚類基本步驟可以描述為：通過高斯核函數計算原始數據集對應的相似矩陣W，進而得到一個度矩陣D，之后進行拉普拉斯變換，對轉換后的拉普拉斯矩陣L進行特征值分解，找出前m個特征值對應的特征向量，并將特征向量按列存儲得到新的特征矩陣，對新的特征矩陣進行K-means聚類處理[20]。譜聚類算法一經提出，其在數據降維、不規則數據聚類、圖像分割等方面獲得了廣泛的應用。

定義1 高斯核函數。定義一個d維的歐式空間P，其中有一點，p到某一中心點p0之間歐氏距離的單調函數記作，稱之為核函數。高斯核函數是一種常用的核函數，定義為

式中：p屬于歐式空間P；po為核函數中心；為函數的寬度參數。

定義2 相似矩陣。相似矩陣又稱親和矩陣，其與原矩陣特征值和特征向量相同，本文用W來表示，矩陣定義為

定義3 度矩陣。將W的每行元素相加，將相加后的數值用作對角元素構建對角矩陣，稱之為度矩陣，其中非對角元素取值為0。本文用D來表示度矩陣，其定義為

定義4 拉普拉斯矩陣。拉普拉斯矩陣主要應用在圖論中，是一種用來表示圖的矩陣，用L來表示，本文選取不規范拉普拉斯矩陣，其定義為

1.2 標記分布學習

標記分布學習是一種更加貼近真實世界的分布學習范式[21]。在傳統的多標記學習中，每一個實例對應一個標記集合，其中每一個標記的描述度為“1”或“-1”。當將這種描述度用一種類似于概率分布的形式來表示，即為標記分布。一個實例對應一個標記分布的學習過程，稱為標記分布學習[22]。真實世界中的實例所對應的標記多是有重要程度之分的，標記分布學習考慮這些重要程度，并且結合概率分布理論，將標記集合通過一種概率分布的形式來表達。

定義5 在標記分布學習中，每一個用來描述實例x的標記y用∑來 標注重要程度，不失一般性，可知，且。

2 結合譜聚類算法的標記分布學習算法的構造

2.1 譜聚類NJW算法

算法1 NJW算法

輸入 預設參數σ、k，其中k值選擇樣本數的20%(k為聚類數目)，標記分布訓練集S =

輸出 簇類中心C。

1)利用式(1)和式(2)計算相似矩陣W；

3)通過式(4)對度矩陣D進行拉普拉斯變換，得到變換后的矩陣L；

4)對矩陣L進行特征值分解；

5)升序排列；

6)得出前m個特征值對應的特征向量，按列存儲得到新的特征矩陣；

8)初始樣本點Si劃分為j個聚類，當且僅當樣本矩陣的第i行被劃分為第j聚類；

9)輸出聚類中心C ;

10)結束。

通過NJW算法，將原有標記分布集合劃分成q個不相關的簇類，其中簇類中心。

2.2 結合譜聚類算法的構造過程

當使用NJW算法對樣本數據聚類得到簇類中心C后，對應的標記分布劃分為相應簇類，對應新的分布矩陣，命名為。使用KNN分類器對中的樣本進行分類，通過式(5)計算，得到最終預測標記分布。式中：為中標記；k為示例的最近鄰居數；表示 S′中的索引集。

算法2 結合譜聚類N{JW的標記分}布學習算法

1)計算當前數據點和各個數據點的距離；

2)將該距離升序排列；

3)選擇和當前數據點最近的k個數據點；

4)判斷這k個數據點對應類別的出現頻率；

5)將最高出現頻率的這k個數據點對應類別作為當前數據點的預測分類；

6)結束。

3 實驗與結果分析

為了驗證本文SC-LDL算法有效性，選取5種經典算法在12個標準數據集上進行對比實驗。相關實驗結果還使用統計分析中Nemenyi檢驗來進一步表明算法有效性。其中Nemenyi檢驗是統計學中一種針對成組數據的有效檢驗方法。

3.1 標記分布學習評價指標

標記分布學習輸出的是一個標記分布，評價算法并不能簡單地用標記準確度多少來建立。根據Geng等在文獻[4]中提出的對標記分布學習評價算法的建議，本實驗采用了6種代表性的標記分布評價指標，分別為Chebyshev距離、Clark距離、Canberra距離、Kullback-Leibler(KL-div)散度、余弦相關系數(Cosine)和交叉相似度(Intersection)。其中，前4個指標是衡量距離的指標，后兩個是相似度指標。假設有c個標記的實例，真實標記分布為，預測標記分布為，各個指標的計算公式見表1，其中↓表示該指標越低越好，而↑表示該指標越高越好。

表1 標記分布評價指標Table 1 Evaluation measures for label distribution learning

3.2 實驗數據與環境描述

實驗數據：本文SC-LDL算法與5種常用經典算法進行對比，使用的12個數據集相關信息如表2。Yeast類都是在酵母菌上做實驗收集到的真實數據，每個數據集中含有2 465個酵母菌基因，每個基因由24個特征表達，標記對應不同的時間點，標記分布是不同的時間點上基因表達水平。s-JAFFE和SDU_3DFE數據集是兩個常用的表情數據集的拓展，其中s-JAFFE數據集中包含213張對10名日本女性模特進行人臉采集得到表情灰度圖，特征向量是由Local Binary Patterns方法抽取圖像特征獲得的，實例中的標記分布包含了開心、難過、驚訝、害怕、生氣和厭惡6種情感。SDU_3DFE數據集與s-JAFFE不同的是，它包含了2 500張表情灰度圖。Movie是用戶對電影評級的數據集。所有數據來自于Netflix，電影評級分5級，作為標記，用戶在各個級別上的評價比例作為標記分布存在，該數據集所有特征均來自于電影相關屬性的提取。

表2 數據集Table 2 Data sets

本文所有實驗均在Matlab2016a中運行，硬件環境 Intel? CoreTMi5-7500 3.40 GHz CPU，操作系統為Windows 10。

本文SC-LDL為了加強說服力，使用十折交叉驗證來進行實驗，即每次進行實驗時將數據集隨機分為10個部分，其中1份數據集用來測試，剩余9份作為訓練數據集，總計進行10次實驗，綜合10次實驗得到的評價指標結果求出平均值(mean)和標準差(std)。

3.3 實驗結果與分析

表3～8給出了本文算法與5種對比算法在12個數據集上的實驗對比結果，其中在每一個數據集上運行的最優結果用黑體表示；表格最后一行給出了6種算法的算法排位。算法排位越小，表示算法總體性能越好。

對以上6項評價指標結果進行統計檢驗，結果如圖1所示。

表3 Chebyshev(↓)指標結果Table 3 Results in Chebyshev (↓)

表4 Clark(↓)指標結果Table 4 Results in Clark (↓)

表5 Canberra (↓)指標結果Table 5 Results in Canberra (↓)

表6 Kullback-Leibler (↓)指標結果Table 6 Results in Kullback-Leibler (↓)

表7 Cosine (↑)指標結果Table 7 Results in Cosine (↑)

表8 Intersection (↑)指標結果Table 8 Results in Intersection (↑)

圖1 Nemenyi檢驗在6個標記分布學習算法上的CD圖Fig. 1 CD diagrams of the nemenyi test on six label distribution learning algorithms

實驗結果分析：表2～8給出了6種算法在12個標準數據集上的6項評價指標結果，圖1是實驗結果的統計分析圖。由表2～8分析可以得到：

1)在6項指標中，SC-LDL至少4項占優，其它2項相差也很小；

2)本實驗選擇的數據集中，9個數據集為酵母菌基因，2個表情數據集，1個影評，其中在酵母菌基因數據集中，SC-LDL效果均最優；

3)在樣本數少，特征數多的數據集(例如s-JAFFE)中，少部分結果略優；

4)在樣本數多，特征數很多的數據集(Movie)中，算法效果偏低；

5) 通過綜合算法排位分析，SC-LDL總是總體最優。

圖1統計分析Nemenyi檢驗結果均在顯著性水平為5%下得出。Nemenyi檢驗是當兩個算法的評價指標結果在平均排序中差值不大于臨界值(critical difference，CD)，則說明二者無顯著性差異，反之則有顯著性差異。該統計分析中有5個對比算法，12個數據集，其中CD=2.176 7。在圖1中，線段相連的算法表示二者的平均排序差值低于CD值，即無顯著性差異，各子圖中無顯著性差異的算法用線段連接，可以看出，SC-LDL與大部分算法有顯著性差異。這進一步說明SC-LDL具有更好的效果。

綜上所述，在考慮樣本相似性的前提下，將原始樣本轉化為圖模型進行降維，在大多數據集下提升了算法精度。這說明使用譜聚類是一種有效的方式。在大樣本高維特征下，由于相似度計算的復雜性及Movie數據集的稀疏性，導致算法精度偏低，這也說明了進一步研究降低相似度矩陣構造復雜性的必要性。

4 結束語

譜聚類在圖像分割領域取得了較大成就，將譜聚類引入標記分布學習是一個大膽的嘗試。實驗結果表明是有效的。本文提出的結合譜聚類的標記分布學習算法SC-LDL，繼承了標記分布學習和譜聚類的優點，考慮數據樣本之間的聯系，對原始數據降維處理，減少了原有標記分布學習計算復雜度。對比現有主流算法，實驗結果表明，經過約簡的數據建立概率分布模型預測未知樣本的標記分布精度更高，假設統計檢驗也證明了算法的有效性。

雖然譜聚類效果理想，但是在高維樣本下計算卻變得復雜，如何解決譜聚類在高維下計算復雜問題，將是未來研究重點方向。