面向不確定數(shù)據(jù)的序數(shù)回歸算法

李 晰，肖燕珊+，劉 波

(1.廣東工業(yè)大學 計算機學院，廣東 廣州 510006； 2.廣東工業(yè)大學 自動化學院，廣東 廣州 510006)

0 引 言

序數(shù)回歸 (ordinal regression，OR)問題與傳統(tǒng)的多分類學習問題[1]的根本區(qū)別在于：不同分類結(jié)果之間是否具有順序性。序數(shù)回歸模型廣泛應用于不同的領(lǐng)域，例如協(xié)同過濾、信息檢索、信用評級和醫(yī)學研究等。

為了提高序數(shù)回歸模型分類效果，本文在支持向量有序回歸的基礎(chǔ)上做了相關(guān)改進。通過本文所提出的面向不確定數(shù)據(jù)的支持向量機序數(shù)回歸模型(support vector ordinal regression based on uncertain data， USVOR)，可以減少不確定信息對序數(shù)回歸模型的影響，提高模型的魯棒性。本文的主要貢獻有3個方面：

(1)通過建立不確定性數(shù)據(jù)的模型，減少外界環(huán)境產(chǎn)生的不確定數(shù)據(jù)對序數(shù)回歸模型的影響。

(2)把不確定數(shù)據(jù)模型融合到序數(shù)回歸算法中，設(shè)計面向不確定數(shù)據(jù)的支持向量機序數(shù)回歸模型，并給出求解方法。

(3)在真實數(shù)據(jù)集的實驗結(jié)果表明，相比現(xiàn)有的序數(shù)回歸算法，我們算法具有更好的魯棒性。

1 相關(guān)工作

根據(jù)研究人員的不同構(gòu)建方式，本文可將現(xiàn)有的序數(shù)回歸分為三大類：

(1)樸素方法，將序數(shù)回歸問題作為標準的分類問題或傳統(tǒng)的回歸問題，并結(jié)合機器學習算法來提高序數(shù)回歸的性能。Xiao等[2]提出了基于支持向量機 (support vector machine， SVM)和多示例學習的方法來處理多分類問題，其中的標簽按順序進行排列，數(shù)據(jù)采用的是多實例的形式。李亞克等[3]通過大量離散樣本來構(gòu)建緩變類內(nèi)散度矩陣，從而獲取樣本數(shù)據(jù)中準確的時間序列，基于有序條件的約束和線性判別規(guī)則獲取最佳的映射，進而可以訓練得到有序數(shù)據(jù)。馬闖等[4]也引入有序信息，并基于最小平方回歸的方法對序數(shù)回歸函數(shù)中的標號改造來擴大分類間隔。其中，序數(shù)回歸中的樸素方法可結(jié)合機器學習算法來訓練模型，目前結(jié)合相關(guān)的機器學習主要有最小二乘法回歸、回歸樹、支持向量機等內(nèi)容。

(2)有序二分類法，即將基于序數(shù)目標變量分解成為多個二元變量，然后由單個模型或多個模型對有序信息預測最終的分類結(jié)果，有序二分類方法強調(diào)了基于有序選擇背后的潛在變量的方法與基于定義良好模式的概率分布的方法。曾慶田等[5]基于頻繁模式挖掘的方法，利用K-L散度值來提取最有區(qū)分能力的頻繁模式，并對將這兩種方法進行特征組合，進而來提取序數(shù)回歸中最有辨識能力的特征，從而提升序數(shù)回歸模型的訓練效果。Yldrm等[6]考慮到數(shù)據(jù)集中的目標屬性值是具有固有順序的，提出了一種新的集成的有序分類方法(ensemble-based ordinal classifcation，EBOC)，該方法結(jié)合了裝袋算法和提升算法，用于解決交通運輸部門中有序分類的問題，并且在準確性方面對所提出的EBOC方法與結(jié)合樹的分類算法(例如C4.5決策樹、隨機樹和REP樹)等傳統(tǒng)有序分類器進行比較。結(jié)果表明 EBOC方法比傳統(tǒng)的序數(shù)回歸方法能夠更充分挖掘排序信息和運用集成策略，從結(jié)果上體現(xiàn)出更為準確的分類精度。

(3)閾值模型，因為不同類別之間的距離并沒有預先定義，所以閾值模型必須學習不同類間的距離。閾值模型結(jié)合數(shù)學幾何的方法，其中對應的閾值是對預測值進行劃分，按照設(shè)定好的順序排列，預測變量的結(jié)果是從輸入空間投影到與每個類別相對應的一維空間的結(jié)果。Wang等[7]提出了非平行支持向量序數(shù)回歸，該方法學習多個非平行超平面，每個分類等級通過構(gòu)造定義好的超平面來進行分離，從而該模型可以達到并行學習的能力。Nguyen等[8]提出了一種用于序數(shù)分類的距離度量學習方法，將包含排序信息的局部三元約束合并到傳統(tǒng)的最大間隔距離度量學習方法。本文所提出的方法是基于第三種類型的序數(shù)回歸閾值模型，建立面向不確定數(shù)據(jù)的支持向量序數(shù)回歸閾值模型。

在過去的幾十年里，關(guān)于序數(shù)回歸的文獻增長得非?？?。雖然序數(shù)回歸取得了大量的成果，但是，在面向樣本不確定性的序數(shù)回歸工作還是比較少。在現(xiàn)實應用中，由于儀器不精確、采樣誤差和傳輸干擾等外界環(huán)境的原因，我們所得到的數(shù)據(jù)可能存在噪聲，我們稱之為樣本數(shù)據(jù)中的不確定性數(shù)據(jù)。目前，序數(shù)回歸工作主要針對分類標簽不確定和協(xié)同系統(tǒng)的決策不確定性。例如，Dopazo等[9]利用指定區(qū)間順序數(shù)據(jù)作為捕獲不確定和不完整信息的靈活方法好的神經(jīng)元組排序問題，該模型提出了兩階段的學習方法。第一階段學習了聚合偏好矩陣，該矩陣可從不確定的和可能相互沖突的信息中收集用戶偏好組的一種方法。在第二階段，通過學習優(yōu)先級向量，該向量是從基于模糊偏好慣性的性質(zhì)和圖論的聚合偏好矩陣中提取。該方法僅僅是考慮了用戶偏好的模糊性，并且放寬了數(shù)據(jù)的確定性和完整性的假設(shè)。Iannario等[10]提出了一種回歸模型的綜合框架，在序數(shù)模型的基礎(chǔ)上，結(jié)合離散均勻分布和二項式分布 (combination of a discrete uniform and a binomial distribution，CUB)，建立了新的有序反映機制，用來考慮決策中的不確定性，該序數(shù)回歸模型的綜合框架可發(fā)現(xiàn)數(shù)據(jù)隱藏的相似性和引入新的數(shù)據(jù)分布，并且可以觀察不同視角的數(shù)據(jù)，改進統(tǒng)計模型對序數(shù)回歸機制的解釋和預測。Tutz[11]擴展了序數(shù)回歸模型，優(yōu)化了傳統(tǒng)的CUB模型，他們考慮了偏好部分是由累積或相鄰類別決定的分布模型，展現(xiàn)了該模型學習的靈活性，并且引入了赤池信息準則(akaike information criterion，AIC)、貝葉斯信息準則(Bayesian information criterion，BIC)和預后指標對模型中的決策不確定性分量進行分析，可以使得優(yōu)化的CUB 模型表現(xiàn)出更好的擬合效果和分類性能?？偟膩碚f，目前序數(shù)回歸工作主要針對分類標簽不確定和協(xié)同系統(tǒng)的決策不確定性，而在樣本數(shù)據(jù)的不確定性方面的研究還比較少。

2 基本概念和符號

本文采用的顯式閾值約束的支持向量有序回歸模型的目標方程為

(1)

3 基于不確定數(shù)據(jù)的支持向量序數(shù)回歸

針對不確定數(shù)據(jù)的問題，本文提出了基于支持向量序數(shù)回歸模型來解決有序數(shù)據(jù)中的不確定數(shù)據(jù)的方法。由于不確定信息的影響，所有收集的數(shù)據(jù)x都可能與真實數(shù)據(jù)存在一定程度上的偏移，本文把這個偏移量表示為Δx。在現(xiàn)實世界中，由于缺乏任何先驗知識，我們難以獲得的數(shù)學分布。根據(jù)文獻[13]的研究，本文給每個樣本的偏移值Δx設(shè)置一個邊界，如下所示

(2)

其中， Δxji為樣本xji由于噪聲所產(chǎn)生的偏移，δji為該偏移Δxji模的最大值。

本文把樣本偏移量Δx加入訓練集樣本中，訓練集可表示為：T={xji+Δxji}， 其中， Δx?Rd。 從訓練集中可看出，xji為所收集的訓練樣本，由于外界噪聲的影響，訓練樣本可能存在一定的不確定信息。 Δxji為樣本xji由于噪聲所產(chǎn)生的偏移，它是一個未知量。把樣本xji轉(zhuǎn)化為xji+Δxji， 可以通過調(diào)整Δxji對樣本進行校正，令xji+Δxji更加接近真實的樣本值。

面向不確定數(shù)據(jù)的支持向量序數(shù)回歸模型如下

(3)

在式(3)中，需要優(yōu)化參數(shù)變量ω，bj， Δxji， 式(3)中的第三個約束條件是指所有不確定數(shù)據(jù)的偏移邊界值。

當Δxji固定時，式(3)變成一個關(guān)于ω、bj(j=1,…,r) 凸優(yōu)化問題。當參數(shù)ω、bj確定時，式(3)則變成關(guān)于Δxji的凸優(yōu)化問題。優(yōu)化定理[14]將雙凸優(yōu)化問題通過分解為兩個凸優(yōu)化問題來解決。本文通過以下兩個步驟來求解式(3)。

(1)固定Δxji， 計算分類器ω和bj

(4)

(5)

(6)

C+αji-γji=0

(7)

(8)

(9)

將式(6)～式(9)代入到拉格朗日函數(shù)(5)中，可得到對偶最優(yōu)化問題，如式(10)所示

(10)

通過上述方法，可以確定分類器中的ω和bj的值。在下一步中，我們固定ω和bj， 優(yōu)化Δxji的值。

(2)固定分類器ω和bj， 計算Δxji

(11)

(12)

按照文獻[14]的方法，根據(jù)原問題(4)中前兩個約束，可求解兩個不同的Δxji， 本文將這兩個不同的Δxji分別設(shè)為Δx1和Δx2。ω、bj

(13)

(14)

(15)

(16)

k=argmin(k1,k2)

(17)

通過固定ω和bj， 在問題(3)中， Δxji的最優(yōu)解是

Δxji=Δxk

(18)

算法1：面向不確定數(shù)據(jù)的支持向量機序數(shù)回歸算法

輸出：f(x)。

(1) 初始化t=0；

(2)t=t+1；

(3) 如果t=1， 初始化Δxji=0；

(5) 由式 (11) 和式 (12) 來確定Δxji的值；

(6) 根據(jù)式 (4) ～ 式 (9) 可計算得到ω、bj；

(7) 令Fval(t) 成為原問題 (3) 的決策函數(shù)值；

(8) 令Fmax={Fval(t-1),Fval(t)}；

本文是對支持向量有序回歸算法的改進，為了提高實際采集數(shù)據(jù)的準確性，把不確定數(shù)據(jù)引入到支持向量序數(shù)回歸中，用來解決現(xiàn)實的有序數(shù)據(jù)受外界干擾產(chǎn)生的擾動性的問題。整個面向不確定數(shù)據(jù)的序數(shù)回歸算法流程如圖1所示。

圖1 面向不確定數(shù)據(jù)的序數(shù)回歸算法流程

4 實驗結(jié)果與分析

為了研究本文提出的算法的有效性，本文在幾個真實的數(shù)據(jù)集上進行了實驗。所有的實驗都運行在一臺2.2 GHz的處理器和4 GB數(shù)字存儲器的筆記本電腦上。SVM的算法是基于LibSVM實現(xiàn)的。本次實驗的目的是：①評價面向不確定數(shù)據(jù)的支持向量序數(shù)回歸模型的有效性；②研究不確定的支持向量序數(shù)回歸模型對不同比例的數(shù)據(jù)噪聲的敏感性。

本文采用平均0-1誤差、平均絕對誤差和p值這3項性能指標對實驗結(jié)果進行分析：

(1)平均0-1誤差

(19)

(2)平均絕對誤差

(20)

(3)p值

在統(tǒng)計學中，p值是指假設(shè)零假設(shè)是正確的，獲得結(jié)果的概率至少與統(tǒng)計假設(shè)檢驗的觀察結(jié)果一樣極端。p值是由匹配好的t檢驗計算得到。在零假設(shè)檢驗下，當我們將USVOR與其它分類器比較時，這與測試0-1誤差分布沒有區(qū)別。

本文選擇了序數(shù)回歸研究領(lǐng)域中的基準數(shù)據(jù)集Amazon Sentiment 數(shù)據(jù)集、BIT-Vehicle 數(shù)據(jù)集和MSRA-MM數(shù)據(jù)集來對本文方法進行驗證。Amazon Sentiment 數(shù)據(jù)集源于亞馬遜網(wǎng)址Amazon.com，其中包含6類產(chǎn)品的評論：“Cameras”、“Laptops”、“Mobile phones”、“Tablets”、“TVs”和 “Video surveillance”。數(shù)據(jù)集評論數(shù)量分別為 7673 條、2473 條、4471 條、1049 條、2365 條和 2790 條。每條評論都有5個不同順序的評級標簽，分別是：{ 1、2、3、4、5 }，較高的評級顯示了更好的評論反饋。BIT-Vehicle數(shù)據(jù)集是由北京智能信息技術(shù)實驗室構(gòu)建，其中包括9850張車輛圖像用來測試本文的方法。有兩個相機在不同的時間和地點捕捉的像素大小分別為1600×1200和1920×1080的圖片。本文中所有車輛將分為3個類別：小型(轎車)、中型(SUV，小型客車，小型貨車)和大型(客車，卡車)。MSRA-MM 數(shù)據(jù)集是由微軟研究公司收集，其中包含68個查詢和19 436張圖像。圖像檢索查詢包括天使、鳥類、貓、狗、足球、樹等。對于每個輸入?yún)?shù)，它與相應查詢的相關(guān)性被標記為3個級別：非常相關(guān)、相關(guān)和無關(guān)。

為了驗證本方法的有效性和優(yōu)越性，本文方法與5種算法SVOR[12]、USVM[13]、SVM[15]、IUTSVM[16]、SUSVM[17]進行比較。SVOR根據(jù)“最大間隔”原則下對k類樣本進行排序。然而，SVOR僅僅考慮有序數(shù)據(jù)，忽略了不確定數(shù)據(jù)對有序數(shù)據(jù)的干擾影響。關(guān)于SVOR，它可以用來評估USVOR 處理不確定數(shù)據(jù)的能力；USVM 考慮了輸入數(shù)據(jù)被噪聲損壞。原始的 USVM 是基于二分類的方法，我們將 USVM 一對一的形式擴展為一對多的形式，因此USVM也能進行多分類學習； SVM 是從支持向量機擴展為多分類的支持向量機學習算法；IUTSVM是在解決Universum數(shù)據(jù)的孿生支持向量機(UTSVM)的基礎(chǔ)上，引入了一個正則化項解決了優(yōu)化矩陣中非奇異的問題，本文將其擴展為具有多分類學習的IUTSVM；SUSVM是將原問題中的二次規(guī)劃問題(QPPs)轉(zhuǎn)化為一對線性規(guī)劃問題，以此減少此算法的計算時間，本文在此基礎(chǔ)上推廣具有多分類學習能力的 SUSVM。不同方法的性能比較分別用平均0-1誤差和平均絕對誤差這兩種指標，見表1、表2。

表1 不同方法的平均0-1誤差

表1(續(xù))

表2 不同方法的平均絕對誤差

不同算法的平均0-1誤差、平均絕對誤差和p-value見表1、表2。p-value越小，表示算法表現(xiàn)越顯著穩(wěn)定。表1和表2顯示了AmazonSentiment數(shù)據(jù)集上的平均0-1誤差和平均絕對誤差。以表1中的“Mobile phone”數(shù)據(jù)集為例，USVOR在平均0-1誤差中有0.037至0.116的改進。從表2中可以看出，USVOR在Amazon Sentiment數(shù)據(jù)集中達到了最佳的分類性能。例如，在“Mobile phone”數(shù)據(jù)集中，USVOR在平均絕對誤差指標上相對于其它對比方法有了0.027至0.514的幅度提升。本文可以觀察到，USVOR的平均絕對誤差低于SVOR、SVM、IUTSVM和SUSVM。在SVM、IUTSVM和SUSVM中，有序信息被忽略，超平面通常是無序的和相交的。跟SVM、IUTSVM和SUSVM不同的是，USVOR不僅利用平行超平面來劃分數(shù)據(jù)，而且還將有序信息整合到模型中，通過對超平面的約束來劃分超平面之間的等級性。本文方法USVOR在平均0-1誤差和平均絕對誤差上都優(yōu)于其它5種算法，說明本文方法的有效性和優(yōu)越性，這是因為USVOR可以在迭代訓練階段通過更新不確定數(shù)據(jù)的計算來解決基于不確定數(shù)據(jù)的序數(shù)回歸學習問題。同時觀察到SVOR、USVM、IUTSVM和SUSVM的平均0-1誤差和平均絕對誤差低于只考慮多分類SVM的方法，因為SVOR方法考慮了數(shù)據(jù)回歸的有序性，但忽略了有序數(shù)據(jù)中的不確定信息，而USVM考慮了不確定信息的分類但卻忽略了數(shù)據(jù)回歸的有序性。IUTSVM和SUSVM對于摻雜了無關(guān)數(shù)據(jù)的有序數(shù)據(jù)進行分類，仍然存在不足。

本文研究了USVOR、SVOR、USVM、SVM、IUTSVM和SUSVM應對不同程度噪聲水平的敏感性。從圖2和圖3中可看出本文所提取的部分子數(shù)據(jù)集將噪聲百分比從20%增加到100%時的平均0-1誤差和平均絕對誤差的變化情況。很明顯該子數(shù)據(jù)集隨著噪聲比的增加，平均0-1誤差和平均絕對誤差而因此增加。其中，x軸表示添加到訓練集中的噪聲百分比，其中y軸在圖2表示平均0-1誤差，y軸在圖3中則表示為平均絕對誤差。隨著噪聲百分比的增加，訓練數(shù)據(jù)可能變得難以區(qū)分，訓練樣本受到不確定數(shù)據(jù)影響產(chǎn)生的矢量偏移程度也會因此而增大。與SVOR、USVM、SVM、IUTSVM和SUSVM相比，當噪聲百分比從20%和100%增加時，本文提出的方法USVOR仍然保持最低的平均0-1誤差和平均絕對誤差的水平，這表明USVOR考慮不確定數(shù)據(jù)時能夠有效抵抗噪聲的有效性。

圖2 不同數(shù)據(jù)集在不同程度噪聲下的平均0-1誤差

圖3 不同數(shù)據(jù)集在不同程度噪聲下的平均絕對誤差

5 結(jié)束語

本文基于不確定數(shù)據(jù)提出了支持向量序數(shù)回歸的方法。在支持向量序數(shù)回歸中引入了不確定數(shù)據(jù)，解決了有序數(shù)據(jù)中包含的不確定數(shù)據(jù)。由于現(xiàn)有的序數(shù)回歸模型沒有考慮有序數(shù)據(jù)中包含的不確定數(shù)據(jù)，在處理不確定信息時，模型的抗干擾性差和分類精度并不是很顯著。因此，本文將不確定數(shù)據(jù)考慮在序數(shù)回歸模型中，有利于提高模型的分類性能。本文采用平均0-1誤差和平均絕對誤差這兩種評價指標。通過對比實驗得出的評價指標，本文在平均0-1誤差和平均絕對誤差性能方面都優(yōu)于其它3種方法，說明本文方法的有效性和優(yōu)越性。未來的工作是在多視角數(shù)據(jù)中研究多視角中的無關(guān)信息的序數(shù)回歸問題。