代價敏感屬性中對數加權算法和信息增益算法的比較

牛軍霞

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

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

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

2 最小測試代價屬性選擇的對數加權算法

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

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

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

算法：最小測試代價的對數加權啟發式算法

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

輸出最后的屬性約簡集合：B使用的方法：對數加權法

(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 //刪除屬性，主要根據信息熵的變化刪除冗余屬性。

(13)end if。

(14)end for。

(15)Return B。

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

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

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

算法評價指標

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

3 分析算法的效果與效率

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

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

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

4 比較已有的啟發式算法

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

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