代價敏感屬性中模擬退火算法和信息增益算法的比較

牛軍霞

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

1 4個基本初等函數(shù)

1.1 測試代價敏感線性函數(shù)

線性函數(shù)的數(shù)學(xué)模型在現(xiàn)實生活中是最簡單的，這個數(shù)學(xué)模型不僅操作簡單，而且一些簡單的科學(xué)決策也可以用此模型。假設(shè)用CN表示把健康人誤診為病人所付出的代價，用CP表示把病人誤診為健康人所付出的代價。其中，關(guān)于CN和CP的計算，如公式(1)和(2)。

CN(B，AF)(y，n)=β(y，n)×(AFtc(B) + |C|)

(1)

CP(B，AF)(n，y)=β(n，y)×AFtc(B)

(2)

對于任意的B?C，測試代價函數(shù)tc(B) = (a (Btc(a)，其中tc(a)是針對屬性a的一個初始代價值。那么CN(B，AF)(y，n)表示把健康人誤診為病人所付出的代價值，其中β(n，y)是一個懲罰因子，它可以根據(jù)實際生活的不同情況，進(jìn)行不斷調(diào)整。

1.2 測試代價敏感指數(shù)函數(shù)

指數(shù)函數(shù)的數(shù)學(xué)模型在現(xiàn)實生活中應(yīng)用也極其廣泛，例如細(xì)胞分裂、病毒感染和計算電腦的流通速度等方面。在指數(shù)函數(shù)模型中，CN和CP如公式(3)和(4)。

CN(B，EF)(y，n)=β× ((1 + (EFtc(B))α+|C|)

(3)

CP(B，EF)(n，y)=β(n，y)×(1 + (EFtc(B))α

(4)

1.3 測試代價敏感冪函數(shù)

由于冪函數(shù)的數(shù)學(xué)模型，根據(jù)冪函數(shù)冪次的取值不同，對應(yīng)的曲線不同，這更能與實際生活相聯(lián)系。如果原測試代價為tc，平均增長率為β，則誤分類代價用冪函數(shù)如公式(5)和(6)。

CN(B，PF)(y，n) = β(y，n)×( (PFtc(B) + |C|)

(5)

CP(B，PF)(n，y) = β(n，y)×PFtc(B)

(6)

1.4 測試代價敏感對數(shù)函數(shù)

由于對數(shù)函數(shù)其性質(zhì)有多條，在實驗部分，我們可以借助其性質(zhì)，這樣算法的復(fù)雜度將大大降低，進(jìn)而可以提高算法的效率。這對處理大數(shù)據(jù)集將是一種行之有效的方法。CN和CP如公式(7)和(8)。

CN(B，LF)(y，n) = β(y，n)×((LFlog10tc(B) + |C|)

(7)

CP(B，LF)(n，y) = β(n，y)×LFlog10tc(B)

(8)

以上4個簡單的初等函數(shù)的數(shù)學(xué)模型，將其引入算法流程中，將是一種新的嘗試。通過一個實例來演示模擬退火算法的整個算法流程。

(1)第1階段：初始化原子解。

在算法的初始階段，模擬退火首先通過隨機(jī)機(jī)制產(chǎn)生一批初始原子解，為了說明實驗的整個流程，我們先假設(shè)初始有5個原子，其中用“1”表示選擇的條件屬性，反之用“0”。例如原子atom4表示選擇屬性子集為{a1，a4}。

(2)第2階段：算法演化原子。

在算法的整個運(yùn)行過程中，整個原子的演化過程的值代表屬性子集的目標(biāo)函數(shù)值。實驗中可采用atom1′、atom2′、atom3′、atom4′以及atom5′來代表atom1、atom2、atom3、atom4和atom5的鄰居解。實驗中以atom1為例來演示模擬退火演化的過程。

當(dāng)溫度達(dá)到6時，atom1={a1，a2}，溫度降到3時，atom1={a1，a2}，此時算法采用隨機(jī)機(jī)制生成一個atom1的鄰居解，設(shè)為{a1}，標(biāo)為atom1′。由于atom1的目標(biāo)函數(shù)值為fv(atom1) = 4.6。atom1′目標(biāo)函數(shù)值為fv(atom1′)=3.00。由于fv(atom1) = 4.6>fv(atom1′) = 3.00，所以atom1′比atom1效果差，這時目標(biāo)函數(shù)的差值為4.6-3=1.3。根據(jù)Metropolis準(zhǔn)則，接受概率為P = exp(-1.3/(1+3)) =0.5<α，α是[0，1]之間產(chǎn)生的任意隨機(jī)數(shù)，因此atom2′被隨機(jī)概率接受。最后atom1′代替了atom1作為下一輪迭代的起點，直到溫度達(dá)到0時這個過程才停止。

(3)第3階段：根據(jù)測試代價的限制調(diào)解每個原子的大小。

當(dāng)溫度為6時，atom4= {a1，a4}，此時atom4鄰居解為atom4′= {a1，a2，a4}。atom4′的測試代價c(atom4′) = $270> $100，這大于限制代價。因此需刪除atom4′中的冗余屬性，保證在預(yù)算之內(nèi)。

(4)第4階段：輸出最小測試代價。

當(dāng)退火過程終止時，選擇總測試代價最小的原子。從實驗中看出子集{a1，a2}的總代價是$90，其代價最小，因此原子解為屬性子集。

2 比較模擬退火算法、信息增益算法和遺傳算法的效果

本文的實驗部分借助MATLAB軟件，重點比較了模擬退火算法與信息增益啟發(fā)式算法[1]以及遺傳算法[2]的效果。在數(shù)據(jù)集Iris上，模擬退火算法與信息增益啟發(fā)式算法以及遺傳算法有相同的效果，在剩余的數(shù)據(jù)集上，模擬退火算法的實驗效果比剩余2個算法的效果好。

由于正太分布更能說明實驗的效果，因此在4個數(shù)據(jù)集上，也比較了3種算法的效果。通過實驗的數(shù)據(jù)發(fā)現(xiàn)，無論在哪種分布上，模擬退火算法的效果都要高于其它2種算法。通過實驗表明模擬退火算法在解決測試代價敏感屬性選擇問題方面具有很大的優(yōu)勢。不過在實驗的部分，只比較了3種算法在3個分布上的效果，并沒有比較3個算法在實驗中的效率問題，所以在后續(xù)的工作中，實驗會重點比較3個算法在3種分布上的效率問題。