分類樹演算法

Ⅰ 請比較k近鄰，決策樹和樸素貝葉斯這三種分類演算法之間的異同點

決策樹演算法主要包括id3，c45，cart等演算法，生成樹形決策樹，而樸素貝葉斯是利用貝葉斯定律，根據先驗概率求算後驗概率。

如果訓練集很小，那麼高偏差/低方差分類器（如樸素貝葉斯分類器）要優於低偏差/高方差分類器（如k近鄰分類器），因為後者容易過擬合。然而，隨著訓練集的增大，低偏差/高方差分類器將開始勝出（它們具有較低的漸近誤差），因為高偏差分類器不足以提供准確的模型。

一些特定演算法的優點：

樸素貝葉斯的優點：

超級簡單，你只是在做一串計算。如果樸素貝葉斯（NB）條件獨立性假設成立，相比於邏輯回歸這類的判別模型，樸素貝葉斯分類器將收斂得更快，所以只需要較小的訓練集。而且，即使NB假設不成立，樸素貝葉斯分類器在實踐方面仍然表現很好。

如果想得到簡單快捷的執行效果，這將是個好的選擇。它的主要缺點是，不能學習特徵之間的相互作用（比如，它不能學習出：雖然你喜歡布拉德·皮特和湯姆·克魯斯的電影，但卻不喜歡他們一起合作的電影）。

邏輯回歸的優點：

有許多正則化模型的方法，不需要像在樸素貝葉斯分類器中那樣擔心特徵間的相互關聯性。與決策樹和支撐向量機不同，還可以有一個很好的概率解釋，並能容易地更新模型來吸收新數據（使用一個在線梯度下降方法）。

如果想要一個概率框架（比如，簡單地調整分類閾值，說出什麼時候是不太確定的，或者獲得置信區間），或你期望未來接收更多想要快速並入模型中的訓練數據，就選擇邏輯回歸。

決策樹的優點：

易於說明和解釋（對某些人來說—我不確定自己是否屬於這個陣營）。它們可以很容易地處理特徵間的相互作用，並且是非參數化的，所以你不用擔心異常值或者數據是否線性可分（比如，決策樹可以很容易地某特徵x的低端是類A，中間是類B，然後高端又是類A的情況）。

一個缺點是，不支持在線學習，所以當有新樣本時，你將不得不重建決策樹。另一個缺點是，容易過擬合，但這也正是諸如隨機森林（或提高樹）之類的集成方法的切入點。另外，隨機森林往往是很多分類問題的贏家（我相信通常略優於支持向量機），它們快速並且可擴展，同時你不須擔心要像支持向量機那樣調一堆參數，所以它們最近似乎相當受歡迎。

(1)分類樹演算法擴展閱讀：

樸素貝葉斯演算法：

設每個數據樣本用一個n維特徵向量來描述n個屬性的值，即：X={x1，x2，…，xn}，假定有m個類，分別用C1, C2,…，Cm表示。給定一個未知的數據樣本X（即沒有類標號），若樸素貝葉斯分類法將未知的樣本X分配給類Ci，則一定是

P(Ci|X)>P(Cj|X) 1≤j≤m，j≠i

根據貝葉斯定理：

由於P(X)對於所有類為常數，最大化後驗概率P(Ci|X)可轉化為最大化先驗概率P(X|Ci)P(Ci)。如果訓練數據集有許多屬性和元組，計算P(X|Ci)的開銷可能非常大，為此，通常假設各屬性的取值互相獨立，這樣

先驗概率P(x1|Ci)，P(x2|Ci)，…，P(xn|Ci)可以從訓練數據集求得。

根據此方法，對一個未知類別的樣本X，可以先分別計算出X屬於每一個類別Ci的概率P(X|Ci)P(Ci)，然後選擇其中概率最大的類別作為其類別。

樸素貝葉斯演算法成立的前提是各屬性之間互相獨立。當數據集滿足這種獨立性假設時,分類的准確度較高，否則可能較低。另外，該演算法沒有分類規則輸出。

TAN演算法（樹增強型樸素貝葉斯演算法）

TAN演算法通過發現屬性對之間的依賴關系來降低NB中任意屬性之間獨立的假設。它是在NB網路結構的基礎上增加屬性對之間的關聯(邊)來實現的。

實現方法是：用結點表示屬性，用有向邊表示屬性之間的依賴關系，把類別屬性作為根結點，其餘所有屬性都作為它的子節點。通常，用虛線代表NB所需的邊，用實線代表新增的邊。屬性Ai與Aj之間的邊意味著屬性Ai對類別變數C的影響還取決於屬性Aj的取值。

這些增加的邊需滿足下列條件：類別變數沒有雙親結點，每個屬性有一個類別變數雙親結點和最多另外一個屬性作為其雙親結點。

Ⅱ 名詞解釋 決策樹

決策樹(Decision Tree）是在已知各種情況發生概率的基礎上，通過構成決策樹來求取凈現值的期望值大於等於零的概率，評價項目風險，判斷其可行性的決策分析方法，是直觀運用概率分析的一種圖解法。由於這種決策分支畫成圖形很像一棵樹的枝幹，故稱決策樹。在機器學習中，決策樹是一個預測模型，他代表的是對象屬性與對象值之間的一種映射關系。Entropy = 系統的凌亂程度，使用演算法ID3, C4.5和C5.0生成樹演算法使用熵。這一度量是基於信息學理論中熵的概念。
決策樹是一種樹形結構，其中每個內部節點表示一個屬性上的測試，每個分支代表一個測試輸出，每個葉節點代表一種類別。
分類樹（決策樹）是一種十分常用的分類方法。他是一種監管學習，所謂監管學習就是給定一堆樣本，每個樣本都有一組屬性和一個類別，這些類別是事先確定的，那麼通過學習得到一個分類器，這個分類器能夠對新出現的對象給出正確的分類。這樣的機器學習就被稱之為監督學習。

Ⅲ 決策樹ID3，C4.5，CART演算法中某一屬性分類後，是否能運用該屬性繼續分類

決策樹主要有ID3，C4.5，CART等形式。ID3選取信息增益的屬性遞歸進行分類，C4.5改進為使用信息增益率來選取分類屬性。CART是Classfication and Regression Tree的縮寫。表明CART不僅可以進行分類，也可以進行回歸。其中使用基尼系數選取分類屬性。以下主要介紹ID3和CART演算法。
ID3演算法：
信息熵： H(X)=-sigma（對每一個x）（plogp） H(Y|X)=sigma(對每一個x)（pH(Y|X=xi)）
信息增益：H（D）-H(D|X) H(D)是整個數據集的熵
信息增益率：（H(D)-H(D|X)）/H(X)
演算法流程：（1）對每一個屬性計算信息增益，若信息增益小於閾值，則將該支置為葉節點，選擇其中個數最多的類標簽作為該類的類標簽。否則，選擇其中最大的作為分類屬 性。
（2）若各個分支中都只含有同一類數據，則將這支置為葉子節點。
否則 繼續進行（1）。
CART演算法：
基尼系數：Gini（p）=sigma（每一個類）p(1-p)
回歸樹：屬性值為連續實數。將整個輸入空間劃分為m塊，每一塊以其平均值作為輸出。f(x)=sigma(每一塊)Cm*I(x屬於Rm)
回歸樹生成：（1）選取切分變數和切分點，將輸入空間分為兩份。
（2）每一份分別進行第一步，直到滿足停止條件。
切分變數和切分點選取：對於每一個變數進行遍歷，從中選擇切分點。選擇一個切分點滿足分類均方誤差最小。然後在選出所有變數中最小分類誤差最小的變數作為切分 變數。
分類樹：屬性值為離散值。
分類樹生成：（1）根據每一個屬性的每一個取值，是否取該值將樣本分成兩類，計算基尼系數。選擇基尼系數最小的特徵和屬性值，將樣本分成兩份。
（2）遞歸調用（1）直到無法分割。完成CART樹生成。

決策樹剪枝策略：
預剪枝（樹提前停止生長）和後剪枝（完全生成以後減去一些子樹提高預測准確率）
降低錯誤率剪枝：自下而上對每一個內部節點比較減去以其為葉節點和子樹的准確率。如果減去准確率提高，則減去，依次類推知道准確率不在提高。
代價復雜度剪枝：從原始決策樹T0開始生成一個子樹序列{T0、T1、T2、...、Tn},其中Ti+1是從Ti總產生，Tn為根節點。每次均從Ti中 減去具有最小誤差增長率的子樹。然後通過 交叉驗證比較序列中各子樹的效果選擇最優決策樹。

Ⅳ 決策樹CART演算法優點和缺點

CART的全稱是分類和回歸樹，既可以做分類演算法，也可以做回歸。
決策樹的優缺點：
優點：

1.可以生成可以理解的規則。
2.計算量相對來說不是很大。
3.可以處理連續和種類欄位。
4.決策樹可以清晰的顯示哪些欄位比較重要
缺點：

1. 對連續性的欄位比較難預測。
2.對有時間順序的數據，需要很多預處理的工作。
3.當類別太多時，錯誤可能就會增加的比較快。
4.一般的演算法分類的時候，只是根據一個欄位來分類。

Ⅳ 決策樹演算法是按什麼來進行分類的

決策樹演算法是一種逼近離散函數值的方法。它是一種典型的分類方法，首先對數據進行處理，利用歸納演算法生成可讀的規則和決策樹，然後使用決策對新數據進行分析。本質上決策樹是通過一系列規則對數據進行分類的過程。
決策樹方法最早產生於上世紀60年代，到70年代末。由J Ross Quinlan提出了ID3演算法，此演算法的目的在於減少樹的深度。但是忽略了葉子數目的研究。C4.5演算法在ID3演算法的基礎上進行了改進，對於預測變數的缺值處理、剪枝技術、派生規則等方面作了較大改進，既適合於分類問題，又適合於回歸問題。
決策樹演算法構造決策樹來發現數據中蘊涵的分類規則．如何構造精度高、規模小的決策樹是決策樹演算法的核心內容。決策樹構造可以分兩步進行。第一步，決策樹的生成：由訓練樣本集生成決策樹的過程。一般情況下，訓練樣本數據集是根據實際需要有歷史的、有一定綜合程度的，用於數據分析處理的數據集。第二步，決策樹的剪枝：決策樹的剪枝是對上一階段生成的決策樹進行檢驗、校正和修下的過程，主要是用新的樣本數據集（稱為測試數據集）中的數據校驗決策樹生成過程中產生的初步規則，將那些影響預衡准確性的分枝剪除。

Ⅵ 決策樹演算法原理

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

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

一棵決策樹的生成過程主要分為以下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。 當特徵在大多數樣本中具有零值時，與密集矩陣相比，稀疏矩陣輸入的訓練時間可以快幾個數量級。

Ⅶ GBDT與XGBoost

之前介紹過 梯度下降法與牛頓法 ，GBDT與XGBoost就與這兩種方法有關。

GBDT泛指所有梯度提升樹演算法，包括XGBoost，它也是GBDT的一種變種，為了區分它們，GBDT一般特指「Greedy Function Approximation：A Gradient Boosting Machine」里提出的演算法，只用了一階導數信息。

演算法流程如下：

演算法流程圖也可以如下圖：

GBDT常用損失函數
分類演算法：
分類演算法中CART樹也是採用回歸樹
(1) 指數損失函數：

負梯度計算和葉子節點的最佳負梯度擬合與Adaboost相似。
(2) 對數損失函數：
二元分類：

多元分類：

回歸演算法：
(1)均方差：

(2)絕對損失：

負梯度誤差為：

(3)Huber損失：
均方差和絕對損失的折中，對遠離中心的異常點，採用絕對損失，而中心附近的點採用均方差。界限一般用分位數點度量。損失函數如下：

負梯度誤差：

(4) 分位數損失：分位數回歸的損失函數，表達式為

θ為分位數，需要我們在回歸前指定。對應的負梯度誤差為：

Huber損失和分位數損失，減少異常點對損失函數的影響。

問題：GBDT如何減少異常點的影響？

GBDT優點：

GBDT缺點：

Adaboost與GBDT：

RF與GBDT：

RF優點：

RF缺點：

XGBoost目標函數及歸一化公式

歸一化解釋

XGBoost參數定義

XGBoost第t次迭代： 訓練第t棵子樹，損失函數最小求參數，計算過程如下

假設分到j這個葉子節點上的樣本只有一個。那麼，w* j 如下：

回歸樹的學習策略

XGBoost的打分函數

樹節點分裂方法

尋找分為點可以使用Weighted Quantile Sketch—分布式加權直方圖演算法

稀疏值處理

關鍵的改進是只訪問非缺失的條目I k 。 所提出的演算法將不存在的值視為缺失值並且學習處理缺失值的最佳方向。稀疏感知演算法運行速度比初始版本快50倍

XGBoost的其它特性

Shrinkage and Column Subsampling
Shrinkage and Column Subsampling均是為了防止過擬合

XGBoost的系統設計

Column Block
xgboost的並行不是tree粒度的並行，而是特徵粒度上。

緩存感知訪問（Cache-aware Access）

XGBoost的優點

XGBoost與GBDT對比

問題：XGBoost為什麼使用CART樹而不是用普通的決策樹呢？

XGBoost參數說明

回歸樹 生成演算法如下，使用最小二乘偏差（LSD）。

分類樹 演算法流程如下，使用GINI指數

GINI 指數：

分類中，假設 K 個類，樣本屬於第 k 類的概率為 p k ，概率分布的基尼指數為：

樣本集合 D 的基尼指數為：

C k 為數據集D中屬於第k類的樣本子集，| * |表示樣本集中樣本的個數。
數據集 D 根據特徵 A 在某一取值 a 上進行分割，得到 D 1 、D 2 兩部分，則在特徵 A 下集合 D 的基尼指數為：

停止條件：

剪枝
決策樹防止過擬合方法：

代價復雜度剪枝 Cost-Complexity Pruning(CCP) 方法對CART剪枝，演算法流程如下：

其中 C(T)為誤差（例如基尼指數），|T| 為 T 的葉節點個數，alpha 為非負參數，用來權衡訓練數據的擬合程度和模型的復雜度。

剪枝例子如下：

例如 t 1 節點，R(t)即剪枝後誤差，數據所佔比例16/16，節點誤差率 = 該節點較少類別的數/該節點類別總數 = 8/16
R(Tt)為剪枝前誤差，即葉子節點誤差之和，以該節點為根節點的4葉子節點均只有一個類別的樣本，該節點較少類別的數/該節點類別總數 = 0，所以R(Tt) = 0

參考

Ⅷ 決策樹演算法是按什麼來進行分類的

決策樹演算法是一種逼近離散函數值的方法。它是一種典型的分類方法，首先對數據進行處理，利用歸納演算法生成可讀的規則和決策樹，然後使用決策對新數據進行分析。本質上決策樹是通過一系列規則對數據進行分類的過程。
決策樹方法最早產生於上世紀60年代，到70年代末。由J
Ross
Quinlan提出了ID3演算法，此演算法的目的在於減少樹的深度。但是忽略了葉子數目的研究。C4.5演算法在ID3演算法的基礎上進行了改進，對於預測變數的缺值處理、剪枝技術、派生規則等方面作了較大改進，既適合於分類問題，又適合於回歸問題。
決策樹演算法構造決策樹來發現數據中蘊涵的分類規則．如何構造精度高、規模小的決策樹是決策樹演算法的核心內容。決策樹構造可以分兩步進行。第一步，決策樹的生成：由訓練樣本集生成決策樹的過程。一般情況下，訓練樣本數據集是根據實際需要有歷史的、有一定綜合程度的，用於數據分析處理的數據集。第二步，決策樹的剪枝：決策樹的剪枝是對上一階段生成的決策樹進行檢驗、校正和修下的過程，主要是用新的樣本數據集（稱為測試數據集）中的數據校驗決策樹生成過程中產生的初步規則，將那些影響預衡准確性的分枝剪除。