1. 決策樹
https://blog.csdn.net/dorisi_h_n_q/article/details/82787295
1.1 決策樹定義
決策樹（decision tree）是一個樹結(jié)構(gòu)（可以是二叉樹或非二叉樹）。決策過程是從根節(jié)點開始，測試待分類項中相應(yīng)的特征屬性，并按照其值選擇輸出分支，直到到達葉子節(jié)點，將葉子節(jié)點存放的類別作為決策結(jié)果。
1.2 決策樹原理
決策樹的關(guān)鍵步驟是分裂屬性。就是在某節(jié)點處按某一特征屬性的不同劃分構(gòu)造不同的分支，目標是讓各個分裂子集盡可能地“純”。即讓一個分裂子集中待分類項屬于同一類別。
簡而言之，決策樹的劃分原則就是：將無序的數(shù)據(jù)變得更加有序
分裂屬性分為三種不同的情況：
- 屬性是離散值且不要求生成二叉決策樹。此時用屬性的每一個劃分作為一個分支。
- 屬性是離散值且要求生成二叉決策樹。此時使用屬性劃分的一個子集進行測試，按照“屬于此子集”和“不屬于此子集”分成兩個分支。
- 屬性是連續(xù)值。此時確定一個值作為分裂點split_point，按照>split_point和<=split_point生成兩個分支。
構(gòu)造決策樹的關(guān)鍵性內(nèi)容是進行屬性選擇度量，屬性選擇度量（找一種計算方式來衡量怎么劃分更劃算）是一種選擇分裂準則，它決定了拓撲結(jié)構(gòu)及分裂點split_point的選擇。
屬性選擇度量算法有很多，一般使用自頂向下遞歸分治法，并采用不回溯的貪心策略。這里介紹常用的ID3算法。
貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，所做出的是在某種意義上的局部最優(yōu)解。
2.ID3算法
2.1 熵
此概念最早起源于物理學(xué)，是用來度量一個熱力學(xué)系統(tǒng)的無序程度。
而在信息學(xué)里面，熵是對不確定性的度量。
在1948年，香農(nóng)引入了信息熵，將其定義為離散隨機事件出現(xiàn)的概率，一個系統(tǒng)越是有序，信息熵就越低，反之一個系統(tǒng)越是混亂，它的信息熵就越高。所以信息熵可以被認為是系統(tǒng)有序化程度的一個度量。
熵定義為信息的期望值，在明晰這個概念之前，我們必須知道信息的定義。如果待分類的事務(wù)可能劃分在多個分類之中，則符號x的信息定義為：
2.2 信息增益
在劃分數(shù)據(jù)集之前之后信息發(fā)生的變化稱為信息增益。
知道如何計算信息增益，就可計算每個特征值劃分數(shù)據(jù)集獲得的信息增益，獲得信息增益最高的特征就是最好的選擇。
條件熵 表示在已知隨機變量的條件下隨機變量的不確定性，隨機變量X給定的條件下隨機變量Y的條
件熵(conditional entropy) ，定義X給定條件下Y的條件概率分布的熵對X的數(shù)學(xué)期望：
根據(jù)上面公式，我們假設(shè)將訓(xùn)練集D按屬性A進行劃分，則A對D劃分的期望信息為
則信息增益為如下兩者的差值
2.3 ID3算法
ID3算法就是在每次需要分裂時，計算每個屬性的增益率，然后選擇增益率最大的屬性進行分裂
步驟：1. 對當前樣本集合，計算所有屬性的信息增益；
- 選擇信息增益最?的屬性作為測試屬性，把測試屬性取值相同的樣本劃為同?個子樣本集；
- 若?樣本集的類別屬性只含有單個屬性，則分?為葉?節(jié)點， 判斷其屬性值并標上相應(yīng)的符號，然后返回調(diào)用處； 否則對子樣本集遞歸調(diào)用此算法。
2.4.1 cls算法
是最原始的決策樹分類算法，基本流程是，從一棵空數(shù)出發(fā)，不斷的從決策表選取屬性加入數(shù)的生長過程中，直到?jīng)Q策樹可以滿足分類要求為止。CLS算法存在的主要問題是在新增屬性選取時有很大的隨機性。ID3算法是對CLS算法的改進，主要是摒棄了屬性選擇的隨機性。
2.4.2 c4.5算法
基于ID3算法的改進，主要包括：使用信息增益比替換了信息增益下降度作為屬性選擇的標準；在決策樹構(gòu)造的同時進行剪枝操作；避免了樹的過度擬合情況；可以對不完整屬性和連續(xù)型數(shù)據(jù)進行處理；使用k交叉驗證降低了計算復(fù)雜度；針對數(shù)據(jù)構(gòu)成形式，提升了算法的普適性。
信息增益值的大小相對于訓(xùn)練數(shù)據(jù)集而言的，并沒有絕對意義，在分類問題困難時，也就是說在訓(xùn)練數(shù)據(jù)集經(jīng)驗熵大的時候，信息增益值會偏大，反之信息增益值會偏小，使用信息增益比可以對這個問題進行校正，這是特征選擇
的另一個標準。
特征對訓(xùn)練數(shù)據(jù)集的信息增益比定義為其信息增益gR( D,A) 與訓(xùn)練數(shù)據(jù)集的經(jīng)驗熵g(D,A)之比 ：
gR(D,A) = g(D,A) / H(D)
2.5 CART(Classification and RegressionTrees, CART)：
sklearn的決策樹模型就是一個CART樹。是一種二分遞歸分割技術(shù)，把當前樣本劃分為兩個子樣本，使得生成的每個非葉子節(jié)點都有兩個分支，因此，CART算法生成的決策樹是結(jié)構(gòu)簡潔的二叉樹。
分類回歸樹算法(Classification and Regression Trees,簡稱CART算法)是一種基于二分遞歸分割技術(shù)的算法。該算法是將當前的樣本集，分為兩個樣本子集，這樣做就使得每一個非葉子節(jié)點最多只有兩個分支。因此，使用CART
算法所建立的決策樹是一棵二叉樹，樹的結(jié)構(gòu)簡單，與其它決策樹算法相比，由該算法生成的決策樹模型分類規(guī)則較少。
CART分類算法的基本思想是：對訓(xùn)練樣本集進行遞歸劃分自變量空間，并依次建立決策樹模型，然后采用驗證數(shù)據(jù)的方法進行樹枝修剪，從而得到一顆符合要求的決策樹分類模型。
CART分類算法和C4.5算法一樣既可以處理離散型數(shù)據(jù)，也可以處理連續(xù)型數(shù)據(jù)。CART分類算法是根據(jù)基尼(gini)系
數(shù)來選擇測試屬性，gini系數(shù)的值越小，劃分效果越好。設(shè)樣本集合為T，則T的gini系數(shù)值可由下式計算：
CART算法優(yōu)點：除了具有一般決策樹的高準確性、高效性、模式簡單等特點外，還具有一些自身的特點。
如，CART算法對目標變量和預(yù)測變量在概率分布上沒有要求，這樣就避免了因目標變量與預(yù)測變量概率分布的不同造成的結(jié)果；CART算法能夠處理空缺值，這樣就避免了因空缺值造成的偏差；CART算法能夠處理孤立的葉子結(jié)點，這樣可以避免因為數(shù)據(jù)集中與其它數(shù)據(jù)集具有不同的屬性的數(shù)據(jù)對進一步分支產(chǎn)生影響；CART算法使用的是二元分支，能夠充分地運用數(shù)據(jù)集中的全部數(shù)據(jù)，進而發(fā)現(xiàn)全部樹的結(jié)構(gòu)；比其它模型更容易理解，從模型中得到的規(guī)則能獲得非常直觀的解釋。
CART算法缺點：CART算法是一種大容量樣本集挖掘算法，當樣本集比較小時不夠穩(wěn)定；要求被選擇的屬性只能產(chǎn)生兩個子結(jié)點，當類別過多時，錯誤可能增加得比較快。
2.6 sklearn算法的參數(shù)說明：
sklearn.tree.DecisionTreeClassifier
skleanr決策樹模型參數(shù)含義如下所示：
criterion：gini或者entropy,前者是基尼系數(shù)，后者是信息熵。
splitter： best or random 前者是在所有特征中找最好的切分點后者是在部分特征中，默認的”best”適合樣本量不大的時候，而如果樣本數(shù)據(jù)量非常大，此時決策樹構(gòu)建推薦”random” 。
max_features：None（所有），log2，sqrt，N 特征小于50的時候一般使用所有的
max_depth： int or None, optional (default=None) 設(shè)置決策隨機森林中的決策樹的最大深度，深度越大，越容易過擬合，推薦樹的深度為：5-20之間。
min_samples_split：設(shè)置結(jié)點的最小樣本數(shù)量，當樣本數(shù)量可能小于此值時，結(jié)點將不會在劃分。
min_samples_leaf： 這個值限制了葉子節(jié)點最少的樣本數(shù)，如果某葉子節(jié)點數(shù)目小于樣本數(shù)，則會和兄弟節(jié)點一起被剪枝。
min_weight_fraction_leaf： 這個值限制了葉子節(jié)點所有樣本權(quán)重和的最小值，如果小于這個值，則會和兄弟節(jié)點一起被剪枝默認是0，就是不考慮權(quán)重問題。
max_leaf_nodes： 通過限制最大葉子節(jié)點數(shù)，可以防止過擬合，默認是"None”，即不限制最大的葉子節(jié)點
數(shù)。
class_weight： 指定樣本各類別的的權(quán)重，主要是為了防止訓(xùn)練集某些類別的樣本過多導(dǎo)致訓(xùn)練的決策樹過于偏向這些類別。這里可以自己指定各個樣本的權(quán)重，如果使用“balanced”，則算法會自己計算權(quán)重，樣本量少的類別所對應(yīng)的樣本權(quán)重會高。
min_impurity_split： 這個值限制了決策樹的增長，如果某節(jié)點的不純度(基尼系數(shù)，信息增益，均方差，絕對差)小于這個閾值則該節(jié)點不再生成子節(jié)點。即為葉子節(jié)點 。
2.7 安裝graphviz.msi可以繪制決策樹
1.安裝graphviz.msi ， 一路next即可
- 添加環(huán)境變量： 把graphviz 安裝包下的bin文件夾路徑添加到 系統(tǒng)變量的path里面去。
3.終端輸入dot -version 出現(xiàn)版本信息為安裝成功。
# 繪制決策樹
import graphviz
from sklean import tree
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 = graphviz.Source(dot_data)
graph
3. ID3算法實現(xiàn)
ID3算法就是在每次需要分裂時，計算每個屬性的增益率，然后選擇增益率最大的屬性進行分裂
import numpy as np
import math
# 類別就是【賬號是否真實】p(no) 3/10 p(yes) 7/10
原始熵值：
info_D = -0.3math.log2(0.3) -0.7math.log2(0.7)
info_D #0.8812908992306927
按照好友密度劃分的信息增益：
info_s = -(3/4)math.log2(3/4) -(1/4)math.log2(1/4)
info_m = 0
info_l = 0
info_F_D = 0.4info_s + 0.4info_m + 0.2*info_l
info_D - info_F_D #信息增益 0.5567796494470396
按照是否使用真實頭像H劃分的信息增益
info_n = -(2/5)math.log2(2/5) -(3/5)math.log2(3/5)
info_y = -(1/5)math.log2(1/5) -(4/5)math.log2(4/5)
info_H_D = 0.5info_n + 0.5info_y
info_D - info_H_D # 信息增益 0.034851554559677256
**所以，按先按好友密度劃分的信息增益比按真實頭像劃分的大。應(yīng)先按好友密度劃分。
