王蕾，房俊民

（中國(guó)科學(xué)院國(guó)家科學(xué)圖書(shū)館成都分館，成都610021）

基于決策樹(shù)方法的信息價(jià)值求解方法

王蕾，房俊民

（中國(guó)科學(xué)院國(guó)家科學(xué)圖書(shū)館成都分館，成都610021）

傳統(tǒng)的信息價(jià)值求解方法在行動(dòng)選擇或?qū)嶒?yàn)結(jié)果情況很多的情況下，步驟繁瑣，計(jì)算量大，引起眾多麻煩。而決策樹(shù)方法是輔助行動(dòng)選擇的重要參考，并且在excel的宏工具容易求解。文章用決策樹(shù)的思路和方法求解決策問(wèn)題中的信息價(jià)值，給出了方法合理性的證明，并結(jié)合實(shí)例演示了求解方法。

信息價(jià)值;決策樹(shù);決策分析;貝葉斯分析

1 信息的期望價(jià)值求解

1.1 信息價(jià)值的概念

在決策過(guò)程中，可以通過(guò)隨機(jī)試驗(yàn)獲得觀察值x，去改進(jìn)決策人設(shè)定的自然狀態(tài)θ的先驗(yàn)概率π(θ)，從而減少期望損失。但是由于隨機(jī)試驗(yàn)或高或低，所以通常試驗(yàn)前要考慮試驗(yàn)的成本與價(jià)值。如果通過(guò)試驗(yàn)收集到的新信息所降低的損失還不足以支付試驗(yàn)費(fèi)用，則試驗(yàn)不值得進(jìn)行，反之，隨機(jī)試驗(yàn)才算獲得額外價(jià)值。這種在決策中進(jìn)行隨機(jī)實(shí)驗(yàn)帶來(lái)的額外收益（也就是期望損失的減少）稱(chēng)為信息價(jià)值[1]。

1.2 完全信息的期望價(jià)值

所謂完全信息的期望價(jià)值是指在理想情況下，通過(guò)試驗(yàn)?zāi)軌颢@得自然狀態(tài)θ的完全信息，那么決策人就可以事先知道狀體θ的確切值，進(jìn)而根據(jù)這種狀態(tài)來(lái)選擇似的損失最小的行動(dòng)。完全信息的期望價(jià)值就是這種獲得自然狀態(tài)完全信息的隨機(jī)試驗(yàn)帶來(lái)的期望損失減少量。

1.3 采樣信息的期望價(jià)值

因?yàn)橥耆畔⒌那闆r幾乎不能實(shí)現(xiàn)，那么也無(wú)法根據(jù)完全信息帶來(lái)的價(jià)值來(lái)評(píng)估隨機(jī)試驗(yàn)的效果。所以在一般決策過(guò)程中，我們只考慮采樣信息價(jià)值。采樣信息價(jià)值是通過(guò)試驗(yàn)收集新信息來(lái)指導(dǎo)決策后，期望損失比采樣之前的期望損失的減少量。

1.4 傳統(tǒng)采樣信息的期望價(jià)值求法

傳統(tǒng)的采樣信息價(jià)值求解中，需要先計(jì)算采樣之前的貝葉斯風(fēng)險(xiǎn)的期望值：。具體而言，就是在不進(jìn)行隨機(jī)試驗(yàn)的情況下，僅僅依據(jù)未來(lái)狀態(tài)的先驗(yàn)概率分布，求解每種行動(dòng)帶來(lái)的期望損失Eπ[l(θ,a)]。之后在所有行動(dòng)的后果的期望損失中取最小值，此時(shí)的ai作為行動(dòng)方案，此時(shí)的期望損失作為不進(jìn)行隨機(jī)試驗(yàn)的期望損失。

1.5 基于決策樹(shù)的采樣信息的期望價(jià)值求法

但是傳統(tǒng)方法求解，需要根據(jù)不同的貝葉斯規(guī)則分別計(jì)算期望損失，當(dāng)實(shí)驗(yàn)結(jié)果較多或者行動(dòng)選擇較多的情況下，規(guī)則十分多，計(jì)算量大，步驟繁瑣重復(fù)，帶來(lái)眾多麻煩。所以需要尋求快速準(zhǔn)確的方法來(lái)計(jì)算信息價(jià)值。

根據(jù)貝葉斯分析的第二擴(kuò)展型得到，在進(jìn)行隨機(jī)試驗(yàn)之后，最佳決策規(guī)則應(yīng)該是等價(jià)于對(duì)應(yīng)每一種x∈X，選擇一個(gè)a，使得積分r’’=∑l(θ,δ(x))π(θ|x)達(dá)到為極小，就能得葉斯葉斯規(guī)則。所對(duì)應(yīng)的a也就是最佳行動(dòng)的決策方案，得到的Eπ，所以我們?cè)谇蠼鈺r(shí)候只需要針對(duì)每一個(gè)x∈X，選擇最佳行動(dòng)ai，得到的規(guī)則就是最佳規(guī)則δi(x)——貝葉斯規(guī)則。

這種最佳規(guī)則的決策，與決策樹(shù)的思想一致，即在excel的宏treeplan中，選擇決策樹(shù)終端為每個(gè)分支行動(dòng)或狀態(tài)對(duì)應(yīng)的損失值（默認(rèn)終端為求和，此處可以修改為相應(yīng)損失函數(shù)），每個(gè)決策節(jié)點(diǎn)選擇較小的分支作為行動(dòng)。這樣自動(dòng)選擇了貝葉斯規(guī)則中對(duì)每種實(shí)驗(yàn)結(jié)果得到的最佳行動(dòng)。

這樣在每個(gè)決策分支都存在此分支下的期望損失，為了用決策樹(shù)計(jì)算信息價(jià)值，就不要將進(jìn)行試驗(yàn)預(yù)測(cè)的費(fèi)用寫(xiě)入決策樹(shù)中成本的部分，而是單純計(jì)算進(jìn)行預(yù)測(cè)和不預(yù)測(cè)的兩種情況下的各分支期望損失。這樣構(gòu)造的決策樹(shù)在是否進(jìn)行預(yù)測(cè)的分支上得出的期望值就是進(jìn)行預(yù)測(cè)和不進(jìn)行預(yù)測(cè)兩種情況下的期望損失。最后在excel表格中任意空白表格計(jì)算進(jìn)行預(yù)測(cè)和不進(jìn)行預(yù)測(cè)的期望損失之差，就是此預(yù)測(cè)信息的價(jià)值。將得到的信息價(jià)值與試驗(yàn)成本做比較，可以判斷是否進(jìn)行試驗(yàn)預(yù)測(cè)。

2 基于決策樹(shù)的信息價(jià)值求法實(shí)例

2.1 實(shí)例

舉個(gè)案例說(shuō)明：某農(nóng)民擬在兩種作物中選擇一種。若旱年θ1占60%，正常年景θ2占40%；種植耐旱作物a1以及不種植耐旱作物a2的后果矩陣如表1所示（單位：萬(wàn)元）。

表1

設(shè)該農(nóng)民的效用函數(shù)為μ(y)=1.156(1-e-0.02y(單位：萬(wàn)元），并且如果存在天氣預(yù)報(bào)，并且天氣預(yù)報(bào)的準(zhǔn)確性為0.8，請(qǐng)問(wèn)農(nóng)民應(yīng)該采取什么樣的行動(dòng)，天氣預(yù)報(bào)的信息價(jià)值是多少？

2.2 后驗(yàn)概率求解

因?yàn)樘鞖忸A(yù)報(bào)的準(zhǔn)確性為0.8，設(shè)x1為預(yù)報(bào)為旱年，x2為預(yù)報(bào)為正常年景，P（θ1）=0.6，P（θ2）=0.4。所以P（x1|θ1）= 0.8，P（x2|θ1）=0.2，P（x1|θ2）=0.2，P（x2|θ2）=0.8

得到預(yù)報(bào)旱災(zāi)概率P（x1）=P（x1|θ1）P（θ1）+P（x1|θ2）P（θ2）=0.48+0.08=0.56

預(yù)報(bào)正常年景概率P（x2）=P（x2|θ1）P（θ1）+P（x2|θ2）P（θ2）=0.12+0.32=0.44

得到各種可能的后驗(yàn)概率為：

預(yù)報(bào)旱災(zāi)，發(fā)生旱災(zāi)概率為π(θ1|x1)=P（x1|θ1）P（θ1）/P（x1）=0.48/0.56=0.857143

預(yù)報(bào)旱災(zāi)，正常年景概率為π(θ2|x1)=P（x1|θ2）P（θ2）/P（x1）=0.08/0.56=0.142857

預(yù)報(bào)正常年景，發(fā)生旱災(zāi)的概率π(θ1|x2)=P（x2|θ1）P（θ1）/ P（x2）=0.12/0.44=0.2727273

預(yù)報(bào)正常年景，正常年景的概率π(θ2|x2)=P（x2|θ2）P（θ2）/ P（x2）=0.32/0.44=0.7272727

令損失函數(shù)l（y）=-u(y)

2.3 正規(guī)貝葉斯分析的方法求解

進(jìn)行正規(guī)性貝葉斯分析，對(duì)以下四種策略進(jìn)行比較：

策略1：收聽(tīng)天氣預(yù)報(bào)，若預(yù)報(bào)旱災(zāi)則種植耐旱作物，預(yù)報(bào)正常則種植非耐旱作物。

期望損失為r(π,δ1)=πx1*(π(θ1|x1)*l(a1|θ1)+π(θ2|x1)*l (a1|θ2))+πx2(π(θ1|x2)*l(a2|θ1)+π(θ2|x2)*l(a2|θ2)=0.86*(-0.38) +0.14*(-0.81)+0.27*0+.73*(-1)=-0.57

策略2：收聽(tīng)天氣預(yù)報(bào)，若預(yù)報(bào)旱災(zāi)則種植不耐旱作物，預(yù)報(bào)正常則種植耐旱作物期望損失為r(π,δ2)=πx1*(π(θ1|x1) *l(a2|θ1)+π(θ2|x1)*l(a2|θ2))+πx2(π(θ1|x2)*l(a1|θ1)+π(θ2|x2)*l (a1|θ2)=0.56*(0.86*0+0.14*(-1))+0.44*(0.27*(-0.38)+ 0.73*(-0.81))=22-0.38

策略3：忽略天氣預(yù)報(bào)，不論預(yù)報(bào)是否旱災(zāi)，都種植耐旱作物期望損失為r(π,δ3)=Pθ1*l(a1|θ1)+Pθ2*l(a1|θ2) =-0.55

策略4：忽略天氣預(yù)報(bào)，不論預(yù)報(bào)是否旱災(zāi)，都種植不耐旱作物期望損失為r(π,δ4)=Pθ1*l(a2|θ1)+Pθ2*l(a2| θ2)=-0.40

四種策略比較得到r(π,δ1)

所以行動(dòng)方案一為最佳規(guī)則，即天氣預(yù)報(bào)預(yù)報(bào)旱災(zāi)則種植耐旱作物，預(yù)報(bào)正常則種不耐旱作物。信息價(jià)值

此方法在此例中需要計(jì)算四種策略中的期望損失，步驟重復(fù)，較為麻煩，如果行動(dòng)選擇更大，隨機(jī)試驗(yàn)結(jié)果更多，策略數(shù)量過(guò)多不易窮舉，計(jì)算量也將十分大。

2.4 決策樹(shù)方法求解信息價(jià)值

不考慮天氣預(yù)報(bào)的成本前提下，不在決策樹(shù)中進(jìn)行預(yù)測(cè)的成本，并且在決策樹(shù)分支末端輸入損失函數(shù)l(y)=-μ(y)=-1.156(1-e-0.02y)，并在末端單元格的右側(cè)輸入效用函數(shù)和收益。構(gòu)造決策樹(shù)如下，用于比較農(nóng)民是否收聽(tīng)天氣預(yù)報(bào)和采取不同策略的后果。

按照上文所述的決策樹(shù)方法，決策點(diǎn)1的兩分支的期望損失就分別為收聽(tīng)天氣預(yù)報(bào)和不收聽(tīng)天氣預(yù)報(bào)的期望損失，二者之差就是天氣預(yù)報(bào)的信息價(jià)值。

這種方法的原理很容易理解，一句話(huà)概括就是決策樹(shù)的決策選擇方式恰好符合決策問(wèn)題的貝葉斯規(guī)則。直觀上來(lái)看，決策樹(shù)在每個(gè)決策節(jié)點(diǎn)都選擇在不同未來(lái)狀態(tài)下的期望損失最小值，這個(gè)思路正與貝葉斯分析第二種擴(kuò)展型完全符合。決策樹(shù)根據(jù)試驗(yàn)的每種結(jié)果，都相應(yīng)采取是的期望損失最小的行動(dòng)，那么這種決策規(guī)則就是最佳決策規(guī)則，此時(shí)的貝葉斯風(fēng)險(xiǎn)為極小。也等價(jià)于取達(dá)到為極小，就能得到貝葉斯規(guī)則正規(guī)性中采取不同決策規(guī)則中得到的期望損失極小值而上圖決策樹(shù)中決策節(jié)點(diǎn)1的的上面分支，求出了進(jìn)行預(yù)報(bào)后的貝葉斯風(fēng)險(xiǎn)最小值；下面一支中，恰好求出了不進(jìn)行試驗(yàn)的貝葉斯損失最小值。所以二者的差值就是信息價(jià)值。

3 關(guān)于決策樹(shù)方法的思考

正如前文所述，決策樹(shù)方法之所以可以十分方便地求解信息價(jià)值，是因?yàn)闆Q策樹(shù)的判斷規(guī)則與貝葉斯分析的第二種擴(kuò)展型一致。那么我們就用應(yīng)用第二種擴(kuò)展型求解此實(shí)例，并與決策樹(shù)方法比較。

A：當(dāng)取x1（預(yù)報(bào)旱災(zāi)）

采取行動(dòng)a1：r1’’=l(θ1,a1)π(θ1|x1)+l(θ2,a1)π(θ2|x1) =(-0.38)*0.86+(-0.81)*0.14=-0.4402

采取行動(dòng)a2：r2’’=l(θ1,a2)π(θ1|x1)+l(θ2,a2)π(θ2|x1) =(0)*0.86+(-1)*0.14=-0.14

采取行動(dòng)a1

B：當(dāng)取x2（預(yù)報(bào)正常）

采取行動(dòng)a1：r3’’=1(θ1,a1)π(θ1|x2)+l(θ2,a1)π(θ2|x2)=-0.69

采取行動(dòng)a2：r4’’=l(θ1,a2)π(θ1|x2)+l(θ2,a2)π(θ2|x2)=-0.73

所以采取行動(dòng)a2

所以貝葉斯規(guī)則δπ：a1=δπ(x1),a2=δπ(x2)

這里面不同決策的期望損失恰好與下圖決策樹(shù)分支的四種情況完全一致?？梢?jiàn)決策樹(shù)方法與貝葉斯分析第二種擴(kuò)展型的思路的一致。

4 結(jié)論

傳統(tǒng)信息價(jià)值的求法公式復(fù)雜、計(jì)算費(fèi)時(shí)，而決策樹(shù)是求解效用問(wèn)題的實(shí)用方法，因此用決策樹(shù)方法求解信息價(jià)值，在excel中自動(dòng)計(jì)算，具有應(yīng)用意義。在計(jì)算中，只需確定要求解哪項(xiàng)信息的價(jià)值，并求出各種情況的后驗(yàn)概率，進(jìn)而構(gòu)造決策樹(shù)，就可十分方便地計(jì)算出決策問(wèn)題中的信息價(jià)值。所有計(jì)算都可由excel自動(dòng)完成，沒(méi)有重復(fù)步驟。在處理行動(dòng)選擇很多、實(shí)驗(yàn)結(jié)果很多的實(shí)際問(wèn)題中，仍可以很好的應(yīng)用。

[1]岳超源.決策理論與方法[M].北京：科學(xué)出版社，2006.

[2]王宏.基于屬性約簡(jiǎn)的決策樹(shù)構(gòu)建[J].統(tǒng)計(jì)與決策,2006,(7).

[3]孟飛翔，帥立國(guó)，姜昌金.決策樹(shù)在客戶(hù)價(jià)值分析中的應(yīng)用[J].計(jì)算機(jī)技術(shù)與發(fā)展，2007,(7).

[4]Quinlan J R.Induction of Decision Trees[J].Machine Learning,1986, (4).

（責(zé)任編輯/亦民）

F224

A

1002-6487(2010)22-0054-03