朱弘揚(yáng)，丁 怡，柴華金，李 升

（1. 廣東海洋大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院；2. 廣東海洋大學(xué) 機(jī)械與動(dòng)力工程學(xué)院，廣東 湛江 524088）

伴隨著人工智能技術(shù)的飛速發(fā)展和廣泛應(yīng)用，模式識(shí)別和機(jī)器學(xué)習(xí)等基于數(shù)據(jù)處理的研究領(lǐng)域變得比以往任何時(shí)期都更具有重要意義，而分類是處理數(shù)據(jù)挖掘問題無(wú)法避免的基礎(chǔ)操作[1]. 決策樹是解決分類問題的一種經(jīng)典算法，相比于神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)和邏輯回歸算法，決策樹算法更容易理解和操作，尤其是在處理多分類問題和離散型數(shù)值分類問題中具有較高的自主學(xué)習(xí)能力和較低的先驗(yàn)知識(shí)要求，因而在很多領(lǐng)域都有著廣泛的應(yīng)用. 決策樹算法是一種逼近離散值目標(biāo)函數(shù)的方法，這種方法通過對(duì)訓(xùn)練集的學(xué)習(xí)，找到特定樣本環(huán)境下樣本類別屬性和單個(gè)特征屬性的集合關(guān)系，并提取出該特定環(huán)境和集合關(guān)系作為分類規(guī)則，把所有的分類規(guī)則構(gòu)建為一棵決策樹，從而達(dá)到預(yù)測(cè)模型的目的. 決策樹方法以其速度快、精度高、生成的模式簡(jiǎn)單等優(yōu)點(diǎn)，在數(shù)據(jù)挖掘中受到許多研究者和軟件公司的關(guān)注[2].

單標(biāo)簽分類問題是一類典型的矛盾問題，因?yàn)闃颖静豢赡芡瑫r(shí)屬于兩種類別，因而造成了分類結(jié)果“是”與“不是”的單一描述，和“對(duì)”或“不對(duì)”的評(píng)價(jià)標(biāo)準(zhǔn)[3]. 可拓學(xué)是以矛盾問題為研究對(duì)象、以矛盾問題的智能化處理為主要內(nèi)容、以可拓方法論為主要研究方法的一門學(xué)科，對(duì)矛盾問題的解決有著橫跨哲學(xué)、數(shù)學(xué)和工程學(xué)領(lǐng)域的邏輯思維模式. 所以不同于其他學(xué)者從正確率、泛化能力和分類效率等方面對(duì)決策樹進(jìn)行分析和改進(jìn)，從數(shù)學(xué)推導(dǎo)和計(jì)算的方式來(lái)評(píng)價(jià)該算法，文章嘗試從可拓邏輯和可拓思維模式的角度對(duì)決策樹分類算法的各個(gè)步驟進(jìn)行邏輯和理論分析，從全新視角下驗(yàn)證決策樹算法的可行性和優(yōu)劣性，并根據(jù)可拓集理論以關(guān)聯(lián)函數(shù)為參考，建立一套關(guān)于決策樹分類結(jié)果的評(píng)價(jià)體系.

1 決策樹算法簡(jiǎn)介

決策樹學(xué)習(xí)算法是一種歸納算法，它采用自上而下、閾值區(qū)分的方法將樣本集劃分為若干個(gè)互不相交的子集，并將每個(gè)子集按層層遞進(jìn)的規(guī)則提取出來(lái)作為一個(gè)分枝，并建立決策樹，用來(lái)形成分類器和預(yù)測(cè)模型，可以對(duì)未知數(shù)據(jù)進(jìn)行分類、預(yù)測(cè)和數(shù)據(jù)預(yù)處理等. 每一層選擇哪個(gè)屬性作為子節(jié)點(diǎn)，以及怎樣對(duì)子節(jié)點(diǎn)進(jìn)行分枝將決定決策樹的規(guī)模和分類精度[2]. 設(shè)訓(xùn)練集為S，其類別集包含 k個(gè)類別值{c1，c2，···，ck}，每個(gè)樣本有個(gè)屬性 (A1，A2，···，AM).構(gòu)建決策樹的一般流程如下[4-6].

Step1 把全體樣本集作為根節(jié)點(diǎn)，計(jì)算所有屬性的信息增益值，并找到信息增益值最大的屬性作為分枝的子節(jié)點(diǎn).

(1) 根據(jù)類別集劃分樣本集S所得信息熵為

其中，Pi(i=1，2，···.k)為樣本屬于類別ci的概率，Pi=|ci|/|S|，|ci|為樣本集S中屬于第i個(gè)類別ci的樣本個(gè)數(shù)，|S|是樣本集S所含樣本的個(gè)數(shù).

(2) 假{設(shè)所有樣本}的第 m個(gè) 屬性 Am共有 q 個(gè)不同的取值，a1，a2，···，aq，把取值為aj的樣{本劃分到同}一個(gè)子集Sj，則樣本可以劃分為q 個(gè) 子集S1，S2，···，Sq，根據(jù)屬性 Am劃分樣本集S的信息熵為

(3) 屬性 Am的信息熵為

根據(jù)式(4)～(5)可得信息增益率

Step2 選擇信息增益率最大的屬性作為子節(jié)點(diǎn)對(duì)根節(jié)點(diǎn)進(jìn)行分類，把樣本集分為若干子集，然后采用與step1相同的方法遞歸地對(duì)子集進(jìn)行分類，建立樹的分枝，一直循環(huán)到所有分枝節(jié)點(diǎn)中的樣本都屬于同一類別，則該子節(jié)點(diǎn)就成為葉子節(jié)點(diǎn)，該分枝停止生長(zhǎng).

Step3 對(duì)構(gòu)建好的決策樹進(jìn)行剪枝，消除噪聲和孤立點(diǎn)等隨機(jī)因素的影響，以得到簡(jiǎn)化的決策樹，其中剪枝方法可分為預(yù)剪枝和后剪枝兩種類型.

Step4 根據(jù)修剪好的決策樹，提取分類規(guī)則，對(duì)新的樣本進(jìn)行逐層分類，一直到葉子結(jié)點(diǎn)，從而預(yù)測(cè)樣本的類別.

2 可拓學(xué)視角下的決策樹算法分析

可拓學(xué)理論認(rèn)為解決矛盾問題的工具是變換和推理，若不考慮事物的內(nèi)涵和外延，就不能表達(dá)物、事、關(guān)系和特征變換以及變換所引起的其他物、事、關(guān)系和特征變換的傳導(dǎo)變換. 所以可拓學(xué)處理矛盾問題的過程就是把物、事、關(guān)系看成是可以拓展的，并根據(jù)物、事、關(guān)系的可拓性，變換問題的目標(biāo)或條件，使得目標(biāo)得以實(shí)現(xiàn)[7].

決策樹算法是解決分類問題這一典型矛盾問題的有效方法，其解決問題的過程符合可拓學(xué)處理矛盾問題的理論，樣本的屬性和類別就是事物的內(nèi)涵，樣本的屬性和類別之間的關(guān)系就是事物的外延，而樣本某一或某些屬性值的變化導(dǎo)致類別發(fā)生變化，就是事物的傳導(dǎo)變換. 文章從可拓思維模式中的菱形思維模式的角度分析決策樹算法每個(gè)節(jié)點(diǎn)的選擇，以可拓邏輯中基元變換理論來(lái)評(píng)價(jià)決策樹算法的規(guī)則提取，以可拓邏輯中的基元發(fā)散規(guī)則來(lái)解釋決策樹算法的預(yù)測(cè)步驟，驗(yàn)證了決策樹算法和可拓學(xué)理論的契合程度.

2.1 菱形思維模式

菱形思維模式是一種先發(fā)散后收斂的思維方式，它包括了發(fā)散思維和收斂思維兩個(gè)階段. 利用菱形思維模式解決問題，首先對(duì)問題進(jìn)行拓展分析，提出解決問題的盡可能多的信息和豐富資料，這個(gè)過程就是發(fā)散；然后從可行性、優(yōu)劣性、相容性等角度

出發(fā)對(duì)信息進(jìn)行整合，向最佳的解決方案聚焦，這個(gè)過程就是收斂[8-10]. 在構(gòu)建決策樹的過程中，找到每個(gè)節(jié)點(diǎn)，即每個(gè)子集的最優(yōu)的分類屬性，我們要拓展出所有會(huì)影響分類效果的信息，不僅要考慮每個(gè)屬性分類的精度和分類的集中度，為了構(gòu)建更簡(jiǎn)單有效的決策樹，還要考慮子集的類別復(fù)雜度和屬性復(fù)雜度；在找到所有影響因素之后，還需要對(duì)這些因素進(jìn)行綜合考慮，使得決策樹在精度和復(fù)雜度兩個(gè)方面達(dá)到平衡. 利用可拓思維模式中的菱形思維模式來(lái)解決這一問題的模型如圖1所示[11-12].

圖1 決策樹的菱形思維模式Fig.1 The rhombus thought model of Decision Tree

在圖1子集 T(Am，C，v)中，T ， Am表示當(dāng)前考慮的屬性，表示子集 T 的類別集，而v 表示對(duì)分類效果有影響的因素. 根據(jù)屬性 Am對(duì)子集T 分類的菱形思維模式過程如下：

(1) 在菱形思維模式的第一階段進(jìn)行發(fā)散思維，發(fā)現(xiàn)對(duì)分類效果有影響的因素有：根據(jù)類別集C 劃分樣本集 T 所得信息熵 T(Am，C，I(C))，根據(jù)屬性 Am對(duì)子集 T 分類的所得信息熵T (Am，C，E(Am))，和屬性 Am的信息熵T (Am，C，Split(Am))；

(2) 在菱形思維模式的第二階段進(jìn)行收斂思維，根據(jù)式(4)把 T(Am，C，I(C))和 T(Am，C，E(Am))綜合考慮為一個(gè)新的因素T (Am，C，Gain(Am))；

(3) 在菱形思維模式的第三階段繼續(xù)對(duì)第二階段的兩個(gè)因素進(jìn)行收斂思維，根據(jù)式(6)把T(Am，C，Gain(Am))和T(Am，C，Split(Am))組合為一個(gè)新的因素 T(Am，C，Gain_Ratio(Am))，就得到可以同時(shí)考慮到 I(C)，E (Am)和 Split(Am)3個(gè)因素的選擇節(jié)點(diǎn)的評(píng)價(jià)指標(biāo).

2.2 基元變換

可拓邏輯不同于經(jīng)典數(shù)理邏輯和模糊邏輯，是通過變換和推理將矛盾問題轉(zhuǎn)換為不矛盾問題的邏輯思維方法. 在數(shù)理邏輯和模糊邏輯中，事物是否屬于某種類別，命題為“真”或“假”是對(duì)立的，但在可拓邏輯中，由于引入了變換，事物屬于某類別的程度或者說命題的“真假”程度是會(huì)隨著事物某些屬性的改變而改變的，比如性別“男”和“女”是對(duì)立的，但在生活中我們經(jīng)常會(huì)有“很男人”或者某人比另外一人“更男人”的說法. 所以，數(shù)理邏輯是從靜態(tài)的角度研究事物的特征和命題的真假，而可拓邏輯從變換的角度研究事物的動(dòng)態(tài)和變化的特征[13].

決策樹分類規(guī)則的提取是基于屬性的分類方法，在每一個(gè)節(jié)點(diǎn)都根據(jù)該節(jié)點(diǎn)的屬性，把具有相同屬性值的樣本分到同一個(gè)子集，然后在對(duì)所有子集使用同樣的方法遞歸處理，直到子集里的樣本全都屬于同一類，則該分枝就是一個(gè)分類規(guī)則. 把樣本看作基元，樣本的屬性和類別就是基元的要素，樣本某一屬性的取值不同可能會(huì)使得樣本的類別不同，就相當(dāng)于基元內(nèi)部的某一屬性要素的變化導(dǎo)致了類別要素的傳導(dǎo)變換.

圖2為一棵簡(jiǎn)單的決策樹，首先根據(jù)屬性 A1的3個(gè)取值 a11，a12，a13把樣本集分為3個(gè)子集，其中第二個(gè)子集中的樣本都屬于同一類別 c1，因此成為葉子結(jié)點(diǎn)，然后再對(duì)另外兩個(gè)子集根據(jù)不同的屬性繼續(xù)劃分為不同的子集，直到子集中的樣本都屬于同一類別為止.

圖2 簡(jiǎn)單決策樹Fig.2 A simple decision tree

根據(jù)可拓學(xué)基元變換的理論，圖2決策樹的分類規(guī)則可以理解為對(duì)于具有多個(gè)屬性的基元，即使僅僅改變其中一個(gè)重要屬性，也有可能會(huì)對(duì)基元的性質(zhì)產(chǎn)生影響，而相反的，改變多個(gè)無(wú)關(guān)屬性，也有可能對(duì)基元的性質(zhì)沒有影響. 文本將可拓化的樣本記作基元O，傳導(dǎo)規(guī)則T決定了基元O的所屬類別C，比如 A1→c1該分枝決策規(guī)則的基元變換的傳導(dǎo)規(guī)則為

即若基元O的A1特征取值為a12，那么該基元屬于c1類. 樣本屬于類別c3的A1→A2→c3決策規(guī)則的基元變換的傳導(dǎo)規(guī)則為

即若基元O的A1特征取值為a12，A2特征取值為a21，那么該基元屬于c3類.

A1→A3→c2決策規(guī)則的基元變換的傳導(dǎo)規(guī)則為

對(duì)基元O 做變換TOO ，改變其關(guān)鍵特征 A1、A2、A3的量值就會(huì)改變基元的類別性質(zhì)C ，而其他的變換沒有影響.

2.3 預(yù)測(cè)中的基元發(fā)散規(guī)則

決策樹構(gòu)建完成以后，就可以用來(lái)預(yù)測(cè)新樣本的類別. 根據(jù)樣本在決策樹中根節(jié)點(diǎn)屬性的取值，把樣本劃分到不同的子集，然后再根據(jù)子節(jié)點(diǎn)的屬性取值繼續(xù)劃分，直到把樣本劃分到葉子結(jié)點(diǎn)，就得到樣本類別的預(yù)測(cè)結(jié)果. 這種預(yù)測(cè)方法和可拓學(xué)中基元的發(fā)散過程推理是一致的. 基元發(fā)散是基元拓展推理中的一種，可以利用基元的發(fā)散推理，結(jié)合決策樹的分類規(guī)則，對(duì)已知類別的樣本進(jìn)行發(fā)散，把某些屬性和該已知樣本的取值相同的未知樣本分類到該類別中[14-15]. 如圖2所示的決策樹，根據(jù)訓(xùn)練得到的A1→c1規(guī)則為 A1屬性取值為 a12的樣本為c1類，那么對(duì)未知樣本進(jìn)行預(yù)測(cè)時(shí)，如果某樣本 S1的 A1屬性取值為 a12，那么無(wú)論其他屬性的取值怎樣都可以根據(jù)發(fā)散規(guī)則預(yù)測(cè)該樣本為 c1類. 同理，根據(jù)A1→A3→c1規(guī)則，若某樣本S2的 A1屬性取值為 a13，并且 A3屬性取值為 a31，無(wú)論其他屬性怎樣，該樣本都可以預(yù)測(cè)為c1類，其基元發(fā)散推理過程為

根據(jù) A1→A2→c2規(guī)則和 A1→A3→c2規(guī)則，可以得到c2類樣本的基元發(fā)散推理過程為

3 可拓評(píng)價(jià)體系

在構(gòu)建決策樹的過程中，不同的分類規(guī)則也有可能得到同樣的分類結(jié)果，如圖2所示的決策樹中，A1→c1和A1→A3→c1都可以得到結(jié)果為c1的分類結(jié)果. 對(duì)于傳統(tǒng)的決策樹預(yù)測(cè)，不同規(guī)則預(yù)測(cè)得到的相同結(jié)果，并沒有進(jìn)行更具體的區(qū)分. 但很明顯，在日常生活的很多分類問題中，不同事物屬于同一類別的程度是不一樣的. 比如，香蕉和蘋果都屬于水果，而且沒有隸屬程度的區(qū)別，但是換一個(gè)問題，身高178 cm和身高185 cm的人都可能被分類為“高個(gè)”，但很明顯后者隸屬于這一類別的程度要更多一些.為了評(píng)價(jià)決策樹預(yù)測(cè)結(jié)果的程度多少，筆者參考可拓學(xué)中關(guān)聯(lián)函數(shù)的內(nèi)容，建立以可拓距反映隸屬程度的評(píng)價(jià)體系[16].

當(dāng)樣本根據(jù)決策樹的某一分枝的預(yù)測(cè)規(guī)則被預(yù)測(cè)為某一類別時(shí)，找到訓(xùn)練集中所有符合該規(guī)則的樣本，求得其每個(gè)屬性的平均取值，最大取值和最小取值，把每個(gè)屬性都取平均值的樣本視為該分枝的標(biāo)準(zhǔn)枝，把每個(gè)屬性的最大值的和最小值的作為樣本取值區(qū)間的上下限. 然后計(jì)算預(yù)測(cè)樣本與標(biāo)準(zhǔn)枝的可拓距，以此來(lái)反映樣本屬于該類別的程度.

假設(shè)數(shù)據(jù)集中樣本共有5個(gè)屬性，其決策樹規(guī)則如圖2所示，某樣本S=(a11，a22，a3，a4，a5)在分枝A1→A2→c2規(guī)則下，被分為c2類. 因?yàn)闃颖緦儆谕环种?，若?jié)點(diǎn)屬性是離散的，那么節(jié)點(diǎn)屬性的取值是一樣的，只需要統(tǒng)計(jì)該分枝非節(jié)點(diǎn)屬性的最大值和最小值，計(jì)算平均值. 訓(xùn)練集中屬于該分枝下的樣本 A1屬性和 A2屬性的取值都應(yīng)該為a11，a22，若訓(xùn)練樣本中 A3、A4和 A5屬性的平均取值為(?ˉ，βˉ，λˉ)，最大取值為(?1，β1(，λ1)，最小取值)為( ?2，β2，λ2)，那么該分枝的標(biāo)準(zhǔn)枝為 a11，a22該樣本在 A3屬性上與c2類的可拓距為

同理，該樣本在屬性 A4和 A5上與c2類的可拓距為

根據(jù)式(12-14)，把樣本S與該分枝的標(biāo)準(zhǔn)枝的可拓距定義為

可拓距越小，則表示該樣本屬于 c2類的程度或者可能性越大.

若樣本的特征量化值是連續(xù)的，需要對(duì)某分枝上所有樣本找到每個(gè)屬性的最大值和最小值，并求得平均值，作為該分枝的標(biāo)準(zhǔn)枝. 以fisher iris數(shù)據(jù)為例，我們建立一套基于可拓距的決策樹分類評(píng)價(jià)體系，因?yàn)樵摂?shù)據(jù)的特征量化值是連續(xù)的，因此得到如圖3所示的二叉樹.

圖3 fisher iris的決策樹Fig.3 Tree of fisher iris

4 結(jié)論

可拓學(xué)以形式化的模型，探討事物拓展的可能性以及開拓創(chuàng)新的規(guī)律與方法，并用于解決矛盾問題，其理論價(jià)值或應(yīng)用價(jià)值在各個(gè)領(lǐng)域都能得到體現(xiàn). 本文以可拓學(xué)的視角去解析決策樹分類算法的邏輯推理過程，不僅證明了決策樹算法和可拓學(xué)理論的契合性，還對(duì)決策樹算法的預(yù)測(cè)結(jié)果建立基于可拓距的評(píng)價(jià)標(biāo)準(zhǔn).