李閃閃,田文泉，潘正高

(宿州學院 信息工程學院，安徽 宿州 234000)

大數(shù)據(jù)時代，信息的高速產生和發(fā)展，使得從海量、龐大的“大數(shù)據(jù)”信息中篩選和挖掘出有價值的數(shù)據(jù)信息成為了新的技術挑戰(zhàn).現(xiàn)實世界中事物的存在往往面臨多義性問題，即一個樣本可能不僅僅具備一個標記信息，這種情況下，多標記學習[1]的框架應運而生.在該框架下，為了更好地描述數(shù)據(jù)對象，需要收集豐富的特征數(shù)據(jù).與此同時，特征數(shù)據(jù)的大量增長也會伴隨許多冗余特征的產生，從而造成分類困難，增加模型的訓練時間.因此，對多標記數(shù)據(jù)的維度約簡處理有重要意義.

矩陣分解技術是一種常見的對復雜、高維度數(shù)據(jù)進行壓縮、去噪和降維的方法.傳統(tǒng)的矩陣分解是將一個維數(shù)較大的矩陣分解成V=WH的形式，而不在乎分解后的矩陣W和H中元素是正值還是負值.但是實際生活中，矩陣中負值元素不具備物理可解釋意義.比如，在圖像處理中，每一個非負數(shù)值都可以被解釋為與之對應的特征圖例.在文本統(tǒng)計中，每一個非負取值都可以表示一篇文章的主題.而如果這些元素為負值，就無從解釋了.

為了解決這一問題，Lee和Seung在《Nature》提出了一種有限定約束條件的非負矩陣分解(Non-negative Matrix Factorization，NMF)算法[1].該算法限定矩陣中所有元素均為非負值，規(guī)避了傳統(tǒng)的矩陣分解技術中存在可解釋性比較差的問題.NMF算法通過非負分解數(shù)據(jù)矩陣，將原始矩陣維數(shù)進行削減、壓縮，是處理大規(guī)模數(shù)據(jù)的一種有效手段.基于此，針對高維數(shù)據(jù)在多標記學習中帶來的分類困難等問題，本文提出一種基于NMF算法的多標記學習技術(A Multi-label Learning Method Based on NMF Algorithm，ML-NMF).首先，針對大規(guī)模的多標記數(shù)據(jù)集，本文采用NMF算法對其進行特征降維.其次，融合標記空間，訓練ELM極限學習機[2]模型，最后，將該模型下對未知標記的分類預測結果與其他常見的多標記特征降維方法進行對比，結果顯示本文算法是有效的.

1 NMF算法

1.1 NMF算法原理

已知有m個n維向量的數(shù)據(jù)矩陣X={x1,x2,…,xm}，NMF算法[3]的本質是把原始數(shù)據(jù)矩陣X用兩個非負矩陣W={w1,w2,…,wr}和H={h1,h2,…,hm}的乘積來近似表示，即：

Xn×m≈Wn×r·Hr×m，

(1)

其中，W被稱作基本矩陣，H被稱作系數(shù)矩陣，并且r遠小于n和m，這樣用H代替原始數(shù)據(jù)矩陣X便可以達到對原始矩陣X進行數(shù)據(jù)壓縮與降維處理的目的.

1.2 NMF算法求解

NMF算法[4]基本原則是將原高維空間的數(shù)據(jù)矩陣X投影到低維度的線性空間，用低維的矩陣H表示，因此，NMF算法本質是最小化原矩陣X與分解矩陣W和H的差異度，即轉化為公式(2)的優(yōu)化問題：

minf(W,H)
s.t.0≤W∈Rn×r,0≤H∈Rr×m，

(2)

其中f(W,H)是差異度函數(shù)，借助于Euclidean距離作為評判標準求得該公式的局部最優(yōu)解[5].算法具體步驟如下.

算法：基于Euclidean距離的非負矩陣分解；

輸入：數(shù)據(jù)特征矩陣X，迭代次數(shù)t；

輸出：非負分解矩陣W和H.

(1)隨機初始化非負矩陣W和H.

(2)對迭代次數(shù)t=1,2,…

(3) 輸出非負分解矩陣W和H.

2 多標記學習

2.1 問題定義

在多標簽學習中X表示標簽特征，X=Rp表示定義在實數(shù)域R上的p維樣本空間，Y={y1,y2,…,yq}表示標記空間.給定多標記數(shù)據(jù)集D={(xi,Yi)|1≤i≤n},其中每一個xi=[xi1,xi2,…,xip]表示數(shù)據(jù)集的第i個樣本，該樣本含有p個特征，而Yi=(yi1,yi2,…,yiq)表示與每個樣本xi對應的一組標記序列，并且滿足，Yi∈{-1,+1},如果樣本xi包含第k個標記，則yik=+1,否則yik=-1.多標記學習主要是通過訓練數(shù)據(jù)集D，獲得從原始輸入空間X到最終輸出空間的一個映射模型f:X→2Y.該模型滿足：當輸入待分類樣本xi∈X時，通過分類器f能夠預測得到屬于該樣本的類別標記集合f(x)?Y.

2.2 多標記學習評價指標

由于多標記數(shù)據(jù)結構的復雜性，傳統(tǒng)的單標記學習評價標準已經不能準確評判算法的好壞.因此，針對多標簽數(shù)據(jù)的評估指標被提出，其中常用的有平均查準率(Average Precision，AP)、覆蓋率(Coverage,CO)、漢明損失(Hamming Loss,HL)、一錯誤率(One-Error,OE)、排位損失(Ranking Loss,RL)[1]等，設有預測函數(shù)f(x,y)定義排序函數(shù)為rankf(x,y)，若給定多標記測試集S={(xi,yi)|1≤i≤P},具體描述如下：

平均查準率(Average Precision, AP)用于評估在樣本的預測標記序列中，排在前面的標記同時也是真實標記的情況.該指標值越大，分類效果越好，公式定義如下[1]：

(3)

覆蓋率(Coverage,CO)用于評估在樣本的預測標記序列中，找出全部樣本所含的標記類別至少需要多少個標記.該指標值越小，分類效果越好，公式定義如下[1]：

(4)

漢明損失(Hamming Loss,HL)用于評估預測標簽集合和實際標簽集合之間的差距情況.該指標值越小，分類效果越好，公式定義如下[1]：

(5)

排位損失(Ranking Loss,RL)用于評估無關標記的排在真實標記之前的比例情況.該指標值越小，算法性能越好，公式描述如下[1]：

(6)

一錯誤率(One-Error,OE)用于評估在樣本的預測標記排序中，排在前面單但是不屬于樣本的真實標記的情況.該指標值越小，分類效果越好，公式定義如下[1]：

(7)

3 基于NMF算法的多標記學習

3.1 數(shù)據(jù)形式化表示

假定現(xiàn)有X=Rp代表p維樣本空間，Y={y1,y2,…,yq}表示標記空間.對于給定的多標記數(shù)據(jù)集D={(xi,Yi)|1≤i≤n},其中xi=(xi1,xi2,…,xip)表示的是數(shù)據(jù)集中第i個樣本，并且每個樣本包含p個特征，而Yi=(yi1,yi2,…,yiq)表示與每個樣本xi對應的一組標記序列.基于此，本文實驗訓練數(shù)據(jù)集的特征矩陣和標簽矩陣分別描述為X=(x1,x2,…xn)T∈Rn×p和Y=(Y1,Y2,…Yn)T∈{+1,-1}n×q.

3.2 ML-NMF算法分析

本文利用非負矩陣分解算法能夠進行數(shù)據(jù)降維的特性，對于海量的多標記數(shù)據(jù)集進行處理，提出一種基于非負矩陣分解的多標記學習算法(ML-NMF).基本思路是：①輸入原始數(shù)據(jù)特征矩陣和標記矩陣相關信息，設置好相應參數(shù)以及需要選擇的特征數(shù)量；②使用NMF分解算法進行降維處理，獲取特征排序序列；③借助于ELM極限學習機進行特征映射，建立特征與標記的訓練模型.

ML-NMF算法的具體實現(xiàn)步驟如下.

算法：基于NMF算法的多標記學習;

輸入：原始數(shù)據(jù)特征矩陣X，標記矩陣Y，降維后的特征個數(shù)k;

輸出：降維的特征索引向量I.

(1) 隨機初始化特征空間矩陣X;

(2) 利用優(yōu)化公式迭代求解滿足條件的非負矩陣X′;

(3) 利用非負矩陣結構獲得特征排序的前k個特征;

(4) 輸出降維的特征索引向量I.

4 實驗及結果分析

4.1 實驗數(shù)據(jù)

為了分析算法的實驗性能，本文實驗共計選取6個公開基準多標記數(shù)據(jù)集：Birds、Emotion、Flags、Natural Scene、Scene和Recreation，數(shù)據(jù)集信息如表1所列.

表1 多標記數(shù)據(jù)集

所選數(shù)據(jù)集均是取自http://mulan.sourceforge.net/datasets.html.

4.2 實驗環(huán)境與實驗對比方案

實驗代碼均在Windows 10 、Matlab2016a 中運行，硬件環(huán)境為Intel i5-4200 CPU 8G 內存.為了分析算法的實驗性能，選擇5種典型評價指標，分別是：平均查準率(AP)、漢明損失(HL)、覆蓋率(CV)、一錯誤率(OE)和排位損失(RL)作為算法的性能評價指標.通過這5種評價指標來共同評價ML-KNN[6]、Rank-SVM[7]、ML-RBF[8]和ML-NMF 4種算法的性能，最終得出各算法的整體效能評估結果.如表2～6所列，用黑體突出標識，作為此實驗結果的最優(yōu)數(shù)值，采用統(tǒng)計分析的方法對各種算法進行排序.

4.3 實驗結果與穩(wěn)定性分析

表2～6分別給出在Birds、Emotion、Flags、Natural Scene、Scene和Recreation數(shù)據(jù)集上的算法實驗結果.各評價指標之后的向上“↑”代表值越大，實驗性能越優(yōu)；向下“↓”則代表值越小，實驗性能越優(yōu).

表2 漢明損失測試結果

表2基于漢明損失(HL)的評價結果顯示，本文提出的ML-NMF算法在6個數(shù)據(jù)集上的實驗結果均優(yōu)于其他3種算法；表3基于排位損失(RL)的評價指標可以看出NL-NMF算法也明顯優(yōu)于其他3種算法；表4基于一錯誤率(OE)的評價指標顯示，僅僅在Flags一個數(shù)據(jù)集上結果低于ML-RBF算法，但整體結果較優(yōu)；表5基于覆蓋率(CV)的評價指標，Rank-SVM也僅僅在Recreation這一個數(shù)據(jù)集上表現(xiàn)較好，其余數(shù)據(jù)集實驗結果均不及本文的ML-NMF算法；表6基于平均查準率(AP)的整體實驗結果也是優(yōu)于其他3種算法.總體分析，本文提出的ML-NMF算法在各個數(shù)據(jù)集實驗結果都要勝于其他算法，因此，本文提出的基于NMF的多標記學習是可行的.

表4 一錯誤率測試結果

表5 覆蓋率測試結果

表6 平均查準率測試結果

5 結語

本文介紹的基于NMF算法的多標記學習，首先采用NMF算法對標記數(shù)據(jù)集進行維度約簡，然后將約簡后的特征子集融合標記信息，訓練分類模型，預測未知標記.最終基于5種相同評價指標，在6種數(shù)據(jù)集上的實驗結果表明，本文提出的ML-NMF算法具有很好的分類效果.