劉 偲，秦亮曦

廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，南寧 530004

測(cè)試代價(jià)敏感的決策粗糙集正域約簡(jiǎn)*

劉 偲+，秦亮曦

廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，南寧 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.

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

決策粗糙集（DTRS）；代價(jià)敏感；屬性約簡(jiǎn)

1 引言

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

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

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

本文將測(cè)試代價(jià)納入正域約簡(jiǎn)的考慮范圍，在正域約簡(jiǎn)的基礎(chǔ)上用模擬退火方法找到測(cè)試代價(jià)總和最小的正域約簡(jiǎn)結(jié)果。通過(guò)找到測(cè)試代價(jià)總和最小的正域約簡(jiǎn)，可以在實(shí)際應(yīng)用中，找到一個(gè)分類能力和屬性全集相近但測(cè)試代價(jià)大大降低的屬性約簡(jiǎn)。

2 相關(guān)理論介紹

2.1 決策粗糙集正域約簡(jiǎn)

在經(jīng)典粗糙集正域約簡(jiǎn)中，因?yàn)榻?jīng)典粗糙集具有正域單調(diào)性，所以Pawlak正域約簡(jiǎn)要求屬性子集的正域保持不變。但是決策粗糙集模型中，正域不具備單調(diào)性，即正域不會(huì)隨著屬性的增加而擴(kuò)大。針對(duì)決策粗糙集的這種情況，Yao等人在文獻(xiàn)[5]中給出了新的屬性約簡(jiǎn)定義。

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

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

如果屬性子集同時(shí)滿足上述兩個(gè)性質(zhì)，則屬于一個(gè)正域約簡(jiǎn)，正域約簡(jiǎn)可能不止一個(gè)。

2.2 決策粗糙集正域約簡(jiǎn)算法

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

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

文獻(xiàn)[12]給出了決策粗糙集α-正域約簡(jiǎn)算法。

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

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

輸出：該決策表的α-正域約簡(jiǎn)。

步驟1令初始α-正域約簡(jiǎn)屬性集B=?。

步驟2計(jì)算C中每個(gè)屬性的α-正域全局重要度γ

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

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

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

步驟6輸出該決策表的一個(gè)α-正域約簡(jiǎn)。

3 測(cè)試代價(jià)敏感與屬性約簡(jiǎn)

3.1 測(cè)試代價(jià)敏感

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

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

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

在考慮樣本x在屬性子集B上的測(cè)試代價(jià)時(shí)，假設(shè)各個(gè)樣本在同一屬性上的測(cè)試代價(jià)是相等的，因此，x在屬性子集B上的測(cè)試代價(jià)為屬性子集B中所有屬性測(cè)試代價(jià)的和，測(cè)試代價(jià)設(shè)為一個(gè)非負(fù)實(shí)數(shù)?？梢缘玫揭粋€(gè)計(jì)算測(cè)試代價(jià)函數(shù)[6]：

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

3.2 屬性約簡(jiǎn)

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

首先，通過(guò)算法1的前4步找到一個(gè)屬性子集，該屬性子集的正域不小于屬性全集的正域，用該屬性子集作為初始集合。然后，結(jié)合模擬退火的方法[13-14]，在溫度的每個(gè)平衡點(diǎn)用隨機(jī)變換產(chǎn)生屬性子集，并在當(dāng)前溫度下判斷是否保留此變換。最后保留下來(lái)的即為測(cè)試代價(jià)總和最小的正域約簡(jiǎn)。

算法2TCSPR

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

輸出：測(cè)試代價(jià)敏感的正域約簡(jiǎn)。

步驟1令初始正域約簡(jiǎn)屬性集B=BOringe，令P=C-BOringe，計(jì)算初始化tmin,t。

步驟2通過(guò)隨機(jī)刪除、替換、添加屬性的方式，由屬性集B產(chǎn)生新的B*。

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

步驟6判斷當(dāng)t>tmin并且結(jié)果不收斂時(shí)，回到步驟2，并讓t衰減一個(gè)Δt。

步驟7輸出B即為測(cè)試代價(jià)總和最小的正域約簡(jiǎn)。

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

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

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

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

模擬退火算法是一種隨機(jī)算法，每次運(yùn)行的狀態(tài)可能不一致，因此對(duì)每個(gè)數(shù)據(jù)集都運(yùn)行10次取平均值作為運(yùn)行結(jié)果。

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

Table 1 Basic information of experimental data表1 實(shí)驗(yàn)數(shù)據(jù)基本信息

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

Table 2 Misclassification cost matrix表2 誤分類代價(jià)矩陣

數(shù)據(jù)集中沒有給出各屬性的測(cè)試代價(jià)，因?qū)嶒?yàn)需要，本文假定各測(cè)試代價(jià)服從正態(tài)分布N(μ,σ)，并設(shè)Spambase的屬性測(cè)試代價(jià)服從N(0.2,0.1)，WDBC和WPBC的屬性測(cè)試代價(jià)服從N(0.02,0.01)，使用正態(tài)隨機(jī)函數(shù)隨機(jī)生成各屬性的測(cè)試代價(jià)。

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

表3為3組屬性約簡(jiǎn)實(shí)驗(yàn)結(jié)果（比較約簡(jiǎn)屬性集平均個(gè)數(shù)）。

由表3可以看出，算法2約簡(jiǎn)后得到的最優(yōu)屬性集個(gè)數(shù)更少，特別是在WPBC數(shù)據(jù)集上，算法2在算法1的基礎(chǔ)上約簡(jiǎn)了77%的屬性個(gè)數(shù)，但是正域?qū)ο髠€(gè)數(shù)和算法1得到的正域?qū)ο髠€(gè)數(shù)相差無(wú)幾，且算法2約簡(jiǎn)后的平均正域?qū)ο髠€(gè)數(shù)都大于等于全屬性集的正域?qū)ο髠€(gè)數(shù)。證明算法2能在保證約簡(jiǎn)后正域?qū)ο髠€(gè)數(shù)不減的情況下得到屬性個(gè)數(shù)更少的正域約簡(jiǎn)最優(yōu)屬性集，即具有更強(qiáng)的屬性約簡(jiǎn)能力。

Table 3 Comparison of experimental results表3 實(shí)驗(yàn)結(jié)果比較

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

Table 4 Average total test cost表4 平均總測(cè)試代價(jià)

表5展示了3組實(shí)驗(yàn)約簡(jiǎn)得到的最優(yōu)屬性集，對(duì)測(cè)試樣本集進(jìn)行風(fēng)險(xiǎn)最小化的決策粗糙集決策分類的平均正確率。

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

由表5可以看出，算法1在3個(gè)數(shù)據(jù)集上的分類正確率都比較高，而算法2只有在數(shù)據(jù)集Spambase上正確率和算法1相近，在另外兩個(gè)數(shù)據(jù)集上的正確率略低于算法1。由實(shí)驗(yàn)可以看出，在數(shù)據(jù)集Spambase上，相對(duì)算法1的測(cè)試代價(jià)約簡(jiǎn)率只為57.9%，屬性約簡(jiǎn)率只有32%；在WDBC和WPBC平均正確率較低的數(shù)據(jù)集上測(cè)試代價(jià)約簡(jiǎn)率高達(dá)96.1%和 96.2%，屬性約簡(jiǎn)率高達(dá)67%和77%。說(shuō)明單單追求測(cè)試代價(jià)的最小化將導(dǎo)致正確率的下降。

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

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

Table 6 Average running time表6 平均運(yùn)行時(shí)間 s

圖1~圖4分別展示了算法1和算法2在約簡(jiǎn)屬性集平均個(gè)數(shù)、平均總測(cè)試代價(jià)（因?yàn)閿?shù)量級(jí)不一致，將3組都化為同一數(shù)量級(jí)顯示）、分類平均正確率和平均運(yùn)行時(shí)間的比較。

Fig.1 Average number of reduction attribute set圖1 約簡(jiǎn)屬性集平均個(gè)數(shù)

Fig.2 Average total test cost圖2 平均總測(cè)試代價(jià)

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

Fig.4 Average running time圖4 平均運(yùn)行時(shí)間

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

5 結(jié)束語(yǔ)

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

[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.

附中文參考文獻(xiàn)：

[2]王國(guó)胤,姚一豫,于洪.粗糙集理論與應(yīng)用研究綜述[J].計(jì)算機(jī)學(xué)報(bào),2009,32(7):1229-1246.

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

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

[9]黃國(guó)順.保正域的決策粗糙集屬性約簡(jiǎn)[J].計(jì)算機(jī)工程與應(yīng)用,2016,52(2):165-169.

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

[11]賈修一,商琳,陳家駿.決策風(fēng)險(xiǎn)最小化屬性約簡(jiǎn)[J].計(jì)算機(jī)科學(xué)與探索,2011,5(2):155-160.

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

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

[15]李華雄,劉盾,周獻(xiàn)中.決策粗糙集模型研究綜述[J].重慶郵電大學(xué)學(xué)報(bào):自然科學(xué)版,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—），男，湖南岳陽(yáng)人，廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)闆Q策粗糙集，數(shù)據(jù)挖掘，機(jī)器學(xué)習(xí)等。

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

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(國(guó)家自然科學(xué)基金).

Received 2016-03,Accepted 2016-08.

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