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

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

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

1 基本概念

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

定義1[6]設(shè)S為不完備信息系統(tǒng),AAT, 由A決定的可變精度分類關(guān)系記為且

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

(1)

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

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

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

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

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

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

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

定義5 設(shè)TCSIIDS為測試代價敏感不完備決策系統(tǒng), 其中AAT, 由A決定的可變精度分類關(guān)系記為且

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

其中：α[0, 1。

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

3 屬性約簡

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

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

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

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

證明根據(jù)定義6, 定理1易證。

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

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

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

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

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

式中：aiATA, LSigout(ai,A,D)用以度量向?qū)傩约疉增加屬性ai后近似質(zhì)量的變化。 根據(jù)上述屬性的重要度可以設(shè)計啟發(fā)式屬性約簡算法。 Min等在文獻[11]中設(shè)計了傳統(tǒng)的啟發(fā)式算法(記為算法1)。 其算法復雜度為i+1))。

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

3.1 考慮屬性測試代價的啟發(fā)式算法

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

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)的大小與屬性測試代價的大小無關(guān), 僅與LSigin(ai,AT,D)的值有關(guān)。 隨著θ值的不斷減小, (c*(ai))θ的值也不斷減小(本文隨機產(chǎn)生測試代價在[10, 100]), 此時(c*(ai))θ在TCSLSigin(ai,AT,D)中所占的比重也越來越小, 表明屬性測試代價在屬性的重要度中的影響作用越來越小。根據(jù)新的屬性融合重要度, 不難設(shè)計出綜合考慮了測試代價的啟發(fā)式算法, 具體算法流程見算法1。

算法1 基于測試代價敏感不完備決策系統(tǒng)TCSIIDS綜合考慮測試代價的啟發(fā)式算法

輸入:測試代價敏感不完備決策系統(tǒng)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), 則重復以下循環(huán), 否則轉(zhuǎn)6);

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

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

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

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

3.2 實驗分析

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

表1 實驗數(shù)據(jù)基本信息

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

(a)Bridges

(b)Credit approval

(c)Heart-disease

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

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

4 結(jié)束語

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

參考文獻:

[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 集理論在不完備信息系統(tǒng)中的擴充[J]. 計算機研究與發(fā)展, 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]楊習貝, 楊靜宇, 於東軍, 等. 不完備信息系統(tǒng)中的可變精度分類粗糙集模型[J]. 系統(tǒng)工程理論與實踐, 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.