pythonid3演算法

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

要弄清楚這個問題，首先要弄懂決策樹三大流行演算法ID3、C4.5和CART的原理，以及sklearn框架下DecisionTreeClassifier的幫助文檔。
3個演算法的主要區別在於度量信息方法、選擇節點特徵還有分支數量的不同。
ID3，採用熵（entropy）來度量信息不確定度，選擇「信息增益」最大的作為節點特徵，它是多叉樹，即一個節點可以有多個分支。
C4.5，同樣採用熵（entropy）來度量信息不確定度，選擇「信息增益比」最大的作為節點特徵，同樣是多叉樹，即一個節點可以有多個分支。
CART，採用基尼指數（Gini index）來度量信息不純度，選擇基尼指數最小的作為節點特徵，它是二叉樹，即一個節點只分兩支。
然後你認真閱讀sklearn的DecisionTreeClassifier的幫助文檔，可以發現，度量信息的方法默認是Gini，但可以改成entropy，請按需選擇；構建的樹是二叉樹；可以通過設置max_deepth、max_leaf等來實現「剪枝」，這是根據CART的損失函數減少的理論進行的。
所以總結說，如果信息度量方法按照默認的設置，那麼sklearn所用的決策樹分類器就是CART，如果改成了entropy，那麼只是使用了別的度量方法而已。其實兩者差不多。

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

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

C. ML - 決策樹(decision tree)

機器學習中分類和預測演算法的評估：

判定樹是一個類似於流程圖的樹結構：其中，每個內部結點表示在一個 屬性上的測試 ，每個分支代表一個 屬性輸出 ，而每個樹葉結點代表 類或類分布 。樹的最頂層是根結點。
機器學習中分類方法中的一個重要演算法

信息和抽象，如何度量？

1948年，香農提出了 」信息熵(entropy)「的概念

一條信息的信息量大小和它的不確定性有直接的關系，要搞清楚一件非常非常不確定的事情，或者

是我們一無所知的事情，需要了解大量信息==> 信息量的度量就等於不確定性的多少

例子：猜世界盃冠軍，假如一無所知，猜多少次？

每個隊奪冠的幾率不是相等的

比特(bit)來衡量信息的多少

變數的不確定性越大，熵也就越大

3.1 決策樹歸納演算法 （ ID3 ）

1970-1980， J.Ross. Quinlan, ID3演算法

選擇屬性（A為age時）判斷結點

信息獲取量(Information Gain) ：
Gain(A) = Info(D) - Infor_A(D)
Gain(A) =按yes/no分的熵 - 按A屬性分類的熵

通過A來作為節點分類獲取了多少信息

類似
Gain(income) = 0.029
Gain(student) = 0.151
Gain(credit_rating)=0.048
所以，選擇age作為第一個根節點

重復。。。

演算法：

*其他演算法：

C4.5 : Quinlan

Classification and Regression Trees (CART): (L. Breiman, J. Friedman, R. Olshen, C. Stone)

共同點：都是貪心演算法，自上而下(Top-down approach)

區別：屬性選擇度量方法不同： C4.5 （gain ratio), CART(gini index), ID3 (Information Gain)

先剪枝

後剪枝

直觀，便於理解，小規模數據集有效

處理連續變數不好（離散化，閾值選擇對結果影響大）

類別較多時，錯誤增加的比較快

可規模性一般

1. Python

2. Python機器學習的庫： scikit-learn

2.1： 特性：

簡單高效的數據挖掘和機器學習分析

對所有用戶開放，根據不同需求高度可重用性

基於Numpy, SciPy和matplotlib

開源，商用級別：獲得 BSD許可

2.2 覆蓋問題領域：

分類（classification), 回歸（regression), 聚類（clustering), 降維(dimensionality rection)

模型選擇(model selection), 預處理(preprocessing)

3. 使用用scikit-learn

安裝scikit-learn: pip, easy_install, windows installer

安裝必要package：numpy， SciPy和matplotlib， 可使用 Anaconda (包含numpy, scipy等科學計算常用package）

4. 例子：

文檔： http://scikit-learn.org/stable/moles/tree.html

安裝 Graphviz： http://www.graphviz.org/
配置環境變數
轉化dot文件至pdf可視化決策樹：dot -Tpdf iris.dot -o outpu.pdf

D. 決策樹(decisionTree)

決策樹(decisionTree)是一種基本的分類和回歸方法。此文僅討論用於分類方法的決策樹。

決策樹的學習通常分為3步：

決策樹的學習的思想主要源於

定義決策樹 ：

分類決策樹模型是一種描述對實例進行分類的樹形結構。決策樹由結點(node)和有向邊(directed edge)組成。結點又分為內部結點(internal node)和葉結點(leaf node)。內部結點表示一個特徵或屬性，葉結點表示一個類。
形如：

其中，圓表示內部結點，方框表示葉結點。

if-then規則，簡單來說就是 ：

舉例：對於一個蘋果，外表是紅色的是紅蘋果，外表是綠色的是青蘋果。可以表示為：

if-then規則集合具有一個重要的性質：

這就是說每一個實例都被一條路徑或規則覆蓋，並且只被一條路徑或規則覆蓋。這里所謂的覆蓋是指實例的特徵與路徑上的特徵一致，或實例滿足規則的條件。

給定數據集：

其中， 為輸入實例（特徵向量），含有 個特徵， 為類標記， , 為樣本容量。

目標 ：
根據給定的訓練數據集構建一個決策樹模型，使它能夠對實例進行正確分類。

特徵選擇在於選取對訓練數據具有分類能力的特徵，這樣可以提高決策樹學習的效率。

如果我們利用某一個特徵進行分類的結果與隨機分類的結果沒什麼很大的差別的話，則稱這個特徵沒有分類能力。

那麼問題來了，怎麼選擇特徵呢？

通常特徵選擇的准則是

下面通過例子來說明一下。

目標 ：
希望通過所給的訓練集數據，學習一個貸款申請的決策樹。當新的客戶提出貸款申請的時候，根據申請人的特徵利用決策樹決定是否批准貸款申請。

可見這里共有4個特徵可供選擇。用特徵選擇的准則是 。接下來介紹 。

：
熵是表示隨機變數不確定性的度量。

設 是一個取有限個值的隨機變數，其概率分布為

則隨機變數 的熵定義為

若 ，則定義 。通常對數取以2為底，或是以 為底，熵的單位分布為比特（bit）或是納特（nat）。
由上式可知，熵只依賴 的分布，而已 的值無關，則 的熵還可記作 ，即

則從定義可知

當隨機變數只取2個值的時候，例如 時， 的分布為

熵為

熵隨概率變化的曲線為

當 或 時 ，隨機變數完全沒有不確定性，當 時 ，熵取值最大，隨機變數不確定性最大。

設隨機變數 ，其聯合概率分布

條件熵 表示在已知隨機變數 的條件下隨機變數 的不確定性。隨機變數 給定條件下隨機變數 的條件熵(conditional entropy)，定義為 給定條件下 的條件概率分布的熵對 的數學期望

信息增益
特徵 對訓練集 的信息增益

根據信息增益准則的特徵選擇方法：對訓練集 ，計算其每個特徵的信息增益，並比較大小，選擇信息增益最大的特徵。

前期定義各個量：

信息增益的演算法
輸入：訓練集 和特徵 ；
輸出：特徵 對訓練集 的信息增益

回看剛才的例子，

解 ：

這一次我很無聊的想用一下.csv文件類型。

所以訓練數據集部分如下，我存在一個loan.csv文件里了。對.csv文件的各種處理一般由python的pandas模塊完成。

第一步，導入相關模塊

第二步，讀入數據

若是使用jupyter，可以即刻查看一下數據，和數據標簽。

可以看出，除了'ID'之外前4個標簽 'age', 'work', 'own house', 'Credit conditions'為我們一直在說的特徵 ，而最後一個標簽'label'是我們所說的類 ，所以要處理一下這些標簽，

第三步，計算訓練集 的熵 ：

這里會用到pandas的一個統計數據的功能， groupby(by = [列]).groups ，將數據統計成字典的形式，這么說比較抽象，看下圖，將我們用pandas讀入的data，分為2類， ， Index 表示索引，即第0，1，4，5，6，14（python計數從0開始）個數據的 ，第2，3，7，8，9，10，11，12，13個數據的 .

那麼計算訓練集 的熵

第四步，計算特徵 對數據集 的條件熵

第五步 ，計算信息增益

輸入：訓練集 和特徵 和閾值 ；
輸出：決策樹
(1) 中所有實例都屬於同一類 ，則 為單結點樹，並將類 作為該結點的類標記，返回 ；
(2) 若 ，則 為單結點樹，並將 中實例數最大的類 作為該結點的類標記，返回 ；
(3)否則，按照上述信息增益的演算法，計算 中各個特徵對 的信息增益，選擇信息增益最大的特徵 ；
(4)如果特徵 的信息增益小於閾值 ，將置 為單結點樹，並將 中實例數最大的類 作為該結點的類標記，返回 ；
(5)否則，對 的每一個可能值 ，依 將 分割為若干非空子集 ，將 中實例數最大的類 作為該結點的類標記，構建子結點，由結點及其子結點構成樹 ，返回 ；
(6)對第 個子結點，以 為訓練集，以 為特徵集，遞歸的調用步驟(1)~步驟(5)，得到子樹 ，返回 。

對上述表的訓練集數據，利用ID3演算法建立決策樹。

解 ：

第一次迭代 ：

【特徵：有自己的房子】將數據集 劃分為2個子集 （有自己的房子）和 （沒有自己的房子），觀察一下 和 ：

：

由於 所有實例都屬於同一類 ，所以它是一個葉結點，結點的類標記為「是」。

：

對於 則需從特徵 中選擇新的特徵。

第二次迭代 ：

將 看作新的數據集 。【特徵：有工作】有2個可能值，劃分為2個子集 （有工作）和 （沒有工作），觀察一下 和 ：

：

由於 所有實例都屬於同一類 ，所以它是一個葉結點，結點的類標記為「是」。

：

E. 人工智慧到底是學些什麼

從大的技術層面來看，人工智慧的知識體系主要涉及到六個大的學習方向，包括自然語言處理、計算機視覺、機器學習（深度學習）、自動推理、知識表示和機器人學，這些方向各有體系且聯系緊密。

人工智慧是典型的交叉學科，涉及到數學、哲學、控制學、計算機、經濟學、神經學和語言學等學科，同時學習人工智慧還需要具有一定的實驗環境，對於數據、算力和演算法都有一定的要求，所以當前人工智慧領域的人才培養依然以研究生教育為主。

簡介

對於初學者來說，如果想入門人工智慧領域，可以從機器學習入手，一方面機器學習的知識體系相對比較容易理解，另一方面機器學習的應用場景也比較多，機器學習也是大數據分析的兩種常見方式之一。

機器學習的步驟涉及到數據收集、演算法設計、演算法實現、演算法訓練、演算法驗證和演算法應用，這個過程需要學習編程語言、數據整理和演算法設計這三大塊內容。

編程語言可以從Python語言開始學起，目前Python語言在機器學習領域的應用也比較普遍，有大量的案例可以參考。在學習的初期完全可以採用一些公開的數據集，這樣也方便做結果對比，而演算法可以從基礎的常見演算法入手，比如決策樹、樸素貝葉斯、支持向量機等等。

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

#這里有一個示例，你可以看一下。
#http://scikit-learn.org/stable/moles/tree.html
>>>fromIPython.displayimportImage
>>>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())

G. 決策樹（Decision Tree）

決策樹是一種非參數有監督的機器學習方法，可以用於解決回歸問題和分類問題。通過學習已有的數據，計算得出一系列推斷規則來預測目標變數的值，並用類似流程圖的形式進行展示。決策樹模型可以進行可視化，具有很強的可解釋性，演算法容易理解，以決策樹為基礎的各種集成演算法在很多領域都有廣泛的應用。

熵的概念最早起源於物理學，用於度量一個熱力學系統的無序程度。在資訊理論裡面，信息熵代表著一個事件或一個變數等所含有的信息量。 在信息世界，熵越高，則能傳輸越多的信息，熵越低，則意味著傳輸的信息越少。

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

我們可以用計算事件發生的概率來計算事件的信息，又稱「香農信息」（ Shannon Information ）。一個離散事件x的信息可以表示為：
h(x) = -log(p(x))
p() 代表事件x發生的概率， log() 為以二為底的對數函數，即一個事件的信息量就是這個事件發生的概率的負對數。選擇以二為底的對數函數代表計算信息的單位是二進制。因為概率p(x)小於1，所以負號就保證了信息熵永遠不為負數。當事件的概率為1時，也就是當某事件百分之百發生時，信息為0。

熵（ entropy ），又稱「香農熵」（ Shannon entropy ），表示一個隨機變數的分布所需要的平均比特數。一個隨機變數的信息熵可以表示為：
H(x) = -sum(each k in K p(k)log(p(k)))
K表示變數x所可能具有的所有狀態（所有事件），將發生特定事件的概率和該事件的信息相乘，最後加和，即可得到該變數的信息熵。可以理解為，信息熵就是平均而言發生一個事件我們得到的信息量大小。所以數學上，信息熵其實是事件信息量的期望。

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

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

由以上的香農信息公式可知，信息熵主要有三條性質：
- 單調性 。發生概率越高的事件，其所攜帶的信息熵越低。比如一個真理的不確定性是極低的，那麼它所攜帶的信息熵就極低。
- 非負性 。信息熵不能為負。單純從邏輯層面理解，如果得知了某個信息後，卻增加了不確定性，這也是不合邏輯的。
- 可加性 。即多隨機事件同時發生存在的總不確定性的量度是可以表示為各事件不確定性的量度的和。

若兩事件A和B同時發生，兩個事件相互獨立。 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 ），即一個隨機變數包含另一個隨機變數信息量的度量。即已知X的情況下，Y的分布是否會改變。

可以理解為，兩個隨機變數的互信息度量了兩個變數間相互依賴的程度。X 和 Y的互信息可以表示為：
I(X;Y) = H(X) - H(X|Y)
H(X)是X的信息熵，H(X|Y)是已知Y的情況下，X的信息熵。結果的單位是比特。
簡單來說，互信息的性質為：
- I(X;Y)>=0 互信息永遠不可能為負
- H(X) - H(X|Y) = I(X;Y) = I (Y;X) = H(Y) - H(Y|X) 互信息是對稱的
-當X，Y獨立的時候， I(X;Y) = 0 互信息值越大，兩變數相關性越強。
-當X，Y知道一個就能推斷另一個的時候， I(X;Y) = H(Y) = H(X)

在數據科學中，互信息常用於特徵篩選。在通信系統中互信息也應用廣泛。在一個點到點的通信系統中，發送信號為X，通過信道後，接收端接收到的信號為Y，那麼信息通過信道傳遞的信息量就是互信息 I(X,Y) 。根據這個概念，香農推導出信道容量（即臨界通信傳輸速率的值）。

信息增益（ Information Gain ）是用來按照一定規則劃分數據集後，衡量信息熵減少量的指數。

那數據集的信息熵又是怎麼計算的呢？比如一個常見的0,1二分類問題，我們可以計算它的熵為：
Entropy = -(p(0) * log(P(0)) + p(1) * log(P(1)))
當該數據集為50/50的數據集時，它的信息熵是最大的（1bit）。而10/90的數據集將會大大減少結果的不確定性，減小數據集的信息熵（約為0.469bit）。

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

信息增益是提供了一種可以使用信息熵計算數據集經過一定的規則（比如決策樹中的一系列規則）進行數據集分割後信息熵的變化的方法。
IG(S,a) = H(S) - H(S|a)
其中，H(s) 是原數據集S的信息熵（在做任何改變之前），H(S|a)是經過變數a的一定分割規則。所以信息增益描述的是數據集S變換後所節省的比特數。

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

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

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

這種時候，信息增益率就起到了很重要的作用。
gR(D,A)=g(D,A)/HA(D)
HA(D) 又叫做特徵A的內部信息，HA(D)其實像是一個衡量以特徵AA的不同取值將數據集D分類後的不確定性的度量。如果特徵A的取值越多，那麼不確定性通常會更大，那麼HA(D)的值也會越大，而1/HA(D)的值也會越小。這相當於是在信息增益的基礎上乘上了一個懲罰系數。即 gR(D,A)=g(D,A)∗懲罰系數 。

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

舉例來說，如果有綠色和藍色兩類數據點，各佔一半（藍色50%，綠色50%）。那麼我們隨機分類，有以下四種情況：
-分為藍色，但實際上是綠色（❌），概率25%
-分為藍色，實際上也是藍色（✔️），概率25%
-分為綠色，實際上也是綠色（✔️），概率25%
-分為綠色，但實際上是藍色（❌），概率25%
那麼將任意一個數據點分錯的概率為25%+25% = 50%。基尼不純度為0.5。

在特徵選擇中，我們可以選擇加入後使數據不純度減少最多的特徵。

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

決策樹其實是一種圖結構，由節點和邊構成。
-根節點：只有出邊沒有入邊。包含樣本全集，表示一個對樣本最初的判斷。
-內部節點：一個入邊多個出邊。表示一個特徵或是屬性。每個內部節點都是一個判斷條件，包含數據集中從根節點到該節點所有滿足條件的數據的集合。
-葉節點：一個入邊無出邊。表示一個類，對應於決策結果。

決策樹的生成主要分為三個步驟：
1. 節點的分裂 ：當一個節點不夠純（單一分類佔比不夠大或者說信息熵較大）時，則選擇將這一節點進行分裂。
2. 決策邊界的確定 ：選擇正確的決策邊界（ Decision Boundary ），使分出的節點盡量純，信息增益（熵減少的值）盡可能大。
3. 重復及停止生長 ：重復1，2步驟，直到純度為0或樹達到最大深度。為避免過擬合，決策樹演算法一般需要制定樹分裂的最大深度。到達這一深度後，即使熵不等於0，樹也不會繼續進行分裂。

下面以超級知名的鳶尾花數據集舉例來說明。
這個數據集含有四個特徵：花瓣的長度（ petal length ）、花瓣的寬度( petal width )、花萼的長度( sepal length )和花萼的寬度( sepal width )。預測目標是鳶尾花的種類 iris setosa, iris versicolor 和 iris virginica 。

建立決策樹模型的目標是根據特徵盡可能正確地將樣本劃分到三個不同的「陣營」中。

根結點的選擇基於全部數據集，使用了貪婪演算法：遍歷所有的特徵，選擇可以使信息熵降到最低、基尼不純度最低的特徵。

如上圖，根節點的決策邊界為' petal width = 0.8cm '。那麼這個決策邊界是怎麼決定的呢？
-遍歷所有可能的決策邊界（需要注意的是，所有可能的決策邊界代表的是該子集中該特徵所有的值，不是以固定增幅遍歷一個區間內的所有值！那樣很沒有必要的～）
-計算新建的兩個子集的基尼不純度。
-選擇可以使新的子集達到最小基尼不純度的分割閾值。這個「最小」可以指兩個子集的基尼不純度的和或平均值。

ID3是最早提出的決策樹演算法。ID3演算法的核心是在決策樹各個節點上根據 信息增益 來選擇進行劃分的特徵，然後遞歸地構建決策樹。
- 缺點 ：
（1）沒有剪枝
（2）只能用於處理離散特徵
（3）採用信息增益作為選擇最優劃分特徵的標准，然而信息增益會偏向那些取值較多的特徵(例如，如果存在唯一標識屬性身份證號，則ID3會選擇它作為分裂屬性，這樣雖然使得劃分充分純凈，但這種劃分對分類幾乎毫無用處。)

C4.5 與ID3相似，但對ID3進行了改進：
-引入「悲觀剪枝」策略進行後剪枝
-信息增益率作為劃分標准
-將連續特徵離散化，假設 n 個樣本的連續特徵 A 有 m 個取值，C4.5 將其排序並取相鄰兩樣本值的平均數共 m-1 個劃分點，分別計算以該劃分點作為二元分類點時的信息增益，並選擇信息增益最大的點作為該連續特徵的二元離散分類點；
-可以處理缺失值

對於缺失值的處理可以分為兩個子問題：
（1）在特徵值缺失的情況下進行劃分特徵的選擇？（即如何計算特徵的信息增益率）
C4.5 中對於具有缺失值特徵，用沒有缺失的樣本子集所佔比重來折算；
（2）選定該劃分特徵，對於缺失該特徵值的樣本如何處理？（即到底把這個樣本劃分到哪個結點里）
C4.5 的做法是將樣本同時劃分到所有子節點，不過要調整樣本的權重值，其實也就是以不同概率劃分到不同節點中。

（1）剪枝策略可以再優化；
（2）C4.5 用的是多叉樹，用二叉樹效率更高；
（3）C4.5 只能用於分類；
（4）C4.5 使用的熵模型擁有大量耗時的對數運算，連續值還有排序運算；
（5）C4.5 在構造樹的過程中，對數值屬性值需要按照其大小進行排序，從中選擇一個分割點，所以只適合於能夠駐留於內存的數據集，當訓練集大得無法在內存容納時，程序無法運行。

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

CART 包含的基本過程有 分裂，剪枝和樹選擇 。
分裂 ：分裂過程是一個二叉遞歸劃分過程，其輸入和預測特徵既可以是連續型的也可以是離散型的，CART 沒有停止准則，會一直生長下去；
剪枝 ：採用「代價復雜度」剪枝，從最大樹開始，每次選擇訓練數據熵對整體性能貢獻最小的那個分裂節點作為下一個剪枝對象，直到只剩下根節點。CART 會產生一系列嵌套的剪枝樹，需要從中選出一顆最優的決策樹；
樹選擇 ：用單獨的測試集評估每棵剪枝樹的預測性能（也可以用交叉驗證）。

（1）C4.5 為多叉樹，運算速度慢，CART 為二叉樹，運算速度快；
（2）C4.5 只能分類，CART 既可以分類也可以回歸；
（3）CART 使用 Gini 系數作為變數的不純度量，減少了大量的對數運算；
（4）CART 採用代理測試來估計缺失值，而 C4.5 以不同概率劃分到不同節點中；
（5）CART 採用「基於代價復雜度剪枝」方法進行剪枝，而 C4.5 採用悲觀剪枝方法。

（1）決策樹易於理解和解釋，可以可視化分析，容易提取出規則
（2）可以同時處理分類型和數值型數據
（3）可以處理缺失值
（4）運行速度比較快（使用Gini的快於使用信息熵，因為信息熵演算法有log）

（1）容易發生過擬合（集成演算法如隨機森林可以很大程度上減少過擬合）
（2）容易忽略數據集中屬性的相互關聯；
（3）對於那些各類別樣本數量不一致的數據，在決策樹中，進行屬性劃分時，不同的判定準則會帶來不同的屬性選擇傾向。

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

參考資料鏈接：
1. https://machinelearningmastery.com/what-is-information-entropy/
2. https://zhuanlan.hu.com/p/29679277
3. https://machinelearningmastery.com/information-gain-and-mutual-information/
4. https://victorzhou.com/blog/gini-impurity/
5. https://sci2s.ugr.es/noisydata
6. https://towardsdatascience.com/understanding-decision-trees-once-and-for-all-2d891b1be579
7. https://blog.csdn.net/weixin_36586536/article/details/80468426
8. https://zhuanlan.hu.com/p/85731206

H. 人工智慧是學習什麼

1、學習並掌握一些數學知識

高等數學是基礎中的基礎，一切理工科都需要這個打底，數據挖掘、人工智慧、模式識別此類跟數據打交道的又尤其需要多元微積分運算基礎。

線性代數很重要，一般來說線性模型是你最先要考慮的模型，加上很可能要處理多維數據，你需要用線性代數來簡潔清晰的描述問題，為分析求解奠定基礎。

概率論、數理統計、隨機過程更是少不了，涉及數據的問題，不確定性幾乎是不可避免的，引入隨機變數順理成章，相關理論、方法、模型非常豐富。很多機器學習的演算法都是建立在概率論和統計學的基礎上的，比如貝葉斯分類器、高斯隱馬爾可夫鏈。

再就是優化理論與演算法，除非你的問題是像二元一次方程求根那樣有現成的公式，否則你將不得不面對各種看起來無解但是要解的問題，優化將是你的GPS為你指路。

以上這些知識打底，就可以開拔了，針對具體應用再補充相關的知識與理論，比如說一些我覺得有幫助的是數值計算、圖論、拓撲，更理論一點的還有實/復分析、測度論，偏工程類一點的還有信號處理、數據結構。

2、掌握經典機器學習理論和演算法

如果有時間可以為自己建立一個機器學習的知識圖譜，並爭取掌握每一個經典的機器學習理論和演算法，我簡單地總結如下：

1) 回歸演算法：常見的回歸演算法包括最小二乘法（OrdinaryLeast Square），邏輯回歸（Logistic Regression），逐步式回歸（Stepwise Regression），多元自適應回歸樣條（MultivariateAdaptive Regression Splines）以及本地散點平滑估計（Locally Estimated Scatterplot Smoothing）；

2) 基於實例的演算法：常見的演算法包括 k-Nearest Neighbor(KNN), 學習矢量量化（Learning Vector Quantization， LVQ），以及自組織映射演算法（Self-Organizing Map ， SOM）；

3) 基於正則化方法：常見的演算法包括：Ridge Regression， Least Absolute Shrinkage and Selection Operator（LASSO），以及彈性網路（Elastic Net）；

4) 決策樹學習：常見的演算法包括：分類及回歸樹（ClassificationAnd Regression Tree， CART）， ID3 (Iterative Dichotomiser 3)， C4.5， Chi-squared Automatic Interaction Detection(CHAID), Decision Stump, 隨機森林（Random Forest）， 多元自適應回歸樣條（MARS）以及梯度推進機（Gradient Boosting Machine， GBM）；

5) 基於貝葉斯方法：常見演算法包括：樸素貝葉斯演算法，平均單依賴估計（AveragedOne-Dependence Estimators， AODE），以及Bayesian Belief Network（BBN）；

6) 基於核的演算法：常見的演算法包括支持向量機（SupportVector Machine， SVM）， 徑向基函數（Radial Basis Function ，RBF)， 以及線性判別分析（Linear Discriminate Analysis ，LDA)等；

7) 聚類演算法：常見的聚類演算法包括 k-Means演算法以及期望最大化演算法（Expectation Maximization， EM）；

8) 基於關聯規則學習：常見演算法包括 Apriori演算法和Eclat演算法等；

9) 人工神經網路：重要的人工神經網路演算法包括：感知器神經網路（PerceptronNeural Network）, 反向傳遞（Back Propagation）， Hopfield網路，自組織映射（Self-OrganizingMap, SOM）。學習矢量量化（Learning Vector Quantization， LVQ）；

10) 深度學習：常見的深度學習演算法包括：受限波爾茲曼機（RestrictedBoltzmann Machine， RBN）， Deep Belief Networks（DBN），卷積網路（Convolutional Network）, 堆棧式自動編碼器（Stacked Auto-encoders）；

11) 降低維度的演算法：常見的演算法包括主成份分析（PrincipleComponent Analysis， PCA），偏最小二乘回歸（Partial Least Square Regression，PLS）， Sammon映射，多維尺度（Multi-Dimensional Scaling, MDS）, 投影追蹤（ProjectionPursuit）等；

12) 集成演算法：常見的演算法包括：Boosting， Bootstrapped Aggregation（Bagging），AdaBoost，堆疊泛化（Stacked Generalization， Blending），梯度推進機（GradientBoosting Machine, GBM），隨機森林（Random Forest）。

3、掌握一種編程工具，比如Python
一方面Python是腳本語言，簡便，拿個記事本就能寫，寫完拿控制台就能跑；另外，Python非常高效，效率比java、r、matlab高。matlab雖然包也多，但是效率是這四個裡面最低的。

4、了解行業最新動態和研究成果，比如各大牛的經典論文、博客、讀書筆記、微博微信等媒體資訊。

5、買一個GPU，找一個開源框架，自己多動手訓練深度神經網路，多動手寫寫代碼，多做一些與人工智慧相關的項目。

6、選擇自己感興趣或者工作相關的一個領域深入下去
人工智慧有很多方向，比如NLP、語音識別、計算機視覺等等，生命有限，必須得選一個方向深入的鑽研下去，這樣才能成為人工智慧領域的大牛，有所成就。

根據網路給的定義，人工智慧（Artificial Intelligence），英文縮寫為AI。它是研究、開發用於模擬、延伸和擴展人的還能的理論、方法、技術及應用系統的一門新的技術科學。
網路關於人工智慧的定義詳解中說道：人工智慧是計算機的一個分支，二十世紀七十年代以來被稱為世界三大尖端技術之一（空間技術、能源技術、人工智慧）。也被認為是二十一世紀三大尖端技術（基因工程、納米科學、人工智慧）之一。這是因為近三十年來它獲得了迅速的發展，在很多學科領域都獲得了廣泛應用，並取得了豐碩的成果，人工智慧已逐步成為一個獨立的分支，無論在理論和實踐上都已自成一個系統。
綜上，從定義上講，人工智慧是一項技術。

I. 數據分析師—技術面試

數據分析師—技術面試
三月份開始找實習，到現在已經有半年的時間了，在這半年的時間中，該經歷的基本上都已經經歷，春招實習時候，拿到了7個offer，校招時候，成功的拿下一份心儀的工作，結束了我的秋招旅程。對於面試，技術層面即演算法、軟體等等，業務層面就是忽悠（畢竟沒有做過完整的項目），但是也要有自己的邏輯和思考方式（這方面我也有很大的欠缺），下面將自己的面試經歷梳理為技術層面和業務層面，來分享給大家。
技術面試
一、軟體

1. R語言的文件讀取：csv文件的讀取方式（read.csv），txt文件的讀取方式（read.table）
2. R語言中一些小函數的作用
①apply函數：1代表調用每一行的函數，0代表調用每一列的函數（注意其用法和Python的區別）
②runif函數：生成均勻分布的隨機數
③sample（，return = TRUE）：隨機有放回的抽樣
3. Python中list列表和元組的最大區別：元組的值不可以改變，但是列表的值是可以改變的。
4.資料庫中表的連接方式
①內部連接：inner join
②外部連接：outer join
③左連接：left join
註：對於數據分析，建議大家無論是R，Python，sql都有自己一套流程化的體系，這一體系可以很好的幫助你解決實際中的問題。
二、演算法

對於演算法（分類，聚類，關聯等），更是建議大家有一套流程化的體系，在面試演算法的時候，是一個依次遞進的過程，不要給自己挖坑，相反，更要將自己的優勢發揮的淋漓盡致，把自己會的東西全部釋放出來。
下面我將自己的所有面試串聯起來，給大家分享一下，僅供參考。
面試官：小張同學，你好，看了你的簡歷，對相關演算法還是略懂一些，下面開始我們的面試，有這么一個場景，在一個樣本集中，其中有100個樣本屬於A，9900個樣本屬於B，我想用決策樹演算法來實現對AB樣本進行區分，這時會遇到什麼問題：
小張：欠擬合現象，因為在這個樣本集中，AB樣本屬於嚴重失衡狀態，在建立決策樹演算法的過程中，模型會更多的偏倚到B樣本的性質，對A樣本的性質訓練較差，不能很好的反映樣本集的特徵。
面試官：看你決策樹應該掌握的不錯，你說一下自己對於決策樹演算法的理解？
小張：決策樹演算法，無論是哪種，其目的都是為了讓模型的不確定性降低的越快越好，基於其評價指標的不同，主要是ID3演算法，C4.5演算法和CART演算法，其中ID3演算法的評價指標是信息增益，C4.5演算法的評價指標是信息增益率，CART演算法的評價指標是基尼系數。
面試官：信息增益，好的，這裡面有一個資訊理論的概念，你應該知道的吧，敘述一下
小張：香農熵，隨機變數不確定性的度量。利用ID3演算法，每一次對決策樹進行分叉選取屬性的時候，我們會選取信息增益最高的屬性來作為分裂屬性，只有這樣，決策樹的不純度才會降低的越快。
面試官：OK，你也知道，在決策樹無限分叉的過程中，會出現一種現象，叫過擬合，和上面說過的欠擬合是不一樣的，你說一下過擬合出現的原因以及我們用什麼方法來防止過擬合的產生？
小張：對訓練數據預測效果很好，但是測試數據預測效果較差，則稱出現了過擬合現象。對於過擬合現象產生的原因，有以下幾個方面，第一：在決策樹構建的過程中，對決策樹的生長沒有進行合理的限制（剪枝）；第二：在建模過程中使用了較多的輸出變數，變數較多也容易產生過擬合；第三：樣本中有一些雜訊數據，雜訊數據對決策樹的構建的干擾很多，沒有對雜訊數據進行有效的剔除。對於過擬合現象的預防措施，有以下一些方法，第一：選擇合理的參數進行剪枝，可以分為預剪枝後剪枝，我們一般用後剪枝的方法來做；第二：K-folds交叉驗證，將訓練集分為K份，然後進行K次的交叉驗證，每次使用K-1份作為訓練樣本數據集，另外的一份作為測試集合；第三：減少特徵，計算每一個特徵和響應變數的相關性，常見的為皮爾遜相關系數，將相關性較小的變數剔除，當然還有一些其他的方法來進行特徵篩選，比如基於決策樹的特徵篩選，通過正則化的方式來進行特徵選取等。
面試官：你剛剛前面有提到預剪枝和後剪枝，當然預剪枝就是在決策樹生成初期就已經設置了決策樹的參數，後剪枝是在決策樹完全建立之後再返回去對決策樹進行剪枝，你能否說一下剪枝過程中可以參考的某些參數？
小張：剪枝分為預剪枝和後剪枝，參數有很多，在R和Python中都有專門的參數來進行設置，下面我以Python中的參數來進行敘述，max_depth（樹的高度），min_samples_split（葉子結點的數目），max_leaf_nodes（最大葉子節點數），min_impurity_split（限制不純度），當然R語言裡面的rpart包也可以很好的處理這個問題。
面試官：對了，你剛剛還說到了用決策樹來進行特徵的篩選，現在我們就以ID3演算法為例，來說一下決策樹演算法對特徵的篩選？
小張：對於離散變數，計算每一個變數的信息增益，選擇信息增益最大的屬性來作為結點的分裂屬性；對於連續變數，首先將變數的值進行升序排列，每對相鄰值的中點作為可能的分離點，對於每一個劃分，選擇具有最小期望信息要求的點作為分裂點，來進行後續的決策數的分裂。
面試官：你剛剛還說到了正則化，確實可以對過擬合現象來進行很好的調整，基於你自己的理解，來說一下正則化？
小張：這一塊的知識掌握的不是很好，我簡單說一下自己對這一塊的了解。以二維情況為例，在L1正則化中，懲罰項是絕對值之和，因此在坐標軸上會出現一個矩形，但是L2正則化的懲罰項是圓形，因此在L1正則化中增大了系數為0的機會，這樣具有稀疏解的特性，在L2正則化中，由於系數為0的機率大大減小，因此不具有稀疏解的特性。但是L1沒有選到的特性不代表不重要，因此L1和L2正則化要結合起來使用。
面試官：還可以吧！正則化就是在目標函數後面加上了懲罰項，你也可以將後面的懲罰項理解為范數。分類演算法有很多，邏輯回歸演算法也是我們經常用到的演算法，剛剛主要討論的是決策樹演算法，現在我們簡單聊一下不同分類演算法之間的區別吧！討論一下決策樹演算法和邏輯回歸演算法之間的區別？
小張：分為以下幾個方面：第一，邏輯回歸著眼於對整體數據的擬合，在整體結構上優於決策樹；但是決策樹採用分割的方法，深入到數據內部，對局部結構的分析是優於邏輯回歸；第二，邏輯回歸對線性問題把握較好，因此我們在建立分類演算法的時候也是優先選擇邏輯回歸演算法，決策樹對非線性問題的把握較好；第三，從本質來考慮，決策樹演算法假設每一次決策邊界都是和特徵相互平行或垂直的，因此會將特徵空間劃分為矩形，因而決策樹會產生復雜的方程式，這樣會造成過擬合現象；邏輯回歸只是一條平滑的邊界曲線，不容易出現過擬合現象。
面試官： 下面呢我們來聊一下模型的評估，演算法進行模型評估的過程中，常用的一些指標都有哪些，精度啊？召回率啊？ROC曲線啊？這些指標的具體含義是什麼？
小張：精度（precision），精確性的度量，表示標記為正例的元組占實際為正例的比例；召回率（recall），完全性的度量，表示為實際為正例的元組被正確標記的比例；ROC 曲線的橫坐標為假陽性，縱坐標為真陽性，值越大，表示分類效果越好。
（to be honest，這個問題第一次我跪了，雖然說是記憶一下肯定沒問題，但是當時面試的那個時候大腦是一片空白）
面試官：聚類分析你懂得的吧！在我們一些分析中，它也是我們經常用到的一類演算法，下面你介紹一下K-means演算法吧！
小張：對於K-means演算法，可以分為以下幾個步驟：第一，從數據點中隨機抽取K個數據點作為初始的聚類中心；第二：計算每個點到這K個中心點的距離，並把每個點分到距離其最近的中心中去；第三：求取各個類的均值，將這些均值作為新的類中心；第四：重復進行步驟二三過程，直至演算法結束，演算法結束有兩種，一種是迭代的次數達到要求，一種是達到了某種精度。
後記
面試的水很深，在數據分析技術面的時候問到的東西當然遠遠不止這些，因此在我們的腦子裡面一定要形成一個完整的體系，無論是對某一門編程語言，還是對數據挖掘演算法，在工作中都需要形成你的閉環，在面試中更是需要你形成閉環，如何更完美的包裝自己，自己好好總結吧！
附錄
R語言數據處理體系：數據簡單預處理個人總結
1、數據簡單查看
⑴查看數據的維度：dim
⑵查看數據的屬性：colnames
⑶查看數據類型：str
註：有一些演算法，比如說組合演算法，要求分類變數為因子型變數；層次聚類，要求是一個距離矩陣，可以通過str函數進行查看
⑷查看前幾行數據：head
註：可以初步觀察數據是不是有量綱的差異，會後續的分析做准備
⑸查看因子型變數的佔比情況：table/prop.table
註：可以為後續數據抽樣做准備，看是否產生類不平衡的問題
2、數據缺失值處理
⑴summary函數進行簡單的查看
⑵利用mice和VIM包查看數據缺失值情況，代表性函數： md.pattern、aggr
⑶caret包中的preProcess函數，可以進行缺失值的插補工作，有knn、袋裝、中位數方法
⑷missForest包中的missForest函數，可以用隨機森林的方法進行插補
⑸可以用回歸分析的方法完成缺失值插補工作
⑹如果樣本量很多，缺失的數據很少，可以選擇直接剔除的方法
3、數據異常值處理
⑴summary函數進行簡單的查看，比如：最大值、最小值等
⑵boxplot函數繪制箱線圖
4、數據抽樣
⑴sample函數進行隨機抽樣
⑵caret包中的createDataPartition()函數對訓練樣本和測試樣本進行等比例抽樣
⑶caret包中的createFold函數根據某一個指標進行等比例抽樣
⑷DMwR包中SMOTE函數可以解決處理不平衡分類問題
註：比如決策樹演算法中，如果樣本嚴重不平衡，那麼模型會出現欠擬合現象
5、變數的多重共線性處理
⑴結合業務，先刪除那些和分析無關的指標
⑵corrgram包的corrgram函數查看相關系數矩陣
⑶caret包中的findCorrelation函數查看多重共線性
⑷如果相關性太大，可以考慮刪除變數；如果變數比較重要，可以考慮主成分/因子分析進行降維處理

J. 向大神求教！python寫的決策樹的ID3演算法怎麼一直提示bestfeat=labels[bestfeat_index]超出索引啊！

1、對當前訓練集，計算各屬性的信息增益（假設有屬性A1,A2,…An）；
2、選擇信息增益最大的屬性Ak（1<=k<=n），作為根節點；
3、把在Ak處取值相同的例子歸於同一子集，作為該節點的一個樹枝，Ak取幾個值就得幾個子集；
4、若在某個子集中的所有樣本都是屬於同一個類型（本位只討論正(Y)、反(N)兩種類型的情況），則給該分支標上類型號作為葉子節點；
5、對於同時含有多種（兩種）類型的子集，則遞歸調用該演算法思路來完成樹的構造。