基于GBDT的標記分布學習算法研究

王遠志，陸文成，田文泉，高 標

（安慶師范大學計算機與信息學院，安徽安慶246133）

標記是對樣本的描述與反映，傳統(tǒng)標記學習一般分為單標記學習和多標記學習，單標記學習是假定數據集中的每個樣本對應一個標記的學習范式，而多標記學習是將樣本對應多個標記的學習范式，且每個相關標記對于整個樣本是同等重要的[1]。多標記學習可以更好地處理標記域地不確定問題，能夠知道哪些標記描述樣本，卻不清楚這些標記如何描述樣本。但在實際問題中，需要更細致地了解標記對樣本的描述程度，而標記分布學習（LDL）則可以很好地處理這類需要了解標記分布強度的問題。Geng[2]等提出了標記分布思想概念，并設計了IIS-LDL算法并應用在自動年齡的估計上，獲取到更多的樣本信息，從而降低了由于年齡訓練數據稀缺帶來的風險。后來Geng等[3]規(guī)范化定義標記分布學習，設計相關算法，提出衡量算法效果的指標，建立了一套完整的標記分布學習框架。隨著不斷的研究與發(fā)展，標記分布學習在機器學習領域運用越來越廣泛[4]，對相關算法預測標記分布的準確度要求也越來越高，因此需要設計出預測結果更加理想的算法。

決策樹（Decision Tree）是很常用的機器學習方法，單個決策樹處理問題十分有限，通常采用集成學習的思想組合多算法或多分類器得出更理想的結果[5]。在以往研究中，決策樹算法能夠有效解決多標記學習的問題，如多標記模糊粗糙決策樹和基于標記相關特征的多標記決策樹算法[6]，通過改進Adaboost處理多標記數據的Adaboost.MH與Adaboost.MR算法[7]等。GBDT（Gradient Boost Decision Tree）是一種迭代的決策樹算法，能靈活處理各種類型的數據，適用于大多數回歸或分類問題，廣泛應用在科研和工業(yè)領域[8]。由于標記分布的數據集樣本特征較少，需要進行特征變換，相對于其他算法，GBDT能夠選擇出具有代表性的特征，避免無效特征的干擾，防止過擬化，是非常高效實用的算法。

因此，本文結合GBDT的特性，提出一種基于GBDT的標記分布學習算法GBDT-LDL。該算法是將現有樣本特征進行變換組合，生成新的組合特征以提高標記分布的準確程度。在實驗部分，采用PTBayes算法、AA-kNN算法、AA-BP算法和SA-IIS算法[9]與該算法做對比，實驗結果表明GBDT-LDL比其他算法更具優(yōu)越性。

1 標記分布學習

1.1 標記分布學習理論

令x表示標記樣本，y表示能夠代表x的標記，則定義dyx表示y描述樣本x的重要程度，該數值取值范圍是0到1，且越大越能代表樣本。所有標記的描述度構成一種類似概率分布的數據結構稱為標記分布，標注樣本學習的過程稱為標記分布學習[10]。作為一種新的學習范式，在一定條件下，單標記和多標記都可看作標記分布學習的特例，這使得標記分布學習更具泛化性，再運用合適的算法使標記分布學習在實際研究中更具廣泛性和實用性。標記學習算法的設計思想可分為3類：問題轉換、算法改造和專用算法。問題轉換（Problem Transformation）是將標記分布問題轉換為傳統(tǒng)學習范式處理，典型算法是PTBayes算法。算法改造（Algorithm Adaption）是通過改造某些機器學習算法來適應標記分布學習，典型算法有AA-kNN算法和AA-BP算法。專用算法（Specialized Algorithms）則是設計專門的算法更直接地解決標記分布問題，相關算法有SA-IIS算法。這些算法能有效提高標記分布學習的預測效果。

1.2 評價指標

標記分布學習的預測結果是各個標記的分布形式，類似于數理統(tǒng)計中的概率分布。因此可將衡量兩個概率分布之間相似度或距離大小的指標來評價標記分布預測結果的準確度[1]。即將樣本的標記分布預測結果和真實數據作比較，通過二者的距離或相似度大小來衡量算法的準確度。其中，二者距離越小或者相似度越大，兩個標記分布越接近，結果越好；反之距離越大或者相似度越小，得出的結果越差。本文選用了具有代表性的4個距離標準（Chebyshev距離、Clark距離、Canberra距離和Kullback-Leibler距離）和2個相似度標準（Cosine相似度和Intersection相似度）來作算法的評測指標。

2 結合GBDT的標記分布學習算法

2.1 GBDT算法

GBDT的核心是計算上一輪迭代的負梯度，往減少殘差(殘差指預測值與真實值的差值)的梯度方向上建立新的決策樹，通過不斷迭代改進來得到更準確的預測結果[11]。

輸入訓練集{(x1,y1),(x2,y2),…,(xN,yN)}，損失函數為L(y,f(x))。定義輪數為t=1,2,3,…,T。

對t輪第i個樣本計算殘差：

對回歸樹的每個葉子節(jié)點計算最小損失函數，得到最佳的葉子節(jié)點輸出值：

其中Rtj是第t棵決策樹對應葉子節(jié)點區(qū)域，j為樹的葉子節(jié)點個數，θ為初始常數，則本輪最終的算法模型：

上述是GBDT算法的基本框架，在每輪迭代中，擬合損失函數的負梯度，不斷改進從而得出最佳結果，以解決分類或回歸問題。

2.2 GBDT-LDL

本文提出GBDT-LDL算法，其原理是利用已有特征讓GBDT模型學習，以GBDT中決策樹的每個葉子節(jié)點對應新的特征，將特征向量取值為0或1。輸入的樣本點通過某棵決策樹中的一個葉子節(jié)點，則該葉子節(jié)點賦值為1，而該樹其他葉子節(jié)點為0[12]。GBDT所有樹的葉子節(jié)點總和將構成新的特征向量長度，利用此原理對特征進行變換與組合。算法主要過程是對于標記分布數據集，將原始數據集分為訓練集和測試集，其中訓練集分為訓練集1和訓練集2，首先將訓練集1通過GBDT進行特征學習，然后將訓練集1通過特征學習模型進行特征變換，對特征變換之后的特征進行歸一化處理，與訓練集2合并形成新的樣本特征數據集。將新的數據集通過GBDT 進行訓練，建立特征變換之后的標記分布GBDTLDL模型，通過對測試樣本的預測，可以得出準確的樣本標記分布。

3 實驗過程與分析

3.1 實驗數據描述

本文實驗總共采用了12組數據集，其中Yeast的9種數據集都是釀酒酵母的數據集，每組有2 465個酵母菌基因樣本，每個樣本有24個特征，記錄各個時間點的酵母菌基因表達水平為標記分布。s-JAFFE和s-BU_3DFE是有243個特征的人類表情數據集，以6種表情作標記，不同人對照片以6種表情作評分處理，然后以評分結果得出標記分布數據。Movie是7 755部電影的評分數據，1 869個特征，5種電影級別作為標記，以該級別人數占總人數比例得出標記分布。具體數據集如表1所示。

表1 實驗數據集

3.2 實驗方案及結果分析

本文以Windows 10為實驗平臺，Matlab 2016a為實驗環(huán)境。采用表1的12組標記分布數據集通過PT-Bayes、AA-KNN、AA-BP、SA-IIS 和本文的GBDT-LDL 5 種算法及6 項評價指標進行對比，實驗結果如表2到表7所示。其中，表2到表5代表實驗距離度量，數值越小越好；表6、表7代表實驗相似度距離度量，數值越大越好。最好的結果已加粗表示。再利用十折交叉驗證來測試算法準確性，將原數據集分為10份，輪流實驗，得出5種算法的平均值mean和方差sd，再以6個評測指標利用統(tǒng)計分析對比來檢驗算法。圖2表示5種算法在0.05顯著性水平下的Nemenyi檢驗結果，是按照表2到表7的數據結果以算法平均排名建立坐標軸，每個子圖橫坐標軸中從左至右算法效果依次降低，其中彩色線條連接表示算法之間沒有顯著差異。

表2 Chebyshev距離實驗結果↓

表3 Clark距離實驗結果↓

表4 Canberra距離實驗結果↓

續(xù)表4

表5 Kullback-Leibler距離實驗結果↓

表6 Cosine相似度實驗結果↑

表7 Intersection相似度實驗結果↑

續(xù)表7

每個算法對于其他算法有24種比較結果，由圖1可知：

①GBDT-LDL 算法在大部分評價指標上性能較優(yōu)，在37.5%的統(tǒng)計下與其他算法無顯著性差異。其中圖1（a）顯示，在Chebyshev 距離指標上，GBDT-LDL、AA-KNN 和SA-IIS 三者無顯著性差異。圖1（b）顯示，在Clark距離指標上，GBDT-LDL與AA-KNN相比無顯著性差異。圖1（c）顯示，在Canberra距離指標上，GBDT-LDL 與AA_KNN 相比無顯著性差異。圖1（d）顯示，在Canberra 距離指標上，GBDTLDL 優(yōu)于算法PT-Bayes。圖1（e）顯示，在 Kullback-Leibler相似度指標上，GBDT-LDL 與 AA-KNN 相比無顯著性差異。圖1（f）顯示，在Cosine 相似度指標上，GBDT-LDL 與AA-KNN 相比無顯著性差異。而GBDT-LDL在62.5%的水平下，在統(tǒng)計上對比其他算法效果更優(yōu)。

圖1 5種標記分布學習算法的Nemenyi檢驗CD圖

②AA-KNN算法在41.7%情況下在統(tǒng)計上優(yōu)于其他算法，在58.3%情況下與其他算法無顯著性差異。

③SA-IIS算法在20.8%情況下在統(tǒng)計上優(yōu)于其他算法，在79.2%情況下與其他算法無顯著性差異。

綜上所述，GBDT-LDL 算法性能最優(yōu)，以62.5%的統(tǒng)計水平優(yōu)于其他算法，其次AA-KNN 以41.7%情況下優(yōu)于其他算法，之后SA-IIS以20.8%情況下優(yōu)于其他算法，最后是AA-BP、PT-Bayes算法。

從不同數據集的數值中相比較可以看出，雖然GBDT-LDL在某些情況下對于其他算法沒有顯著差異，但整體上按效果由好到差排序是GBDT-LDL、AA-KNN、SA-IIS、AA-BP、PT-Bayes，而GBDT-LDL在各類數據集以及6項指標的實驗結果中比其他算法都具有優(yōu)勢，這說明本文算法比其他算法更加能夠描述整個標記分布，提高標記分布描述樣本的準確性，對標記分布學習在未來實際運用方面更具利用價值。

4 總 結

本文主要針對標記分布數據集特征較少的問題進行研究，基于GBDT對樣本進行學習，對特征進行變換組合，提出了一種結合GBDT模型的標記分布學習算法，算法對現有樣本特征進行特征變換組合，生成新的組合特征。實驗表明變換后的特征能夠更好地表示樣本數據，提高標記分布的預測準確率。

雖然將特征變換組合的方法在一定程度上提升了模型的預測精度，但與預期效果之間還存在一定差距。因此針對現有特征提出更加有效的組合變換方法是今后研究的重點。