基于三支決策的序列數(shù)據(jù)代價(jià)敏感分類算法

劉牧雷，徐菲菲

（上海電力學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 200090）

當(dāng)前，LSTM 作為深度學(xué)習(xí)的一種處理序列數(shù)據(jù)最為流行的解決方案，擁有著較傳統(tǒng)方案更加實(shí)用性強(qiáng)且準(zhǔn)確率高的特點(diǎn)[1-2]。但是，基于深度學(xué)習(xí)的代價(jià)敏感決策仍未得到主流的研究關(guān)注。當(dāng)前的研究重點(diǎn)多集中于如何更高效的獲得精確的整體準(zhǔn)確率。在有關(guān)于深度學(xué)習(xí)的代價(jià)敏感分類或決策問題上，當(dāng)前的算法常見解決方案多集中于通過對數(shù)據(jù)的預(yù)處理和運(yùn)行參數(shù)調(diào)整的方式來使分類器獲得對某一類代價(jià)敏感類別更高的關(guān)注從而實(shí)現(xiàn)減少整體的代價(jià)[3]。但是這種方法的缺點(diǎn)如前文所述。為了訓(xùn)練對高代價(jià)分類敏感的模型，篩選出的數(shù)據(jù)集將會面臨嚴(yán)重的數(shù)據(jù)不平衡問題。而無論是填充或者再平衡的方式，都會使原數(shù)據(jù)集的結(jié)構(gòu)改變[4]。其次，無論是對數(shù)據(jù)集的預(yù)處理還是對運(yùn)行參數(shù)或者模型結(jié)構(gòu)的調(diào)整，都與具體問題相關(guān)性較大[5-7]。對于不同的具體問題，數(shù)據(jù)清洗和參數(shù)調(diào)整或模型調(diào)整的優(yōu)劣與模型設(shè)計(jì)者的經(jīng)驗(yàn)與對問題的了解有著較大的關(guān)系。并且，對于不同的問題，相同的解決方案并不能保證穩(wěn)定的表現(xiàn)。在不同的數(shù)據(jù)集之間，相同的數(shù)據(jù)清洗和參數(shù)調(diào)整所帶來的模型上的改變影響是不同的。

基于此，本文提出的將三支決策運(yùn)用于深度學(xué)習(xí)模型能夠一定程度上解決上述問題。1) 三支決策算法的理論基礎(chǔ)為粗糙集理論，以分類置信度為基礎(chǔ)判斷決策或分類代價(jià)。從算法邏輯的角度，三支決策算法要求更高的全局分類的準(zhǔn)確性而不是對單獨(dú)高代價(jià)類的分類，此特點(diǎn)使得三支決策算法與更高的更廣泛的分類算法優(yōu)點(diǎn)相結(jié)合，在前置分類器不用做出改動或者調(diào)整的情況下降低決策的風(fēng)險(xiǎn)。2) 三支決策算法傾向于判斷單獨(dú)決策。因此，新改進(jìn)的算法將避免在正常預(yù)處理的前提下，將避免因平衡特殊分類類別而造成的數(shù)據(jù)重新擴(kuò)展或裁剪，從而進(jìn)一步影響數(shù)據(jù)平衡問題。綜上，結(jié)合三支決策的LSTM 模型可以在原先的深度模型的基礎(chǔ)上，進(jìn)一步增強(qiáng)模型在代價(jià)敏感問題上的表現(xiàn)。

1 相關(guān)工作

1.1 三支決策

三支決策[8]是Y.Y.Yao 由概率粗糙集理論提出的一種新決策思想。相較于傳統(tǒng)的“是，否”二支決策而言，三支決策提出了一種不同但是更合理的決策思想，即當(dāng)對象當(dāng)前提供的信息不足以支撐決策時(shí)，采用延遲決策，等待更多信息來完成最終決策。所以，三支決策可以規(guī)避分類信息不足時(shí)盲目決策造成的風(fēng)險(xiǎn)。

三支決策在進(jìn)行分類決策前，需對樣本進(jìn)行域的劃分。劃分的原理基于粗糙集理論。按照粗糙集的定義，根據(jù)元素x是否屬于概念A(yù)，x與A將分為3 種關(guān)系：x∈A,x∈ ?A,x∈BND(A)。由此，考慮一般分類問題，將元素x是否符合概念A(yù)作為分類標(biāo)準(zhǔn)，將可能會得到x∈BND(A) ， 即元素x屬于概念A(yù)的邊界域。由此，可得知決策粗糙集在 代價(jià)敏感分類問題上的整體思路。

在決策粗糙集公式化描述中，X是全集U的子集，狀態(tài)集合可以表示為 ?={X,?X}，X和 ?X分別表示屬于X和不屬于X。為了方便，子集和子集的狀態(tài)都使用X來表示。狀態(tài)X對應(yīng)的動作集合為 ∧={P,B,N} ， 其中P、B、N分別表示3種判定動作，即x∈POS(X)、x∈BND(X)、x∈NEG(X)。三支決策的損失函數(shù)由各個(gè)動作帶來的損失決定。如表1 所示，其中λPP、λBP、λNP表 示當(dāng)x屬于X時(shí)采取動作P、B、N產(chǎn)生的損失，λPN、λBN、λNN表示當(dāng)對象屬于 ?X時(shí)采取動作P、B、N時(shí)產(chǎn)生的損失。

表1 三支決策的損失函數(shù)Table 1 Loss function of 3WD

根據(jù)最小風(fēng)險(xiǎn)決策規(guī)則：

(P)當(dāng)Pr(X|[x])≥ α 時(shí)，x∈POS(X);

(B)當(dāng) β ＜Pr(X|[x])＜ α 時(shí)，x∈BND(X);

(N)當(dāng)Pr(X|[x])≤ β 時(shí)，x∈NEG(X);

其中

且

1.2 長短時(shí)記憶網(wǎng)絡(luò)

LSTM 是由Hoehreiterhe 與Schmiduhber 于1997 年提出后經(jīng)過大量的改進(jìn)，目前被廣泛應(yīng)用[9]，成為目前處理序列與時(shí)序問題上的熱門方案。LSTM 是由一般的RNN 改進(jìn)而來。LSTM 與一般的RNN 的主要區(qū)別是在LSTM 中的神經(jīng)元不再是由單純的神經(jīng)元組成而是由4 個(gè)功能不同的門來共同作用。其中包括了輸入門、輸出門、狀態(tài)門，以及遺忘門。具體的結(jié)構(gòu)如圖1 所示。

圖1 LSTM 網(wǎng)絡(luò)結(jié)構(gòu)Fig.1 LSTM network structure

LSTM 的獨(dú)特結(jié)構(gòu)是為了使其能夠解決長期依賴問題而專門設(shè)計(jì)的。不同于RNN 網(wǎng)絡(luò)，LSTM 的重復(fù)結(jié)構(gòu)是由更加復(fù)雜的3 個(gè)門相互連接而成。包括遺忘門、輸入門與輸出門。

式(4)～(9)描述了細(xì)胞內(nèi)各個(gè)門的處理流程。

式(4)描述了遺忘門決定了當(dāng)細(xì)胞更新時(shí)細(xì)胞狀態(tài)會丟棄什么信息。該門會讀取ht-1和xt，輸出在 [0,1] 之間的數(shù)值與原先細(xì)胞狀態(tài)Ct-1相結(jié)合。其中，1 表示完全保留，0 表示完全遺忘。其中，ht-1表示上一個(gè)細(xì)胞的輸出，xt表示當(dāng)前細(xì)胞的輸入， σ 表示sigmod 函數(shù)。

式(5) 描述輸入門決定了讓多少新的信息加入到細(xì)胞狀態(tài)中。第一步，細(xì)胞輸入xt與細(xì)胞的上個(gè)輸出ht-1會通過sigmod 元來決定更新的內(nèi)容。

式(6)描述了更新內(nèi)容。與式(5)同時(shí)，同樣的輸入會通過一個(gè)tanh 元，生成備用的更新內(nèi)容。

式(7) 描述了更新內(nèi)容Ct。將式(5) 與式(6)兩部分結(jié)果相乘，將細(xì)胞狀態(tài)由Ct-1更新至Ct。

最終輸出數(shù)據(jù)由式(8)的輸出與當(dāng)前細(xì)胞狀態(tài)的一部分共同決定輸出的最終值，如式(9)描述。

以上為LSTM 模型的基本工作流。

1.3 代價(jià)敏感分類

一般的，對于分類算法的研究的核心與重點(diǎn)為如何取得更高的分類準(zhǔn)確率，但事實(shí)上，只要有誤差存在，分類過程總會產(chǎn)生代價(jià)。而代價(jià)敏感分類就是關(guān)注如何使分類過程中產(chǎn)生的代價(jià)最小。根據(jù)問題的難易程度，代價(jià)敏感問題常被分為二分類與多分類問題。對于二分類問題，目前大部分的代價(jià)敏感分類多是從非代價(jià)敏感分類算法加以轉(zhuǎn)化得到的。

結(jié)合上述，可將代價(jià)敏感分類等價(jià)于一個(gè)優(yōu)化問題: 將實(shí)例使用分類算法A劃分至類別I時(shí)，使損失函數(shù)L(x,i) 達(dá)到最小[10]：

式中：x表示一個(gè)實(shí)例；L(x,i) 表示x的類別為i時(shí)錯(cuò)誤分類的代價(jià)；P(j|x) 表示算法將x劃分至類別j的概率；c(i,j) 表示將i分類劃分至j所產(chǎn)生的代價(jià)。

對于每個(gè)類別i，L(x,i) 表示x所有可能的劃分結(jié)果的代價(jià)的概率和。故由式(10)知，當(dāng)分類代價(jià)最小時(shí)，其分類結(jié)果P(j|x) 不一定取到最大值。即為了得到更小的分類代價(jià)，可能會放棄最大的分類結(jié)果。

在如何使算法獲得傾向性的問題上，有兩種經(jīng)典算法：1)通過預(yù)處理，使算法對某些結(jié)果具有敏感性，此方法稱為rescaling[11]；2)希望通過以代價(jià)為基準(zhǔn)修改不同分類在算法中的成員可能性，從而產(chǎn)生不同的傾向性。此方法稱為reweighted[12]。

2 基于LSTM 的三支決策分類算法

基于三支決策的L S T M 算法在原有的LSTM 基礎(chǔ)上，增加了三支決策步驟，對前端分類器給出的預(yù)測結(jié)果做出接受、拒絕、延遲3 種不同的方案，算法流程如圖2 所示。

圖2 基于LSTM 的三支決策算法流程Fig.2 Flow of 3WD based on LSTM

算法包括兩部分：1) 前置分類器，用于初步分類；2) 三支決策，考慮決策風(fēng)險(xiǎn)，通過算法的判斷降低決策風(fēng)險(xiǎn)。

2.1 前置分類器

前置分類器的作用主要體現(xiàn)在前置分類器的分類精度最終決定了整體上的分類效果。此后的三支決策對前置分類器的分類結(jié)果做出評判，決定接受、拒絕、或者延遲推斷。對于LSTM 分類器，主要用來解決分類和時(shí)序問題預(yù)測。輸出包括預(yù)測結(jié)果C和預(yù)測的分類概率p。分類概率p用于下一步中三支決策算法來判斷是否采納分類結(jié)果。

2.2 三支決策

三支決策對前置分類器給出的結(jié)果進(jìn)行分析。根據(jù)式(1)～(3)，可以得出相應(yīng)的判斷代價(jià) ?。

將根據(jù)前置分類器的分類結(jié)果X，與由對應(yīng)的損失函數(shù) λ 計(jì)算出的代價(jià)，由判斷規(guī)則(Pli)、(Bli)、(Nli)判斷，給出相應(yīng)的決策建議。

2.3 算法概述

結(jié)合上述分析，本文提出基于LSTM 與三支決策的代價(jià)敏感分類算法，算法描述如下：

BEGIN：

3 實(shí)驗(yàn)與結(jié)果

實(shí)驗(yàn)在自建實(shí)驗(yàn)平臺中運(yùn)行。實(shí)驗(yàn)平臺包括4 臺服務(wù)器，每臺服務(wù)器均使用相同的配置。每臺服務(wù)器有6 個(gè)CPU，主頻2.5 GHz，運(yùn)行內(nèi)存16 GB。

測試數(shù)據(jù)集來自UCI 開放數(shù)據(jù)集中的Beijing PM2.5 Data Set 與International airline passengers。數(shù)據(jù)集均為分類任務(wù)。

PM2.5 數(shù)據(jù)集來自于UCI 數(shù)據(jù)庫，該數(shù)據(jù)集記錄了從2010 年1 月1 日至2014 年12 月31 日北京市的空氣質(zhì)量指數(shù)和氣象數(shù)據(jù)。數(shù)據(jù)集為時(shí)間序列數(shù)據(jù)，特征為連續(xù)特征，任務(wù)可作為分類或回歸任務(wù)。數(shù)據(jù)一共43 824 條記錄，特征共13 個(gè)，部分?jǐn)?shù)據(jù)缺失。

數(shù)據(jù)集中包括了時(shí)間，當(dāng)日的溫度、濕度、氣壓、風(fēng)向、累計(jì)風(fēng)速、累計(jì)降雨/降雪量、PM2.5 指數(shù)共13 個(gè)數(shù)據(jù)。其中的PM2.5 指數(shù)為當(dāng)日PM2.5 值，為連續(xù)實(shí)數(shù)。當(dāng)預(yù)測PM2.5 值時(shí)，問題為回歸問題。若以判斷PM2.5 區(qū)間作為空氣質(zhì)量判斷時(shí)，問題為分類問題。本例中，將原數(shù)據(jù)集中的PM2.5 均分為4 個(gè)區(qū)間，從小到大分別標(biāo)記為[優(yōu)，良，一般，差]4 類。根據(jù)前tn-i的氣象數(shù)據(jù)，預(yù)測tn的空氣質(zhì)量。

圖3 表示了原數(shù)據(jù)集中，PM2.5 與氣象數(shù)據(jù)的關(guān)系。圖4 表示了兩段分類結(jié)果的分布信息。

圖3 原始數(shù)據(jù)集中的特征分布Fig.3 Frequency of features in this dataset

圖4 原數(shù)據(jù)集中分類結(jié)果與時(shí)間的變化關(guān)系Fig.4 Relations between classify result and time change

從圖4 可以看出，空氣質(zhì)量與時(shí)間有明顯的關(guān)系，并且呈現(xiàn)出一定的周期規(guī)律。

國際旅行旅客數(shù)據(jù)集包括了1949—1960 年12 年之間每個(gè)月的國際航線航班旅客人數(shù)。共144 個(gè)數(shù)據(jù)，單位為1 千人。圖5 為原數(shù)據(jù)集中數(shù)據(jù)的分布。

圖5 1949—1960 年國際航班旅客人數(shù)Fig.5 Number of international airline traveler between 1949—1960

3.1 PM2.5 數(shù)據(jù)集

根據(jù)前述對數(shù)據(jù)集的分析，將數(shù)據(jù)通過前置分類器進(jìn)行回歸分析，得到分類結(jié)果。此LSTM分類器在數(shù)據(jù)集上的分類準(zhǔn)確率為0.997。由于為多分類問題，參考指標(biāo)由準(zhǔn)確率?召回率改為混淆矩陣。此分類器在測試數(shù)據(jù)上的結(jié)果混淆矩陣見圖6。圖7 為分類器訓(xùn)練的最終損失函數(shù)。

設(shè)代價(jià)函數(shù)為：

式中： λix為判斷是否正確；wix為權(quán)重；即判斷代價(jià)；b為偏移值。 λix的計(jì)算方式由表1 所述代價(jià)函數(shù)計(jì)算可得。

圖6 分類結(jié)果的混淆矩陣Fig.6 Confusion matrix of classification result

圖7 LSTM 訓(xùn)練損失Fig.7 Loss of LSTM training

將預(yù)測結(jié)果代入式(11)后, 得到原分類器的決策代價(jià)。

將得到的損失偏差與代入三支決策的決策規(guī)則 (Pli、Bli、Nli) 中，對明顯偏離預(yù)測中心的值進(jìn)行標(biāo)記，得到新的分類代價(jià)。

表2 可知，使用三支決策算法進(jìn)行判斷的分類任務(wù)在代價(jià)優(yōu)化上有顯著作用。

表2 使用三支決策的分類代價(jià)與未使用三支決策的分 類代價(jià)對比Table 2 Compara of cost of classification between 3WD and non-3WD

3.2 國際旅行旅客人數(shù)數(shù)據(jù)集

根據(jù)前述數(shù)據(jù)集的基本信息，將數(shù)據(jù)集進(jìn)行前期分類。圖8 為LSTM 作為前置分類器的預(yù)測數(shù)據(jù)。取預(yù)測步長為3，預(yù)測網(wǎng)絡(luò)兩層，每層含128 個(gè)LSTM 單元。

圖8 經(jīng)過前置分類器的預(yù)測數(shù)據(jù)Fig.8 Predict data after preprocessing

顯然，隨著時(shí)間推移，距預(yù)測點(diǎn)較遠(yuǎn)的點(diǎn)預(yù)測誤差越大。在整個(gè)數(shù)據(jù)集上，前置分類器的測試數(shù)據(jù)均方誤差為28.03。

對于回歸問題，由于沒有直接的方式判斷分類的正誤，本文使用均方誤差來描述對應(yīng)的置信度。由此，相應(yīng)的代價(jià)函數(shù)可表示為

但是與前述判斷規(guī)則(Pli、Bli、Nli)不同，此時(shí)的分類不再是由有限的狀態(tài)集合 {X,?X} 描述，而是由偏差和 方差組成的連續(xù)集合。所以，此時(shí)的(代) 價(jià) λi,j不再是確定的函數(shù)而是與由均方差 MSEθ? 描述的模型和距離預(yù)測點(diǎn)t的兩者組成的概率分布。

式中：f為訓(xùn)練模型的偏差分布；為模型的均方差；tn為當(dāng)前點(diǎn)距預(yù)測點(diǎn)的距離。

本例中，為方便計(jì)算，假設(shè)分布f為均勻分布。此時(shí)，代價(jià)函數(shù)簡化為只與時(shí)間tn相關(guān)的函數(shù)。由此，代入假設(shè)條件，可以得到如圖9 的代價(jià)曲線。

將代入三支決策算法結(jié)果如圖9。由結(jié)果可知，對于問題中給定時(shí)刻t， 在t+12 時(shí)，代價(jià)第一次大于閾值 α ，故在 [t,t+12] 時(shí)刻的數(shù)據(jù)是可信的。同理，在 [t+26] 時(shí)，預(yù)測代價(jià)第一次大于閾值 β ，所以從t+26 時(shí)刻起，預(yù)測數(shù)據(jù)不再可信。圖10 表示t與代價(jià)之間的關(guān)系。

圖9 隨 tn 而代價(jià)越來越大的判斷曲線 λtFig.9 As tn increases, the prediction results become more and more inaccurate

圖10 代價(jià)判斷決定的三支決策結(jié)果Fig.10 Discarding costly predictions given by 3WD

4 結(jié)束語

本文通過兩個(gè)實(shí)驗(yàn)的驗(yàn)證，提出了基于LSTM 的三支決策分類算法。實(shí)驗(yàn)1 在LSTM 分類的基礎(chǔ)上，增加三支決策分類后明顯地降低了決策風(fēng)險(xiǎn)；實(shí)驗(yàn)2 在原先分類器中引入三支決策后，也有了代價(jià)上的優(yōu)化。實(shí)驗(yàn)表明：1)三支決策的決策準(zhǔn)確率受前端分類器準(zhǔn)確率的較大影響；2)三支決策算法可以結(jié)合深度學(xué)習(xí)模型解決代價(jià)敏感分類問題，而非僅限于非貝葉斯模型的分類器；3)三支決策在解決代價(jià)敏感分類問題的同時(shí)，可以通過擴(kuò)展代價(jià)定義的方式，為回歸模型建立可信度判據(jù)。結(jié)合三支決策理論，在時(shí)間序列分析問題中，三支決策模型可以為預(yù)測結(jié)果增加可信度的判據(jù)，使得預(yù)測結(jié)果更加具有分析和處理的價(jià)值。

但是當(dāng)前的工作只是初步的驗(yàn)證有關(guān)于深度學(xué)習(xí)與三支決策相結(jié)合形成新的代價(jià)敏感分類的初步研究。本文的研究尚處于初步的階段。未來，對于模型的改進(jìn)仍有許多研究空間。例如，對于三支決策算法，可以結(jié)合新的邊界理論，形成自動化的邊界確定；在整體模型中，可以借助boost 或?qū)＜曳诸惼鞯饶Ｐ?，提出更完善的理論；以及結(jié)合Alex-net 等其他更高效的分類器來進(jìn)一步提高前置分類器的性能等。這些改進(jìn)都將能夠進(jìn)一步提高三支決策在在代價(jià)敏感分類領(lǐng)域的應(yīng)用頻率。