決策樹之ID3算法及其Python實現(xiàn)

決策樹之ID3算法及其Python實現(xiàn)

創(chuàng)新互聯(lián)公司專業(yè)為企業(yè)提供清遠(yuǎn)網(wǎng)站建設(shè)、清遠(yuǎn)做網(wǎng)站、清遠(yuǎn)網(wǎng)站設(shè)計、清遠(yuǎn)網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計與制作、清遠(yuǎn)企業(yè)網(wǎng)站模板建站服務(wù)，10年清遠(yuǎn)做網(wǎng)站經(jīng)驗，不只是建網(wǎng)站，更提供有價值的思路和整體網(wǎng)絡(luò)服務(wù)。

1. 決策樹背景知識

??決策樹是數(shù)據(jù)挖掘中最重要且最常用的方法之一，主要應(yīng)用于數(shù)據(jù)挖掘中的分類和預(yù)測。決策樹是知識的一種呈現(xiàn)方式，決策樹中從頂點到每個結(jié)點的路徑都是一條分類規(guī)則。決策樹算法最先基于信息論發(fā)展起來，經(jīng)過幾十年發(fā)展，目前常用的算法有：ID3、C4.5、CART算法等。

2. 決策樹一般構(gòu)建過程

??構(gòu)建決策樹是一個自頂向下的過程。樹的生長過程是一個不斷把數(shù)據(jù)進(jìn)行切分細(xì)分的過程，每一次切分都會產(chǎn)生一個數(shù)據(jù)子集對應(yīng)的節(jié)點。從包含所有數(shù)據(jù)的根節(jié)點開始，根據(jù)選取分裂屬性的屬性值把訓(xùn)練集劃分成不同的數(shù)據(jù)子集，生成由每個訓(xùn)練數(shù)據(jù)子集對應(yīng)新的非葉子節(jié)點。對生成的非葉子節(jié)點再重復(fù)以上過程，直到滿足特定的終止條件，停止對數(shù)據(jù)子集劃分，生成數(shù)據(jù)子集對應(yīng)的葉子節(jié)點，即所需類別。測試集在決策樹構(gòu)建完成后檢驗其性能。如果性能不達(dá)標(biāo)，我們需要對決策樹算法進(jìn)行改善，直到達(dá)到預(yù)期的性能指標(biāo)。

??注：分裂屬性的選取是決策樹生產(chǎn)過程中的關(guān)鍵，它決定了生成的決策樹的性能、結(jié)構(gòu)。分裂屬性選擇的評判標(biāo)準(zhǔn)是決策樹算法之間的根本區(qū)別。

3. ID3算法分裂屬性的選擇——信息增益

??屬性的選擇是決策樹算法中的核心。是對決策樹的結(jié)構(gòu)、性能起到?jīng)Q定性的作用。ID3算法基于信息增益的分裂屬性選擇。基于信息增益的屬性選擇是指以信息熵的下降速度作為選擇屬性的方法。它以的信息論為基礎(chǔ)，選擇具有最高信息增益的屬性作為當(dāng)前節(jié)點的分裂屬性。選擇該屬性作為分裂屬性后，使得分裂后的樣本的信息量最大，不確定性最小，即熵最小。

??信息增益的定義為變化前后熵的差值，而熵的定義為信息的期望值，因此在了解熵和信息增益之前，我們需要了解信息的定義。

??信息：分類標(biāo)簽xi 在樣本集 S 中出現(xiàn)的頻率記為 p(xi)，則 xi 的信息定義為：?log2p(xi) 。

??分裂之前樣本集的熵：E(S)=?∑Ni=1p(xi)log2p(xi)，其中 N 為分類標(biāo)簽的個數(shù)。

??通過屬性A分裂之后樣本集的熵：EA(S)=?∑mj=1|Sj||S|E(Sj)，其中 m 代表原始樣本集通過屬性A的屬性值劃分為 m 個子樣本集，|Sj| 表示第j個子樣本集中樣本數(shù)量，|S| 表示分裂之前數(shù)據(jù)集中樣本總數(shù)量。

??通過屬性A分裂之后樣本集的信息增益：InfoGain(S,A)=E(S)?EA(S)

??注：分裂屬性的選擇標(biāo)準(zhǔn)為：分裂前后信息增益越大越好，即分裂后的熵越小越好。

4. ID3算法

??ID3算法是一種基于信息增益屬性選擇的決策樹學(xué)習(xí)方法。核心思想是：通過計算屬性的信息增益來選擇決策樹各級節(jié)點上的分裂屬性，使得在每一個非葉子節(jié)點進(jìn)行測試時，獲得關(guān)于被測試樣本最大的類別信息。基本方法是：計算所有的屬性，選擇信息增益最大的屬性分裂產(chǎn)生決策樹節(jié)點，基于該屬性的不同屬性值建立各分支，再對各分支的子集遞歸調(diào)用該方法建立子節(jié)點的分支，直到所有子集僅包括同一類別或沒有可分裂的屬性為止。由此得到一棵決策樹，可用來對新樣本數(shù)據(jù)進(jìn)行分類。

ID3算法流程：

(1) 創(chuàng)建一個初始節(jié)點。如果該節(jié)點中的樣本都在同一類別，則算法終止，把該節(jié)點標(biāo)記為葉節(jié)點，并用該類別標(biāo)記。

(2) 否則，依據(jù)算法選取信息增益最大的屬性，該屬性作為該節(jié)點的分裂屬性。

(3) 對該分裂屬性中的每一個值，延伸相應(yīng)的一個分支，并依據(jù)屬性值劃分樣本。

(4) 使用同樣的過程，自頂向下的遞歸，直到滿足下面三個條件中的一個時就停止遞歸。

??A、待分裂節(jié)點的所有樣本同屬于一類。

??B、訓(xùn)練樣本集中所有樣本均完成分類。

??C、所有屬性均被作為分裂屬性執(zhí)行一次。若此時，葉子結(jié)點中仍有屬于不同類別的樣本時，選取葉子結(jié)點中包含樣本最多的類別，作為該葉子結(jié)點的分類。

ID3算法優(yōu)缺點分析

優(yōu)點：構(gòu)建決策樹的速度比較快，算法實現(xiàn)簡單，生成的規(guī)則容易理解。

缺點：在屬性選擇時，傾向于選擇那些擁有多個屬性值的屬性作為分裂屬性，而這些屬性不一定是最佳分裂屬性；不能處理屬性值連續(xù)的屬性；無修剪過程，無法對決策樹進(jìn)行優(yōu)化，生成的決策樹可能存在過度擬合的情況。

python中的sklearn中決策樹使用的是哪一種算法

sklearn中決策樹分為DecisionTreeClassifier和DecisionTreeRegressor，所以用的算法是CART算法，也就是分類與回歸樹算法(classification and regression tree,CART)，劃分標(biāo)準(zhǔn)默認(rèn)使用的也是Gini，ID3和C4.5用的是信息熵，為何要設(shè)置成ID3或者C4.5呢

使用python+sklearn的決策樹方法預(yù)測是否有信用風(fēng)險

import numpy as np11

import pandas as pd11

names=("Balance,Duration,History,Purpose,Credit amount,Savings,Employment,instPercent,sexMarried,Guarantors,Residence duration,Assets,Age,concCredit,Apartment,Credits,Occupation,Dependents,hasPhone,Foreign,lable").split(',')11

data=pd.read_csv("Desktop/sunshengyun/data/german/german.data",sep='\s+',names=names)11

data.head()11

Balance

Duration

History

Purpose

Credit amount

Savings

Employment

instPercent

sexMarried

Guarantors

…

Assets

Age

concCredit

Apartment

Credits

Occupation

Dependents

hasPhone

Foreign

lable

A11 6 A34 A43 1169 A65 A75 4 A93 A101 … A121 67 A143 A152 2 A173 1 A192 A201 1

1

A12 48 A32 A43 5951 A61 A73 2 A92 A101 … A121 22 A143 A152 1 A173 1 A191 A201 2

2

A14 12 A34 A46 2096 A61 A74 2 A93 A101 … A121 49 A143 A152 1 A172 2 A191 A201 1

3

A11 42 A32 A42 7882 A61 A74 2 A93 A103 … A122 45 A143 A153 1 A173 2 A191 A201 1

4

A11 24 A33 A40 4870 A61 A73 3 A93 A101 … A124 53 A143 A153 2 A173 2 A191 A201 2

5 rows × 21 columns

data.Balance.unique()11

array([‘A11’, ‘A12’, ‘A14’, ‘A13’], dtype=object)data.count()11

Balance 1000 Duration 1000 History 1000 Purpose 1000 Credit amount 1000 Savings 1000 Employment 1000 instPercent 1000 sexMarried 1000 Guarantors 1000 Residence duration 1000 Assets 1000 Age 1000 concCredit 1000 Apartment 1000 Credits 1000 Occupation 1000 Dependents 1000 hasPhone 1000 Foreign 1000 lable 1000 dtype: int64#部分變量描述性統(tǒng)計分析

data.describe()1212

Duration

Credit amount

instPercent

Residence duration

Age

Credits

Dependents

lable

count

1000.000000 1000.000000 1000.000000 1000.000000 1000.000000 1000.000000 1000.000000 1000.000000

mean

20.903000 3271.258000 2.973000 2.845000 35.546000 1.407000 1.155000 1.300000

std

12.058814 2822.736876 1.118715 1.103718 11.375469 0.577654 0.362086 0.458487

min

4.000000 250.000000 1.000000 1.000000 19.000000 1.000000 1.000000 1.000000

25%

12.000000 1365.500000 2.000000 2.000000 27.000000 1.000000 1.000000 1.000000

50%

18.000000 2319.500000 3.000000 3.000000 33.000000 1.000000 1.000000 1.000000

75%

24.000000 3972.250000 4.000000 4.000000 42.000000 2.000000 1.000000 2.000000

max

72.000000 18424.000000 4.000000 4.000000 75.000000 4.000000 2.000000 2.000000

data.Duration.unique()11

array([ 6, 48, 12, 42, 24, 36, 30, 15, 9, 10, 7, 60, 18, 45, 11, 27, 8, 54, 20, 14, 33, 21, 16, 4, 47, 13, 22, 39, 28, 5, 26, 72, 40], dtype=int64)data.History.unique()11

array([‘A34’, ‘A32’, ‘A33’, ‘A30’, ‘A31’], dtype=object)data.groupby('Balance').size().order(ascending=False)11

c:\python27\lib\site-packages\ipykernel\__main__.py:1: FutureWarning: order is deprecated, use sort_values(…) if __name__ == ‘__main__’: Balance A14 394 A11 274 A12 269 A13 63 dtype: int64data.groupby('Purpose').size().order(ascending=False)11

c:\python27\lib\site-packages\ipykernel\__main__.py:1: FutureWarning: order is deprecated, use sort_values(…) if __name__ == ‘__main__’: Purpose A43 280 A40 234 A42 181 A41 103 A49 97 A46 50 A45 22 A44 12 A410 12 A48 9 dtype: int64data.groupby('Apartment').size().order(ascending=False)11

c:\python27\lib\site-packages\ipykernel\__main__.py:1: FutureWarning: order is deprecated, use sort_values(…) if __name__ == ‘__main__’: Apartment A152 713 A151 179 A153 108 dtype: int64import matplotlib.pyplot as plt

%matplotlib inline

data.plot(x='lable', y='Age', kind='scatter',

alpha=0.02, s=50);12341234

data.hist('Age', bins=15);11

target=data.lable11

features_data=data.drop('lable',axis=1)11

numeric_features = [c for c in features_data if features_data[c].dtype.kind in ('i', 'f')] # 提取數(shù)值類型為整數(shù)或浮點數(shù)的變量11

numeric_features11

[‘Duration’, ‘Credit amount’, ‘instPercent’, ‘Residence duration’, ‘Age’, ‘Credits’, ‘Dependents’]numeric_data = features_data[numeric_features]11

numeric_data.head()11

Duration

Credit amount

instPercent

Residence duration

Age

Credits

Dependents

6 1169 4 4 67 2 1

1

48 5951 2 2 22 1 1

2

12 2096 2 3 49 1 2

3

42 7882 2 4 45 1 2

4

24 4870 3 4 53 2 2

categorical_data = features_data.drop(numeric_features, axis=1)11

categorical_data.head()11

Balance

History

Purpose

Savings

Employment

sexMarried

Guarantors

Assets

concCredit

Apartment

Occupation

hasPhone

Foreign

A11 A34 A43 A65 A75 A93 A101 A121 A143 A152 A173 A192 A201

1

A12 A32 A43 A61 A73 A92 A101 A121 A143 A152 A173 A191 A201

2

A14 A34 A46 A61 A74 A93 A101 A121 A143 A152 A172 A191 A201

3

A11 A32 A42 A61 A74 A93 A103 A122 A143 A153 A173 A191 A201

4

A11 A33 A40 A61 A73 A93 A101 A124 A143 A153 A173 A191 A201

categorical_data_encoded = categorical_data.apply(lambda x: pd.factorize(x)[0]) # pd.factorize即可將分類變量轉(zhuǎn)換為數(shù)值表示

# apply運算將轉(zhuǎn)換函數(shù)應(yīng)用到每一個變量維度

categorical_data_encoded.head(5)123123

Balance

History

Purpose

Savings

Employment

sexMarried

Guarantors

Assets

concCredit

Apartment

Occupation

hasPhone

Foreign

0 0 0 0 0 0 0 0 0 0 0 0 0

1

1 1 0 1 1 1 0 0 0 0 0 1 0

2

2 0 1 1 2 0 0 0 0 0 1 1 0

3

0 1 2 1 2 0 1 1 0 1 0 1 0

4

0 2 3 1 1 0 0 2 0 1 0 1 0

features = pd.concat([numeric_data, categorical_data_encoded], axis=1)#進(jìn)行數(shù)據(jù)的合并

features.head()

# 此處也可以選用one-hot編碼來表示分類變量，相應(yīng)的程序如下：

# features = pd.get_dummies(features_data)

# features.head()1234512345

Duration

Credit amount

instPercent

Residence duration

Age

Credits

Dependents

Balance

History

Purpose

Savings

Employment

sexMarried

Guarantors

Assets

concCredit

Apartment

Occupation

hasPhone

Foreign

6 1169 4 4 67 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0

1

48 5951 2 2 22 1 1 1 1 0 1 1 1 0 0 0 0 0 1 0

2

12 2096 2 3 49 1 2 2 0 1 1 2 0 0 0 0 0 1 1 0

3

42 7882 2 4 45 1 2 0 1 2 1 2 0 1 1 0 1 0 1 0

4

24 4870 3 4 53 2 2 0 2 3 1 1 0 0 2 0 1 0 1 0

X = features.values.astype(np.float32) # 轉(zhuǎn)換數(shù)據(jù)類型

y = (target.values == 1).astype(np.int32) # 1:good,2:bad1212

from sklearn.cross_validation import train_test_split # sklearn庫中train_test_split函數(shù)可實現(xiàn)該劃分

X_train, X_test, y_train, y_test = train_test_split(

X, y, test_size=0.2, random_state=0) # 參數(shù)test_size設(shè)置訓(xùn)練集占比

1234512345

from sklearn.tree import DecisionTreeClassifier

from sklearn.cross_validation import cross_val_score

clf = DecisionTreeClassifier(max_depth=8) # 參數(shù)max_depth設(shè)置樹最大深度

# 交叉驗證，評價分類器性能，此處選擇的評分標(biāo)準(zhǔn)是ROC曲線下的AUC值，對應(yīng)AUC更大的分類器效果更好

scores = cross_val_score(clf, X_train, y_train, cv=3, scoring='roc_auc')

print("ROC AUC Decision Tree: {:.4f} +/-{:.4f}".format(

np.mean(scores), np.std(scores)))123456789123456789

ROC AUC Decision Tree: 0.6866 +/-0.0105

#利用learning curve，以樣本數(shù)為橫坐標(biāo)，訓(xùn)練和交叉驗證集上的評分為縱坐標(biāo)，對不同深度的決策樹進(jìn)行對比（判斷是否存在過擬合或欠擬合）

from sklearn.learning_curve import learning_curve

def plot_learning_curve(estimator, X, y, ylim=(0, 1.1), cv=3,

n_jobs=1, train_sizes=np.linspace(.1, 1.0, 5),

scoring=None):

plt.title("Learning curves for %s" % type(estimator).__name__)

plt.ylim(*ylim); plt.grid()

plt.xlabel("Training examples")

plt.ylabel("Score")

train_sizes, train_scores, validation_scores = learning_curve(

estimator, X, y, cv=cv, n_jobs=n_jobs, train_sizes=train_sizes,

scoring=scoring)

train_scores_mean = np.mean(train_scores, axis=1)

validation_scores_mean = np.mean(validation_scores, axis=1)

plt.plot(train_sizes, train_scores_mean, 'o-', color="r",

label="Training score")

plt.plot(train_sizes, validation_scores_mean, 'o-', color="g",

label="Cross-validation score")

plt.legend(loc="best")

print("Best validation score: {:.4f}".format(validation_scores_mean[-1]))12345678910111213141516171819202122231234567891011121314151617181920212223

clf = DecisionTreeClassifier(max_depth=None)

plot_learning_curve(clf, X_train, y_train, scoring='roc_auc')

# 可以注意到訓(xùn)練數(shù)據(jù)和交叉驗證數(shù)據(jù)的得分有很大的差距，意味著可能過度擬合訓(xùn)練數(shù)據(jù)了123123

Best validation score: 0.6310

clf = DecisionTreeClassifier(max_depth=10)

plot_learning_curve(clf, X_train, y_train, scoring='roc_auc')1212

Best validation score: 0.6565

clf = DecisionTreeClassifier(max_depth=8)

plot_learning_curve(clf, X_train, y_train, scoring='roc_auc')1212

Best validation score: 0.6762

clf = DecisionTreeClassifier(max_depth=5)

plot_learning_curve(clf, X_train, y_train, scoring='roc_auc')1212

Best validation score: 0.7219

clf = DecisionTreeClassifier(max_depth=4)

plot_learning_curve(clf, X_train, y_train, scoring='roc_auc')1212

Best validation score: 0.7226

如何將python生成的決策樹利用graphviz畫出來

#?這里有一個示例，你可以看一下。

#?

from?IPython.display?import?Image??

dot_data?=?tree.export_graphviz(clf,?out_file=None,?

feature_names=iris.feature_names,??

class_names=iris.target_names,??

filled=True,?rounded=True,??

special_characters=True)??

graph?=?pydotplus.graph_from_dot_data(dot_data)??

Image(graph.create_png())

決策樹（Decision Tree）

決策樹是一種非參數(shù)有監(jiān)督的機(jī)器學(xué)習(xí)方法，可以用于解決回歸問題和分類問題。通過學(xué)習(xí)已有的數(shù)據(jù)，計算得出一系列推斷規(guī)則來預(yù)測目標(biāo)變量的值，并用類似流程圖的形式進(jìn)行展示。決策樹模型可以進(jìn)行可視化，具有很強(qiáng)的可解釋性，算法容易理解，以決策樹為基礎(chǔ)的各種集成算法在很多領(lǐng)域都有廣泛的應(yīng)用。

熵的概念最早起源于物理學(xué)，用于度量一個熱力學(xué)系統(tǒng)的無序程度。在信息論里面，信息熵代表著一個事件或一個變量等所含有的信息量。 在信息世界，熵越高，則能傳輸越多的信息，熵越低，則意味著傳輸?shù)男畔⒃缴佟?/p>

發(fā)生概率低的事件比發(fā)生概率高的事件具有更大的不確定性，需要更多的信息去描述他們，信息熵更高。

我們可以用計算事件發(fā)生的概率來計算事件的信息，又稱“香農(nóng)信息”（ Shannon Information ）。一個離散事件x的信息可以表示為：

h(x) = -log(p(x))

p() 代表事件x發(fā)生的概率， log() 為以二為底的對數(shù)函數(shù)，即一個事件的信息量就是這個事件發(fā)生的概率的負(fù)對數(shù)。選擇以二為底的對數(shù)函數(shù)代表計算信息的單位是二進(jìn)制。因為概率p(x)小于1，所以負(fù)號就保證了信息熵永遠(yuǎn)不為負(fù)數(shù)。當(dāng)事件的概率為1時，也就是當(dāng)某事件百分之百發(fā)生時，信息為0。

熵（ entropy ），又稱“香農(nóng)熵”（ Shannon entropy ），表示一個隨機(jī)變量的分布所需要的平均比特數(shù)。一個隨機(jī)變量的信息熵可以表示為：

H(x) = -sum(each k in K p(k)log(p(k)))

K表示變量x所可能具有的所有狀態(tài)（所有事件），將發(fā)生特定事件的概率和該事件的信息相乘，最后加和，即可得到該變量的信息熵。可以理解為，信息熵就是平均而言發(fā)生一個事件我們得到的信息量大小。所以數(shù)學(xué)上，信息熵其實是事件信息量的期望。

當(dāng)組成該隨機(jī)變量的一個事件的概率為1時信息熵最小，為0， 即該事件必然發(fā)生。當(dāng)組成該隨機(jī)變量的所有事件發(fā)生的概率相等時，信息熵最大，即完全不能判斷那一個事件更容易發(fā)生，不確定性最大。

當(dāng)一個事件主導(dǎo)時，比如偏態(tài)分布（ Skewed Probability Distribution ），不確定性減小，信息熵較低（low entropy）；當(dāng)所有事件發(fā)生概率相同時，比如均衡分布（ Balanced Probability Distribution ），不確定性極大，信息熵較高（high entropy）。

由以上的香農(nóng)信息公式可知，信息熵主要有三條性質(zhì)：

- 單調(diào)性 。發(fā)生概率越高的事件，其所攜帶的信息熵越低。比如一個真理的不確定性是極低的，那么它所攜帶的信息熵就極低。

- 非負(fù)性 。信息熵不能為負(fù)。單純從邏輯層面理解，如果得知了某個信息后，卻增加了不確定性，這也是不合邏輯的。

- 可加性 。即多隨機(jī)事件同時發(fā)生存在的總不確定性的量度是可以表示為各事件不確定性的量度的和。

若兩事件A和B同時發(fā)生，兩個事件相互獨立。 p(X=A,Y=B) = p(X = A)*p(Y=B) , 那么信息熵為 H(A,B) = H(A) + H(B) 。但若兩事件不相互獨立，那么 H(A,B) = H(A) + H(B) - I(A,B) 。其中 I(A,B) 是互信息（ mutual information，MI ），即一個隨機(jī)變量包含另一個隨機(jī)變量信息量的度量。即已知X的情況下，Y的分布是否會改變。

可以理解為，兩個隨機(jī)變量的互信息度量了兩個變量間相互依賴的程度。X 和 Y的互信息可以表示為：

I(X;Y) = H(X) - H(X|Y)

H(X)是X的信息熵，H(X|Y)是已知Y的情況下，X的信息熵。結(jié)果的單位是比特。

簡單來說，互信息的性質(zhì)為：

- I(X;Y)=0 互信息永遠(yuǎn)不可能為負(fù)

- H(X) - H(X|Y) = I(X;Y) = I (Y;X) = H(Y) - H(Y|X) 互信息是對稱的

-當(dāng)X，Y獨立的時候， I(X;Y) = 0 互信息值越大，兩變量相關(guān)性越強(qiáng)。

-當(dāng)X，Y知道一個就能推斷另一個的時候， I(X;Y) = H(Y) = H(X)

在數(shù)據(jù)科學(xué)中，互信息常用于特征篩選。在通信系統(tǒng)中互信息也應(yīng)用廣泛。在一個點到點的通信系統(tǒng)中，發(fā)送信號為X，通過信道后，接收端接收到的信號為Y，那么信息通過信道傳遞的信息量就是互信息 I(X,Y) 。根據(jù)這個概念，香農(nóng)推導(dǎo)出信道容量（即臨界通信傳輸速率的值）。

信息增益（ Information Gain ）是用來按照一定規(guī)則劃分?jǐn)?shù)據(jù)集后，衡量信息熵減少量的指數(shù)。

那數(shù)據(jù)集的信息熵又是怎么計算的呢？比如一個常見的0,1二分類問題，我們可以計算它的熵為：

Entropy = -(p(0) * log(P(0)) + p(1)\ * log(P(1)))

當(dāng)該數(shù)據(jù)集為50/50的數(shù)據(jù)集時，它的信息熵是最大的（1bit）。而10/90的數(shù)據(jù)集將會大大減少結(jié)果的不確定性，減小數(shù)據(jù)集的信息熵（約為0.469bit）。

這樣來說，信息熵可以用來表示數(shù)據(jù)集的純度（ purity ）。信息熵為0就表示該數(shù)據(jù)集只含有一個類別，純度最高。而較高的信息熵則代表較為平衡的數(shù)據(jù)集和較低的純度。

信息增益是提供了一種可以使用信息熵計算數(shù)據(jù)集經(jīng)過一定的規(guī)則（比如決策樹中的一系列規(guī)則）進(jìn)行數(shù)據(jù)集分割后信息熵的變化的方法。

IG(S,a) = H(S) - H(S|a)

其中，H(s) 是原數(shù)據(jù)集S的信息熵（在做任何改變之前），H(S|a)是經(jīng)過變量a的一定分割規(guī)則。所以信息增益描述的是數(shù)據(jù)集S變換后所節(jié)省的比特數(shù)。

信息增益可以用做決策樹的分枝判斷方法。比如最常用CART樹（ Classification and Regression Tree ）中的分枝方法，只要在python中設(shè)置參數(shù) criterion 為 “entropy” 即可。

信息增益也可以用作建模前的特征篩選。在這種場景下，信息增益和互信息表達(dá)的含義相同，會被用來計算兩變量之間的獨立性。比如scikit-learn 中的函數(shù) mutual_info_classiif()

信息增益在面對類別較少的離散數(shù)據(jù)時效果較好，但是面對取值較多的特征時效果會有 偏向性 。因為當(dāng)特征的取值較多時，根據(jù)此特征劃分得到的子集純度有更大的可能性會更高(對比與取值較少的特征)，因此劃分之后的熵更低，由于劃分前的熵是一定的，因此信息增益更大，因此信息增益比較偏向取值較多的特征。舉一個極端的例子來說，如果一個特征為身份證號，當(dāng)把每一個身份證號不同的樣本都分到不同的子節(jié)點時，熵會變?yōu)?，意味著信息增益最大，從而該特征會被算法選擇。但這種分法顯然沒有任何實際意義。

這種時候，信息增益率就起到了很重要的作用。

gR(D,A)=g(D,A)/HA(D)

HA(D) 又叫做特征A的內(nèi)部信息，HA(D)其實像是一個衡量以特征AA的不同取值將數(shù)據(jù)集D分類后的不確定性的度量。如果特征A的取值越多，那么不確定性通常會更大，那么HA(D)的值也會越大，而1/HA(D)的值也會越小。這相當(dāng)于是在信息增益的基礎(chǔ)上乘上了一個懲罰系數(shù)。即 gR(D,A)=g(D,A)?懲罰系數(shù) 。

在CART算法中，基尼不純度表示一個隨機(jī)選中的樣本被分錯類別的可能性，即這個樣本被選中的概率乘以它被分錯的概率。當(dāng)一個節(jié)點中所有樣本均為一種時（沒有被分錯的樣本），基尼不純度達(dá)到最低值0。

舉例來說，如果有綠色和藍(lán)色兩類數(shù)據(jù)點，各占一半（藍(lán)色50%，綠色50%）。那么我們隨機(jī)分類，有以下四種情況：

-分為藍(lán)色，但實際上是綠色（?），概率25%

-分為藍(lán)色，實際上也是藍(lán)色（??），概率25%

-分為綠色，實際上也是綠色（??），概率25%

-分為綠色，但實際上是藍(lán)色（?），概率25%

那么將任意一個數(shù)據(jù)點分錯的概率為25%+25% = 50%。基尼不純度為0.5。

在特征選擇中，我們可以選擇加入后使數(shù)據(jù)不純度減少最多的特征。

噪音數(shù)據(jù)簡單來說就是會對模型造成誤導(dǎo)的數(shù)據(jù)。分為類別噪聲（ class noise 或 label noise ）和 變量噪聲（ attribute noise ）。類別噪聲指的的是被錯誤標(biāo)記的錯誤數(shù)據(jù)，比如兩個相同的樣本具有不同的標(biāo)簽等情況。變量噪聲指的是有問題的變量，比如缺失值、異常值和無關(guān)值等。

決策樹其實是一種圖結(jié)構(gòu)，由節(jié)點和邊構(gòu)成。

-根節(jié)點：只有出邊沒有入邊。包含樣本全集，表示一個對樣本最初的判斷。

-內(nèi)部節(jié)點：一個入邊多個出邊。表示一個特征或是屬性。每個內(nèi)部節(jié)點都是一個判斷條件，包含數(shù)據(jù)集中從根節(jié)點到該節(jié)點所有滿足條件的數(shù)據(jù)的集合。

-葉節(jié)點：一個入邊無出邊。表示一個類，對應(yīng)于決策結(jié)果。

決策樹的生成主要分為三個步驟：

1. 節(jié)點的分裂 ：當(dāng)一個節(jié)點不夠純（單一分類占比不夠大或者說信息熵較大）時，則選擇將這一節(jié)點進(jìn)行分裂。

2. 決策邊界的確定 ：選擇正確的決策邊界（ Decision Boundary ），使分出的節(jié)點盡量純，信息增益（熵減少的值）盡可能大。

3. 重復(fù)及停止生長 ：重復(fù)1，2步驟，直到純度為0或樹達(dá)到最大深度。為避免過擬合，決策樹算法一般需要制定樹分裂的最大深度。到達(dá)這一深度后，即使熵不等于0，樹也不會繼續(xù)進(jìn)行分裂。

下面以超級知名的鳶尾花數(shù)據(jù)集舉例來說明。

這個數(shù)據(jù)集含有四個特征：花瓣的長度（ petal length ）、花瓣的寬度( petal width )、花萼的長度( sepal length )和花萼的寬度( sepal width )。預(yù)測目標(biāo)是鳶尾花的種類 iris setosa, iris versicolor 和 iris virginica 。

建立決策樹模型的目標(biāo)是根據(jù)特征盡可能正確地將樣本劃分到三個不同的“陣營”中。

根結(jié)點的選擇基于全部數(shù)據(jù)集，使用了貪婪算法：遍歷所有的特征，選擇可以使信息熵降到最低、基尼不純度最低的特征。

如上圖，根節(jié)點的決策邊界為' petal width = 0.8cm '。那么這個決策邊界是怎么決定的呢？

-遍歷所有可能的決策邊界（需要注意的是，所有可能的決策邊界代表的是該子集中該特征所有的值，不是以固定增幅遍歷一個區(qū)間內(nèi)的所有值！那樣很沒有必要的～）

-計算新建的兩個子集的基尼不純度。

-選擇可以使新的子集達(dá)到最小基尼不純度的分割閾值。這個“最小”可以指兩個子集的基尼不純度的和或平均值。

ID3是最早提出的決策樹算法。ID3算法的核心是在決策樹各個節(jié)點上根據(jù) 信息增益 來選擇進(jìn)行劃分的特征，然后遞歸地構(gòu)建決策樹。

- 缺點 ：

（1）沒有剪枝

（2）只能用于處理離散特征

（3）采用信息增益作為選擇最優(yōu)劃分特征的標(biāo)準(zhǔn)，然而信息增益會偏向那些取值較多的特征(例如，如果存在唯一標(biāo)識屬性身份證號，則ID3會選擇它作為分裂屬性，這樣雖然使得劃分充分純凈，但這種劃分對分類幾乎毫無用處。)

C4.5 與ID3相似，但對ID3進(jìn)行了改進(jìn)：

-引入“悲觀剪枝”策略進(jìn)行后剪枝

-信息增益率作為劃分標(biāo)準(zhǔn)

-將連續(xù)特征離散化，假設(shè) n 個樣本的連續(xù)特征 A 有 m 個取值，C4.5 將其排序并取相鄰兩樣本值的平均數(shù)共 m-1 個劃分點，分別計算以該劃分點作為二元分類點時的信息增益，并選擇信息增益最大的點作為該連續(xù)特征的二元離散分類點；

-可以處理缺失值

對于缺失值的處理可以分為兩個子問題：

（1）在特征值缺失的情況下進(jìn)行劃分特征的選擇？（即如何計算特征的信息增益率）

C4.5 中對于具有缺失值特征，用沒有缺失的樣本子集所占比重來折算；

（2）選定該劃分特征，對于缺失該特征值的樣本如何處理？（即到底把這個樣本劃分到哪個結(jié)點里）

C4.5 的做法是將樣本同時劃分到所有子節(jié)點，不過要調(diào)整樣本的權(quán)重值，其實也就是以不同概率劃分到不同節(jié)點中。

（1）剪枝策略可以再優(yōu)化；

（2）C4.5 用的是多叉樹，用二叉樹效率更高；

（3）C4.5 只能用于分類；

（4）C4.5 使用的熵模型擁有大量耗時的對數(shù)運算，連續(xù)值還有排序運算；

（5）C4.5 在構(gòu)造樹的過程中，對數(shù)值屬性值需要按照其大小進(jìn)行排序，從中選擇一個分割點，所以只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時，程序無法運行。

可以用于分類，也可以用于回歸問題。CART 算法使用了基尼系數(shù)取代了信息熵模型，計算復(fù)雜度更低。

CART 包含的基本過程有 分裂，剪枝和樹選擇 。

分裂 ：分裂過程是一個二叉遞歸劃分過程，其輸入和預(yù)測特征既可以是連續(xù)型的也可以是離散型的，CART 沒有停止準(zhǔn)則，會一直生長下去；

剪枝 ：采用“代價復(fù)雜度”剪枝，從最大樹開始，每次選擇訓(xùn)練數(shù)據(jù)熵對整體性能貢獻(xiàn)最小的那個分裂節(jié)點作為下一個剪枝對象，直到只剩下根節(jié)點。CART 會產(chǎn)生一系列嵌套的剪枝樹，需要從中選出一顆最優(yōu)的決策樹；

樹選擇 ：用單獨的測試集評估每棵剪枝樹的預(yù)測性能（也可以用交叉驗證）。

（1）C4.5 為多叉樹，運算速度慢，CART 為二叉樹，運算速度快；

（2）C4.5 只能分類，CART 既可以分類也可以回歸；

（3）CART 使用 Gini 系數(shù)作為變量的不純度量，減少了大量的對數(shù)運算；

（4）CART 采用代理測試來估計缺失值，而 C4.5 以不同概率劃分到不同節(jié)點中；

（5）CART 采用“基于代價復(fù)雜度剪枝”方法進(jìn)行剪枝，而 C4.5 采用悲觀剪枝方法。

（1）決策樹易于理解和解釋，可以可視化分析，容易提取出規(guī)則

（2）可以同時處理分類型和數(shù)值型數(shù)據(jù)

（3）可以處理缺失值

（4）運行速度比較快（使用Gini的快于使用信息熵，因為信息熵算法有l(wèi)og）

（1）容易發(fā)生過擬合（集成算法如隨機(jī)森林可以很大程度上減少過擬合）

（2）容易忽略數(shù)據(jù)集中屬性的相互關(guān)聯(lián)；

（3）對于那些各類別樣本數(shù)量不一致的數(shù)據(jù)，在決策樹中，進(jìn)行屬性劃分時，不同的判定準(zhǔn)則會帶來不同的屬性選擇傾向。

寫在后面：這個專輯主要是本小白在機(jī)器學(xué)習(xí)算法學(xué)習(xí)過程中的一些總結(jié)筆記和心得，如有不對之處還請各位大神多多指正！（關(guān)于決策樹的剪枝還有很多沒有搞懂，之后弄明白了會再單獨出一篇總結(jié)噠）

參考資料鏈接：

1.

2.

3.

4.

5.

6.

7.

8.

網(wǎng)站欄目：python中決策樹函數(shù) 決策樹算法 python
路徑分享：http://chinadenli.net/article40/dodpceo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App設(shè)計、外貿(mào)網(wǎng)站建設(shè)、品牌網(wǎng)站制作、營銷型網(wǎng)站建設(shè)、服務(wù)器托管、自適應(yīng)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)