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

袁路妍 李 鋒

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

0 引 言

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

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

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

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

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

1 基本理論

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

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

(1)

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

(2)

(3)

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

(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)

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

(5)

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

2 雙論域下三支決策的動態更新

由于現實環境下數據的動態性，雙論域信息系統往往處于不斷動態更新之中，因此本節主要研究雙論域信息系統動態變化后三支決策的動態更新問題。由于雙論域的動態更新涉及到兩個論域的變化，因此分別對每個論域進行單獨分析。

2.1 論域U變化時三支決策的動態更新

2.1.1對象增加時模型的更新

根據第1節，三支決策規則的誘導主要取決于三個區域的計算，因此當信息系統發生變化后，研究三支決策的動態更新即轉換為研究三個區域的動態更新。

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

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

(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) 根據正區域的定義有：

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可以發現，當論域U增加對象集U+后，只需要對增加的對象計算相應的三個區域，然后與原來三個區域進行合并便可以更新出最終結果。

2.1.2對象減少時模型的更新

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

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

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

(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) 根據正區域的定義有：

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可以發現，當論域U減少一部分對象U-，只需要對原來三個區域中的對象作出相應的刪除便可以更新出最終結果。

2.2 論域V變化時三支決策的動態更新

2.2.1對象增加時模型的更新

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

定理3對于?u∈Ut，設Yt關于u在二元關系Ft下的條件概率為P(Yt|Ft(u))，雙論域信息系統更新后，Yt+1=Yt∪Y+關于對象u在二元關系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+關于u在二元關系F+下的條件概率。

證明：根據定義有：

這里令:

|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表明，當雙論域信息系統更新后，P(Yt+1|Ft+1(u))值始終介于P(Yt|Ft(u))與P(Y+|F+(u))之間，根據條件概率這一變化規律，可以進一步得到論域V中對象增加時三個區域的增量式更新。

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

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))≥α,根據定理3滿足：

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

因此u∈POS(Yt+1)。

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

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

2.2.2對象減少時模型的更新

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

定理5對于?u∈Ut，設Yt關于u在二元關系Ft下的條件概率為P(Yt|Ft(u))，雙論域信息系統更新后，Yt+1=Yt-Y-關于對象u在二元關系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))

證明：根據定義有:

這里令：

|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)。

證畢。

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

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

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

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

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

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

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

輸入：新的雙論域信息系統S=(Ut+1,Vt+1),閾值參數α、β和目標概念集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關于對象u在二元關系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步中關于條件概率的計算，由于目標概念集Yt+1已經給定，條件概率的計算即為Ft+1(u)的計算，每個對象計算Ft+1(u)的時間復雜度為O(|Vt+1|)，計算Ut+1中所有對象的時間復雜度為O(|Ut+1||Vt+1|)。因此整個算法1的時間復雜度為O(|Ut+1||Vt+1|)。

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

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

輸入：更新前后的雙論域信息系統S=(Ut,Vt)和S=(Ut+1,Vt+1)，其中Ut+1=Ut∪U+;閾值參數α、β和目標概念集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關于對象u在二元關系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所示的是雙論域信息系統下論域U中對象減少時三支決策的增量式更新算法。在算法3中，只需要對U-中的對象進行考察分析便可以完成整個更新過程，因此算法3的時間復雜度為O(|U-|)。

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

輸入：更新前后的雙論域信息系統S=(Ut,Vt)和S=(Ut+1,Vt+1)，其中Ut+1=Ut-U-;閾值參數α、β和目標概念集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所示的是雙論域信息系統下論域V中對象增加時三支決策的增量式更新算法。在算法4中，主要的計算量集中在計算條件概率P(Y+|F+(u))上，對于部分條件概率P(Yt+1|Ft+1(u))可采用增量式方法計算得出，因此整個算法4的時間復雜度為O(|Ut+1||V+|)。

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

輸入：更新前后的雙論域信息系統S=(Ut,Vt)和S=(Ut+1,Vt+1)，其中Vt+1=Vt∪V+；閾值參數α、β和目標概念集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))≥α時u∈POS(Yt+1)，否則根據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)，否則根據P(Y+|F+(u))增量式計算出P(Yt+1|Ft+1(u))，然后根據定理4判別u的隸屬情況。

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

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

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

輸入：更新前后的雙論域信息系統S=(Ut,Vt)和S=(Ut+1,Vt+1)，其中Vt+1=Vt-V-；閾值參數α、β和目標概念集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),否則根據P(Y-|F-(u))增量式計算出P(Yt+1|Ft+1(u))，然后判別u的隸屬情況。

② 若u∈BUN(Yt)，那么根據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),否則根據P(Y-|F-(u))增量式計算出P(Yt+1|Ft+1(u))，然后根據定理6判別u的隸屬情況。

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

4 實驗分析

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

表1 實驗數據集

4.1 實驗設計與參數設置

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.4 實驗總結

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

5 結 語

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