黃俊南

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

0 前言

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

1 選取戶外運動典型數(shù)據(jù)

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

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

表1 戶外運動信息系統(tǒng)表 續(xù)表

2 決策類劃分的多變量決策樹實例解析

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

2.1 根據(jù)決策樹性值劃分決策類

對戶外運動信息系統(tǒng)表(表1)U的決策值進行不可分辨關(guān)系劃分.決策屬性值域VD={Y，N}，論域U被劃分為Y,N兩個等價決策類，分別用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ǎo)出不同的決策屬性值時，表明論域存在數(shù)據(jù)二義性.通過二義性條件屬性排除法對上述論域樣本進行運算，CY∩CN=?，表明數(shù)據(jù)并未存在二義性.在選取典型數(shù)據(jù)時已充分考慮二義性問題，故在此未出現(xiàn)此類情況才為正常.

2.3 判斷獨立決策條件屬性

用CY和CN表示各條件屬性對應(yīng)決策值Y和N的集合，CN各個條件屬性的值域為：Va1N={熱，冷，適中}，Va2N={小，無，大}，Va3N={正常，高}，Va4N={大，無，小}，Va5N={無，有}.

CP各個條件屬性的值域為：Va1Y={熱，冷，適中}，Va2Y={小，無}，Va3Y={正常，高}，Va4Y={無，小}，Va5Y={無}.

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

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

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

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

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

2.5 獲取多變量邏輯表達式步驟

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

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

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

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

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

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

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

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

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

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

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

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

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

8)對表7循環(huán)執(zhí)行上述步驟(后續(xù)步驟，略之)直至推導(dǎo)出最終數(shù)據(jù)，值為：{?，?，?，2，1}.約簡后的多變量表達式為：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)對表7循環(huán)執(zhí)行步驟1)～8)過程略…，推導(dǎo)出最終結(jié)果為：{?，?，?，1，1}.約簡后的多變量表達式為：a4=1∧a5=1.分析表7，發(fā)現(xiàn)CY數(shù)據(jù)滿足被推導(dǎo)完畢.

2.6 完整的多變量邏輯表達式

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

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

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

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

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

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

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

then class=”N”;

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

then class=”Y”;

3 結(jié)語

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