基于動(dòng)態(tài)策略的多源遷移學(xué)習(xí)數(shù)據(jù)流分類研究

周 勝,劉三民

(安徽工程大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 蕪湖 241000)

0 概述

隨著大數(shù)據(jù)技術(shù)的不斷發(fā)展,數(shù)據(jù)流挖掘在天氣預(yù)報(bào)、金融預(yù)測(cè)、電子商務(wù)等領(lǐng)域得到廣泛應(yīng)用。傳統(tǒng)的數(shù)據(jù)流分類方法需要大量的標(biāo)簽樣本來訓(xùn)練分類模型,而獲取大量標(biāo)簽樣本費(fèi)時(shí)費(fèi)力,且這類方法無法有效解決數(shù)據(jù)流中的概念漂移和噪聲問題。

目前,將多源遷移學(xué)習(xí)[1-2]與集成學(xué)習(xí)[3-4]相結(jié)合并應(yīng)用于數(shù)據(jù)流分類的研究得到廣泛關(guān)注,該類方法通過將訓(xùn)練得到的多個(gè)源領(lǐng)域分類器進(jìn)行集成來對(duì)目標(biāo)領(lǐng)域新到樣本進(jìn)行分類,能夠解決源領(lǐng)域和目標(biāo)領(lǐng)域相似度較低以及目標(biāo)領(lǐng)域標(biāo)注樣本不足的問題[5-7]。根據(jù)多源領(lǐng)域分類器的不同集成方式,可以將多源領(lǐng)域分類器集成分為多源領(lǐng)域分類器直接集成和多源領(lǐng)域分類器選擇集成兩類。

多源領(lǐng)域分類器直接集成的方法將所有源領(lǐng)域分類器進(jìn)行集成。文獻(xiàn)[8]建立一種多源遷移學(xué)習(xí)算法OMS-TL,該算法根據(jù)二部圖實(shí)現(xiàn)對(duì)目標(biāo)領(lǐng)域樣本的預(yù)測(cè),通過對(duì)數(shù)據(jù)樣本進(jìn)行重用來實(shí)現(xiàn)遷移學(xué)習(xí)。文獻(xiàn)[9]設(shè)計(jì)OTLMS算法,該算法將源領(lǐng)域分類器和目標(biāo)領(lǐng)域分類器進(jìn)行組合以構(gòu)建預(yù)測(cè)分類器,解決了與目標(biāo)學(xué)習(xí)任務(wù)無關(guān)的噪聲源數(shù)據(jù)影響分類精度的問題。文獻(xiàn)[10]通過將目標(biāo)特征空間分成源域的同構(gòu)和異構(gòu)2個(gè)部分,將基分類器進(jìn)行加權(quán)組合獲得多個(gè)源領(lǐng)域分類器,并將它們組合成一個(gè)集成模型來解決多源異構(gòu)遷移學(xué)習(xí)問題。但是,每個(gè)源領(lǐng)域都可能不包含目標(biāo)域的完整類別信息,當(dāng)多個(gè)源領(lǐng)域之間存在較大差異時(shí),將所有源領(lǐng)域分類器進(jìn)行集成會(huì)導(dǎo)致分類性能降低。

針對(duì)多源領(lǐng)域分類器直接集成方法的不足,眾多國(guó)內(nèi)外學(xué)者提出使用多源領(lǐng)域分類器選擇集成的方法來解決數(shù)據(jù)流分類問題。文獻(xiàn)[11]基于局部分類精度提出一種多源遷移學(xué)習(xí)算法LC-MSOTL,該算法將局部分類精度最高的源領(lǐng)域分類器和目標(biāo)領(lǐng)域分類器進(jìn)行加權(quán)集成,實(shí)驗(yàn)結(jié)果顯示,該方法具有較高的準(zhǔn)確率。針對(duì)概念漂移數(shù)據(jù)流分類中的概念重現(xiàn)問題,文獻(xiàn)[12]提出一種重現(xiàn)概念漂移數(shù)據(jù)流分類算法RC-OTL,其根據(jù)領(lǐng)域相似度挑選最合適的源領(lǐng)域分類器,實(shí)驗(yàn)結(jié)果表明,RC-OTL算法能夠有效克服“負(fù)遷移”問題。文獻(xiàn)[13]構(gòu)建一種多源迭代自適應(yīng)算法MSIDA,該算法根據(jù)貪婪思想實(shí)現(xiàn)最佳源域的選擇,同時(shí)通過創(chuàng)建額外的偽標(biāo)記實(shí)例來解決樣本標(biāo)注問題。文獻(xiàn)[14]通過求解每個(gè)源領(lǐng)域?qū)?yīng)的權(quán)值向量,并用該權(quán)值向量表示源領(lǐng)域和目標(biāo)領(lǐng)域之間的相似度,從而顯著地提高了遷移學(xué)習(xí)的效率以及分類性能。文獻(xiàn)[15]提出一種OHTWC算法,其通過計(jì)算異構(gòu)域中同現(xiàn)數(shù)據(jù)的異構(gòu)相似性,解決了異構(gòu)域上的數(shù)據(jù)流分類問題。文獻(xiàn)[16]通過調(diào)整每個(gè)源領(lǐng)域分類器對(duì)應(yīng)的權(quán)重,同時(shí)用目標(biāo)領(lǐng)域分類器更換權(quán)重最大的源領(lǐng)域分類器,在出現(xiàn)概念漂移后快速恢復(fù)集成分類器的分類準(zhǔn)確率,最終使集成分類器的分類性能得到改善。

在數(shù)據(jù)流分類任務(wù)中,多源領(lǐng)域分類器選擇集成技術(shù)具有明顯優(yōu)勢(shì),但在多源遷移學(xué)習(xí)過程中,從多個(gè)源領(lǐng)域分類器中如何挑選最合適的分類器進(jìn)行遷移集成是急需解決的問題。本文提出一種基于樣本確定性的動(dòng)態(tài)分類器選擇方法,以高效選擇最合適的源領(lǐng)域分類器并解決數(shù)據(jù)流中的概念漂移和噪聲問題。

1 基本概念

為便于分析和理解,對(duì)本文涉及的基本概念進(jìn)行定義:

定義1數(shù)據(jù)流指按時(shí)間順序依次到達(dá)的n個(gè)樣本的集合,即:

S={(xt,yt)|t=1,2,…,n},(xt,yt)∈X×Y,X∈Rm,Y={-1,+1}

其中,X表示m維的特征空間,Y指樣本類別。

定義2概念漂移指數(shù)據(jù)樣本產(chǎn)生的聯(lián)合概率分布函數(shù)隨時(shí)間的推進(jìn)發(fā)生無法預(yù)知的變化,即:

pt(x,y)≠pt+1(x,y)

其中,x表示樣本特征信息,y表示樣本所屬類別。

定義3信息熵用來衡量某隨機(jī)事件發(fā)生的不確定性,其計(jì)算如下:

(1)

其中,X為隨機(jī)變量,k為隨機(jī)變量X所有可能發(fā)生的事件數(shù)目,pi為對(duì)應(yīng)事件發(fā)生的概率。

對(duì)信息熵計(jì)算公式分析可知,當(dāng)概率為1時(shí),信息熵最小為0,相當(dāng)于確定性事件。對(duì)于只有2種事件的隨機(jī)變量,當(dāng)概率為0.5時(shí),信息熵取得最大值,表明無法對(duì)當(dāng)前事件進(jìn)行有意義的判斷。隨機(jī)事件的信息熵與概率之間的關(guān)系如圖1所示。

圖1 信息熵與概率之間的關(guān)系

定義4樣本確定性指分類器對(duì)待分類樣本x預(yù)測(cè)結(jié)果的確定性程度。本文討論的是二分類問題,結(jié)合信息熵的定義可得樣本確定性計(jì)算公式如下:

(2)

其中,pi為樣本x對(duì)應(yīng)的類別后驗(yàn)概率。

通過樣本確定性進(jìn)行數(shù)據(jù)流分類,可以有效避免不確定分類器對(duì)噪聲數(shù)據(jù)流帶來的不利影響,同時(shí)提高分類準(zhǔn)確率。

2 棄權(quán)分類器

針對(duì)概念漂移數(shù)據(jù)流分類問題,文獻(xiàn)[17-19]提出基于棄權(quán)分類器的數(shù)據(jù)流分類方法,以挑選最合適的基分類器。棄權(quán)是指未能達(dá)到特定規(guī)則要求的基分類器不參與決策,當(dāng)發(fā)生概念漂移時(shí),該方法通過允許基分類器對(duì)新實(shí)例丟失信心時(shí)放棄預(yù)測(cè),同時(shí)允許選擇的基分類器參與決策,從而探索集成的多樣性,棄權(quán)分類器的結(jié)構(gòu)如圖2所示。首先計(jì)算多個(gè)基分類器對(duì)新到樣本的確定性值,然后強(qiáng)制未能達(dá)到閾值限制的基分類器放棄預(yù)測(cè),最后采用多數(shù)投票的方法對(duì)新到樣本進(jìn)行集成決策。該方法強(qiáng)制不確定分類器(未能達(dá)到特定規(guī)則要求的分類器)不進(jìn)行預(yù)測(cè),即不確定分類器可以放棄參與最終決策,并將所選擇的基分類器的輸出結(jié)果作為分類器集合的輸出。

棄權(quán)分類器的優(yōu)點(diǎn)在于能夠挑選出達(dá)到特定規(guī)則要求的分類器,更快適應(yīng)概念漂移現(xiàn)象,有利于消除噪聲數(shù)據(jù)的影響。本文基于棄權(quán)分類器,將多個(gè)源領(lǐng)域分類器對(duì)目標(biāo)領(lǐng)域數(shù)據(jù)塊中每個(gè)樣本的確定性值與給定的閾值進(jìn)行比較,對(duì)于未能達(dá)到閾值限制的源領(lǐng)域分類器,強(qiáng)制其不參與投票。若所選擇的源領(lǐng)域分類器集合能夠正確地預(yù)測(cè)標(biāo)簽,則意味著已經(jīng)選擇了有能力的源領(lǐng)域分類器,可以通過降低閾值來探索其他類似能力的源領(lǐng)域分類器。如果所選擇的源領(lǐng)域分類器集合做出不正確的決定,則表示可能發(fā)生了概念漂移現(xiàn)象,在這種情況下,需要增加閾值來排除不太合格的源領(lǐng)域分類器,以挑選出最適合當(dāng)前流狀態(tài)的源領(lǐng)域分類器。

3 算法描述

在樣本確定性和棄權(quán)分類器的基礎(chǔ)上,本文提出一種基于動(dòng)態(tài)策略的多源遷移學(xué)習(xí)算法DSMTL。該算法求得源領(lǐng)域分類器對(duì)目標(biāo)領(lǐng)域數(shù)據(jù)塊中每個(gè)樣本的類別后驗(yàn)概率,然后根據(jù)樣本確定性計(jì)算方法求得各源領(lǐng)域分類器對(duì)目標(biāo)領(lǐng)域數(shù)據(jù)塊中每個(gè)樣本的確定性值,最后將樣本確定性值滿足當(dāng)前閾值限制的源領(lǐng)域分類器與目標(biāo)領(lǐng)域分類器進(jìn)行在線集成,以對(duì)目標(biāo)領(lǐng)域數(shù)據(jù)塊進(jìn)行分類,其中,使用多數(shù)投票的方式進(jìn)行有關(guān)預(yù)測(cè)標(biāo)簽的最終決策,并根據(jù)集成決策的正確性修改閾值。DSMTL算法的詳細(xì)描述如下:

算法1DSMTL算法

輸入目標(biāo)域數(shù)據(jù)流DS,源領(lǐng)域分類器集合CS,棄權(quán)閾值θ,調(diào)整因子S

輸出集成分類模型對(duì)目標(biāo)領(lǐng)域數(shù)據(jù)塊的分類準(zhǔn)確率

1.參數(shù)初始化θ、S,緩存10個(gè)規(guī)模大小相等的數(shù)據(jù)塊,并分別在數(shù)據(jù)塊上訓(xùn)練源領(lǐng)域分類器

2.For j=1,2,…,對(duì)后續(xù)數(shù)據(jù)塊Dj依次循環(huán)處理

3.基于目標(biāo)領(lǐng)域數(shù)據(jù)塊Dj構(gòu)建目標(biāo)領(lǐng)域分類器ftj

4.計(jì)算各源領(lǐng)域分類器對(duì)目標(biāo)領(lǐng)域數(shù)據(jù)塊中每個(gè)樣本x的類別后驗(yàn)概率pi

5.計(jì)算各源領(lǐng)域分類器對(duì)目標(biāo)領(lǐng)域數(shù)據(jù)塊中每個(gè)樣本x的樣本確定性值sc:

6.將樣本確定性值滿足閾值限制的源領(lǐng)域分類器fs與目標(biāo)領(lǐng)域分類器ftj進(jìn)行在線集成,以對(duì)目標(biāo)領(lǐng)域數(shù)據(jù)塊Dj進(jìn)行分類

7.根據(jù)集成決策的正確性修改棄權(quán)閾值θ,如果集成分類器對(duì)目標(biāo)領(lǐng)域數(shù)據(jù)塊Dj的分類準(zhǔn)確率大于棄權(quán)閾值θ,則:

θ=θ·(1-S)

否則:

θ=θ·(1+S)

8.End For

在算法1中,步驟1表示初始化,步驟3表示基于目標(biāo)領(lǐng)域數(shù)據(jù)塊構(gòu)建目標(biāo)領(lǐng)域分類器,步驟4～步驟5表示求各源領(lǐng)域分類器對(duì)目標(biāo)領(lǐng)域數(shù)據(jù)塊中每個(gè)樣本的確定性值,步驟6表示選取樣本確定性值滿足閾值限制的源領(lǐng)域分類器,并與目標(biāo)領(lǐng)域分類器在線集成以對(duì)目標(biāo)領(lǐng)域數(shù)據(jù)塊進(jìn)行分類,步驟7表示棄權(quán)閾值修改。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)集

4.2 結(jié)果分析

本文將所提方法與基于準(zhǔn)確率選擇集成的多源遷移學(xué)習(xí)方法ASIMTL[4]進(jìn)行對(duì)比。實(shí)驗(yàn)采用Bayes分類器作為基分類器,通過批處理模式生成數(shù)據(jù)塊以及訓(xùn)練基分類器,其中,源領(lǐng)域數(shù)據(jù)塊大小為2 000,源領(lǐng)域數(shù)據(jù)塊個(gè)數(shù)為10,訓(xùn)練10個(gè)源領(lǐng)域分類器,同時(shí)基于目標(biāo)域數(shù)據(jù)流形成20個(gè)數(shù)據(jù)塊,數(shù)據(jù)塊大小設(shè)為500,求得各源領(lǐng)域分類器對(duì)目標(biāo)領(lǐng)域數(shù)據(jù)塊中每個(gè)樣本的確定性值,將樣本確定性值滿足閾值限制的源領(lǐng)域分類器與目標(biāo)領(lǐng)域分類器進(jìn)行在線集成,從而對(duì)目標(biāo)領(lǐng)域數(shù)據(jù)塊進(jìn)行分類。

實(shí)驗(yàn)1驗(yàn)證棄權(quán)閾值參數(shù)的影響。為驗(yàn)證棄權(quán)閾值對(duì)算法的影響,本文選擇3個(gè)不同的閾值,將平均準(zhǔn)確率和標(biāo)準(zhǔn)差統(tǒng)計(jì)量作為評(píng)價(jià)指標(biāo),固定調(diào)整因子的值為0.01,實(shí)驗(yàn)結(jié)果如表1所示。

表1 棄權(quán)閾值對(duì)DSMTL算法性能的影響

Table 1 Effect of waiver threshold on performance of DSMTL algorithm

棄權(quán)閾值平均準(zhǔn)確率標(biāo)準(zhǔn)差統(tǒng)計(jì)量0.6440.70080.04170.6500.70860.02830.6600.70820.0327

從表1可以看出,當(dāng)棄權(quán)閾值為0.650時(shí),算法平均準(zhǔn)確率和標(biāo)準(zhǔn)差統(tǒng)計(jì)量較優(yōu)。當(dāng)棄權(quán)閾值較大時(shí),每次迭代選擇的源領(lǐng)域投票分類器數(shù)量不夠,而閾值較小時(shí)選擇的源領(lǐng)域投票分類器可能并不適合當(dāng)前流狀態(tài),棄權(quán)閾值較大或較小都會(huì)導(dǎo)致無法挑選出最合適的源領(lǐng)域分類器,從而影響算法的分類性能。

實(shí)驗(yàn)2驗(yàn)證DSMTL算法的分類性能。圖3所示為DSMTL和ASIMTL 2種算法在數(shù)據(jù)集D1上采用先測(cè)試后訓(xùn)練策略所得的分類準(zhǔn)確率情況。從圖3可以看出,在無噪聲的情況下,相對(duì)于ASIMTL算法,DSMTL算法的分類準(zhǔn)確率有明顯提高,其能夠及時(shí)發(fā)現(xiàn)概念漂移并且挑選出最合適的源領(lǐng)域分類器以處理新出現(xiàn)的概念,如在數(shù)據(jù)塊2和數(shù)據(jù)塊5之間出現(xiàn)了分類準(zhǔn)確率持續(xù)下降的情況,數(shù)據(jù)塊12和數(shù)據(jù)塊14之間出現(xiàn)了曲線低峰,但算法能夠快速地恢復(fù)其識(shí)別準(zhǔn)確率,說明DSMTL算法能夠很好地適應(yīng)概念漂移情況,即通過樣本確定性值選擇源領(lǐng)域分類器的策略能夠有效改善遷移效果。

圖3 數(shù)據(jù)集D1上的實(shí)驗(yàn)結(jié)果

圖4、圖5是噪聲環(huán)境下2個(gè)數(shù)據(jù)集中的實(shí)驗(yàn)結(jié)果,從圖4、圖5可以看出,在有噪聲的情況下,DSMTL算法仍然具有較高的分類準(zhǔn)確率,優(yōu)于ASIMTL算法,說明其具備一定的抗噪性能,這是由于DSMTL算法使用了信息熵求樣本確定性值,其消除了噪聲數(shù)據(jù)的影響。但隨著噪聲數(shù)據(jù)的增加,DSMTL算法分類準(zhǔn)確率出現(xiàn)較大波動(dòng),這是由于噪聲樣本被誤認(rèn)為是概念漂移樣本用以構(gòu)建目標(biāo)領(lǐng)域分類器,導(dǎo)致集成分類器對(duì)新概念無法收斂。

圖4 數(shù)據(jù)集D2上的實(shí)驗(yàn)結(jié)果

圖5 數(shù)據(jù)集D3上的實(shí)驗(yàn)結(jié)果

綜上可知,DSMTL數(shù)據(jù)流分類算法可行,分類準(zhǔn)確率優(yōu)于ASIMTL算法,原因是DSMTL算法將求得的各源領(lǐng)域分類器對(duì)目標(biāo)領(lǐng)域數(shù)據(jù)塊中每個(gè)樣本的確定性值與一個(gè)給定的閾值進(jìn)行比較,只選擇滿足當(dāng)前閾值限制的源領(lǐng)域投票分類器,即強(qiáng)制不確定的分類器不參與投票,目的是為投票步驟選擇最不可能受噪聲數(shù)據(jù)影響的源領(lǐng)域分類器。因此,該算法能夠通過設(shè)置棄權(quán)閾值的方式挑選出最合適的源領(lǐng)域分類器,且其策略可以消除噪聲數(shù)據(jù)的影響,更快地適應(yīng)概念漂移現(xiàn)象,使分類模型面對(duì)概念漂移問題時(shí)具有更好的泛化能力。

從表2可以看出,DSMTL算法性能明顯優(yōu)于ASIMTL算法,平均準(zhǔn)確率約高出5個(gè)百分點(diǎn),在噪聲環(huán)境下仍然具有較高的準(zhǔn)確率,說明DSMTL算法能夠有效地處理數(shù)據(jù)流中的噪聲,更快地適應(yīng)概念漂移現(xiàn)象。當(dāng)數(shù)據(jù)集由不含噪聲的數(shù)據(jù)變?yōu)楹性肼暤臄?shù)據(jù)時(shí),DSMTL算法的分類準(zhǔn)確率下降程度小于ASIMTL算法,說明DSMTL算法面對(duì)噪聲數(shù)據(jù)流時(shí)具有更好的穩(wěn)定性和更強(qiáng)的抗噪性。原因是DSMTL算法利用信息熵求得各源領(lǐng)域分類器對(duì)目標(biāo)領(lǐng)域數(shù)據(jù)塊中每個(gè)樣本的確定性值,有效消除了噪聲數(shù)據(jù)的影響,使分類模型保持較高的分類精度以及較好的穩(wěn)定性。

表2 2種算法平均準(zhǔn)確率和標(biāo)準(zhǔn)差統(tǒng)計(jì)量對(duì)比

Table 2 Comparison of average accuracy and standard deviation statistics of two algorithms

數(shù)據(jù)集平均準(zhǔn)確率標(biāo)準(zhǔn)差統(tǒng)計(jì)量ASIMTLDSMTLASIMTLDSMTLD10.66080.70540.01460.0279D20.60280.65620.01710.0408D30.54380.60020.01130.0256

5 結(jié)束語

本文結(jié)合棄權(quán)分類器和樣本確定性計(jì)算方法,提出一種多源遷移數(shù)據(jù)流分類學(xué)習(xí)算法DSMTL。該算法能夠有效利用棄權(quán)分類器思想強(qiáng)制不確定分類器不進(jìn)行預(yù)測(cè),同時(shí)計(jì)算樣本確定性值以從源領(lǐng)域分類器集合中挑選最合適的分類器,并與目標(biāo)領(lǐng)域分類器進(jìn)行在線集成。實(shí)驗(yàn)結(jié)果表明,DSMTL算法能夠?qū)傻亩鄻有赃M(jìn)行選擇性控制,消除噪聲數(shù)據(jù)的影響,并解決數(shù)據(jù)流中概念變化和樣本標(biāo)注問題。下一步將對(duì)源領(lǐng)域與目標(biāo)領(lǐng)域數(shù)據(jù)的共有特征進(jìn)行識(shí)別,根據(jù)新到達(dá)樣本對(duì)分類模型進(jìn)行更準(zhǔn)確的權(quán)重設(shè)置,并探究對(duì)源領(lǐng)域和目標(biāo)領(lǐng)域之間的區(qū)分性進(jìn)行建模的方法。