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

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

(廣西多源信息挖掘與安全重點(diǎn)實(shí)驗(yàn)室　廣西 桂林 541004)(廣西師范大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院　廣西 桂林 541004)

?

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

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

(廣西多源信息挖掘與安全重點(diǎn)實(shí)驗(yàn)室廣西 桂林 541004)(廣西師范大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院廣西 桂林 541004)

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

測(cè)試代價(jià)敏感不完備決策系統(tǒng)屬性重要性屬性約簡(jiǎn)不一致對(duì)象

0　引　言

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

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

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

1　基本概念

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

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

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

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

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

表2　一個(gè)簡(jiǎn)單的測(cè)試代價(jià)向量

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

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

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

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

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

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

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

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

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

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

性質(zhì)2由性質(zhì)1得到。

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

證明：對(duì)于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的對(duì)象個(gè)數(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)的屬性約簡(jiǎn)中，求容差類的計(jì)算時(shí)間影響整個(gè)屬性約簡(jiǎn)過程的效率，目前文獻(xiàn)[14]中的求解容差類的算法較高效，該算法基于基數(shù)排序思想求容差類，時(shí)間復(fù)雜度為O(k|C||U|)，其中k為條件屬性中缺省對(duì)象所產(chǎn)生的容差類最大的個(gè)數(shù)，該算法利用文獻(xiàn)[15]中求等價(jià)類的算法思想。但是該時(shí)間復(fù)雜度是在條件屬性值為一位數(shù)據(jù)的時(shí)候才能得到此結(jié)果，基數(shù)排序的時(shí)間復(fù)雜度為O(m|U|)，其中m為屬性值的位數(shù)。本文提出一個(gè)新的求解容差類的算法，該算法的時(shí)間復(fù)雜度為O(k|C||U|)，能更有效率更適合求屬性值為多位的容差類。

算法1求測(cè)試代價(jià)獨(dú)立的不完備決策系統(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計(jì)算條件屬性ai中f(x,ai)的最大值max和最小值min；

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

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

Step2建立一個(gè)大小為max-min的對(duì)象數(shù)組X[max-min],數(shù)組中X每一元素對(duì)應(yīng)儲(chǔ)存對(duì)象的集合(儲(chǔ)存對(duì)象的下標(biāo)來儲(chǔ)存對(duì)象的集合)，初始化X[i]←?，i∈[0,max-min]；

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

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

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

//一個(gè)元素中(儲(chǔ)存對(duì)象的下標(biāo)來儲(chǔ)存對(duì)象的集合)；

Step4for(k=0;k

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

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

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

算法2求測(cè)試代價(jià)獨(dú)立的不完備決策系統(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)計(jì)所有對(duì)象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)的時(shí)間復(fù)雜度為O(k|U|)其中k=max|TB(xi)|，若求TP(x)只需要循環(huán)|P-B|次時(shí)間復(fù)雜度為O(k|P-B|·|U|)而最壞的情況下空間復(fù)雜度為O(|U|)。

2.2不一致對(duì)象集

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

算法3求測(cè)試代價(jià)獨(dú)立的不完備決策系統(tǒng)的不一致對(duì)象集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對(duì)于取任意一個(gè)對(duì)象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。

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

3　屬性約簡(jiǎn)算法

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

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

問題1測(cè)試代價(jià)獨(dú)立的不完備決策系統(tǒng)的屬性約簡(jiǎn)

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

輸出：B?C

約束條件：RB=RC

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

3.1屬性重要性及其計(jì)算算法

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

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

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

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

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

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

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

性質(zhì)3不完備決策表S=(U,C,D,V,f)中，對(duì)于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可知，對(duì)于?x∈RB∪{a}，則?x∈RB，即RB∪{a}?RB又因?yàn)閨RB|=|RB∪{a}|，可得RB∪{a}和RB一定滿足RB∪{a}=RB，根據(jù)性質(zhì)1，可有POSB∪{a}(D)=POSB(D)，即得到性質(zhì)3。

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

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

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

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

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

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

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

算法4測(cè)試代價(jià)獨(dú)立的不完備決策系統(tǒng)屬性重要性的計(jì)算算法

輸入：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對(duì)于任何一個(gè)a∈C-B由算法1、2、3可得出TB∪{a}(x)，RB∪{a}以及|RB∪a|；

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

算法4根據(jù)算法1-算法3可以依次很快速地求出結(jié)果。

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

3.2約簡(jiǎn)算法

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

算法5測(cè)試代價(jià)獨(dú)立的不完備決策系統(tǒng)的屬性約簡(jiǎn)算法

輸入：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|)]

輸出：屬性約簡(jiǎn)R

Step1令R=?；

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

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

4　實(shí)例分析

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

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

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

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

建立一個(gè)數(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=?;故輸出屬性約簡(jiǎn)R={a3,a4}。

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

5　實(shí)驗(yàn)分析

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

表4　兩種約簡(jiǎn)算法實(shí)驗(yàn)結(jié)果

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

6　結(jié)　語

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

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

[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ù)的五種代價(jià)敏感屬性約簡(jiǎn)算法比較[J].計(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)中測(cè)試代價(jià)敏感的可變精度分類粗糙集[J].智能系統(tǒng)學(xué)報(bào),2014,9(2):219-223.

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

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

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

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

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

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

TP18

A

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