第三章線性和非線性判別分析第三章線性和非線性判別分析3.1Fisher線性判別3.2感知準則函數(shù)3.3廣義線性判別分析3.4k近鄰3.5決策樹第三章線性和非線性判別分析3.1Fisher線性判別3.2感知準則函數(shù)3.3廣義線性判別分析3.4k近鄰3.5決策樹4貝葉斯估計：先驗概率和類條件概率密度已知，通過貝葉斯公式，來求解后驗概率的問題。實際問題中，類條件概率密度可能并不知道，這種情況下，可以采用非參數(shù)估計——當樣本比較充足的時候，估計類條件概率密度的方法。但實際中，有時候并沒有充分的樣本，同時存在樣本維數(shù)比較高，這種情況下，可能會使類條件概率密度估計不準確，我們就采用另一種方法。線性判別函數(shù)：我們直接假設判別函數(shù)，我們用樣本估計判別函數(shù)的參數(shù)，這樣就省去了估計類條件概率。在這一章之后，都采用這種方式。我們直接估計決策面或判別函數(shù)。這種情況下，最簡單的是假設判別函數(shù)是線性函數(shù)。決策面是超平面。3.1Fisher線性判別5假設判別函數(shù)是線性的時候，利用樣本用什么準則來求解這個判別函數(shù)的參數(shù)？當判別函數(shù)的參數(shù)有了，這個判別函數(shù)就確定了，這樣決策面也就確定了。如果假設判別函數(shù)為線性函數(shù)，包含參數(shù)w和w0。當準則函數(shù)不同，求解出的參數(shù)就存在不同。貝葉斯決策中，最小錯誤率和最小風險就是準則函數(shù)，不同的準則最終判別函數(shù)存在不同。貝葉斯分類器，它使得錯誤率或風險達到最小，是所有分類器中的最優(yōu)分類器。而其他準則函數(shù)下得到的分類器稱為次優(yōu)分類器。后續(xù)章節(jié)中介紹的準則函數(shù)，求出的是給定準則下的最優(yōu)解。求得的最優(yōu)解并不是這個問題的最優(yōu)解。既然是次優(yōu)解，為什么去研究？因為在樣本有限情況下，簡單容易實現(xiàn)，計算代價，存儲量，求解速度快。所以，線性判別函數(shù)方法廣泛使用。3.1Fisher線性判別63.1Fisher線性判別7方程g(x)=0定義了一個決策面，把歸于不同類的點分割開來，當g(x)為線性函數(shù)時，這個決策面便是超平面。3.1Fisher線性判別8設計線性分類器的步驟3.1Fisher線性判別9Fisher線性判別出發(fā)點：—應用統(tǒng)計方法解決模式識別問題時，一再碰到的問題之一就是維數(shù)問題。—在低維空間里解析上或計算上行得通的方法，在高維空間里往往行不通。—降低維數(shù)有時就會成為處理實際問題的關鍵。問題描述：對兩分類問題，考慮把d維空間的樣本投影到一條直線上，形成一維空間，即把維數(shù)壓縮到一維，同時保持較好的分類性能。3.1Fisher線性判別引言10如何根據(jù)實際數(shù)據(jù)找到一條最好的、最易于分類的投影方向，這就是Fisher判別方法所要解決的基本問題。（1）降低維數(shù)，降低計算復雜度；（2）易于分類的；3.1Fisher線性判別11假設有一集合D包含m個n維樣本{x1,x2,…,xm}

第一類樣本集合記為D1，規(guī)模為N1第二類樣本集合記為D2，規(guī)模為N2若對xi的分量做線性組合可得標量：yi

=wTxi,i=1,2,…,m這樣便得到m個一維樣本yi組成的集合，并可分為兩個子集D'1和D'2。從d維空間到一維空間的一般數(shù)學變換方法—w的值是無關緊要的，它僅使x乘上一個比例因子，重要的是選擇w的方向。它將影響樣本投影后的可分離程度。—上述尋找最佳投影方向的問題，在數(shù)學上就是尋找最好的變換向量w*的問題。3.1Fisher線性判別Fisher準則函數(shù)基本思想12最佳投影方向的評價依據(jù)：

使兩類樣本在該軸上投影之間的距離盡可能遠，而每一類樣本的投影盡可能緊湊。如何度量？評價標準—類內(nèi)離散度矩陣，類間離散度矩陣x1x2w1H:g=0w23.1Fisher線性判別13

在n維X空間(1)各類樣本的均值向量：(2)樣本類內(nèi)離散度矩陣Si和總樣本類內(nèi)離散度矩陣SwFisher準則函數(shù)中的基本參量其中Sw是對稱半正定矩陣，而且當m>n時通常是非奇異的。(3)樣本類間離散度矩陣Sb其中Sb是對稱半正定矩陣。3.1Fisher線性判別14

在一維Y空間(1)各類樣本的均值:

(2)樣本類內(nèi)離散度

和總樣本類內(nèi)離散度Fisher準則函數(shù)中的基本參量(3)樣本類間離散度3.1Fisher線性判別15

目標：投影后，在一維Y空間中各類樣本盡可能分得開些，即使原樣本向量在該方向上的投影能兼顧類間分布盡可能分開，類內(nèi)樣本投影盡可能密集的要求.Fisher準則函數(shù)3.1Fisher線性判別16

目標：投影后，在一維Y空間中各類樣本盡可能分得開些，即使原樣本向量在該方向上的投影能兼顧類間分布盡可能分開，類內(nèi)樣本投影盡可能密集的要求.Fisher準則函數(shù)：Fisher最佳投影方向的求解:不同類的投影點盡量分開同一類的投影點盡量靠近Fisher準則函數(shù)3.1Fisher線性判別17Fisher準則函數(shù)由各類樣本均值可推出：投影樣本均值之差可以展開為：將J(w)變成w的顯函數(shù)3.1Fisher線性判別18由類內(nèi)散布矩陣可推出：于是有：Fisher準則函數(shù)準則函數(shù)可以寫為：3.1Fisher線性判別19要求使J(w)最大的w，可以采用Lagrange乘子法求解。假設分母等于非零常數(shù)，即：定義Lagrange函數(shù)為：最佳變換向量w*的求取

矩陣/向量求導法則3.1Fisher線性判別20要求使J(w)最大的w，可以采用Lagrange乘子法求解。假設分母等于非零常數(shù)，即：定義Lagrange函數(shù)為：對w求偏導數(shù)，令偏導數(shù)為0：即：標量R最佳變換向量w*的求取

3.1Fisher線性判別21由于w的模對問題本身無關緊要，因此降維：對樣本集合作線性變換w*Tx，得到n個樣本投影后

的樣本值y1，y2，……，ynFisher線性判別分析3.1Fisher線性判別22一維空間的分類面是一個點將兩類分開即是確定一個閾值分類規(guī)則:Fisher線性分類3.1Fisher線性判別23例：兩組訓練數(shù)據(jù)D1和D2D1=[-0.4,0.58,0.089;-0.31,0.27,-0.04;-0.38,0.055,-0.035;-0.15,0.53,0.011;-0.35,0.47,0.034;0.17,0.69,0.1;-0.011,0.55,-0.18;-0.27,0.61,0.12;-0.065,0.49,0.0012;-0.12,0.054,-0.063]D2=[0.83,1.6,-0.014;1.1,1.6,0.48;-0.44,-0.41,0.32;0.047,-0.45,1.4;0.28,0.35,3.1;-0.39,-0.48,0.11;0.34,-0.079,0.14;-0.3,-0.22,2.2;1.1,1.2,-0.46;0.18,-0.11,-0.49]例題3.1Fisher線性判別（1）求取兩組訓練數(shù)據(jù)D1和D2的均值向量

和由公式：得:例題3.1Fisher線性判別（2）然后求取兩組訓練數(shù)據(jù)D1和D2的類內(nèi)散度矩陣Si和總樣本類內(nèi)離散度矩陣Sw。由公式：得:例題3.1Fisher線性判別（3）求取最佳變換向量w*

由公式：得投影方向（4）求閾值由公式：得例題3.1Fisher線性判別（5）將兩組訓練數(shù)據(jù)D1和D2作線性變換，得到20個樣本投影后的樣本值兩組數(shù)據(jù)投影后的樣本值分別為：例題3.1Fisher線性判別28訓練效果圖：例題3.1Fisher線性判別測試數(shù)據(jù)和

：計算投影變換和：由：得：判別準則：例題3.1Fisher線性判別301.Fisher辨別分析要求：在UCI數(shù)據(jù)集上的Iris和sonar數(shù)據(jù)上驗證算法的有效性；Iris數(shù)據(jù)3類，4維，150個數(shù)據(jù)；Sonar數(shù)據(jù)2類，60維，208個樣本；訓練和測試樣本有三種方式進行劃分：（三選一）1）將數(shù)據(jù)隨機分訓練和測試，多次平均求結果2）k折交叉驗證3）留1法仿真結果+報告。第一次大作業(yè)3.1Fisher線性判別第三章線性和非線性判別分析3.1Fisher線性判別3.2感知準則函數(shù)3.3廣義線性判別分析3.4k近鄰3.5決策樹幾個基本概念線性可分樣本的規(guī)范化解向量和解區(qū)對解區(qū)的限制3.2感知準則函數(shù)線性可分性假設樣本集，為樣本個數(shù)m，為n維向量，其中包含兩類和。如果存在一個向量，滿足如下條件，則稱樣本集是線性可分的，反之是線性不可分的。33幾個基本概念3.2感知準則函數(shù)樣本的規(guī)范化對于線性可分的樣本集，若令則樣本集線性可分的條件可改寫為。上述過程就被稱為樣本的規(guī)范化。被稱為規(guī)范化增廣樣本向量，后續(xù)介紹中，我們簡化記為。34幾個基本概念3.2感知準則函數(shù)解向量和解區(qū)對于線性可分的一組樣本(規(guī)范化增廣樣本向量)，若存在一個權向量滿足則稱為一個解向量，在權值空間中所有解向量組成的區(qū)域稱作為解區(qū)。35幾個基本概念3.2感知準則函數(shù)對解區(qū)的限制由于解向量不唯一，我們可以通過加入額外的限制得到更好的選擇。一般認為，越靠近解區(qū)中間的解向量，似乎越能對新的樣本正確分類。因此，我們可以選找一個單位長度的解向量使之最大化樣本到分界面的距離，也可以引用一個余量

，尋找對所有樣本滿足的最小長度的向量。新的解區(qū)位于原解區(qū)之中，而且它的邊界到原解區(qū)邊界的距離為。實際上，只要解向量嚴格位于解區(qū)之中都能滿足要求，這里引入余量主要是為了避免求解權向量的算法收斂到解區(qū)邊界的某點上。36幾個基本概念3.2感知準則函數(shù)37幾個基本概念解向量和解區(qū)的兩維示意圖解區(qū)里面的向量叫解向量；讓它線性可分的解不唯一；準則不同，落在這個解區(qū)中的解不同；但準則確定，解一般是唯一的。3.2感知準則函數(shù)感知準則出發(fā)點一旦判別函數(shù)的形式確定下來，不管它是線性的還是非線性的，剩下的問題就是如何確定它的系數(shù)。在模式識別中，系數(shù)確定的一個主要方法就是通過對已知樣本的訓練和學習來得到。感知器算法就是通過訓練樣本模式的迭代和學習，產(chǎn)生線性（或廣義線性）可分的模式判別函數(shù)。感知準則函數(shù)，是人工神經(jīng)網(wǎng)絡的雛形，最早的人工神經(jīng)網(wǎng)絡就是感知器神經(jīng)網(wǎng)絡。感知器準則求解過程，線性判別函數(shù)形式一但確定，通過樣本不斷試錯糾正迭代來求解更新參數(shù)w和w0的過程。給定一個w和w0的初始值，來一個樣本，如果這個參數(shù)結果不好，就進行修正，如果結果好，就保留，不斷這樣迭代，等所有樣本都可以正確劃分，保留這時的參數(shù)，就是最終要求解的參數(shù)。3.2感知準則函數(shù)感知器算法基本思想采用感知器算法(PerceptionApproach)能通過對訓練模式樣本集的“學習”得到判別函數(shù)的系數(shù)說明這里采用的算法不需要對各類別中模式的統(tǒng)計性質(zhì)做任何假設，因此稱為確定性的方法。3.2感知準則函數(shù)對于權向量w，如果某個樣本被錯誤分類，。我們可以用對所有錯分樣本的求和來表示對錯分樣本的懲罰，定義感知器準則函數(shù)：當且僅當函數(shù)取得最小值0時，求得最優(yōu)的w。可以用梯度下降法進行求解。3.2感知準則函數(shù)樣本線性可分滿足：其中，梯度下降算法3.2感知準則函數(shù)梯度下降算法梯度是一個向量，它的最重要性質(zhì)就是指出了函數(shù)f在其自變量y增加時最大增長率的方向。負梯度指出f的最陡下降方向利用這個性質(zhì)，可以設計一個迭代方案來尋找函數(shù)的最小值3.2感知準則函數(shù)討論若正確地選擇了準則函數(shù)J(w,x)，則當權向量w是一個解時，J達到極小值（J的梯度為零）。為了使權向量能較快地收斂于一個使函數(shù)J極小的解，C值的選擇是很重要的。若C值太小，則收斂太慢；若C值太大，則搜索可能過頭，引起發(fā)散。梯度下降算法3.2感知準則函數(shù)3.2感知準則函數(shù)感知器算法3.2感知準則函數(shù)感知器算法感知器算法實質(zhì)上是一種賞罰過程對正確分類的模式則“賞”，實際上是“不罰”，即權向量不變。對錯誤分類的模式則“罰”，使w(k)加上一個正比于Xk的分量。當用全部模式樣本訓練過一輪以后，只要有一個模式是判別錯誤的，則需要進行下一輪迭代，即用全部模式樣本再訓練一次。如此不斷反復直到全部模式樣本進行訓練都能得到正確的分類結果為止。3.2感知準則函數(shù)感知器算法的收斂性只要模式類別是線性可分的，就可以在有限的迭代步數(shù)里求出權向量。如果有一個樣本線性不可分，那么感知器算法就會一直迭代，無法收斂。這是它的局限性。3.2感知準則函數(shù)感知器算法采用感知器算法的多類模式的分類討論這個分類算法都是通過訓練樣本來確定判別函數(shù)的系數(shù)，并沒有考慮到測試樣本，但一個分類器的性能最終用未知的測試樣本來檢驗。要使一個分類器設計完善，必須采用有代表性的正確的訓練數(shù)據(jù)，它能夠合理反映模式數(shù)據(jù)的整體。如果訓練樣本中有噪聲樣本，就會影響分類的性能。局限性在于對噪聲數(shù)據(jù)敏感，解不夠魯棒。3.2感知準則函數(shù)采用感知器算法的多類模式的分類討論要獲得一個判別性能好的線性分類器，究竟需要多少訓練樣本？直觀上是越多越好，但實際上能收集到的樣本數(shù)目會受到客觀條件的限制；過多的訓練樣本在訓練階段會使計算機需要較長的運算時間；一般來說，合適的樣本數(shù)目可如下估計： 若k是模式的維數(shù)，令C=2(k+1)，則通常選用的訓練樣本數(shù)目約為C的10~20倍。3.2感知準則函數(shù)50三種梯度下降優(yōu)化框架批量梯度下降法（BatchGradientDescent,BGD）每次使用全部的訓練樣本來更新模型參數(shù)/學習；優(yōu)點：每次更新都會朝著正確的方向進行，最后能夠保證收斂于極值點；缺點：每次學習時間過長，并且如果訓練集很大以至于需要消耗大量的內(nèi)存，不能進行在線模型參數(shù)更新。3.2感知準則函數(shù)51隨機梯度下降法（StochasticGradientDescent,SGD）隨機梯度下降算法每次從訓練集中隨機選擇一個樣本來進行學習；優(yōu)點：每次只隨機選擇一個樣本來更新模型參數(shù)，因此每次的學習是非常快速的，并且可以進行在線更新；SGD波動帶來的好處，在類似盆地區(qū)域，即很多局部極小值點，那么這個波動的特點可能會使得優(yōu)化的方向從當前的局部極小值點調(diào)到另一個更好的局限極小值點，這樣便可能對于非凹函數(shù)，最終收斂于一個較好的局部極值點，甚至全局極值點。缺點：每次更新可能并不會按照正確的方向進行，因此會帶來優(yōu)化波動，使得迭代次數(shù)增多，即收斂速度變慢。3.2感知準則函數(shù)52小批量梯度下降法（Mini-batchGradientDescent,SGD）小批量梯度下降綜合了batch梯度下降與stochastic梯度下降，在每次更新速度與更新次數(shù)中間一個平衡，其每次更新從訓練集中隨機選擇k(k<m)個樣本進行學習；優(yōu)點：相對于隨機梯度下降，Mini-batch梯度下降降低了收斂波動性，即降低了參數(shù)更新的方差，使得更新更加穩(wěn)定；相對于批量梯度下降，其提高了每次學習的速度；MBGD不用擔心內(nèi)存瓶頸從而可以利用矩陣運算進行高效計算；3.2感知準則函數(shù)第三章線性和非線性判別分析3.1Fisher線性判別3.2感知準則函數(shù)3.3廣義線性判別分析3.4k近鄰3.5決策樹54對于非線性問題，線性判別函數(shù)難以正確分類，而且設計非線性判別函數(shù)比較復雜。此時，常用的方法是將原特征空間映射到一個高維空間，將低維空間中的非線性問題轉化為高維空間中的線性問題，從而降低模式分類的難度。3.3廣義線性判別分析例：如右圖，55對于非線性問題，線性判別函數(shù)難以正確分類，而且設計非線性判別函數(shù)比較復雜。此時，常用的方法是將原特征空間映射到一個高維空間，將低維空間中的非線性問題轉化為高維空間中的線性問題，從而降低模式分類的難度。3.3廣義線性判別分析例：如右圖，二次判別函數(shù)可以表達為563.3廣義線性判別分析廣義線性判別函數(shù)這樣一個非線性判別函數(shù)通過映射，變換成線性判別函數(shù)。原始的特征空間是非線性，但通過某種映射，在新的空間能保證是線性函數(shù)，原始空間的判別函數(shù)為廣義線性判別函數(shù)。判別函數(shù)的一般形式：3.3廣義線性判別分析第三章線性和非線性判別分析3.1Fisher線性判別3.2感知準則函數(shù)3.3廣義線性判別分析3.4k近鄰3.5決策樹近鄰法

近鄰法則是一種根據(jù)樣本提供的信息，繞開概率的估計而直接決策的技術，所以它也屬于非參數(shù)判別方法的一種。（沒有訓練過程）模式識別的基本方法有兩大類，一類是將特征空間劃分成決策域，這就要確定判別函數(shù)和分界面方程（線性判別函數(shù)）。而另一種方法則稱為模板匹配，即將待分類樣本與標準模板進行比較，看跟哪個模板匹配度更好些，從而確定待測試樣本的分類。近鄰法

線性判別函數(shù)是將特征空間劃分為決策域，并用判別函數(shù)或決策面方程表示決策域的方法。近鄰法則在原理上屬于模板匹配。它將訓練樣本集中的每個樣本都作為模板，用測試樣本與每個模板做比較，看與哪個模板最相似(即為近鄰)，就按最近似的模板的類別作為自己的類別。譬如A類有10個訓練樣本，因此有10個模板，B類有8個訓練樣本，就有8個模板。任何一個待測試樣本在分類時與這18個模板都算一算相似度，如最相似的那個近鄰是B類中的一個，就確定待測試樣本為B類，否則為A類。因此原理上說近鄰法是最簡單的。近鄰法

但是近鄰法有一個明顯的缺點:就是計算量大，存儲量大，要存儲的模板很多，每個測試樣本要對每個模板計算一次相似度，因此在模板數(shù)量很大時，計算量也很大的。

思想簡單，有一個如此明顯缺點的方法還有沒有存在的必要性呢？優(yōu)點:在模板數(shù)量很大時其錯誤率指標還是相當不錯的。該方法普適性比較好。常用來作為一個基準算法。

結論:這就是說近鄰法有存在的必要。最近鄰法則最近鄰法:將與測試樣本最近鄰樣本的類別作為決策的方法。對一個C類別問題，每類有Ni個樣本，i＝1，…，C，則第i類ωi的判別函數(shù)

其中表示是ωi類的第k個樣本。對于C類：決策規(guī)則為：如果則決策X∈ωj。

最近鄰法則

最近鄰法在原理上最直觀，方法上也十分簡單，只要對所有樣本(共N＝∑Ni)進行N次距離運算，然后以最小距離者的類別作決策。

公式中用‖·‖表示距離，其實這是一個象征性的表示，可以采用任何一種相似性的度量，一般采用歐氏距離為相似性度量的較多。但由于特征向量各個分量之間對應的物理意義很可能不一致，因此究竟采用何種相似性度量要看問題而定。

近鄰法則的錯誤率實際問題中，近鄰法的錯誤率是比較難算的，因為訓練樣本集的數(shù)量總是有限的，有時多一個少一個訓練樣本對測試樣本分類的結果影響很大。譬如圖中:(A3)

紅點表示A類訓練樣本，藍點表示B類訓練樣本綠點O表示待測樣本。假設以歐氏距離來衡量，O的最近鄰是A3，其次是B1，因此O應該屬于A類，但若A3被拿開，O就會被判為B類。這說明計算最近鄰法的錯誤率會有偶然性，也就是指與具體的訓練樣本集有關。計算錯誤率的偶然性會因訓練樣本數(shù)量的增大而減小。隨著訓練樣本的增加，準確率會有所提高。因此人們就利用訓練樣本數(shù)量增至極大，來對其性能進行評價。

近鄰法則的錯誤率最近鄰法則

最近鄰規(guī)則是次優(yōu)的方法，通常的錯誤率比最小可能錯誤率（即最小貝葉斯法則的錯誤率）要大。但在無限訓練樣本的情況下，這個錯誤率不會超過貝葉斯錯誤率的一倍。小于等于兩倍，錯誤率有上限的。當訓練樣本足夠多時：最近鄰法的錯誤率要高于貝葉斯錯誤率，可以證明以下關系式成立：

最近鄰法的漸近平均錯誤率的下、上界分別為貝葉斯錯誤率及

由于一般情況下

很小，因此上式又可粗略表示成

近鄰法則的錯誤率

因此可以說最近鄰法的漸近平均錯誤率在貝葉斯錯誤率的兩倍之內(nèi)。從這點說最近鄰法是優(yōu)良的，因此它是模式識別重要方法之一。近鄰法則的錯誤率

最近鄰方法最近的樣本可能受噪聲影響。最近鄰法可以擴展成找測試樣本的k個最近樣本作決策依據(jù)的方法。k近鄰基本規(guī)則是，在所有N個樣本中找到與測試樣本的k個最近鄰者，其中第i個類別所占個數(shù)為gi(X),i＝1，…，c，決策規(guī)則：如果

則決策X∈ωj

。K-近鄰法則k近鄰一般采用k為奇數(shù)，跟投票表決一樣，避免因兩種票數(shù)相等而難以決策。可以這樣理解:K近鄰算法從測試樣本點開始生長，不斷擴大區(qū)域，直到包含進k個訓練樣本點為止，并且把X歸為這最近的k個訓練樣本點中出現(xiàn)頻率最大的類別中。如圖為k=5的情況。K-近鄰法則

在N→∞的條件下，k-近鄰法的錯誤率要低于最近鄰法。從圖中也可看出，無論是最近鄰法，還是k-近鄰法，其錯誤率的上下界都是在一倍到兩倍貝葉斯決策方法的錯誤率范圍內(nèi)。不同k值時的錯誤率情況K-近鄰法則的錯誤率：K-近鄰法則最近鄰法和K近鄰法的共同優(yōu)點是簡單，而且結果比較好，但仍存在不少缺點：

(1)要求的計算機存儲容量和計算量相當大。

(2)沒有考慮到?jīng)Q策風險。

(3)以上的分析是建立在無窮多樣本的基礎上的，對于有限樣本的情況，缺乏理論上的分析。K-近鄰法則732.近鄰法數(shù)據(jù)：1）USPS手寫體2）UCI數(shù)據(jù)庫中sonar數(shù)據(jù)源3）UCI數(shù)據(jù)庫中Iris數(shù)據(jù)驗證算法：不進行降維，1）K近鄰方法分類；2）最近鄰方法分類；對比算法：fisher+K近鄰（最近鄰）作業(yè)形式：程序+大報告+上機課演示第二次大作業(yè)第三章線性和非線性判別分析3.1Fisher線性判別3.2感知準則函數(shù)3.3廣義線性判別分析3.4k近鄰3.5決策樹3.5.1決策樹分類介紹3.5.2ID33.5.3C4.5決策樹簡介決策樹：（適合離散屬性的分類問題）一種多級分類器，它采用分級的形式，綜合用多個決策規(guī)則，逐步把復雜的多類別分類問題轉化為若干個簡單的分類問題來解決n1n2n3n4n5t1t2t3t4t5t6t7多類

問題根節(jié)點：所有樣本集合葉子節(jié)點：分完類的樣本集合，每個集合屬于同一類別二叉決策樹二叉決策樹：除葉節(jié)點外，決策樹的每個節(jié)點ni都有且只有兩個子節(jié)點nil和nir。二叉決策樹把復雜的多類別分類問題轉化為多級兩類分類問題來解決。在每個節(jié)點ni，都把樣本集分成兩個子集。每個子集可能仍包含多類別的樣本，繼續(xù)分直至僅包含單類別樣本的葉節(jié)點n1n2n3n4t1t2t5x2≤5x1≤2x3≤4x2≤2ω1ω2ω3ω2ω3t3t4多類

問題簡介決策樹方法的起源是概念學習系統(tǒng)，然后發(fā)展到ID3（處理離散屬性）方法而為高潮，最后又演化為能處理連續(xù)屬性的C4.5。有名的決策樹方法還有CART和Assistant（處理缺失屬性的數(shù)據(jù)，比如互聯(lián)網(wǎng)數(shù)據(jù)）。是應用最廣的歸納推理算法之一一種逼近離散值目標函數(shù)的方法對噪聲數(shù)據(jù)有很好的健壯性且能學習析取表達式，之前的線性判別函數(shù)中的感知器函數(shù)對噪聲特別敏感，決策樹對噪聲魯棒性較好決策樹舉例決策樹樹的基礎知識樹的結構示意圖決策樹的表示法決策樹通過把實例（樣本）從根節(jié)點排列到某個葉子節(jié)點來分類實例，葉子節(jié)點即為實例所屬的分類。樹上的每一個節(jié)點說明了對實例的某個屬性的測試，并且該節(jié)點的每一個后繼分支對應于該屬性的一個可能值（二叉決策樹：是或否）例子類標示例天氣溫度濕度風力打網(wǎng)球1SunnyHotHighWeakNo2SunnyHotHighStrongNo3OvercastHotHighWeakYes4RainMildHighWeakYes5RainCoolNormalWeakYes6RainCoolNormalStrongNo7OvercastCoolNormalStrongYes8SunnyMildHighWeakNo9SunnyCoolNormalWeakYes10RainMildNormalWeakYes11SunnyMildNormalStrongYes12OvercastMildHighStrongYes13OvercastHotNormalWeakYes14RainMildHighStrongNo圖離散屬性：若干個確定的特征值14個訓練樣本，2分類問題，4個屬性表達式?jīng)Q策樹代表實例屬性值約束的合取的析取式。屬性之間的合取（且的關系），多種情況下的析取（或的關系）。從樹根到樹葉的每一條路徑對應一組屬性測試的合取，樹本身對應這些合取的析取。（基于規(guī)則的分類）決策樹學習的適用問題實例是由‘屬性-值’對表示的:如實例是用一系列固定的屬性（例如，Temperature）和它們的值（離散的值）（例如，Hot）來描述的目標函數(shù)具有離散的輸出值:決策樹給每個實例賦予一個布爾型的分類（例如，yes或no），如果是多分類，就是多個離散輸出。決策樹方法很容易擴展到學習有兩個以上輸出值的函數(shù)。一種更強有力的擴展算法允許學習具有實數(shù)值輸出的函數(shù)，比如C4.5.可能需要析取的描述訓練數(shù)據(jù)可以包含錯誤：決策樹學習對錯誤有很好的魯棒性，無論是訓練樣例所屬的分類錯誤還是描述這些樣例的屬性值錯誤。單個樣本存在錯誤，對整個決策樹的構造影響并不明顯。訓練數(shù)據(jù)可以包含缺少屬性值的實例:決策樹學習甚至可以在有未知屬性值的訓練樣例中使用（例如，僅有一部分訓練樣