91n在线中文字幕,无码久久一区二区三区

基本流程

決策樹（decision tree）是一類常見的機器學(xué)習(xí)方法。決策樹是一個預(yù)測模型；他代表的是對象屬性與對象值之間的一種映射關(guān)系。樹中每個節(jié)點表示某個對象，而每個分叉路徑則代表的某個可能的屬性值，而每個葉結(jié)點則對應(yīng)從根節(jié)點到該葉節(jié)點所經(jīng)歷的路徑所表示的對象的值。決策樹僅有單一輸出，若欲有復(fù)數(shù)輸出，可以建立獨立的決策樹以處理不同輸出。數(shù)據(jù)挖掘中決策樹是一種經(jīng)常要用到的技術(shù)，可以用于分析數(shù)據(jù)，同樣也可以用來作預(yù)測。

決策樹

決策樹的建立

輸入: 訓(xùn)練集 $D = \{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\}$ ;
屬性集: $A=\{a_1,a_2,...,a_d\} a_*$
偽代碼：

函數(shù) TreeGenerate(D,A)
生成節(jié)點node:
if D 中的樣本全屬于同一類別 C then
    將node標記為C類葉子節(jié)點；return
end if
if A = ? OR D 中樣本在 A 上取值相同 then
    將 node 標記為葉節(jié)點，其類別標記為 D 中樣本數(shù)最多的類；return
end if
從A中選則最優(yōu)劃分屬性a?;
for a* 的每一個值a*(v) do
    為node生成一個分支；令Dv表示D中在a*上取值為a*(v)的樣本子集；
    if Dv 為空 then
        將分支節(jié)點標記為葉節(jié)點，其類別標記為D中樣本最多的類；return
    else
        以Tree(Dv,A\{a*})為分支節(jié)點
    end if
end for

輸出：以node為根的一顆決策數(shù)

決策數(shù)的生成是一個遞歸的過程，在決策樹基本算法中有三種情況會導(dǎo)致遞歸返回：

當(dāng)前節(jié)點包含的樣本種類屬于同一類別，無需劃分
當(dāng)前樣本屬性集為空，或者所有樣本在所有屬性上的取值相同，無法劃分
當(dāng)前節(jié)點包含的樣本集合為空，不能劃分

劃分選擇

決策樹算法的關(guān)鍵在于如歌選擇最優(yōu)劃分屬性，隨著劃分的不斷進行，我們希望決策樹的分支節(jié)點所包含的樣本盡可能的屬于同一類別。

信息熵

熵的概念最早起源于物理學(xué)，用于度量一個熱力學(xué)系統(tǒng)的無序程度。在信息論里面，熵是對不確定性的測量。但是在信息世界，熵越高，則能傳輸越多的信息，熵越低，則意味著傳輸?shù)男畔⒃缴佟?br> 信息熵(information entropy)是度量樣本集合純度最常用的一種指標，假定當(dāng)前樣本集合 $D$ 中第 $k$ 類樣本所占的比例為 $p_k(k=1,2,...,|y|)$ ,則 $D$ 的信息熵定義為：
$Ent(D)= - \Sigma_{k=1}^{|y|}p_k log_2p_k$
$Ent(D)$ 的值越小，則 $D$ 的純度越高

信息增益與ID3算法

假定離散屬性 $a$ 有 $V$ 個可能的取值 $\{a^1,a^2,...,a^V\}$ ，若使用 $a$ 來對樣本集 $D$ 進行劃分，則會產(chǎn)生 $V$ 個分支節(jié)點，之中第 $v$ 個節(jié)點包含了 $D$ 中所有在屬性 $a$ 上取值為 $a^v$ 的樣本，記為 $D^v$ ，我們可以計算出 $D^v$ 的信息熵，在考慮到不同的分支節(jié)點包含的樣本數(shù)的不同，給分支節(jié)點賦予權(quán)重 $|D^v|/|D|$ ,
信息增益：
$Gain(D,a)=Ent(D)-\Sigma_1^V\frac{|D^v|}{|D|}Ent(D^v)$
$\frac{|D^v|}{|D|}Ent(D^v)$ 可記為 $Ent(a^v|a)$ 表示特征屬性 $a$ 的條件下樣本的條件熵,信息增益越大，則以為則使用屬性 $a$ 來進行劃分所獲得的純度越高，因此可以用來作為屬性劃分的依據(jù)
$a_*=argmin Gain(D,a) ,a \in A$
這也是ID3(Iterative Dichotomiser 3)算法的原理。
決策樹ID3算法請參考：傳送門

信息增益率與C4.5算法

C4.5決策樹算法不直接使用信息增益，而是使用信息增益率來選擇最優(yōu)劃分屬性。
$Gain_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$
其中
$IV(a)=-\Sigma_{v=1}^V\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}$
$IV(a)$ 稱為屬性a的固有值，屬性a的可能取值數(shù)目越多，則 $IV(a)$ 的值通常會越大。增益率準則對取值數(shù)目較少的屬性有所偏好。
決策樹C4.5算法：傳送門

基尼指數(shù)與分類回歸樹

CART樹(Classification and Regression Tree)使用基尼指數(shù)來選擇屬性的劃分，通過基尼值來度量數(shù)據(jù)集的純度
基尼值：
$Gini(D)=\Sigma_{k=1}^{|y|}\Sigma_{k^{'}\neq k}p_kp_k{'}=1-\Sigma_{k=1}^{|y|}p_k^2$
$Gini(D)$ 反映了從數(shù)據(jù)集 $D$ 中取出兩個樣本，不為同一種類的概率，因此 $Gini(D)$ 越小，數(shù)據(jù)集的純度越高。
基尼指數(shù)：
$Gini_index(D,a)=\Sigma_{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)$
于是我們在候選屬性集合 $A$ 中選擇使那個劃分后基尼指數(shù)最小的那個屬性作為最優(yōu)劃分屬性。
CRAT算法：傳送門

過擬合處理

在決策樹學(xué)習(xí)中，為了盡可能正確分類訓(xùn)練樣本，結(jié)點劃分過程將不斷重復(fù)，有時會造成決策樹分支過多，導(dǎo)致過擬合，因此可以通過主動去掉一些分支來降低過擬合的風(fēng)險。
剪枝的基本策略有：預(yù)剪枝和后剪枝

預(yù)剪枝

預(yù)剪枝是在決策樹生成的過程中，對每個結(jié)點在劃分前先進行預(yù)估，若當(dāng)前結(jié)點的劃分不能使決策樹泛化性能提升，則停止劃分并將當(dāng)前結(jié)點標記為葉節(jié)點。

后剪枝

后剪枝是先從訓(xùn)練集中生成一顆完整的決策樹，然后自底向上的對非葉子結(jié)點進行考察，若將改結(jié)點對應(yīng)的子樹替換為葉子結(jié)點能提高泛化能力，則進行替換。

連續(xù)值缺失值處理

連續(xù)值處理

由于連續(xù)屬性的可能取值不再有限，因此不能直接根據(jù)連續(xù)屬性的可能取值進行劃分。我們可以使用離散化技術(shù)對其進行處理。
二分法：
給定樣本集 $D$ ，和連續(xù)屬性 $a$ ， $a$ 在 $D$ 上出現(xiàn)了n個不同的取值，
將其排序 $\{a^1,a^2,...,a^n\}$ ，然后基于劃分點 $t$ 將樣本劃分為 $D_t^-$ 和 $D_t^+$ ， $D_t^-$ 包括在屬性 $a$ 上取值小于 $t$ 的樣本， $D_t^+$ 反之。通常將劃分點設(shè)為該屬性在訓(xùn)練集中出現(xiàn)額不大于中位點的最大值從而是的最終決策樹使用的劃分點都在訓(xùn)練集中出現(xiàn)過。
eg:
$T_a=\{\frac{a^i+a^{i+1}}{2}|1\le i\le n-1\}$
$Gain(D,a)=max\{Gain(D,a,t)|t \in T_a\}$
$Gain(D,a)=max\{Ent(D) - \Sigma_{\lambda\in \{+,-\}} \frac{|D_t^{\lambda}|}{|D|}Ent(D_t^{\lambda})|t \in T_a\}$
$Gain(D,a,t)$ 是樣本 $D$ 基于劃分點 $t$ 的信息增益，選擇使得 $Gain(D,a,t)$ 最大化的劃分點。

缺失值處理

現(xiàn)實任務(wù)中常常會遇到不完整的樣本，也就是樣本中的某些屬性值缺失的情況，最簡單的方法是直接去除缺失的數(shù)據(jù)，但是這是對數(shù)據(jù)信息的極大浪費，我們可以考慮下利用有缺失屬性值的樣本來進行學(xué)習(xí)。
需解決的問題：

在屬性值缺失的情況下進行劃分屬性的選擇
給定劃分屬性，若樣本在該屬性上的值缺失，如何進行劃分

給定訓(xùn)練集 $D$ ,屬性集 $a$ ,令 $\overline{D}$ 表示 $D$ 中在屬性 $a$ 上沒有缺失值的樣本子集

對于問題一，根據(jù) $\overline{D}$ 來判斷屬性 $a$ 的優(yōu)劣，屬性 $a$ 的取值 $\{a^1,...,a^V\}$ ，令 $\overline{D}^v$ 表示 $\overline{D}$ 在 $a$ 上取值為 $v$ 的樣本子集， $\overline{D}_k$ 表示 $\overline{D}$ 中屬于第 $k，(k=1,2,3...,|y|)$ 類的樣本子集
$\overline{D}=\cup_{k=1}^{|y|}\overline{D}_k$ , $\overline{D}=\cup_{v=1}^{V}\overline{D}^v$ ,假定為每一個樣本賦予一個權(quán)重 $w_x$
設(shè)

$\rho ={ \Sigma_{x \in \overline{D} } w_x } / { \Sigma_{x \in D } w_x }$
$\overline{p}_k ={ \Sigma_{x \in \overline{D}_k } w_x } / { \Sigma_{x \in D } w_x }$
$\overline{r}_v ={ \Sigma_{x \in \overline{D}^v } w_x } / { \Sigma_{x \in D } w_x }$

$\rho$ 表示屬性 $a$ 上無缺樣本所占比例， $\overline{p}_k$ 表示無缺樣本中第 $k$ 類所占的比例, $\overline{r}_v$ 表示無缺樣本中屬性 $a$ 上取值為 $a^v$ 的所占的比例。
推廣到信息增益公式上：

$Gain(D,a)=\rho * Gain(\overline{D},a)$
$Gain(D,a)=\rho *(Ent(\overline{D})-\Sigma_{v=1}^V \overline{r}_v Ent(\overline{D}^v))$
其中 $Ent(\overline{D}) = -\Sigma_{k=1}^{|y|} \overline{p}_k log_2\overline{p}_k$

對于問題二，樣本 $x$ 在屬性 $a$ 上的取值缺失，則將 $x$ 劃分到所有額子結(jié)點中，將權(quán)值變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Coverline%7Br%7D_v%20*%20w_x" alt="\overline{r}_v * w_x" mathimg="1">,意思i將同一個樣本以不同的概率劃入到同的子結(jié)點中。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

【算法】決策樹

【算法】決策樹

基本流程

決策樹的建立

劃分選擇