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

牛軍霞

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

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

1.1 測(cè)試代價(jià)敏感線性函數(shù)

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

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

(1)

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

(2)

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

1.2 測(cè)試代價(jià)敏感指數(shù)函數(shù)

指數(shù)函數(shù)的數(shù)學(xué)模型在現(xiàn)實(shí)生活中應(yīng)用也極其廣泛，例如細(xì)胞分裂、病毒感染和計(jì)算電腦的流通速度等方面。在指數(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 測(cè)試代價(jià)敏感冪函數(shù)

由于冪函數(shù)的數(shù)學(xué)模型，根據(jù)冪函數(shù)冪次的取值不同，對(duì)應(yīng)的曲線不同，這更能與實(shí)際生活相聯(lián)系。如果原測(cè)試代價(jià)為tc，平均增長(zhǎng)率為β，則誤分類代價(jià)用冪函數(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 測(cè)試代價(jià)敏感對(duì)數(shù)函數(shù)

由于對(duì)數(shù)函數(shù)其性質(zhì)有多條，在實(shí)驗(yàn)部分，我們可以借助其性質(zhì)，這樣算法的復(fù)雜度將大大降低，進(jìn)而可以提高算法的效率。這對(duì)處理大數(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個(gè)簡(jiǎn)單的初等函數(shù)的數(shù)學(xué)模型，將其引入算法流程中，將是一種新的嘗試。通過(guò)一個(gè)實(shí)例來(lái)演示模擬退火算法的整個(gè)算法流程。

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

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

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

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

當(dāng)溫度達(dá)到6時(shí)，atom1={a1，a2}，溫度降到3時(shí)，atom1={a1，a2}，此時(shí)算法采用隨機(jī)機(jī)制生成一個(gè)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效果差，這時(shí)目標(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作為下一輪迭代的起點(diǎn)，直到溫度達(dá)到0時(shí)這個(gè)過(guò)程才停止。

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

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

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

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

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

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

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