黃俊南

(泉州經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院 信息系，福建 泉州 362000)

0 前言

決策樹(shù)是機(jī)器學(xué)習(xí)最基礎(chǔ)且廣泛應(yīng)用的算法模型，大多數(shù)歸納學(xué)習(xí)系統(tǒng)得到的結(jié)果是一棵決策樹(shù)[1].決策樹(shù)算法從早期的單變量算法轉(zhuǎn)變?yōu)槿缃竦亩嘧兞克惴?，典型算法包含Quinlan的單變量算法ID3[2]和C4.5[3]及粗糙集多變量算法[1].2015年筆者發(fā)表論文“基于決策類(lèi)劃分的新型多變量決策樹(shù)算法”[4]，這是一種基于不可分辨關(guān)系、復(fù)合運(yùn)算、集合運(yùn)算和邏輯運(yùn)算推導(dǎo)出的新型多變量算法.研究采用新型多變量決策樹(shù)算法“算”出天氣與是否進(jìn)行戶(hù)外運(yùn)動(dòng)的關(guān)系，驗(yàn)證其準(zhǔn)確性和高效性.

1 選取戶(hù)外運(yùn)動(dòng)典型數(shù)據(jù)

天氣預(yù)報(bào)是計(jì)算機(jī)“算”出來(lái)的.天氣預(yù)報(bào)員先用計(jì)算機(jī)解出描述天氣演變的方程組，“算”出來(lái)天氣；再通過(guò)分析天氣圖、氣象衛(wèi)星資料等，結(jié)合積累的經(jīng)驗(yàn)，做出未來(lái)3天至5天的具體天氣預(yù)報(bào)[5].氣候?qū)θ祟?lèi)生產(chǎn)活動(dòng)方方面面均起著重大的影響，主要因素包含：氣溫、風(fēng)、日照、降水和氣壓.對(duì)于體育運(yùn)動(dòng)而言主要影響因素有：溫度、風(fēng)向風(fēng)速、濕度、降水和雷電.但并非各種體育項(xiàng)目均會(huì)受上述因素影響，如雷電對(duì)足球、棒球、網(wǎng)球、高爾夫、田徑等空曠場(chǎng)地運(yùn)動(dòng)有較大雷擊風(fēng)險(xiǎn)，而降水的大小也影響類(lèi)似網(wǎng)球、馬拉松、小輪車(chē)等運(yùn)動(dòng).

在研究中選用東南沿海的5個(gè)氣候因素(常見(jiàn)數(shù)據(jù)值)，分別是：溫度(冷、熱、適中)、風(fēng)(大、小、無(wú))、濕度(正常、高)、降水(大、小、無(wú))和雷電(有、無(wú)).訓(xùn)練集數(shù)據(jù)選用常見(jiàn)天氣數(shù)據(jù)，具體情況如表1所示.

表1 戶(hù)外運(yùn)動(dòng)信息系統(tǒng)表 續(xù)表

2 決策類(lèi)劃分的多變量決策樹(shù)實(shí)例解析

決策表可以形式化定義[6]為：S=〈U，C∪D，V，F(xiàn)〉，其中U={u1，u2，…，un}是所感興趣對(duì)象的有限集合，C∪D是屬性的有限集，C為條件屬性集，D為決策屬性集，并且C∩D= ?，V為屬性集C∪D的值域，f:U×(C∪D)→V為一個(gè)信息函數(shù)，表示任一對(duì)象的屬性在V上的取值，即f(x，r)∈Vr，它指定了U中每個(gè)對(duì)象x的屬性值.決策表S=〈U，C∪D〉中的依賴(lài)關(guān)系C→KD決定了一套if…then…形式的規(guī)則集.從邏輯觀點(diǎn)出發(fā)，決策規(guī)則將形如a=v(a為屬性名，v為屬性值)的基本公式是利用連接詞語(yǔ)“與”“或”和“蘊(yùn)含”連接起來(lái)所建立的蘊(yùn)含式.蘊(yùn)含式前件表示條件，后件表示決策[7].

2.1 根據(jù)決策樹(shù)性值劃分決策類(lèi)

對(duì)戶(hù)外運(yùn)動(dòng)信息系統(tǒng)表(表1)U的決策值進(jìn)行不可分辨關(guān)系劃分.決策屬性值域VD={Y，N}，論域U被劃分為Y,N兩個(gè)等價(jià)決策類(lèi)，分別用UY,UN表示.劃分后的結(jié)果為：UY={1，3，6，7，8，10，12，13，14，15，16，18，19，20}，UN={2，4，5，9，11，17} .

2.2 二義性[8]條件屬性判斷

當(dāng)存在相同的條件屬性值能推導(dǎo)出不同的決策屬性值時(shí)，表明論域存在數(shù)據(jù)二義性.通過(guò)二義性條件屬性排除法對(duì)上述論域樣本進(jìn)行運(yùn)算，CY∩CN=?，表明數(shù)據(jù)并未存在二義性.在選取典型數(shù)據(jù)時(shí)已充分考慮二義性問(wèn)題，故在此未出現(xiàn)此類(lèi)情況才為正常.

2.3 判斷獨(dú)立決策條件屬性

用CY和CN表示各條件屬性對(duì)應(yīng)決策值Y和N的集合，CN各個(gè)條件屬性的值域?yàn)椋篤a1N={熱，冷，適中}，Va2N={小，無(wú)，大}，Va3N={正常，高}，Va4N={大，無(wú)，小}，Va5N={無(wú)，有}.

CP各個(gè)條件屬性的值域?yàn)椋篤a1Y={熱，冷，適中}，Va2Y={小，無(wú)}，Va3Y={正常，高}，Va4Y={無(wú)，小}，Va5Y={無(wú)}.

對(duì)VY和VN各值域集進(jìn)行比較，且將值域數(shù)大的集合減去小的集合得：Va1N-Va1Y=φ、Va2N-Va2Y={大}，Va3N-Va3Y=φ，Va4N-Va4Y={大}，Va5N-Va5Y={有}.當(dāng)值為空時(shí)，說(shuō)明該條件屬性不存在獨(dú)立決策條件屬性值，所以a1和a3沒(méi)有獨(dú)立條件屬性值.對(duì)其他三個(gè)條件屬性分別從UN中提取樣本得：σa2=大(UN)={5，9}，σa4=大(UN)={2，9}，σa5=有(UN)={4，9，11，17}.對(duì)所取得樣本集進(jìn)行包含性分析：σa2=大(UN)?σa4=大(UN)?σa5=有(UN)，說(shuō)明a2，a4，a5均有存在獨(dú)立決策條件屬性值，故推導(dǎo)結(jié)果為：a2=大D=Nora4=大D=Nora5=有D=N.

推導(dǎo)完畢后，將上述樣本從論域中刪除，UY保持不變，UN= ?.

2.4 重設(shè)論域數(shù)據(jù)值

為便于后續(xù)運(yùn)算，對(duì)論域中的數(shù)據(jù)值重新進(jìn)行定義，設(shè)置內(nèi)容如下：溫度(a1)中的冷為0、熱為1、適中為2；風(fēng)(a2)中的大為0、小為1、無(wú)為2；濕度(a3)中的正常為0、高為1；降水(a4)中的大為0、小為1、無(wú)為2；雷電(a5)中的有為0、無(wú)為1.重定義后的條件屬性集CY的情況如表2所示(UN= ?表明CN無(wú)數(shù)據(jù)).

表2 屬性集CY數(shù)據(jù)表

2.5 獲取多變量邏輯表達(dá)式步驟

1)執(zhí)行對(duì)象分量相交復(fù)合運(yùn)算，運(yùn)算法則為：將樣本某行中的每個(gè)條件屬性值一一與其他行相同條件屬性值進(jìn)行交運(yùn)算，并生產(chǎn)新的條件屬性集，對(duì)樣本其他行分別執(zhí)行上述算法.如樣本有n行數(shù)據(jù)則生成n-1個(gè)新數(shù)據(jù)表，每個(gè)新數(shù)據(jù)表有n-1個(gè)新樣本.

2)刪除無(wú)效樣本，運(yùn)算法則為：由于是多變量邏輯表達(dá)式運(yùn)算，當(dāng)某行樣本的有效條件屬性值小于2個(gè)有效數(shù)據(jù)時(shí)，該樣本無(wú)效刪除之.

3)判斷最優(yōu)對(duì)象近似度，運(yùn)算法則為：統(tǒng)計(jì)各樣本有效數(shù)據(jù)個(gè)數(shù)，個(gè)數(shù)最多為最優(yōu)近似度最高.

對(duì)CY執(zhí)行1)～3)步驟后生成13個(gè)數(shù)據(jù)表，每個(gè)數(shù)據(jù)表包含13條樣本.最優(yōu)近似度分析結(jié)果如表3所示：

表3 第一次復(fù)合運(yùn)算最優(yōu)近似度數(shù)據(jù)表

4)保留最優(yōu)近似度最高的數(shù)據(jù)表.分析表3樣本12,16,20生成的新數(shù)據(jù)表最優(yōu)近似度最大且均為39，保留之(未保留樣本數(shù)據(jù)量過(guò)大，略之).保留下的數(shù)據(jù)表如表4所示：

表4 第一次復(fù)合運(yùn)算保留下的數(shù)據(jù)表 續(xù)表

注：樣本12和樣本20均有一行加刪除線，表明該樣本數(shù)據(jù)無(wú)效(有效值為1).

5) 對(duì)上述樣本分別執(zhí)行步驟1)～3)，共生成34個(gè)新數(shù)據(jù)表(數(shù)據(jù)量過(guò)大，略之)，最優(yōu)近似度最大值為31的數(shù)據(jù)表一共有5個(gè).

6)優(yōu)化數(shù)據(jù)表：文獻(xiàn)4中提出對(duì)最優(yōu)近似度數(shù)據(jù)表循環(huán)執(zhí)行步驟1)～3)，直至獲取多變量決策表達(dá)式.在此對(duì)步驟5)所獲取的數(shù)據(jù)表進(jìn)行分析，發(fā)現(xiàn)5個(gè)數(shù)據(jù)表中有2個(gè)重復(fù)，如直接循環(huán)執(zhí)行步1)～3)，則會(huì)造成非常嚴(yán)重?cái)?shù)據(jù)重復(fù)運(yùn)算.因此對(duì)該算法提出優(yōu)化數(shù)據(jù)步驟，法則為：對(duì)最優(yōu)近似度數(shù)據(jù)表進(jìn)行數(shù)據(jù)比較，并去除重復(fù)數(shù)據(jù)表，再執(zhí)行循環(huán)步驟.優(yōu)化步驟5)后的3個(gè)數(shù)據(jù)表樣本數(shù)減少為12行，如表5所示.

表5 優(yōu)化后的3個(gè)數(shù)據(jù)表

7)對(duì)表6分別執(zhí)行步驟1)～3)，共生成30個(gè)新數(shù)據(jù)表(數(shù)據(jù)量過(guò)大，略之)，最優(yōu)近似度最大值為27的數(shù)據(jù)表一共3個(gè)，且數(shù)據(jù)完全相同.因此也證明了文獻(xiàn)4算法的內(nèi)斂性行為.獲取的數(shù)據(jù)表如表6所示.

表6 第二次復(fù)合運(yùn)算最優(yōu)近似度數(shù)據(jù)表

8)對(duì)表7循環(huán)執(zhí)行上述步驟(后續(xù)步驟，略之)直至推導(dǎo)出最終數(shù)據(jù)，值為：{?，?，?，2，1}.約簡(jiǎn)后的多變量表達(dá)式為：a4=2∧a5=1.

9)重設(shè)論域數(shù)據(jù)：獲取UY中可以用a4=2∧a5=1決策的數(shù)據(jù)σa4=2∧a5=1(UY)={3，6，10，12，14，15，16，19，20}.重設(shè)UY數(shù)據(jù)：UY=UY-σa4=2∧a5=1(UY)={1，7，8，13，18}.重設(shè)UY后的數(shù)據(jù)如表7所示.

表7 重設(shè)后的UY數(shù)據(jù)表

10)對(duì)表7循環(huán)執(zhí)行步驟1)～8)過(guò)程略…，推導(dǎo)出最終結(jié)果為：{?，?，?，1，1}.約簡(jiǎn)后的多變量表達(dá)式為：a4=1∧a5=1.分析表7，發(fā)現(xiàn)CY數(shù)據(jù)滿(mǎn)足被推導(dǎo)完畢.

2.6 完整的多變量邏輯表達(dá)式

根據(jù)上述分析后所獲取的多變量邏輯表達(dá)式包含：

1)獨(dú)立決策表達(dá)式有：a2=大D=Nora4=大D=Nora5=有D=N.

2)多變量表達(dá)式有：(a4=2∧a5=1)D=Y、(a4=1∧a5=1)D=Y.

依據(jù)2.4的聲明，將多變量表達(dá)式中的數(shù)值轉(zhuǎn)換回狀態(tài)值，最后獲取的多變量表達(dá)式為：(a4=無(wú)∧a5=無(wú))D=Yor (a4=小∧a5=無(wú))D=Y.

綜上所述，完整的邏輯表達(dá)式最終結(jié)果為：(風(fēng)=大)∨(降水=大)∨(雷電=有)D=N，(降水=無(wú)∧雷電=無(wú))∨(降水=小∧雷電=無(wú))D=Y.

轉(zhuǎn)換成對(duì)應(yīng)的邏輯語(yǔ)句為：

if (風(fēng)=”大”) or (降水=”大”) or (雷電=”有”)

then class=”N”;

if (降水=”無(wú)” and 雷電=”無(wú)”) or (降水=”小” and 雷電=”無(wú)”)

then class=”Y”;

3 結(jié)語(yǔ)

使用新型多變量決策樹(shù)算法，對(duì)選用的“天氣與戶(hù)外運(yùn)動(dòng)”典型數(shù)據(jù)進(jìn)行訓(xùn)練并構(gòu)造出相關(guān)決策樹(shù)，證明了該算法在“天氣與戶(hù)外運(yùn)動(dòng)”中的有效性、準(zhǔn)確性和高效性，也證明的戶(hù)外運(yùn)動(dòng)與雷電和降雨關(guān)系密切.同時(shí)為算法增加了步驟6)簡(jiǎn)單的“優(yōu)化數(shù)據(jù)”判斷方法，為算法進(jìn)一步提升運(yùn)算速度.在步驟7)中同時(shí)證明了新型多變量算法的內(nèi)斂性.然天氣變化因素并非單一，針對(duì)不同戶(hù)外運(yùn)動(dòng)進(jìn)行決策時(shí)應(yīng)針對(duì)實(shí)際情況對(duì)條件屬性進(jìn)行增刪，而非拘泥與此.故在使用新型多變量決策樹(shù)算法做各種決策時(shí)，更應(yīng)根據(jù)事實(shí)進(jìn)行實(shí)際分析.