一種最小測(cè)試代價(jià)約簡(jiǎn)的改進(jìn)算法

何華平， 陳光建

(四川理工學(xué)院 計(jì)算機(jī)學(xué)院 四川 自貢 643000)

?

一種最小測(cè)試代價(jià)約簡(jiǎn)的改進(jìn)算法

何華平， 陳光建

(四川理工學(xué)院 計(jì)算機(jī)學(xué)院 四川 自貢 643000)

傳統(tǒng)屬性約簡(jiǎn)的目標(biāo)是在決策表中的所有條件屬性中，選擇一組分類代價(jià)最小的約簡(jiǎn)，算法構(gòu)建了測(cè)試代價(jià)最小的約簡(jiǎn).以往的測(cè)試代價(jià)約簡(jiǎn)算法查找成功率不夠理想，性能不穩(wěn)定，提出了一種改進(jìn)的測(cè)試代價(jià)約簡(jiǎn)算法.通過(guò)運(yùn)行2個(gè)UCI數(shù)據(jù)集實(shí)驗(yàn)，證明算法是有效的，并為提高測(cè)試代價(jià)約簡(jiǎn)算法性能提供了新途徑.

代價(jià)敏感學(xué)習(xí)； 屬性約簡(jiǎn)； 最小測(cè)試代價(jià)

0 引言

在數(shù)據(jù)挖掘中，要?jiǎng)h除冗余數(shù)據(jù)是十分困難的，屬性約簡(jiǎn)是目前最廣泛采用的方法之一[1-3].以前的一些約簡(jiǎn)算法在大多數(shù)情況下是可以找到最小約簡(jiǎn)的，但性能和穩(wěn)定性不夠好[4].文[5]解釋了測(cè)試代價(jià)敏感約簡(jiǎn)，定義并實(shí)現(xiàn)了該算法.測(cè)試代價(jià)敏感約簡(jiǎn)算法與傳統(tǒng)約簡(jiǎn)算法相比具有更強(qiáng)的通用性，該算法關(guān)心測(cè)試代價(jià)，而不再像傳統(tǒng)算法只關(guān)注分類的精度.測(cè)試代價(jià)在很多應(yīng)用場(chǎng)合是很重要的，不同的約簡(jiǎn)產(chǎn)生相同的分類精度，而測(cè)試代價(jià)各不相同.文[6]提出了算法框架用于解決該問(wèn)題.測(cè)試代價(jià)敏感約簡(jiǎn)算法的性能總是不能令人滿意.本文提出了一種算法：首先利用條件信息熵找出核，再把除核之外的屬性添加到核集中，形成(N-L)個(gè)集合(N代表決策屬性數(shù)，L代表決策屬性中除核之外的屬性數(shù))，然后對(duì)每個(gè)集合使用文[6]的框架算法求最小代價(jià)約簡(jiǎn)，最后把(N-L)個(gè)可能的最小代價(jià)約簡(jiǎn)進(jìn)行比較，找出測(cè)試代價(jià)最小的約簡(jiǎn)作為本次約簡(jiǎn)的結(jié)果.通過(guò)2個(gè)UCI數(shù)據(jù)集實(shí)驗(yàn)，把改進(jìn)的算法和文[6]的算法進(jìn)行比較，結(jié)果表明不管是在查找成功率、最大超出率和平均超出率上均有大幅的提高，穩(wěn)定性大大增強(qiáng).

1 問(wèn)題定義

1.1 測(cè)試代價(jià)獨(dú)立決策系統(tǒng)

文[7]定義了一個(gè)測(cè)試代價(jià)獨(dú)立決策系統(tǒng)(TCI-DS)S，它是一個(gè)6元組，

(1)

其中，U是一個(gè)有窮對(duì)象集，稱為域，C是條件屬性集合，D是決策屬性集合，Va是a∈C∪D的所有值的集合，Ia：U→Va，a∈C∪D的一個(gè)信息功能，c：C→R+∪ {0}是測(cè)試代價(jià)功能.

任何的φ?A?C，可以使用公式

(2)

式(2)表明所有屬性測(cè)試代價(jià)之間是相互獨(dú)立的.例如，如果醫(yī)生給病人做測(cè)體溫和量血壓兩項(xiàng)測(cè)試，假設(shè)測(cè)試代價(jià)相應(yīng)為5.00元和10.00元，那么總的測(cè)試代價(jià)為5.00+10.00=15.00元.

1.2 最小測(cè)試代價(jià)約簡(jiǎn)

本文只考慮最基本的概念,例如基于正區(qū)域的約簡(jiǎn)算法[8].為了提出定義，需要明白粗糙集理論的一些基本概念.任何的φ≠B?C∪D決定了在域U上的一個(gè)關(guān)系I(B).一個(gè)被B決定的分割記為U/I(B)，或者簡(jiǎn)寫(xiě)為U/B.把B(X)記為X的下近似，則把B?C，D的正區(qū)域定義為：POSB(D) = ∪X∈U/DB(X).

定義1任何B?C是S的一個(gè)決策關(guān)系約簡(jiǎn)，當(dāng)且僅當(dāng)：

1)POSB(D)=POSC(D)；

2) ?a∈B,POSB{a}(D)?POSC(D).

定義1的條件表明，該約簡(jiǎn)是充分的，必須維持決策系統(tǒng)的特有特性[5].S上所有可能的約簡(jiǎn)記為Red(S).約簡(jiǎn)的核是所有約簡(jiǎn)的共有屬性集合，即Core(S)=∩Red(S)[8].

2 算法描述

文[6]提出了一種通用的測(cè)試代價(jià)感知約簡(jiǎn)算法代碼框架，該算法主要分為3個(gè)主要步驟：1)通過(guò)計(jì)算各條件信息熵的辦法，找出約簡(jiǎn)的核；2)以核為基礎(chǔ)再把其余的屬性添加進(jìn)去，計(jì)算各屬性的加權(quán)信息增益，把最大的添加進(jìn)去，直到POSB(D) ≠POSC(D)；3)把冗余的屬性去掉，剩下的就是此次查找成功的最小代價(jià)約簡(jiǎn).該算發(fā)是啟發(fā)式算法，查找到的約簡(jiǎn)可能是最終最小代價(jià)約簡(jiǎn)，也可能失敗.通過(guò)分析文[8]中的實(shí)例，發(fā)現(xiàn)：第1)步驟都是成功的，第3)步驟總是能剔出候選約簡(jiǎn)中的冗余屬性，查找失敗總是發(fā)生在第2)步驟.在通過(guò)加權(quán)的信息增益添加屬性到候選約簡(jiǎn)中，算法基于這樣一種假設(shè)：前一輪添加的是信息增益大屬性，那么后面一定添加信息增益大的屬性，則一定得到的約簡(jiǎn)是最小代價(jià)約簡(jiǎn).當(dāng)所有屬性測(cè)試代價(jià)相等時(shí)，這種假設(shè)是成立的，但測(cè)試代價(jià)是隨機(jī)產(chǎn)生的，它的大小影響了屬性代價(jià)函數(shù)，使前面的假設(shè)不成立，所以可能產(chǎn)生失敗.

基于前面的分析，本文把算法框架的第2)步驟，即在核上直接開(kāi)始執(zhí)行根據(jù)信息增益的約簡(jiǎn)，直到該約簡(jiǎn)具有原決策系統(tǒng)的完備性，修改為在核上直接添加一個(gè)其余的非核屬性，得到多個(gè)集合.例如：有8個(gè)決策屬性{a,b,c,d,e,f,g,h}，其中核屬性有2個(gè)Core={a,c},則可以得到{a,b,c},{a,c,d},{a,c,e},{a,c,f},{a,c,g},{a,c,h}.然后分別基于每個(gè)集合進(jìn)行約簡(jiǎn)及去冗余屬性，再分別計(jì)算最小代價(jià).最后再選擇代價(jià)最小的作為最終的結(jié)果.

定義3Ri=Core∪ {ai},ai∈C,i=1,2,…，N-L.Ri為核屬性再增加一個(gè)非核屬性的關(guān)系，i為關(guān)系編號(hào).

定義4Reducti=Reduction(Ri),i=1,2,…,N-L.Reducti為定義3中的用文[5]算法查找到的最小代價(jià)約簡(jiǎn)關(guān)系Ri.

定義5Mj=Reductj,j=minimal(c(Reducti)),i=1,2,…,N-L；c為式(2)定義的函數(shù)，Mj就是本文改進(jìn)算法所得到的最小代價(jià)約簡(jiǎn).算法的描述如下：

Output:Areductwithsub-minimaltest-cost

Method:tcs-reduction

1:B0←?

3:if(POSC→{ai}(D)≠POSC(D))then

4:B0←B0∪{ai}//aiisacoreattribute

5:endif

6:endfor

8:Bj=B0∪{ak}//ak?B0,andak∈C

9:while(POSBj(D) ≠POSC(D))do

10:a=anelementof(C-Bj)suchthatf(B,a,c,gc)ismaximal

11:Bj=Bj∪{a}

12:endwhile

14:if(ai∈Bj&&POSBj-{ai}(D)=POSBj(D))then

15:Bj=Bj- {ai}//removeredundantattributes

16:endif

17:endfor

18:endfor

20:returnB0.

3 實(shí)驗(yàn)

3.1 數(shù)據(jù)集

表1 屬性集信息Tab.1 Information about attribute set

3.2 測(cè)試代價(jià)的設(shè)定和結(jié)果評(píng)價(jià)

本文把各屬性的測(cè)試代價(jià)的值限定在[1, 100]范圍的整數(shù)，通過(guò)一個(gè)隨機(jī)發(fā)生器產(chǎn)生并把它們送給各屬性作為測(cè)試代價(jià).

圖1 查找成功率(FOF)

圖2 最大超出率(AEF)

圖3 平均超出率(AEF)

4 結(jié)論

本文提出了一種最小測(cè)試代價(jià)約簡(jiǎn)的改進(jìn)算法.實(shí)驗(yàn)結(jié)果表明，它比原算法有更高的性能和穩(wěn)定性.從2個(gè)UCI數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果證明，該改進(jìn)算法具有更高的查找成功率，最大超出率和平均超出率均低于原算法.實(shí)驗(yàn)結(jié)果表明，實(shí)驗(yàn)數(shù)據(jù)的曲線更加平滑，算法的性能更加穩(wěn)定.實(shí)際應(yīng)用過(guò)程中可以進(jìn)行多級(jí)構(gòu)建來(lái)進(jìn)一步提高性能，但同時(shí)算法的時(shí)間復(fù)雜度會(huì)大量增加，在構(gòu)建算法過(guò)程中可以采用折中的辦法來(lái)解決.

[1] 毛華，趙小娜，史田敏，等．多部圖的最大匹配算法[J]．鄭州大學(xué)學(xué)報(bào)：理學(xué)版，2013，45(1)：27-29．

[2] 王瑜．NMF方法在遮擋人耳識(shí)別中的應(yīng)用[J]．鄭州大學(xué)學(xué)報(bào)：理學(xué)版，2013，45(1)：61-64．

[3] 王長(zhǎng)明，聶建軍．基于遺傳算法的二次曲面提取技術(shù)研究[J]．鄭州大學(xué)學(xué)報(bào)：理學(xué)版，2013，45(1)：65-68．

[4] 申雪芬，謝珺，劉海峰，等．一種改進(jìn)的基于相對(duì)正域的增量式屬性約簡(jiǎn)算法[J]．廣西師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，31(3)：45-49．

[5] Yao J T, Yao Y Y.Information granulation for web based information retrieval support systems[C]// Proceedings of SPIE.Florida，2003:138-146.

[6] Min F，Liu Q. A hierarchical model for test-cost-sensitive decision systems[J]. Information Sciences, 2009, 179(14): 2442-2452.

[7] Pawlak Z. Rough sets[J].International Journal of Computer and Information Sciences, 1982, 11(2):341-356.

[8] 許長(zhǎng)志，閔帆.帶權(quán)約簡(jiǎn)及其在漢語(yǔ)詞性標(biāo)注自動(dòng)校對(duì)中的應(yīng)用[J].控制與決策，2007, 22(7): 740-744.

An Improved Algorithm of Minimal Test-cost Attributes Reduction in Decision Systems

HE Hua-ping, CHEN Guang-jian

(DepartmentofComputerScience,SichuanUniversityofScience&Engineering,Zigong643000,China)

The traditional attribute reduction problem was aimed at constructing a minimal reduct. As later on, it aimed at constructing a minimal test-cost reduct under the model. The current test-cost reduction algorithm could not ensure a satisfactory performance. And an enhanced algorithm was designed for better performance.The experimental results in two UCI datasets showed that this algorithm was efficient and effective. This algorithm was a new way to improve the performance.

cost-sensitive learning; attribute reduction; minimal test-cost

2014-09-06

國(guó)家自然科學(xué)基金資助項(xiàng)目，編號(hào)60873077;企業(yè)信息化與物聯(lián)網(wǎng)測(cè)控技術(shù)四川省高校重點(diǎn)實(shí)驗(yàn)室項(xiàng)目，編號(hào)2013WZY02;四川理工學(xué)院培育項(xiàng)目，編號(hào)2013PY06;四川省教育廳科研項(xiàng)目，編號(hào)12ZB083.

何華平(1976-)，男，四川自貢人，副教授，主要從事代價(jià)敏感學(xué)習(xí)研究，E-mail:hehuaping_001@163.com.

TP181

A

1671-6841(2015)01-0074-04

10.3969/j.issn.1671-6841.2015.01.016