基于雙論域信息系統(tǒng)的三支決策增量式更新算法

袁路妍 李 鋒

1(紹興職業(yè)技術(shù)學(xué)院信息工程學(xué)院 浙江 紹興 312000) 2(東華大學(xué)計算機科學(xué)與技術(shù)學(xué)院 上海 200051)

0 引 言

三支決策模型[1]是由著名學(xué)者Yao提出的一種新的決策模型，它由決策粗糙集進行誘導(dǎo)得出，通過一對閾值將整個論域空間分成三個不相交的區(qū)域，這三個區(qū)域?qū)?yīng)著三種決策結(jié)果，即接受、延遲和拒絕[1-2]。目前三支決策模型已成功運用于多種工程應(yīng)用中[3-6]。

繼Yao提出三支決策之后，學(xué)者們不斷對其進行改進和推廣，使得該模型適用于更為復(fù)雜的數(shù)據(jù)環(huán)境和更為廣泛的應(yīng)用場景。傳統(tǒng)的三支決策模型建立在完備的信息系統(tǒng)中，為了擴大適用范圍，Liu等[7]在不完備信息系統(tǒng)的基礎(chǔ)上提出了一種改進的三支決策。針對數(shù)值型的數(shù)據(jù)，Li等[8]將傳統(tǒng)的三支決策模型推廣至鄰域空間，提出了鄰域三支決策模型。在模糊環(huán)境下，Deng等[9]提出了基于模糊集的三支決策。Liang等[10]在直覺模糊集下誘導(dǎo)出了多種策略的三支決策模型。Zhao等[11]在模糊區(qū)間值信息系統(tǒng)下定義了三支決策。同時在其他模型中，學(xué)者們也做出了大量的改進與推廣。Qian等[12]在多粒度粗糙集中融入了三支決策模型。Lin等[13]學(xué)者在Qian等的基礎(chǔ)上提出了模糊環(huán)境下的多粒度三支決策。在多個代價函數(shù)方面，Dou等[14]提出了多代價策略的三支決策。對于多分類情形，Zhou[15]提出了多類情形的三支決策?？傊谄渌黝惖睦碚撃Ｐ椭校Q策模型已經(jīng)成為較為熱門的研究內(nèi)容[16-18]。

在數(shù)據(jù)挖掘領(lǐng)域，雙論域信息系統(tǒng)是一種重要的數(shù)據(jù)形式[19]，它常見于推薦系統(tǒng)中。對于這種類型的數(shù)據(jù)，Sun等[20-21]提出了一種推廣的三支決策模型，即雙論域三支決策。在該模型的基礎(chǔ)上，學(xué)者們又進行了多種推廣和應(yīng)用[22-23]，例如Huang等[23]提出了基于三支決策的個性化推薦算法。關(guān)于雙論域信息系統(tǒng)的三支決策也是目前的一個研究熱點。

然而，實際中的數(shù)據(jù)總是不斷動態(tài)更新的，這給傳統(tǒng)模型和算法的實際應(yīng)用帶來了一定的挑戰(zhàn)。解決這類問題的主要方法是進行增量式學(xué)習(xí)，針對三支決策模型，目前已有一些相關(guān)的增量式算法被提出[24-27]，例如Luo等[27]提出了一種矩陣方法的三支決策動態(tài)更新。遺憾的是，在這些已有的研究成果中，還未有對雙論域信息系統(tǒng)下的三支決策模型進行增量式更新的相關(guān)研究，因此促使本文對這方面的問題進行探索。

為了彌補雙論域信息系統(tǒng)下三支決策模型關(guān)于增量式更新研究的空白，本文提出一種高效的增量式更新算法。首先分別研究了雙論域信息系統(tǒng)下兩個論域動態(tài)更新時，三支決策模型中三個區(qū)域的增量式更新問題，理論證明了這種增量更新只依賴于變化的數(shù)據(jù)。然后基于這種更新機制，提出對應(yīng)的增量式更新算法。最后通過進行一系列的仿真實驗驗證了所提出增量式算法的有效性。

1 基本理論

定義1[20]設(shè)雙論域信息系統(tǒng)可表示為S=(U,V),其中U和V為該信息系統(tǒng)下的兩個論域。記F為從U到V上的二元關(guān)系，對于u∈U和v∈V，若它們滿足二元關(guān)系F，即(u,v)∈F，并且u和v存在如下映射關(guān)系：

F(u)={v∈V|(u,v)∈F}u∈UF-1(v)={u∈U|(u,v)∈F}v∈V

(1)

定義2[20]設(shè)雙論域信息系統(tǒng)S=(U,V)以及U和V上確定的二元關(guān)系F，那么對于Y?V關(guān)于二元關(guān)系F的下近似和上近似分別定義為：

(2)

(3)

在三支決策模型中，通常研究三種動作行為的決策問題。對于Y=Yj，那么Yc=V-Yj，即狀態(tài)集可表示為Ω={Y,Yc},行為集包含三種動作，即A={dP,dB,dN},分別代表了接受、延遲和拒絕三種決策。根據(jù)貝葉斯決策過程，對于u∈U可以誘導(dǎo)出如下最小代價規(guī)則：

(1) 當P(Y|F(u))≥α且P(Y|F(u))≥γ， 決策POS(Y)。

(2) 當P(Y|F(u))≤α且P(Y|F(u))≥β，決策BUN(Y)。

(3) 當P(Y|F(u))≤β且P(Y|F(u))≤γ，決策NEG(Y)。

其中：

(4)

由于代價通常滿足特定的關(guān)系[1-2],這使得閾值通常滿足0≤β<γ<α≤1。對于Y?U可以得到在二元關(guān)系F下關(guān)于閾值α、β的三個區(qū)域：

(5)

這三個區(qū)域直接對應(yīng)三支決策模型中的三個決策規(guī)則[1]，即正區(qū)域POS(Y)中的對象接受Y決策，邊界域BUN(Y)中的對象延遲Y決策，負區(qū)域NEG(Y)中的對象拒絕Y決策。因此對于雙論域信息系統(tǒng)下的三支決策模型，即需要得到?jīng)Q策對象集關(guān)于給定α、β閾值的三個區(qū)域[20]。

2 雙論域下三支決策的動態(tài)更新

由于現(xiàn)實環(huán)境下數(shù)據(jù)的動態(tài)性，雙論域信息系統(tǒng)往往處于不斷動態(tài)更新之中，因此本節(jié)主要研究雙論域信息系統(tǒng)動態(tài)變化后三支決策的動態(tài)更新問題。由于雙論域的動態(tài)更新涉及到兩個論域的變化，因此分別對每個論域進行單獨分析。

2.1 論域U變化時三支決策的動態(tài)更新

2.1.1對象增加時模型的更新

根據(jù)第1節(jié)，三支決策規(guī)則的誘導(dǎo)主要取決于三個區(qū)域的計算，因此當信息系統(tǒng)發(fā)生變化后，研究三支決策的動態(tài)更新即轉(zhuǎn)換為研究三個區(qū)域的動態(tài)更新。

設(shè)t時刻的雙論域信息系統(tǒng)表示為St=(Ut,Vt)，Ut和Vt確定的二元關(guān)系為Ft，對于Yt?Vt在Ft下關(guān)于閾值α、β確定的三個區(qū)域分別表示為POS(Yt)、BUN(Yt)和NEG(Yt)。t+1時刻雙論域信息系統(tǒng)更新為St+1=(Ut+1,Vt+1)，其中：Ut+1=Ut∪U+;Vt+1=Vt;此時Ut+1和Vt+1確定的二元關(guān)系為Ft+1。對于Yt+1=Yt在Ft+1下關(guān)于閾值α、β確定的三個區(qū)域表示為POS(Yt+1)、BUN(Yt+1)和NEG(Yt+1)。

定理1設(shè)0≤β<α≤1，t時刻Yt?Vt關(guān)于二元關(guān)系Ft的三個區(qū)域為POS(Yt)、BUN(Yt)和NEG(Yt)。那么t+1時刻Yt+1關(guān)于二元關(guān)系Ft+1的三個區(qū)域增量式更新為：

(1)POS(Yt+1)=POS(Yt)∪Δ，其中：

Δ={u∈U+|P(Yt+1|Ft+1(u))≥α}

(2)BUN(Yt+1)=BUN(Yt)∪Δ，其中：

Δ={u∈U+|β

(3)NEG(Yt+1)=NEG(Yt)∪Δ，其中：

Δ={u∈U+|P(Yt+1|Ft+1(u))≤β}

證明：

(1) 根據(jù)正區(qū)域的定義有：

POS(Yt+1)={u∈Ut+1|P(Yt+1|Ft+1(u))≥α}=

{u∈Ut∪U+|P(Yt+1|Ft+1(u))≥α}=

{u∈Ut|P(Yt+1|Ft+1(u))≥α}∪

{u∈U+|P(Yt+1|Ft+1(u))≥α}

對于?x∈Ut，即Ft+1(u)=Ft(u),又由于Yt+1=Yt，所以P(Yt+1|Ft+1(u))=P(Yt|Ft(u)),u∈Ut。則{u∈Ut|P(Yt+1|Ft+1(u))≥α}=POS(Yt),所以POS(Yt+1)=POS(Yt)∪Δ，其中：Δ={u∈U+|P(Yt+1|Ft+1(u))≥α}

(2)和(3)的證明類似于(1)。

證畢。

通過定理1可以發(fā)現(xiàn)，當論域U增加對象集U+后，只需要對增加的對象計算相應(yīng)的三個區(qū)域，然后與原來三個區(qū)域進行合并便可以更新出最終結(jié)果。

2.1.2對象減少時模型的更新

類似于2.1.1節(jié)的探究思路，這里同樣可以得到論域U中對象減少時三個區(qū)域的增量式更新問題。

設(shè)t時刻的雙論域信息系統(tǒng)表示為St=(Ut,Vt)，Ut和Vt確定的二元關(guān)系為Ft，對于Yt?Vt在Ft下關(guān)于閾值α、β確定的三個區(qū)域分別表示為POS(Yt)、BUN(Yt)和NEG(Yt)。t+1時刻雙論域信息系統(tǒng)更新為St+1=(Ut+1,Vt+1)，其中：Ut+1=Ut-U-;Vt+1=Vt；此時Ut+1和Vt+1確定的二元關(guān)系為Ft+1。對于Yt+1=Yt在Ft+1下關(guān)于閾值α、β確定的三個區(qū)域表示為POS(Yt+1)、BUN(Yt+1)和NEG(Yt+1)。

定理2設(shè)0≤β<α≤1，t時刻Yt?Vt關(guān)于二元關(guān)系Ft的三個區(qū)域為POS(Yt)、BUN(Yt)和NEG(Yt)。那么t+1時刻Yt+1關(guān)于二元關(guān)系Ft+1的三個區(qū)域增量式更新為：

(1)POS(Yt+1)=POS(Yt)-Δ，其中：

Δ={u∈U-|u∈POS(Yt)}

(2)BUN(Yt+1)=BUN(Yt)-Δ，其中：

Δ={u∈U-|u∈BUN(Yt)}

(3)NEG(Yt+1)=NEG(Yt)-Δ，其中：

Δ={u∈U-|u∈NEG(Yt)}

證明：

(1) 根據(jù)正區(qū)域的定義有：

POS(Yt+1)={u∈Ut+1|P(Yt+1|Ft+1(u))≥α}=

{u∈Ut-U-|P(Yt+1|Ft+1(u))≥α}=

{u∈Ut|P(Yt+1|Ft+1(u))≥α}-

{u∈U-|P(Yt+1|Ft+1(u))≥α}

對于?x∈Ut，即Ft+1(u)=Ft(u)。又由于Yt+1=Yt，所以：

{u∈Ut|P(Yt+1|Ft+1(u))≥α}=POS(Yt)

由于U-?Ut，所以：

{u∈U-|P(Yt+1|Ft+1(u))≥α}?POS(Yt)

則POS(Yt+1)=POS(Yt)-Δ，其中：

Δ={u∈U-|u∈POS(Yt)}

(2)和(3)的證明類似于(1)。

證畢。

通過定理2可以發(fā)現(xiàn)，當論域U減少一部分對象U-，只需要對原來三個區(qū)域中的對象作出相應(yīng)的刪除便可以更新出最終結(jié)果。

2.2 論域V變化時三支決策的動態(tài)更新

2.2.1對象增加時模型的更新

設(shè)t時刻的雙論域信息系統(tǒng)表示為St=(Ut,Vt)，Ut和Vt確定的二元關(guān)系為Ft，對于Yt?Vt在Ft下關(guān)于閾值α、β確定的三個區(qū)域分別表示為POS(Yt)、BUN(Yt)和NEG(Yt)。t+1時刻雙論域信息系統(tǒng)更新為St+1=(Ut+1,Vt+1)，其中：Ut+1=Ut；Vt+1=Vt∪V+；此時Ut+1和Vt+1確定的二元關(guān)系為Ft+1且Ft+1=Ft∪F+，顯然F+是論域Ut和V+確定的二元關(guān)系。對于Yt+1=Yt∪Y+(Y+?V+)在Ft+1下關(guān)于閾值α、β確定的三個區(qū)域分別表示為POS(Yt+1)、BUN(Yt+1)和NEG(Yt+1)。

定理3對于?u∈Ut，設(shè)Yt關(guān)于u在二元關(guān)系Ft下的條件概率為P(Yt|Ft(u))，雙論域信息系統(tǒng)更新后，Yt+1=Yt∪Y+關(guān)于對象u在二元關(guān)系Ft+1下的條件概率為P(Yt+1|Ft+1(u))。則：

(1) 若P(Y+|F+(u))≥P(Yt|Ft(u))，那么：

P(Yt|Ft(u))≤P(Yt+1|Ft+1(u))≤P(Y+|F+(u))

(2) 若P(Y+|F+(u))≤P(Yt|Ft(u))，那么：

P(Y+|F+(u))≤P(Yt+1|Ft+1(u))≤P(Yt|Ft(u))

式中：P(Y+|F+(u))表示Y+關(guān)于u在二元關(guān)系F+下的條件概率。

證明：根據(jù)定義有：

這里令:

|Yt∩Ft|=a,|Y+∩F+|=a+,|Ft|=b,|F+|=b+

那么:

則有:

所以:

P(Y+|F+(u))≥P(Yt+1|Ft+1(u))

P(Yt|Ft(u))-P(Yt+1|Ft+1(u))=

所以:

P(Yt|Ft(u))≤P(Yt+1|Ft+1(u))

綜上有:

P(Yt|Ft(u))≤P(Yt+1|Ft+1(u))≤P(Y+|F+(u))

(2) 的證明過程類似于(1)。

證畢。

定理3表明，當雙論域信息系統(tǒng)更新后，P(Yt+1|Ft+1(u))值始終介于P(Yt|Ft(u))與P(Y+|F+(u))之間，根據(jù)條件概率這一變化規(guī)律，可以進一步得到論域V中對象增加時三個區(qū)域的增量式更新。

定理4設(shè)0≤β<α≤1，t時刻Yt?Vt關(guān)于二元關(guān)系Ft的三個區(qū)域為POS(Yt)、BUN(Yt)和NEG(Yt)。那么t+1時刻Yt+1關(guān)于二元關(guān)系Ft+1的三個區(qū)域增量式更新為：

1) ?u∈POS(Yt)，那么:

(1) 若P(Y+|F+(u))≥α，則u∈POS(Yt+1)。

(2) 若P(Y+|F+(u))<α，則：

2) ?u∈BUN(Yt)，那么：

(1) 若β

(2) 若P(Y+|F+(u))≥α，則:

(3) 若P(Y+|F+(u))≤β，則:

3) ?u∈NEG(Yt)，那么：

(1) 若P(Y+|F+(u))≤β，則u∈NEG(Yt+1)。

(2) 若P(Y+|F+(u))>β，則:

證明：

(1) 對于?u∈POS(Yt)，有P(Yt|Ft(u))≥α。

若P(Y+|F+(u))≥α,根據(jù)定理3滿足：

P(Yt+1|Ft+1(u))≥α

因此u∈POS(Yt+1)。

若P(Y+|F+(u))<α，根據(jù)定理3可知P(Yt+1|Ft+1(u))的值介于P(Yt|Ft(u))和P(Y+|F+(u))之間，因此P(Yt+1|Ft+1(u))的值無法確定，所以此時需要分開討論，則有:

因此(1)成立。

(2)和(3)的證明過程類似于(1)。

證畢。

定理4表明，當雙論域信息系統(tǒng)論域V中的對象動態(tài)增加后，需要對對象u∈U計算條件概率P(Y+|F+(u))，當該條件概率與閾值α、β滿足某些特定關(guān)系時，可以直接判定出u隸屬于哪個區(qū)域。對于條件概率與閾值α、β不滿足特定關(guān)系時，這時才需要計算對象u的新條件概率P(Yt+1|Ft+1)，然后根據(jù)新的條件概率判定該對象的區(qū)域隸屬情況，同時新條件概率的計算可采用增量式的方式，即：

因此，按定理4的更新方式具有較高的計算效率。

2.2.2對象減少時模型的更新

設(shè)t時刻的雙論域信息系統(tǒng)表示為St=(Ut,Vt)，Ut和Vt確定的二元關(guān)系為Ft，對于Yt?Vt在Ft下關(guān)于閾值α、β確定的三個區(qū)域分別表示為POS(Yt)、BUN(Yt)和NEG(Yt)。t+1時刻雙論域信息系統(tǒng)更新為St+1=(Ut+1,Vt+1)，這里的Ut+1=Ut,Vt+1=Vt-V-，此時Ut+1和Vt+1確定的二元關(guān)系為Ft+1，且Ft+1=Ft-F-，顯然F-是論域Ut和V-確定的二元關(guān)系。對于Yt+1=Yt-Y-(Y-?V-)在Ft+1下關(guān)于閾值α、β確定的三個區(qū)域表示為POS(Yt+1)、BUN(Yt+1)和NEG(Yt+1)。

定理5對于?u∈Ut，設(shè)Yt關(guān)于u在二元關(guān)系Ft下的條件概率為P(Yt|Ft(u))，雙論域信息系統(tǒng)更新后，Yt+1=Yt-Y-關(guān)于對象u在二元關(guān)系Ft+1下的條件概率為P(Yt+1|Ft+1(u))。則：

(1) 若P(Y-|F-(u))≥P(Yt|Ft(u))，則:

P(Yt+1|Ft+1(u))≤P(Yt|Ft(u))

(2) 若P(Y-|F-(u))≤P(Yt|Ft(u))則:

P(Yt|Ft(u))≤P(Yt+1|Ft+1(u))

證明：根據(jù)定義有:

這里令：

|Yt∩Ft|=a,|Y-∩F-|=a-,|Ft|=b,|F-|=b-

那么：

則有：

P(Yt|Ft(u))-P(Yt+1|Ft+1(u))=

所以P(Yt+1|Ft+1(u))≤P(Yt|Ft(u))。

(2) 的證明過程類似于(1)。

證畢。

根據(jù)定理5所示的條件概率變化關(guān)系，可以得到當論域V中對象減少時三支決策中三個區(qū)域的增量式更新。

定理6設(shè)0≤β<α≤1，t時刻Yt?Vt關(guān)于二元關(guān)系Ft的三個區(qū)域為POS(Yt)、BUN(Yt)和NEG(Yt)。那么t+1時刻Yt+1關(guān)于二元關(guān)系Ft+1的三個區(qū)域增量式更新為：

1) ?u∈POS(Yt)，那么：

(1) 若P(Y-|F-(u))≤P(Yt|Ft(u))，則u∈POS(Yt+1)。

(2) 若P(Y-|F-(u))≥P(Yt|Ft(u))，則：

2) ?u∈BUN(Yt)，那么：

(1) 若P(Y-|F-(u))≤P(Yt|Ft(u))，則：

(2) 若P(Y-|F-(u))≥P(Yt|Ft(u))，則：

3) ?u∈NEG(Yt)，那么：

(1) 若P(Y-|F-(u))≥P(Yt|Ft(u))，則u∈NEG(Yt+1)。

(2) 若P(Y-|F-(u))≤P(Yt|Ft(u))，則：

證明過程類似于定理4。

定理6也表明，當雙論域信息系統(tǒng)論域V中的對象動態(tài)減少后，需要對對象u∈U計算條件概率P(Y-|F-(u))，當該條件概率P(Y-|F-(u))滿足某些特定關(guān)系時，可以直接判定出u隸屬于哪個區(qū)域。對于條件概率不滿足特定關(guān)系時，這時才需要計算對象u的新條件概率P(Yt+1|Ft+1)，然后根據(jù)新的條件概率判定該對象的區(qū)域隸屬情況，類似于定理4，新條件概率的計算同樣可采用增量式的方式，即：

因此，按定理6的更新方式同樣具有較高的計算效率。

3 雙論域下三支決策的更新算法

本節(jié)給出雙論域信息系統(tǒng)下三支決策的動態(tài)更新算法，首先給出非增量式的動態(tài)更新算法。根據(jù)文獻[20]，當雙論域信息系統(tǒng)動態(tài)更新后，非增量式更新算法的主要思想是按照三個區(qū)域最基本的計算方式去更新三個區(qū)域，具體如算法1所示。

算法1[20]雙論域信息系統(tǒng)下三支決策的非增量式更新算法

輸入：新的雙論域信息系統(tǒng)S=(Ut+1,Vt+1),閾值參數(shù)α、β和目標概念集Yt+1。

輸出：POS(Yt+1)，BUN(Yt+1)，NEG(Yt+1)。

1.初始化POS(Yt+1)=?，BUN(Yt+1)=?，NEG(Yt+1)=?。

2.對于?u∈Ut+1，計算Yt+1關(guān)于對象u在二元關(guān)系Ft+1下的條件概率:

3.對于?u∈Ut+1進行判斷：

① 若P(Yt+1|Ft+1(u))≥α，則:

POS(Yt+1)=POS(Yt+1)∪{u}

② 若β

BUN(Yt+1)=BUN(Yt+1)∪{u}

③ 若P(Yt+1|Ft+1(u))≤β，則:

NEG(Yt+1)=NEG(Yt+1)∪{u}

4.返回POS(Yt+1)、BUN(Yt+1)和NEG(Yt+1)。

在算法1所示的非增量式更新算法中，其主要的計算量集中在第2步中關(guān)于條件概率的計算，由于目標概念集Yt+1已經(jīng)給定，條件概率的計算即為Ft+1(u)的計算，每個對象計算Ft+1(u)的時間復(fù)雜度為O(|Vt+1|)，計算Ut+1中所有對象的時間復(fù)雜度為O(|Ut+1||Vt+1|)。因此整個算法1的時間復(fù)雜度為O(|Ut+1||Vt+1|)。

算法2所示的是雙論域信息系統(tǒng)論域U中對象增加時三支決策的增量式更新算法。根據(jù)算法1，算法2的時間復(fù)雜度為O(|U+||Vt+1|)。

算法2雙論域信息系統(tǒng)下三支決策的增量式更新算法(U增加)

輸入：更新前后的雙論域信息系統(tǒng)S=(Ut,Vt)和S=(Ut+1,Vt+1)，其中Ut+1=Ut∪U+;閾值參數(shù)α、β和目標概念集Yt+1=Yt;POS(Yt)、BUN(Yt)和NEG(Yt)。

輸出：POS(Yt+1),BUN(Yt+1)，NEG(Yt+1)。

1.初始化:

POS(Yt+1)=POS(Yt)

BUN(Yt+1)=BUN(Yt)

NEG(Yt+1)=NEG(Yt)

2.對于?u∈U+，計算Yt+1關(guān)于對象u在二元關(guān)系Ft+1下的條件概率：

3.對于?u∈U+進行判斷：

① 若P(Yt+1|Ft+1(u))≥α，則:

POS(Yt+1)=POS(Yt+1)∪{u}

② 若β

BUN(Yt+1)=BUN(Yt+1)∪{u}

③ 若P(Yt+1|Ft+1(u))≤β，則:

NEG(Yt+1)=NEG(Yt+1)∪{u}

4.返回POS(Yt+1)、BUN(Yt+1)和NEG(Yt+1)。

算法3所示的是雙論域信息系統(tǒng)下論域U中對象減少時三支決策的增量式更新算法。在算法3中，只需要對U-中的對象進行考察分析便可以完成整個更新過程，因此算法3的時間復(fù)雜度為O(|U-|)。

算法3雙論域信息系統(tǒng)下三支決策的增量式更新算法(U減少)

輸入：更新前后的雙論域信息系統(tǒng)S=(Ut,Vt)和S=(Ut+1,Vt+1)，其中Ut+1=Ut-U-;閾值參數(shù)α、β和目標概念集Yt+1=Yt；POS(Yt)、BUN(Yt)和NEG(Yt)。

輸出：POS(Yt+1),BUN(Yt+1)，NEG(Yt+1)。

1.初始化

POS(Yt+1)=POS(Yt)

BUN(Yt+1)=BUN(Yt)

NEG(Yt+1)=NEG(Yt)

2.對于?u∈U-進行以下判斷：

① 若u∈POS(Yt)，則:

POS(Yt+1)=POS(Yt+1)-{u}

② 若u∈BUN(Yt)，則:

BUN(Yt+1)=BUN(Yt+1)-{u}

③ 若u∈NEG(Yt)，則:

NEG(Yt+1)=NEG(Yt+1)-{u}

3.返回POS(Yt+1)、BUN(Yt+1)和NEG(Yt+1)。

算法4所示的是雙論域信息系統(tǒng)下論域V中對象增加時三支決策的增量式更新算法。在算法4中，主要的計算量集中在計算條件概率P(Y+|F+(u))上，對于部分條件概率P(Yt+1|Ft+1(u))可采用增量式方法計算得出，因此整個算法4的時間復(fù)雜度為O(|Ut+1||V+|)。

算法4雙論域信息系統(tǒng)下三支決策的增量式更新算法(V增加)

輸入：更新前后的雙論域信息系統(tǒng)S=(Ut,Vt)和S=(Ut+1,Vt+1)，其中Vt+1=Vt∪V+；閾值參數(shù)α、β和目標概念集Yt+1=Yt∪Y+；?u∈Ut+1,條件概率P(Yt|Ft(u))；POS(Yt)、BUN(Yt)、NEG(Yt)。

輸出：POS(Yt+1),BUN(Yt+1)，NEG(Yt+1)。

1.初始化POS(Yt+1)=?，BUN(Yt+1)=?，NEG(Yt+1)=?。

2.對于?u∈Ut+1計算P(Y+|F+(u))：

① 若u∈POS(Yt)，當P(Y+|F+(u))≥α?xí)ru∈POS(Yt+1)，否則根據(jù)P(Y+|F+(u))增量式計算出P(Yt+1|Ft+1(u))，然后判別u的隸屬情況。

② 若u∈BUN(Yt),當β

③ 若u∈NEG(Yt)，當P(Y+|F+(u))≤β時u∈NEG(Yt+1)，否則根據(jù)P(Y+|F+(u))增量式計算出P(Yt+1|Ft+1(u))，然后根據(jù)定理4判別u的隸屬情況。

3.返回POS(Yt+1)、BUN(Yt+1)和NEG(Yt+1)。

算法5所示的是雙論域信息系統(tǒng)下論域V中對象減少時三支決策的增量式更新算法，類似于算法4，算法5的時間復(fù)雜度為O(|Ut+1||V-|)。

算法5雙論域信息系統(tǒng)下三支決策的增量式更新算法(V減少)

輸入：更新前后的雙論域信息系統(tǒng)S=(Ut,Vt)和S=(Ut+1,Vt+1)，其中Vt+1=Vt-V-；閾值參數(shù)α、β和目標概念集Yt+1=Yt-Y-；?u∈Ut,條件概率P(Yt|Ft(u))；POS(Yt)、BUN(Yt)和NEG(Yt)。

輸出：POS(Yt+1)、BUN(Yt+1)和NEG(Yt+1)。

1.初始化POS(Yt+1)=?，BUN(Yt+1)=?，NEG(Yt+1)=?。

2.對于?u∈Ut+1計算P(Y-|F-(u))：

① 若u∈POS(Yt)，當P(Y-|F-(u))≤P(Yt|Ft(u))時u∈POS(Yt+1),否則根據(jù)P(Y-|F-(u))增量式計算出P(Yt+1|Ft+1(u))，然后判別u的隸屬情況。

② 若u∈BUN(Yt)，那么根據(jù)P(Y-|F-(u))增量式計算出P(Yt+1|Ft+1(u))，然后判別u的隸屬情況。

③ 若u∈NEG(Yt)，當P(Y-|F-(u))≥P(Yt|Ft(u))時u∈NEG(Yt+1),否則根據(jù)P(Y-|F-(u))增量式計算出P(Yt+1|Ft+1(u))，然后根據(jù)定理6判別u的隸屬情況。

3.返回POS(Yt+1)、BUN(Yt+1)和NEG(Yt+1)。

4 實驗分析

本節(jié)將進行一系列實驗來驗證本文所提出增量式更新算法的有效性。表1給出了實驗所使用的6個數(shù)據(jù)集，其中編號1至4的數(shù)據(jù)集為個性化推薦系統(tǒng)中常用的公開數(shù)據(jù)集，編號5和編號6給出了本文實驗隨機生成的人工數(shù)據(jù)集。本文實驗所有的算法采用MATLAB 2014b進行編程實現(xiàn)，并且實驗用計算機配置為CPU:Intel Core i5 4460 3.2 GHz, 內(nèi)存:DDR3 16 GB 1 600 MHz。

表1 實驗數(shù)據(jù)集

4.1 實驗設(shè)計與參數(shù)設(shè)置

本文提出雙論域信息系統(tǒng)下三支決策模型的動態(tài)更新算法，即雙論域信息系統(tǒng)是不斷動態(tài)更新的，而表1所示的均為靜態(tài)數(shù)據(jù)集，因此本文實驗采用文獻[27]的處理方法，即讓整個數(shù)據(jù)集均分成多個子數(shù)據(jù)集，然后通過逐個合并與分割的方式完成數(shù)據(jù)集的動態(tài)更新。將每個數(shù)據(jù)集按照論域U或論域V均分成7個子數(shù)據(jù)集，然后隨機選擇一份，不斷讓其他子數(shù)據(jù)集添加進行合并，這樣構(gòu)造出了6次動態(tài)增加更新，對于完整的數(shù)據(jù)集，每次移除一個子數(shù)據(jù)集，這樣便構(gòu)造出了6次動態(tài)減少更新。本文實驗中所有算法都是基于該處理方式進行動態(tài)更新。

對于本文算法中的目標概念集Y，實驗設(shè)定為隨機選擇當前論域V的四分之一對象，當論域V增加V+后，在V+中隨機選擇四分之一對象添加入Y中達到更新的效果。當論域V逐漸減小時，則按照相反的處理方式進行更新。在編號1至編號4的數(shù)據(jù)集中，其屬性值為離散型，在編號5和編號6的人工數(shù)據(jù)集中，其屬性值也為離散型，因此算法中的二元關(guān)系設(shè)定為等價關(guān)系。另外，算法中包含了參數(shù)α和參數(shù)β，在三支決策模型中，這兩個參數(shù)由代價函數(shù)得出，因此本實驗中令α=0.75，β=0.45。

4.2 論域U動態(tài)更新時增量式與非增量式算法的更新效率比較

本節(jié)針對論域U的動態(tài)變化，比較雙論域三支決策的非增量式更新算法與增量式更新算法的更新效率。由于論域U的動態(tài)變化分為兩種形式，因此分開進行實驗。

圖1是論域U中對象增加時，雙論域三支決策在非增量式與增量式兩類算法下的更新效率比較。

圖1 各個數(shù)據(jù)集論域U增加時非增量式與增量式算法的更新效率比較

可以看出，隨著數(shù)據(jù)集中論域U的不斷增加更新，非增量式算法更新所需的時間也是不斷增大的，并且增長的速率大致是線性的。而對于增量式更新算法，隨著論域U的增大，其更新所需的時間基本上是保持不變的。出現(xiàn)這樣的結(jié)果主要是由于其更新機制不同導(dǎo)致的，不同的機制有著不同的時間復(fù)雜度，從而表現(xiàn)出了很大的差異。對于非增量式更新算法，當論域U更新時，該算法在計算新數(shù)據(jù)集下三支決策仍然采用傳統(tǒng)的計算方法，論域U增大，那么計算的時間也會增多。而增量式算法是對增加的數(shù)據(jù)進行計算，然后增量式更新得到新的模型結(jié)果，因此計算的時間只與增加的數(shù)據(jù)量有關(guān)，由于本文實驗中數(shù)據(jù)集每次是均勻增加的，因此增量式算法每次的更新時間大致不變。可以看出，增量式算法比非增量式算法具有更高的更新效率。

圖2為論域U中對象減小時，雙論域三支決策在非增量式與增量式兩類算法下的更新效率比較。

圖2 各個數(shù)據(jù)集論域U減少時非增量式與增量式算法的更新效率比較

可以看出，隨著論域U的逐漸減小，非增量式算法更新所需的時間是逐漸減小的，而增量式算法更新所需的時間非常少，幾乎可以忽略。出現(xiàn)這種結(jié)果的主要原因同樣是非增量式算法在更新時，需要對數(shù)據(jù)集進行重新計算，由于數(shù)據(jù)集的規(guī)模逐漸減小，因此所需的更新時間也是減小的。而對于增量式更新算法，定理2已經(jīng)表明，只需對原來模型結(jié)果中的相關(guān)元素進行刪除便可以完成更新，因此更新所需的時間極短，增量式更新算法的優(yōu)勢非常明顯。

4.3 論域V動態(tài)更新時增量式與非增量式算法的更新效率比較

本節(jié)針對論域V的動態(tài)變化，比較雙論域三支決策的非增量式更新算法與增量式更新算法的更新效率。同樣地,由于論域V的動態(tài)變化分為兩種形式，因此這里也需要分開進行實驗。

圖3是論域V中對象增加時，雙論域三支決策在非增量式與增量式兩類算法下的更新效率比較。

圖3 各個數(shù)據(jù)集論域V增加時非增量式與增量式算法的更新效率比較

觀察圖3可以發(fā)現(xiàn)與圖1具有類似的實驗結(jié)果，即隨著論域V的不斷增大，非增量式算法更新時所需的時間不斷增大，而增量式算法所需的更新時間大致保持不變，并且遠小于非增量式算法。其主要原因同樣是非增量式算法采用傳統(tǒng)的計算，計算量與數(shù)據(jù)集的規(guī)模相關(guān)，規(guī)模越大計算量越大，而增量式算法只對新增加的數(shù)據(jù)進行相關(guān)計算，然后增量式地更新最終結(jié)果，因此計算時間只與新加入的數(shù)據(jù)量相關(guān)。所以增量式算法具有更高的更新效率。

圖4是論域V中對象減少時，雙論域三支決策在非增量式與增量式兩類算法下的更新效率比較。

圖4 各個數(shù)據(jù)集論域V減少時非增量式與增量式算法的更新效率比較

可以看出，隨著論域V的不斷減小，非增量式算法更新所需的時間也是不斷減小的，而增量式算法所需的更新時間大致保持不變，并且遠小于非增量式算法。其主要原因也是非增量式算法直接對數(shù)據(jù)集進行計算，當數(shù)據(jù)集論域V逐漸減小，因而計算時間也是逐漸減小。增量式算法只對減少的數(shù)據(jù)進行計算，然后在原來模型的結(jié)果上進行進一步更新，因此更新時所需的時間與減少的數(shù)據(jù)量相關(guān)，由于每次減少的數(shù)據(jù)量是一樣的，因此增量式算法的更新時間保持不變。

4.4 實驗總結(jié)

綜合兩部分的實驗結(jié)果可以看出，無論是論域U的動態(tài)更新還是論域V的動態(tài)更新，本文所提出的雙論域三支決策增量式更新算法，只對變化的數(shù)據(jù)進行增量式計算，更新時所需的時間遠低于非增量式更新算法，因此本文算法具有更高的動態(tài)數(shù)據(jù)更新效率。

5 結(jié) 語

針對雙論域信息系統(tǒng)的動態(tài)更新問題，本文在雙論域三支決策模型下提出一種增量式更新算法。分別研究了論域U動態(tài)更新和論域V動態(tài)更新時，雙論域三支決策模型中三個區(qū)域的增量式更新，理論分析表明這種更新方式只需對變化的數(shù)據(jù)進行計算。針對這一更新機制提出了增量式更新算法，實驗結(jié)果表明增量式算法對于動態(tài)雙論域信息系統(tǒng)具有更高的更新效率。由于現(xiàn)實中數(shù)據(jù)的動態(tài)性，本文研究成果有助于推動雙論域三支決策模型在現(xiàn)實環(huán)境下的應(yīng)用，這將是未來的研究重點之一。