大數據演算法決策樹

㈠ 決策樹演算法-原理篇

關於決策樹演算法，我打算分兩篇來講，一篇講思想原理，另一篇直接擼碼來分析演算法。本篇為原理篇。
通過閱讀這篇文章，你可以學到：
1、決策樹的本質
2、決策樹的構造過程
3、決策樹的優化方向

決策樹根據使用目的分為：分類樹和回歸樹，其本質上是一樣的。本文只講分類樹。

決策樹，根據名字來解釋就是，使用樹型結構來模擬決策。
用圖形表示就是下面這樣。

其中橢圓形代表：特徵或屬性。長方形代表：類別結果。
面對一堆數據（含有特徵和類別），決策樹就是根據這些特徵（橢圓形）來給數據歸類（長方形）
例如，信用貸款問題，我根據《神奇動物在哪裡》的劇情給銀行造了個決策樹模型，如下圖：

然而，決定是否貸款可以根據很多特徵，然麻雞銀行選擇了：（1）是否房產價值>100w；（2）是否有其他值錢的抵押物；（3）月收入>10k；（4）是否結婚；這四個特徵，來決定是否給予貸款。
先不管是否合理，但可以肯定的是，決策樹做了特徵選擇工作，即選擇出類別區分度高的特徵。

由此可見， 決策樹其實是一種特徵選擇方法。 （特徵選擇有多種，決策樹屬於嵌入型特徵選擇，以後或許會講到，先給個圖）即選擇區分度高的特徵子集。

那麼， 從特徵選擇角度來看決策樹，決策樹就是嵌入型特徵選擇技術

同時，決策樹也是機器學習中經典分類器演算法，通過決策路徑，最終能確定實例屬於哪一類別。
那麼， 從分類器角度來看決策樹，決策樹就是樹型結構的分類模型

從人工智慧知識表示法角度來看，決策樹類似於if-then的產生式表示法。
那麼， 從知識表示角度來看決策樹，決策樹就是if-then規則的集合

由上面的例子可知，麻雞銀行通過決策樹模型來決定給哪些人貸款，這樣決定貸款的流程就是固定的，而不由人的主觀情感來決定。
那麼， 從使用者角度來看決策樹，決策樹就是規范流程的方法

最後我們再來看看決策樹的本質是什麼已經不重要了。
決策樹好像是一種思想，而通過應用在分類任務中從而成就了「決策樹演算法」。

下面內容還是繼續講解用於分類的「決策樹演算法」。

前面講了決策樹是一種 特徵選擇技術 。

既然決策樹就是一種特徵選擇的方法，那麼經典決策樹演算法其實就是使用了不同的特徵選擇方案。
如：
（1）ID3：使用信息增益作為特徵選擇
（2）C4.5：使用信息增益率作為特徵選擇
（3）CART：使用GINI系數作為特徵選擇
具體選擇的方法網上一大把，在這里我提供幾個鏈接，不細講。

但，不僅僅如此。
決策樹作為嵌入型特徵選擇技術結合了特徵選擇和分類演算法，根據特徵選擇如何生成分類模型也是決策樹的一部分。
其生成過程基本如下：

根據這三個步驟，可以確定決策樹由：（1）特徵選擇；（2）生成方法；（3）剪枝，組成。
決策樹中學習演算法與特徵選擇的關系如下圖所示：

原始特徵集合T：就是包含收集到的原始數據所有的特徵，例如：麻瓜銀行收集到與是否具有償還能力的所有特徵，如：是否結婚、是否擁有100w的房產、是否擁有汽車、是否有小孩、月收入是否>10k等等。
中間的虛線框就是特徵選擇過程，例如：ID3使用信息增益、C4.5使用信息增益率、CART使用GINI系數。
其中評價指標（如：信息增益）就是對特徵的要求，特徵需要滿足這種條件（一般是某個閾值），才能被選擇，而這一選擇過程嵌入在學習演算法中，最終被選擇的特徵子集也歸到學習演算法中去。
這就是抽象的決策樹生成過程，不論哪種演算法都是將這一抽象過程的具體化。
其具體演算法我將留在下一篇文章來講解。

而決策樹的剪枝，其實用得不是很多，因為很多情況下隨機森林能解決決策樹帶來的過擬合問題，因此在這里也不講了。

決策樹的優化主要也是圍繞決策樹生成過程的三個步驟來進行優化的。
樹型結構，可想而知，演算法效率決定於樹的深度，優化這方面主要從特徵選擇方向上優化。
提高分類性能是最重要的優化目標，其主要也是特徵選擇。
面對過擬合問題，一般使用剪枝來優化，如：李國和基於決策樹生成及剪枝的數據集優化及其應用。
同時，決策樹有很多不足，如：多值偏向、計算效率低下、對數據空缺較為敏感等，這方面的優化也有很多，大部分也是特徵選擇方向，如：陳沛玲使用粗糙集進行特徵降維。
由此，決策樹的優化方向大多都是特徵選擇方向，像ID3、C4.5、CART都是基於特徵選擇進行優化。

參考文獻
統計學習方法-李航
特徵選擇方法綜述-李郅琴
決策樹分類演算法優化研究_陳沛玲
基於決策樹生成及剪枝的數據集優化及其應用-李國和

㈡ 決策樹演算法原理是什麼

決策樹構造的輸入是一組帶有類別標記的例子，構造的結果是一棵二叉樹或多叉樹。二叉樹的 內部節點(非 葉子節點)一般表示為一個邏輯判斷，如形式為a=aj的邏輯判斷，其中a是屬性，aj是該屬性的所有取值：樹的邊是邏輯判斷的分支結果。

多叉樹(ID3)的內部結點是屬性，邊是該屬性的所有取值，有幾個 屬性值就有幾條邊。樹的葉子節點都是類別標記。

由於數據表示不當、有雜訊或者由於決策樹生成時產生重復的子樹等原因，都會造成產生的決策樹過大。

因此，簡化決策樹是一個不可缺少的環節。尋找一棵最優決策樹，主要應解決以下3個最優化問題：①生成最少數目的葉子節點；②生成的每個葉子節點的深度最小；③生成的決策樹葉子節點最少且每個葉子節點的深度最小。

(2)大數據演算法決策樹擴展閱讀：

決策樹演算法的優點如下：

（1）分類精度高；

（2）生成的模式簡單；

（3）對雜訊數據有很好的健壯性。

因而是目前應用最為廣泛的歸納推理演算法之一，在 數據挖掘中受到研究者的廣泛關注。

㈢ 決策樹基本概念及演算法優缺點

分類決策樹模型是一種描述對實例進行分類的樹形結構. 決策樹由結點和有向邊組成. 結點有兩種類型: 內部結點和葉節點. 內部節點表示一個特徵或屬性, 葉節點表示一個類.
決策樹(Decision Tree),又稱為判定樹, 是一種以樹結構(包括二叉樹和多叉樹)形式表達的預測分析模型.

分類樹--對離散變數做決策樹

回歸樹--對連續變數做決策樹

優點:
(1)速度快: 計算量相對較小, 且容易轉化成分類規則. 只要沿著樹根向下一直走到葉, 沿途的分裂條件就能夠唯一確定一條分類的謂詞.
(2)准確性高: 挖掘出來的分類規則准確性高, 便於理解, 決策樹可以清晰的顯示哪些欄位比較重要, 即可以生成可以理解的規則.
(3)可以處理連續和種類欄位
(4)不需要任何領域知識和參數假設
(5)適合高維數據
缺點:
(1)對於各類別樣本數量不一致的數據, 信息增益偏向於那些更多數值的特徵
(2)容易過擬合
(3)忽略屬性之間的相關性

若一事假有k種結果, 對應概率為 , 則此事件發生後所得到的信息量I為:

給定包含關於某個目標概念的正反樣例的樣例集S, 那麼S相對這個布爾型分類的熵為:

其中 代表正樣例, 代表反樣例

假設隨機變數(X,Y), 其聯合分布概率為P(X=xi,Y=yi)=Pij, i=1,2,...,n;j=1,2,..,m
則條件熵H(Y|X)表示在已知隨機變數X的條件下隨機變數Y的不確定性, 其定義為X在給定條件下Y的條件概率分布的熵對X的數學期望

在Hunt演算法中, 通過遞歸的方式建立決策樹.

使用信息增益, 選擇 最高信息增益 的屬性作為當前節點的測試屬性

ID3( Examples,Target_attribute,Attributes )

Examples 即訓練樣例集. Target_attribute 是這棵樹要預測的目標屬性. Attributes 是除目標屬性外供學習到的決策樹測試的屬性列表. 返回能正確分類給定 Examples 的決策樹.

class sklearn.tree.DecisionTreeClassifier(criterion='gini', splitter='best', max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, class_weight=None, presort=False)

限制決策樹層數為4的DecisionTreeClassifier實例

This plot compares the decision surfaces learned by a dcision tree classifier(first column), by a random forest classifier(second column), by an extra-trees classifier(third column) and by an AdaBoost classifier(fouth column).

Output:

A comparison of a several classifiers in scikit-learn on synthetic datasets.
The point of this examples is to illustrate the nature of decision boundaries of different classifiers.

Particularly in high-dimensional spaces, data can more easily be separated linearly and the simplicity of classifiers such as naive Bayes and linear SVMs might lead to better generalization than is achieved by other classifiers.

This example fits an AdaBoost decisin stump on a non-linearly separable classification dataset composed of two "Gaussian quantiles" clusters and plots the decision boundary and decision scores.

Output:

㈣ 大數據挖掘的演算法有哪些

大數據挖掘的演算法：
1.樸素貝葉斯，超級簡單，就像做一些數數的工作。如果條件獨立假設成立的話，NB將比鑒別模型收斂的更快，所以你只需要少量的訓練數據。即使條件獨立假設不成立，NB在實際中仍然表現出驚人的好。
2. Logistic回歸，LR有很多方法來對模型正則化。比起NB的條件獨立性假設，LR不需要考慮樣本是否是相關的。與決策樹與支持向量機不同，NB有很好的概率解釋，且很容易利用新的訓練數據來更新模型。如果你想要一些概率信息或者希望將來有更多數據時能方便的更新改進模型，LR是值得使用的。
3.決策樹，DT容易理解與解釋。DT是非參數的，所以你不需要擔心野點（或離群點）和數據是否線性可分的問題，DT的主要缺點是容易過擬合，這也正是隨機森林等集成學習演算法被提出來的原因。
4.支持向量機，很高的分類正確率，對過擬合有很好的理論保證，選取合適的核函數，面對特徵線性不可分的問題也可以表現得很好。SVM在維數通常很高的文本分類中非常的流行。

如果想要或許更多更詳細的訊息，建議您去參加CDA數據分析課程。大數據分析師現在有專業的國際認證證書了，CDA，即「CDA 數據分析師」，是在數字經濟大背景和人工智慧時代趨勢下，面向全行業的專業權威國際資格認證， 旨在提升全民數字技能，助力企業數字化轉型，推動行業數字化發展。 「CDA 數據分析師」具體指在互聯網、金融、零售、咨詢、電信、醫療、旅遊等行業專門從事數據的採集、清洗、處理、分析並能製作業務報告、 提供決策的新型數據分析人才。點擊預約免費試聽課。

㈤ 大數據三大核心技術：拿數據、算數據、賣數據！

大數據的由來

對於「大數據」（Big data）研究機構Gartner給出了這樣的定義。「大數據」是需要新處理模式才能具有更強的決策力、洞察發現力和流程優化能力來適應海量、高增長率和多樣化的信息資產。

1

麥肯錫全球研究所給出的定義是：一種規模大到在獲取、存儲、管理、分析方面大大超出了傳統資料庫軟體工具能力范圍的數據集合，具有海量的數據規模、快速的數據流轉、多樣的數據類型和價值密度低四大特徵。

大數據技術的戰略意義不在於掌握龐大的數據信息，而在於對這些含有意義的數據進行專業化處理。換而言之，如果把大數據比作一種產業，那麼這種產業實現盈利的關鍵，在於提高對數據的「加工能力」，通過「加工」實現數據的「增值」。

從技術上看，大數據與雲計算的關系就像一枚硬幣的正反面一樣密不可分。大數據必然無法用單台的計算機進行處理，必須採用分布式架構。它的特色在於對海量數據進行分布式數據挖掘。但它必須依託雲計算的分布式處理、分布式資料庫和雲存儲、虛擬化技術。

大數據需要特殊的技術，以有效地處理大量的容忍經過時間內的數據。適用於大數據的技術，包括大規模並行處理（MPP）資料庫、數據挖掘、分布式文件系統、分布式資料庫、雲計算平台、互聯網和可擴展的存儲系統。

最小的基本單位是bit，按順序給出所有單位：bit、Byte、KB、MB、GB、TB、PB、EB、ZB、YB、BB、NB、DB。

大數據的應用領域

大數據無處不在，大數據應用於各個行業，包括金融、 汽車 、餐飲、電信、能源、體能和 娛樂 等在內的 社會 各行各業都已經融入了大數據的印跡。

製造業，利用工業大數據提升製造業水平，包括產品故障診斷與預測、分析工藝流程、改進生產工藝，優化生產過程能耗、工業供應鏈分析與優化、生產計劃與排程。

金融行業，大數據在高頻交易、社交情緒分析和信貸風險分析三大金融創新領域發揮重大作用。

汽車 行業，利用大數據和物聯網技術的無人駕駛 汽車 ，在不遠的未來將走入我們的日常生活。

互聯網行業，藉助於大數據技術，可以分析客戶行為，進行商品推薦和針對性廣告投放。

電信行業，利用大數據技術實現客戶離網分析，及時掌握客戶離網傾向，出台客戶挽留措施。

能源行業，隨著智能電網的發展，電力公司可以掌握海量的用戶用電信息，利用大數據技術分析用戶用電模式，可以改進電網運行，合理設計電力需求響應系統，確保電網運行安全。

物流行業，利用大數據優化物流網路，提高物流效率，降低物流成本。

城市管理，可以利用大數據實現智能交通、環保監測、城市規劃和智能安防。

體育 娛樂 ，大數據可以幫助我們訓練球隊，決定投拍哪種 題財的 影視作品，以及預測比賽結果。

安全領域，政府可以利用大數據技術構建起強大的國家安全保障體系，企業可以利用大數據抵禦網路攻擊，警察可以藉助大數據來預防犯罪。

個人生活， 大數據還可以應用於個人生活，利用與每個人相關聯的「個人大數據」，分析個人生活行為習慣，為其提供更加周到的個性化服務。

大數據的價值，遠遠不止於此，大數據對各行各業的滲透，大大推動了 社會 生產和生活，未來必將產生重大而深遠的影響。

大數據方面核心技術有哪些？

大數據技術的體系龐大且復雜，基礎的技術包含數據的採集、數據預處理、分布式存儲、NoSQL資料庫、數據倉庫、機器學習、並行計算、可視化等各種技術范疇和不同的技術層面。首先給出一個通用化的大數據處理框架，主要分為下面幾個方面：數據採集與預處理、數據存儲、數據清洗、數據查詢分析和數據可視化。

數據採集與預處理

對於各種來源的數據，包括移動互聯網數據、社交網路的數據等，這些結構化和非結構化的海量數據是零散的，也就是所謂的數據孤島，此時的這些數據並沒有什麼意義，數據採集就是將這些數據寫入數據倉庫中，把零散的數據整合在一起，對這些數據綜合起來進行分析。數據採集包括文件日誌的採集、資料庫日誌的採集、關系型資料庫的接入和應用程序的接入等。在數據量比較小的時候，可以寫個定時的腳本將日誌寫入存儲系統，但隨著數據量的增長，這些方法無法提供數據安全保障，並且運維困難，需要更強壯的解決方案。

Flume NG

Flume NG作為實時日誌收集系統，支持在日誌系統中定製各類數據發送方，用於收集數據，同時，對數據進行簡單處理，並寫到各種數據接收方(比如文本，HDFS，Hbase等)。Flume NG採用的是三層架構：Agent層，Collector層和Store層，每一層均可水平拓展。其中Agent包含Source，Channel和 Sink，source用來消費(收集)數據源到channel組件中，channel作為中間臨時存儲，保存所有source的組件信息，sink從channel中讀取數據，讀取成功之後會刪除channel中的信息。

NDC

Logstash

Logstash是開源的伺服器端數據處理管道，能夠同時從多個來源採集數據、轉換數據，然後將數據發送到您最喜歡的 「存儲庫」 中。一般常用的存儲庫是Elasticsearch。Logstash 支持各種輸入選擇，可以在同一時間從眾多常用的數據來源捕捉事件，能夠以連續的流式傳輸方式，輕松地從您的日誌、指標、Web 應用、數據存儲以及各種 AWS 服務採集數據。

Sqoop

Sqoop，用來將關系型資料庫和Hadoop中的數據進行相互轉移的工具，可以將一個關系型資料庫(例如Mysql、Oracle)中的數據導入到Hadoop(例如HDFS、Hive、Hbase)中，也可以將Hadoop(例如HDFS、Hive、Hbase)中的數據導入到關系型資料庫(例如Mysql、Oracle)中。Sqoop 啟用了一個 MapRece 作業(極其容錯的分布式並行計算)來執行任務。Sqoop 的另一大優勢是其傳輸大量結構化或半結構化數據的過程是完全自動化的。

流式計算

流式計算是行業研究的一個熱點，流式計算對多個高吞吐量的數據源進行實時的清洗、聚合和分析，可以對存在於社交網站、新聞等的數據信息流進行快速的處理並反饋，目前大數據流分析工具有很多，比如開源的strom，spark streaming等。

Strom集群結構是有一個主節點(nimbus)和多個工作節點(supervisor)組成的主從結構，主節點通過配置靜態指定或者在運行時動態選舉，nimbus與supervisor都是Storm提供的後台守護進程，之間的通信是結合Zookeeper的狀態變更通知和監控通知來處理。nimbus進程的主要職責是管理、協調和監控集群上運行的topology(包括topology的發布、任務指派、事件處理時重新指派任務等)。supervisor進程等待nimbus分配任務後生成並監控worker(jvm進程)執行任務。supervisor與worker運行在不同的jvm上，如果由supervisor啟動的某個worker因為錯誤異常退出(或被kill掉)，supervisor會嘗試重新生成新的worker進程。

Zookeeper

Zookeeper是一個分布式的，開放源碼的分布式應用程序協調服務，提供數據同步服務。它的作用主要有配置管理、名字服務、分布式鎖和集群管理。配置管理指的是在一個地方修改了配置，那麼對這個地方的配置感興趣的所有的都可以獲得變更，省去了手動拷貝配置的繁瑣，還很好的保證了數據的可靠和一致性，同時它可以通過名字來獲取資源或者服務的地址等信息，可以監控集群中機器的變化，實現了類似於心跳機制的功能。

數據存儲

Hadoop作為一個開源的框架，專為離線和大規模數據分析而設計，HDFS作為其核心的存儲引擎，已被廣泛用於數據存儲。

HBase

HBase，是一個分布式的、面向列的開源資料庫，可以認為是hdfs的封裝，本質是數據存儲、NoSQL資料庫。HBase是一種Key/Value系統，部署在hdfs上，克服了hdfs在隨機讀寫這個方面的缺點，與hadoop一樣，Hbase目標主要依靠橫向擴展，通過不斷增加廉價的商用伺服器，來增加計算和存儲能力。

Phoenix

Phoenix，相當於一個Java中間件，幫助開發工程師能夠像使用JDBC訪問關系型資料庫一樣訪問NoSQL資料庫HBase。

Yarn

Yarn是一種Hadoop資源管理器，可為上層應用提供統一的資源管理和調度，它的引入為集群在利用率、資源統一管理和數據共享等方面帶來了巨大好處。Yarn由下面的幾大組件構成：一個全局的資源管理器ResourceManager、ResourceManager的每個節點代理NodeManager、表示每個應用的Application以及每一個ApplicationMaster擁有多個Container在NodeManager上運行。

Mesos

Mesos是一款開源的集群管理軟體，支持Hadoop、ElasticSearch、Spark、Storm 和Kafka等應用架構。

Redis

Redis是一種速度非常快的非關系資料庫，可以存儲鍵與5種不同類型的值之間的映射，可以將存儲在內存的鍵值對數據持久化到硬碟中，使用復制特性來擴展性能，還可以使用客戶端分片來擴展寫性能。

Atlas

Atlas是一個位於應用程序與MySQL之間的中間件。在後端DB看來，Atlas相當於連接它的客戶端，在前端應用看來，Atlas相當於一個DB。Atlas作為服務端與應用程序通訊，它實現了MySQL的客戶端和服務端協議，同時作為客戶端與MySQL通訊。它對應用程序屏蔽了DB的細節，同時為了降低MySQL負擔，它還維護了連接池。Atlas啟動後會創建多個線程，其中一個為主線程，其餘為工作線程。主線程負責監聽所有的客戶端連接請求，工作線程只監聽主線程的命令請求。

Ku

Ku是圍繞Hadoop生態圈建立的存儲引擎，Ku擁有和Hadoop生態圈共同的設計理念，它運行在普通的伺服器上、可分布式規模化部署、並且滿足工業界的高可用要求。其設計理念為fast analytics on fast data。作為一個開源的存儲引擎，可以同時提供低延遲的隨機讀寫和高效的數據分析能力。Ku不但提供了行級的插入、更新、刪除API，同時也提供了接近Parquet性能的批量掃描操作。使用同一份存儲，既可以進行隨機讀寫，也可以滿足數據分析的要求。Ku的應用場景很廣泛，比如可以進行實時的數據分析，用於數據可能會存在變化的時序數據應用等。

在數據存儲過程中，涉及到的數據表都是成千上百列，包含各種復雜的Query，推薦使用列式存儲方法，比如parquent,ORC等對數據進行壓縮。Parquet 可以支持靈活的壓縮選項，顯著減少磁碟上的存儲。

數據清洗

MapRece作為Hadoop的查詢引擎，用於大規模數據集的並行計算，」Map(映射)」和」Rece(歸約)」，是它的主要思想。它極大的方便了編程人員在不會分布式並行編程的情況下，將自己的程序運行在分布式系統中。

隨著業務數據量的增多，需要進行訓練和清洗的數據會變得越來越復雜，這個時候就需要任務調度系統，比如oozie或者azkaban，對關鍵任務進行調度和監控。

Oozie

Oozie是用於Hadoop平台的一種工作流調度引擎，提供了RESTful API介面來接受用戶的提交請求(提交工作流作業)，當提交了workflow後，由工作流引擎負責workflow的執行以及狀態的轉換。用戶在HDFS上部署好作業(MR作業)，然後向Oozie提交Workflow，Oozie以非同步方式將作業(MR作業)提交給Hadoop。這也是為什麼當調用Oozie 的RESTful介面提交作業之後能立即返回一個JobId的原因，用戶程序不必等待作業執行完成(因為有些大作業可能會執行很久(幾個小時甚至幾天))。Oozie在後台以非同步方式，再將workflow對應的Action提交給hadoop執行。

Azkaban

Azkaban也是一種工作流的控制引擎，可以用來解決有多個hadoop或者spark等離線計算任務之間的依賴關系問題。azkaban主要是由三部分構成：Relational Database，Azkaban Web Server和Azkaban Executor Server。azkaban將大多數的狀態信息都保存在MySQL中，Azkaban Web Server提供了Web UI，是azkaban主要的管理者，包括project的管理、認證、調度以及對工作流執行過程中的監控等;Azkaban Executor Server用來調度工作流和任務，記錄工作流或者任務的日誌。

流計算任務的處理平台Sloth，是網易首個自研流計算平台，旨在解決公司內各產品日益增長的流計算需求。作為一個計算服務平台，其特點是易用、實時、可靠，為用戶節省技術方面(開發、運維)的投入，幫助用戶專注於解決產品本身的流計算需求

數據查詢分析

Hive

Hive的核心工作就是把SQL語句翻譯成MR程序，可以將結構化的數據映射為一張資料庫表，並提供 HQL(Hive SQL)查詢功能。Hive本身不存儲和計算數據，它完全依賴於HDFS和MapRece。可以將Hive理解為一個客戶端工具，將SQL操作轉換為相應的MapRece jobs，然後在hadoop上面運行。Hive支持標準的SQL語法，免去了用戶編寫MapRece程序的過程，它的出現可以讓那些精通SQL技能、但是不熟悉MapRece 、編程能力較弱與不擅長Java語言的用戶能夠在HDFS大規模數據集上很方便地利用SQL 語言查詢、匯總、分析數據。

Hive是為大數據批量處理而生的，Hive的出現解決了傳統的關系型資料庫(MySql、Oracle)在大數據處理上的瓶頸 。Hive 將執行計劃分成map->shuffle->rece->map->shuffle->rece…的模型。如果一個Query會被編譯成多輪MapRece，則會有更多的寫中間結果。由於MapRece執行框架本身的特點，過多的中間過程會增加整個Query的執行時間。在Hive的運行過程中，用戶只需要創建表，導入數據，編寫SQL分析語句即可。剩下的過程由Hive框架自動的完成。

Impala

Impala是對Hive的一個補充，可以實現高效的SQL查詢。使用Impala來實現SQL on Hadoop，用來進行大數據實時查詢分析。通過熟悉的傳統關系型資料庫的SQL風格來操作大數據，同時數據也是可以存儲到HDFS和HBase中的。Impala沒有再使用緩慢的Hive+MapRece批處理，而是通過使用與商用並行關系資料庫中類似的分布式查詢引擎(由Query Planner、Query Coordinator和Query Exec Engine三部分組成)，可以直接從HDFS或HBase中用SELECT、JOIN和統計函數查詢數據，從而大大降低了延遲。Impala將整個查詢分成一執行計劃樹，而不是一連串的MapRece任務，相比Hive沒了MapRece啟動時間。

Hive 適合於長時間的批處理查詢分析，而Impala適合於實時互動式SQL查詢，Impala給數據人員提供了快速實驗，驗證想法的大數據分析工具，可以先使用Hive進行數據轉換處理，之後使用Impala在Hive處理好後的數據集上進行快速的數據分析。總的來說：Impala把執行計劃表現為一棵完整的執行計劃樹，可以更自然地分發執行計劃到各個Impalad執行查詢，而不用像Hive那樣把它組合成管道型的map->rece模式，以此保證Impala有更好的並發性和避免不必要的中間sort與shuffle。但是Impala不支持UDF，能處理的問題有一定的限制。

Spark

Spark擁有Hadoop MapRece所具有的特點，它將Job中間輸出結果保存在內存中，從而不需要讀取HDFS。Spark 啟用了內存分布數據集，除了能夠提供互動式查詢外，它還可以優化迭代工作負載。Spark 是在 Scala 語言中實現的，它將 Scala 用作其應用程序框架。與 Hadoop 不同，Spark 和 Scala 能夠緊密集成，其中的 Scala 可以像操作本地集合對象一樣輕松地操作分布式數據集。

Nutch

Nutch 是一個開源Java 實現的搜索引擎。它提供了我們運行自己的搜索引擎所需的全部工具，包括全文搜索和Web爬蟲。

Solr

Solr用Java編寫、運行在Servlet容器(如Apache Tomcat或Jetty)的一個獨立的企業級搜索應用的全文搜索伺服器。它對外提供類似於Web-service的API介面，用戶可以通過http請求，向搜索引擎伺服器提交一定格式的XML文件，生成索引;也可以通過Http Get操作提出查找請求，並得到XML格式的返回結果。

Elasticsearch

Elasticsearch是一個開源的全文搜索引擎，基於Lucene的搜索伺服器，可以快速的儲存、搜索和分析海量的數據。設計用於雲計算中，能夠達到實時搜索，穩定，可靠，快速，安裝使用方便。

還涉及到一些機器學習語言，比如，Mahout主要目標是創建一些可伸縮的機器學習演算法，供開發人員在Apache的許可下免費使用;深度學習框架Caffe以及使用數據流圖進行數值計算的開源軟體庫TensorFlow等，常用的機器學習演算法比如，貝葉斯、邏輯回歸、決策樹、神經網路、協同過濾等。

數據可視化

對接一些BI平台，將分析得到的數據進行可視化，用於指導決策服務。主流的BI平台比如，國外的敏捷BI Tableau、Qlikview、PowrerBI等，國內的SmallBI和新興的網易有數等。

在上面的每一個階段，保障數據的安全是不可忽視的問題。

基於網路身份認證的協議Kerberos，用來在非安全網路中，對個人通信以安全的手段進行身份認證，它允許某實體在非安全網路環境下通信，向另一個實體以一種安全的方式證明自己的身份。

控制許可權的ranger是一個Hadoop集群許可權框架，提供操作、監控、管理復雜的數據許可權，它提供一個集中的管理機制，管理基於yarn的Hadoop生態圈的所有數據許可權。可以對Hadoop生態的組件如Hive，Hbase進行細粒度的數據訪問控制。通過操作Ranger控制台，管理員可以輕松的通過配置策略來控制用戶訪問HDFS文件夾、HDFS文件、資料庫、表、欄位許可權。這些策略可以為不同的用戶和組來設置，同時許可權可與hadoop無縫對接。

簡單說有三大核心技術：拿數據，算數據，賣數據。

㈥ 決策樹法分為那幾個步驟

1、特徵選擇

特徵選擇決定了使用哪些特徵來做判斷。在訓練數據集中，每個樣本的屬性可能有很多個，不同屬性的作用有大有小。因而特徵選擇的作用就是篩選出跟分類結果相關性較高的特徵，也就是分類能力較強的特徵。在特徵選擇中通常使用的准則是：信息增益。

2、決策樹生成

選擇好特徵後，就從根節點觸發，對節點計算所有特徵的信息增益，選擇信息增益最大的特徵作為節點特徵，根據該特徵的不同取值建立子節點；對每個子節點使用相同的方式生成新的子節點，直到信息增益很小或者沒有特徵可以選擇為止。

3、決策樹剪枝

剪枝的主要目的是對抗「過擬合」，通過主動去掉部分分支來降低過擬合的風險。

【簡介】

決策樹是一種解決分類問題的演算法，決策樹演算法採用樹形結構，使用層層推理來實現最終的分類。

㈦ 決策樹演算法

決策樹演算法的演算法理論和應用場景

演算法理論：

我了解的決策樹演算法，主要有三種，最早期的ID3，再到後來的C4.5和CART這三種演算法。

這三種演算法的大致框架近似。

決策樹的學習過程

1.特徵選擇

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

2.決策樹生成

根據選擇的特徵評估標准，從上至下遞歸生成子節點，直到數據集不可分或者最小節點滿足閾值，此時決策樹停止生長。

3.剪枝

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

有些演算法用剪枝過程，有些沒有，如ID3。

預剪枝：對每個結點劃分前先進行估計，若當前結點的劃分不能帶來決策樹的泛化性能的提升，則停止劃分，並標記為葉結點。

後剪枝：現從訓練集生成一棵完整的決策樹，然後自底向上對非葉子結點進行考察，若該結點對應的子樹用葉結點能帶來決策樹泛化性能的提升，則將該子樹替換為葉結點。

但不管是預剪枝還是後剪枝都是用驗證集的數據進行評估。

ID3演算法是最早成型的決策樹演算法。ID3的演算法核心是在決策樹各個節點上應用信息增益准則來選擇特徵，遞歸構建決策樹。缺點是，在選擇分裂變數時容易選擇分類多的特徵，如ID值【值越多、分叉越多，子節點的不純度就越小，信息增益就越大】。

ID3之所以無法 處理缺失值、無法處理連續值、不剪紙等情況，主要是當時的重點並不是這些。

C4.5演算法與ID3近似，只是分裂標准從 信息增益 轉變成  信息增益率。可以處理連續值，含剪枝，可以處理缺失值，這里的做法多是 概率權重。

CART：1.可以處理連續值 2.可以進行缺失值處理 3.支持剪枝 4.可以分類可以回歸。

缺失值的處理是 作為一個單獨的類別進行分類。

建立CART樹

我們的演算法從根節點開始，用訓練集遞歸的建立CART樹。

1) 對於當前節點的數據集為D，如果樣本個數小於閾值或者沒有特徵，則返回決策子樹，當前節點停止遞歸。

2) 計算樣本集D的基尼系數， 如果基尼系數小於閾值 （說明已經很純了！！不需要再分了！！），則返回決策樹子樹，當前節點停止遞歸。

3) 計算當前節點現有的各個特徵的各個特徵值對數據集D的基尼系數。

4) 在計算出來的各個特徵的各個特徵值對數據集D的基尼系數中，選擇 基尼系數最小的特徵A和對應的特徵值a。根據這個最優特徵和最優特徵值，把數據集劃分成兩部分D1和D2，同時建立當前節點的左右節點，做節點的數據集D為D1，右節點的數據集D為D2。 (註：注意是二叉樹，故這里的D1和D2是有集合關系的，D2=D-D1)

5) 對左右的子節點遞歸的調用1-4步，生成決策樹。

CART採用的辦法是後剪枝法，即先生成決策樹，然後產生所有可能的剪枝後的CART樹，然後使用交叉驗證來檢驗各種剪枝的效果，選擇泛化能力最好的剪枝策略。

應用場景

比如欺詐問題中，通過決策樹演算法簡單分類，默認是CART的分類樹，默認不剪枝。然後在出圖後，自行選擇合適的葉節點進行拒絕操作。

這個不剪枝是因為欺詐問題的特殊性，欺詐問題一般而言較少，如數據的萬幾水平，即正樣本少，而整個欺詐問題需要解決的速度較快。此時只能根據業務要求，迅速針對已有的正樣本情況，在控制准確率的前提下，盡可能提高召回率。這種情況下，可以使用決策樹來簡單應用，這個可以替代原本手工選擇特徵及特徵閾值的情況。

㈧ 大數據經典演算法解析（1）一C4.5演算法

姓名：崔升    學號：14020120005

【嵌牛導讀】：

C4.5作為一種經典的處理大數據的演算法，是我們在學習互聯網大數據時不得不去了解的一種常用演算法

【嵌牛鼻子】：經典大數據演算法之C4.5簡單介紹

【嵌牛提問】：C4.5是一種怎麼的演算法，其決策機制靠什麼實現？

【嵌牛正文】：

決策樹模型：

決策樹是一種通過對特徵屬性的分類對樣本進行分類的樹形結構，包括有向邊與三類節點：

根節點（root node），表示第一個特徵屬性，只有出邊沒有入邊；

內部節點（internal node），表示特徵屬性，有一條入邊至少兩條出邊

葉子節點（leaf node），表示類別，只有一條入邊沒有出邊。

上圖給出了（二叉）決策樹的示例。決策樹具有以下特點：

對於二叉決策樹而言，可以看作是if-then規則集合，由決策樹的根節點到葉子節點對應於一條分類規則;

分類規則是 互斥並且完備 的，所謂 互斥 即每一條樣本記錄不會同時匹配上兩條分類規則，所謂 完備 即每條樣本記錄都在決策樹中都能匹配上一條規則。

分類的本質是對特徵空間的劃分，如下圖所示，

決策樹學習：

決策樹學習的本質是從訓練數據集中歸納出一組分類規則[2]。但隨著分裂屬性次序的不同，所得到的決策樹也會不同。如何得到一棵決策樹既對訓練數據有較好的擬合，又對未知數據有很好的預測呢？

首先，我們要解決兩個問題：

如何選擇較優的特徵屬性進行分裂？每一次特徵屬性的分裂，相當於對訓練數據集進行再劃分，對應於一次決策樹的生長。ID3演算法定義了目標函數來進行特徵選擇。

什麼時候應該停止分裂？有兩種自然情況應該停止分裂，一是該節點對應的所有樣本記錄均屬於同一類別，二是該節點對應的所有樣本的特徵屬性值均相等。但除此之外，是不是還應該其他情況停止分裂呢？

2. 決策樹演算法

特徵選擇

特徵選擇指選擇最大化所定義目標函數的特徵。下面給出如下三種特徵（Gender, Car Type, Customer ID）分裂的例子：

圖中有兩類類別（C0, C1），C0: 6是對C0類別的計數。直觀上，應選擇Car Type特徵進行分裂，因為其類別的分布概率具有更大的傾斜程度，類別不確定程度更小。

為了衡量類別分布概率的傾斜程度，定義決策樹節點tt的不純度（impurity），其滿足：不純度越小，則類別的分布概率越傾斜；下面給出不純度的的三種度量：

其中，p(ck|t)p(ck|t)表示對於決策樹節點tt類別ckck的概率。這三種不純度的度量是等價的，在等概率分布是達到最大值。

為了判斷分裂前後節點不純度的變化情況，目標函數定義為信息增益（information gain）：

I(⋅)I(⋅)對應於決策樹節點的不純度，parentparent表示分裂前的父節點，NN表示父節點所包含的樣本記錄數，aiai表示父節點分裂後的某子節點，N(ai)N(ai)為其計數，nn為分裂後的子節點數。

特別地，ID3演算法選取 熵值 作為不純度I(⋅)I(⋅)的度量，則

cc指父節點對應所有樣本記錄的類別；AA表示選擇的特徵屬性，即aiai的集合。那麼，決策樹學習中的信息增益ΔΔ等價於訓練數據集中 類與特徵的互信息 ，表示由於得知特徵AA的信息訓練數據集cc不確定性減少的程度。

在特徵分裂後，有些子節點的記錄數可能偏少，以至於影響分類結果。為了解決這個問題，CART演算法提出了只進行特徵的二元分裂，即決策樹是一棵二叉樹；C4.5演算法改進分裂目標函數，用信息增益比（information gain ratio）來選擇特徵：

因而，特徵選擇的過程等同於計算每個特徵的信息增益，選擇最大信息增益的特徵進行分裂。此即回答前面所提出的第一個問題（選擇較優特徵）。ID3演算法設定一閾值，當最大信息增益小於閾值時，認為沒有找到有較優分類能力的特徵，沒有往下繼續分裂的必要。根據最大表決原則，將最多計數的類別作為此葉子節點。即回答前面所提出的第二個問題（停止分裂條件）。

決策樹生成：

ID3演算法的核心是根據信息增益最大的准則，遞歸地構造決策樹；演算法流程如下：

如果節點滿足停止分裂條件（所有記錄屬同一類別 or 最大信息增益小於閾值），將其置為葉子節點；

選擇信息增益最大的特徵進行分裂；

重復步驟1-2，直至分類完成。

C4.5演算法流程與ID3相類似，只不過將信息增益改為 信息增益比 。

3. 決策樹剪枝

過擬合

生成的決策樹對訓練數據會有很好的分類效果，卻可能對未知數據的預測不準確，即決策樹模型發生過擬合（overfitting）——訓練誤差（training error）很小、泛化誤差（generalization error，亦可看作為test error）較大。下圖給出訓練誤差、測試誤差（test error）隨決策樹節點數的變化情況：

可以觀察到，當節點數較小時，訓練誤差與測試誤差均較大，即發生了欠擬合（underfitting）。當節點數較大時，訓練誤差較小，測試誤差卻很大，即發生了過擬合。只有當節點數適中是，訓練誤差居中，測試誤差較小；對訓練數據有較好的擬合，同時對未知數據有很好的分類准確率。

發生過擬合的根本原因是分類模型過於復雜，可能的原因如下：

訓練數據集中有噪音樣本點，對訓練數據擬合的同時也對噪音進行擬合，從而影響了分類的效果；

決策樹的葉子節點中缺乏有分類價值的樣本記錄，也就是說此葉子節點應被剪掉。

剪枝策略

為了解決過擬合，C4.5通過剪枝以減少模型的復雜度。[2]中提出一種簡單剪枝策略，通過極小化決策樹的整體損失函數（loss function）或代價函數（cost function）來實現，決策樹TT的損失函數為：

其中，C(T)C(T)表示決策樹的訓練誤差，αα為調節參數，|T||T|為模型的復雜度。當模型越復雜時，訓練的誤差就越小。上述定義的損失正好做了兩者之間的權衡。

如果剪枝後損失函數減少了，即說明這是有效剪枝。具體剪枝演算法可以由動態規劃等來實現。

4. 參考資料

[1] Pang-Ning Tan, Michael Steinbach, Vipin Kumar, Introction to Data Mining .

[2] 李航，《統計學習方法》.

[3] Naren Ramakrishnan, The Top Ten Algorithms in Data Mining.

㈨ 決策樹演算法總結

目錄

一、決策樹演算法思想

二、決策樹學習本質

三、總結

一、決策樹（decision tree）演算法思想：

決策樹是一種基本的分類與回歸方法。本文主要討論分類決策樹。決策樹模型呈樹形結構，在分類問題中，表示基於特徵對實例進行分類的過程。 它可以看做是if-then的條件集合，也可以認為是定義在特徵空間與類空間上的條件概率分布 。決策樹由結點和有向邊組成。結點有兩種類型：內部結點和葉結點，內部結點表示一個特徵或屬性，葉結點表示一個類。（橢圓表示內部結點，方塊表示葉結點）

         決策樹與if-then規則的關系

決策樹可以看做是多個if-then規則的集合。將決策樹轉換成if-then規則的過程是：由決策樹的根結點到葉結點的每一條路徑構建一條規則；路徑上的內部結點的特徵對應著規則的條件，而葉結點的類對應著規則的結論。決策樹的路徑或其對應的if-then規則集合具有一個重要的性質：互斥且完備。這就是說，每一個實例都被一條路徑或一條規則所覆蓋，且只被一條路徑或一條規則所覆蓋。這里的覆蓋是指實例的特徵與路徑上的特徵一致或實例滿足規則的條件。

         決策樹與條件概率分布的關系

決策樹還表示給定特徵條件下類的條件概率分布。這一條件概率分布定義在特徵空間的一個劃分上。將特徵空間劃分為互不相交的單元或區域，並在每個單元定義一個類的概率分布，就構成一個條件概率分布。決策樹的一條路徑對應於劃分中的一個單元。決策樹所表示的條件概率分布由各個單元給定條件下類的條件概率分布組成。

         決策樹模型的優點

決策樹模型具有可讀性，分類速度快。學習時，利用訓練數據，根據損失函數最小化原則建立決策樹模型；預測時，對新的數據，利用決策樹模型進行分類 。

二、決策樹學習本質：

決策樹學習是從訓練數據集中歸納一組分類規則、與訓練數據集不相矛盾的決策樹可能有多個，也可能一個沒有。我們需要訓練一個與訓練數據矛盾較小的決策樹，同時具有很好的泛化能力。從另一個角度看 決策樹學習是訓練數據集估計條件概率模型 。基於特徵空間劃分的類的條件概率模型有無窮多個。我們選擇的條件概率模型應該是不僅對訓練數據有很好的擬合，而且對未知數據有很好的預測。 決策樹的學習使用損失函數表示這一目標，通常的損失函數是正則化的極大似然函數。決策樹的學習策略是以損失函數為目標函數的最小化。當損失函數確定後，決策樹學習問題變為損失函數意義下選擇最優決策樹的問題。這一過程通常是一個遞歸選擇最優特徵，並根據特徵對訓練數據進行分割，使得對各個子數據集有一個最好分類的過程。這一過程對應著特徵選擇、決策樹的生成、決策樹的剪枝。

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

         決策樹的生成 ： 根據不同特徵作為根結點，劃分不同子結點構成不同的決策樹。

         決策樹的選擇 ：哪種特徵作為根結點的決策樹信息增益值最大，作為最終的決策樹（最佳分類特徵）。

         信息熵 ： 在資訊理論與概率統計中，熵是表示隨機變數不確定性的度量。設X是一個取有限個值的離散隨機變數，其概率分布為P(X= ) = ，i=1，2，3...n，則隨機變數X的熵定義為

        H(X) =  —  ，0 <=  H(X) <= 1，熵越大，隨機變數的不確定性就越大。

        條件熵（Y|X） ： 表示在已知隨機變數X的條件下隨機變數Y的不確定性。

         信息增益  ： 表示得知特徵X的信息而使得類Y的信息的不確定性減少的程度。

        信息增益  = 信息熵(父結點熵 ) — 條件熵（子結點加權熵）

三、 總結 ：

        優點

        1、可解釋性高，能處理非線性的數據，不需要做數據歸一化，對數據分布沒有偏好。

        2、可用於特徵工程，特徵選擇。

        3、可轉化為規則引擎。

        缺點

        1、啟發式生成，不是最優解。

        2、容易過擬合。

        3、微小的數據改變會改變整個數的形狀。

        4、對類別不平衡的數據不友好。

㈩ 決策樹（Decision Tree）

通俗來說，決策樹分類的思想類似於找對象。現想像一個女孩的母親要給這個女孩介紹男朋友，於是有了下面的對話：

      女兒：多大年紀了？

      母親：26。

      女兒：長的帥不帥？

      母親：挺帥的。

      女兒：收入高不？

      母親：不算很高，中等情況。

      女兒：是公務員不？

      母親：是，在稅務局上班呢。

      女兒：那好，我去見見。

      這個女孩的決策過程就是典型的分類樹決策。相當於通過年齡、長相、收入和是否公務員對將男人分為兩個類別：見和不見。假設這個女孩對男人的要求是：30歲以下、長相中等以上並且是高收入者或中等以上收入的公務員，圖1表示了女孩的決策邏輯。

如果你作為一個女生，你會優先考慮哪個條件：長相？收入？還是年齡。在考慮年齡條件時使用25歲為劃分點，還是35歲為劃分點。有這么多條件，用哪個條件特徵先做if，哪個條件特徵後做if比較優呢？還有怎麼確定用特徵中的哪個數值作為劃分的標准。這就是決策樹機器學習演算法的關鍵了。

首先，我們需要熟悉資訊理論中熵的概念。熵度量了事物的不確定性，越不確定的事物，它的熵就越大。具體的，隨機變數X的熵的表達式如下：

如拋一枚硬幣為事件 ， ， ，

擲一枚骰子為事件 ， ，

，顯然擲骰子的不確定性比投硬幣的不確定性要高。 

熟悉了單一變數的熵，很容易推廣到多個個變數的聯合熵，這里給出兩個變數X和Y的聯合熵表達式：

有了聯合熵，又可以得到條件熵的表達式H(X|Y)，條件熵類似於條件概率,它度量了我們在知道Y以後X剩下的不確定性。表達式：

我們剛才提到 度量了 的不確定性，條件熵 度量了我們在知道 以後 剩下的不確定性，那麼 呢？它度量了 在知道 以後不確定性減少程度，這個度量我們在資訊理論中稱為互信息，記為 。

信息熵 ，聯合熵 ，條件熵 ，互信息 之間的關系由圖2所示：

在決策樹的ID3演算法中，互信息 被稱為信息增益。ID3演算法就是用信息增益來判斷當前節點應該用什麼特徵來構建決策樹。信息增益大，則越適合用來分類。

下面我們用SNS社區中不真實賬號檢測的例子說明如何使用ID3演算法構造決策樹。為了簡單起見，我們假設訓練集合包含10個元素：

設L、F、H和D表示日誌密度、好友密度、是否使用真實頭像和賬號是否真實，下面計算各屬性的信息增益：

 因此日誌密度的信息增益是0.276。用同樣方法得到H和F的信息增益分別為0.033和0.553。因為F具有最大的信息增益，所以第一次分裂選擇F為分裂屬性，分裂後的結果圖3表示：

在上圖的基礎上，再遞歸使用這個方法計運算元節點的分裂屬性，最終就可以得到整個決策樹。

但是ID3演算法中還存在著一些不足之處：

1.ID3沒有考慮連續特徵，比如長度，密度都是連續值，無法在ID3運用。這大大限制了ID3的用途。

2.ID3採用信息增益大的特徵優先建立決策樹的節點。很快就被人發現，在相同條件下，取值比較多的特徵比取值少的特徵信息增益大。比如一個變數有2個值，各為 ，另一個變數為3個值，各為 ，其實他們都是完全不確定的變數，但是取3個值的比取2個值的信息增益大。（信息增益反映的給定一個條件以後不確定性減少的程度,必然是分得越細的數據集確定性更高,也就是條件熵越小,信息增益越大）如河校正這個問題呢？為了解決這些問題我們有了C4.5演算法。

對於第一個問題，不能處理連續特徵， C4.5的思路是將連續的特徵離散化。比如m個樣本的連續特徵A有m個，從小到大排列為 。則C4.5取相鄰兩樣本值的平均數，一共取得m-1個劃分點，其中第i個劃分點 表示為： 。對於這m-1個點，分別計算以該點作為二元分類點時的信息增益。選擇信息增益最大的點作為該連續特徵的二元離散分類點。比如取到的增益最大的點為 ，取大於 為類別1，小於 為類別2。這樣我們就做到了連續特徵的離散化。

對於第二個問題，信息增益作為標准容易偏向於取值較多的特徵。C4.5中提出了信息增益比：

即特徵 的對數據集 的信息增益與特徵 信息熵的比，信息增益比越大的特徵和劃分點，分類效果越好。某特徵中值得種類越多，特徵對應的特徵熵越大，它作為分母，可以校正信息增益導致的問題。

回到上面的例子：

 

同樣可得：  ， 。

因為F具有最大的信息增益比，所以第一次分裂選擇F為分裂屬性，分裂後的結果圖3表示。

再遞歸使用這個方法計運算元節點的分裂屬性，最終就可以得到整個決策樹。

看完上述材料，我們知道在ID3演算法中我們使用了信息增益來選擇特徵，信息增益大的優先選擇。在C4.5演算法中，採用了信息增益比來選擇特徵，以減少信息增益容易選擇特徵值種類多的特徵的問題。但是無論是ID3還是C4.5,都是基於資訊理論的熵模型的，這裡面會涉及大量的對數運算。能不能簡化模型同時也不至於完全丟失熵模型的優點呢？有！CART分類樹演算法使用基尼系數來代替信息增益比，基尼系數代表了模型的不純度，基尼系數越小，則不純度越低，特徵越好。這和信息增益(比)是相反的。

在分類問題中，假設有 個類別，第 個類別的概率為 ,則基尼系數為：

對於給定的樣本 ，假設有 個類別，第 個類別的數量為 ，則樣本的基尼系數為:

特別的，對於樣本D,如果根據特徵A的某個值a,把D分成D1和D2兩部分，則在特徵A的條件下，D的基尼系數為：

回到上面的例子：

同理得： ， 。

因為L具有最小的基尼系數，所以第一次分裂選擇L為分裂屬性。

再遞歸使用這個方法計運算元節點的分裂屬性，最終就可以得到整個決策樹。

小夥伴們如果覺得文章還行的請點個贊呦！！同時覺得文章哪裡有問題的可以評論一下  謝謝你！