當(dāng)前位置：首頁 > news >正文

perl網(wǎng)站開發(fā)西安網(wǎng)站搭建

news 2025/7/7 13:33:26

perl網(wǎng)站開發(fā),西安網(wǎng)站搭建,阿里云認(rèn)證網(wǎng)站建設(shè),國際學(xué)校網(wǎng)站如何建設(shè)目錄 1. 什么是決策樹? 2. 決策樹的原理 2.1 如何構(gòu)建決策樹？ 2.2 構(gòu)建決策樹的數(shù)據(jù)算法 2.2.1 信息熵 2.2.2 ID3算法 2.2.2.1 信息的定義 2.2.2.2 信息增益 2.2.2.3 ID3算法舉例 2.2.2.4 ID3算法優(yōu)缺點 2.2.3 C4.5算法 2.2.3.1 C4.5算法舉例 2.2.4 CART算法 2.2.4…

目錄

1. 什么是決策樹?

2. 決策樹的原理

2.1 如何構(gòu)建決策樹？

2.2?構(gòu)建決策樹的數(shù)據(jù)算法

2.2.1 信息熵

2.2.2 ID3算法

2.2.2.1?信息的定義

2.2.2.2 信息增益

2.2.2.3?ID3算法舉例

2.2.2.4?ID3算法優(yōu)缺點

2.2.3 C4.5算法

2.2.3.1?C4.5算法舉例

2.2.4 CART算法

2.2.4.1 Gini指數(shù)（基尼指數(shù)）

2.2.4.2?Cart算法相關(guān)公式

2.2.4.3 Cart算法舉例

3. 未完待續(xù)。。。

4. 本文涉及的代碼

1. 什么是決策樹?

決策樹分類的思想類似于找對象。

想象一個女孩的母親要給這個女孩介紹男朋友，于是有了下面的對話：

女孩決定是否見男孩的一個過程，就像一個樹形結(jié)構(gòu)，只不過是反正的樹，數(shù)學(xué)上或者機器學(xué)習(xí)里的樹，根在最上方

最上方的為樹的根節(jié)點，下面的都是子節(jié)點

?像下圖的橙色的部分，下面在沒有往下的結(jié)點的叫葉子節(jié)點

如果一顆樹每個節(jié)點下面最多只有兩個節(jié)點就屬于二叉樹?

下圖的就是一個非二叉樹( 到收入下面有三個節(jié)點)

上圖完整表達(dá)了這個女孩決定是否見一個約會對象的策略，

其中綠色節(jié)點表示判斷條件，

橙色節(jié)點表示決策結(jié)果，

箭頭表示在一個判斷條件在不同情況下的決策路徑，

圖中紅色箭頭表示了上面例子中女孩的決策過程。
這幅圖基本可以算是一顆決策樹，說它“基本可以算”是因為圖中的判定條件沒有量化，

如收入高中低等等，還不能算是嚴(yán)格意義上的決策樹，

如果將所有條件量化，則就變成真正的決策樹了。
有了上面直觀的認(rèn)識，我們可以正式定義決策樹了：

????????決策樹(decision tree)是一個樹結(jié)構(gòu)（可以是二叉樹或非二叉樹)。

其每個非葉節(jié)點表示一個特征屬性上的測試，每個分支代表這個特征屬性在某個值域上的輸出，而每個葉節(jié)點存放一個類別。

使用決策樹進(jìn)行決策的過程就是從根節(jié)點開始，測試待分類項中相應(yīng)的特征屬性，并按照其值選擇輸出分支，直到到達(dá)葉子節(jié)
點，將葉子節(jié)點存放的類別作為決策結(jié)果

????????可以看到，決策樹的決策過程非常直觀，容易被人理解。目前決策樹已經(jīng)成功運用于醫(yī)學(xué)、制造產(chǎn)業(yè)、天文學(xué)、分支
生物學(xué)以及商業(yè)等諸多領(lǐng)域。決策樹的主要優(yōu)勢就在于數(shù)據(jù)形式非常容易理解。

????????決策樹算法能夠讀取數(shù)據(jù)集合，構(gòu)建類似于上面的決策樹，決策樹很多任務(wù)都是為了數(shù)據(jù)中所蘊含的知識信息，因此決策樹可以使用不熟悉的數(shù)據(jù)集合，并從中提取出一系列規(guī)則，機器學(xué)習(xí)算法最終將使用這些機器從數(shù)據(jù)集中創(chuàng)造的規(guī)則。專家系統(tǒng)中經(jīng)常使用決策樹，而且決策樹給出結(jié)果往往可以匹敵在當(dāng)前領(lǐng)域具有幾十年工作經(jīng)驗的人類專家

2. 決策樹的原理

2.1 如何構(gòu)建決策樹？

首先，例如上方的圖，我們可以分析到，我們要先選擇判斷條件，

例如有些女孩找男朋友的第一個條件考慮年齡而有的考慮收入有的還考慮長相等等，所以這就是構(gòu)造決策樹的第一個關(guān)鍵的點：判斷條件的順序，

有了判斷條件之后，怎么判斷這個節(jié)點的分裂，例如，年齡這個判斷條件，是按照30歲分還是按照什么分，符合這個條件是一個節(jié)點，不符合這個判斷條件的是另外一個節(jié)點，這就是構(gòu)造決策樹的第二個關(guān)鍵的點：節(jié)點分裂的界限或者說節(jié)點分裂的定義和分類

????????構(gòu)造決策樹關(guān)鍵步驟是分裂屬性，所謂分裂屬性就是在某個節(jié)點處，按照某一特征屬性的不同劃分構(gòu)造不同的分支，其目標(biāo)是讓各個分裂子集盡可能的“純”，盡可能“純” 就是盡量讓一個分裂子集中待分類項屬于同一類別

2.2?構(gòu)建決策樹的數(shù)據(jù)算法

2.2.1 信息熵

有了剛說的兩個關(guān)鍵點，對于這個兩個關(guān)鍵點的選擇就有點困難，所以需要具體的算法來做

建決策樹的數(shù)據(jù)算法有很多

ID3算法

C4.5算法

CART算法

.....

等等

這里面就牽扯了信息論中的信息熵有關(guān)信息熵可參考（可以點開全部回答，然后搜索閱讀，或者自行查看）

信息熵是什么？ - 知乎原創(chuàng)文章，一家之言。轉(zhuǎn)載請注明出處。個人公眾號：follow_bobo機器學(xué)習(xí)入門：重要的概念---信息熵（Shan…https://www.zhihu.com/question/22178202/answer/265757803

信息熵的數(shù)學(xué)公式：

2.2.2 ID3算法

ID3算法算的是信息增益

2.2.2.1?信息的定義

熵定義為信息的期望值，在明確這個概念之前，我們必須知道信息的定義，如果待分類的事務(wù)劃分在多個分類之中，則符合X的信息定義為：
$l(x_i)=-log_2p(x_i)$

其中p(x)是選擇該分類的概率

為了計算熵，我們需要計算所有類別所有可能的信息期望值，通過下面的公式得到：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? $H=-\sum ^n_{i=1}p(x_i)log_2p(x_i)$

其中n 是分類的數(shù)目

在決策樹當(dāng)中，設(shè)D為用類別對訓(xùn)練元組進(jìn)行的劃分，則D的熵(entropy)表示為：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? $info(D)=-\sum_{i=1}^{m}p_ilog_2(p_i)$

其中pi 表示第i個類別在整個訓(xùn)練元組出現(xiàn)的概率，可以用屬于此類別元素的數(shù)量除以訓(xùn)練元組元素總數(shù)作為估計。

熵的實際意義表示是D中元組的類標(biāo)號所需要的平均信息量

現(xiàn)在我們假設(shè)將訓(xùn)練元組D按屬性A進(jìn)行劃分，則A對D劃分的期望信息為：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? $info_A(D)=\sum_{j=1}^{v}\frac{|D_j|}{D}info(D_j)$

2.2.2.2 信息增益

ID3算法利用信息增益來決定優(yōu)先使用哪個特征進(jìn)行分裂

先用沒有進(jìn)行任何屬性分類的時候，計算一個信息熵

再選其中的某一個特征進(jìn)行分裂構(gòu)造決策樹，再計算一個信息熵，具體用哪個特征來計算，要看哪個特征計算出來的信息熵大，就用哪個，因為這樣算出來的值越大相減之后就消除了原來數(shù)據(jù)里面最大的不確定性

這兩個信息熵之間會有一個差值，這兩個信息熵之差，得到的值叫做信息增益

2.2.2.3?ID3算法舉例

ID3算法就是在每次需要分裂時，計算每個屬性的增益率，然后選擇增益率最大的屬性進(jìn)行分裂，

如下圖假設(shè)訓(xùn)練集合包含10條數(shù)據(jù)，預(yù)測一下，社交網(wǎng)站上的賬號是否真實的賬號

根據(jù)日志密度，好友密度，是否使用真是頭像等（這些都為特征）來預(yù)測

代表的含義： s 小，m中等，l 大

先完成構(gòu)建決策樹其中一個關(guān)鍵點：首先用那個特征進(jìn)行分裂

計算思路：

1?? 先計算沒有使用任何特征對賬號是否真實的計算的信息熵

2?? 再算隨便使用一個特征對賬號是否真實的計算的信息熵

代碼如下：（使用 jupyter notebook）
import pandas as pd
import numpy as np
# 計算圖中的信息熵，確定一個分類的特征
# D 就是我們的原始數(shù)據(jù)
# 先計算未使用任何特征的進(jìn)行分類的信息熵（所以只需關(guān)心賬號是否真實這一列）
# 賬號是否真實： 有兩種情況，分別為 yes no, yes數(shù)量為7(概率為0.7)，no的數(shù)量為3(概率為0.3)
# 根據(jù)信息熵公式：
info_D = -(0.7 * np.log2(0.7) + 0.3 * np.log2(0.3))
info_D
# 0.8812908992306927
使用日志密度對賬號是否真實的信息熵?
使用公式 ?
$info_A(D)=\sum_{j=1}^{v}\frac{|D_j|}{D}info(D_j)$
# 使用 日志密度 對賬號是否真實的信息熵 使用公式
# j 就是 3（因為日志密度有三種情況，s,l,m）
# s 三個（0.3），對應(yīng)賬號是否真實列，2個no, 1個yes
# l 三個（0.3）, 對應(yīng)賬號是否真實列，0個no, 3個yes
# m 四個（0.4）, 對應(yīng)賬號是否真實列，1個no, 3個yes
# s情況中對日志密度劃分的信息熵 = s 的 概率 ??  s 中對賬號是否真實的信息熵 = 0.3 * ((-1/3) * np.log2(1/2) + (-2/3) * np.log2(2/3))
# 同理 l  = 0.3 * (-1 * log2(1))
# 同理 m  = 
info_D_Log = 0.3 * ((-1/3) * np.log2(1/3) + (-2/3) * np.log2(2/3)) + 0.3 * (-1 * np.log2(1)) + 0.4 * ((-1/4) * np.log2(1/4) + (-3/4) * np.log2(3/4))
info_D_Log
# 使用 日志密度 進(jìn)行劃分的信息增益
info_D - info_D_Log
# 0.2812908992306927
# 使用 好友密度 對賬號是否真實的信息熵
# s 4個（0.4），對應(yīng)賬號是否真實列，3個no, 1個yes
# m 4個（0.4）, 對應(yīng)賬號是否真實列，0個no, 4個yes
# l 2個（0.2）, 對應(yīng)賬號是否真實列，0個no, 2個yes
info_D_F = 0.4 * ((-3/4) * np.log2(3/4) + (-1/4) * np.log2(1/4)) + 0 + 0
info_D_F
# 0.32451124978365314
# 使用 好友密度 進(jìn)行劃分的信息增益
info_D - info_D_F
# 0.5567796494470396
# 使用 是否使用真實頭像 對賬號是否真實的信息熵
# no 5個  2個no,3個yes 
# yes  5個 1個no,4個yes
info_D_H = 0.5 * ((-2/5) * np.log2(2/5) + (-3/5) * np.log2(3/5)) + 0.5 * ((-1/5) * np.log2(1/5) + (-4/5) * np.log2(4/5))
info_D_H
# 0.8464393446710154
# 使用 是否使用真實頭像 進(jìn)行劃分的信息增益
info_D - info_D_H
# 0.034851554559677256
根據(jù)上述的運算結(jié)果，可以看到，使用好友密度進(jìn)行劃分的信息增益的值最大，所以我們就用好友密度這個特征來構(gòu)建決策樹

再完成構(gòu)建決策樹另外一個關(guān)鍵點：首先用那個特征進(jìn)行分裂節(jié)點分裂的界限或者說節(jié)點分裂的定義和分類，而這些我們不需要關(guān)心，ID3算法會幫我們做好，只要能確定出來用哪個特征即可

分裂屬性分為三種不同的情況：

屬性是離散值且不要求生成二叉決策樹。此時用屬性的每一個劃分作為一個分支。
屬性是離散值且要求生成二叉決策樹。此時使用屬性劃分的一個子集進(jìn)行測試，按照“屬于此子集”和“不屬于此子集”分成兩個分支。
屬性是連續(xù)值。此時確定一個值作為分裂點split_point,
?按照>split_point和<=split_points生成兩個分支。

離散值即例子中的 s,m,l,這種就是有三個劃分，而連續(xù)值類似年齡這種連續(xù)值，29，30，31等

2.2.2.4?ID3算法優(yōu)缺點

優(yōu)點：簡單、時間復(fù)雜度、時間復(fù)雜度都不高
缺點：數(shù)據(jù)中大量的離散型的數(shù)據(jù)，會對分裂造成誤差

2.2.3 C4.5算法

因為ID3算法在對于離散型特征的處理不好，引入C4.5算法

C4.5算法，計算的是信息增益率

計算步驟：

先計算信息增益
再除以這個特征本身的信息熵

2.2.3.1?C4.5算法舉例

信息增益，上面ID3算法已經(jīng)計算出來，可以直接使用，代碼如下

2.2.4 CART算法

2.2.4.1 Gini指數(shù)（基尼指數(shù)）

? ? ? ? 由上面的內(nèi)容我們已經(jīng)知道，決策樹的核心就是尋找純凈的劃分，因此引入了純度的概念。在屬性選擇上，我們是通過統(tǒng)計“不純度”來做判斷的，ID3 是基于信息增益做判斷，C4.5 在 ID3 的基礎(chǔ)上做了改進(jìn)，提出了信息增益率的概念。實際上 CART 分類樹與 C4.5 算法類似，只是屬性選擇的指標(biāo)采用的是基尼指數(shù)。

????????基尼指數(shù)本身反應(yīng)了樣本的不確定度。當(dāng)基尼系數(shù)越小的時候，說明樣本之間的差異性小，不確定程度低。分類的過程本身是一個不確定度降低的過程，即純度的提升過程。所以 CART 算法在構(gòu)造分類樹的時候，會選擇基尼系數(shù)最小的屬性作為屬性的劃分。

? ? ? ? 在決策樹Cart算法中用Gini指數(shù)來衡量數(shù)據(jù)的不純度或者不確定性

2.2.4.2?Cart算法相關(guān)公式

$Gini(D)=1-\sum_{i}p_i^2$ ? ?在分類問題中，樣本屬于第 i 類的概率為 $p_i$

$Gini(D,a)=\sum_{v}\frac{|D_v|}{D}Gini(D_v)$ ? 經(jīng)過特征a分割之后集合D的不確定性，基尼指數(shù)越大，不確定性越大，因此我們需要尋找基尼指數(shù)越小的特征作為節(jié)點

2.2.4.3 Cart算法舉例

3. 本文涉及的代碼

https://download.csdn.net/download/wei18791957243/88660903https://download.csdn.net/download/wei18791957243/88660903https://download.csdn.net/download/wei18791957243/88660904https://download.csdn.net/download/wei18791957243/88660904

https://download.csdn.net/download/wei18791957243/88664136https://download.csdn.net/download/wei18791957243/88664136