A. Python中的樹你知道嗎
樹與二叉樹
在了解二叉樹之前，我們要先了解樹的一些概念，方便我們對二叉樹的理解。
什麼是樹？
樹(英語:tree)是一種抽象數據類型(ADT)或是實作這種抽象數據類型的數據結構,用來模擬具有樹狀結構性質的數據集合。
它是由n(n>=1)個有限節點組成一個具有層次關系的集合。把它叫做「樹」是因為它看起來像一棵倒掛的樹,也就是說它是根朝上,而葉朝下的。它具有以下的特點:
每個節點有零個或多個子節點;
沒有父節點的節點稱為根節點;
每一個非根節點有且只有一個父節點;
除了根節點外,每個子節點可以分為多個不相交的子樹;
樹的術語：
節點的度: 一個節點含有的子樹的個數稱為該節點的度;
樹的度: 一棵樹中,最大的節點的度稱為樹的度;
根結點： 樹的最頂端的節點，繼續往下分為子節點
父節點： 子節點的上一層為父節點
兄弟節點： 具有同一個父節點的節點稱為兄弟節點
葉子節點/終端節點： 不再有子節點的節點為葉子節點
二叉樹：
二叉樹是樹的特殊一種，具有如下特點：
每個節點最多有兩個子樹，節點的度最大為2
左子樹和右子樹是有順序的，次序不能顛倒
即是某節點只有一個子樹，也要區分左右子樹
二叉樹的性質：
在非空二叉樹的第i層，最多有2i-1個節點(i>=1)
在深度為K的二叉樹上最多有2k-1個節點(k>.1)
對於任意一個非空的二叉樹，如果葉子節點個數為n0，度數為2的節點數為n2，則有n0=n2+1
推倒過程：在一棵二叉樹中，除了葉子節點（度為0）外，就剩下度為2(n2)和度為1(n1)的節點了。則樹的節點總數為T = n0 + n1 + n2；在二叉樹中節點總數為T，而連線總數為T-1 = 2*n2 + n1，所以就有：n0 + n1 + n2 - 1 = 2 *n2 + n1，得到n0=n2+1。
特殊的二叉樹
滿二叉樹
在二叉樹中除了葉子節點，其他所有節點的度為2，且所有的葉子節點都在同一層上，這樣的二叉樹成為滿二叉樹。
滿二叉樹的特點：
葉子節點只能出現在最下一層
非葉子節點度數一定為2
在同樣深度的二叉樹中，滿二叉樹的節點個數最多，葉子節點數最多
完全二叉樹
如果二叉樹中除去最後一層葉子節點後為滿二叉樹，且最後一層的葉子節點依次從左到右分布，則這樣的二叉樹稱為完全二叉樹
完全二叉樹的特點：
葉子節點一般出現在最下一層，如果倒數第二層出現葉子節點，一定出現在右部連續位置
最下層葉子節點一定集中在左部連續位置
同樣節點的二叉樹，完全二叉樹的深度最小（滿二叉樹也對）
小例題：
某完全二叉樹共有200個節點，該二叉樹中共有（）個葉子節點？
解：n0 + n1 + n2 = 200， 其中n0 = n2 + 1，n1 = 0或者1 （n1=1，出現在最下一層節點數為奇數，最下一層節點數為偶數，則n1=0）， 因為n0為整數，所以最後算得n0 = 100。
完全二叉樹的性質：
具有n個節點的完全二叉樹的深度為log2n+1。log2n結果取整數部分。
如果有一棵有n個節點的完全二叉樹的節點按層次序編號，對任一層的節點i(1 <= i <= n)
1. 如果i=1，則節點是二叉樹的根，無父節點，如果i>1,則其父節點為i/2，向下取整
2. 如果2*1>n，那麼節點i沒有左孩子，否則其左孩子為2i
3. 如果2i+1>n那麼節點沒有右孩子，否則右孩子為2i+1
驗證：
第一條：
當i=1時，為根節點。當i>1時，比如結點為7，他的雙親就是7/2= 3；結點9雙親為4.
第二條：
結點6,62 = 12>10，所以結點6無左孩子，是葉子結點。結點5，52 = 10，左孩子是10,結點4，為8.
第三條：
結點5，2*5+1>10,沒有右孩子，結點4，則有右孩子。
更多Python相關知識，請移步Python視頻教程繼續學習！！
B. 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