廣義多尺度集值決策系統(tǒng)最優(yōu)尺度選擇

胡 軍 陳 艷 張清華 王國(guó)胤

1(計(jì)算智能重慶市重點(diǎn)實(shí)驗(yàn)室(重慶郵電大學(xué)) 重慶 400065)

2(重慶郵電大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 重慶 400065)

(hujun@cqupt.edu.cn)

在實(shí)際應(yīng)用中，人們可能要在不同的粒度下對(duì)同一對(duì)象進(jìn)行觀察、表示、分析和決策，即對(duì)一個(gè)對(duì)象和某個(gè)屬性，根據(jù)實(shí)際問題的不同粒度層次的需要，可取不同的值.針對(duì)上述多粒度描述的問題，Wu等人[1]提出了一種稱為多尺度信息系統(tǒng)的知識(shí)表示系統(tǒng).在多尺度信息系統(tǒng)中，一個(gè)對(duì)象根據(jù)不同的度量尺度，在每個(gè)屬性上可以有多個(gè)不同取值，且不同尺度空間存在從細(xì)到粗的信息粒轉(zhuǎn)換.多尺度廣泛存在于地理空間分布、圖像分析等多個(gè)研究領(lǐng)域[2-9].

目前，學(xué)者已經(jīng)對(duì)多尺度信息系統(tǒng)進(jìn)行了大量研究.Wu等人[1,10-11]介紹了多尺度決策系統(tǒng)的最優(yōu)尺度選擇方法及規(guī)則獲取.從一致性角度考慮，Xu等人[12]及Wu等人[13-15]研究了多尺度決策系統(tǒng)的最優(yōu)尺度選擇方法.Hao等人[16]考慮到數(shù)據(jù)的動(dòng)態(tài)變化，利用三支決策的方法研究了動(dòng)態(tài)多尺度決策系統(tǒng)的最優(yōu)尺度選擇方法.鐵文彥等人[17]討論了對(duì)象動(dòng)態(tài)更新情況下多粒度決策系統(tǒng)的最優(yōu)粒度選擇.顧沈明等人[18]定義了局部最優(yōu)粒度，研究了多尺度決策系統(tǒng)的局部最優(yōu)粒度和規(guī)則提取方法.Chen等人[19]為了簡(jiǎn)化最優(yōu)尺度選擇的計(jì)算過程，研究了基于矩陣的多尺度決策系統(tǒng)的最優(yōu)尺度選擇方法.以上研究假設(shè)多尺度信息系統(tǒng)中所有屬性都具有相同尺度級(jí)數(shù)，Li等人[20]針對(duì)每個(gè)屬性具有不同尺度級(jí)數(shù)的情況，定義了廣義多尺度信息系統(tǒng)，并提出補(bǔ)充模型和格點(diǎn)模型來分析廣義多尺度決策系統(tǒng)的最優(yōu)尺度選擇，此后又提出了基于屬性重要度的逐步最優(yōu)尺度選擇方法[21].Wu等人[22]討論了廣義多尺度決策系統(tǒng)中幾種最優(yōu)尺度組合之間的關(guān)系.牛東苒等人[23]通過引入概率粗糙集，研究了可變精度下廣義多尺度決策系統(tǒng)的最優(yōu)尺度選擇方法.Cheng等人[24-25]提出了基于序貫三支決策的最優(yōu)尺度選擇和屬性約簡(jiǎn)方法.

文獻(xiàn)[1-25]研究假設(shè)對(duì)象在屬性各個(gè)尺度的取值都是唯一的，然而一些實(shí)際問題卻不滿足這一假設(shè)[26-31].為此，陳艷等人[32]提出了多尺度集值信息系統(tǒng)，給出了4種最優(yōu)尺度選擇方法，并討論了在一致/不一致多尺度集值信息系統(tǒng)中它們之間的關(guān)系.該研究假設(shè)所有屬性具有相同的尺度級(jí)數(shù)，使得屬性只能在同一個(gè)尺度下進(jìn)行組合.其次，最優(yōu)尺度選擇僅考慮決策系統(tǒng)的一致性或不確定性，忽略了實(shí)際應(yīng)用中的代價(jià)問題，無法滿足用戶的個(gè)性化需求.

于是，針對(duì)不同屬性具有不同數(shù)量的尺度及獲取不同尺度數(shù)據(jù)的代價(jià)不同2個(gè)問題，本文對(duì)多尺度集值信息系統(tǒng)進(jìn)行了擴(kuò)展，提出具有代價(jià)的廣義多尺度集值信息系統(tǒng).在廣義多尺度集值信息系統(tǒng)中，每個(gè)屬性的尺度級(jí)數(shù)不同，在遍歷每個(gè)屬性的所有尺度時(shí)，針對(duì)尺度組合爆炸問題，提出了一種尺度空間更新方法，有效減少尺度空間中尺度組合數(shù)量；然后，綜合考慮不確定性和代價(jià)2個(gè)因素的影響，提出了其最優(yōu)尺度選擇方法，可以快速地找到?jīng)Q策或分類結(jié)果最優(yōu)且滿足用戶需求的尺度.

1 基本概念

本節(jié)主要介紹多尺度信息系統(tǒng)[1]及多尺度集值信息系統(tǒng)[32]的基本概念.

2 廣義多尺度集值信息系統(tǒng)

本節(jié)主要給出廣義多尺度集值信息系統(tǒng)的概念及相關(guān)性質(zhì)，并討論不同尺度組合下決策系統(tǒng)的不確定性和代價(jià)變化趨勢(shì).

2.1 廣義多尺度集值信息系統(tǒng)

現(xiàn)有關(guān)于多尺度集值信息系統(tǒng)的研究假設(shè)每個(gè)屬性的尺度級(jí)數(shù)都相同，然而實(shí)際問題中不同屬性的尺度級(jí)數(shù)可能不同，因而需要對(duì)其做進(jìn)一步推廣.

本文的研究基于集值的合取語(yǔ)義，即一個(gè)集值表示一個(gè)對(duì)象在某個(gè)屬性下所有的值，并且它們都為真.

例1.表1是某行業(yè)關(guān)于供應(yīng)商的信息調(diào)查與評(píng)價(jià)，其中U={x1,x2,…,x10}表示10個(gè)供應(yīng)商，屬性a1,a2,a3分別代表產(chǎn)品質(zhì)量、配送效率和服務(wù)水平，且它們擁有不同的尺度級(jí)數(shù)，即I1=4,I2=3,I3=2，屬性取值“E”“G”“F”“P”“B”“S”“M”“L”“Y”“N”分別表示“Excellent”“Good”“Fair”“Pass”“Bad”“Super”“Middle”“Low”“Yes”“No”[33].

Table 1 A Generalized Multi-Scale Set-Valued Information System表1 廣義多尺度集值信息系統(tǒng)

例2.在例1所示的廣義多尺度集值信息系統(tǒng)中，其尺度空間ψ={(1,1,1),(2,1,1),(1,1,2),(1,2,1),(3,1,1),(2,1,2),(2,2,1),(1,2,2),(1,3,1),(4,1,1),(3,2,1),(3,1,2),(2,3,1),(2,2,2),(1,3,2),(4,2,1),(4,1,2),(3,3,1),(3,2,2),(2,3,2),(4,3,1),(4,2,2),(3,3,2),(4,3,2)}.

定義5.已知目標(biāo)集合X?U，K是S的一個(gè)尺度組合，則X關(guān)于K的上、下近似集分別為

在尺度組合K下，通過上、下近似集，可將論域U劃分為3個(gè)互不相交的區(qū)域，即正域、負(fù)域和邊界域：

其中POSAK(X)表示一定屬于X的對(duì)象集，NEGAK(X)表示一定不屬于X的對(duì)象集，BNDAK(X)表示不能確定是否屬于X的對(duì)象集.

關(guān)于決策屬性d的等價(jià)關(guān)系為Rd={(x,y)∈U×U|d(x)=d(y)}，則可將論域劃分為U/Rd={D1,D2,…,Dr}，其中Dj,j=1,2,…,r表示不同的決策類.

假設(shè)SK和SK′分別是廣義多尺度集值決策系統(tǒng)S關(guān)于尺度組合K和K′的單尺度集值決策系統(tǒng)，且KK′.由定義7及可知，若單尺度集值決策系統(tǒng)SK是不一致的，則SK′也是不一致的；并且，若單尺度集值決策系統(tǒng)SK′是一致的，則SK也是一致的.

2.2 廣義多尺度集值決策系統(tǒng)的不確定性

為了定量分析不同尺度下的不確定性，下面給出廣義多尺度集值決策系統(tǒng)的不確定性度量.由于正域和負(fù)域的對(duì)象都是確定的，因此目標(biāo)概念的不確定性僅來自邊界域.于是，基于相似關(guān)系R，X?U關(guān)于尺度組合K的不確定性可以度量為[34]

作文教學(xué)效率的高低在一定程度上決定著語(yǔ)文教學(xué)的成敗。但提起寫作文，卻令不少師生感到為難。如何幫助學(xué)生突破寫作瓶頸，讓初中生愛上寫作并寫出好作文，進(jìn)而提高寫作水平呢？采取有效的作文教學(xué)策略是關(guān)鍵。

因此，若2個(gè)尺度組合滿足KK′，則始終可以得到

證畢.

定理1表明，在廣義多尺度集值決策系統(tǒng)中，尺度組合越粗，目標(biāo)概念X的不確定性越大.

2.3 廣義多尺度集值決策系統(tǒng)的代價(jià)

在決策過程中，不同尺度的數(shù)據(jù)，其測(cè)試代價(jià)往往不同，且對(duì)邊界域?qū)ο筮M(jìn)行延遲決策會(huì)產(chǎn)生延遲代價(jià).本節(jié)主要討論廣義多尺度集值決策系統(tǒng)中的測(cè)試代價(jià)和延遲代價(jià).

Table 2 A Generalized Multi-Scale Set-Valued Information System with Test Cost and Delay Cost表2 具有測(cè)試代價(jià)和延遲代價(jià)的廣義多尺度集值決策系統(tǒng)

定義10.已知廣義多尺度集值決策系統(tǒng)S=(U,A∪j5i0abt0b,V,F,η,ω)，X?U.X關(guān)于尺度組合K的延遲代價(jià)定義為

其中,BNDAK(X)是在尺度組合K下的邊界域?qū)ο蠹?，ωxi是關(guān)于xi延遲決策的代價(jià)，即決策系統(tǒng)SK的延遲代價(jià)為尺度組合K下邊界域?qū)ο蠹舆t決策的代價(jià).

定義11.在廣義多尺度集值決策系統(tǒng)S=(U,A∪j5i0abt0b,V,F,η,ω)中，X?U.X關(guān)于尺度組合K的總代價(jià)為

COSTK(X)=TCK+DCK(X).

其中,TCK是在尺度組合K下獲取所有對(duì)象屬性值的測(cè)試代價(jià)，DCK(X)是在尺度組合K下邊界域?qū)ο蠹难舆t代價(jià).

定理2.已知S=(U,A∪j5i0abt0b,V,F,η,ω)是一個(gè)具有測(cè)試代價(jià)和延遲價(jià)的廣義多尺度集值決策系統(tǒng)，X?U.K和K′是關(guān)于S的2個(gè)尺度組合，當(dāng)KK′時(shí)，可以得到TCK≤TCK′.

證畢.

定理3.已知S=(U,A∪j5i0abt0b,V,F,η,ω)是一個(gè)具有測(cè)試代價(jià)和延遲代價(jià)的廣義多尺度集值決策系統(tǒng)，X?U.K和K′是關(guān)于S的2個(gè)尺度組合，當(dāng)KK′時(shí)，可以得到DCK(X)≤DCK′(X).

證明.假設(shè)尺度組合K下邊界域?yàn)镋1,尺度組合K′下邊界域?yàn)镋2，當(dāng)KK′時(shí)，X關(guān)于尺度組合K和K′的粗糙近似關(guān)系有及根據(jù)邊界域定義可以得到E1?E2.因此，對(duì)于?x∈BNDAK(X),始終滿足x∈BNDAK′(X)，于是得到DCK(X)≤DCK′(X).

證畢.

可以看出，隨著尺度組合變粗，其對(duì)應(yīng)單尺度集值決策系統(tǒng)的延遲代價(jià)逐漸增大，測(cè)試代價(jià)逐漸減小，而總代價(jià)不具有單調(diào)性.

3 廣義多尺度集值決策系統(tǒng)最優(yōu)尺度選擇

現(xiàn)有的最優(yōu)尺度選擇方法，大多是從決策系統(tǒng)的一致性或不確定性的角度出發(fā)，沒有考慮到實(shí)際場(chǎng)景中的代價(jià)問題.因此，本節(jié)主要結(jié)合不確定性和代價(jià)，以用戶需求為前提，找到?jīng)Q策或分類最優(yōu)的尺度.

3.1 基于序貫三支決策的尺度空間更新

在廣義多尺度集值決策系統(tǒng)中，當(dāng)屬性的尺度級(jí)數(shù)較大時(shí)，遍歷每個(gè)屬性的所有尺度將會(huì)導(dǎo)致尺度組合爆炸，計(jì)算成本較高.因此，這里基于序貫三支決策思想提出一種能有效減少一致性判斷時(shí)間的尺度空間更新方法.

定義12.假設(shè)存在尺度組合K∈ψ，那么關(guān)于K的上、下邊界定義為

UBψ(K)={K′|K′∈ψ,K′?K}，
LBψ(K)={K′|K′∈ψ,K′K}.

其中,UBψ(K)表示尺度空間ψ中所有較K更粗的尺度組合，LBψ(K)表示尺度空間ψ中所有較K更細(xì)的尺度組合.

假設(shè)需進(jìn)行一致性判斷的尺度組合集合為UNC(ψ0)=ψ，其中ψ是S的初始尺度空間，第i-1次更新后決策結(jié)果分別為ACK(ψi-1)，REJ(ψi-1)，UNC(ψi-1)，則需進(jìn)一步判斷的尺度組合集合為ψi=UNC(ψi-1).通過引入序貫三支決策思想對(duì)UNC(ψi-1)中的尺度組合進(jìn)行判斷可得到第i次更新后尺度空間的決策結(jié)果分別為

ACK(ψi)={Ki}∪ACK(ψi-1)，
REJ(ψi)={Kj}∪UBψi(Kj)∪REJ(ψi-1)，
UNC(ψi)=ψi-ACK(ψi)-REJ(ψi).

其中,Ki是尺度空間第i層滿足一致性的尺度組合，Kj是尺度空間第i層不滿足一致性的尺度組合，UBψi(Kj)為尺度組合Kj的上邊界，UNC(ψi)表示i次更新后需進(jìn)行一致性判斷的尺度組合.當(dāng)UNC(ψi)=?，可以得到S中所有一致的單尺度集值決策系統(tǒng)的尺度組合，即更新后的尺度空間ψ′=ACK(ψi).

因此，可得到尺度空間更新算法：

算法1.廣義多尺度集值決策系統(tǒng)尺度空間更新.

輸入：廣義多尺度集值決策系統(tǒng)S=(U,A∪j5i0abt0b,V,F);

輸出：更新后的尺度空間ψ′.

① 初始化ψ={K=(l1,l2,…,lm)|1≤lj≤Ij,j=1,2,…,m},ACK(ψ0)=?,

REJ(ψ0)=?,UNC(ψ0)=ψ,

ψi=UNC(ψi-1)(i≥1);

② whileUNC(ψi-1)≠? do

③ for eachK∈UNC(ψi-1) do

⑤ACK(ψi)←{K}∪ACK(ψi-1);

⑥ else

⑦REJ(ψi)←{K}∪UBψi(K)∪

REJ(ψi-1);

⑧ end if

⑨UNC(ψi)←UNC(ψi-1)-ACK(ψi)-REJ(ψi);

⑩i++;

算法1首先計(jì)算了廣義多尺度集值決策系統(tǒng)的尺度空間，時(shí)間復(fù)雜度為O(I1×I2×…×Im).然后針對(duì)尺度空間中尺度組合對(duì)應(yīng)的決策系統(tǒng)進(jìn)行一致性判斷，其中每個(gè)相似類的計(jì)算需要時(shí)間復(fù)雜度為O(m×|U|).在最壞情況下，假設(shè)所有尺度組合的決策系統(tǒng)都是一致的，需進(jìn)行|ψ|=I1×I2×…×Im次判斷，所以算法1總的時(shí)間復(fù)雜度為O(m×|U|×|ψ|).

下面舉例說明尺度空間更新的計(jì)算過程.

Fig. 1 The scale space of generalized multi-scaleset-valued decision system圖1 廣義多尺度集值決策系統(tǒng)的尺度空間

例3.根據(jù)例2可知，廣義多尺度集值決策系統(tǒng)S的尺度空間如圖1(a)所示.通過計(jì)算可以得到：

第1層關(guān)于尺度組合(1,1,1)的決策系統(tǒng)S(1,1,1)是一致的，則ACK(ψ0)={(1,1,1)}，REJ(ψ0)=?，UNC(ψ0)=ψ-ACK(ψ0)=ψ1.

第2層尺度組合(2,1,1),(1,1,2),(1,2,1)是一致的，則ACK(ψ1)={(1,1,1),(2,1,1),(1,1,2),(1,2,1)},REJ(ψ1)=?，UNC(ψ1)=ψ1-ACK(ψ1)=ψ2.

第3層尺度組合(3,1,1),(1,2,2),(1,3,1)是一致的，(2,1,2),(2,2,1)是不一致的.根據(jù)圖1(b)(c)可知UBψ2(2,1,2)={(3,1,2),(2,2,2),(4,1,2),(3,2,2),(4,2,2),(3,3,2),(4,3,2)},UBψ2(2,2,1)={(3,2,1),(2,3,1),(2,2,2),(4,2,1),(3,3,1),(3,2,2),(2,3,2),(4,3,1),(4,2,2),(3,3,2),(4,3,2)},則ACK(ψ2)={(1,1,1),(2,1,1),(1,1,2),(1,2,1),(3,1,1),(1,2,2),(1,3,1)}，REJ(ψ2)={(2,1,2),(2,2,1)}，UNC(ψ2)=ψ2-ACK(ψ2)-REJ(ψ2)={(4,1,1),(1,3,2)}=ψ3.

第4層尺度組合(4,1,1),(1,3,2)是一致的，則ACK(ψ3)={(1,1,1),(2,1,1),(1,1,2),(1,2,1),(3,1,1),(1,2,2),(1,3,1),(4,1,1),(1,3,2)},REJ(ψ3)={(2,1,2),(2,2,1)},UNC(ψ3)=?.

于是，更新的尺度空間ψ′=ACK(ψ3)={(1,1,1),(2,1,1),(1,1,2),(1,2,1),(3,1,1),(1,2,2),(1,3,1),(4,1,1),(1,3,2)}.

可以發(fā)現(xiàn)，廣義多尺度集值決策系統(tǒng)的初始尺度空間|ψ|=I1×I2×I3=24，即需進(jìn)行24次一致性判斷，而更新后的尺度空間|ψ′|=9，且只需11次一致性判斷即可得到所有一致的單尺度集值決策系統(tǒng).因此，對(duì)于尺度級(jí)數(shù)較高的廣義多尺度集值決策系統(tǒng)，該尺度空間更新方法能有效地提高計(jì)算效率.

3.2 最優(yōu)尺度選擇

定義14.已知S=(U,A∪j5i0abt0b,V,F,η,ω)是一個(gè)具有測(cè)試代價(jià)和延遲代價(jià)的廣義多尺度集值決策系統(tǒng)，X?U.那么，X關(guān)于尺度組合K的評(píng)價(jià)為

因此，在滿足用戶需求的情況下，以最小化不確定性和代價(jià)為目標(biāo)建立最優(yōu)尺度選擇模型，具體為：

其中,Huser和Costuser分別是用戶對(duì)于不確定性和代價(jià)的需求.

該模型以用戶需求為約束條件，根據(jù)最小化評(píng)價(jià)來選擇最優(yōu)尺度.對(duì)于一個(gè)廣義多尺度集值決策系統(tǒng)，有可能存在一組滿足用戶需求的可行解.由于該模型需要同時(shí)優(yōu)化2個(gè)目標(biāo)且目標(biāo)之間存在沖突，即一個(gè)目標(biāo)性能的提高是以犧牲另一個(gè)目標(biāo)為代價(jià)的.例如，在滿足約束條件可行的解決方案中，有些是低代價(jià)高不確定性的，有些是低不確定性高代價(jià)的.為此，通過引入理想解來計(jì)算可行解與理想解的差值，差值越小則表明越接近理想解，那么最接近理想解的尺度為最優(yōu)尺度.

定義16.已知S=(U,A∪j5i0abt0b,V,F,η,ω)是一個(gè)具有測(cè)試代價(jià)和延遲代價(jià)的廣義多尺度集值決策系統(tǒng)，基于加權(quán)的最優(yōu)尺度選擇模型為

其中,DifK表示加權(quán)差異程度，θ∈[0,1]表示加權(quán)系數(shù).加權(quán)系數(shù)θ可根據(jù)用戶需求進(jìn)行設(shè)置，當(dāng)θ=0時(shí)，該模型退化為基于代價(jià)的最優(yōu)尺度選擇；當(dāng)θ=1時(shí)，該模型退化為基于不確定性的最優(yōu)尺度選擇.

因此，可以設(shè)計(jì)廣義多尺度集值決策系統(tǒng)最優(yōu)尺度選擇算法為：

算法2.廣義多尺度集值決策系統(tǒng)最優(yōu)尺度選擇.

輸入：廣義多尺度集值決策系統(tǒng)S=(U,A∪j5i0abt0b,V,F,η,ω)，Huser，Costuser，θ，X;

輸出：最優(yōu)尺度組合K′.

② 調(diào)用算法1更新尺度空間為ψ′；

③ for eachK∈ψ′ do

④ 得到POSAK(X),NEGAK(X),BNDAK(X)；

⑥ end for

⑦ for eachK∈ψ′ do

Costuserthen

在最壞情況下來分析算法2的時(shí)間復(fù)雜度，即假設(shè)每個(gè)對(duì)象都是一個(gè)獨(dú)立于條件和決策屬性的概念.在算法2中，步驟③～⑥在不同尺度下計(jì)算不確定性和代價(jià)，它的時(shí)間復(fù)雜度是O(|ψ′|×|U|2).步驟⑦～的目的是獲取滿足用戶需求的可行解，時(shí)間復(fù)雜度為O(|ψ′|).在最壞的情況下，初始尺度空間ψ中的所有尺度組合K的單尺度集值決策系統(tǒng)SK都是一致的，即|ψ|=|ψ′|.根據(jù)分析可知，該算法的時(shí)間復(fù)雜度為O(|ψ|×|U|2).下面舉例說明最優(yōu)尺度選擇的計(jì)算過程.

例4.在表2給出的具有測(cè)試代價(jià)和延遲代價(jià)的廣義多尺度集值決策系統(tǒng)S=(U,A∪j5i0abt0b,V,F,η,ω)中U={x1,x2,…,x10},X={x1,x2,x3,x9,x10}，關(guān)于決策屬性的論域劃分結(jié)果為U/Rd={(x1,x3,x4,x7,x9),(x2,x5,x6,x8,x10)}.根據(jù)例3可知：更新的尺度空間ψ′={(1,1,1),(2,1,1),(1,1,2),(1,2,1),(3,1,1),(1,2,2),(1,3,1),(4,1,1),(1,3,2)}，其中BNDA(1,1,1)(X)=BNDA(2,1,1)(X)=BNDA(1,1,2)(X)=BNDA(1,2,1)(X)=BNDA(3,1,1)(X)=BNDA(1,3,1)(X)=BNDA(4,1,1)(X)={x6,x7,x9,x10}，BNDA(1,2,2)(X)=BNDA(1,3,2)(X)={x2,x6,x7,x9,x10}.根據(jù)定義14～16及歸一化處理，其計(jì)算結(jié)果如表3所示，表3中粗體數(shù)據(jù)表明：在當(dāng)前尺度組合下決策系統(tǒng)的不確定性或代價(jià)是最小的.當(dāng)用戶對(duì)不確定性和代價(jià)需求分別是Huser=0.4，Costuser=100時(shí)，根據(jù)最優(yōu)尺度選擇模型，可得到不確定性和代價(jià)最小的最優(yōu)尺度組合是K=(4,1,1).

Table 3 The Results Based on Weighted Optimal ScaleSelection Model表3 基于加權(quán)的最優(yōu)尺度選擇模型計(jì)算結(jié)果

例4中，根據(jù)最優(yōu)尺度選擇模型可得到唯一的尺度組合解，但在有些廣義多尺度集值決策系統(tǒng)中，根據(jù)最優(yōu)尺度模型可能得到一組可行解.假設(shè)在例4模型中，滿足用戶需求的尺度組合為(1,1,2),(2,1,1),(1,3,1),(3,1,1),(4,1,1)，于是可以得到其理想解為Ide=[0.318,0.314].在基于加權(quán)的最優(yōu)尺度選擇模型中，假設(shè)用戶給定的加權(quán)系數(shù)θ=0.5，可以計(jì)算出Dif(1,1,2)=0.003，Dif(2,1,1)=0.020，Dif(1,3,1)=0.030，Dif(3,1,1)=0.010，Dif(4,1,1)=0.因此，可以得到(4,1,1)是最優(yōu)尺度組合.

例4說明算法2在得到唯一解或一組可行解情況下，其最優(yōu)尺度選擇的一致性.

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

為了驗(yàn)證本文提出的最優(yōu)尺度選擇算法的可行性和有效性，從UCI數(shù)據(jù)庫(kù)中選取了6個(gè)數(shù)據(jù)集進(jìn)行數(shù)值模擬，其詳細(xì)信息如表4所示.

為了滿足實(shí)驗(yàn)要求，本文參照文獻(xiàn)[16]中提出的方法構(gòu)造多尺度決策系統(tǒng).具體而言，首先對(duì)條件屬性進(jìn)行擴(kuò)展.若條件屬性值為離散型，則盡量對(duì)屬性值進(jìn)行合并，保證其不重復(fù)；若條件屬性值為連續(xù)型，則將屬性值劃分為多個(gè)區(qū)間，并將每個(gè)區(qū)間看作一個(gè)屬性值.然后，隨機(jī)丟失部分?jǐn)?shù)據(jù)值，其取值為該屬性相應(yīng)尺度下的值域，即可得到廣義多尺度集值決策系統(tǒng).表5列出了經(jīng)過預(yù)處理后數(shù)據(jù)集的信息.

Table 4 The Original Dataset Information表4 原始數(shù)據(jù)集信息

Table 5 The Dataset Information after Preprocessing表5 預(yù)處理后的數(shù)據(jù)集信息

Table 6 The Related Cost Parameters of Datasets表6 數(shù)據(jù)集的相關(guān)代價(jià)參數(shù)

使用算法1對(duì)每個(gè)數(shù)據(jù)集進(jìn)行尺度空間更新，結(jié)果如圖2所示，其中橫坐標(biāo)表示數(shù)據(jù)集，縱坐標(biāo)表示數(shù)據(jù)集的尺度組合數(shù)量.與LM(lattice mode)模型[20]相比，該尺度空間更新方法顯著減少了尺度組合數(shù)量，從而可以減少?zèng)Q策系統(tǒng)一致性判斷次數(shù).

由于測(cè)試代價(jià)和延遲代價(jià)的變化趨勢(shì)不同，總代價(jià)并不總是與不確定性的變化趨勢(shì)相同，實(shí)驗(yàn)將不確定性和總代價(jià)進(jìn)行歸一化處理.如表7是6個(gè)數(shù)據(jù)集進(jìn)行最優(yōu)尺度選擇的結(jié)果.

Fig. 2 The scale space update results圖2 尺度空間更新結(jié)果

Table 7 The Optimal Scale Selection Results表7 最優(yōu)尺度選擇結(jié)果

為了分析不確定和代價(jià)對(duì)最優(yōu)尺度選擇的影響，本文分別在2組不同的參數(shù)下對(duì)Hayes-Roth數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，其結(jié)果如圖3和圖4所示.在圖3和圖4中，橫坐標(biāo)代表更新尺度空間后決策系統(tǒng)的尺度組合數(shù)量，根據(jù)圖2中的數(shù)據(jù)可知，經(jīng)過尺度空間更新后，Hayes-Roth的尺度空間大小為64；縱坐標(biāo)代表決策系統(tǒng)的不確定性或代價(jià)；曲線H表示不同尺度組合下決策系統(tǒng)的不確定性；曲線Cost表示不同尺度組合下決策系統(tǒng)的代價(jià)；曲線Dif表示在2種加權(quán)系數(shù)下，決策系統(tǒng)的不確定性和代價(jià)與理想解的差異程度.其中，在第1組參數(shù)下，測(cè)試代價(jià)和延遲代價(jià)都為1～10范圍內(nèi)的隨機(jī)數(shù)，用戶對(duì)不確定性和代價(jià)的需求分別為Huser=0.36和Costuser=300，其最優(yōu)尺度組合為圖3所標(biāo)出的結(jié)果，即K=(1,2,4,4).在第2組參數(shù)下，測(cè)試代價(jià)和延遲代價(jià)都為1～15范圍內(nèi)的隨機(jī)數(shù)，用戶對(duì)不確定性和代價(jià)的需求分別為Huser=0.36和Costuser=600，其最優(yōu)尺度組合為圖4所標(biāo)出的結(jié)果，即K=(1,1,4,4).可以發(fā)現(xiàn)，在2組不同的參數(shù)設(shè)定下，決策系統(tǒng)的不確定性和代價(jià)不同，但通過本文提出的方法均可得到滿足用戶需求的最優(yōu)尺度.

Fig. 3 The optimal scale of Hayes-Roth underthe first set of parameters圖3 第1組參數(shù)下Hayes-Roth的最優(yōu)尺度

Fig. 4 The optimal scale of Hayes-Roth under thesecond set of parameters圖4 第2組參數(shù)下Hayes-Roth的最優(yōu)尺度

5 總 結(jié)

本文主要研究了廣義多尺度集值決策系統(tǒng)的最優(yōu)尺度選擇問題.首先，定義了廣義多尺度集值決策系統(tǒng)的概念，并討論了不同尺度組合下決策系統(tǒng)的不確定性和代價(jià).然后，引入序貫三支決策思想對(duì)決策系統(tǒng)的尺度空間進(jìn)行更新，減少了決策系統(tǒng)的一致性判斷次數(shù).在此基礎(chǔ)上，提出了一種綜合考慮不確定性和代價(jià)的最優(yōu)尺度選擇方法，并通過引入具有用戶偏好的理想解對(duì)其進(jìn)行優(yōu)化.最后，通過實(shí)驗(yàn)證明該方法能夠快速地得到一個(gè)滿足用戶需求的最優(yōu)尺度.

作者貢獻(xiàn)聲明：胡軍提出論文研究?jī)?nèi)容，并指導(dǎo)論文寫作；陳艷負(fù)責(zé)研究?jī)?nèi)容的實(shí)現(xiàn)和論文寫作；張清華、王國(guó)胤參與論文的研討與修改.