基于決策樹方法的信息價值求解方法

王蕾，房俊民

（中國科學院國家科學圖書館成都分館，成都610021）

基于決策樹方法的信息價值求解方法

王蕾，房俊民

（中國科學院國家科學圖書館成都分館，成都610021）

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

信息價值;決策樹;決策分析;貝葉斯分析

1 信息的期望價值求解

1.1 信息價值的概念

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

1.2 完全信息的期望價值

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

1.3 采樣信息的期望價值

因為完全信息的情況幾乎不能實現(xiàn)，那么也無法根據(jù)完全信息帶來的價值來評估隨機試驗的效果。所以在一般決策過程中，我們只考慮采樣信息價值。采樣信息價值是通過試驗收集新信息來指導決策后，期望損失比采樣之前的期望損失的減少量。

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

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

1.5 基于決策樹的采樣信息的期望價值求法

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

根據(jù)貝葉斯分析的第二擴展型得到，在進行隨機試驗之后，最佳決策規(guī)則應該是等價于對應每一種x∈X，選擇一個a，使得積分r’’=∑l(θ,δ(x))π(θ|x)達到為極小，就能得葉斯葉斯規(guī)則。所對應的a也就是最佳行動的決策方案，得到的Eπ，所以我們在求解時候只需要針對每一個x∈X，選擇最佳行動ai，得到的規(guī)則就是最佳規(guī)則δi(x)——貝葉斯規(guī)則。

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

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

2 基于決策樹的信息價值求法實例

2.1 實例

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

表1

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

2.2 后驗概率求解

因為天氣預報的準確性為0.8，設(shè)x1為預報為旱年，x2為預報為正常年景，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

得到預報旱災概率P（x1）=P（x1|θ1）P（θ1）+P（x1|θ2）P（θ2）=0.48+0.08=0.56

預報正常年景概率P（x2）=P（x2|θ1）P（θ1）+P（x2|θ2）P（θ2）=0.12+0.32=0.44

得到各種可能的后驗概率為：

預報旱災，發(fā)生旱災概率為π(θ1|x1)=P（x1|θ1）P（θ1）/P（x1）=0.48/0.56=0.857143

預報旱災，正常年景概率為π(θ2|x1)=P（x1|θ2）P（θ2）/P（x1）=0.08/0.56=0.142857

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

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

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

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

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

策略1：收聽天氣預報，若預報旱災則種植耐旱作物，預報正常則種植非耐旱作物。

期望損失為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：收聽天氣預報，若預報旱災則種植不耐旱作物，預報正常則種植耐旱作物期望損失為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：忽略天氣預報，不論預報是否旱災，都種植耐旱作物期望損失為r(π,δ3)=Pθ1*l(a1|θ1)+Pθ2*l(a1|θ2) =-0.55

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

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

所以行動方案一為最佳規(guī)則，即天氣預報預報旱災則種植耐旱作物，預報正常則種不耐旱作物。信息價值

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

2.4 決策樹方法求解信息價值

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

按照上文所述的決策樹方法，決策點1的兩分支的期望損失就分別為收聽天氣預報和不收聽天氣預報的期望損失，二者之差就是天氣預報的信息價值。

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

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

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

A：當取x1（預報旱災）

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

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

采取行動a1

B：當取x2（預報正常）

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

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

所以采取行動a2

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

這里面不同決策的期望損失恰好與下圖決策樹分支的四種情況完全一致。可見決策樹方法與貝葉斯分析第二種擴展型的思路的一致。

4 結(jié)論

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

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

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

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

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

（責任編輯/亦民）

F224

A

1002-6487(2010)22-0054-03