判別多維標度特征學習

唐海濤，王紅軍*，李天瑞

（1.西南交通大學 計算機與人工智能學院，成都 611756；2.綜合交通大數據應用技術國家工程實驗室（西南交通大學），成都 611756）

0 引言

許多實際應用中獲取到的數據通常具有很高的維度，如絕大多數的圖片數據、文本數據和視頻數據。高維數據中的冗余信息不僅會降低后續機器學習任務的性能，還會使后續機器學習任務花費更多算力和內存來處理這些數據，即維度災難［1］。因此，利用特征學習或降維的方式，通過原始數據得到一個好的低維數據表示成為了許多學者的研究對象。在特征學習的過程中，低維的特征表示在消除原始數據冗余和噪聲信息的同時，還要盡可能保留原始數據內在結構。特征學習還有其他許多的應用，包括信息檢索［2］以及聚類［3］。

在特征學習中，根據學習過程中是否使用數據的標注信息分為監督、半監督以及無監督的特征學習方法。經典的無監督特征學習方法有主成分分析（Principal Component Analysis，PCA）［4］，它的核心思想是尋找一個正交的投影矩陣，使投影后的數據方差最大。半監督方法有半監督降維（Semi-Supervised Dimensionality Reduction，SSDR）［5］，它的原理是利用成對約束使低維數據表示更具有判別性。線性判別分析（Linear Discriminant Analysis，LDA）［6］是一種經典的有監督特征學習方法，它的思路是尋找一個正交的投影矩陣，使投影后同類中的樣本盡可能接近，不同類別的樣本盡可能遠離。

另一種劃分方式是線性和非線性的特征學習。PCA 和LDA 都屬于線性的特征學習，優勢在于計算快速，并且當有新樣本到來時，可以通過投影矩陣快速計算出新樣本的數據表示。與PCA 和LDA 不同的是，基于流形學習的非線性特征學習則是讓低維的數據表示盡可能保留原始數據的局部拓撲結構，比如局部線性嵌入（Locally Linear Embedding，LLE）［7］，該方法先學習到原始空間中每個樣本與鄰居間的局部線性關系，然后讓數據的低維嵌入盡可能保留在原始空間中學習到的局部線性關系。多維標度法（MultiDimensional Scaling，MDS）［8］則更看重樣本間的非相似度，該方法需要先得到樣本的非相似度矩陣，然后尋找一個能夠盡可能保持原始樣本非相似度的低維嵌入。拉普拉斯特征映射（Laplacian Eigenmaps，LE）［9］也是流形學習的代表方法之一，它通過圖的拉普拉斯矩陣使得原始空間中相近的樣本在低維嵌入后也保持相近。非線性特征學習能夠很好地發現數據內部潛在的流形結構，但是面臨新樣本問題［10］。也有不少算法在投影過程中盡可能保持局部拓撲結構，比如局部保持投影（Locality Preserving Projection，LPP）［11］和近鄰 保持嵌 入（Neighborhood Preserving Embedding，NPE）［12］，就是分別在LE 和LLE 的基礎上增加了投影矩陣。

本文提出了一種基于多維標度法的無監督判別性特征學習方法——判別多維標度模型（Discriminative MultiDimensional Scaling model，DMDS）。該方法一方面使相似度低的樣本在低維嵌入中遠離，另一方面讓相似度高的樣本在低維嵌入中盡可能靠近其簇中心，從而使學習到的低維數據表示更具有判別性。該方法使用迭代更新算法求解，并且在12 個公開數據集進行對比實驗。結果表明，經過該方法學習到的特征相較于原始空間和傳統多維標度法［13］更具判別性。本文的主要工作包括：

1）提出了DMDS 及其對應的目標公式，該目標公式體現了所學習特征在保留拓撲性的同時能增強判別性；DMDS 能在學習低維數據表示的同時發現簇結構，并使同簇的低維數據表示更接近。

2）使用迭代優化方法近似求解目標函數，并根據推理過程設計了相應的算法。

3）在12 個公開數據集上進行實驗，評價指標采用聚類平均準確率和平均純度，實驗結果表明DMDS 得到的低維嵌入更具有判別性。

1 相關工作

為了更清晰地了解公式的物理意義，表1 先總結了本文所使用的不同符號的含義。

表1 符號說明Tab.1 Symbol notations

1.1 多維度標度法

給定原始數據矩陣X=[x1，x2，…，xN]∈Rn×N，其中n和N分別表示原始樣本的維度和個數；學習到的低維數據表示Y=[y1，y2，…，yN]∈Rl×N，l表示低維數據表示的維度。MDS作為一種保持樣本距離的特征學習方法，它的損失函數［14］為：

其中：dij表示原始數據點xi和xj的距離表示對應的低維數據表示yi和yj的距離；S=[sij]∈RN×N是一個非負對稱的權重矩陣，sij越大，表示越希望接近dij。文獻［9］中給出了兩種權重構造方式：

1）熱核權重（heat kernel weight）：如果xi與xj或xj與xi近鄰，則sij=否則sij=0。其中t是一個實數。

2）0-1權重：如果xi與xj或xj與xi近鄰，則sij=1；否則sij=0。

式（1）中的MDS 是一種非線性的特征學習方法，得到的直接是低維數據表示Y，如果有新的數據到來，它對應的低維數據表示不能直接獲取。所以Webb［13］將投影矩陣融入MDS，提出了帶有投影矩陣的MDS（Projective MDS，PMDS），目標公式為：

其中：‖·‖2表示向量的二范數；W∈Rn×l表示投影矩陣，可以看到，Y直接由X投影而來。Webb［13］還通過讓同一個類別中低維數據表示距離更近來增加MDS 的判別性。基于此，Biswas 等［15-16］將MDS 應用到低分辨率的人臉識別，并通過同一人的人臉圖片的低維數據表示靠近的方式來增加MDS 的判別性。Yang 等［17］進一步考慮了不同人的人臉的低維數據表示距離應該更大，提出了更具有判別性的MDS。

1.2 模糊K均值聚類

高效的聚類算法包括K均值（K-Means，KM）算法［18］、近鄰傳播聚類（Affinity Propagation，AP）算法［19］以及密度峰值聚類（Density Peak，DP）算法［20］等。隨著模糊集理論的提出和完善，模糊聚類［21-22］被提出。模糊聚類能夠給出樣本與簇的隸屬程度，模糊K均值（FuzzyK-Means，FKM）的目標公式是：

其中：C表示簇的個數；U=[uik]∈RN×C是隸屬度矩陣，uik表示xi與第k個簇的隸屬度；V=[v1，v2，…，vC]是簇中心矩陣，m≥1 表示模糊指數權重。為了提高聚類算法對于高維數據的性能，不少學者將特征學習融入聚類算法，讓聚類算法在低維嵌入的過程中發現好的簇結構。比如Hou 等［23］將PCA與K均值結合，讓K均值在PCA 學習過程中進行聚類，兩者相互影響，從而找到更好的簇結構；Li 等［24］將非負矩陣分解（Non-negative Matrix Factorization，NMF）與K均值結合，在NMF 得到的低維數據表示中進行聚類；Nie 等［25］將PCA 融入FKM，同樣在PCA 得到的低維數據表示完成聚類。

2 DMDS

2.1 模型目標函數

在1.1 節詳細介紹了MDS，為了增強其特征學習的判別性，不同學者都使用了標簽信息進行監督或者半監督學習，但很多時候獲取標簽信息比較困難。本文采用無監督學習的思想來增加MDS 判別性。DMDS 目標函數如下：

其中：E1表示特征學習過程中盡量保持原有數據的拓撲結構，同時E2期望在學習過程中增加學習到的特征的判別性；α和β分別表示E1和E2的權重。

在式（4）中，如果α取值很小，此時會盡可能讓低維數據表示非常靠近；而如果β取值很小，此時將盡可能讓低維嵌入保持原始數據的距離。即式（4）的目標公式體現了一方面期望保持樣本的原始拓撲信息，另一方面期望同簇樣本靠近簇中心，兩者相互影響以學習到判別性的數據表示。值得注意的是權重矩陣S，傳統的MDS 在特征學習過程中是盡可能保持每個樣本與鄰居的距離；而在DMDS 中，更看重每個樣本距其較遠的樣本，也就是盡可能使低維數據表示保持每個樣本與距其較遠的樣本的距離，并且通過第二項E2使得低維數據表示中每個樣本與其簇中心靠近，從而增加了低維數據表示的判別性。具體而言，權重矩陣構造方式為：

1）改進熱核權重：如果xi與xj或xj與xi近鄰，則sij=1 -；否則sij=1。其中參數t是一個大于0實數。

2）改進0-1 權重：如果xi與xj或xj與xi近鄰，則sij=0；否則sij=1。

2.2 模型推理

式（4）中的目標函數要求解的參數是投影矩陣W、隸屬度矩陣U和簇中心矩陣V，由于無法直接得到這三個矩陣的閉式解，故本文采用迭代的方式求解。

1）固定U和V，更新W。此時式（5）是僅關于W的函數：

可以采用迭代優化算法（Iterative Majorization Algorithm，IMA）［8，13］優化式（5）。此時，構造的輔助函數是σ(W，Z)，定義為：

其中(·)-1表示矩陣的Moore-Penrose 廣義逆。

2）固定W和V，更新U。由于式（4）中E1不含有U，所以只需考慮E2，此時是一個僅關于U的函數：

采用拉格朗日乘子法［26］：

3）固定W和U，更新V。與步驟2）類似，有：

對式（16）求關于vk的梯度并使其為0，即：

2.3 算法描述

根據2.2 節DMDS 的推理過程，算法1 給出了DMDS 算法的整體流程。

算法1 DMDS 算法。

計算矩陣A的時間復雜度為O(n2N+nN2)；與矩陣A類似的是，計算矩陣D（Z）的時間復雜度也是O(n2N+nN2)；一個n×n的對稱矩陣的Moore-Penrose 逆可以通過對它進行奇異值分解來得到，奇異值分解的時間復雜度為O(n3)［27］；所以更新一次W的時間復雜度為O(nN2+n2N+n3)。更新一次隸屬度矩陣U的時間復雜度為O(NC2l)。更新一次矩陣V的時間復雜度為O(NCl)。則DMDS 算法的時間復雜度為：O(T(nN2+n2N+n3+NC2l))，其中T為最大迭代次數。

3 實驗與結果分析

3.1 數據集

為驗證DMDS 的性能，在由微軟亞洲研究院公開的多媒體數據 集（MicroSoft Research Asia MultiMedia，MSRAMM）［28］和UCI 機器學習數據集上進行實驗。MSRA-MM 數據集包括兩個子數據集：圖像數據集和視頻數據集。其中圖像數據集包括68 個類別，共計65 433 張圖片，每個類別大約有1 000 張。表2 總結了所使用的12 個數據集，前10 個數據集來源于MSRA-MM；最后2 個數據集來源于UCI 機器學習數據集，QSAR_AR 是指QSAR androgen receptor 數據集。

表2 實驗數據集Tab.2 Experimental datasets

3.2 評價指標

實驗使用了聚類算法的常用兩個指標：準確率［23］和純度［29］，并使用Friedman 統計量［30］來進行整體評估。準確率和純度的取值都是[0，1]，并且值越大，代表聚類效果越好。

準確率的計算公式：

其中：N表示樣本點的個數；map（·）是一個將簇索引映射到類別標簽的函數，一般通過匈牙利算法求得；li和ri分別表示樣本點xi的類別標簽和簇索引；δ(a，b)是一個函數，當a=b時，函數值為1，否則為0。

純度定義為：

其中：N表示樣本點數；C表示簇數；k表示簇索引；q是類別數，一般而言，q與C相等表示第k個簇中類標簽為r的樣本數。

Friedman 統計量是一種非參數測試的統計方法，用于評估一組算法在不同數據集上性能的整體差異。Friedman 統計量需要先得到每個算法在同一個數據集上性能的排序，性能最好的算法排序為1，次好的算法排序為2，以此類推可以得到所有算法的排序，如果有相同的性能，則取平均排序值。具體而言，Friedman 統計量定義為：

其中：a表示數據集的個數，b表示算法的個數；Rj=表示第j個算法在第i個數據集上的排序值，可以看出Rj表示的是第j個算法在所有數據集上的平均排序值。服從自由度為b-1 的卡方分布（Chi-square Distribution）。原始Friedman 統計量檢驗結果相對保守，一般使用式（22）所示的方式進行評估：

FF是自由度為b-1 和(b-1)(a-1)的F 分布，通過查表可計算其p值，基于p值對算法性能進行評估。

3.3 實驗設置

為了驗證DMDS 的特征學習性能，本文采用了對比實驗的方法，即分別對原始的數據表示、PMDS［13］算法得到的低維數據表示和本文提出的DMDS 算法得到的低維數據表示進行多種聚類實驗；如果數據表示更具有判別性，那么聚類效果就更好。為了實驗的公平性，特征學習算法PMDS 和DMDS 的低維表示的維度都是原始數據維度的1/10；每個聚類算法在不同數據表示上配置的參數一樣，簇個數設置為數據集類別數，并且每個聚類算法對同一個數據集都重復運行10 次，然后取10 次結果的均值作為最終結果，以降低實驗結果的偶 然性差 異。選擇的聚類算法包括KM［18］、AP［19］和DP［20］算法。

對于PMDS 算法，其目標公式中的權重矩陣S使用熱核權重，熱核權重中使用的近鄰關系是K近鄰算法，即如果xi是xj的K近鄰或者xj是xi的K近鄰，則xi與xj具有近鄰關系，其中K取樣本總數的1/10；熱核權重的t=100；距離采用的是樣本間的歐氏距離。

對于DMDS 算法，權重矩陣S使用的改進熱核權重，改進熱核權重中使用的近鄰關系也是K近鄰算法，其中K取樣本總數的9/10（由改進熱核權重的定義可知，更希望保留每個樣本距離其最遠的總樣本1/10 的樣本的距離）；熱核權重的t=100；距離采用的是樣本間的歐氏距離；模糊指數權重為2。在前10個數據 集中，α和β分 別取1 和1 000；對于CNAE-9 數據集α和β分別取1 和100；QSAR_AR 數據集α和β分別取1 和5 000。

3.4 實驗結果

3.4.1 判別性實驗結果與分析

表3 和表4 分別給出了12 個數據集在不同數據表示下分別通過KM、AP 和DP 聚類的平均準確率和平均純度的結果。表3 中，列KM、AP 和DP 是三種聚類算法在原始數據表示上的聚類準確率；PMDS-KM、PMDS-AP 和PMDS-DP 是三種聚類算法在經過PMDS 算法得到的低維數據表示上聚類的準確率；DMDS-KM、DMDS-AP 和DMDS-DP 是三種聚類算法在經過DMDS 算法得到的低維數據表示上聚類的準確率；Avg 表 示KM、AP 和DP 的均值；PMDS-Avg 是PMDS-KM、PMDS-AP 和PMDS-DP 的均值；類似地，DMDS-Avg 是DMDSKM、DMDS-AP 和DMDS-DP 的均值。表4 的表頭含義與表3類似，只是表格中數據是平均純度。

表3 不同數據表示下的平均聚類準確率Tab.3 Average clustering accuracy under different data representations

表4 不同數據表示下的平均聚類純度Tab.4 Average clustering purity under different data representations

從表3 可以看出，在這12 個數據集中，準確率最高的模型有10 個是在經過DMDS 特征學習的數據表示上（表格中的加粗數據），有2 個在原始數據表示上，這說明DMDS 能夠提高數據表示的判別性。而且對于同一個聚類算法而言，在DMDS 算法得到的數據表示上表現出來的性能絕大多數時候都優于原始數據表示和PMDS 的數據表示，這也進一步說明了經過DMDS 算法得到的數據表示能夠提高后續機器學習任務的性能。另外，從平均準確率來看（即表3 的最后三列），有11 個最高的平均準確率在DMDS 算法的特征表示上，有1 個在PMDS 算法的數據表示上，這也說明了經過DMDS 特征學習算法后得到數據表示更有利于后續機器學習的性能。

然后用Friedman 統計量來評估模型整體的性能。根據表3 最后3 列可以得出每個數據集中不同指標的排序值，比如對于第一個數據集而言，Avg、PMDS-Avg 和DMDS-Avg 的排序值分別為2、3 和1。然后可以得出在12 個數據集上Avg、PMDS-Avg 和DMDS-Avg 的平均排序值分別為2.583 3、2.333 3 和1.083 3。根據平均排序值可計算出Friedman 統計量≈15.500 0，則Iman-Davenport 為FF≈20.058 8。由于數據集有12 個，有3 種不同數據表示，所以FF服從自由度為3 -1=2 和(12 -1)(3 -1)=22 的F 分布。由F(2，22)分布可以計算p值為1.100 × 10-5，所以在高顯著性水平下拒絕原假設，即綜合評價DMDS 算法優于PMDS 算法，經過DMDS 算法得到的數據表示比PMDS 得到的數據表示和原始數據表示更具有判別性。

表4 列出了在不同數據表示上聚類結果的平均純度。可以看出，有7 個最高純度在DMDS 的數據表示上；3 個最高純度相等；2 個最高純度在原始數據表示上。總體而言在DMDS 上的聚類性能優于PMDS 和原始空間。另外，從表4的三個平均純度列來看，也是大部分最高純度位于DMDS 的數據表示上，這也說明DMDS 的有效性。

同樣，用Friedman 統計量來評估模型整體的性能。根據表4 最后3 列可得出Avg、PMDS-Avg 和DMDS-Avg 的平均排序值分別為2.250 0、2.333 3 和1.416 7。可計算出Friedman統計量為≈6.166 7，則Iman-Davenport 為FF≈3.803 7。由F(2，22)分布可以計算p值為0.038 1，所以在較高顯著性水平下拒絕原假設，即綜合評價DMDS 算法優于PMDS 和原始空間。

從準確率和純度綜合而言，DMDS 得到的數據表示相較于原始數據表示和PMDS 得到的數據表示對于后續的聚類算法都有著更好的性能，能夠學習到更具有判別性的特征。

3.4.2 參數敏感度分析

從DMDS 的目標函數式（4）可知，DMDS 通過參數α和β權衡新的數據表示中保持原始空間樣本拓撲結構和同簇樣本靠近其簇中心的程度，所以本節將討論不同的α和β之間的比重關系對于特征學習性能的影響結果。

對于每個數據集，在不同的β與α的比值（記為β/α）下分別通過DMDS 學習到新的數據表示，然后通過KM、AP 和DP三種聚類算法進行聚類，根據聚類結果計算出準確率和純度，以三種聚類算法的平均準確率和平均純度作為最終結果。β/α選取的比值為{10-1，101，102，103，104}。

圖1 給出了12 個數據集的參數敏感度結果。可以看出，隨著β/α的比值變化，準確率有明顯的變化，純度變化幅度較 小。對 于voituretuning、border、bicycle、building、banner、wallpaper2、banana 以及bus 這7 個數據集，在β/α為103取得了較好的結果；而對于CNAE-9 數據集，則是在β/α為10-1取得了較好的結果；并且都隨著β/α比值的增大性能開始下降。這也說明剛開始β/α比值不是很大時，新的數據表示一方面較好地保留了原始樣本的拓撲信息，另一方面同簇的樣本更加緊湊，從而能夠較好地提高判別性并提高聚類性能。而當β/α比值很大時，此時同簇樣本很緊湊以致于原始樣本的拓撲信息有了較大的損失，導致性能開始下降。綜合而言，在β/α為103附近時，能夠達到一個較好的平衡。

圖1 DMDS在12個數據集上在不同β與α的比值下的平均準確率和平均純度對比Fig.1 Average clustering accuracy and purity comparison of DMDS on 12 datasets with different ratios between β and α

3.4.3 算法運行時間對比

2.3節已經詳細分析了DMDS 算法的時間復雜度，為了更直觀地表示DMDS 算法與PMDS 算法時間復雜度的差異性，圖2 給出了它們迭代500 次所需的時間，可以看出DMDS算法相較于PMDS 算法需要更多的時間。

圖2 DMDS與PMDS運行時間的對比Fig.2 Running time comparison of DMDS and PMDS

4 結語

本文提出了一種判別多維標度法的特征學習模型DMDS，該模型加強了映射后的數據的判別性，這對后續的數據類別劃分尤為重要，從數據內在的特性上提高了數據可劃分性。將無監督學習的思想融入多維標度法，通過模糊K均值聚類能夠自動發現數據中的簇結構，使得在MDS 學習低維數據表示的過程中，同簇中的樣本更加靠近簇中心，原始距離較遠的樣本遠離，從而使學習到的數據表示更具有判別性。本文還使用了一種迭代更新的方法求解目標公式，在公開數據集上進行實驗。實驗結果表明，DMDS 能夠學習到更具有判別性的特征，從而提高后續機器學習任務的性能。

從3.4.2 節可以看出DMDS 算法受到超參數α和β的影響比較大，所以在未來的工作中，將致力于減少算法中的超參數，或者讓超參數能夠自動適應數據，從而進一步提高算法的性能。此外，也將研究如何使用部分監督信息（如樣本成對約束信息）來進一步提高DMDS 學習的特征的判別性。