決定木

KNN概要

From Wiki
決定木は予測モデルであり、ある事項に対する観察結果から、その事項の目標値に関する結論を導く。内部の節点は変数に対応し、子である節点への枝はその変数の取り得る値を示す。葉（端点）は、根(root)からの経路によって表される変数値に対して、目的変数の予測値を表す。
決定木の学習は、元となる集合を属性値テストに基づいて部分集合に分割することによって行える[2]。この処理は、すべての部分集合に対して再帰的に繰り返される。繰返しは、分割が実行不可能となった場合、または部分集合の個々の要素が一つずつの分類となってしまう段階で終了する。

从根节点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分配到叶结点的类中。

アルゴリズム

C4.5

情報利得 (Information Gain)

情報利得は簡単に言うと、子ノードが親ノードと比べてどれくらい綺麗にデータを分類できたかを示す値です。もしくは、各ノードで標準偏差がどのくらい減るかを表した値です。どれくらいこの情報利得を計算するのに、不純度と呼ばれる値が使われます。不純度にはいくつか種類がありますが、今回は最も代表的なGiniとEntropyを紹介します。

Gini

Gini は次の式で表されます。

$G = 1 - \sum_{n = 1}^{classes}P(i|t)^2$ 各ノードで、データがあるクラスに分類される確率が高いほどGiniは0に近ずくことがわかります。仮にクラスが１つしかない場合、Giniは0となります。逆に、全てのサンプルが異なるクラスに属す時、Giniは1に近似します。更に、各ノードでGiniからInformation Gain (IG)を計算します。

$IG = G(parent) - \sum_{children}\frac{N_j}{N}G(child_j)$ ここでは、親枝のGiniと子枝のGiniの加重平均(各クラスに含まれるデータの数の割合)の差を情報利得として取得します。

Entropy

Entropyは次の式で表されます。

$E = - \sum_{i = 1}^{N}P(i|t)*log(P(i|t))$ ここで、P(i|t)が0.5に近いほど(1か0か分からない；分類できない)ほどエントロピーは高くなることがわかります。反対にP(i|t)が0か1の時、エントロピーは０となります。

$IG = E(parent) - \sum_{children}\frac{N_j}{N}E(child_j)$ 先程と同様、親枝の交差Entropyと子枝の交差Entropyの加重平均の差を情報利得として取得します。

この情報利得が大きい分割方法が各ノードで選択されます。

Gini と Entropy の使い分け

Gigiは回帰問題に向いており、Entropyは分類問題に向いています。

信息熵 & 信息增益

熵（entropy）：
熵指的是体系的混乱的程度

信息论（information theory）中的熵（香农熵）：
是一种信息的度量方式，表示信息的混乱程度，
信息越有序，信息熵越低。 例如：火柴有序放在火柴盒里，熵值很低，相反，熵值很高。

信息增益（information gain）： 在划分数据集前后信息发生的变化称为信息增益。

###Scikit-learn 決定木

from sklearn.tree import DecisionTreeClassifier

clf = DecisionTreeClassifier(criterion="entropy", max_depth=3)
clf = clf.fit(X_train,y_train)
y_pred = clf.predict(X_test)

decision tree