張春英，喬 鵬，王立亞，秦 豪，劉 璐，唐 虎

(1.華北理工大學(xué) 理學(xué)院 河北 唐山 063210；2.河北省數(shù)據(jù)科學(xué)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室 河北 唐山 063210；3.華北理工大學(xué) 信息工程學(xué)院 河北 唐山 063210)

0 引言

三支決策理論是在傳統(tǒng)二支決策只有兩種決策規(guī)則(接受、拒絕)的基礎(chǔ)上， 增加一種決策規(guī)則，即不承諾決策規(guī)則， 從而拓展為包括接受、拒絕和不承諾三個(gè)決策規(guī)則的理論模型[1-7].目前，三支決策理論已成功應(yīng)用在多個(gè)領(lǐng)域中.文獻(xiàn) [8]通過(guò)對(duì)現(xiàn)有的三支決策理論和方法的分析，提出基于集對(duì)信息?？臻g的三支決策模型；文獻(xiàn) [9]建立了基于集對(duì)聯(lián)系熵的三支決策模型；文獻(xiàn) [10]提出了基于概率圖的三支決策模型.這些模型的構(gòu)建都是基于確定的集合，沒(méi)有考慮到集合的動(dòng)態(tài)變化.文獻(xiàn)[11]提出了一種基于區(qū)間概念格的三支決策動(dòng)態(tài)策略調(diào)控模型；文獻(xiàn) [12]提出了動(dòng)態(tài)三支概率粗糙集的統(tǒng)一結(jié)構(gòu)；文獻(xiàn) [13]針對(duì)延遲決策問(wèn)題，以動(dòng)態(tài)視角將基于概率粗糙集的三支決策推廣到一個(gè)序列，提出了一種三支決策的動(dòng)態(tài)決策模型；文獻(xiàn) [14]提出了一種面向決策對(duì)象變化的動(dòng)態(tài)三支決策方法，設(shè)計(jì)了基于概率粗糙集模型的增量式三支決策算法，該算法可以有效利用原有信息系統(tǒng)中所獲得的粒度結(jié)構(gòu)和知識(shí)結(jié)果，從而實(shí)現(xiàn)概率粗糙三支近似地快速更新求解.而在實(shí)際問(wèn)題中，往往會(huì)針對(duì)某信息系統(tǒng)U中的一部分子集X進(jìn)行研究，而X也是動(dòng)態(tài)變化的，既有新的對(duì)象從U中遷入到X中，也有X中對(duì)象遷出返回到U中.

文獻(xiàn)[15-16]提出奇異集(簡(jiǎn)稱S-粗集)，為解決動(dòng)態(tài)系統(tǒng)識(shí)別、動(dòng)態(tài)系統(tǒng)決策、動(dòng)態(tài)系統(tǒng)推理與動(dòng)態(tài)證據(jù)合成等問(wèn)題提供了有力的工具.而雙向概率PS-粗糙集模型[17]既考慮集合的動(dòng)態(tài)特性，又考慮知識(shí)庫(kù)中的統(tǒng)計(jì)信息，提高了決策精度，是Pawlak粗糙集[18-19]和雙向S-粗糙集的進(jìn)一步發(fā)展.文獻(xiàn)[20]首次提出將概率PS-粗糙集與三支決策相融合，構(gòu)建了基于PS-粗糙集的動(dòng)態(tài)三支決策的初步模型，根據(jù)雙向概率PS-粗糙集的上、下近似重新劃分了三支決策中的正域、負(fù)域和邊界域，并基于不同區(qū)域給出了決策規(guī)則，但并未給出具體的算法.因此，在前期研究工作的基礎(chǔ)上，本文進(jìn)一步提出基于PS-粗糙集的動(dòng)態(tài)三支決策算法，根據(jù)對(duì)象的遷入和遷出，討論不同情況下的動(dòng)態(tài)決策算法，并通過(guò)實(shí)驗(yàn)驗(yàn)證了算法的有效性和高效性.

1 概率PS-粗糙集上的三支決策模型

本節(jié)介紹PS-粗糙集的基本定義[17]與基于PS-粗糙集的動(dòng)態(tài)三支決策模型的相關(guān)動(dòng)態(tài)性質(zhì)[20].

定義1設(shè)X*是X?U的雙向S-集合,f∈F是定義在U上的元素遷移,給定一對(duì)閾值(α,β),且滿足0≤β≤α≤1,則稱F-(X*)(α,β)={x|x∈U,Pr(X*|[x]R)≥α}為X*依參數(shù)(α,β)的概率PS-下近似，稱F-(X*)(α,β)={x|x∈U,Pr(X*|[x]R)>β}為X*依參數(shù)(α,β)的概率PS-上近似.稱(F-(X*)(α,β)，F(xiàn)-(X*)(α,β))為X*依參數(shù)(α,β)的概率PS-粗糙集.

根據(jù)概率PS-粗糙集模型可以得到一種新的正域、負(fù)域和邊界域的劃分.

定義2設(shè)X*是X?U的概率PS-粗糙集，X*?U，基于X*的概率PS的上、下近似，則X*的概率PS-粗糙集的正域、負(fù)域、邊界域分別定義為

POS(α,β)(X*)=F-(X*)(α,β)={x|x∈U,Pr(X*|[x]R)≥α}，

NEG(α,β)(X*)=U-F-(X*)(α,β)={x|x∈U,Pr(X*|[x]R)>β}，

BND(α,β)(X*)=F-(X*)(α,β)-F-(X*)(α,β)={x|x∈U,β

設(shè)雙向S-集合X*依參數(shù)(α,β)的概率PS-粗糙集的正域、負(fù)域、邊界域分別為POS(α,β)(X*)、NEG(α,β)(X*)、BND(α,β)(X*),則有

正規(guī)則：Des(x)→接收，x∈X*,[x]R?POS(α,β)(X*)，

負(fù)規(guī)則：Des(x)→拒絕，x∈X*,[x]R?NEG(α,β)(X*)，

邊界規(guī)則：Des(x)→既不接收也不拒絕，x∈X*,[x]R?BND(α,β)(X*).

2 PS-粗糙集上的動(dòng)態(tài)三支決策算法

2.1 動(dòng)態(tài)三支決策的基本思想

在實(shí)際生活中，需要進(jìn)行決策的對(duì)象往往是動(dòng)態(tài)變化的，隨時(shí)有新的對(duì)象遷入或遷出.動(dòng)態(tài)三支決策的基本思想為：在給定決策信息數(shù)據(jù)集的條件下，可以根據(jù)決策屬性進(jìn)行決策分類，通過(guò)給出的確定子集和概率閾值，可以分別計(jì)算出條件概率，并與概率閾值進(jìn)行比較，從而判斷出對(duì)象屬于正域、負(fù)域和邊界域，根據(jù)概率PS-粗糙集上的三支規(guī)則做出接受、拒絕和既不接受也不拒絕的決策.

約定：S=(U,A,d)是一個(gè)決策信息數(shù)據(jù)集，其中U={x1,x2,…,xn}是所有對(duì)象的集合，A={a1,a2,…,am}是條件屬性集合，pfzfxzz是決策屬性.Xq是tq時(shí)刻的對(duì)象子集，設(shè)初始時(shí)刻為t0，子集為X0，按照決策屬性劃分的等價(jià)類為D1,D2,…,Dm，概率閾值為(α,β)，每個(gè)等價(jià)類對(duì)應(yīng)的條件概率分別為p1,p2,…,pm.下面分兩種情況討論動(dòng)態(tài)三支決策的思想.

(1) 僅有對(duì)象單向遷入或單向遷出子集

設(shè)ti時(shí)刻，或者有新對(duì)象加入到子集中，或者子集不變，或者有對(duì)象遷出子集，則每個(gè)時(shí)刻t1,t2,…,tn所對(duì)應(yīng)的子集分別為X1,X2,…,Xn，遷入時(shí)子集之間的關(guān)系為X1?X2?…?Xn，遷出時(shí)子集之間的關(guān)系為X1?X2?…?Xn.設(shè)在ti時(shí)刻相對(duì)于Dj增加或減少的對(duì)象集為Δxj,i，且Δxj,i?Dj，則變化的對(duì)象集的條件概率表示為Pr(Δxj,i|Dj).由定理1和定理2知，

命題1設(shè)ti時(shí)刻新遷入或遷出的對(duì)象為x，x?Dj，則對(duì)Dj中對(duì)象所做決策與ti-1時(shí)刻相同.

命題2設(shè)ti時(shí)刻新遷入的對(duì)象為x，x∈Dj，且遷入新對(duì)象后，有Xi∩Dj=Dj，那么對(duì)Dj中對(duì)象所做決策為接受；設(shè)ti時(shí)刻遷出的對(duì)象為x，x∈Dj，有Xi∩Dj=?，那么對(duì)Dj中對(duì)象所做決策為拒絕.

命題3設(shè)ti時(shí)刻新遷入或遷出的對(duì)象為x，x∈Dj，遷入時(shí)，Xi∩Dj≠Dj，有X0∩Dj?Xi∩Dj，當(dāng)Dj中對(duì)象在t0時(shí)刻所做決策為接受時(shí)，那么在ti時(shí)刻所做決策也為接受.遷出時(shí)，Xi∩Dj≠?，有Xi∩Dj?X0∩Dj，當(dāng)Dj中對(duì)象在t0時(shí)刻所做決策為拒絕時(shí)，那么在ti時(shí)刻所做決策也為拒絕.

命題4設(shè)ti時(shí)刻新遷入或遷出的對(duì)象為x，x∈Dj，遷入時(shí)，Xi∩Dj≠Dj，有X0∩Dj?Xi∩Dj，當(dāng)Dj中對(duì)象在t0時(shí)刻所做決策為既不接受也不拒絕時(shí)，那么在ti時(shí)刻所做決策為：當(dāng)Δp≥α-pj時(shí)，決策為接受；當(dāng)Δp<α-pj時(shí)，決策為既不接受也不拒絕.遷出時(shí)，Xi∩Dj≠?，有Xi∩Dj?X0∩Dj，當(dāng)Dj中對(duì)象在t0時(shí)刻所做決策為既不接受也不拒絕時(shí)，那么在ti時(shí)刻所做決策為：當(dāng)Δp′≥pj-β時(shí)，決策為拒絕；當(dāng)Δp′

命題5設(shè)ti時(shí)刻新遷入或遷出的對(duì)象為x，x∈Dj，遷入時(shí)，Xi∩Dj≠Dj，有X0∩Dj?Xi∩Dj，當(dāng)Dj中對(duì)象在t0時(shí)刻所做決策為拒絕時(shí)，那么在ti時(shí)刻所做決策為：當(dāng)Δp≥α-pj時(shí)，決策為接受；當(dāng)β-pj<Δp<α-pj時(shí)，決策為既不接受也不拒絕；當(dāng)Δp≤β-pj時(shí)，決策為拒絕.遷出時(shí)，Xi∩Dj≠?，有Xi∩Dj?Xi-1∩Dj，當(dāng)Dj中對(duì)象在t0時(shí)刻所做決策為接受時(shí)，那么在ti時(shí)刻所做決策為：當(dāng)Δp′≤pj-α?xí)r，決策為接受；當(dāng)pj-α<Δp′

(2) 同時(shí)有對(duì)象遷入/遷出子集

設(shè)ti時(shí)刻同時(shí)有元素遷入和遷出，設(shè)子集為Xi，若Xi-1∩Xi≠?，設(shè)Xi-1∩Xi=Y，Xi相當(dāng)于在子集Y中遷入了新的對(duì)象，計(jì)算出Y的條件概率，可以用情況(1)中的方法對(duì)Xi中的對(duì)象進(jìn)行決策；若Xi-1∩Xi=?，此時(shí)Xi中的對(duì)象為新遷入的全部對(duì)象，需要重新計(jì)算條件概率，并由決策規(guī)則進(jìn)行決策.

2.2 算法描述

算法基于PS-粗糙集的動(dòng)態(tài)三支決策算法.

輸入： 數(shù)據(jù)集U，子集X，等價(jià)類Dj(j=1,2,…)，不同時(shí)刻遷入對(duì)象子集It(t=1,2，…)/不同時(shí)刻遷出對(duì)象子集Ot(t=1,2，…)；

輸出： 不同時(shí)刻的決策D={Dj|Dj∈POSITIVE}(j=1,2,…)或D={Dj|Dj∈BOUNDARY}(j=1,2,…)或D={Dj|Dj∈NEGATIVE}(j=1,2,…).

Step1計(jì)算初始時(shí)刻X在每個(gè)等價(jià)類Dj下的條件概率pj，由決策規(guī)則做出初始時(shí)刻的決策.

Step2當(dāng)遷入新對(duì)象集It(t=1,2，…)時(shí)，判斷新對(duì)象集It中的元素x是否屬于Dj.若x?Dj，則決策不變；若x∈Dj，判斷Xi∩Dj是否等于Dj.若Xi∩Dj=Dj，則輸出D={Dj|Dj∈POSITIVE}，決策為接受.若Xi∩Dj≠Dj，初始時(shí)刻決策為接受，輸出D={Dj|Dj∈POSITIVE}，決策為接受.若Xi∩Dj≠Dj，初始時(shí)刻決策為既不接受也不拒絕，當(dāng)Δp≥α-pj時(shí)，輸出D={Dj|Dj∈POSITIVE}，決策為接受；當(dāng)Δp<α-pj時(shí)，輸出D={Dj|Dj∈BOUNDARY}，決策為既不接受也不拒絕.若Xi∩Dj≠Dj，初始時(shí)刻決策為拒絕，當(dāng)Δp≥α-pj時(shí)，輸出D={Dj|Dj∈POSITIVE}，決策為接受；當(dāng)β-pj<Δp<α-pj時(shí)，輸出D={Dj|Dj∈BOUNDARY}，決策為既不接受也不拒絕；當(dāng)Δp≤β-pj時(shí)，輸出D={Dj|Dj∈NEGATIVE}，決策為拒絕.

Step3當(dāng)遷出對(duì)象集Ot(t=1,2，…)時(shí)，判斷遷出對(duì)象集Ot中的元素x是否屬于Dj.若x?Dj，則決策不變；若x∈Dj，判斷Xi∩Dj是否等于?.若Xi∩Dj=?，則輸出D={Dj|Dj∈NEGATIVE}，決策為拒絕.若Xi∩Dj≠?，初始時(shí)刻決策為拒絕，輸出D={Dj|Dj∈NEGATIVE}，決策為拒絕.若Xi∩Dj≠?，初始時(shí)刻為既不接受也不拒絕，當(dāng)Δp′≥pj-β時(shí)，輸出D={Dj|Dj∈NEGATIVE}，決策為拒絕；當(dāng)Δp′

Step4當(dāng)有對(duì)象集遷入和遷出時(shí)，判斷Xi-1∩Xi是否等于?.若Xi-1∩Xi=?，則計(jì)算Xi的條件概率，根據(jù)規(guī)則決策；若Xi-1∩Xi≠?，記Xi-1∩Xi=Y，把Y當(dāng)作初始時(shí)刻的子集，計(jì)算條件概率，Xi為Y遷入元素后的子集，按照遷入時(shí)的情況判斷即可.

Step5遷入/遷出對(duì)象子集是否為空，如果不為空，轉(zhuǎn)到Step 2，否則結(jié)束.

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

3.1 實(shí)驗(yàn)環(huán)境

選取了一組UCI數(shù)據(jù)集中用于活動(dòng)識(shí)別的數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)，共有50 000個(gè)對(duì)象作為信息系統(tǒng)U，該數(shù)據(jù)集有三個(gè)條件屬性和一個(gè)決策屬性，根據(jù)決策屬性將對(duì)象集分為三個(gè)等價(jià)類，分別為D1(由第1～20 000個(gè)對(duì)象組成)、D2(由第20 001～40 000個(gè)對(duì)象組成)和D3(由第40 001～50 000個(gè)對(duì)象組成).隨機(jī)選取14 000、25 000和22 000個(gè)對(duì)象作為子集進(jìn)行對(duì)象單向遷入、單向遷出和雙向遷入/遷出實(shí)驗(yàn).該實(shí)驗(yàn)在處理器為X64、RAM為4 GB的WIN10系統(tǒng)環(huán)境下用Java實(shí)現(xiàn)，通過(guò)選取子集Xi，對(duì)在Xi下三個(gè)等價(jià)類中的對(duì)象如何決策進(jìn)行分析，并通過(guò)不斷遷入/遷出對(duì)象到Xi，分析不同時(shí)刻等價(jià)類中對(duì)象的決策規(guī)律，決策結(jié)果中的1a、2a和3a分別表示拒絕、不承諾和接受決策.

3.2 對(duì)象單向遷入實(shí)驗(yàn)與分析

隨機(jī)選取14 000個(gè)對(duì)象作為實(shí)驗(yàn)子集X1，由1～4 000、20 001～25 000、40 001～45 000個(gè)對(duì)象構(gòu)成，t1～t10時(shí)刻分別遷入新的子集，其中t1時(shí)刻的遷入子集I1={10 001～11 000,25 001～26 000,45 001～45 500}，t2時(shí)刻的遷入子集I2={11 001～13 000,26 001～27 000,45 501～46 000}，…，t10時(shí)刻的遷入子集I10={18 001～20 000}.設(shè)定概率閾值為(0.5,0.2),單向遷入實(shí)驗(yàn)結(jié)果如圖1所示.

經(jīng)過(guò)分析可知，t0時(shí)刻，由于子集中相對(duì)D1的對(duì)象個(gè)數(shù)較少，可以看出，D1、D2和D3分別屬于負(fù)域、邊界域和正域，根據(jù)決策規(guī)則，對(duì)三個(gè)等價(jià)類中的對(duì)象分別執(zhí)行拒絕、既不接受也不拒絕和接受決策；在之后的每一個(gè)時(shí)刻，當(dāng)有元素不斷遷入到子集時(shí)，D3的決策在每一個(gè)時(shí)刻都為接受；t1時(shí)刻，有新的對(duì)象遷入到子集X1中，因?yàn)檫w入對(duì)象屬于D1等價(jià)類的相對(duì)較多，導(dǎo)致條件概率增加，對(duì)D1中對(duì)象做出的決策由拒絕變?yōu)榧炔唤邮芤膊痪芙^，而子集對(duì)象相對(duì)D2的條件變化較小，因此決策不變；t2和t3時(shí)刻，雖然有新的對(duì)象遷入，條件概率相對(duì)增加但變化量不大，因此決策沒(méi)有發(fā)生變化；t4時(shí)刻，D2的條件概率大于等于0.5，因此決策由不承諾變?yōu)榻邮?；t5時(shí)刻，每個(gè)等價(jià)類的條件概率都滿足決策為接受時(shí)的條件，因此對(duì)每個(gè)對(duì)象都做出接受決策.由結(jié)果可以看出，從t5時(shí)刻開(kāi)始，三個(gè)等價(jià)類決策都為接受，當(dāng)子集中不斷地遷入新的對(duì)象時(shí)，決策都不會(huì)發(fā)生變化.

3.3 對(duì)象單向遷出實(shí)驗(yàn)與分析

選取25 000個(gè)對(duì)象作為實(shí)驗(yàn)子集X2，由1～15 000、20 001～34 000、40 001～46 000個(gè)對(duì)象構(gòu)成，t1～t10時(shí)刻分別從子集中遷出對(duì)象，其中t1時(shí)刻的遷出子集O1={1～1 000,20 001～21 000,40 001～41 000}，t2時(shí)刻的遷出子集O2={1 001～2 000,21 001～23 000,41 001～42 000}，…，t10時(shí)刻的遷出子集O10={14 001～15 000,33 001～34 000}.設(shè)定概率閾值為(0.7,0.3)，單向遷出實(shí)驗(yàn)結(jié)果如圖2所示.

圖1 單向遷入實(shí)驗(yàn)結(jié)果Fig.1 The experiment result of one-way moving in

圖2 單向遷出實(shí)驗(yàn)結(jié)果Fig.2 The experiment result of one-way moving out

t0時(shí)刻，子集中屬于D1和D2的對(duì)象相對(duì)較多，根據(jù)決策規(guī)則做出接受決策，而屬于D3的對(duì)象相對(duì)較少，由概率閾值判斷出D3屬于邊界域，因此做出既不接受也不拒絕決策；t1時(shí)刻，有對(duì)象從子集中遷出，概率閾值均減小，因?yàn)镈2的條件概率減少得相對(duì)較多，所屬區(qū)域變?yōu)檫吔缬?，因此決策需要進(jìn)一步觀察，而其他等價(jià)類的條件概率變化較小，決策不變；t2時(shí)刻，D1的條件概率減少到低于0.7，決策發(fā)生變化，此時(shí)三個(gè)等價(jià)類的決策都為不承諾；t3時(shí)刻，D3的條件概率減少，屬于負(fù)域，因此，對(duì)D3的對(duì)象做出拒絕決策，在之后的每一個(gè)時(shí)刻，D3的條件概率都在下降或不變，而決策也不再變化，均為拒絕；t4和t5時(shí)刻，遷出對(duì)象后導(dǎo)致D1和D2的條件概率減少較多，因此對(duì)D1和D2做出不承諾決策；t6時(shí)刻，D2條件概率減少較多，變化較大，此時(shí)對(duì)D2做出拒絕決策；t7時(shí)刻，有對(duì)象的遷出，D1的條件概率減少到低于0.3，決策變?yōu)榫芙^；t7時(shí)刻之后，D1、D2和D3均屬于負(fù)域，對(duì)所有對(duì)象做出拒絕決策.

圖3 雙向遷入/遷出實(shí)驗(yàn)結(jié)果Fig.3 The experiment result of two-way moving in/out

3.4 對(duì)象雙向遷入/遷出實(shí)驗(yàn)與分析

選取22 000個(gè)對(duì)象作為實(shí)驗(yàn)子集X3，由1～10 000、20 001～25 000、40 01～47 000個(gè)對(duì)象構(gòu)成，t1～t5時(shí)刻分別從子集中遷入/遷出對(duì)象.設(shè)定概率閾值為(0.6,0.3)，雙向遷入/遷出實(shí)驗(yàn)結(jié)果如圖3所示.

t0時(shí)刻，根據(jù)概率閾值及相應(yīng)的決策規(guī)則可知，對(duì)D1中對(duì)象做出的決策為既不接受也不拒絕，對(duì)D2中對(duì)象做出的決策為拒絕，對(duì)D3中對(duì)象做出的決策為接受；t1時(shí)刻，相對(duì)于每個(gè)等價(jià)類的條件概率變化幅度較小，因此決策沒(méi)有變化；t2和t3時(shí)刻，遷入了相對(duì)較多的D2中的對(duì)象，其他等價(jià)類下遷入和遷出的較少，因此只有D2的決策發(fā)生變化，由拒絕變?yōu)榧炔唤邮芤膊痪芙^；t4時(shí)刻，子集中屬于D3的對(duì)象沒(méi)有變化，決策也沒(méi)有變化，相對(duì)D2遷入了大量新的對(duì)象，只有少量的遷出，由此導(dǎo)致條件概率改變較大，做出的決策變?yōu)榻邮?；t5時(shí)刻，子集中相對(duì)D1和D3遷出的對(duì)象多于遷入的對(duì)象，因此兩個(gè)等價(jià)類下的決策均發(fā)生改變，而D2的條件概率變化值較小，決策沒(méi)有變化.

三組數(shù)據(jù)子集以及遷入和遷出的對(duì)象集都是隨機(jī)選取的，從圖1～3中可以看出，算法給出的實(shí)驗(yàn)結(jié)果能清晰地判斷決策類型，子集的不同、對(duì)象的遷入/遷出和概率閾值的設(shè)定都會(huì)影響決策結(jié)果的變化，同時(shí)也會(huì)影響決策的準(zhǔn)確性.在后續(xù)的研究中，將繼續(xù)討論閾值設(shè)定對(duì)子集變化的影響.

4 結(jié)束語(yǔ)

本文提出了一個(gè)基于概率PS-粗糙集的三支決策動(dòng)態(tài)算法，根據(jù)對(duì)象的遷入和遷出，討論不同情況下的動(dòng)態(tài)決策算法，進(jìn)行了對(duì)象的單向遷入、單向遷出和雙向遷入/遷出實(shí)驗(yàn)，通過(guò)實(shí)驗(yàn)驗(yàn)證了算法的有效性和高效性.該動(dòng)態(tài)算法還涉及很多的問(wèn)題有待進(jìn)一步研究，例如概率閾值的優(yōu)化、邊界域?qū)ο蟮淖顑?yōu)化處理方案和在具體決策中的應(yīng)用等.