袁路妍 李 鋒

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

0 引 言

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

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

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

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

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

1 基本理論

定義1[20]設(shè)雙論域信息系統(tǒng)可表示為S=(U,V),其中U和V為該信息系統(tǒng)下的兩個(gè)論域。記F為從U到V上的二元關(guān)系，對(duì)于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，那么對(duì)于Y?V關(guān)于二元關(guān)系F的下近似和上近似分別定義為：

(2)

(3)

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

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

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

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

其中：

(4)

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

(5)

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

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

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

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

2.1.1對(duì)象增加時(shí)模型的更新

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

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

定理1設(shè)0≤β<α≤1，t時(shí)刻Yt?Vt關(guān)于二元關(guān)系Ft的三個(gè)區(qū)域?yàn)镻OS(Yt)、BUN(Yt)和NEG(Yt)。那么t+1時(shí)刻Yt+1關(guān)于二元關(guān)系Ft+1的三個(gè)區(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))≥α}

對(duì)于?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)。

證畢。

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

2.1.2對(duì)象減少時(shí)模型的更新

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

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

定理2設(shè)0≤β<α≤1，t時(shí)刻Yt?Vt關(guān)于二元關(guān)系Ft的三個(gè)區(qū)域?yàn)镻OS(Yt)、BUN(Yt)和NEG(Yt)。那么t+1時(shí)刻Yt+1關(guān)于二元關(guān)系Ft+1的三個(gè)區(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))≥α}

對(duì)于?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)。

證畢。

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

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

2.2.1對(duì)象增加時(shí)模型的更新

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

定理3對(duì)于?u∈Ut，設(shè)Yt關(guān)于u在二元關(guān)系Ft下的條件概率為P(Yt|Ft(u))，雙論域信息系統(tǒng)更新后，Yt+1=Yt∪Y+關(guān)于對(duì)象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) 的證明過(guò)程類似于(1)。

證畢。

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

定理4設(shè)0≤β<α≤1，t時(shí)刻Yt?Vt關(guān)于二元關(guān)系Ft的三個(gè)區(qū)域?yàn)镻OS(Yt)、BUN(Yt)和NEG(Yt)。那么t+1時(shí)刻Yt+1關(guān)于二元關(guān)系Ft+1的三個(gè)區(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) 對(duì)于?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))的值無(wú)法確定，所以此時(shí)需要分開(kāi)討論，則有:

因此(1)成立。

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

證畢。

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

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

2.2.2對(duì)象減少時(shí)模型的更新

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

定理5對(duì)于?u∈Ut，設(shè)Yt關(guān)于u在二元關(guān)系Ft下的條件概率為P(Yt|Ft(u))，雙論域信息系統(tǒng)更新后，Yt+1=Yt-Y-關(guān)于對(duì)象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) 的證明過(guò)程類似于(1)。

證畢。

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

定理6設(shè)0≤β<α≤1，t時(shí)刻Yt?Vt關(guān)于二元關(guān)系Ft的三個(gè)區(qū)域?yàn)镻OS(Yt)、BUN(Yt)和NEG(Yt)。那么t+1時(shí)刻Yt+1關(guān)于二元關(guān)系Ft+1的三個(gè)區(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))，則：

證明過(guò)程類似于定理4。

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

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

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

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

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

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

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

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

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

3.對(duì)于?u∈Ut+1進(jìn)行判斷：

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

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

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

輸入：更新前后的雙論域信息系統(tǒng)S=(Ut,Vt)和S=(Ut+1,Vt+1)，其中Ut+1=Ut∪U+;閾值參數(shù)α、β和目標(biāo)概念集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.對(duì)于?u∈U+，計(jì)算Yt+1關(guān)于對(duì)象u在二元關(guān)系Ft+1下的條件概率：

3.對(duì)于?u∈U+進(jìn)行判斷：

① 若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中對(duì)象減少時(shí)三支決策的增量式更新算法。在算法3中，只需要對(duì)U-中的對(duì)象進(jìn)行考察分析便可以完成整個(gè)更新過(guò)程，因此算法3的時(shí)間復(fù)雜度為O(|U-|)。

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

輸入：更新前后的雙論域信息系統(tǒng)S=(Ut,Vt)和S=(Ut+1,Vt+1)，其中Ut+1=Ut-U-;閾值參數(shù)α、β和目標(biāo)概念集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.對(duì)于?u∈U-進(jìn)行以下判斷：

① 若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中對(duì)象增加時(shí)三支決策的增量式更新算法。在算法4中，主要的計(jì)算量集中在計(jì)算條件概率P(Y+|F+(u))上，對(duì)于部分條件概率P(Yt+1|Ft+1(u))可采用增量式方法計(jì)算得出，因此整個(gè)算法4的時(shí)間復(fù)雜度為O(|Ut+1||V+|)。

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

輸入：更新前后的雙論域信息系統(tǒng)S=(Ut,Vt)和S=(Ut+1,Vt+1)，其中Vt+1=Vt∪V+；閾值參數(shù)α、β和目標(biāo)概念集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.對(duì)于?u∈Ut+1計(jì)算P(Y+|F+(u))：

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

② 若u∈BUN(Yt),當(dāng)β

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

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

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

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

輸入：更新前后的雙論域信息系統(tǒng)S=(Ut,Vt)和S=(Ut+1,Vt+1)，其中Vt+1=Vt-V-；閾值參數(shù)α、β和目標(biāo)概念集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.對(duì)于?u∈Ut+1計(jì)算P(Y-|F-(u))：

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

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

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

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

4 實(shí)驗(yàn)分析

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

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

4.1 實(shí)驗(yàn)設(shè)計(jì)與參數(shù)設(shè)置

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.4 實(shí)驗(yàn)總結(jié)

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

5 結(jié) 語(yǔ)

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