牛軍霞
(陜西服裝工程學(xué)院,咸陽(yáng) 712000)
線性函數(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)整。
指數(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)
由于冪函數(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)
由于對(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é)模型,將其引入算法流程中,將是一種新的嘗試。通過一個(gè)實(shí)例來演示模擬退火算法的整個(gè)算法流程。
(1)第1階段:初始化原子解。
在算法的初始階段,模擬退火首先通過隨機(jī)機(jī)制產(chǎn)生一批初始原子解,為了說明實(shí)驗(yàn)的整個(gè)流程,我們先假設(shè)初始有5個(gè)原子,其中用“1”表示選擇的條件屬性,反之用“0”。例如原子atom4表示選擇屬性子集為{a1,a4}。
(2)第2階段:算法演化原子。
在算法的整個(gè)運(yùn)行過程中,整個(gè)原子的演化過程的值代表屬性子集的目標(biāo)函數(shù)值。實(shí)驗(yàn)中可采用atom1′、atom2′、atom3′、atom4′以及atom5′來代表atom1、atom2、atom3、atom4和atom5的鄰居解。實(shí)驗(yàn)中以atom1為例來演示模擬退火演化的過程。
當(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è)過程才停止。
(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)退火過程終止時(shí),選擇總測(cè)試代價(jià)最小的原子。從實(shí)驗(yàn)中看出子集{a1,a2}的總代價(jià)是$90,其代價(jià)最小,因此原子解為屬性子集。
本文的實(shí)驗(yàn)部分借助MATLAB軟件,重點(diǎn)比較了模擬退火算法與信息增益啟發(fā)式算法[1]以及遺傳算法[2]的效果。在數(shù)據(jù)集Iris上,模擬退火算法與信息增益啟發(fā)式算法以及遺傳算法有相同的效果,在剩余的數(shù)據(jù)集上,模擬退火算法的實(shí)驗(yàn)效果比剩余2個(gè)算法的效果好。
由于正太分布更能說明實(shí)驗(yàn)的效果,因此在4個(gè)數(shù)據(jù)集上,也比較了3種算法的效果。通過實(shí)驗(yàn)的數(shù)據(jù)發(fā)現(xiàn),無論在哪種分布上,模擬退火算法的效果都要高于其它2種算法。通過實(shí)驗(yàn)表明模擬退火算法在解決測(cè)試代價(jià)敏感屬性選擇問題方面具有很大的優(yōu)勢(shì)。不過在實(shí)驗(yàn)的部分,只比較了3種算法在3個(gè)分布上的效果,并沒有比較3個(gè)算法在實(shí)驗(yàn)中的效率問題,所以在后續(xù)的工作中,實(shí)驗(yàn)會(huì)重點(diǎn)比較3個(gè)算法在3種分布上的效率問題。