【正文】 是一組例子（正例和反例），示例學(xué)習(xí)就是要從這些特殊知識(shí)中歸納出適用于更大范圍的一般性知識(shí)，以覆蓋所有的正例并排除所有反例。 觀察發(fā)現(xiàn)學(xué)習(xí) 觀察發(fā)現(xiàn)學(xué)習(xí)又稱為描述性概括，其目標(biāo)是確定一個(gè)定律或理論的一般性描述，刻畫觀察集，指定某類對(duì)象的性質(zhì)。觀察發(fā)現(xiàn)學(xué)習(xí)可分為觀察學(xué)習(xí)與機(jī)器發(fā)現(xiàn)兩種。前者用于對(duì)事例進(jìn)行聚類，形成概念描述；后者用于發(fā)現(xiàn)規(guī)律，產(chǎn)生定律或規(guī)則。 2022/2/15 《人工智能》 22 歸納學(xué)習(xí)示例 決策樹學(xué)習(xí) 決策樹學(xué)習(xí)是應(yīng)用最廣的歸納推理算法之一。它是一種逼近離散值函數(shù)的方法。在這種方法中學(xué)習(xí)到的函數(shù)被表示為一顆決策樹。學(xué)習(xí)得到的決策樹也能再被表示為多個(gè) ifthen規(guī)則，以提高可讀性。 決策樹學(xué)習(xí)方法對(duì)噪聲數(shù)據(jù)有很好的健壯性且能夠?qū)W習(xí)析取表達(dá)式。決策樹學(xué)習(xí)算法有很多，比如 ID ASSISTANT等等。這些決策樹學(xué)習(xí)方法搜索一個(gè)完整表示的假設(shè)空間，從而避免了受限假設(shè)空間的不足。決策樹學(xué)習(xí)的歸納偏置是優(yōu)先選擇較小的樹。 2022/2/15 《人工智能》 23 決策樹表示法 ? 決策樹通過把實(shí)例從根節(jié)點(diǎn)排列 (sort)到某個(gè)葉子節(jié)點(diǎn)來分類實(shí)例，葉子節(jié)點(diǎn)即為實(shí)例所屬的分類。樹上的每一個(gè)節(jié)點(diǎn)說明了對(duì)實(shí)例的某個(gè)屬性 (attribute)的測(cè)試，并且該節(jié)點(diǎn)的每一個(gè)后繼分枝對(duì)應(yīng)于該屬性的一個(gè)可能值。 ? 分類實(shí)例的方法是從這顆樹的根節(jié)點(diǎn)開始，測(cè)試這個(gè)節(jié)點(diǎn)指定的屬性，然后按照給定實(shí)例的該屬性值對(duì)應(yīng)的樹枝向下移動(dòng)。然后這個(gè)過程再以新節(jié)點(diǎn)為根的子樹上重復(fù)。 例子：在一個(gè)水果的分類問題中，采用的特征向量為： {顏色 ,尺寸 ,形狀 ,味道 }，其中：顏色取值為 {紅 ,綠 ,黃 }，尺寸取值為 {大 ,中 ,小 }，味道取值為 {甜 ,酸 }，形狀取值為 {圓 ,細(xì) }。 樣本集：一批水果，知道其特征向量及類別 問 題：一個(gè)新的水果，觀測(cè)到了其特征向量，將其分類 2022/2/15 《人工智能》 24 2022/2/15 《人工智能》 25 通常決策樹代表實(shí)例屬性值約束的合取 (conjunction)的析取式 (disjunction)。從樹根到樹葉的每一條路徑對(duì)應(yīng)一組屬性測(cè)試的合取，樹本身對(duì)應(yīng)這些合取的析取。 上述例子可對(duì)應(yīng)如下析取式： (color=green∧ size=big) ∨ (color=green∧ size=medium) ∨ (color=green∧ size=small) ∨ (color=yellow∧ shape=round∧ size=big) ∨ (color=yellow∧ shape=round∧ size=small) ∨ (color=yellow∧ shape=thin) ∨ (color=red∧ size=medium) ∨ (color=red∧ size=small∧ taste=sweet) ∨ (color=red∧ size=small∧ taste=sour) 2022/2/15 《人工智能》 26 決策樹的適用問題 ? 決策樹學(xué)習(xí)適合解決具有以下特征的問題 ? 實(shí)例是由 “ 屬性 值 ” 對(duì)表示的：實(shí)例是用一系列固定的屬性和它們的值來描述的。 ? 目標(biāo)函數(shù)具有離散的輸出值：決策樹給每個(gè)實(shí)例賦予一個(gè)布爾型的分類。決策樹方法很容易擴(kuò)展到學(xué)習(xí)有兩個(gè)以上輸出值的函數(shù)。 ? 可能需要析取的描述：決策樹很自然地代表了析取表達(dá)式。 ? 訓(xùn)練數(shù)據(jù)可以包含錯(cuò)誤：決策樹學(xué)習(xí)對(duì)錯(cuò)誤有很好的健壯性，無論是訓(xùn)練樣例所屬的分類錯(cuò)誤，還是描述這些樣例的屬性值錯(cuò)誤。 ? 訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例：決策樹甚至可以再有未知屬性值的訓(xùn)練樣例中使用。 2022/2/15 《人工智能》 27 決策樹學(xué)習(xí)的常見問題 ? 確定決策樹增長的深度，避免過度擬合； ? 處理連續(xù)值的屬性； ? 選擇一個(gè)適當(dāng)?shù)膶傩院Y選度量標(biāo)準(zhǔn)； ? 處理屬性值不完整的訓(xùn)練數(shù)據(jù)； ? 處理不同代價(jià)的屬性； ? 提高計(jì)算效率。 2022/2/15 《人工智能》 28 ID3算法 ? 大多數(shù)已開發(fā)的決策樹學(xué)習(xí)算法是一種核心算法 （ CLS算法 ） 的變體 。 該算法采用自頂向下的貪婪搜索遍歷可能的決策樹空間 。這種方法是 ID3算法 (Quinlan 1986)和后繼的 (Quinlan 1993)的基礎(chǔ) 。 ? ID3是一種自頂向下增長樹的貪婪算法，在每個(gè)節(jié)點(diǎn)選取能最好分類樣例的屬性。繼續(xù)這個(gè)過程指導(dǎo)這棵樹能完美分類訓(xùn)練樣例，或所有的屬性都已被使用過。 ? 構(gòu)造過程是從“哪一個(gè)屬性將在樹的根節(jié)點(diǎn)被測(cè)試”這個(gè)問題開始。為了回答這個(gè)問題，使用統(tǒng)計(jì)測(cè)試來確定每一個(gè)實(shí)例屬性單獨(dú)分類訓(xùn)練樣例的能力。分類能力最好的屬性被選作樹的根節(jié)點(diǎn)的測(cè)試。然后為根節(jié)點(diǎn)屬性的每個(gè)可能值產(chǎn)生一個(gè)分枝，并把訓(xùn)練樣例排列到適當(dāng)?shù)姆种Γㄒ簿褪?，樣例的該屬性值?duì)應(yīng)的分枝）之下。然后重復(fù)整個(gè)過程，用每個(gè)分枝節(jié)點(diǎn)關(guān)聯(lián)的訓(xùn)練樣例來選取在該點(diǎn)被測(cè)試的最佳屬性。這形成了對(duì)合格決策樹的貪婪搜索，也就是算法從不回溯重新考慮以前的選擇。 2022/2/15 《人工智能》 29 決策樹的構(gòu)建 ? 已知訓(xùn)練樣本集，構(gòu)造決策樹需要解決以下幾個(gè)問題（考慮 Binary Decision Trees）： （ 1）最佳提問的選擇：應(yīng)該先對(duì)哪一個(gè)屬性提出問題？應(yīng)該按什么樣的順序提出問題？ 每一個(gè)問題都是一個(gè) YES/NO問題。 （ 2）葉結(jié)點(diǎn)的確定：什么時(shí)候可以結(jié)束提問，并判定模式的類別？ （ 3）決策樹修剪：如果決策樹過大，應(yīng)該如何修剪決策樹，以保證其泛化能力？ 2022/2/15 《人工智能》 30 最佳提問的選擇（ 1） （ 1）決策樹中的每一個(gè)結(jié)點(diǎn)（葉結(jié)點(diǎn)除外）對(duì)應(yīng)于一個(gè)提問。每一個(gè)葉結(jié)點(diǎn)給出最終的分類。決策樹的構(gòu)建從根結(jié)點(diǎn)開始。 （ 2）根結(jié)點(diǎn)的構(gòu)建：根結(jié)點(diǎn)對(duì)應(yīng)于訓(xùn)練樣本集 D。通過選擇針對(duì)某一屬性的一個(gè)問題進(jìn)行提問，可以根據(jù)對(duì)該問題的回答，將訓(xùn)練樣本集 D分類兩個(gè)部分： Dy及 Dn （其中， Dy為回答YES的樣本， Dn為回答 NO的樣本） ，并建立與之相對(duì)應(yīng)的兩個(gè)子結(jié)點(diǎn)。我們希望選擇一個(gè)這樣問題進(jìn)行提問：使得 Dy及 Dn盡可能純凈。 （ 3）中間結(jié)點(diǎn)的構(gòu)造：對(duì)于每一個(gè)中間結(jié)點(diǎn)（結(jié)點(diǎn) N），都有一個(gè)與之對(duì)應(yīng)的子集 DN。同樣，根據(jù)結(jié)點(diǎn) N的提問，可以將DN進(jìn)一步劃分為兩個(gè)部分 DNy及 DNn（其中， DNy為回答YES的樣本， DNn為回答 NO的樣本），并得到與之相對(duì)應(yīng)的兩個(gè)子結(jié)點(diǎn)。我們希望根據(jù)結(jié)點(diǎn) N提出的問題，能夠使DNy及 DNn盡可能純凈。 2022/2/15 《人工智能》 31 最佳提問的選擇（ 2） （ 4）當(dāng)如上得到的某一個(gè)子結(jié)點(diǎn)足夠純凈時(shí)，就可以確定該結(jié)點(diǎn)為葉結(jié)點(diǎn)，并給出其類別。 （ 5）當(dāng)決策樹中的每一條路徑都對(duì)應(yīng)于一個(gè)葉結(jié)點(diǎn)時(shí)，學(xué)習(xí)過程結(jié)束，決策樹構(gòu)建完畢。 （ 6）根據(jù)上述準(zhǔn)則（純凈度準(zhǔn)則）構(gòu)建決策樹，可以保證決策樹的復(fù)雜度較?。ńY(jié)點(diǎn)數(shù)量少、深度?。? （ 7）在對(duì)訓(xùn)練集分類能力相近的條件下，復(fù)雜度小的決策樹（分類器）優(yōu)于復(fù)雜度大的決策樹（分類器）。復(fù)雜度小的分類器通常具有較好的泛化能力。這一原則稱為 Occam’s razor。 2022/2/15 《人工智能》 32 最佳提問的選擇（ 3） ( | )21( ) ( | ) l og jc pnjji n p n ????? ?( | )jnjnNpnN? ?（ 8）結(jié)點(diǎn) n非純凈度的定義 其中， i(n)為結(jié)點(diǎn) n的非純凈度， Nn 為結(jié)點(diǎn) n對(duì)應(yīng)的樣本的數(shù)量， Njn為結(jié)點(diǎn) n中屬于 ?j的樣本的數(shù)量，C為類別的個(gè)數(shù)。 2022/2/15 《人工智能》 33 最佳提問的選擇（ 4） ( ) ( ) ( ) ( )ny nnynnnN Ni n i n i n i nNN??? ? ? ????? 其中， ny為結(jié)點(diǎn) n的 YES子結(jié)點(diǎn)， nn 為 NO子結(jié)點(diǎn)， Nny為 YES子結(jié)點(diǎn)對(duì)應(yīng)的樣本的數(shù)量， Nnn為 NO子結(jié)點(diǎn)對(duì)應(yīng)的樣本的數(shù)量。 結(jié)點(diǎn) n的最佳選擇問題：使△ i(n)取得最大值。 （ 9）結(jié)點(diǎn) n最佳問題的選擇： 對(duì)于結(jié)點(diǎn) n，通過提出并回答某個(gè)問題，可以得到如下的純凈度的提高（不純凈度的降低）： 2022/2/15 《人工智能》 34 最佳提問的選擇（ 5） （ 10）結(jié)點(diǎn) n最佳問題的選擇范圍： 需要枚舉出所有可以提出的問題，從中選出有效的問題，并在這些有效的問題中選擇一個(gè)最佳的問題。 由于特征的數(shù)量是有限的，每個(gè)特征的可能取值也是有限的，所以所有可能提出的問題是可以枚舉的。 所提問題通常限制為針對(duì)某個(gè)特征提出的簡單問題，問題的形式如前面的二叉數(shù)所示。 2022/2/15 《人工智能》 35 葉結(jié)點(diǎn)的確定問題 決策樹結(jié)點(diǎn)劃分的原則是使其子結(jié)點(diǎn)盡可能純凈（指兩個(gè)子結(jié)點(diǎn)的平均純凈度最高）。對(duì)于任意一個(gè)結(jié)點(diǎn) n，可以出現(xiàn)以下三種情況： （ 1）結(jié)點(diǎn) n中的樣本屬于同一類，即結(jié)點(diǎn) n絕對(duì)純凈。此時(shí)結(jié)點(diǎn) n不可進(jìn)一步劃分。 （ 2）結(jié)點(diǎn) n中的樣本不屬于同一類，但是不存在任何一個(gè)劃分（即提出一個(gè)問題并根據(jù)該問題對(duì)結(jié)點(diǎn) n的樣本進(jìn)行劃分）可以使其子結(jié)點(diǎn)的平均純凈度高于結(jié)點(diǎn) n。此時(shí)結(jié)點(diǎn) n不可進(jìn)一步劃分。 （ 3）可以提出一個(gè)問題對(duì)結(jié)點(diǎn) n進(jìn)行劃分，從而使結(jié)點(diǎn) n的子結(jié)點(diǎn)具有更高的純凈度。此時(shí)結(jié)點(diǎn) n可以進(jìn)一步劃分。 2022/2/15 《人工智能》 36 葉結(jié)點(diǎn)的確定問題 ? 問題：在構(gòu)建決策樹的過程中，確定葉節(jié)點(diǎn)的一個(gè)策略是：對(duì)于每一個(gè)可以進(jìn)一步劃分的結(jié)點(diǎn)都進(jìn)行劃分，直到得到一個(gè)不可劃分的子結(jié)點(diǎn)，并將該子結(jié)點(diǎn)定為葉結(jié)點(diǎn)。這樣構(gòu)造的決策樹，其葉結(jié)點(diǎn)均為不可再進(jìn)一步劃分的結(jié)點(diǎn)。這種葉結(jié)點(diǎn)的確定方法是否可行？ ? 答案：決策樹是根據(jù)訓(xùn)練樣本的集合構(gòu)成的。該集合中的樣本是隨機(jī)的。不同的隨機(jī)實(shí)驗(yàn)會(huì)得到不同的樣本集合。因此，該集合并不能完全描述樣本 (即特征向量 )真實(shí)分布。當(dāng)葉結(jié)點(diǎn)按上述方法確定時(shí)，所得決策樹雖然對(duì)訓(xùn)練樣本集合給出了最優(yōu)的分類，但是卻背離了樣本的真實(shí)分布，因此削弱了對(duì)未來新樣本的分類能力。這一現(xiàn)象稱為過度擬合 (指決策數(shù)對(duì)訓(xùn)練樣本過度擬合，從而背離了樣本的真實(shí)分布 )。 2022/2/15 《人工智能》 37 葉結(jié)點(diǎn)確定的基本思路 （ 1）并不絕追求對(duì)訓(xùn)練樣本的正確劃分。并不絕對(duì)追求葉結(jié)點(diǎn)的純凈度。絕對(duì)追求葉結(jié)點(diǎn)的純凈度導(dǎo)致過度擬合。此時(shí)決策樹的復(fù)雜度偏高。 （ 2）要適度保證葉結(jié)點(diǎn)的純凈度，適度保證對(duì)訓(xùn)練樣本的正確分類能力。葉結(jié)點(diǎn)的不純凈度過高，對(duì)訓(xùn)練樣本的正確分類能力過低稱為欠學(xué)習(xí)（此時(shí)，決策樹不能夠充分提取樣本集合中蘊(yùn)涵的有關(guān)樣本真實(shí)分布的信息。欠學(xué)習(xí)同樣不能保證對(duì)未來新樣本的正確分類能力）。此時(shí)決策樹的復(fù)雜度偏低。 （ 3）因此，在決策樹的構(gòu)建過程中，需要在過度擬合與欠學(xué)習(xí)之間尋求合理的平衡，即尋求復(fù)雜度適中的決策樹。具體方法為：在結(jié)點(diǎn)還可以進(jìn)一步劃分的時(shí)候，可根據(jù)預(yù)先設(shè)定的準(zhǔn)則停止對(duì)其劃分，并將其設(shè)置為葉結(jié)點(diǎn)。 2022/2/15 《人工智能》 38 確定葉結(jié)點(diǎn)的基本方法（ 1） 方法 1：采用測(cè)試集的方法。將樣本集合分為訓(xùn)練集與測(cè)試集。根據(jù)訓(xùn)練集構(gòu)建決策樹，決策樹中的結(jié)點(diǎn)逐層展開。每展開一層子結(jié)點(diǎn)，并將其設(shè)為葉結(jié)點(diǎn)，就得到一棵決策樹，然后采用測(cè)試集對(duì)所得決策樹的分類性能進(jìn)行統(tǒng)計(jì)。重復(fù)上述過程，可以得到?jīng)Q策樹在測(cè)試集上的學(xué)習(xí)曲線。根據(jù)學(xué)習(xí)曲線，選擇在測(cè)試集上性能最佳的決策樹為最終的決策樹。 方法 2：在決策樹開始訓(xùn)練以前，首先設(shè)定一個(gè)閾值 A。在決策樹的訓(xùn)練過程中，對(duì)于任意一個(gè)結(jié)點(diǎn) n，如果該結(jié)點(diǎn)的最優(yōu)劃分（即最優(yōu)問題對(duì)該結(jié)點(diǎn)的樣本集合所作的劃分）所導(dǎo)致的純凈度的提高小于 A，則將該結(jié)點(diǎn)定為葉結(jié)點(diǎn)。采用該方法不需要將樣本集合分為訓(xùn)練集及測(cè)試集。決策樹直接采用全體樣本集合構(gòu)建。 2022/2/15 《人工智能》 39 確定葉結(jié)點(diǎn)的基本方法（ 2） ()n le a f n o d e ssiz e i n???? ?方法 3：在決策樹開始訓(xùn)練以前，首先設(shè)定一個(gè)閾值 A。在決策樹的訓(xùn)練過程中，對(duì)于任意一個(gè)結(jié)點(diǎn) n，如果 Nn/NA，則確定結(jié)點(diǎn)n為葉結(jié)點(diǎn)。其中， Nn為結(jié)點(diǎn) n對(duì)應(yīng)的樣本的數(shù)量， N 為全體樣本的數(shù)量。采用該方法同樣不需要將樣本集合分為訓(xùn)練集及測(cè)試集。決策樹直接采用全體樣本集合構(gòu)建。 方法 4：采用如下的性能準(zhǔn)則函數(shù)： 其中 size 代表決策樹的復(fù)雜度， i(n)為結(jié)點(diǎn) n 的非純凈度。該準(zhǔn)則函數(shù)表達(dá)出了過度擬合與欠學(xué)習(xí)之間的相互關(guān)系。決策樹的優(yōu)化準(zhǔn)則為：使該準(zhǔn)則函數(shù)取得最小值。 2022/2/15 《人工智能》 40 決策樹修剪（ 1） 決策樹的修剪是決策樹學(xué)習(xí)的另外一種有效的方法。其基本思路是