基于測試代價敏感的不完備決策系統屬性約簡算法

謝小軍　徐章艷　喬麗娟　朱金虎

(廣西多源信息挖掘與安全重點實驗室　廣西 桂林 541004)(廣西師范大學計算機科學與信息工程學院　廣西 桂林 541004)

?

基于測試代價敏感的不完備決策系統屬性約簡算法

謝小軍徐章艷喬麗娟朱金虎

(廣西多源信息挖掘與安全重點實驗室廣西 桂林 541004)(廣西師范大學計算機科學與信息工程學院廣西 桂林 541004)

提出不完備決策系統測試代價敏感屬性約簡問題，給出不一致對象集定義以及求解不一致對象集的算法。根據不一致對象的性質改進屬性重要性定義，考慮測試代價因素以及不一致對象個數的改變量給出一個新的屬性重要性的定義和屬性重要性中權重的設置方法，并給出屬性重要性的計算算法。在此基礎上，給出一個時間復雜度為O(k|C|2|U|)和空間復雜度為O(|U|)的啟發式屬性約簡算法，并通過理論分析、實例分析和實驗分析說明該算法準確性和可行性。

測試代價敏感不完備決策系統屬性重要性屬性約簡不一致對象

0　引　言

在近些年數據挖掘和機器學習的研究中，代價敏感學習得到了許多研究者的關注，也獲得了重要的進展。Turney[1]提出代價敏感樹算法，該算法考慮了測試代價和誤分類代價。隨后文獻[2]中提出9種不同類型的代價：誤分類代價、測試代價、計算代價、指導代價、干預代價、副作用引起的代價、獲取樣本的代價、不穩定性代價和人機交互的代價。這些代價在我們現實生活中也是存在的，例如在醫療系統病人需要花費金錢、時間以及其他代價來獲得最終的診斷結果。因此代價問題是一項具有意義的研究。

波蘭科學家Pawlak[3]在20世紀80年代提出粗糙集理論，粗糙集理論是數據挖掘中一種常見的處理模糊性和不精確性知識的數學工具。屬性約簡是粗糙集理論研究的主要內容之一，將代價引入屬性約簡問題使得其更具有現實意義和實用性[4]，很多學者通過不同方面的代價敏感屬性約簡進行研究分析。文獻[5]首先提出代價敏感粗糙集理論體系以及獨立測試代價敏感決策系統，測試代價敏感屬性約簡目的就是以最小的測試代價獲得約簡結果，即最小測試代價屬性約簡。文獻[6]中提出一個搜索樹算法來解決最小測試代價屬性約簡問題。該算法都能得出較好的約簡結果，對于較大的數據集而言搜索空間較大導致算法效率不高。文獻[5]中提出一個傳統啟發式的最小測試代價屬性約簡算法。該算法時間復雜度和空間復雜度為O(|C|3|U|2)和O(|C||U|)。文獻[7]中提出一種基于遺傳算法的最小測試代價屬性約簡算法，該算法給我們提供一個很好的解決屬性約簡問題的思路，并且較傳統的啟發式算法更效率，還有很多學者提出一些改進的啟發式算法[8]和快速隨機的算法[9]。

在完備決策系統中測試代價敏感屬性約簡已經取得了一定的成功，但是在現實生活中，由于信息的缺失或者遺漏，導致決策系統不完備。因此將測試代價引入不完備決策系統具有更高的研究意義，文獻[10]中提出基于測試代價敏感的不完備信息系統可變精度分類粗糙集模型，并給出了啟發式的屬性約簡算法。本文提出一種基于容差關系的測試代價敏感不完備決策系統屬性約簡算法。該算法改進了傳統的屬性重要性的定義，在屬性重要性中考慮測試代價因素得出一個新的屬性重要性定義。最后通過理論分析、實例分析和實驗分析說明該算法的準確性和可行性。

1　基本概念

一個決策系統可以表示為五元組:S=(U,C,D,V,f)，其中U={x1,x2,…,xn}是論域(對象集)； C為條件屬性集； D為決策屬性；f:U×(C∪D)→V是信息函數，其中F=C∪D，C∩D= ?，V=∪Va，a∈F，Va表示屬性a的值域。

定義1在決策系統S中，用“*”表示缺省值，若S中至少存在一個“*”，即至少存在a∈C，x∈U，使得f(x,a)=*，則稱該信息系統為不完備決策系統。

定義2一個測試代價獨立的不完備決策系統定義如下：S=(U,C,D,V,f,c)，其中U,C,D,V,f與定義1中的U,C,D,V,f相同，c：表示一個測試代價函數，其中代價為一個非負數。

由于測試代價之間相互獨立，測試代價函數表示為：c=[c(a1),c(a2),…,c(a|C|)]。對于?B?C有條件屬性集B的測試代價為：c(B)=∑c(ai),ai∈B。表1和表2給出一個簡單的醫療不完備決策系統和該決策系統的測試代價向量。

表1　一個簡單的醫療不完備決策系統

表2　一個簡單的測試代價向量

定義3[11]不完備決策表中S=(U,C,D,V,f)，對于?B?C，定義B上的容差關系T(B)如下：

T(B)={(x,y)|(x,y)∈U×U,?b∈B,f(x,b)=f(y,b)∨f(x,b)=*∨f(y,b)=*}

TB(x)表示在B下與對象x具有容差關系的對象的集合即在條件屬性集下的容差類。

定義4[12]不完備決策表S=(U,C,D,V,f)中，對于條件屬性集B?C所產生的容差類TB(x)中，對于?a∈B,?y1,y2∈TB(x)有f(y1,D)≠f(y2,D)則稱在條件屬性集B中產生不一致對象。若B=C，則稱該決策表為不一致決策表。

定義5[13]不完備決策表S=(U,C,D,V,f)中，對于B?C，Q?D,U/D={D1,D2,…,Dk}則B相對于Q的正區域定義如下：POSB(D)=∪{x|x∈U,TB(x)?Di}，其中Di∈U/D由定義可知C相對于D的正區域可以為如下：POSC(D)=∪{x|x∈U,TC(x)?Di}其中Di∈U/D。

定義6[13]不完備決策表S=(U,C,D,V,f)中，對?B?C，POSB(D)=POSC(D)且?a∈B使得POSB-{a}(D)≠POSC(D)則稱B是C相對于D的一個屬性約簡。

定義7不完備決策表S=(U,C,D,V,f)中，對于B?C，定義在B上產生的不一致對象集定義如下：RB={x|x∈U,|TB(x)/D|≠1},若B=?則RB=U。

定理1不完備決策表S=(U,C,D,V,f)中，對于B?C在B上產生的不一致對象集與B相對于D的正區域滿足：RB=U-POSB(D)。

而RB={x|x∈U,|TB(x)/D|≠1}，故可有對于任意一個對象不是在POSB(D)中就是在RB即可得證RB=U-POSB(D)，證畢。

性質1不完備決策表S=(U,C,D,V,f)中，對于?B?C，有RB=RC和POSB(D)=POSC(D)是等價的。

由定理1可知RB=U-POSB(D)，如果RB=RC那么POSB(D)=POSC(D)，如果POSB(D)=POSC(D)那么RB=RC很顯然兩者是等價的。

性質2不完備決策表S=(U,C,D,V,f)中，對?B?C，RB=RC,且?a∈B使得RB-{a}≠RC則稱B是C相對于D的一個屬性約簡。

性質2由性質1得到。

定理2不完備決策表S=(U,C,D,V,f)中，對?B?C，a∈C-B可有RB∪{a}?RB。

證明：對于xi∈U，易知TB∪{a}(xi)?TB(xi)。

則TB∪{a}(xi)/D?TB(xi)/D。

可知假設|TB(xi)/D|=1那么一定有|TB∪{a}(xi)/D|=1。

而假設|TB∪{a}(xi)/D|=1那么不能確定|TB∪{a}(xi)/D|=1是否成立。

又假設|TB∪{a}(xi)/D|≠1那么一定有|TB(xi)/D|≠1。

而假設|TB(xi)/D|≠1那么不能確定|TB∪{a}(xi)/D|≠1是否成立。

由上可得xi∈U，|TB∪{a}(xi)/D|≠1的對象個數不多于|TB(xi)/D|≠1。

若x∈RB∪{a}，則x∈RB。

即RB∪{a}?RB，即得證。由定理2易知|RB∪{a}|≤|RB|。

根據式(28)可知聯立式(27)和式(29)可得累積公差與同軸度Tc的關系。依據3.3節和式(29)構建FM在Lv、Q方向的2維空間域，其2維空間域的2維空間域的位置關系如圖14所示。

2　基本算法

2.1容差類

在不完備決策系統的屬性約簡中，求容差類的計算時間影響整個屬性約簡過程的效率，目前文獻[14]中的求解容差類的算法較高效，該算法基于基數排序思想求容差類，時間復雜度為O(k|C||U|)，其中k為條件屬性中缺省對象所產生的容差類最大的個數，該算法利用文獻[15]中求等價類的算法思想。但是該時間復雜度是在條件屬性值為一位數據的時候才能得到此結果，基數排序的時間復雜度為O(m|U|)，其中m為屬性值的位數。本文提出一個新的求解容差類的算法，該算法的時間復雜度為O(k|C||U|)，能更有效率更適合求屬性值為多位的容差類。

算法1求測試代價獨立的不完備決策系統的容差類Tai(x)

輸入：S=(U,C,D,V,f,c)，B?C，其中U={x1,x2,…,x|U|},B={a1,a2,…,a|B|}

輸出：Tai(x)，其中i∈[1,|B|]

Step1計算條件屬性ai中f(x,ai)的最大值max和最小值min；

若存在 f(x,ai)=*max=max+1；

對于所有f(x,ai)=*f(x,ai)=max；

Step2建立一個大小為max-min的對象數組X[max-min],數組中X每一元素對應儲存對象的集合(儲存對象的下標來儲存對象的集合)，初始化X[i]←?，i∈[0,max-min]；

Step3for(j=1;j<|U|+1;j++)

X[f(xj,ai)-min]←X[f(xj,ai)-min]∪{xi}//掃描所

//有對象將每一個對象根據f(x,ai)分別儲存在對象數組的每

//一個元素中(儲存對象的下標來儲存對象的集合)；

Step4for(k=0;k

?xj∈X[k]，Tai(xj)=X[k]∪X[max-min]；

Step5?xj∈X[max-min],Tai(xj)=U。

算法1主要計算條件屬性ai的容差類Tai(x)。Step1、Step2的時間復雜度為O(|U|)，Step3循環|U|，故時間復雜度也為O(|U|)，Step4、Step5的時間復雜度同樣也是O(|U|)。故算法1時間復雜為O(|U|)。

算法2求測試代價獨立的不完備決策系統的容差類TP(x)

輸入：S=(U,C,D,V,f,c)，B?P?C，其中U={x1,x2,…,x|U|},B={a1,a2,…,a|B|}，Tai(x)，TB(x)

輸出：TB∪{a}(x)

Step1統計所有對象f(x,a)；

Step2if(f(x,a′)==*)

TP∪{a′}(x)=TP(x)；

elseif(?x′∈Tp(x)∧f(x′,a′)==*∨f(x′,a′)==f(x,a′))

TP∪{a′}(x)=TP(x)∪{x′}；

Step3輸出TB∪{a}(x)。

很顯然根據算法2可以求出TP(x)。該算法根據TB(x)求TB∪{a}(x)的時間復雜度為O(k|U|)其中k=max|TB(xi)|，若求TP(x)只需要循環|P-B|次時間復雜度為O(k|P-B|·|U|)而最壞的情況下空間復雜度為O(|U|)。

2.2不一致對象集

根據不一致對象集的定義，求解不一致對象集主要是要求容差類，由算法1、算法2可以快速地求解容差類，然后設計算法3求解不一致對象集以及對象集的對象個數。

算法3求測試代價獨立的不完備決策系統的不一致對象集RB

輸入：S=(U,C,D,V,f,c)，B?C，其中U={x1,x2,…,x|U|},B={a1,a2,…,a|B|}，TB(x)

輸出：RB，|RB|

Step1RB=?；N=0；flag=0；

Step2對于取任意一個對象x′∈U；

Step3U=U-{x′}；TB(x′)={y1,y2,…,y|TB(x′)|}；

Step4if(|TB(x′)|>1)

{for(i=1;i<|TB(x′)|+1;i++)

if(f(yi,D)≠f(x′,D))

{ RB=RB∪{x′}；N++；flag=1；break；}

}

Step5if(flag==0) return Step2；

Step6輸出RB和N。

該算法主要通過求出每個對象的容差類，在容差類中是否與該對象決策值一致，不一致就把該對象并入不一致對象集中。該算法主要是計算容差類。故該算時間復雜度為O(k|C|·|U|)，其中k=max|TB(xi)|。空間復雜度為O(|U|)。

3　屬性約簡算法

定義8[5]最小測試代價屬性約簡定義如下：設R(S)為測試代價獨立的不完備決策系統的相對約簡的集合。對于?R∈R(S)，c(R)=min{c(R′)|R′∈R(S}，則R就是一個最小測試代價約簡。

測試代價敏感屬性約簡的目的就是以最小的測試代價獲得約簡結果，在測試代價獨立的不完備決策系統中的屬性約簡問題可以描述如下：

問題1測試代價獨立的不完備決策系統的屬性約簡

輸入：決策系統S=(U,C,D,V,f,c)，測試代價函數c*

輸出：B?C

約束條件：RB=RC

最優化目標：minc(B)

3.1屬性重要性及其計算算法

測試代價獨立不完備決策系統的屬性約簡是一個最優或者次優約簡問題，采用啟發式算法解決最優或者次優約簡問題相對比較理想。在建立啟發式屬性約簡算法中，根據屬性的重要性來建立啟發函數可以提高算法的效率。本文同時考慮屬性重要性以及測試代價因素建立一個測試代價獨立不完備決策系統的屬性重要性啟發函數。

定義9[16]不完備決策表S=(U,C,D,V,f,c)中，屬性a∈C-B(B?C)，相對于D的屬性重要性定義如下：

SGF(a,B,D)=γB∪{a}-γB

其中γB=|POSB(D)|/|U|

定理3不完備決策表S=(U,C,D,V,f)中，對于B?C，a∈C-B,則屬性重要性如下：

證明：由定義9可知屬性重要性：

根據定義定理1可有：

性質3不完備決策表S=(U,C,D,V,f)中，對于B?C，a∈C-B,有屬性重要性Sig(B,a)，若Sig(B,a)=0，則POSB∪{a}(D)=POSB(D)。

證明：Sig(B,a)=0，即|RB|-|RB∪{a}|=0，|RB|=|RB∪{a}|，由定理2可知，對于?x∈RB∪{a}，則?x∈RB，即RB∪{a}?RB又因為|RB|=|RB∪{a}|，可得RB∪{a}和RB一定滿足RB∪{a}=RB，根據性質1，可有POSB∪{a}(D)=POSB(D)，即得到性質3。

定義10測試代價獨立的不完備決策系統S=(U,C,D,V,f,c)對于B?C，a∈C-B,則屬性重要性定義如下：

說明：由定義中SIGcost為一個考慮測試代價和約簡的屬性重要性，SIGcost的值越大則表示屬性測試代價小且該屬性越重要。其中c(B)表示條件屬性集B的測試代價，其中c(B∪{a})表示條件屬性集B∪a的測試代價。α>0和β≥0是權重系數，且α+β=1。當β取0時表示不考慮測試代價因素，α和β的大小影響屬性重要性與測試代價因素的重要性，α較大時屬性重要性更重要，β較大時測試代價因素更重要。

對于定義10的屬性重要性的定義，在約簡過程中屬性重要性和測試代價因素的權重α和β隨著約簡的進行不斷改變。剛開始為了得到測試代價低且是重要屬性的屬性可以設置測試代價因素的重要性與約簡的重要性等同，隨著約簡個數的增多對分類精度的要求變高而測試代價因素變低。本文給出一個改進后屬性重要性的權值設置如下：

首先初始α和β的權值為β?，α?=1-β?表示為：

隨著約簡個數的增多屬性重要性的權值表示為：

根據該權重表達式測試代獨立的不完備決策系統屬性重要性可表示為：

對于SIGCOST(B,a,c)和Sig(B,a)，根據算法1-算法3我們可以得出求屬性重要性的計算算法。SIGCOST(B,a,c)越大且Sig(B,a)≠0表示該屬性較重要，而SIGCOST(B,a,c)不管多大Sig(B,a)=0則該屬性為冗余屬性。下面給出改進屬性重要性的計算算法。

算法4測試代價獨立的不完備決策系統屬性重要性的計算算法

輸入：S=(U,C,D,V,f,c),B?C其中U={x1,x2,…,x|U|}，B={a1,a2,…,a|B|}，c=[c(a1),c(a2),…,c(a|c|)]

輸出：sig(B,a)和SIGCOST(B,a,c(a))

Step1由算法1、2、3可以求出TB(x)，RB以及|RB|；

Step2對于任何一個a∈C-B由算法1、2、3可得出TB∪{a}(x)，RB∪{a}以及|RB∪a|；

Step3計算c(B)和c(B∪{a})；

算法4根據算法1-算法3可以依次很快速地求出結果。

算法4中Step1求TB(x)和RB的時間復雜度為O(k|C||U|)，其中k=max|TB(xi)|。Step2中根據Step1的結果中求TB∪{a}(x)和RB∪{a}的時間復雜度為O(k|C||U|)，其中，k=max|TB∪{a}(xi)|。Step3計算測試代價的時間復雜度為O(1)。Step4根據Step1-Step3的結果計算兩個屬性重要性的時間復雜度為O(1)。所以算法4主要是在求容差類和不一致對象集，故時間復雜度為O(k|C||U|)，空間復雜度為O(|U|)，其中k=max{|TB(xi)||B?C,xi∈U}。

3.2約簡算法

算法4給出求解屬性重要性的算法，我們可以根據算法4給出一個測試代價獨立不完備決策系統的屬性約簡算法。

算法5測試代價獨立的不完備決策系統的屬性約簡算法

輸入：S=(U,C,D,V,f,c)，其中U={x1,x2,…,x|U|}，C={a1,a2,…,a|C|}，c=[c(a1),c(a2),…,c(a|C|)]

輸出：屬性約簡R

Step1令R=?；

Step2對于任何一個a∈C-R根據算法求出屬性重要度sig(R,a)和SIGCOST(R,a,c(a))；

計算SIGCOST(R,a′,c(a′))=maxSIGCOST(R,a,c(a))；

Step3若sig(R,a′)≠0

R=R∪{a′}；

Step4否則C=C-{a′}；return Step2；

Step5若C-R=?;

輸出R。

算法5中Step2主要計算屬性重要性根據，算法4時間復雜度分析可知，該步驟時間復雜度為O(k|C||U|)，其中k=max{|TB(xi)||B?C,xi∈U}，Step3、Step4是一個循環過程，每次循環剔除一個屬性，最多循環|C|次。故該算法總的時間復雜度為O(k|C|2|U|)，空間復雜度為O(|U|)。

4　實例分析

本節根據表1簡單醫療不完備決策系統說明本文中的算法，其中改進的屬性重要性權重設置使用本文給出的權重設置方法。將表1中屬性值映射成表3所示結果。

表3　一個簡單的醫療不完備系統的映射

用算法1分別求出條件屬性ai的容差類Ta4(x)；

對于屬性a4由算法1可有max=2+1=3和最小值min=1；

建立一個數組X[max-min]=X[3-1]=X[2]；

X[0]={1,2}；

X[1]={3,4,5}；

X[2]={6,7}；

故可得：Ta4(x1)=Ta4(x2)={1,2,6,7},Ta4(x3)=Ta4(x4)=Ta4(x5)={3,4,5},Ta4(x6)=Ta4(x7)=U

根據算法1可以依次求出Tai(x)。

再結合算法1、算法2求出TB∪{a}(x)。

|R?|=7，根據算法3、算法4首先求出sig(?,a)和SIGCOST(?,a,c(a))；

|Ra1|=7，|Ra2|=7，|Ra3|=4，|Ra4|=7

sig(?,a1)=0；sig(?,a2)=0；sig(?,a3)=3/7；sig(?,a4)=0

SIGCOST(?,a1,c(a1))=0；SIGCOST(?,a2,c(a2))=0；SIGCOST(?,a3,c(a3))=3/7；SIGCOST(?,a4,c(a4))=0

取最大的SIGCOST(?,a3,c(a3))=3/7，且sig(?,a3)≠0，則R={a3}，C={a1,a2,a4}

|R{a1,a3}|=4，|R{a2,a3}|=4,|R{a3,a4}|=3

sig(a3,a1)=0，sig(a3,a2)=0，sig(a3,a4)=1/7

|R{a1,a3,a4}|=3，|R{a2,a3,a4}|=3

sig({a3,a4},a1)=0；sig({a3,a4},a2)=0

均為零，C=C-{a1,a2}={a3,a4}；C-R=?;故輸出屬性約簡R={a3,a4}。

在表1所示的一個簡單醫療不完備決策系統中，我們可初步花最小的代價去檢測體溫和心跳，就可以快速地確診是否患流感。這里得出的結果與現實是一致的，我們生活中去初步判斷是否得了流感，首先檢查體溫和心跳,說明本文算法是正確的。

5　實驗分析

本節通過實驗從UCI數據庫中根據數據集的規模分別選取4個數據集進行實驗。對本文算法(記為NEW-Algorithm)和文獻[5]傳統的啟發式算法(記為1-Algorithm)進行實驗比較。由于UCI大部分數據沒有測試代價數據，本文在每組數據中增加測試代價數據，設置測試代價在[1，100]區間內，設置屬性重要性權重使用本文給出的權重設置方法。實驗結果記錄約簡個數、測試代價以及運行時間，見表4所示。

表4　兩種約簡算法實驗結果

由表4中數據對比分析可以看出1-Algorithm算法獲得的測試代價總是比NEW-Algorithm要大，并1-Algorithm算法運行時間要比NEW-Algorithm運行的時間要多，這里我們可以通過時間復雜度分析可知1-Algorithm算法時間復雜比NEW-Algorithm大得多。因此本文中的NEW-Algorithm算法改進了啟發函數，比傳統的啟發式算法更適合測試代價敏感的屬性約簡問題。

6　結　語

在基于容差關系的不完備決策系統屬性約簡中，首先要計算容差類，屬性約簡過程大部分時間是在求容差類。設計一個更適合求容差類的算法，無論屬性值為多少位都可以用該算法快速的求出，該算法改進了基于基數排序的求容差類的算法中算法時間復雜度受屬性值位數的影響。根據容差類給出不完備決策系統不一致對象集的定義以及求解不一致對象集的算法。利用不一致對象集和正區域的關系，再考慮到測試代價改進屬性重要性設計一個新的屬性重要性的計算公式并給出屬性重要性的計算方法。結合兩種屬性重要性的性質設計一個測試代價敏感不完備決策系統的屬性約簡算法。理論分析、實例分析和實驗分析得出該算法的有效性和可行性。

本文只考慮了測試代價，結合誤分類代價研究不完備決策系統代價敏感屬性算法以及利用群智能算法解決代價敏感屬性約簡問題是下一步研究工作。

[1] Turney P D.Cost-sensitive classification:empirical evaluation of a hybrid genetic decision tree induction al-gorithm[J].Journal of Artificial Intelligence Research,1994,2(1):369-409.

[2] Turney P.Types of cost in inductive concept learning[C]//Proceedings of the Cost-Sensitive Learning Workshop at the 17th ICML-2000 Conference,Stanford,CA,Jul 2,2000.Ottawa,CA:National Research Council of Canada,2000:15-21.

[3] Pawlak Z.Rough Sets[J].International Journal of Computer and information Science,1982,11(5):341-356.

[4] 林姿瓊,李靜寬,趙紅.名詞性數據的五種代價敏感屬性約簡算法比較[J].計算機科學與探索,2014(9):1137-1145.

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

[6] Min Fan,Zhu W.Minimal cost attribute reduction through backtracking[C]//Proceedings of the 2011 Inter-national Conferences on Database Theory and Applica-tion,Bio-Science and Bio-Technology (DTA and BSBT 2011),Jeju Island,Korea,Dec8-10, 2011.Berlin,Hei-delberg:Springer-Verlag,2011:100-107.

[7] Jiabin Liu,Fan Min,Shujiao Liao,et al.Test Cost Constraint Attribute Reduction Through a Genetic Approach[J].J Inf Comput Sci,2013,10(3):839-849.

[8] Xu Zilong,Min Fan,Liu Jiabin,et al.Ant colony opti-mization to minimal test cost reduction[C]//Proceedings of the 2012 IEEE International Conference on Granular Computing (GrC’12),Hangzhou,China,Aug 2012.Pis-cataway,NJ,USA:IEEE,2012:585-590.

[9] Li Jingkuan,Min Fan,Zhu W. Fast randomized algorithm for minimal test cost attribute reduction[C]//Proceedings of the International Conference on Reliability,Infocom Technologies and Optimization (ICRITO’13),Noida,In-dia,Jan 29-31,2013:12-17.[10] 鞠恒榮,馬興斌,楊習貝,等.不完備信息系統中測試代價敏感的可變精度分類粗糙集[J].智能系統學報,2014,9(2):219-223.

[11] Kryskiewicz M.Rules in incomplete imformarion systems[J].Information Sciences,1999,113(2):271-292.

[12] 劉勇,熊蓉,褚健.Hash快速屬性約簡算法[J].計算機學報,2009,32(8):1493-1499.

[13] 王煒,徐章艷,李曉瑜.不完備決策表中基于對象矩陣屬性約簡算法[J].計算機科學,2012,39(4):201-204.

[14] 錢文彬,楊炳儒,徐章艷,等.基于不完備決策表的容差類高效求解算法[J].小型微型計算機系統,2013,34(2):345-350.

[15] 徐章艷,劉作鵬,楊炳儒,等.一個復雜度為max(O(|C||U|),O(|C|2|U/C|))的快速屬性約簡算法[J].計算機學報,2006,29(3):391-399.

[16] 劉少輝,盛秋戩,吳斌,等.Rough集高效算法的研究[J].計算機學報,2003,26(5):524-529.

ATTRIBUTE REDUCTION ALGORITHM OF INCOMPLETE DECISION SYSTEM BASED ON TEST COST SENSITIVITY

Xie XiaojunXu ZhangyanQiao LijuanZhu Jinhu

(Guangxi Key Lab of Multi-source Information Mining and Security,Guilin 541004,Guangxi,China)(CollegeofComputerScienceandInformationTechnology,GuangxiNormalUniversity,Guilin541004,Guangxi,China)

We introduced the problem of test-cost-sensitive attribute reduction in incomplete decision system, and suggested the definition of inconsistent object set and an algorithm for computing the inconsistent object set. According to the nature of inconsistent object set we improved the definition of attribute significance. Considering the test cost factors and the varied amount of the number of inconsistent objects we presented a new definition of attribute significance and the weight setting method of it. And then we gave the calculation algorithm of attribute significance. Based on these conditions, we proposed a heuristic attribute reduction algorithm with the time complexity O(k|C|2|U|) and the space complexity O(|U|). Through theoretical analysis, example analysis and experiment analysis we explained the accuracy and feasibility of the reduction algorithm.

Test-cost-sensitiveIncomplete decision systemAttribute significanceAttribute reductionInconsistent object

2015-06-12。國家自然科學基金項目(61262004，6136 3034，60963008)；廣西自然科學基金項目(2011GXNSFA018163)；八桂學者專項基金。謝小軍，碩士生，主研領域：數據挖掘，粗糙集理論及其應用。徐章艷，教授。喬麗娟，碩士生。朱金虎，碩士生。

TP18

A

10.3969/j.issn.1000-386x.2016.09.062