一,決策樹-解決分類問題的一般方法

1、模型構建（歸納）

通過對訓練集合的歸納，建立分類模型。

2、預測應用（推論）

根據(jù)建立的分類模型，對測試集合進行測試

二, 決策樹的本質(zhì)

?決策樹是一種典型的分類方法

?首先對數(shù)據(jù)進行處理，利用歸納算法生成可讀的規(guī)則和決策樹，

?然后使用決策對新數(shù)據(jù)進行分析。

?本質(zhì)上決策樹是通過一系列規(guī)則對數(shù)據(jù)進行分類的過程。

三,決策樹的優(yōu)點

?1、推理過程容易理解，決策推理過程可以表示成If Then形式；

?2、推理過程完全依賴于屬性變量的取值特點；

?3、可自動忽略目標變量沒有貢獻的屬性變量，也為判斷屬性變量的重要性，減少變量的數(shù)目提供參考。

四,決策樹和歸納算法

?決策樹技術發(fā)現(xiàn)數(shù)據(jù)模式和規(guī)則的核心是歸納算法。

?歸納是從特殊到一般的過程。

?歸納推理從若干個事實中表征出的特征、特性和屬性中，通過比較、總結、概括而得出一個規(guī)律性的結論。

?歸納推理試圖從對象的一部分或整體的特定的觀察中獲得一個完備且正確的描述。即從特殊事實到普遍性規(guī)律的結論。

?歸納對于認識的發(fā)展和完善具有重要的意義。人類知識的增長主要來源于歸納學習。

?歸納學習由于依賴于檢驗數(shù)據(jù)，因此又稱為檢驗學習。

?歸納學習存在一個基本的假設：

?任一假設如果能夠在足夠大的訓練樣本集中很好的逼近目標函數(shù)，則它也能在未見樣本中很好地逼近目標函數(shù)。該假定是歸納學習的有效性的前提條件。

?歸納過程就是在描述空間中進行搜索的過程。

?歸納可分為自頂向下，自底向上和雙向搜索三種方式。

?自底向上法一次處理一個輸入對象。將描述逐步一般化。直到最終的一般化描述。

?自頂向下法對可能的一般性描述集進行搜索，試圖找到一些滿足一定要求的最優(yōu)的描述。

五.決策樹算法

?與決策樹相關的重要算法包括：

?CLS, ID3，C4.5，CART

?算法的發(fā)展過程

?Hunt,Marin和Stone 于1966年研制的CLS學習系統(tǒng)，用于學習單個概 念。

?1979年, J.R. Quinlan 給出ID3算法，并在1983年和1986年對ID3 進行了總結和簡化，使其成為決策樹學習算法的典型。

?Schlimmer 和Fisher 于1986年對ID3進行改造，在每個可能的決策樹節(jié)點創(chuàng)建緩沖區(qū)，使決策樹可以遞增式生成，得到ID4算法。

?1988年，Utgoff 在ID4基礎上提出了ID5學習算法，進一步提高了效率。

?1993年，Quinlan 進一步發(fā)展了ID3算法，改進成C4.5算法。

?另一類決策樹算法為CART，與C4.5不同的是，CART的決策樹由二元邏輯問題生成，每個樹節(jié)點只有兩個分枝，分別包括學習實例的正例與反例。

六,決策樹的表示

決策樹的基本組成部分：決策結點、分支和葉子

決策樹中最上面的結點稱為根結點。

是整個決策樹的開始。每個分支是一個新的決策結點，或者是樹的葉子。

每個決策結點代表一個問題或者決策.通常對應待分類對象的屬性。

每個葉結點代表一種可能的分類結果

在沿著決策樹從上到下的遍歷過程中，在每個結點都有一個測試。對每個結點上問題的不同測試輸出導致不同的分枝，最后會達到一個葉子結點。這一過程就是利用決策樹進行分類的過程，利用若干個變量來判斷屬性的類別.

七,決策樹與條件概率分布

?決策樹表示給定特征條件下類的條件概率分布。

?條件概率分布定義在特征空間的一個劃分(partition)上.將特征空間劃分為互不相交的單元(cell)或區(qū)域(region),并在每個單元定義一個類的概率分布就構成了一個條件概率分布。

?決策樹的一條路徑對應于劃分中的一個單元。

?決策樹所表示的條件概率分布由各個單元給定條件下類的條件概率分布組成

?決策樹學習本質(zhì)上是從訓練數(shù)據(jù)集中歸納出一組分類規(guī)則，與訓練數(shù)據(jù)集不相矛盾的決策樹。

?能對訓練數(shù)據(jù)進行正確分類的決策樹可能有多個，也可能 一個也沒有.我們需要的是一個與訓練數(shù)據(jù)矛盾較小的決策樹，同時具有很好的 泛化能力.

?決策樹學習是由訓練數(shù)據(jù)集估計條件概率模型.基于特征空間劃分的類的條件概率模型有無窮多個.

?我們選擇的條件概率模型應該不僅對訓練數(shù)據(jù)有很好的擬合，而且對未知數(shù)據(jù)有很好的預測.

八,決策樹CLS算法

?CLS（Concept Learning System）算法

?CLS算法是早期的決策樹學習算法。它是許多決策樹學習算法的基礎

?CLS基本思想

?從一棵空決策樹開始，選擇某一屬性（分類屬性）作為測試屬性。該測試屬性對應決策樹中的決策結點。根據(jù)該屬性的值的不同，可將訓練樣本分成相應的子集：

?如果該子集為空，或該子集中的樣本屬于同一個類，則該子集為葉結點，

?否則該子集對應于決策樹的內(nèi)部結點，即測試結點，需要選擇一個新的分類屬性對該子集進行劃分，直到所有的子集都為空或者屬于同一類。

?步驟：

?生成一顆空決策樹和一張訓練樣本屬性集;

?若訓練樣本集T 中所有的樣本都屬于同一類,則生成結點T , 并終止學習算法;否則

?根據(jù)某種策略從訓練樣本屬性表中選擇屬性A 作為測試屬性, 生成測試結點A

?若A的取值為v1,v2,…,vm, 則根據(jù)A 的取值的不同,將T 劃分成 m個子集T1,T2,…,Tm;

?從訓練樣本屬性表中刪除屬性A;

?轉(zhuǎn)步驟2, 對每個子集遞歸調(diào)用CLS;

?CLS算法問題：

?在步驟3中，根據(jù)某種策略從訓練樣本屬性表中選擇屬性A作為測試屬性。沒有規(guī)定采用何種測試屬性。實踐表明，測試屬性集的組成以及測試屬性的先后對決策樹的學習具有舉足輕重的影響。

九,決策樹ID3算法

?ID3算法是一種經(jīng)典的決策樹學習算法，由Quinlan于1979年提出。

?ID3算法主要針對屬性選擇問題。是決策樹學習方法中最具影響和最為典型的算法。

? 該方法使用信息增益度選擇測試屬性。

?當獲取信息時，將不確定的內(nèi)容轉(zhuǎn)為確定的內(nèi)容，因此信息伴著不確定性。

?從直覺上講，小概率事件比大概率事件包含的信息量大。如果某件事情是“百年一見”則肯定比“習以為常”的事件包含的信息量大。

信息增益

?Shannon 1948年提出的信息論理論：

?熵(entropy)：信息量大小的度量，即表示隨機變量不確定性的度量。

?熵的通俗解釋：事件ai的信息量I( ai )可如下度量：

?其中p(ai)表示事件ai發(fā)生的概率。

?假設有n個互不相容的事件a1,a2,a3,….,an,它們中有且僅有一個發(fā)生，則其平均的信息量(熵)可如下度量：

?熵的理論解釋：

?設X是一個取有限個值的離散隨機變量，其概率分布為：

?則隨機變量X的熵定義為：

?對數(shù)以2為底或以e為底(自然對數(shù))，這時熵的單位分別稱作比特(bit)或納特(nat),熵只依賴于X的分布，與X的取值無關。

?熵的理論解釋：

?熵越大，隨機變量的不確定性越大

?定義5.2 (信息增益):特征A對訓練數(shù)據(jù)集D的信息增益，g(D,A), 定義為集合D的經(jīng)驗熵H(D)與特征A給定條件下D的經(jīng)驗條件熵H(D|A)之差，即

g(D,A)=H(D)-H(D|A)

?(Information gain)表示得知特征X的信息而使得類Y的信息的不確定性減少的程度.

?—般地，熵H(Y)與條件熵H(Y|X)之差稱為互信息（mutual information)

?決策樹學習中的信息增益等價于訓練數(shù)據(jù)集中類與特征的互信息.

.....

后續(xù)再更