1. 決策樹
https://blog.csdn.net/dorisi_h_n_q/article/details/82787295
1.1 決策樹定義
決策樹（decision tree）是一個樹結構（可以是二叉樹或非二叉樹）。決策過程是從根節(jié)點開始，測試待分類項中相應的特征屬性彭沼，并按照其值選擇輸出分支，直到到達葉子節(jié)點奢啥，將葉子節(jié)點存放的類別作為決策結果耐量。
1.2 決策樹原理
決策樹的關鍵步驟是分裂屬性糜俗。就是在某節(jié)點處按某一特征屬性的不同劃分構造不同的分支校翔，目標是讓各個分裂子集盡可能地“純”弟跑。即讓一個分裂子集中待分類項屬于同一類別。
簡而言之防症，決策樹的劃分原則就是：將無序的數(shù)據(jù)變得更加有序
分裂屬性分為三種不同的情況：
- 屬性是離散值且不要求生成二叉決策樹窖认。此時用屬性的每一個劃分作為一個分支。
- 屬性是離散值且要求生成二叉決策樹告希。此時使用屬性劃分的一個子集進行測試，按照“屬于此子集”和“不屬于此子集”分成兩個分支搁料。
- 屬性是連續(xù)值新啼。此時確定一個值作為分裂點split_point寨闹，按照>split_point和<=split_point生成兩個分支。
構造決策樹的關鍵性內(nèi)容是進行屬性選擇度量指么，屬性選擇度量（找一種計算方式來衡量怎么劃分更劃算）是一種選擇分裂準則酝惧，它決定了拓撲結構及分裂點split_point的選擇。
屬性選擇度量算法有很多伯诬，一般使用自頂向下遞歸分治法晚唇，并采用不回溯的貪心策略。這里介紹常用的ID3算法盗似。
貪心算法（又稱貪婪算法）是指哩陕，在對問題求解時，總是做出在當前看來是最好的選擇赫舒。也就是說悍及，不從整體最優(yōu)上加以考慮，所做出的是在某種意義上的局部最優(yōu)解接癌。
2.ID3算法
2.1 熵
此概念最早起源于物理學心赶，是用來度量一個熱力學系統(tǒng)的無序程度。
而在信息學里面缺猛，熵是對不確定性的度量缨叫。
在1948年，香農(nóng)引入了信息熵荔燎，將其定義為離散隨機事件出現(xiàn)的概率耻姥，一個系統(tǒng)越是有序，信息熵就越低湖雹，反之一個系統(tǒng)越是混亂咏闪，它的信息熵就越高。所以信息熵可以被認為是系統(tǒng)有序化程度的一個度量摔吏。
熵定義為信息的期望值鸽嫂，在明晰這個概念之前，我們必須知道信息的定義征讲。如果待分類的事務可能劃分在多個分類之中据某，則符號x的信息定義為：
2.2 信息增益
在劃分數(shù)據(jù)集之前之后信息發(fā)生的變化稱為信息增益。
知道如何計算信息增益诗箍，就可計算每個特征值劃分數(shù)據(jù)集獲得的信息增益癣籽，獲得信息增益最高的特征就是最好的選擇。
條件熵 表示在已知隨機變量的條件下隨機變量的不確定性滤祖，隨機變量X給定的條件下隨機變量Y的條
件熵(conditional entropy) 筷狼，定義X給定條件下Y的條件概率分布的熵對X的數(shù)學期望：
根據(jù)上面公式，我們假設將訓練集D按屬性A進行劃分匠童，則A對D劃分的期望信息為
則信息增益為如下兩者的差值
2.3 ID3算法
ID3算法就是在每次需要分裂時埂材，計算每個屬性的增益率，然后選擇增益率最大的屬性進行分裂
步驟：1. 對當前樣本集合汤求，計算所有屬性的信息增益俏险；
- 選擇信息增益最?的屬性作為測試屬性严拒，把測試屬性取值相同的樣本劃為同?個子樣本集；
- 若?樣本集的類別屬性只含有單個屬性竖独，則分?為葉?節(jié)點裤唠， 判斷其屬性值并標上相應的符號，然后返回調用處莹痢； 否則對子樣本集遞歸調用此算法种蘸。
2.4.1 cls算法
是最原始的決策樹分類算法，基本流程是格二，從一棵空數(shù)出發(fā)劈彪，不斷的從決策表選取屬性加入數(shù)的生長過程中，直到?jīng)Q策樹可以滿足分類要求為止顶猜。CLS算法存在的主要問題是在新增屬性選取時有很大的隨機性沧奴。ID3算法是對CLS算法的改進，主要是摒棄了屬性選擇的隨機性长窄。
2.4.2 c4.5算法
基于ID3算法的改進滔吠，主要包括：使用信息增益比替換了信息增益下降度作為屬性選擇的標準；在決策樹構造的同時進行剪枝操作挠日；避免了樹的過度擬合情況疮绷；可以對不完整屬性和連續(xù)型數(shù)據(jù)進行處理；使用k交叉驗證降低了計算復雜度嚣潜；針對數(shù)據(jù)構成形式冬骚，提升了算法的普適性。
信息增益值的大小相對于訓練數(shù)據(jù)集而言的懂算，并沒有絕對意義只冻，在分類問題困難時，也就是說在訓練數(shù)據(jù)集經(jīng)驗熵大的時候计技，信息增益值會偏大喜德，反之信息增益值會偏小，使用信息增益比可以對這個問題進行校正垮媒，這是特征選擇
的另一個標準舍悯。
特征對訓練數(shù)據(jù)集的信息增益比定義為其信息增益gR( D,A) 與訓練數(shù)據(jù)集的經(jīng)驗熵g(D,A)之比 ：
gR(D,A) = g(D,A) / H(D)
2.5 CART(Classification and RegressionTrees, CART)：
sklearn的決策樹模型就是一個CART樹。是一種二分遞歸分割技術睡雇，把當前樣本劃分為兩個子樣本萌衬，使得生成的每個非葉子節(jié)點都有兩個分支，因此它抱，CART算法生成的決策樹是結構簡潔的二叉樹秕豫。
分類回歸樹算法(Classification and Regression Trees,簡稱CART算法)是一種基于二分遞歸分割技術的算法。該算法是將當前的樣本集抗愁，分為兩個樣本子集馁蒂，這樣做就使得每一個非葉子節(jié)點最多只有兩個分支。因此蜘腌，使用CART
算法所建立的決策樹是一棵二叉樹沫屡，樹的結構簡單，與其它決策樹算法相比撮珠，由該算法生成的決策樹模型分類規(guī)則較少沮脖。
CART分類算法的基本思想是：對訓練樣本集進行遞歸劃分自變量空間，并依次建立決策樹模型芯急，然后采用驗證數(shù)據(jù)的方法進行樹枝修剪勺届，從而得到一顆符合要求的決策樹分類模型。
CART分類算法和C4.5算法一樣既可以處理離散型數(shù)據(jù)娶耍，也可以處理連續(xù)型數(shù)據(jù)免姿。CART分類算法是根據(jù)基尼(gini)系
數(shù)來選擇測試屬性，gini系數(shù)的值越小榕酒，劃分效果越好胚膊。設樣本集合為T，則T的gini系數(shù)值可由下式計算：
CART算法優(yōu)點：除了具有一般決策樹的高準確性想鹰、高效性紊婉、模式簡單等特點外，還具有一些自身的特點辑舷。
如喻犁，CART算法對目標變量和預測變量在概率分布上沒有要求，這樣就避免了因目標變量與預測變量概率分布的不同造成的結果何缓；CART算法能夠處理空缺值肢础，這樣就避免了因空缺值造成的偏差；CART算法能夠處理孤立的葉子結點歌殃，這樣可以避免因為數(shù)據(jù)集中與其它數(shù)據(jù)集具有不同的屬性的數(shù)據(jù)對進一步分支產(chǎn)生影響乔妈；CART算法使用的是二元分支，能夠充分地運用數(shù)據(jù)集中的全部數(shù)據(jù)氓皱，進而發(fā)現(xiàn)全部樹的結構路召；比其它模型更容易理解，從模型中得到的規(guī)則能獲得非常直觀的解釋波材。
CART算法缺點：CART算法是一種大容量樣本集挖掘算法股淡，當樣本集比較小時不夠穩(wěn)定；要求被選擇的屬性只能產(chǎn)生兩個子結點廷区，當類別過多時唯灵，錯誤可能增加得比較快。
2.6 sklearn算法的參數(shù)說明：
sklearn.tree.DecisionTreeClassifier
skleanr決策樹模型參數(shù)含義如下所示：
criterion：gini或者entropy,前者是基尼系數(shù)隙轻，后者是信息熵埠帕。
splitter： best or random 前者是在所有特征中找最好的切分點后者是在部分特征中垢揩，默認的”best”適合樣本量不大的時候，而如果樣本數(shù)據(jù)量非常大敛瓷，此時決策樹構建推薦”random” 叁巨。
max_features：None（所有），log2呐籽，sqrt锋勺，N 特征小于50的時候一般使用所有的
max_depth： int or None, optional (default=None) 設置決策隨機森林中的決策樹的最大深度，深度越大狡蝶，越容易過擬合庶橱，推薦樹的深度為：5-20之間。
min_samples_split：設置結點的最小樣本數(shù)量贪惹，當樣本數(shù)量可能小于此值時苏章，結點將不會在劃分。
min_samples_leaf： 這個值限制了葉子節(jié)點最少的樣本數(shù)馍乙，如果某葉子節(jié)點數(shù)目小于樣本數(shù)布近，則會和兄弟節(jié)點一起被剪枝。
min_weight_fraction_leaf： 這個值限制了葉子節(jié)點所有樣本權重和的最小值丝格，如果小于這個值撑瞧，則會和兄弟節(jié)點一起被剪枝默認是0，就是不考慮權重問題显蝌。
max_leaf_nodes： 通過限制最大葉子節(jié)點數(shù)预伺，可以防止過擬合，默認是"None”曼尊，即不限制最大的葉子節(jié)點
數(shù)酬诀。
class_weight： 指定樣本各類別的的權重，主要是為了防止訓練集某些類別的樣本過多導致訓練的決策樹過于偏向這些類別骆撇。這里可以自己指定各個樣本的權重瞒御，如果使用“balanced”，則算法會自己計算權重神郊，樣本量少的類別所對應的樣本權重會高肴裙。
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
**所以雄右，按先按好友密度劃分的信息增益比按真實頭像劃分的大纺讲。應先按好友密度劃分。
