決策樹啟發性演算法

❶ 拉卡拉手機收款寶，都有什麼功能

您好，感謝您對拉卡拉的支持！

拉卡拉手機收款寶功能：刷卡收款、撤銷交易，信用卡還款、手機充值、轉賬匯款、余額查詢，交易查詢，及其他附加功能：計算器。

拉卡拉手機收款寶產品特點：

1、體積小：體積只有名片盒大小，可隨身攜帶；

2、價格低：售價遠遠低於市場上的POS價格，僅需299元；

3、開通簡單：無需繁瑣資料，10分鍾即可開通，即開即用；

4、移動收款：可全國移動收款，不受地域限制；

5、支持金融IC卡：支持帶有銀聯標志的磁條和晶元銀行卡；

6、藍牙連接：可通過藍牙與手機連接，擺脫數據線束縛；

7、電子簽購單：付款人手寫簽名確認交易，保障商戶權益；

您可以撥打拉卡拉客服熱線或者登陸拉卡拉天貓旗艦店和拉卡拉官網購買

若您還有其他問題您也可以通過以下方式聯系我們，我們將更加快速的幫您解決問題
1.拉卡拉微博：拉卡拉
2.拉卡拉微信：ilakala
3.拉卡拉熱線：

拉卡拉祝您生活愉快！

❷ 什麼是NP完全問題

在學習決策樹的時候，我們知道，其一大特點是：尋找最佳的決策樹是NP完成問題。什麼是NP完全問題，決策樹的這一特點又是什麼意思？

這里的NP其實是 Non-deterministic Polynomial 的縮寫，即多項式復雜程度的非確定性問題，NP完全問題有時也會簡稱為NP-C問題。與此概念相關的還有P類問題、NP類問題等。要理解什麼是NP完全問題，首先得從P類問題開始理解。

判定問題 是指回答結果輸出為 Yes 或 No 的問題，比如：3233是否可以寫成兩個大於1的數字的乘積？是否存在一條路線有且僅有一次的走過 七橋問題 的每一座橋？

在設計程序時，我們經常需要評估這個程序的時間復雜度，即衡量當問題規模變大後，程序執行所需的時間增長會有多快。如O(1)表示常數級別，即不管問題的規模變大多少倍，所耗的時間不會改變；O(N^2) 表示平方級別，即當問題規模增大至2倍時，所花費的時間則放大至4倍；O(2^N) 表示指數級別，即當問題規模倍數擴大時，所用時間會呈指數放大。

多項式時間 則是指O(1)、O(logN)、O(N^2) 等這類可用多項式表示的時間復雜度，通常我們認為計算機可解決的問題只限於多項式時間內。而O(2^N)、O(N!)這類非多項式級別的問題，其復雜度往往已經到了計算機都接受不了的程度。

NP類問題將問題分為求解和驗證兩個階段，問題的求解是非確定性的，無法在多項式時間內得到答案，而問題的驗證卻是確定的，能夠在多項式時間里確定結果。

比如：是否存在一個公式可以計算下一個質數是多少？這個問題的答案目前是無法直接計算出來的，但是如果某人給出了一個公式，我們卻可以在多項式時間里對這個公式進行驗證。

可以說NP完全問題是NP類問題的一種特殊情況，總結這幾類問題的特點，可參考如下這個表格：

註：表格中的問題類型的困難程度依次遞增

由表可知，NP類問題是否能在多項式時間內求解，其答案並不明確，如果回答為「是」，豈不是跟P類問題一樣了？值得一題的是，P=NP？是千禧七大難題的首個難題，是一個價值百萬美元的問題，這個問題本質是求證：能用多項式時間驗證解的問題是否內在多項式時間內找出解。

在決策樹演算法中，尋找最優決策樹是一個NP完全問題。決策樹的這一特點，說明我們無法利用計算機在多項式時間內，找出全局最優的解。

也正因為如此，大多數決策樹演算法都採用啟發式的演算法，如貪心演算法，來指導對假設空間的搜索。可以說，決策樹最後的結果，是在每一步、每一個節點上做的局部最優選擇。決策樹得到的結果，是沒法保證為全局最優的。

（全文完）

參考文章：
1、 什麼是P問題、NP問題和NPC問題
2、 what are the differences between np, np-complete and np-hard

❸ 決策樹是什麼東東

小白自學路上的備忘記錄。。。

參考：
決策樹(分類樹、回歸樹)
決策樹 :這個博客的圖真好看，通俗易懂。哈哈
決策樹詳解

決策樹（Decision Tree）是一種有監督學習演算法，常用於分類和回歸。本文僅討論分類問題。

決策樹模型是運用於分類以及回歸的一種樹結構。決策樹由節點和有向邊組成，一般一棵決策樹包含一個根節點、若干內部節點和若干葉節點。決策樹的決策過程需要從決策樹的根節點開始，待測數據與決策樹中的特徵節點進行比較，並按照比較結果選擇選擇下一比較分支，直到葉子節點作為最終的決策結果。

簡而言之，決策樹是一個利用樹的模型進行決策的多分類模型

為了找到最優的劃分特徵，我們需要先了解一些資訊理論的知識：

純度 ：
你可以把決策樹的構造過程理解成為尋找純凈劃分的過程。數學上，我們可以用純度來表示，純度換一種方式來解釋就是讓目標變數的分歧最小

信息熵 ：表示信息的不確定度
在資訊理論中，隨機離散事件出現的概率存在著不確定性。為了衡量這種信息的不確定性，信息學之父香農引入了信息熵的概念.
當不確定性越大時，它所包含的信息量也就越大，信息熵也就越高 。
信息熵越大，純度越低。當集合中的所有樣本均勻混合時，信息熵最大，純度最低

經典的 「不純度」的指標有三種，分別是信息增益（ID3 演算法）、信息增益率（C4.5 演算法）以及基尼指數（Cart 演算法）
信息增益 ：
信息增益指的就是劃分可以帶來純度的提高，信息熵的下降。它的計算公式，是父親節點的信息熵減去所有子節點的信息熵。
信息增益率
信息增益率 = 信息增益 / 屬性熵
基尼指數
基尼指數（基尼不純度）：表示在樣本集合中一個隨機選中的樣本被分錯的概率。
即 基尼指數（基尼不純度）= 樣本被選中的概率 * 樣本被分錯的概率
基尼系數的性質與信息熵一樣：度量隨機變數的不確定度的大小；
G 越大，數據的不確定性越高；
G 越小，數據的不確定性越低；
G = 0，數據集中的所有樣本都是同一類別
詳細參考： 機器學習——基尼指數

ID3 演算法是建立在奧卡姆剃刀（用較少的東西，同樣可以做好事情）的基礎上：越是小型的決策樹越優於大的決策樹
ID3演算法的核心是在決策樹各個節點上根據信息增益來選擇進行劃分的特徵，然後遞歸地構建決策樹。演算法採用自頂向下的貪婪搜索遍歷可能的決策樹空間。

具體方法 ：

ID3的局限 ：

C4.5與ID3相似，但大的特點是克服了 ID3 對特徵數目的偏重這一缺點，引入信息增益率來作為分類標准。

C4.5的實現基於ID3的改進 ：

信息增益率對可取值較少的特徵有所偏好（分母越小，整體越大），因此 C4.5 並不是直接用增益率最大的特徵進行劃分，而是使用一個 啟發式方法 ：先從候選劃分特徵中找到信息增益高於平均值的特徵，再從中選擇增益率最高的。

C4.5的局限 ：

ID3 和 C4.5 生成的決策樹分支、規模都比較大，CART 演算法的二分法可以簡化決策樹的規模，提高生成決策樹的效率。
CART(),分類回歸樹演算法，既可用於分類也可用於回歸，在這一部分我們先主要將其分類樹的生成。區別於ID3和C4.5,CART假設決策樹是二叉樹，內部節點特徵的取值為「是」和「否」，左分支為取值為「是」的分支，右分支為取值為」否「的分支。這樣的決策樹等價於遞歸地二分每個特徵，將輸入空間(即特徵空間)劃分為有限個單元。
CART的分類樹用基尼指數來選擇最優特徵的最優劃分點，具體過程如下

剪枝就是給決策樹瘦身，這一步想實現的目標就是，不需要太多的判斷，同樣可以得到不錯的結果。之所以這么做，是為了防止「過擬合」（Overfitting）現象的發生。
過擬合：指的是模型的訓練結果「太好了」，以至於在實際應用的過程中，會存在「死板」的情況，導致分類錯誤。
欠擬合：指的是模型的訓練結果不理想.
剪枝的方法 ：

參考： 【機器學習】決策樹（上）——ID3、C4.5、CART（非常詳細）

更多模型不斷更新中。。。。

❹ 決策樹（Decision Tree）

  決策樹（Decision Tree）是一種基本的分類與回歸方法，其模型呈樹狀結構，在分類問題中，表示基於特徵對實例進行分類的過程。本質上，決策樹模型就是一個定義在特徵空間與類空間上的條件概率分布。決策樹學習通常包括三個步驟： 特徵選擇 、 決策樹的生成 和 決策樹的修剪 。

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

  利用決策樹進行分類，從根節點開始，對實例的某一特徵進行測試，根據測試結果將實例分配到其子節點；這時，每一個子節點對應著該特徵的一個取值。如此遞歸地對實例進行測試並分配，直至達到葉節點。最後將實例分到葉節點的類中。

  決策樹是給定特徵條件下類的條件概率分布，這一條件概率分布定義在特徵區間的一個劃分（partiton）上。將特徵空間劃分為互不相交的單元（cell）或區域（region），並在每個單元定義一個類的概率分布就構成了一個條件概率分布。決策樹的一條路徑對應劃分中的一個單元，決策樹所表示的條件概率分布由各個單元給定條件下類的條件概率分布組成。假設X為表示特徵的隨機變數，Y為表示類的隨機變數，那麼這個條件概率分布可以表示成P(Y|X)。X取值於給定劃分下單元的集合，Y取值於類的集合，各葉節點（單元）上的條件概率往往偏向於某一個類，即屬於某一類的概率較大，決策樹分類時將該節點的實例分到條件概率大的那一類去。也就以為著決策樹學習的過程其實也就是由數據集估計條件概率模型的過程，這些基於特徵區間劃分的類的條件概率模型由無窮多個，在進行選擇時，不僅要考慮模型的擬合能力還要考慮其泛化能力。

  為了使模型兼顧模型的擬合和泛化能力，決策樹學習使用正則化的極大似然函數來作為損失函數，以最小化損失函數為目標，尋找最優的模型。顯然從所有可能的決策樹中選取最優決策樹是NP完全問題，所以在實際中通常採用啟發式的方法，近似求解這一最優化問題： 通過遞歸的選擇最優特徵，根據該特徵對訓練數據進行劃分直到使得各個子數據集有一個最好的分類，最終生成特徵樹 。當然，這樣得到的決策樹實際上是次最優（sub-optimal）的。進一步的，由於決策樹的演算法特性，為了防止模型過擬合，需要對已生成的決策樹自下而上進行剪枝，將樹變得更簡單，提升模型的泛化能力。具體來說，就是去掉過於細分的葉節點，使其退回到父節點，甚至更高的節點，然後將父節點或更高的節點改為新的葉節點。如果數據集的特徵較多，也可以在進行決策樹學習之前，對數據集進行特徵篩選。

  由於決策樹是一個條件概率分布，所以深淺不同的決策樹對應著不同復雜度的概率模型，決策樹的生成對應模型的局部選擇，決策樹的剪枝對應著模型的全局選擇。

   熵（Entropy） 的概念最早起源於物理學，最初物理學家用這個概念度量一個熱力學系統的無序程度。在1948年， 克勞德·艾爾伍德·香農 將熱力學的熵，引入到 資訊理論 ，因此它又被稱為 香農熵 。在資訊理論中，熵是對不確定性的量度，在一條信息的熵越高則能傳輸越多的信息，反之，則意味著傳輸的信息越少。

  如果有一枚理想的硬幣，其出現正面和反面的機會相等，則拋硬幣事件的熵等於其能夠達到的最大值。我們無法知道下一個硬幣拋擲的結果是什麼，因此每一次拋硬幣都是不可預測的。因此，使用一枚正常硬幣進行若干次拋擲，這個事件的熵是一 比特 ，因為結果不外乎兩個——正面或者反面，可以表示為 0, 1 編碼，而且兩個結果彼此之間相互獨立。若進行 n 次 獨立實驗 ，則熵為 n ，因為可以用長度為 n 的比特流表示。但是如果一枚硬幣的兩面完全相同，那個這個系列拋硬幣事件的熵等於零，因為 結果能被准確預測 。現實世界裡，我們收集到的數據的熵介於上面兩種情況之間。

  另一個稍微復雜的例子是假設一個 隨機變數 X ，取三種可能值 ，概率分別為 ，那麼編碼平均比特長度是： 。其熵為 。因此<u>熵實際是對隨機變數的比特量和順次發生概率相乘再總和的</u> 數學期望 。

  依據玻爾茲曼H定理，香農把隨機變數X的熵 定義為：

  其中 是隨機變數X的信息量，當隨機變數取自有限樣本時，熵可以表示為：

  若 ，則定義 。

  同理可以定義條件熵 :

  很容易看出，條件熵（conditional entropy） 就是X給定條件下Y的條件概率分布的熵對X的數學期望。當熵和條件熵中的概率有極大似然估計得到時，所對應的熵和條件熵分別稱為檢驗熵（empirical entropy）和經驗條件熵（empirical conditional entropy）.

  熵越大，隨機變數的不確定性就越大，從定義可以驗證:

  當底數 時，熵的單位是 ；當 時，熵的單位是 ;而當 時，熵的單位是 .

  如英語有26個字母，假如每個字母在文章中出現的次數平均的話，每個字母的信息量 為：

  同理常用漢字2500有個，假設每個漢字在文章中出現的次數平均的話，每個漢字的信息量 為：

  事實上每個字母和漢字在文章中出現的次數並不平均，少見字母和罕見漢字具有相對較高的信息量，顯然，由期望的定義，熵是整個消息系統的平均消息量。

  熵可以用來表示數據集的不確定性，熵越大，則數據集的不確定性越大。因此使用 劃分前後數據集熵的差值 量度使用當前特徵對於數據集進行劃分的效果（類似於深度學習的代價函數）。對於待劃分的數據集 ，其劃分前的數據集的熵 是一定的，但是劃分之後的熵 是不定的， 越小說明使用此特徵劃分得到的子集的不確定性越小（也就是純度越高）。因此 越大，說明使用當前特徵劃分數據集 時，純度上升的更快。而我們在構建最優的決策樹的時候總希望能更快速到達純度更高的數據子集，這一點可以參考優化演算法中的梯度下降演算法，每一步沿著負梯度方法最小化損失函數的原因就是負梯度方向是函數值減小最快的方向。同理：在決策樹構建的過程中我們總是希望集合往最快到達純度更高的子集合方向發展，因此我們總是選擇使得信息增益最大的特徵來劃分當前數據集 。

  顯然這種劃分方式是存在弊端的，按信息增益准則的劃分方式，當數據集的某個特徵B取值較多時，依此特徵進行劃分更容易得到純度更高的數據子集，使得 偏小，信息增益會偏大，最終導致信息增益偏向取值較多的特徵。

  設 是 個數據樣本的集合，假定類別屬性具有 個不同的值： ,設 是類 中的樣本數。對於一個給定樣本，它的信息熵為：

  其中， 是任意樣本屬於 的概率，一般可以用 估計。

  設一個屬性A具有 個不同的值 ，利用屬性A將集合 劃分為 個子集 ，其中 包含了集合 中屬性 取 值的樣本。若選擇屬性A為測試屬性，則這些子集就是從集合 的節點生長出來的新的葉節點。設 是子集 中類別為 的樣本數，則根據屬性A劃分樣本的信息熵為：

  其中 , 是子集 中類別為 的樣本的概率。最後，用屬性A劃分樣本子集 後所得的 信息增益(Gain) 為：

  即，<u>屬性A的信息增益=劃分前數據的熵-按屬性A劃分後數據子集的熵</u>。 信息增益（information gain）又稱為互信息（matual information）表示得知特徵X的信息而使得類Y的信息的不確定性減少的程度 。信息增益顯然 越小， 的值越大，說明選擇測試屬性A對於分類提供的信息越多，選擇A之後對分類的不確定程度越小。

  經典演算法 ID3 使用的信息增益特徵選擇准則會使得劃分更偏相遇取值更多的特徵，為了避免這種情況。ID3的提出者 J.Ross Quinlan 提出了 C4.5 ,它在ID3的基礎上將特徵選擇准則由 信息增益 改為了 信息增益率 。在信息增益的基礎之上乘上一個懲罰參數。特徵個數較多時，懲罰參數較小；特徵個數較少時，懲罰參數較大（類似於正則化）。這個懲罰參數就是 分裂信息度量 的倒數 。

  不同於 ID3 和 C4.5 , CART 使用基尼不純度來作為特徵選擇准則。基尼不純度也叫基尼指數 , 表示在樣本集合中一個隨機選中的樣本被分錯的概率 則<u>基尼指數（基尼不純度）= 樣本被選中的概率 * 樣本被分錯的概率</u>。Gini指數越小表示集合中被選中的樣本被分錯的概率越小，也就是說集合的純度越高，反之，集合越不純。

樣本集合的基尼指數：
樣本集合 有m個類別， 表示第 個類別的樣本數量,則 的Gini指數為：

基於某個特徵劃分樣本集合S之後的基尼指數：
  CART是一個二叉樹，也就是當使用某個特徵劃分樣本集合後，得到兩個集合：a.等於給定的特徵值的樣本集合 ；b.不等於給定特徵值的樣本集合 。實質上是對擁有多個取值的特徵的二值處理。

對於上述的每一種劃分，都可以計算出基於劃分特=某個特徵值將樣本集合劃分為兩個子集的純度：

因而對於一個具有多個取值（超過2個）的特徵，需要計算以每個取值為劃分點，對樣本集合劃分後子集的純度 ( 表示特徵 的可能取值)然後從所有的劃分可能 中找出Gini指數最小的劃分，這個劃分的劃分點，就是使用特徵 對樣本集合 進行劃分的最佳劃分點。

參考文獻 ：

決策樹--信息增益，信息增益比，Geni指數的理解

【機器學習】深入理解--信息熵（Information Entropy）

統計學習方法 （李航）

  為了便於理解，利用以下數據集分別使用三種方法進行分類：

  在進行具體分析之前，考慮到收入是數值類型，要使用決策樹演算法，需要先對該屬性進行離散化。
  在機器學習演算法中，一些分類演算法（ID3、Apriori等）要求數據是分類屬性形式，因此在處理分類問題時經常需要將一些連續屬性變換為分類屬性。一般來說，連續屬性的離散化都是通過在數據集的值域內設定若干個離散的劃分點，將值域劃分為若干區間，然後用不同的符號或整數數值代表落在每個子區間中的數據值。所以，離散化最核心的兩個問題是：如何確定分類數以及如何將連續屬性映射到這些分類值。常用的離散化方法有 等寬法 ， 等頻法 以及 一維聚類法 等。

在實際使用時往往使用Pandas的 cut() 函數實現等寬離散化:

  可以看到與手工計算的離散化結果相同，需要注意的是，<u> 等寬法對於離群點比較敏感，傾向於不均勻地把屬性值分布到各個區間，導致某些區間數據較多，某些區間數據很少，這顯然不利用決策模型的建立。 </u>

使用四個分位數作為邊界點，對區間進行劃分：

<u> 等頻率離散化雖然避免了等寬離散化的數據分布不均勻的問題,卻可能將相同的數據值分到不同的區間以滿足每個區間具有相同數量的屬性取值的要求。 </u>

使用一維聚類的離散化方法後得到數據集為：

  在本次實例中選擇使用基於聚類的離散化方法後得到的數據集進行指標計算。為了預測客戶能否償還債務，使用A（擁有房產）、B（婚姻情況）、C（年收入）等屬性來進行數據集的劃分最終構建決策樹。

單身 ：

離婚 ：

已婚 ：

顯然，由B屬性取值'已婚'劃分得到的子數據集屬於同一個葉節點，無法再進行分類。
接下來，對由B屬性取值'單身'劃分得到的子數據集 再進行最優特徵選擇：

1）計算數據集 總的信息熵，其中4個數據中，能否償還債務為'是'數據有3，'否'數據有1,則總的信息熵：

2）對於A(擁有房產)屬性，其屬性值有'是'和'否'兩種。其中，在A為'是'的前提下，能否償還債務為'是'的有1、'否'的有0；在A為'否'的前提下，能否償還債務為'是'的有2、為'否'的有1，則A屬性的信息熵為：

3)對於B（婚姻情況）屬性，由於已被確定，在這個數據子集信息熵為0

4)對於C（年收入）屬性，其屬性值有'中等輸入'、'低收入'兩種。在C為'中等收入'的前提下，能否償還作為為'是'的有1,為'否'的有0；在C為'低收入'的前提下，能否償還作為為'是'的有2,為'否'的有1;則C屬性的信息熵為：

5）最後分別計算兩個屬性的信息增益值：


信息增益值相同，說明以兩個屬性對數據子集進行劃分後決策樹的純度上升是相同的，此時任選其一成為葉節點即可。
同理，對數據子集 進行最優特徵選擇，發現信息熵為0：
整理得到最終的決策樹：

❺ 學大數據需要什麼基礎

其實籠統地說大數據原理和基礎都在數學這邊，當然有很多偏應用和軟體使用的技術，例如「深度學習調參」等，這些報個培訓速成班就能學會的技術含量不那麼高的東西，不在討論范圍內。

深度學習：目前非常火，打敗了非常多幾十年積累起來的經典方法。

增強學習：也很火，游戲AI、自動駕駛、機器人等等，它都是核心。

概率圖模型：深度學習之前非常popular的「學習」方法，有嚴格的數學模型和優美的演算法，雖然目前被前倆者蓋過了風頭，但是依然有它的立足之處。

再比如有用偏微分方程做圖像處理的（比較小眾），那麼這時候你肯定要去學一下偏微分方程了，大都是以科研為主導的。

❻ 決策樹演算法原理

決策樹是通過一系列規則對數據進行分類的過程。它提供一種在什麼條件下會得到什麼值的類似規則的方法。決策樹分為分類樹和回歸樹兩種，分類樹對離散變數做決策樹，回歸樹對連續變數做決策樹。

如果不考慮效率等，那麼樣本所有特徵的判斷級聯起來終會將某一個樣本分到一個類終止塊上。實際上，樣本所有特徵中有一些特徵在分類時起到決定性作用，決策樹的構造過程就是找到這些具有決定性作用的特徵，根據其決定性程度來構造一個倒立的樹--決定性作用最大的那個特徵作為根節點，然後遞歸找到各分支下子數據集中次大的決定性特徵，直至子數據集中所有數據都屬於同一類。所以，構造決策樹的過程本質上就是根據數據特徵將數據集分類的遞歸過程，我們需要解決的第一個問題就是，當前數據集上哪個特徵在劃分數據分類時起決定性作用。

一棵決策樹的生成過程主要分為以下3個部分:

特徵選擇：特徵選擇是指從訓練數據中眾多的特徵中選擇一個特徵作為當前節點的分裂標准，如何選擇特徵有著很多不同量化評估標准標准，從而衍生出不同的決策樹演算法。

決策樹生成： 根據選擇的特徵評估標准，從上至下遞歸地生成子節點，直到數據集不可分則停止決策樹停止生長。 樹結構來說，遞歸結構是最容易理解的方式。

剪枝：決策樹容易過擬合，一般來需要剪枝，縮小樹結構規模、緩解過擬合。剪枝技術有預剪枝和後剪枝兩種。

劃分數據集的最大原則是：使無序的數據變的有序。如果一個訓練數據中有20個特徵，那麼選取哪個做劃分依據？這就必須採用量化的方法來判斷，量化劃分方法有多重，其中一項就是「資訊理論度量信息分類」。基於資訊理論的決策樹演算法有ID3、CART和C4.5等演算法，其中C4.5和CART兩種演算法從ID3演算法中衍生而來。

CART和C4.5支持數據特徵為連續分布時的處理，主要通過使用二元切分來處理連續型變數，即求一個特定的值-分裂值：特徵值大於分裂值就走左子樹，或者就走右子樹。這個分裂值的選取的原則是使得劃分後的子樹中的「混亂程度」降低，具體到C4.5和CART演算法則有不同的定義方式。

ID3演算法由Ross Quinlan發明，建立在「奧卡姆剃刀」的基礎上：越是小型的決策樹越優於大的決策樹（be simple簡單理論）。ID3演算法中根據資訊理論的信息增益評估和選擇特徵，每次選擇信息增益最大的特徵做判斷模塊。ID3演算法可用於劃分標稱型數據集，沒有剪枝的過程，為了去除過度數據匹配的問題，可通過裁剪合並相鄰的無法產生大量信息增益的葉子節點（例如設置信息增益閥值）。使用信息增益的話其實是有一個缺點，那就是它偏向於具有大量值的屬性--就是說在訓練集中，某個屬性所取的不同值的個數越多，那麼越有可能拿它來作為分裂屬性，而這樣做有時候是沒有意義的，另外ID3不能處理連續分布的數據特徵，於是就有了C4.5演算法。CART演算法也支持連續分布的數據特徵。

C4.5是ID3的一個改進演算法，繼承了ID3演算法的優點。C4.5演算法用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足在樹構造過程中進行剪枝；能夠完成對連續屬性的離散化處理；能夠對不完整數據進行處理。C4.5演算法產生的分類規則易於理解、准確率較高；但效率低，因樹構造過程中，需要對數據集進行多次的順序掃描和排序。也是因為必須多次數據集掃描，C4.5隻適合於能夠駐留於內存的數據集。

CART演算法的全稱是Classification And Regression Tree，採用的是Gini指數（選Gini指數最小的特徵s）作為分裂標准,同時它也是包含後剪枝操作。ID3演算法和C4.5演算法雖然在對訓練樣本集的學習中可以盡可能多地挖掘信息，但其生成的決策樹分支較大，規模較大。為了簡化決策樹的規模，提高生成決策樹的效率，就出現了根據GINI系數來選擇測試屬性的決策樹演算法CART。

決策樹演算法的優點：

（1）便於理解和解釋，樹的結構可以可視化出來

（2）基本不需要預處理，不需要提前歸一化，處理缺失值

（3）使用決策樹預測的代價是O(log2m)，m為樣本數

（4）能夠處理數值型數據和分類數據

（5）可以處理多維度輸出的分類問題

（6）可以通過數值統計測試來驗證該模型，這使解釋驗證該模型的可靠性成為可能

（7）即使該模型假設的結果與真實模型所提供的數據有些違反，其表現依舊良好

決策樹演算法的缺點:

（1）決策樹模型容易產生一個過於復雜的模型,這樣的模型對數據的泛化性能會很差。這就是所謂的過擬合.一些策略像剪枝、設置葉節點所需的最小樣本數或設置數的最大深度是避免出現該問題最為有效地方法。

（2）決策樹可能是不穩定的，因為數據中的微小變化可能會導致完全不同的樹生成。這個問題可以通過決策樹的集成來得到緩解。

（3）在多方面性能最優和簡單化概念的要求下，學習一棵最優決策樹通常是一個NP難問題。因此，實際的決策樹學習演算法是基於啟發式演算法，例如在每個節點進行局部最優決策的貪心演算法。這樣的演算法不能保證返回全局最優決策樹。這個問題可以通過集成學習來訓練多棵決策樹來緩解,這多棵決策樹一般通過對特徵和樣本有放回的隨機采樣來生成。

（4）有些概念很難被決策樹學習到,因為決策樹很難清楚的表述這些概念。例如XOR，奇偶或者復用器的問題。

（5）如果某些類在問題中佔主導地位會使得創建的決策樹有偏差。因此，我們建議在擬合前先對數據集進行平衡。

（1）當數據的特徵維度很高而數據量又很少的時候，這樣的數據在構建決策樹的時候往往會過擬合。所以我們要控制樣本數量和特徵的之間正確的比率；

（2）在構建決策樹之前，可以考慮預先執行降維技術（如PCA，ICA或特徵選擇），以使我們生成的樹更有可能找到具有辨別力的特徵；

（3）在訓練一棵樹的時候，可以先設置max_depth=3來將樹可視化出來，以便我們找到樹是怎樣擬合我們數據的感覺，然後在增加我們樹的深度；

（4）樹每增加一層，填充所需的樣本數量是原來的2倍，比如我們設置了最小葉節點的樣本數量，當我們的樹層數增加一層的時候，所需的樣本數量就會翻倍，所以我們要控制好樹的最大深度，防止過擬合；

（5）使用min_samples_split（節點可以切分時擁有的最小樣本數） 和 min_samples_leaf（最小葉節點數）來控制葉節點的樣本數量。這兩個值設置的很小通常意味著我們的樹過擬合了，而設置的很大意味著我們樹預測的精度又會降低。通常設置min_samples_leaf=5；

（6）當樹的類比不平衡的時候，在訓練之前一定要先平很數據集，防止一些類別大的類主宰了決策樹。可以通過采樣的方法將各個類別的樣本數量到大致相等，或者最好是將每個類的樣本權重之和(sample_weight)規范化為相同的值。另請注意，基於權重的預剪枝標准（如min_weight_fraction_leaf）將比不知道樣本權重的標准（如min_samples_leaf）更少偏向主導類別。

（7）如果樣本是帶權重的，使用基於權重的預剪枝標准將更簡單的去優化樹結構，如mn_weight_fraction_leaf，這確保了葉節點至少包含了樣本權值總體總和的一小部分；

（8）在sklearn中所有決策樹使用的數據都是np.float32類型的內部數組。如果訓練數據不是這種格式，則將復制數據集，這樣會浪費計算機資源。

（9）如果輸入矩陣X非常稀疏，建議在調用fit函數和稀疏csr_matrix之前轉換為稀疏csc_matrix，然後再調用predict。 當特徵在大多數樣本中具有零值時，與密集矩陣相比，稀疏矩陣輸入的訓練時間可以快幾個數量級。

❼ 蒙特卡洛樹搜索 - 以蠻力對抗智慧

蒙特卡洛樹搜索（Monte Carlo tree search；簡稱：MCTS）是一種用於某些決策過程的啟發式搜索演算法，最引人注目的是在游戲中的使用。一個主要例子是計算機圍棋程序，它也用於其他棋盤游戲、即時電子游戲以及不確定性游戲。

比如圍棋，棋手需要針對盤面的情況，選擇下一步走哪個位置。這個決策過程可以認為是一個決策函數
a = f(s) ，即面對 可能的狀態s ， 決策函數f 會提供一個 行動a （落子位置）。當然，我們希望 f 盡可能優秀，其決策a能夠盡可能贏棋。

我們也可以將f構造為一顆決策樹。從盤面初始狀態開始（沒有棋子），令初始狀態為根節點，第一手棋有19*19=361個位置，因此根節點下面有361個子節點，第二手棋有360個可能的位置，即361個節點下，每個節點又有360個子節點......隨著雙方的落子，樹的分枝越來越多，每個分支最終會進入葉子狀態（對局結束，黑勝或白勝）。理論上可以列舉所有可能的情況，做一棵完整的決策樹，但實際上這個數據量大到不可能實現。因此，我們必須在有限的時間和空間之內，高效的構建一個子樹，這是一個不完整但 盡量好的決策樹 。

即便只是盡量好的決策，也是很困難的。因為一步棋的好壞通常不能立即判斷出來，最終的評判要到下完的時候才能決定誰贏，況且即便贏了棋，也不代表其中每一步都是好的。

但是，無論怎樣，必須提供某種方法讓AI知道一步棋好不好，也就是要提供一些 啟發 ，於是我們可以採用蒙特卡洛樹搜索方法。

剛才我們說到下一盤棋不能判定其中走法的好壞，但如果下很多次呢？比如在某個特定盤面s1情況下，進行n次對局（接著s1盤面往後走），如果統計下來黑棋贏得多，說明s1情況對黑棋比較有利。這就是蒙特卡洛方法的思想，用大量隨機事件逼近真實情況。

雖然通過蒙特卡羅方法可以近似估計一個狀態的好壞，但我們依然無法對太多狀態進行估算。因此，我們需要有選擇的集中力量對決策樹中的可能更有價值的那些節點進行估算。這就需要使用蒙特卡洛樹搜索，它提供了一種選擇機制，使我們能夠盡量選擇決策樹中比較有潛力的節點進行蒙特卡洛模擬，從而使得樹可以盡量集中在「較好」的策略上進行「生長」。

蒙特卡洛樹搜索有四個主要步驟：

從根節點R開始，選擇連續的子節點向下至葉子節點L。讓決策樹向最優的方向擴展，這是蒙特卡洛樹搜索的精要所在。也就是要選擇一個盡量」有潛力「的樹節點，那麼怎樣的節點是有潛力呢？ 一個是勝率高，另一個是被考察的次數少 。
勝率高的節點（狀態）意味著最後贏棋的概率較大，當然應該多花些精力分析其後續走法。被考察次數少的節點意味著該節點（狀態）尚未經過充分研究，有成為黑馬的可能。

具體來說，通常用UCB1（Upper Confidence Bound，上置信區間）公式來計算一個節點的」潛力「：

wi：第 i 次移動後取勝的次數
ni：第 i 次移動後模擬的次數
c：探索參數/權衡參數，理論上等於 根號2，在實際中通常可憑經驗選擇
t：模擬總次數，等於所有 ni 的和

看一個例子（參考 28 天自製你的 AlphaGo（五） ）

上圖中每個節點代表一個局面。而 A/B 代表這個節點被訪問 B 次，黑棋勝利了 A 次。例如一開始的根節點是 12/21，代表總共模擬了 21 次，黑棋勝利了 12 次。

圖中展示了蒙特卡洛樹搜索的四個步驟，我們先看左邊第一個樹（Selection）。假設根節點是輪到黑棋走。那麼我們首先需要在 7/10、5/8、0/3 之間選擇，採用上面的UCB1公式：

假設 C 比較小（比如C=1），上述3個分數為 1.25 1.245 1，於是我們選擇 7/10 節點（它得分1.25是最高的）。然後接下來 7/10 下面的 2/4 和 5/6 之間選擇。注意，由於現在是白棋走，需要把勝率估計倒過來。即圖上黑棋勝率是 2/4 和 5/6，則白棋勝率是 (1 - 2/4) 和 (1 - 5/6)：

那麼白棋應該選 2/4 節點。（圖中擴展的是 5/6 節點，這不是很合理）。

在所選的葉子節點L，如果已經能判定輸贏，則該輪游戲結束，否則創建一個或多個子節點並選取其中一個節點C。

看上圖第2個樹（Expansion），假設黑棋選擇了（當前的）葉子節點 3/3，然後創建了一個子節點，初始狀態 0/0。

從節點C開始，用隨機策略進行游戲，直到分出輸贏（獲得一次准確的回報）。這一步驟又稱為playout或者rollout。

雖然原則上蒙特卡洛方法是採用隨機策略，不過實際中也可以採用一些「有經驗」的策略，或者兩者的結合。所謂有經驗的策略就像一個有一定水平的棋手，ta 可以下出一些比較好的走法。我們可以在模擬的某個階段採用棋手的走法，另外一些階段採用隨機走法。
不過總的來說，模擬需要很快速的完成，這樣才能得到盡量多的模擬結果，使統計結果逼近真實的勝率。

看上圖第3個樹（Simulation），黑棋從 0/0 節點開始進行模擬游戲直到終局，假設黑棋輸，所以得分是 0/1。

使用隨機游戲的結果，更新從C到R的路徑上的節點信息。

看上圖第4個樹（Backpropagation），從 0/0 節點開始遍歷父節點，直到根節點R，這條路徑上的每個節點都添加一個 0/1。

當構建了一棵蒙特卡洛樹以後，需要用它來做決策時，應該選擇訪問量最大的節點，而不是勝率最高的節點，也不是UCB分數最高的節點。

訪問量不夠大的節點，即使勝率高，也不夠可靠（因為模擬次數不夠多）。而訪問量最大的節點，通常也有一定的勝率，想想UCB公式，如果勝率不高是不會經常被選中的（訪問量不會大）。所以採用訪問量最大的節點，AI的表現會更加穩定。

對於圍棋AI，僅使用蒙特卡洛樹搜索是不夠的，尤其是 AlphaGO 這樣的頂級AI，更多分析請參考：
左右互搏，青出於藍而勝於藍？阿爾法狗原理解析

28 天自製你的 AlphaGo（五）
AlphaGo背後的力量：蒙特卡洛樹搜索入門指南
蒙特卡洛樹搜索（MCTS）演算法
維基網路——蒙特卡洛樹搜索
維基網路——蒙特卡羅方法

❽ 決策樹分裂到最後，各個類別相等怎麼辦

決策樹分類演算法的一般流程如下：一開始，所有的實例均位於根節點，所有參數的取值均離散化；根據啟發規則選擇一個參數，根據參數取值的不同對實例集進行分割；對分割後得到的節點進行同樣的啟發式參數選擇分割過程，如此往復，直到(a)分割得到的實例集合屬於同一類；(b)參數用完，以子集中絕大多數的實例類別作為該葉節點的類別。在每一個節點進行參數選擇時，由於有眾多的選項，需要一個選擇規則。基本的原則是使最後構造出的決策樹規模最小。基於這個基本原則，我們啟發式地定義規則為使分割後得到的子節點純度最大。於是參數選擇規則問題就轉化為了純度定義的問題。

❾ Xgboost原理分析

從陳天奇的PPT中進行總結，重點了解模型的構建，策略的選擇和優化演算法的選取。

機器學習的目標函數基本都是：

也就是 損失函數和正則化項的組合。

在目標函數，偏差和方差之間 做trade-off

也稱分類回歸樹

上圖可以看出來，每個葉子結點都有一個分數，那麼被分到該結點的數據獲得這個分數。

我們通過將多個這樣的回歸樹集成起來，獲得我們的集成演算法。

上圖可以看出來，對於小男孩的總體分數，就是兩棵樹的加和結果。

集成樹的特點有：

模型假設我們有K棵樹（上面提到的回歸樹）：

F就是我們的假設空間（函數空間，包含k個回歸樹）

這個模型中的參數包括：

定義目標函數，然後去優化這個目標函數

上圖中，是以時間為變數，來構建回歸樹，評價個人隨著時間t是否喜歡浪漫音樂。

將一個回歸樹等價到一個分段函數中，那麼我們從中需要學習的「參數」也就是我們的：

上面四幅圖中，給出了不同劃分位置和劃分高度，最後的參數模型也就是圖四的效果。

那麼從一棵樹開始，我們可以來定義我們模型的目標函數。

我們有K棵樹

目標函數是:

第一項是我們的損失函數項，第二項是我們的正則化項。

當我們討論決策樹的時候，都是啟發式的從一些方面進行考慮：

我們使用決策樹演算法時候，就是通過信息增益來劃分分支，那麼這里我們可以用每一次劃分的信息增益當做我們的損失函數。（劃分後的信息增益-劃分前的信息增益）

決策樹中的剪枝，就是為了控制決策樹的模型復雜度，這里我們也通過控制葉子節點的個數，來實現正則化，控制模型的復雜度。

限制樹的深度，也是一定程度上限制我們的模型復雜度。

盡可能的讓我們的葉子上的score平滑，使用L2正則化來控制葉子結點上的權重。

目標函數是:

那我們是如何學習這個目標函數的呢？

我們不能使用梯度下降演算法來進行計算損失函數，因為我們這里的參數是回歸樹，而不是一些數值型數據（類比線性模型裡面的參數 w）

從常數開始，然後每次加入一棵新樹（一個新的函數）

其中，我們的 是第t輪的訓練模型， 是t輪前我們的訓練結果， 是新加入的函數（新加入的一棵樹）

那麼我們怎麼樣決定一個新加入的樹（函數 ），這個函數就是我們上面提到的我們的參數，即如何選擇一個參數來優化我們的模型，當然從優化目標函數中找。

上述目標函數還是很復雜，於是作者引入了泰勒展開式來替換損失函數。

類比泰勒展開式的

在我們的目標函數中損失函數 相當於函數

所以我們可以得到我們的目標函數帶入泰勒展開之後的結果是：

這裡面 是我們前t-1輪的對 預測和 的目標的損失，這是一個常數項。因為我們優化的是第t輪，研究怎麼選擇第t輪需要加進去的樹，所以前面的 我們都可以看作是一個常量。

給目標函數對權重求偏導，得到一個能夠使目標函數最小的權重，把這個權重代回到目標函數中，這個回代結果就是 求解後的最小目標函數值 。

是一個葉子結點上的 每一個樣本的梯度值，同理理解

從我們的損失函數 ，說起，看我們如何定義這個 ，不如這里我們以簡單的 為例子：

針對我們的平方差損失函數來說， 就是如下式子：

其中 項也就是我們常說的殘差項。

從例子中理解各個參數的含義，

比如葉子結點1代表的權重（分數）是+2，葉子結點2對應的是+0.1，葉子結點3對應是-1

然後看我們的正則化項，其中T代表葉子結點的數目， 從上面的例子可以很容易的計算得到我們的正則化結果。

我們定義： 就是第i個數據屬於第j個葉子結點。

然後我們將屬於同一個葉子結點的數據放入一個group裡面得到

也就是將從各個樣本上的遍歷，映射到了對葉子結點的遍歷（葉子結點里可能包含多個樣本）

重新定義G 和H ，也將其從單個樣本上的遍歷，映射到對葉子結點的遍歷。

其中的 是來評價一棵樹的結構是否很好，分數越小，結構越好。

但是仍然有無數顆樹可以進行選擇，那麼我們如何選擇才能保證最優化呢？

從常數0開始，我們選擇一個樹加入，每一次嘗試去對已有的葉子加入一個分割。

然後我們來計算分割後的結構分數（左子樹+右子樹）與我們不進行分割的結構分數進行做差，同時還要減去因為分割引入的結構復雜度。

也可以很好的處理非數值型特徵，並且不需要將類別特徵（離散的）和數值型特徵（連續的）分開進行處理。

我們可以通過one-hot編碼將離散的特徵類別映射到數值型。

如果類別特別多，向量會非常稀疏，但是這個演算法也很擅長處理稀疏的數據。

設置最大樹深度，然後遞歸的去剪裁 所有葉子節點出現負的Gain的分裂情況

更細節的問題是，我們不會每個樹做到最優化，這樣容易過擬合，我們賦予一個參數，來控制每次的優化（不讓優化效果太好），這樣留下更多的優化空間給後邊的樹。

分類回歸樹的集成演算法可以用來做回歸，分類，ranking等等，這取決於我們的損失函數如何定義。

（1）objective [ default=reg:linear ] 定義學習任務及相應的學習目標，可選的目標函數如下：

（2）』eval_metric』 The choices are listed below，評估指標:

（3）lambda [default=0] L2 正則的懲罰系數

（4）alpha [default=0] L1 正則的懲罰系數

（5）lambda_bias 在偏置上的L2正則。預設值為0（在L1上沒有偏置項的正則，因為L1時偏置不重要）

（6）eta [default=0.3]
為了防止過擬合，更新過程中用到的收縮步長。在每次提升計算之後，會直接獲得新特徵的權重。 eta通過縮減特徵的權重使提升計算過程更加保守。預設值為0.3
取值范圍為：[0,1]

（7）max_depth [default=6] 數的最大深度。預設值為6 ，取值范圍為：[1,∞]

（8）min_child_weight [default=1]
孩子節點中最小的樣本權重和。如果一個葉子節點的樣本權重和小於min_child_weight則拆分過程結束。在現行回歸模型中，這個參數是指建立每個模型所需要的最小樣本數。該參數越大演算法越保守。
取值范圍為: [0,∞]