劉兆清 古仕林 侯臣平

(國防科技大學文理學院 長沙 410073)

由于現(xiàn)實環(huán)境的開放性與復雜性，在許多實際應用中，人們不得不面臨數據的數量與特征維度都在同時變化的情形.一個典型的場景就是數據當前的特征增加，下一時刻的數據特征只有部分被繼承，并且由于環(huán)境變化難以預知，哪些特征會消失、哪些特征會被繼承難以提前確定.本文將這樣的數據稱為特征繼承性增減的流式數據.例如，在環(huán)境監(jiān)測任務中，任意時刻環(huán)境中都存在著多種不同壽命的傳感器，每個傳感器的反饋均被視為一個特征[1]，不同特征因為傳感器壽命不同，維持的時間也不同.在壽命較短的傳感器失效之前，為維持對環(huán)境的觀察，會向環(huán)境投放新的傳感器，使得在某個較短的時期內數據會包含歷史特征與新增特征；當這部分壽命較短的傳感器失效后，其對應的特征隨即消失，而壽命較長的傳感器對應的特征將繼承到下一時刻.總體來說，這是一個特征先進行增加，然后有繼承地減少的過程.

具體地，如圖1所示：在T1的初始階段(綠色部分)，環(huán)境中存在2種傳感器，返回的數據具有特征S1與S2；在b1階段，新一批傳感器被部署在環(huán)境中，數據中新增特征S3，此時數據中共包含3種特征，稱為過渡階段；在T2的初始階段(藍色部分)，第1批傳感器到達使用壽命之后被銷毀，其對應的數據特征S1隨即消失，此時數據特征僅剩繼承自上個階段的S2與S3，在b2階段，又有一批新的傳感器被部署在環(huán)境中，數據中又會出現(xiàn)新的特征S4.在現(xiàn)實場景中，數據流的特征將隨時間不斷增加或減少，但由于傳感器壽命的差異性，上一時刻數據的特征總有一部分會繼承到下一時刻，因此我們將其定義為特征繼承性增減的流式數據.

Fig. 1 The feature evolution pattern of environment monitoring圖1 環(huán)境監(jiān)測任務中特征的演化規(guī)律

傳統(tǒng)的在線學習算法要么假設數據以流的形式依次到達但是其特征空間保持不變[2-7]，要么假設特征以流的形式不斷到達但是訓練數據集保持不變[8-13]，這些都無法直接用于處理特征繼承性增減的流式數據.解決該問題一個簡單直接的方法是只利用具有相同特征空間的數據進行模型訓練，但是這樣并不能取得好的預測效果，主要原因有2個：1)部分特征消失后，消失特征對應的權重無法繼續(xù)利用，在過去的迭代過程中從樣本中提取的信息被浪費，產生了信息的損失；2)在新特征出現(xiàn)的初始階段，具有新特征的樣本數量少，不足以充分訓練分類器，對分類器的性能造成影響.

解決特征動態(tài)變化這一問題的關鍵就是建立一個能盡可能多地繼承原有信息的動態(tài)分類模型.基于上述思想，近年來有極少部分工作針對動態(tài)特征的場景進行了研究[14-16].這些工作采用不同的特征劃分或投影策略來構建動態(tài)模型，在處理特征動態(tài)變化的問題上做出了原創(chuàng)性的貢獻.但是，上述工作假設的數據特征演化方式與本文都不相同，因此相關的技術挑戰(zhàn)和解決方法也各不相同.

針對特征繼承性增減的流式數據分類問題，本文提出了一種面向特征繼承性增減的在線分類算法(online classification algorithm with feature inheritably increasing and decreasing, OFID)及其2種變體OFID -Ⅰ和OFID -Ⅱ.當新特征出現(xiàn)時，OFID引入新權重對其進行學習，對原始特征與新增特征上的分類器制定不同的更新策略，通過結合在線被動-主動(online passive aggressive algorithms, PA)算法[5]與結構風險最小化原則分別更新原始特征與新增特征上的分類器；當部分原始特征消失時，利用歷史數據與當前數據的一致性，運用在線矩陣補全的方法，對數據流的缺失部分使用Frequent-Directions算法[17-18]進行恢復，使得原始分類器得以繼續(xù)更新迭代；為防止出現(xiàn)過擬合現(xiàn)象，開發(fā)了OFID算法的2種軟間隔變體OFID -Ⅰ和OFID -Ⅱ.理論分析和實驗結果分析都驗證了本文所提算法的有效性.

本文工作的創(chuàng)新點總結有3個方面：

1) 研究了一個對特征繼承性增減的數據流進行分類的新問題，這一問題具有重要的實際應用價值，對該問題進行專門的研究.

2) 設計了一種新穎的算法OFID及其2種變體OFID -Ⅰ和OFID -Ⅱ，從特征繼承性增減的數據流中學習高度動態(tài)的分類模型.從理論上證明了OFID系列算法的損失上界，保證了算法的可靠性與有效性.

3) 通過對比實驗，在公開數據集上與其他算法進行了對比，并取得了良好的表現(xiàn)；同時通過另外2組輔助實驗探究了算法的參數敏感程度與時間復雜情況，驗證了算法自身的良好性質.

1 相關工作

針對特征動態(tài)變化的在線學習研究在實踐上具有廣泛的應用前景，例如環(huán)境監(jiān)測、垃圾郵件識別等.本文致力于研究面向特征繼承性增減的在線學習方法，主要包含2個方面：1)在線學習；2)特征動態(tài)變化.下面我們將從這2個方面對本文的相關工作進行概述.

在線學習的研究經歷了較長時間的發(fā)展，具有成熟的理論與巨大的應用價值[13]，期間發(fā)展出許多經典的方法.大致可以將現(xiàn)有在線學習方法分為利用模型一階信息和二階信息的方法.利用一階信息的在線學習算法有感知機算法(perceptron learning algorithm, PLA)[7]、PA算法[5]、在線梯度下降算法(online gradient descent algorithm, OGD)[19]等.感知機算法只在當前模型預測出現(xiàn)錯誤的情況下才會更新，而PA算法只要當模型產生的預測損失不為0(即使數據標簽預測正確)，都會主動更新當前模型.其核心思想是尋找與當前分類模型最近鄰的約束，若當前模型對新來數據預測沒有損失，模型不更新，否則，模型主動更新，即投影到離現(xiàn)有分類模型最近鄰的位置.因此，PA算法在大多數情形下都會顯著的優(yōu)于感知機算法.在線梯度下降算法在每次迭代時都沿當前損失函數梯度下降的方向更新模型，然后將更新后的模型投影到可行域中.利用二階信息的在線算法有二階感知機算法[20]、NHERD[21]算法(normal herding method via Gaussian herding)、SCW(soft confidence weighted algorithm)算法[22]、IELLIP(online learning algorithms by improved Ellipsoid)算法[23]、AROW(adaptive regularization of weight vectors)算法[24]等.利用二階信息的算法有著更優(yōu)異的預測效果，但是其計算開支與一階算法相比更大.

以上這些算法建立在數據特征空間固定的基礎之上，不能直接在動態(tài)特征的場景下進行應用.為解決動態(tài)特征場景下的在線學習問題，極少部分研究者結合各種特征演化規(guī)律，提出了一些在線動態(tài)特征學習算法.Zhang等人首先對數據數量與特征維度隨時間不斷增加的場景進行了研究，提出了OLSF系列算法(online learning with streaming features)[14].Zhang等人將數量與特征維度都隨時間增加的數據稱為梯形數據，當新到達的數據攜帶了新的特征時，OLSF算法將數據特征分為歷史特征和新增特征2部分，通過改進PA算法使得分類器在面對2種特征時執(zhí)行不同的在線更新規(guī)則.針對訓練集固定、特征以流到來的場景，Wu等人[25]提出了OSFS(online streaming feature selection)算法對數據進行在線特征選擇.Hou等人[26]在OLSF的基礎上研究了特征有增有減的場景，提出FESL(feature evolvable streaming learning)算法，其假設數據的歷史特征是同時消失的，不具有繼承性.FESL通過在新增特征與歷史特征共存的階段學習特征之間的映射關系，從而在歷史特征消失后可以利用新增特征對歷史特征進行恢復，并在2種特征上分別訓練分類器，最后利用集成學習的思想對2個預測結果進行集成得到最后的分類結果.在FESL算法的基礎上，后續(xù)發(fā)展了EDM(evolving discrepancy minimization)[27]和PUFE(prediction with unpredictable feature evolution)算法[28]，對FESL場景進行了深入探索和擴展.進一步地，有研究者研究了數據流的特征可以任意新增或消失的情形.如He等人[29]提出了OLVF算法(online learning with varying feature space)，將當前樣本的特征分為存留特征、共享特征和新特征3部分，將現(xiàn)有模型投影到共享的特征空間中進行預測更新.Beyazit等人[30]提出了GLSC算法(generative learning with streaming capricious data)，在全特征空間上學習新特征與舊特征之間的映射關系.

2 面向特征繼承性增減的在線學習算法

本節(jié)首先詳細介紹繼承性增減的場景以及本文用到的符號和相關含義，然后對OFID算法進行介紹，梳理算法的整體思路，提出相關策略并形成對應的優(yōu)化問題，然后對優(yōu)化問題進行求解，在最后給出算法的偽代碼.

2.1 問題設定以及相關符號

本文需要完成特征繼承性增減場景下的在線二分類任務，本節(jié)首先介紹該場景下數據特征的變化特點，后面列出用到的符號與概念，最后抽象為數學形式上的問題.

本場景下數據的變化呈現(xiàn)出明顯的階段性趨勢，如圖1所示，以數據特征經歷一輪完整的繼承性增減的時間為一個處理階段，例如階段1～T2-b2，不同階段數據的特征變化非常相似，在處理數據時可以按照階段進行.每個階段大致可以分為3個部分，每個部分內數據的特征保持穩(wěn)定，突變發(fā)生在第2，3部分，單階段內特征變化規(guī)律為：

① 1～T1-b1

這段時間內數據的特征空間與第1個樣本相同，此階段的數據具有特征S1與S2；

②T1-b1+1～T1

本階段的初始，t=T1-b1+1時，特征空間發(fā)生突變，數據的維度升高，此時數據攜帶特征S1，S2與S3，本時段也被稱為過渡階段；

③T1+1～T1+T2-b2

在本階段，與上個階段相比，數據特征減少，特征S2，S3得到繼承，特征S1消失.

上述場景可以抽象為一個特征繼承性增減的在線二分類問題.在本文中用{xt,t=1,2,…,T1+T2-b2}表示序貫接收的樣本，其中xt∈dt，表示xt是一個dt維的行向量.wt是t-1輪迭代后得到的分類器.在t=T1-b1+1時，新增特征出現(xiàn)，為了對歷史特征和新增特征加以區(qū)別，文中用表示原始特征組成的向量，表示新增特征組成的向量，原始特征是樣本xt在x1特征空間上的投影，新增特征是樣本xt的剩余部分，即其中分類器w做同樣的劃分，用yt表示樣本xt的真實標簽，表示分類器的預測結果.

Table 1 Notations and Descriptions表1 符號及其含義

2.2 OFID算法

觀察特征的演化規(guī)律可以發(fā)現(xiàn)算法有2個最主要的問題需要解決，主要問題1：在T1-b1+1～T1階段，新的特征S3出現(xiàn)，加入訓練會對第1階段訓練得到的分類器產生影響；T1-b1+1～T1階段維持時間較短，數據數少，如何設計更新策略、在初期攜帶新特征的數據不足的情況下進行較為準確的訓練是一個問題.主要問題2：在T1+1～T1+T2-b2階段，特征S1消失，只利用具有相同特征空間的數據進行模型訓練，對應缺失維度的信息就會丟失，造成信息的浪費，降低預測準確率.既要盡可能的減少信息的損失，保證預測準確率，又要適應周期內特征空間的增減變化，這是算法需要解決的技術重點，針對特征繼承性增減的在線分類場景，本文提出面向特征繼承性增減的在線分類算法OFID及其2種變體.對于問題1，算法的策略是在第2階段更新時引入新分類器對新增特征進行學習，但盡量維持上個階段分類器的權重.歷史模型在原始特征的多輪迭代上得到了充分訓練，具有較高的置信度，因此采用維持原有分類器的更新策略，進行上述處理，模型可能會增加對舊特征的依賴，對于該問題，OFID算法在下個處理過程中，放棄了對于舊特征的恢復，只對新分類器進行訓練，在一定程度上避免了模型對舊特征的依賴，達到了充分擬合新特征的目的；對于問題2，本文采用FD算法對矩陣進行補全.補全后的數據矩陣可以采用已有的成熟技術進行在線分類.

本文在第1部分采取PA算法進行模型更新，因為PA算法具有十分顯著的優(yōu)點：1)PA算法是在線學習任務中應用十分廣泛的算法，具有良好的收斂速度；2)PA算法在保證良好學習性能的前提下，具有較快的運行速率；3)利用PA算法可以使OFID算法具有良好的理論保證.因此本文使用PA算法進行模型更新.

本場景下數據呈現(xiàn)明顯的特征增減規(guī)律，在1～T1-b1時間段內，特征空間保持不變，本階段內第t輪迭代時，PA算法滿足的優(yōu)化表達式為

(1)

(2)

以上處理解決了特征增加時分類器對新增特征的適應問題。然而，在T1+1～T1+T2-b2階段，特征S1消失，數據矩陣出現(xiàn)了缺失.為了繼續(xù)使用和訓練原有分類器，算法選擇利用過渡階段的完整數據進行矩陣補全.

在傳統(tǒng)特征變化的研究中[26,31]，通常采用新特征來補全舊特征，達到挖掘新舊特征之間的關系的目的.然而，本文研究的特征繼承性增減的實際應用場景中，下一時刻數據哪些特征會發(fā)生缺失無法事先確定，難以通過學習新舊特征之間的關系來對消失的舊特征進行補全.因此，本論文采取FD算法進行補全，F(xiàn)D算法的基本思路是尋找出現(xiàn)頻率高的向量作為一組基來補全數據矩陣，將單個的數據樣本作為整體來處理，可以很好地解決新舊特征不確定的問題，對缺失特征進行有效準確的補全.

FD算法不考察特征之間的關系，其補全流程是建立一個r行的矩陣，最后一行設置為零向量，每一個樣本被接收后作為一個行向量替代掉矩陣中的零向量，然后對矩陣做SVD分解，將最小的奇異值剔除，繼續(xù)按照以上步驟操作，遍歷所有數據.最終返回一個草圖矩陣.

T1-b1+1～T1階段接收到的樣本組成矩陣N，對矩陣N使用FD算法繪制秩為r的矩陣草圖B，記B的行向量為vi,i∈{1,2,…,r}，構成一個向量組，B的行空間記為V，利用V對T1+1～T1+T2-b2階段的缺失部分進行補全.

在T1+1～T1+T2-b2階段的第t輪迭代，接收到樣本xt，在V中尋找一個向量zt，記zt∈V，該向量滿足:

(3)

(4)

(5)

(6)

第2個是ξ的平方形式：

(7)

(8)

以此形成2種變體算法OFID -Ⅰ與OFID -Ⅱ，它們是OFID算法的軟間隔形式.

傳統(tǒng)的在線學習算法每次接收一個數據就進行模型的更新，因此具有運行速度快、存儲空間要求小等優(yōu)點，而本文提出的OFID系列算法每次接收一個數據就進行分類器的更新，具有傳統(tǒng)在線學習算法的優(yōu)點，屬于典型的在線學習算法.但由于本文的核心研究內容是特征繼承性增減這一特殊場景，作者在傳統(tǒng)的在線學習算法上做出了改進，提高了算法對特征繼承性增減變化的適應能力，增強了算法在該場景下的分類能力.

2.3 優(yōu)化問題求解

(9)

其中τ是拉格朗日乘數，將w的表達式代入L(w,τ)，進一步有:

(10)

式(10)對τ求導，令其等于0，得到wt+1的閉式解：

(11)

優(yōu)化問題式(2)的求解與問題式(1)的求解類似，使用拉格朗日乘子法，有:

(12)

(13)

式(13)對τ求導，令其等于0，得到wt+1的閉式解：

(14)

繼續(xù)使用拉格朗日乘子法對優(yōu)化問題式(5)～(8)進行求解，得到2個變體算法統(tǒng)一的更新方式，

(15)

其中，

(16)

綜合以上求解過程，3種算法具有統(tǒng)一的更新形式：

OFID算法及其他2種變體算法的偽代碼如下所示：

算法1.OFID算法及其變體.

輸入：參數C>0;

輸出：1～T1+T2-b2階段內預測正確的樣本數量、草圖矩陣B.

初始化：w1=(0,…,0)∈d1;

fort=1,2,…,T1do

① 接收樣本xt;

yt(w·xt)}，wt與xt維度相同時；

wt與xt維度不同時.

④ 接收標簽yt;

⑤ 計算步長τt;

⑥ 利用算法2訓練草圖矩陣B;

⑦ 更新分類器：

end

fort=T1+1,…,T1+T2-b2-1 do

⑨ 重復步驟②③④⑤⑦

end

算法1中采用了Frequent-Directions學習草圖矩陣，其算法偽代碼為：

算法2.Frequent-Directions.

輸出：草圖矩陣B;

初始化：B=0r×dT1.

fort=T1-b1+1,…,T1do

①Br←xt;

② [U,Σ,V]←SVD(B);

③N←ΣVT;

end

3 算法分析

本節(jié)對OFID系列算法的損失進行討論與證明，在理論上保證算法的有效性和可靠性.本節(jié)用到了3個引理、3個定理.引理1用于說明FD算法在條件滿足的情況下可以精確地對矩陣進行補全；引理2，3與定理1用于說明數據集線性可分情況下OFID算法Hinge損失平方和有上界；定理2用于說明算法OFID -Ⅰ犯錯總數有上界；定理3用于說明算法OFID -Ⅱ的Hinge損失平方和有上界.

引理1.在算法2中，對矩陣B做SVD分解，B=UΣVT，令r∈{min(T1-b,d1)}，即r是草圖矩陣B的秩，并且有U=(u1,u2,…,ur)∈(T1-b)×r，V=(v1,v2,…,vr)∈(T1-b)×r，記和是矩陣B的前r個左右奇異向量.定義:

若滿足s≥7μ(r)rln(rb1/δ)，s為消失特征的維數，則在至少1-δ的概率下算法可以將矩陣精確地進行恢復.

證明.引理1的詳細證明可參考文獻[18].

引理2[14].記(xt,yt)，t=1,2,…,T為序貫接收的流式數據，其中xt∈dt，yt∈{-1,+1}，數據的維數滿足dt-1≤dt，步長損失t采用Hinge損失，則對任意向量u∈dT，有:

(17)

即:

下面對單項的?t進行估計.在t=0時，τt=0，有又dwt≤dwt+1，則有:

(18)

(19)

式(19)兩邊對t累加，可得:

(20)

證畢.

引理3[14].記(xt,yt)，t=1,2,…,T為序貫接收的流式數據，其中xt∈dt，yt∈{-1,+1}，dt-1≤dt并且對所有t均成立；假設存在分類器u∈dT，在任意一次迭代中滿足則有：

(21)

(22)

證畢.

定理1.記(xt,yt)，t=1,2,…,T1+T2-b2為序貫接收的流式數據，其中xt∈dt，yt∈{-1,+1}，補全后的樣本滿足對所有t均成立；分類器滿足對所有t均成立；假設存在分類器u∈dT，對補全后的矩陣，對任意的t滿足令R=max{R1,R2}，則有:

證明.令：

?t對t進行累加，得到:

證畢.

定理2.記(xt,yt),t=1,2,…,T1+T2-b2為序貫接收的流式數據，其中xt∈dt，yt∈{-1,+1}，補全后的樣本滿足對所有t均成立，則對于任意向量u∈dT1，算法OFID -Ⅰ犯錯次數的一個上界為

證明.令

代入后得到式(21)中，得到:

整理后得到:

證畢.

定理2說明了算法OFID -Ⅰ在恢復出的樣本有界時，犯錯總數存在上界.

定理3.記(xt,yt),t=1,2,…,T1+T2-b2為序貫接收的流式數據，其中xt∈dt，yt∈{-1,+1}，補全后的樣本滿足對所有t均成立，則對于任意向量u，u∈dT1，有:

證明.通過引理2已知:

(23)

(24)

將τt的定義代入，有:

通過定理3，在理論上驗證了OFID -Ⅱ算法的Hinge損失平方和有上界.

證畢.

4 實 驗

本節(jié)通過數值仿真實驗來驗證OFID算法及其2種變體的表現(xiàn).首先介紹實驗設置及數據集.

本節(jié)共設置4組實驗，組1實驗為主試驗，進行OFID系列算法與FESL-c，F(xiàn)ESL-s，PUFE算法的對比，使用預測準確率作為指標，觀察OFID系列算法在具體數據集上的表現(xiàn)，驗證OFID算法的有效性和可靠性；組2實驗為參數實驗，以預測錯誤率為指標，考察2種變體算法的參數敏感性以及添加松弛變量的效果；組3實驗為算法時間復雜的實驗，指標為時間，用來考察算法的時間復雜度.組4實驗為輔助實驗，指標為算法的預測正確率，在3個不同的迭代階段分別記錄并進行對比，驗證OFID算法在不同迭代階段的有效性.

實驗數據要求具有動態(tài)的特征空間，為滿足這一要求，對特征空間進行了劃分，劃分的樣式如圖1所示，每個數據集的特征隨機進行排序，近似均分為3部分；在場景設置中T1-b1+1～T1階段維持時間較短，在劃分數據集時遵循了這一設定，過渡階段的數據量占比設置為1/10，階段1的數據比例與缺失數據的比例等同，我們按照以上規(guī)則對數據集進行劃分.

每次實驗每個數據集重復20次，每次重復隨機打亂數據的順序，并使用20次結果的平均值作為指標的最終值.參數實驗中，總共進行9次調參，參數C的選擇范圍為10-4～104，參數C的每次變化倍率為10.

本文在公開數據集上進行實驗，包括Cancer，air，WDBC，warpPIE，WBC，Haberman，Wine，Thyroid，Seeds共9個數據集，這些數據集分布在多個領域.數據集的情況如表2所示：

Table 2 The Datasets Used in the Experiments表2 實驗中用到的數據集

4.1 OFID系列算法與FESL,PUFE算法的對比實驗

表3展示了6種算法在不同數據集上的最終預測準確率.在大多數數據集上，OFID系列算法與其他算法相比有著較高的預測準確率，說明OFID系列算法較好地適應了數據特征的動態(tài)變化，具有現(xiàn)實應用的價值.但是一個學習過程中，3個階段的數據的特征有較大的差異，因此最終的預測準確率并不足以概括在整個學習過程各個算法的表現(xiàn).為更加直觀地觀察算法在各個階段的表現(xiàn)，本文選取預測錯誤率作為指標，觀察6種算法在學習過程中預測錯誤率的動態(tài)變化，實驗結果如圖2所示.

Table 3 Prediction Accuracy of Six Algorithms on Different Datasets表3 6種算法在不同數據集上的預測準確率

Fig. 2 Prediction wrong rates of six algorithms on different datasets圖2 6種算法在不同數據集上的預測錯誤率

圖2是6種算法在數據集上預測錯誤率隨時間的變化情況，橫坐標是迭代次數，縱坐標是平均預測錯誤率.OFID -Ⅰ，OFID -Ⅱ在大多數數據集上表現(xiàn)優(yōu)于算法OFID.說明軟間隔形式取得了應有的設計效果，降低了對噪聲的敏感程度，提高了算法性能.

在大多數數據集上，OFID -Ⅰ(紅色)、OFID -Ⅱ(黑色)算法表現(xiàn)最好，算法OFID(藍色)次之，表現(xiàn)優(yōu)于其他3種算法，說明OFID系列算法具有實際應用的價值，該實驗驗證了算法的有效性.

算法FESL，PUFE在數據集Wine上表現(xiàn)較OFID更好.在其余數據集上，OFID系列算法表現(xiàn)最優(yōu).對于上述實驗結果進行觀察，會發(fā)現(xiàn)1～T1-b1階段的預測正確率對算法FESL，PUFE的整體表現(xiàn)有重要的影響，F(xiàn)ESL，PUFE的整體表現(xiàn)優(yōu)于OFID系列算法時在1～T1-b1階段的預測優(yōu)于OFID系列算法.

4.2 參數實驗

在本節(jié)進行參數實驗，評價指標為20次實驗的平均預測正確率，觀察參數變化對實驗結果的影響，考察OFID系列算法對參數C的敏感程度，圖3為參數實驗的具體結果，橫坐標為參數C的數值，參數C的范圍為10-4～104，縱坐標為平均預測正確率.OFID算法無參數，不受參數變化影響，形成實驗的固定參照；觀察圖3，隨著參數C的變動，可以發(fā)現(xiàn)OFID -Ⅰ，OFID -Ⅱ的預測正確率隨之產生了一定程度的波動.參數過小時，OFID算法與OFID -Ⅰ，OFID -Ⅱ算法之間的預測正確率存在差距，但隨著參數C逐漸增大，3種算法準確率之間的差距先增大后減小，最后趨同.

從優(yōu)化問題的結構來分析出現(xiàn)圖中變化趨勢的原因，參數C調節(jié)的是優(yōu)化表達式中松弛變量與分類器變化2部分的比率，當C增大時，要最小化優(yōu)化問題式(5)～(8)，代表著松弛條件收緊，對應的ξ值變小，損失降低，對數據的敏感性提高，隨著參數C增大，2種變體算法逐漸向沒有松弛變量的OFID算法靠攏，分析結果剛好與圖3的實驗結果對應.

Fig. 3 The average rates of right predictions with respect to C=10i圖3 C=10i對平均預測正確率的影響

4.3 算法的時間復雜的實驗

本節(jié)實驗中，評價算法計算復雜度的指標為算法得到預測結果的運行時間.6種算法在不同數據集上的運行時間如表4所示.

Table 4 Running Time of Different Algorithms on Different Datasets表4 不同算法在不同數據集的運行時間 s

6種算法的更新表達式在形式上并無本質上的不同，均為線性迭代算法，區(qū)別只在于每一步迭代中使用的系數，這并不會有時間消耗上的顯著差異，因此，復雜度存在差異的主要原因在于矩陣補全的方式.OFID系列算法與PUFE算法均使用FD算法進行補全，F(xiàn)ESL算法在過渡階段訓練一個線性映射進行補全，這涉及到了矩陣的求逆運算.這也是時間消耗的主要部分.

表4中OFID -Ⅰ與OFID -Ⅱ算法的運行時間明顯高于其他算法，這是因為這2種算法需要進行參數的調節(jié)，每得到一個調參后的預測結果，算法需要運算9次，平均得到一個結果的時間與其他算法相當；OFID算法與FESL算法、PUFE算法在時間消耗上相當，具有相同的計算復雜度.

4.4 分階段預測實驗

本節(jié)實驗中選取4個數據集，觀測指標為OFID系列算法與其他3種對比算法在3個不同階段的平均預測準確率，預測結果取階段結束時算法的平均預測準確率，具體的實驗結果如圖4所示.觀察實驗結果，可以發(fā)現(xiàn)OFID系列算法在迭代的3個階段里均有優(yōu)異的表現(xiàn)，這組輔助實驗充分說明了OFID系列算法在不同迭代階段均具有良好的分類性能.

Fig. 4 The average prediction accuracy of the algorithm in three periods圖4 3個迭代階段中算法的平均預測準確率

5 總結與展望

為解決數據流特征繼承性增減這一新的實際問題，本文提出了一種面向特征繼承性增減的在線學習算法OFID及其2種變體OFID -Ⅰ與OFID -Ⅱ.當新特征出現(xiàn)時，通過結合在線PA算法與結構風險最小化原則分別更新原始特征與新增特征上的分類器；當原始特征消失時，對數據流使用Frequent-Directions算法對數據矩陣進行補全，使得原始分類器得以繼續(xù)更新迭代.理論分析和實驗結果分析都驗證了本文所提算法的有效性.

本文的對比方法中，有一些優(yōu)秀的思想可以進行借鑒，例如對新舊分類器分別進行預測更新，互不干擾，預測標簽來自新舊分類器的預測結果進行加權，這樣不僅避免了分類器對舊特征的過渡依賴，并且可以充分利用恢復出的信息，有著較高的研究價值，這將是未來工作中我們努力的一個方向.

本文所提的算法主要是針對線性場景下的分類問題，因此，將本文算法擴展到非線性場景下是我們未來非常重要的一項工作.同時，如何挖掘特征繼承性增減數據流的更多信息，例如二階信息、數據分布信息，以及如何對特征繼承性增減數據流進行在線聚類等也是值得關注的方向.因此，在未來的工作中我們將對上述內容開展更加深入的研究.