不完備信息系統中測試代價敏感的可變精度分類粗糙集

鞠恒榮，馬興斌，楊習貝,，祁云嵩，楊靜宇

(1.江蘇科技大學 計算機科學與工程學院，江蘇 鎮江 212003； 2. 南京理工大學 計算機科學與技術學院，江蘇 南京 210094)

作為一種處理不精確、不確定性問題的數學工具, 粗糙集理論[1](rough set)由波蘭學者Pawlak 提出后便受到了廣泛關注[2-4]。 然而由于數據測量的誤差、數據獲取的限制等原因, 導致了所面臨的信息系統往往是不完備的。 為處理這類問題, 王國胤[5]提出了限制容差關系。 進一步,楊習貝[6]提出了一種新的基于可變精度分類的拓展粗糙集模型, 對限制容差關系進行了改進。 然而, 在實際工程應用中, 數據的獲取是需要付出一些成本或代價的, 稱其為測試代價。 針對該問題, Min等[7-11]率先將測試代價引入到粗糙集的約簡問題中，終究未能將測試代價引入到不完備信息系統環境下粗糙集本身的近似模型上。

1 基本概念

形式化地, 信息系統可表示為四元組IS= 〈U,AT,V,f〉, 其中U={x1,x2, … ,xm}為研究對象的有限集合, 稱為論域;AT= {a1,a2, … ,an}為描述對象的全部屬性所組成的集合;V= ∪aATVa為屬性集合AT的值域, 其中Va為屬性a的值域;f:UATV為信息函數, 表示對每一個xU,aAT,f(x,a)Va。 特別地, 當信息系統中屬性集A=AT∪D且AT∩D=(其中AT為條件屬性集合,D為決策屬性集合)時, 信息系統也被稱為決策系統。

定義1[6]設S為不完備信息系統,AAT, 由A決定的可變精度分類關系記為且

f(x,a) =f(y,a)

(1)

式中：PA(x) = {aA:f(x,a)已知},α[0, 1], |X| 表示集合X的基數,IU為恒等關系且IU= {(x,x):xU}。

定義2[6]設S為不完備信息系統,AAT, 對于任意的XU,X基于可變精度分類關系的下、上近似集合分別記為和

2 測試代價與可變精度分類粗糙集

不完備信息系統環境下的粗糙集模型未考慮數據的代價問題, Min等[8]將測試代價引入到信息系統中, 具體的描述見定義3。

定義3[8]一個測試代價敏感的不完備決策系統TCSIIDS為一個五元組〈U,AT∪D,V,f,c*〉,U,AT∪D,V和f的含義與第1節所示相同,c*:AT={a1,a2,…,an}R+∪{0}為測試代價函數(R+表示正整數集), 即其中c*({ai})表示單個屬性ai的測試代價。 本文假設所有屬性的測試代價均為正整數, 即c*({ai})0,aiAT。

定義4 令TCSIIDS為測試代價敏感不完備決策系統, 其中AAT,x,yU,aA, 定義特征函數如下所示:

式中：Pa(x) = {aA:f(x,a)已知}。

定義5 設TCSIIDS為測試代價敏感不完備決策系統, 其中AAT, 由A決定的可變精度分類關系記為且

f(x,a)=f(y,a)

其中：α[0, 1。

定義6 設TCSIIDS為測試代價敏感不完備決策系統,AAT, 對于XU,X基于可變精度分類關系的下、上近似集分別記為和

3 屬性約簡

屬性約簡是粗糙理論的主要研究內容之一。 然而, 尋找決策表的最小約簡已被證明是一個NP-hard問題, 在處理大規模數據時計算時間代價很大, 針對這一問題, 許多學者提出了許多高效的約簡算法, 啟發式搜索方法就是其中的一個典型代表。

定義7 設TCSIIDS為測試代價敏感不完備決策系統,α[0, 1],U/IND(D)={X1,,Xn}表示根據決策屬性得到的所有決策類的合集, 那么U/IND(D)的近似質量可定義為

定理1 令TCSIIDS為測試代價敏感不完備決策系統,AAT, 若0α1α21, 則有

γ(A,α1,D)≤γ(A,α2,D)

證明根據定義6, 定理1易證。

定義8 令TCSIIDS為測試代價敏感不完備決策系統,α[0, 1],AAT為一個約簡當且僅當γ(A,α,D) =γ(AT,α,D)且BA,γ(B,α,D)γ(A,α,D)。

令TCSIIDS為測試代價敏感決策系統,α[0, 1],AAT,aiA,ai的重要度為

LSigin(ai,A,D)=γ(A,α,D)γ(Aai,α,D)

可以看出, LSigin(ai,B,D)反映了ai從當前條件屬性集A中刪除后近似質量的變化, 相應地也可定義

LSigout(ai,A,D)=γ(A∪ai,α,D)γ(A,α,D)

式中：aiATA, LSigout(ai,A,D)用以度量向屬性集A增加屬性ai后近似質量的變化。 根據上述屬性的重要度可以設計啟發式屬性約簡算法。 Min等在文獻[11]中設計了傳統的啟發式算法(記為算法1)。 其算法復雜度為i+1))。

Min等從獲取約簡的測試代價最小出發設計出新的約簡算法, 即回溯算法(記為算法2)。 其算法復雜度為O(2|AT|1)。 詳細算法見文獻[11]。

3.1 考慮屬性測試代價的啟發式算法

由上文可知回溯算法的時間復雜度為O(2|AT|1)。 考慮到現實生活中存在著大量高維屬性的數據, 這樣一種機制將會大大制約屬性約簡的時間。 為解決這一問題, 本文依然從啟發式算法的角度出發, 將屬性的測試代價考慮到屬性重要度定義中。 為此, 給出如下的屬性融合重要度定義。

TCSLSigin(ai,AT,D) =

TCSLSigout(ai,AT,D) =

式中：θ≤ 0?？梢钥闯? TCSLSigin(ai,AT,D)是LSigin(ai,AT,D)與(c*(ai))θ之和。 當θ=0時, 無論屬性的測試代價取何值, 都有TCSLSigin(ai,AT,D)=0.1LSigin(ai,AT,D)+1, 這說明TCSLSigin(ai,AT,D)的大小與屬性測試代價的大小無關, 僅與LSigin(ai,AT,D)的值有關。 隨著θ值的不斷減小, (c*(ai))θ的值也不斷減小(本文隨機產生測試代價在[10, 100]), 此時(c*(ai))θ在TCSLSigin(ai,AT,D)中所占的比重也越來越小, 表明屬性測試代價在屬性的重要度中的影響作用越來越小。根據新的屬性融合重要度, 不難設計出綜合考慮了測試代價的啟發式算法, 具體算法流程見算法1。

算法1 基于測試代價敏感不完備決策系統TCSIIDS綜合考慮測試代價的啟發式算法

輸入:測試代價敏感不完備決策系統TCSIIDS,α;

輸出:約簡red及約簡的測試代價c*(red)。

1)計算γ(AT,α,D); 令θ=0,c*(red)=c*(AT);

4)若TCSLSigin(aj,AT,D) = max{TCSLSigin(ai,AT,D):aiAT}, 則redaj,計算γ(red,α,D);

5)若γ(red,α,D)γ(AT,α,D), 則重復以下循環, 否則轉6);

②若TCSLSigout(ai,B,D)=max{TCSLSigout(ai,B,D):aiATred},則redai;

7)c*(red)=min{c*(red), tmp};

8)若θ大于給定閾值, 則θ=θδ(此處δ為步長,δ>0)且重復2)～7),否則轉9);

9)輸出red及c*(red)。

3.2 實驗分析

本節將通過實驗, 對比算法1、算法2和算法3。 表1列出了實驗中使用的4組測試數據的基本信息, 所有數據集均下載于UCI數據集。 由于UCI數據集中的大部分數據不含有測試代價, 所以在本組實驗中為每個數據集的屬性隨機增加了取值在[10, 100]之間的測試代價。

表1 實驗數據基本信息

由于基于測試代價敏感的可變精度分類粗糙集模型的下、上近似集由閾值α控制, 因此, 在實驗中選取了10組不同的α值分別對比3個算法的測試代價, 在算法3的第8步中, 給定閾值設為-5, 步長δ為0.5, 即重復求得10次約簡, 取其中的最小測試代價作為輸出。 具體的實驗結果見圖1。

(a)Bridges

(b)Credit approval

(c)Heart-disease

(d)Hepatitis圖1 3種約簡算法所求得的測試代價對比Fig.1 Comparisons among test costs obtained by three algorithms

由圖1的實驗結果, 可以得到: 1)傳統的啟發式算法所獲取的約簡的測試代價最大, 回溯算法所約簡的測試代價最小, 而綜合考慮測試代價的改進的啟發式算法得到約簡的測試代價則是基于兩者之間。2)從圖1的4個子圖可以發現, 3種算法的測試代價隨α值的不斷增加呈現先增加達到一定峰值后再下降的大致趨勢, 從實驗的角度可看出α值在這3個算法中發揮著調節正域的作用。

4 結束語

本文將測試代價引入不完備信息系統中, 提出了基于測試代價敏感的可變精度分類粗糙集模型。進一步地, 通過分析傳統啟發式約簡算法未考慮測試代價以及回溯約簡算法為獲取最優測試需要消耗大量時間的不足, 本文對傳統屬性重要度測量進行了改進, 并根據新的屬性重要度測量設計了一種新的啟發式算法用以獲取測試代價次優的約簡。 實驗表明, 總體而言, 改進的啟發式算法是尋找約簡測試代價次優的合適方法。

參考文獻:

[1]PAWLAK Z. Rough sets-theoretical aspects of reasoning about data[M]. Dordrecht: Kluwer Academic, 1991.

[2]HU Q H, CHE X J, ZHANG L, et al. Rank entropy based decision trees for monotonic classification[J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(11): 2052-2064.

[3]HU Q H, PAN W W, ZHANG L, et al. Feature selection for monotonic classification[J]. IEEE Transactions on Fuzzy Systems, 2012, 20(1): 69-81.

[4]LUO G Z, YANG X B. Limited dominance-based rough set model and knowledge reductions in incomplete decision system[J]. Journal of Information Science and Engineering, 2010, 26(6): 2199-2211.

[5]王國胤. Rough 集理論在不完備信息系統中的擴充[J]. 計算機研究與發展, 2002, 39(10): 1238-1243.

WANG Guoyin. Extension of rough set under incomplete information systems[J]. Journal of Computer Research and Development, 2002, 39(10): 1238-1243.

[6]楊習貝, 楊靜宇, 於東軍, 等. 不完備信息系統中的可變精度分類粗糙集模型[J]. 系統工程理論與實踐, 2008, 28(5):116-121.

YANG Xibei, YANG Jingyu, YU Dongjun, et al. Rough set model based on variable parameter classification in incomplete information systems[J]. System Engineering-Theory and Practice, 2008, 28(5): 116-121.

[7]MIN F, HE H P, QIAN Y H, et al. Test-cost-sensitive attribute reduction[J]. Information Sciences, 2011, 181(22): 4928-4942.

[8]MIN F, LIU Q H. A hierarchical model for test-cost-sensitive decision systems[J]. Information Sciences, 2009, 179(14): 2442-2452.

[9]MIN F, ZHU W. Test-cost-sensitive attribute reduction based on neighborhood rough set[C]//2011 IEEE International Conference on Granular Computing. Kaohsiung, China, 2011: 802-806.

[10]MIN F, ZHU W. Attribute reduction of data with error ranges and test costs [J]. Information Sciences, 2012, 211: 48-67.

[11]MIN F, HE H P, QIAN Y H, et al. Test-cost-sensitive attribute reduction[J]. Information Sciences, 2011, 181: 4928-4942.