牛軍霞

(陜西服裝工程學院，陜西 咸陽 712000)

1 最小測試代價的屬性選擇

定義1(最小測試代價的屬性選擇問題)[1-2]設(shè)測試代價獨立的決策系統(tǒng)為S，其中，相對約簡所構(gòu)成的集合為Red(S)∈S。對于?R∈Red(S)，有c(R)=min{c(R′)|R′∈ Red(S)}，稱R為最小測試代價屬性約簡(Minimal test cost reduct，MTR)，其中R(MTR(R)。

2 最小測試代價屬性選擇的對數(shù)加權(quán)算法

為了解決最小測試代價屬性選擇的問題，關(guān)于整個對數(shù)加權(quán)啟發(fā)式算法的流程，本文采用了3個階段加以說明。

算法的初始化階段稱之為第1階段，其中的偽代碼是下面算法框架中的第1行。

算法的核心階段為第2階段，其中的偽代碼是算法框架的3到9行，在算法第2階段中，我們可以發(fā)現(xiàn)在已經(jīng)設(shè)定好的啟發(fā)式函數(shù)基礎(chǔ)上算法把最好的屬性逐步添加給屬性集B，直到B為超約簡。關(guān)于整個算法的詳細流程如下所示。

算法：最小測試代價的對數(shù)加權(quán)啟發(fā)式算法

輸入代價敏感決策系統(tǒng)：其中S=(U，C，D，V，I，c)

輸出最后的屬性約簡集合：B使用的方法：對數(shù)加權(quán)法

(1)首先輸入集合B=?。

(2) CA=C； //將原始屬性集合賦值給集合CA。

(3)while ((POSB(D) ( POSC(D)) do//如果逐個添加的屬性正域集合不等于整個屬性的條件正域集合。

(4)for (α∈CA) do。

(5)Compute f(Bi，α，c(αi)，)。

(6) end for。

(9)end while //刪除屬性，主要根據(jù)信息熵的變化刪除冗余屬性。

(13)end if。

(14)end for。

(15)Return B。

算法的刪除階段為第3階段，其中包含算法流程的10到15行，在刪除階段中的屬性集B，算法在運行過程如果任意刪除某一個屬性α后，而整個算法在整體上能夠有效地剔除多余的屬性，以及不會帶來代價的增長時候，正域就保持不變。

通過以上算法的3個階段的運行，一個滿足具有最小代價的屬性子集最終就可以輸出。

關(guān)于算法在實驗的操作部分，幾個名詞性UCI數(shù)據(jù)集引入到本文的算法中：包括Tic-tac-toe，Mushroom，Voting和Zoo[2]。

算法評價指標

一個有效的評價指標才可以更有效地評價算法的效果。本文中采用文獻[2]提出的評價指標。分別是最優(yōu)因子(Finding optimal factor，F(xiàn)OF)、最大超出因子(Maximum exceeding factor，MEF)和平均超出因子(Average exceeding factor，AEF)來評價算法的效果。

3 分析算法的效果與效率

為了測試算法在整個實驗中的效果，參數(shù)的取值需要在實驗中不斷調(diào)整。最優(yōu)參數(shù)的取值往往可以通過不斷競爭的方法來選擇。當然在比較小的數(shù)據(jù)集為了提高算法的效率，人為設(shè)定的參數(shù)取值也是可行的。更進一步地，為了保證算法的可信度，在本篇論文中我們采用3種評價因子2-3]來比較算法的優(yōu)劣。在Voting數(shù)據(jù)集上當δ=1時可觀察到算法效果最佳，在Mushroom，Tic-tac-toe，Zoo數(shù)據(jù)集上，算法的效果不是很好。通過分析可知這與參數(shù)的設(shè)置有關(guān)，因為(參數(shù)的設(shè)置會影響到主函數(shù)。當δ=1，啟發(fā)式函數(shù)為

f(B，αi，c(αi)，()=fe(B，αi)× (1 + lgc(αi)× lg101)=fe(B，αi))

通過啟發(fā)式函數(shù)在整個實驗中的運行分析可知，算法的主要函數(shù)考慮了屬性的信息熵，測試代價在啟發(fā)式函數(shù)并沒有考慮，因此得到的是最小屬性，不是最小測試代價屬性。

4 比較已有的啟發(fā)式算法

在本文中，我們引入了對數(shù)加權(quán)算法求解最小測試代價的屬性選擇問題，為了表明算法在實驗中的有效性，本文中引入信息增益λ-weighted算法[4]與對數(shù)加權(quán)算法作比較。最終用數(shù)據(jù)表示兩個算法在正態(tài)分布上競爭的結(jié)果，通過實驗可知：算法在Voting數(shù)據(jù)集上，對數(shù)加權(quán)算法和增益λ-weighted算法效果相同。但是在Mushroom，Tic-tac-toe，Zoo數(shù)據(jù)集上，對數(shù)加權(quán)算法的效果都比信息增益λ-weighted算法的效果好。通過實驗分析可知，數(shù)據(jù)集越大對數(shù)加權(quán)算法的效果比信息增益λ-weighted算法更顯著。比如對數(shù)加權(quán)算法分別在Uniform和Normal上與信息增益λ-weighted算法在4個數(shù)據(jù)集上的優(yōu)劣的比較，通過實驗分析可知，對數(shù)加權(quán)算法比信息增益λ-weighted算法的提升率都高，提升率在個別數(shù)據(jù)集上可以達到57%和2%，通過以上分析可知，對數(shù)加權(quán)算法比信息增益λ-weighted算法在整個數(shù)據(jù)集上述更有效。

以上在算法的比較中，只比較了FOF的效果，并沒有涉及MEF和AEF的比較，在后續(xù)的文章中，會進一步比較信息增益λ-weighted算法和對數(shù)加權(quán)算法的MEF和AEF。