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

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

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

?

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

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

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

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

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

0　引　言

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

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

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

1　基本概念

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

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

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

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

表1　一個簡單的醫(yī)療不完備決策系統(tǒng)

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

定義3[11]不完備決策表中S=(U,C,D,V,f)，對于?B?C，定義B上的容差關(guān)系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具有容差關(guān)系的對象的集合即在條件屬性集下的容差類。

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

定義5[13]不完備決策表S=(U,C,D,V,f)中，對于B?C，Q?D,U/D={D1,D2,…,Dk}則B相對于Q的正區(qū)域定義如下：POSB(D)=∪{x|x∈U,TB(x)?Di}，其中Di∈U/D由定義可知C相對于D的正區(qū)域可以為如下：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上產(chǎn)生的不一致對象集定義如下：RB={x|x∈U,|TB(x)/D|≠1},若B=?則RB=U。

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

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

性質(zhì)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很顯然兩者是等價的。

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

性質(zhì)2由性質(zhì)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。

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

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

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

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

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

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

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

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

2　基本算法

2.1容差類

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

算法1求測試代價獨立的不完備決策系統(tǒng)的容差類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的對象數(shù)組X[max-min],數(shù)組中X每一元素對應(yīng)儲存對象的集合(儲存對象的下標(biāo)來儲存對象的集合)，初始化X[i]←?，i∈[0,max-min]；

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

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

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

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

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的時間復(fù)雜度為O(|U|)，Step3循環(huán)|U|，故時間復(fù)雜度也為O(|U|)，Step4、Step5的時間復(fù)雜度同樣也是O(|U|)。故算法1時間復(fù)雜為O(|U|)。

算法2求測試代價獨立的不完備決策系統(tǒng)的容差類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統(tǒng)計所有對象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)。

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

2.2不一致對象集

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

算法3求測試代價獨立的不完備決策系統(tǒng)的不一致對象集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。

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

3　屬性約簡算法

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

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

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

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

輸出：B?C

約束條件：RB=RC

最優(yōu)化目標(biāo)：minc(B)

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

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

定義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可知屬性重要性：

根據(jù)定義定理1可有：

性質(zhì)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，根據(jù)性質(zhì)1，可有POSB∪{a}(D)=POSB(D)，即得到性質(zhì)3。

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

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

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

首先初始α和β的權(quán)值為β?，α?=1-β?表示為：

隨著約簡個數(shù)的增多屬性重要性的權(quán)值表示為：

根據(jù)該權(quán)重表達式測試代獨立的不完備決策系統(tǒng)屬性重要性可表示為：

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

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

輸入：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根據(jù)算法1-算法3可以依次很快速地求出結(jié)果。

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

3.2約簡算法

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

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

輸入：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根據(jù)算法求出屬性重要度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主要計算屬性重要性根據(jù)，算法4時間復(fù)雜度分析可知，該步驟時間復(fù)雜度為O(k|C||U|)，其中k=max{|TB(xi)||B?C,xi∈U}，Step3、Step4是一個循環(huán)過程，每次循環(huán)剔除一個屬性，最多循環(huán)|C|次。故該算法總的時間復(fù)雜度為O(k|C|2|U|)，空間復(fù)雜度為O(|U|)。

4　實例分析

本節(jié)根據(jù)表1簡單醫(yī)療不完備決策系統(tǒng)說明本文中的算法，其中改進的屬性重要性權(quán)重設(shè)置使用本文給出的權(quán)重設(shè)置方法。將表1中屬性值映射成表3所示結(jié)果。

表3　一個簡單的醫(yī)療不完備系統(tǒng)的映射

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

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

建立一個數(shù)組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

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

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

|R?|=7，根據(jù)算法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所示的一個簡單醫(yī)療不完備決策系統(tǒng)中，我們可初步花最小的代價去檢測體溫和心跳，就可以快速地確診是否患流感。這里得出的結(jié)果與現(xiàn)實是一致的，我們生活中去初步判斷是否得了流感，首先檢查體溫和心跳,說明本文算法是正確的。

5　實驗分析

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

表4　兩種約簡算法實驗結(jié)果

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

6　結(jié)　語

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

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

[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] 林姿瓊,李靜寬,趙紅.名詞性數(shù)據(jù)的五種代價敏感屬性約簡算法比較[J].計算機科學(xué)與探索,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] 鞠恒榮,馬興斌,楊習(xí)貝,等.不完備信息系統(tǒng)中測試代價敏感的可變精度分類粗糙集[J].智能系統(tǒng)學(xué)報,2014,9(2):219-223.

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

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

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

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

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

[16] 劉少輝,盛秋戩,吳斌,等.Rough集高效算法的研究[J].計算機學(xué)報,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。國家自然科學(xué)基金項目(61262004，6136 3034，60963008)；廣西自然科學(xué)基金項目(2011GXNSFA018163)；八桂學(xué)者專項基金。謝小軍，碩士生，主研領(lǐng)域：數(shù)據(jù)挖掘，粗糙集理論及其應(yīng)用。徐章艷，教授。喬麗娟，碩士生。朱金虎，碩士生。

TP18

A

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