一種基于條件信息熵的多目標(biāo)代價(jià)敏感屬性約簡(jiǎn)算法的研究

徐冰心，陳慧萍

(河海大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 常州 213022)

近年來，代價(jià)敏感屬性約簡(jiǎn)是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)領(lǐng)域的重要課題.現(xiàn)實(shí)生活中大多數(shù)數(shù)據(jù)的獲取需要付出多種代價(jià)，例如，在醫(yī)療體檢中，對(duì)于被檢測(cè)者而言，他們需要花費(fèi)金錢、時(shí)間以及其他的資源來獲取自己的體檢結(jié)果.已有算法[1-5]基本都是針對(duì)單目標(biāo)進(jìn)行優(yōu)化.因此，有必要在多目標(biāo)代價(jià)敏感學(xué)習(xí)的基礎(chǔ)上對(duì)數(shù)據(jù)進(jìn)行屬性約簡(jiǎn).屬性約簡(jiǎn)的目的是在保證信息系統(tǒng)分類能力不變的前提下，刪除冗余的屬性.

在多目標(biāo)代價(jià)敏感屬性約簡(jiǎn)問題中，每個(gè)子目標(biāo)函數(shù)均可體現(xiàn)其中的某一種代價(jià).這些子目標(biāo)函數(shù)之間往往是相互矛盾的，即某個(gè)子目標(biāo)函數(shù)所對(duì)應(yīng)的代價(jià)減少可能導(dǎo)致其他某個(gè)或多個(gè)子目標(biāo)函數(shù)對(duì)應(yīng)的代價(jià)增加，不可能使所有子目標(biāo)函數(shù)所對(duì)應(yīng)的代價(jià)都達(dá)到最小，只能對(duì)多個(gè)子目標(biāo)函數(shù)進(jìn)行平衡折中，尋找使每個(gè)子目標(biāo)函數(shù)所對(duì)應(yīng)的代價(jià)盡可能小的最優(yōu)解集，即帕雷托最優(yōu)解集[6].

代價(jià)敏感學(xué)習(xí)中多目標(biāo)優(yōu)化問題的研究還處于起步階段，基于單目標(biāo)代價(jià)敏感屬性約簡(jiǎn)，本文提出了多目標(biāo)代價(jià)敏感屬性約簡(jiǎn)問題，并設(shè)計(jì)了一種簡(jiǎn)單高效的算法.該算法能較好地解決多目標(biāo)代價(jià)敏感屬性約簡(jiǎn)問題.

1 基本概念

1.1 多代價(jià)決策表(MC-DS)

定義1 多代價(jià)決策表是一個(gè)六元組：S=(U,C,D,V,I,C)，其中，U為對(duì)象的集合也稱論域，C為條件屬性集合，D為決策屬性集合，Va為屬性a的值域，Ia：U→Va為信息函數(shù)，C={c1,c2,…,ck}是k種代價(jià)函數(shù)的集合，ci：C→R+∪0(i∈[1,k])表示第i種代價(jià)函數(shù).簡(jiǎn)單起見，本文只考慮2種類型的代價(jià)，即測(cè)試代價(jià)和延遲代價(jià).它們分別指為獲得對(duì)象的屬性值，進(jìn)行測(cè)試所付出的金錢和時(shí)間代價(jià).

表1 典型的代價(jià)矢量

一項(xiàng)檢測(cè)的等待時(shí)間通常可以和其它項(xiàng)檢測(cè)的測(cè)試時(shí)間或等待時(shí)間重疊.例如，在等待Leukocyte結(jié)果的過程中，可以進(jìn)行任何其它項(xiàng)測(cè)試.屬性子集的延遲代價(jià)可以按照(1)式計(jì)算，其中，T_C表示一個(gè)屬性子集的最小延遲代價(jià)，tj代表第j個(gè)測(cè)試的測(cè)試時(shí)間，wi代表第i個(gè)測(cè)試的等待時(shí)間，n是檢測(cè)的項(xiàng)目數(shù).

(1)

當(dāng)各個(gè)測(cè)試以等待時(shí)間降序排列時(shí)，可獲得最小延遲代價(jià)[7].可以結(jié)合下例予以解釋.

簡(jiǎn)單起見，從表1中選擇4個(gè)測(cè)試項(xiàng)目Temperature，Lymphocyte，Leukocyte和Eosinophil，并分別用a1，a2，a3，a4表示.圖1中，j代表測(cè)試順序，圖1(a)中的測(cè)試按等待時(shí)間降序排列；圖1(b)中的測(cè)試是隨機(jī)安排的.依據(jù)(2)式，圖1(a)中測(cè)試的延遲代價(jià)T_C1為：

T_C01=t1+w1=t(a3)+w(a3)=20+120=140;

T_C02=t1+t2+w2=t(a3)+t(a4)+w(a4)=20+20+90=130;

T_C03=t1+t2+t3+w3=t(a3)+t(a4)+t(a2)+w(a2)=20+20+30+60=130;

T_C04=t1+t2+t3+t4+w4=t(a3)+t(a4)+t(a2)+t(a1)+w(a1)=20+20+30+5+3=78;

T_C1=max{T_C01,T_C02,T_C03,T_C04}=140.

其中，T_C01、T_C02、T_C03和T_C04分別代表第i(i∈[1,4])個(gè)測(cè)試的延遲代價(jià).

同理，圖1(b)中測(cè)試的延遲代價(jià)T_C2為165，T_C1明顯小于T_C2.

通常情況下數(shù)據(jù)信息的獲取都需要花費(fèi)不同類型的代價(jià)，為簡(jiǎn)單起見，本文不考慮免費(fèi)測(cè)試.

1.2 關(guān)聯(lián)約簡(jiǎn)

屬性約簡(jiǎn)是粗糙集研究中的關(guān)鍵問題之一.已有研究從不同的角度處理約簡(jiǎn)問題[8-11].本文采用基于條件信息熵的定義.

定義2S=(U,C,D,V,I)是一個(gè)決策表，當(dāng)B?C時(shí)，H(D|B)表示B對(duì)于D的條件熵，對(duì)于任意的RC，若同時(shí)滿足以下2個(gè)條件則為一個(gè)約簡(jiǎn)：

1)H(D|R)=H(D|C)；

2)?a∈R，H(D|R-{a})>H(D|C).

1.3 多目標(biāo)代價(jià)敏感約簡(jiǎn)問題

定義3 設(shè)S是一個(gè)多代價(jià)決策表(MC-DS)，Red={R1,R2,…,Rn}為S所有約簡(jiǎn)的集合，R表示MC-DS的帕雷托最優(yōu)解集.若滿足以下2個(gè)條件，則稱任意的Ri優(yōu)于Rj，記為Ri>Rj(i,j∈[1,n])：

1)?p∈[1,k]，cp(Ri)≤cp(Rj)；

2)?q∈[1,k]，cq(Ri)

然而，有些約簡(jiǎn)是不可比的，即不存在Ri>Rj或者Ri

由此可見，Red(S)中的約簡(jiǎn)有些是可以比較的，有些是不可比較的，S所有約簡(jiǎn)之間就構(gòu)成了偏序關(guān)系.

為了更好地說明S所有約簡(jiǎn)間的偏序關(guān)系，圖2給出考慮3種代價(jià)的MC-DS中約簡(jiǎn)集Red={R1,R2,…,R9}元素間的偏序關(guān)系.為了簡(jiǎn)潔起見，分別用c1(R1)、c2(R1)和c3(R1)來表示這3種代價(jià).從圖中可以看出，第1層的4個(gè)約簡(jiǎn)對(duì)應(yīng)的3種代價(jià)之間有如下關(guān)系：①c1(R1)c3(R4)，因此R1～R4；②c1(R1)c2(R7)，因此R1～R7；③c2(R1)>c2(R8)并且c3(R1)R1，R2>R4且R3>R2；R6>R7，R6>R8且R5>R2，R5>R6.因此，R3和R5是最優(yōu)約簡(jiǎn).從圖中可以看出，R9與其他8個(gè)約簡(jiǎn)都是不可比較的關(guān)系，因此，帕雷托最優(yōu)約簡(jiǎn)集R={R3,R5,R9}.

2 多目標(biāo)屬性約簡(jiǎn)算法

2.1 算法基本思想及具體步驟

本文設(shè)計(jì)了一種簡(jiǎn)單高效的算法來解決多目標(biāo)代價(jià)敏感屬性約簡(jiǎn)問題.算法基本思想為：首先，利用條件信息熵計(jì)算決策表的所有約簡(jiǎn)，并將其存儲(chǔ)起來以方便讀取，由此可以節(jié)省大量的程序運(yùn)行時(shí)間.然后，分別計(jì)算這些約簡(jiǎn)所對(duì)應(yīng)的測(cè)試代價(jià)和延遲代價(jià)，根據(jù)這2種代價(jià)來比較對(duì)應(yīng)的約簡(jiǎn)，并且移除那些代價(jià)高的約簡(jiǎn)，剩下的約簡(jiǎn)就是帕雷托最優(yōu)解.

算法具體步驟：

輸入：多代價(jià)決策表S={U,C,D,V,I,c,t,w}.

輸出：帕雷托最優(yōu)解集R.

步驟1 計(jì)算并存儲(chǔ)多代價(jià)決策表的所有約簡(jiǎn)；

步驟2 根據(jù)這些約簡(jiǎn)所對(duì)應(yīng)的測(cè)試代價(jià)和延遲代價(jià)，比較各個(gè)約簡(jiǎn)，并移除那些沒有任何代價(jià)優(yōu)勢(shì)的約簡(jiǎn)；

步驟2.1 初始化2個(gè)數(shù)組，分別用來存儲(chǔ)所有約簡(jiǎn)和被移除的約簡(jiǎn)；

步驟2.2 分別計(jì)算這些約簡(jiǎn)所對(duì)應(yīng)的測(cè)試代價(jià)和延遲代價(jià)；

步驟2.3 依據(jù)各自對(duì)應(yīng)的測(cè)試代價(jià)和延遲代價(jià)，將一個(gè)約簡(jiǎn)與其他約簡(jiǎn)進(jìn)行比較；

步驟2.4 存儲(chǔ)最優(yōu)約簡(jiǎn)單，并計(jì)算其個(gè)數(shù)；

步驟2.5 返回R.

2.2 算例

以UCI數(shù)據(jù)集Tic-tac-toe為例，該數(shù)據(jù)集有9個(gè)約簡(jiǎn)，分別用R1，R2，R3，R4，R5，R6，R7，R8和R9表示.算法的執(zhí)行過程如表2所示.

表2 基于條件信息熵的多目標(biāo)約簡(jiǎn)過程實(shí)例

Exclusion：R1，R2，R4，R6，R7，R8

ReturnR={R3，R5，R9}

測(cè)試代價(jià)和延遲代價(jià)分別用m(Ri)和t(Ri)(i∈[1,9])來表示.如果滿足m(Ri)≥m(Rj)，t(Ri)>t(Rj)或者m(Ri)>m(Rj)，t(Ri)≥t(Rj)(i,j∈[1,9]且i≠j)，那么，用“-1”表示RiRj，用“0”表示Ri～Rj.在該算法中，首先將R1對(duì)應(yīng)的測(cè)試代價(jià)和延遲代價(jià)與其他的約簡(jiǎn)對(duì)應(yīng)的代價(jià)進(jìn)行比較.如果返回值是“-1”，移除R1；如果返回值是“1”，移除被比較的約簡(jiǎn)；如果返回值是“0”，同時(shí)保留這2個(gè)約簡(jiǎn).同理，依次將R2，R3，…，R8與那些下標(biāo)比自身大的約簡(jiǎn)進(jìn)行計(jì)較.值得注意的是，在該算法中，若其中一個(gè)約簡(jiǎn)在某次比較中被移除了，就沒有必要將它與其他約簡(jiǎn)進(jìn)行比較了.表2中，被移除的約簡(jiǎn)是R1，R2，R4，R6，R7和R8，所以，剩下的約簡(jiǎn)為帕雷托最優(yōu)解，即R={R3，R5，R9}.

3 實(shí)驗(yàn)結(jié)果

為了測(cè)試本算法的有效性，從UCI數(shù)據(jù)庫(kù)中分別選取實(shí)例和屬性個(gè)數(shù)從低到高的4個(gè)數(shù)據(jù)集作為算例進(jìn)行測(cè)試，見表3.由于這些數(shù)據(jù)集本身不含代價(jià)信息，分別利用均勻分布、正態(tài)分布和帕雷托分布分別為其產(chǎn)生測(cè)試代價(jià)、測(cè)試時(shí)間代價(jià)和等待時(shí)間代價(jià)，這3種代價(jià)均為100至 1 000 的隨機(jī)整數(shù).利用開源軟件Coser[12]實(shí)現(xiàn)本算法，算法獨(dú)立運(yùn)行100次，并統(tǒng)計(jì)100次實(shí)驗(yàn)所得的帕雷托最優(yōu)解的平均數(shù)目，以評(píng)價(jià)算法的收斂性和穩(wěn)定性.

表3 UCI數(shù)據(jù)集

由于空間有限，在此只給出一部分的實(shí)驗(yàn)結(jié)果.圖3中，測(cè)試代價(jià)、測(cè)試時(shí)間和等待時(shí)間分別服從帕雷托分布、正態(tài)分布和均勻分布.Mushroom數(shù)據(jù)集有292個(gè)約簡(jiǎn)，100次實(shí)驗(yàn)獲得的平均帕累托最優(yōu)解的數(shù)目是2.14.因此，Mushroom數(shù)據(jù)集的絕對(duì)基數(shù)是2.14，相對(duì)基數(shù)是2.14÷292≈0.007 33.同理，Voting數(shù)據(jù)集的絕對(duì)基數(shù)是1.09，相對(duì)基數(shù)是1.09÷3≈0.363；Zoo數(shù)據(jù)集的絕對(duì)基數(shù)是1.83，相對(duì)基數(shù)是1.83÷33≈0.055 4；Tic-tac-toe數(shù)據(jù)集的絕對(duì)基數(shù)是2.09，相對(duì)基數(shù)是2.09÷9≈0.232.由此可見，帕雷托最優(yōu)解集的絕對(duì)基數(shù)和相對(duì)基數(shù)都很小.

由以上分析可得，該算法可有效地解決MOR問題，且數(shù)據(jù)集越大，算法的優(yōu)勢(shì)越明顯.假設(shè)Mushroom數(shù)據(jù)集的所有約簡(jiǎn)代表實(shí)際應(yīng)用系統(tǒng)中的292種不同的方案，通過多目標(biāo)約簡(jiǎn)后僅剩下幾種最優(yōu)的方案供選擇，由此，我們的算法可以更好地輔助用戶做出方案的選擇.

圖4中，“U”、“N”和“B”分別代表均勻分布、正態(tài)分布和有界的帕雷托分布.實(shí)驗(yàn)中，考慮Mushroom數(shù)據(jù)集上的測(cè)試代價(jià)和延遲代價(jià)(測(cè)試時(shí)間和等待時(shí)間服從相同的分布).比如，“NB”中的第1個(gè)字母“N”代表測(cè)試代價(jià)的分布是正態(tài)分布，第2個(gè)字母“B”代表延遲代價(jià)中的測(cè)試時(shí)間和等待時(shí)間的分布均為帕雷托分布.每組實(shí)驗(yàn)過程中，保持分布不變，但代價(jià)為100到 1 000 的隨機(jī)整數(shù)，算法獨(dú)立運(yùn)行100次，得到帕雷托最優(yōu)解統(tǒng)計(jì)平均數(shù)目.

由圖4可得以下幾點(diǎn)結(jié)論：①帕雷托最優(yōu)解的數(shù)目隨著測(cè)試代價(jià)和延遲代價(jià)分布的變化而變化；②當(dāng)測(cè)試代價(jià)或者延遲代價(jià)的分布為均勻分布時(shí)，帕雷托最優(yōu)解的數(shù)目會(huì)隨著代價(jià)的變化而變化；③當(dāng)測(cè)試代價(jià)和延遲代價(jià)的分布為正態(tài)分布或者有界的帕雷托分布時(shí)，帕雷托最優(yōu)解的數(shù)目不會(huì)隨著代價(jià)的變化而變化.這是因?yàn)榫鶆蚍植紩?huì)以相同的概率產(chǎn)生隨機(jī)的整數(shù)，而正態(tài)分布會(huì)產(chǎn)生大量的均值附近的數(shù)值，同時(shí)，有界的帕雷托分布會(huì)產(chǎn)生大量小的數(shù)值和少量大的數(shù)值.

4 結(jié)語

本文基于粗糙集理論中屬性約簡(jiǎn)的概念，定義了多目標(biāo)代價(jià)敏感約簡(jiǎn)問題，并設(shè)計(jì)了一種簡(jiǎn)單高效的算法.對(duì)UCI數(shù)據(jù)庫(kù)中選取的有代表性數(shù)據(jù)集的測(cè)試結(jié)果表明，該算法能獲得令人滿意的帕雷托最優(yōu)解集，以輔助用戶優(yōu)化選擇方案.在以后的研究工作中，可以進(jìn)一步研究更加高效的啟發(fā)式算法來解決多目標(biāo)代價(jià)敏感約簡(jiǎn)問題.

參考文獻(xiàn):

[1] PAN G Y, MIN F, ZHU W. A genetic algorithm to the minimal test cost reduct problem[C]// IEEE International Conference on GrC. IEEE，2011: 539-544.

[2] XU Z L, MIN F, LIU J B, ZHU W. Ant colony optimization to minimal test cost reduction[C]// IEEE International Conference on GrC.IEEE，2012: 585-590.

[3] ZHAO H, MIN F, ZHU W. Test-cost-sensitive attribute reduction based on neighborhood Rough set[C]// 2011 IEEE International Conference on GrC. IEEE，2011: 802-806.

[4] MIN F, ZHU W. Minimal cost attribute reduction through backtracking[C]// Proceedings of International Conference on Database Theory and Application, 258 of FGIT-DTA/BSBT, CCIS. 2011: 100-107.

[5] MIN F, ZHU W. A competition strategy to cost-sensitive decision trees[C]// RSKT. 2012: 359-368.

[6] DEB K, PRATAP A, AGARWAL S. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. Evolutionary Computation. IEEE Transactions on, 2002, 6 (2): 182-197.

[7] LI L, CHEN H P, MIN F, et al. Attribute reduction in time-cost-sensitive decision systems through backtracking[J]. Journal of Information and Computational Science,accepted, 2013.

[8] HU Q H, YU D R, LIU J F, et al. Neighborhood rough set based heterogeneous feature subset selection[J]. Information Sciences, 2008, 178 (18): 3577-3594.

[9] PAWLAK Z. Rough sets[J]. International Journal of Computer & Information Sciences, 1982, 11(5): 341-356.

[10] QIAN Y H, LIANG J Y, PEDRYCZ W, et al. Positive approximation: An accelerator for attribute reduction in rough set theory[J]. Artificial Intelligence, 2010, 174 (9/10): 597-618.

[11] 王國(guó)胤, 于洪, 楊大春. 基于條件信息熵的決策表約簡(jiǎn)[J]. 計(jì)算機(jī)學(xué)報(bào), 2002, 25(7): 759-766.

[12] MIN F, ZHU W, ZHAO H, et al. Coser: Cost-senstive rough sets[EB/OL].(2012-01-01). http://grc.fjzs.edu.cn/～fmin/coser/.