測試代價敏感的決策粗糙集正域約簡*

劉 偲，秦亮曦

廣西大學 計算機與電子信息學院，南寧 530004

測試代價敏感的決策粗糙集正域約簡*

劉 偲+，秦亮曦

廣西大學 計算機與電子信息學院，南寧 530004

LIU Cai,QIN Liangxi.Test-cost sensitive reduction on positive region of decision theoretic rough sets.Journal of Frontiers of Computer Science and Technology,2017,11(6)：1014-1020.

對測試代價敏感的決策粗糙集（decision theoretic rough sets，DTRS）正域約簡問題進行了研究。在傳統(tǒng)正域約簡的基礎上將測試代價考慮進來，希望找到測試代價總和最小的正域約簡。采用模擬退火算法結合傳統(tǒng)決策粗糙集正域約簡算法來搜索測試代價總和最小的正域約簡結果。提出了一種測試代價敏感的決策粗糙集正域約簡算法TCSPR（test-cost sensitive positive region-based reduction algorithm for DTRS），并分析了該算法的時間復雜度。實驗結果驗證了TCSPR算法的有效性，該算法能在多項式時間內找到一個屬性更少、測試代價更小的正域約簡，找到的解一般為優(yōu)化目標的最優(yōu)解或次優(yōu)解，即測試代價總和最小的正域約簡,并且該算法在部分數據集上的分類能力幾乎不減。

決策粗糙集（DTRS）；代價敏感；屬性約簡

1 引言

經典粗糙集模型[1]是由Pawlak在1982年提出的一種處理模糊性和不確定性的軟計算工具[2]。因為經典粗糙集是基于嚴格的集合代數包含關系，所以在容錯能力方面具有較大的局限性。Yao將經典粗糙集的嚴格代數包含關系改為概率包含關系，這樣就使得決策類的負域不恒為空，并賦予3個決策域新的語義，重新定義了一個新的模型，即決策粗糙集模型[3]。

屬性約簡是粗糙集研究的核心問題之一，其目的是將冗余的屬性去掉，從而發(fā)現(xiàn)數據的本質信息。眾所周知，經典粗糙集的正域是具有單調性的，Pawlak基于這一特性給出了正域約簡的方法[4]，而決策粗糙集并不具備這個特性，Yao等人為此提出了新的正域約簡方法[5]。

一般而言，樣本的分類結果與測試屬性集緊密相關。在一定范圍內，測試的相關屬性越多，樣本的分類精度越高，錯誤分類結果越少，誤分類代價越小[6]。因此，包含更多屬性的測試屬性集通常具有較小的誤分類代價。但在實際問題中，獲取樣本的屬性值本身具有一定的代價，即測試代價[7]。例如，在醫(yī)療診斷中，取得病人的視力數據、心電圖數據、尿檢數據、血常規(guī)數據等都需要不同的測試代價[8]。測試屬性集越多，雖然分類精度越高即誤分類代價越低，但是同樣的測試代價也越高。因此，需要將測試代價考慮在內，使包括誤分類代價和測試代價的總代價降到最低，才能適應實際問題的需求。在決策粗糙集屬性約簡方面，Yao提出了正域約簡方法，黃國順提出了一種保正域的屬性約簡方法[9]，張智磊等人給出了一種基于回溯搜索算法的屬性約簡方法[10]，賈修一等人提出了一種決策風險最小化屬性約簡[11]，李華雄等人在文獻[11]的基礎上給出了代價敏感的決策風險最小化屬性約簡方法[6]。

本文將測試代價納入正域約簡的考慮范圍，在正域約簡的基礎上用模擬退火方法找到測試代價總和最小的正域約簡結果。通過找到測試代價總和最小的正域約簡，可以在實際應用中，找到一個分類能力和屬性全集相近但測試代價大大降低的屬性約簡。

2 相關理論介紹

2.1 決策粗糙集正域約簡

在經典粗糙集正域約簡中，因為經典粗糙集具有正域單調性，所以Pawlak正域約簡要求屬性子集的正域保持不變。但是決策粗糙集模型中，正域不具備單調性，即正域不會隨著屬性的增加而擴大。針對決策粗糙集的這種情況，Yao等人在文獻[5]中給出了新的屬性約簡定義。

定義1[5]設S={U,C∪D,f,V}為一個決策表，若屬性子集B?C滿足以下兩個條件：

（2）屬性獨立性，對任意屬性a∈B,均有|POSαB-{a}(D)|<則稱屬性子集B為屬性全集C的一個決策粗糙集α-正域約簡。

如果屬性子集同時滿足上述兩個性質，則屬于一個正域約簡，正域約簡可能不止一個。

2.2 決策粗糙集正域約簡算法

目前已知求粗糙集的最小屬性約簡是一個NP難問題，因此大多數求約簡的方法都采用啟發(fā)式方法，通過定義啟發(fā)式函數為搜索方向提供指導，以搜索出部分約簡。在決策粗糙集中求約簡的方法可以采用啟發(fā)式策略，根據定義1可知，在求決策粗糙集α-正域約簡時，屬性子集應具有盡可能大的正域，因此可以將啟發(fā)式函數選為屬性的α-正域重要度[12]。

定義2[12]設S={U,C∪D,f,V}為一個決策表，α∈[0,1]為條件概率閾值，a∈C為單個屬性，則屬性a的α-正域全局重要度為：

文獻[12]給出了決策粗糙集α-正域約簡算法。

算法1[12]PRDTRS（positive region-based heuristic reduction algorithm for DTRS）

輸入：一個決策表S={U,C∪D,f,V}，概率包含度閾值α∈[0,1]。

輸出：該決策表的α-正域約簡。

步驟1令初始α-正域約簡屬性集B=?。

步驟2計算C中每個屬性的α-正域全局重要度γ

步驟3將屬性按照全局重要度由大到小排列，令為P。

步驟4在時重復如下循環(huán)：令a為P中第一個屬性（最高重要度）；將α并入α-正域約簡屬性集，B=B∪{a}；將α從P中刪除，P=P-{a}。

步驟5在B不滿足獨立性條件時重復如下循環(huán)：對所有c∈B,若則B=B-{c}。

步驟6輸出該決策表的一個α-正域約簡。

3 測試代價敏感與屬性約簡

3.1 測試代價敏感

將數據集表示為如下四元組形式的決策信息表：

S={U,C∪D,f,V}

定義屬性子集B?C上的等價關系RB和樣本x?U在屬性集B下的等價類分別為[6]：

在考慮樣本x在屬性子集B上的測試代價時，假設各個樣本在同一屬性上的測試代價是相等的，因此，x在屬性子集B上的測試代價為屬性子集B中所有屬性測試代價的和，測試代價設為一個非負實數。可以得到一個計算測試代價函數[6]：

其中，F(xiàn)(ci)為B中單個屬性的測試代價。

3.2 屬性約簡

在傳統(tǒng)決策粗糙集正域約簡中，不考慮測試代價，只考慮正域的變化。本文將在保證正域不減的同時，尋找屬性子集中測試代價總和最小的屬性集合，提出一種測試代價敏感的決策粗糙集正域約簡算法TCSPR（test-cost sensitive positive region-based reduction algorithm for DTRS）。該算法的目標是在滿足正域不變約束的情況下求總測試代價最小的屬性子集B，即其中k為樣本個數，x為樣本對象，TestcostB(x)為求x對象在屬性集合B下的測試代價，算法思想如下：

首先，通過算法1的前4步找到一個屬性子集，該屬性子集的正域不小于屬性全集的正域，用該屬性子集作為初始集合。然后，結合模擬退火的方法[13-14]，在溫度的每個平衡點用隨機變換產生屬性子集，并在當前溫度下判斷是否保留此變換。最后保留下來的即為測試代價總和最小的正域約簡。

算法2TCSPR

輸入：一個決策表S={U,C∪D,f,V}，由算法1前4步得到的屬性子集BOringe。

輸出：測試代價敏感的正域約簡。

步驟1令初始正域約簡屬性集B=BOringe，令P=C-BOringe，計算初始化tmin,t。

步驟2通過隨機刪除、替換、添加屬性的方式，由屬性集B產生新的B*。

步驟5如果或者exp(-Δf/t)>Random，并且則令B=B*。

步驟6判斷當t>tmin并且結果不收斂時，回到步驟2，并讓t衰減一個Δt。

步驟7輸出B即為測試代價總和最小的正域約簡。

算法1中，添加屬性循環(huán)復雜度為O(C×N2)，刪除屬性循環(huán)復雜度為O(C×N)，因此算法1的時間復雜度為O(C×N2+C×N)，也就是O(C×N2)，其中C為屬性個數，N為樣本個數。在算法2中，目標函數的時間復雜度為O(C×N2)，算法2是基于模擬退火算法的，模擬退火的時間復雜度為O(|Nm|×ln|S|)，其中|S|為狀態(tài)空間中的狀態(tài)數，|Nm|為最大的相鄰狀態(tài)數。該問題的|N|和|S|為問題輸入大小的多項式函數，即該算法可在多項式時間內為這些問題求得近似最優(yōu)解或者最優(yōu)解[13]。

算法2有兩個結束條件，一個是溫度下降到閾值，一個是結果收斂，如果出現(xiàn)解在連續(xù)M個馬爾可夫鏈無任何改變的情況可以判斷為結果收斂。結果如果一直不收斂，初始溫度t也一定會下降到閾值tmin而結束該算法，且模擬退火算法已經從理論上被證明是可收斂的，只是收斂較慢[13]。因此在運行時間上還是算法1具有明顯優(yōu)勢，但是在測試代價總和方面，算法2具有絕對優(yōu)勢，下面通過實驗具體說明。

4 實驗結果及分析

這一部分主要驗證基于模擬退火算法的測試代價敏感決策粗糙集正域約簡方法的有效性，并和傳統(tǒng)決策粗糙集正域約簡算法進行比較。

模擬退火算法是一種隨機算法，每次運行的狀態(tài)可能不一致，因此對每個數據集都運行10次取平均值作為運行結果。

本文實驗的機器為Intel?Xeon?的3.50 GHz CPU，8 GB內存，64位Windows8操作系統(tǒng)，算法在Matlab平臺上實現(xiàn)。實驗數據取自UCI數據庫中的3個數據集Spambase、WDBC（breast cancer Wisconsin（diagnostic）肺癌診斷結果）和WPBC（breast cancer Wisconsin（prognostic）患者是否復發(fā)）。數據集中有少量缺失的數據，使用該屬性在其他所有對象中的最頻值來補齊缺失的屬性值。WDBC、WPBC有數據ID列，將該列刪除，然后使用WEKA（Waikato environment for knowledge analysis）歸一化、離散化。預處理之后的實驗數據基本信息如表1所示。

Table 1 Basic information of experimental data表1 實驗數據基本信息

在實驗中，假定[15]誤分類代價滿足λPP≤λBP≤λNP,λNN≤λBN≤λPN,λNN=λPP=0，為使實驗具有可重復性，3組數據的誤差代價矩陣如表2所示[6]。

Table 2 Misclassification cost matrix表2 誤分類代價矩陣

數據集中沒有給出各屬性的測試代價，因實驗需要，本文假定各測試代價服從正態(tài)分布N(μ,σ)，并設Spambase的屬性測試代價服從N(0.2,0.1)，WDBC和WPBC的屬性測試代價服從N(0.02,0.01)，使用正態(tài)隨機函數隨機生成各屬性的測試代價。

本文實驗隨機選用數據中的100個樣本作為訓練樣本，為使實驗具有可重復性，固定選取前100個樣本作為訓練樣本，剩下的對象作為測試樣本[6]。分別使用算法1和算法2計算局部最優(yōu)屬性集B*，然后用風險最小化分類方法對測試樣本進行分類，得到分類正確率。

表3為3組屬性約簡實驗結果（比較約簡屬性集平均個數）。

由表3可以看出，算法2約簡后得到的最優(yōu)屬性集個數更少，特別是在WPBC數據集上，算法2在算法1的基礎上約簡了77%的屬性個數，但是正域對象個數和算法1得到的正域對象個數相差無幾，且算法2約簡后的平均正域對象個數都大于等于全屬性集的正域對象個數。證明算法2能在保證約簡后正域對象個數不減的情況下得到屬性個數更少的正域約簡最優(yōu)屬性集，即具有更強的屬性約簡能力。

Table 3 Comparison of experimental results表3 實驗結果比較

表4比較了3組實驗的平均測試代價總和。從表4可以很明顯地看出，算法2能大大降低測試代價總和。在3個數據集上，算法2在算法1的基礎上測試代價約簡率都超過了50%，特別在WPBC數據集上，算法2能在算法1的基礎上再降低96.2%的總測試代價。證明算法2確實可以實現(xiàn)找到最小測試代價總和的正域約簡。

Table 4 Average total test cost表4 平均總測試代價

表5展示了3組實驗約簡得到的最優(yōu)屬性集，對測試樣本集進行風險最小化的決策粗糙集決策分類的平均正確率。

Table 5 Average correct rate of classification表5 分類平均正確率 %

由表5可以看出，算法1在3個數據集上的分類正確率都比較高，而算法2只有在數據集Spambase上正確率和算法1相近，在另外兩個數據集上的正確率略低于算法1。由實驗可以看出，在數據集Spambase上，相對算法1的測試代價約簡率只為57.9%，屬性約簡率只有32%；在WDBC和WPBC平均正確率較低的數據集上測試代價約簡率高達96.1%和 96.2%，屬性約簡率高達67%和77%。說明單單追求測試代價的最小化將導致正確率的下降。

由此可以看出，算法2在某些數據集上的正確率較低，因此算法2不適用于要求分類正確率較高的場合。

表6展示了兩個算法的平均運行時間。運行時間是通過使用Matlab自帶的記錄運行時間方式統(tǒng)計得到。通過實驗可以看出，算法1的運行時間比算法2還要低許多，在運行時間方面算法1比較有優(yōu)勢。當然，如果調小判斷結果收斂的參數M，則收斂速度會變快，但是測試總代價約簡率將會下降，反之則變慢，但是更接近全局最優(yōu)解。

Table 6 Average running time表6 平均運行時間 s

圖1~圖4分別展示了算法1和算法2在約簡屬性集平均個數、平均總測試代價（因為數量級不一致，將3組都化為同一數量級顯示）、分類平均正確率和平均運行時間的比較。

Fig.1 Average number of reduction attribute set圖1 約簡屬性集平均個數

Fig.2 Average total test cost圖2 平均總測試代價

Fig.3 Average correct rate of classification圖3 分類平均正確率

Fig.4 Average running time圖4 平均運行時間

從圖1~圖3中可以更清楚地看出，算法2相比較算法1，能實現(xiàn)更高的屬性約簡率，能大大降低測試代價總和，而且分類正確率相差不大。這在實際應用中，如果各屬性的測試代價較高，而且決策者并不需要較高的分類正確率時，算法2可以幫助決策者節(jié)省大量花費在獲取數據上的成本。然而從圖4上也能看出，在運行時間方面，算法2還有很大的改進空間。本文在正域約簡的基礎上，用模擬退火算法來搜索具有最小測試代價總和的正域約簡，雖然已經達到了大大減少測試代價總和的正域約簡，屬性約簡率也有很大的提高，但是在正確率方面還有待提高。這也證明了全力搜索具有最小測試代價總和的正域約簡有一定的局限性，并不是測試代價越低的正域約簡越好。應當在搜索具有最小測試代價總和的正域約簡的同時，考慮誤差代價，提高分類正確率。下一步準備在考慮測試代價敏感的同時考慮誤差代價，將誤差代價也引入正域約簡。

5 結束語

本文針對測試代價敏感和決策粗糙集的正域約簡進行了研究，在傳統(tǒng)正域約簡的基礎上將測試代價考慮進來，提出了一種測試代價敏感的正域約簡算法TCSPR，通過采用模擬退火方法結合傳統(tǒng)正域約簡算法來搜索測試代價總和最小的正域約簡結果。通過實驗分析，驗證了本文提出的TCSPR算法的有效性，分析了TCSPR算法的時間復雜度為O(|Nm|×ln|S|)，即能在多項式時間內找到屬性個數更少的測試代價更小的正域約簡，找到的解一般為優(yōu)化目標的最優(yōu)解或次優(yōu)解。并且TCSPR算法在部分數據集上的分類能力幾乎不減。但是因為算法1的時間復雜度較低，所以TCSPR算法在運行時間方面要明顯弱于算法1，這也是下一步需要改進的地方。而且如果一味追求測試代價最小化可能會引起正確率的下降，因為屬性個數越少測試代價也會越小，但是誤分類代價將上升，導致正確率下降。下一步也將進一步研究如何在降低測試代價的同時，考慮引入誤差代價保持分類的正確率。

[1]Pawlak Z.Rough sets[J].International Journal of Computer and Information Sciences,1982,11(5):341-356.

[2]Wang Guoying,Yao Yiyu,Yu Hong.A survey on rough set theory and applications[J].Chinese Journal of Computers, 2009,32(7):1229-1246.

[3]Yao Yiyu.Decision-theoretic rough set models[C]//LNCS 4481:Proceedings of the 2nd International Conference on Rough Sets and Knowledge Technology,Toronto,Canada,May 14-16,2007.Berlin,Heidelberg:Springer,2007:1-12.

[4]Pawlak Z.Rough sets theoretical aspects of reasoning about data[M].Boston,USA:KluwerAcademic Publishers,1991.

[5]Yao Yiyu,ZhaoYan.Attribute reduction in decision-theoretic rough set models[J].Information Sciences,2008,178(17): 3356-3373.

[6]Li Huaxiong,Zhou Xianzhong,Huang Bing,et al.Decisiontheoretic rough set and cost-sensitive classification[J].Journal of Frontiers of Computer Science and Technology,2013, 7(2):126-135.

[7]Min Fan,He Huaping,Qian Yuhua,et al.Test-cost-sensitive attribute reduction[J].Information Sciences,2011,181(22): 4928-4942.

[8]Liu Jiabin,Min Fan.A survey on cost-sensitive rough set research[J].Journal of Zhangzhou Normal University:Natural Science,2011,24(4):17-22.

[9]Huang Guoshun.Positive region preservation reducts in decision-theoretic rough set models[J].Computer Engineering andApplications,2016,52(2):165-169.

[10]Zhang Zhilei,Liu Sanyang.Decision-theoretic rough set attribute reduction based on backtracking search algorithm [J].Computer Engineering and Applications,2016,52(10): 71-74.

[11]Jia Xiuyi,Shang Lin,Chen Jiajun.Attribute reduction based on minimum decision cost[J].Journal of Frontiers of Computer Science and Technology,2011,5(2):155-160.

[12]Li Huaxiong,Zhou Xianzhong,Zhao Jiabao,et al.Nonmonotonic attribute reduction in decision-theoretic rough sets[J].Fundamenta Informaticae,2013,126(4):415-432.

[13]Yao Xin,Chen Guoliang.Simulated annealing algorithm and its applications[J].Journal of Computer Research and Development,1990,27(7):1-6.

[14]Jia Xiuyi,Shang Lin.A simulated annealing algorithm for learning thresholds in three-way decision-theoretic rough set model[J].Journal of Chinese Computer Systems,2013,34 (11):2603-2606.

[15]Li Huaxiong,Liu Dun,Zhou Xianzhong.Rewiew on decisiontheoretic rough set model[J].Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition, 2010,22(5):624-630.

附中文參考文獻：

[2]王國胤,姚一豫,于洪.粗糙集理論與應用研究綜述[J].計算機學報,2009,32(7):1229-1246.

[6]李華雄,周獻中,黃兵,等.決策粗糙集與代價敏感分類[J].計算機科學與探索,2013,7(2):126-135.

[8]劉家彬,閔帆.代價敏感粗糙集研究綜述[J].漳州師范學院學報:自然科學版,2011,24(4):17-22.

[9]黃國順.保正域的決策粗糙集屬性約簡[J].計算機工程與應用,2016,52(2):165-169.

[10]張智磊,劉三陽.基于回溯搜索算法的決策粗糙集屬性約簡[J].計算機工程與應用,2016,52(10):71-74.

[11]賈修一,商琳,陳家駿.決策風險最小化屬性約簡[J].計算機科學與探索,2011,5(2):155-160.

[13]姚新,陳國良.模擬退火算法及其應用[J].計算機研究與發(fā)展,1990,27(7):1-6.

[14]賈修一,商琳.一種求三支決策閾值的模擬退火算法[J].小型微型計算機系統(tǒng),2013,34(11):2603-2606.

[15]李華雄,劉盾,周獻中.決策粗糙集模型研究綜述[J].重慶郵電大學學報:自然科學版,2010,22(5):624-630.

LIU Cai was born in 1991.He is an M.S.candidate at Guangxi University.His research interests include decision theoretic rough sets,data mining and machine learning,etc.

劉偲（1991—），男，湖南岳陽人，廣西大學計算機與電子信息學院碩士研究生，主要研究領域為決策粗糙集，數據挖掘，機器學習等。

秦亮曦（1963—），男，廣西靈川人，2005年于中國科學院大學計算機軟件與理論專業(yè)獲得博士學位，現(xiàn)為廣西大學教授，主要研究領域為數據挖掘，決策粗糙集等。

Test-Cost Sensitive Reduction on Positive Region of Decision Theoretic Rough Sets*

LIU Cai+,QIN Liangxi
School of Computer,Electronics and Information,Guangxi University,Nanning 530004,China
+Corresponding author:E-mail:liucaitc@163.com

This paper studies the test-cost sensitive reduction on the positive region of decision theoretic rough sets (DTRS).Based on the traditional positive region-based reduction,this paper takes test cost into account for the purpose of discovering the positive region-based reduction with the minimum total test cost,and adopts the simulated annealing algorithm combined with traditional positive region-based reduction of DTRS algorithm to search for the result of the positive region-based reduction with the minimum test cost.Furthermore,this paper proposes a testcost sensitive positive region-based reduction algorithm for DTRS(TCSPR),and analyzes the time complexity of the algorithm.The experimental results confirm the effectiveness of TCSPR that can find a positive region reduction with fewer attributes and less test cost in polynomial time,and whose solution is generally the optimum solution or second-best solution of the optimization objective,viz.the positive region-based reduction with the minimum total test cost,and whose classification ability is hardly reduced in part of the data sets.

decision theoretic rough sets(DTRS);cost sensitive;attribute reduction

xi was born in 1963.He

the Ph.D.degree in computer software and theory from University of Chinese Academy of Sciences in 2005.Now he is a professor at Guangxi University.His research interests include data mining and decision theoretic rough sets,etc.

A

TP181

*The National Natural Science Foundation of China under Grant No.61363027(國家自然科學基金).

Received 2016-03,Accepted 2016-08.

CNKI網絡優(yōu)先出版:2016-08-15,http://www.cnki.net/kcms/detail/11.5602.TP.20160815.1659.002.html