廣義多尺度集值決策系統最優尺度選擇

胡 軍 陳 艷 張清華 王國胤

1(計算智能重慶市重點實驗室(重慶郵電大學) 重慶 400065)

2(重慶郵電大學計算機科學與技術學院 重慶 400065)

(hujun@cqupt.edu.cn)

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

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

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

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

1 基本概念

本節主要介紹多尺度信息系統[1]及多尺度集值信息系統[32]的基本概念.

2 廣義多尺度集值信息系統

本節主要給出廣義多尺度集值信息系統的概念及相關性質，并討論不同尺度組合下決策系統的不確定性和代價變化趨勢.

2.1 廣義多尺度集值信息系統

現有關于多尺度集值信息系統的研究假設每個屬性的尺度級數都相同，然而實際問題中不同屬性的尺度級數可能不同，因而需要對其做進一步推廣.

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

例1.表1是某行業關于供應商的信息調查與評價，其中U={x1,x2,…,x10}表示10個供應商，屬性a1,a2,a3分別代表產品質量、配送效率和服務水平，且它們擁有不同的尺度級數，即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 廣義多尺度集值信息系統

例2.在例1所示的廣義多尺度集值信息系統中，其尺度空間ψ={(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.已知目標集合X?U，K是S的一個尺度組合，則X關于K的上、下近似集分別為

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

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

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

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

2.2 廣義多尺度集值決策系統的不確定性

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

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

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

證畢.

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

2.3 廣義多尺度集值決策系統的代價

在決策過程中，不同尺度的數據，其測試代價往往不同，且對邊界域對象進行延遲決策會產生延遲代價.本節主要討論廣義多尺度集值決策系統中的測試代價和延遲代價.

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

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

其中,BNDAK(X)是在尺度組合K下的邊界域對象集，ωxi是關于xi延遲決策的代價，即決策系統SK的延遲代價為尺度組合K下邊界域對象集延遲決策的代價.

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

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

其中,TCK是在尺度組合K下獲取所有對象屬性值的測試代價，DCK(X)是在尺度組合K下邊界域對象集的延遲代價.

定理2.已知S=(U,A∪g0gggggg,V,F,η,ω)是一個具有測試代價和延遲價的廣義多尺度集值決策系統，X?U.K和K′是關于S的2個尺度組合，當KK′時，可以得到TCK≤TCK′.

證畢.

定理3.已知S=(U,A∪g0gggggg,V,F,η,ω)是一個具有測試代價和延遲代價的廣義多尺度集值決策系統，X?U.K和K′是關于S的2個尺度組合，當KK′時，可以得到DCK(X)≤DCK′(X).

證明.假設尺度組合K下邊界域為E1,尺度組合K′下邊界域為E2，當KK′時，X關于尺度組合K和K′的粗糙近似關系有及根據邊界域定義可以得到E1?E2.因此，對于?x∈BNDAK(X),始終滿足x∈BNDAK′(X)，于是得到DCK(X)≤DCK′(X).

證畢.

可以看出，隨著尺度組合變粗，其對應單尺度集值決策系統的延遲代價逐漸增大，測試代價逐漸減小，而總代價不具有單調性.

3 廣義多尺度集值決策系統最優尺度選擇

現有的最優尺度選擇方法，大多是從決策系統的一致性或不確定性的角度出發，沒有考慮到實際場景中的代價問題.因此，本節主要結合不確定性和代價，以用戶需求為前提，找到決策或分類最優的尺度.

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

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

定義12.假設存在尺度組合K∈ψ，那么關于K的上、下邊界定義為

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

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

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

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次更新后需進行一致性判斷的尺度組合.當UNC(ψi)=?，可以得到S中所有一致的單尺度集值決策系統的尺度組合，即更新后的尺度空間ψ′=ACK(ψi).

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

算法1.廣義多尺度集值決策系統尺度空間更新.

輸入：廣義多尺度集值決策系統S=(U,A∪g0gggggg,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首先計算了廣義多尺度集值決策系統的尺度空間，時間復雜度為O(I1×I2×…×Im).然后針對尺度空間中尺度組合對應的決策系統進行一致性判斷，其中每個相似類的計算需要時間復雜度為O(m×|U|).在最壞情況下，假設所有尺度組合的決策系統都是一致的，需進行|ψ|=I1×I2×…×Im次判斷，所以算法1總的時間復雜度為O(m×|U|×|ψ|).

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

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

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

第1層關于尺度組合(1,1,1)的決策系統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)是不一致的.根據圖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)}.

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

3.2 最優尺度選擇

定義14.已知S=(U,A∪g0gggggg,V,F,η,ω)是一個具有測試代價和延遲代價的廣義多尺度集值決策系統，X?U.那么，X關于尺度組合K的評價為

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

其中,Huser和Costuser分別是用戶對于不確定性和代價的需求.

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

定義16.已知S=(U,A∪g0gggggg,V,F,η,ω)是一個具有測試代價和延遲代價的廣義多尺度集值決策系統，基于加權的最優尺度選擇模型為

其中,DifK表示加權差異程度，θ∈[0,1]表示加權系數.加權系數θ可根據用戶需求進行設置，當θ=0時，該模型退化為基于代價的最優尺度選擇；當θ=1時，該模型退化為基于不確定性的最優尺度選擇.

因此，可以設計廣義多尺度集值決策系統最優尺度選擇算法為：

算法2.廣義多尺度集值決策系統最優尺度選擇.

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

輸出：最優尺度組合K′.

② 調用算法1更新尺度空間為ψ′；

③ for eachK∈ψ′ do

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

⑥ end for

⑦ for eachK∈ψ′ do

Costuserthen

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

例4.在表2給出的具有測試代價和延遲代價的廣義多尺度集值決策系統S=(U,A∪g0gggggg,V,F,η,ω)中U={x1,x2,…,x10},X={x1,x2,x3,x9,x10}，關于決策屬性的論域劃分結果為U/Rd={(x1,x3,x4,x7,x9),(x2,x5,x6,x8,x10)}.根據例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}.根據定義14～16及歸一化處理，其計算結果如表3所示，表3中粗體數據表明：在當前尺度組合下決策系統的不確定性或代價是最小的.當用戶對不確定性和代價需求分別是Huser=0.4，Costuser=100時，根據最優尺度選擇模型，可得到不確定性和代價最小的最優尺度組合是K=(4,1,1).

Table 3 The Results Based on Weighted Optimal ScaleSelection Model表3 基于加權的最優尺度選擇模型計算結果

例4中，根據最優尺度選擇模型可得到唯一的尺度組合解，但在有些廣義多尺度集值決策系統中，根據最優尺度模型可能得到一組可行解.假設在例4模型中，滿足用戶需求的尺度組合為(1,1,2),(2,1,1),(1,3,1),(3,1,1),(4,1,1)，于是可以得到其理想解為Ide=[0.318,0.314].在基于加權的最優尺度選擇模型中，假設用戶給定的加權系數θ=0.5，可以計算出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)是最優尺度組合.

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

4 實驗結果與分析

為了驗證本文提出的最優尺度選擇算法的可行性和有效性，從UCI數據庫中選取了6個數據集進行數值模擬，其詳細信息如表4所示.

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

Table 4 The Original Dataset Information表4 原始數據集信息

Table 5 The Dataset Information after Preprocessing表5 預處理后的數據集信息

Table 6 The Related Cost Parameters of Datasets表6 數據集的相關代價參數

使用算法1對每個數據集進行尺度空間更新，結果如圖2所示，其中橫坐標表示數據集，縱坐標表示數據集的尺度組合數量.與LM(lattice mode)模型[20]相比，該尺度空間更新方法顯著減少了尺度組合數量，從而可以減少決策系統一致性判斷次數.

由于測試代價和延遲代價的變化趨勢不同，總代價并不總是與不確定性的變化趨勢相同，實驗將不確定性和總代價進行歸一化處理.如表7是6個數據集進行最優尺度選擇的結果.

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

Table 7 The Optimal Scale Selection Results表7 最優尺度選擇結果

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

Fig. 3 The optimal scale of Hayes-Roth underthe first set of parameters圖3 第1組參數下Hayes-Roth的最優尺度

Fig. 4 The optimal scale of Hayes-Roth under thesecond set of parameters圖4 第2組參數下Hayes-Roth的最優尺度

5 總 結

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

作者貢獻聲明：胡軍提出論文研究內容，并指導論文寫作；陳艷負責研究內容的實現和論文寫作；張清華、王國胤參與論文的研討與修改.