決策樹

1.

原理

1.1

模型簡介

決策樹是一種基本的回歸和分類算法。在分類問題中，可以認(rèn)為是一系列

if-then

規(guī)則的幾何。決策樹學(xué)通常包括三個步驟：特征選擇，決策樹的生成，

決策樹的修剪。

定義：決策樹由結(jié)點和有向邊組成，內(nèi)部節(jié)點表示一個特征和屬性，葉子

結(jié)點表示一個類。

性質(zhì)：決策樹路徑(或者對應(yīng)的

if-then

規(guī)則)具有互斥且完備性：每一個

實例都被一條路徑或規(guī)則所覆蓋，而且只被這條路徑或規(guī)則所覆蓋。

決策樹學(xué)習(xí)：能夠正確對數(shù)據(jù)集進(jìn)行分類的決策樹可能有多個，也可能一

個也沒有，我們的目的是找到一個與訓(xùn)練數(shù)據(jù)集矛盾較小的，同時具有很好泛

化能力的決策樹。

特征選擇：一種是在決策樹學(xué)習(xí)開始的時候，對特征進(jìn)行選擇，只留下對

訓(xùn)練數(shù)據(jù)有足夠分類能力的特征，一種是在學(xué)習(xí)過程中對訓(xùn)練數(shù)據(jù)分割成自己

的時候，選擇最優(yōu)的特征進(jìn)行分割。

決策樹生成：一般這是一個遞歸的規(guī)程。

決策樹的剪枝：提高決策樹的泛化能力。

1.2

特征選擇

特征選擇的準(zhǔn)則一般是：信息增益和信息增益比

1.2.1

信息增益

a.

信息增益：

信息增益大的特征具有更強(qiáng)的分類能力，

即選擇信息增益值大的特

征作為最優(yōu)特征。

b.

信息熵：表示變量的不確定性(在得知特征

X

的信息時，使得

Y

的信息不確

定性減少的程度)

，熵越大，變量的不確定性越大。設(shè)

X

是一個取有限值的離散型

隨機(jī)變量，其概率分布為：

(

)

i

i

p

X

x

p

?

?

則隨機(jī)變量

X

的熵定義為：

總結(jié)

以上是生活随笔為你收集整理的二叉树剪枝_决策树,生成剪枝,CART算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。