#Lesson4の概要
決定木は今回のコースの教師あり学習アルゴリズムの最後。決定木はロバスト性に優れており、結果を説明できる点が特徴。こちらも、SVMと同じように、線形で決定境界を引くが、kernelトリックによって、非線形分類もできる。
決定木は複数の線形分離をひとつづく行うことができる。

ちなみに、分類だけではなく回帰にも使えるらしい。
決定木を発展させたアルゴリズムとして、バギング、ブースティング、ランダムフォレスト等がある。

#決定木アルゴリズム実装の仕方
ドキュメンテーション:1.10. Decision Trees¶を参照。
実装の流れはLesson3:SVM、Lesson2:Naive Bayesとほとんど一緒。

###公式ドキュメントから転載
from sklearn import tree #まずはインポート
X = [[0, 0], [1, 1]]#特徴量
Y = [0, 1]#教師データ:ラベル
clf = tree.DecisionTreeClassifier()#classifier生成
clf = clf.fit(X, Y)#学習
clf.predict([[2., 2.]])#新データに対してラベルを推定

出力
array([1])

ちなみに

clf.predict_proba([[2., 2.]])

出力
array([[0., 1.]])
.predict_proba()メソッドを使うと、新データから、各クラスに割り当てられる確率を出せる。
出力の左側はクラス「0」に割り当てられる確率、右側がクラス「1」に割り当てられる確率。
決定木の場合は確率は1になる。

下記参照させていただきました。
Python: 機械学習で分類問題のモデルを評価する指標について
 あやめの識別を行ってみる(決定木)

ちなみに.score(X, y)メソッドで精度が出せる。Xはテストデータ、yはその正解ラベル。

#パラメーターチューニング
###min_samples_split
分かれたそれぞれのノードの中にいくつのサンプルデータが入るかを定義するパラメーター。どこまで細かく分けるかという設定。デフォルトは2。
数が小さいほど、細かくなるが複雑になる。

#エントロピー(不純度を表す一つの指標)
取る値は0～1。分類対象がすべて同じ種類なら0。半分半分なら1。
ほかに、sklearnの決定木ではジニ係数が選択できる。

Entropy = -\sum_{i} (p_i)\log{_2} (p_i)

※シグママークはすべてのクラスのエントロピーの足し合わせの意味。
※P_iは各クラスのエントロピー(下でいうP_slow, P_fast)

[slow, slow, fast, fast]のノード(親)のエントロピーは

Entropy = -(p_{slow})\log{_2} (p_{slow})-(p_{fast})\log{_2} (p_{fast})

P_slowはslowの割合。なのでここではslowが2つ、全体がslow, slow, fast, fast で4つのため、2/4で0.5。P_fastも同じで0.5。このノードのエントロピーは

Entropy = -(0.5)\log{_2} (0.5)-(0.5)\log{_2} (0.5) = 1

#Information Gain
決定木アルゴリズムはInformation Gainを最大化しながら、どの特徴で分割を行うかを決める。網羅的にエントロピーを計算して、Information Gainを計算する。確か初期設定はエントロピーと同じような指標のgini係数だが。ビデオで例題が出されているが、下記のように網羅的に計算して、Info Gainが最も高い特徴量で分ける。

#bias-variance dilemma
◆high-bias
データを無視し、学習能力はほぼ皆無。

◆high-variance
汎化能力が低く、学習したことしかできない。

上記はトレードオフの関係。中間が一番良い。

#その他注意点
決定木は過学習しやすい。特に特徴量が多い場合。それを防ぐために適切なところで、木の成長をやめさせたりするようなパラメーターチューニングが必要。そのほか、アンサンブル学習(決定木を複数使った学習)等も用いられる。

#Mini-project
今まで、Lesson2:Naive Bayes、Lesson3: SVM まとめやってきたメールの分類を、今度は決定木で行う。

###video37
decision_tree/dt_author_id.pyを使ってメールを分類したら、精度はどうか？(min_samples_splitは40)学習、推定の時間は？


#########################################################
### your code goes here ###
from sklearn import tree
from sklearn.metrics import accuracy_score
import numpy as np

clf = tree.DecisionTreeClassifier(min_samples_split=40)

t0 = time()
clf = clf.fit(features_train, labels_train)
print "training time:", round(time()-t0,3),"s"

t1 = time()
pred = clf.predict(features_test)
print "predicting time:", round(time()-t1,3),"s"

accuracy = accuracy_score(labels_test, pred)

print(accuracy)

<結果>
no. of Chris training emails: 7936
no. of Sara training emails: 7884
raining time: 542.351 s
predicting time: 0.089 s
0.9772468714448237

SVMに比べて大分時間がかかっている。

###video38
パラメーターチューニングで、アルゴリズムの学習・推定の時間を劇的に向上させられる(Lesson3参照)が、実はアルゴリズムに入力する、トレーニングデータ/テストデータの量を減らしても時間は早くなる。詳しくはLesson12: Feature Selection まとめで解説してくれるようだ。一般に決定木はSVMよりも複雑のようで、時間が上記のようにかかるらしい。
ちなみにトレーニングデータの特徴量数(columnの数)は3785。rowはemailの数。

###video38,39
ここでは、email_preprocess.pyをいじって、トレーニングデータ数を1/10にして、決定木を単純化している。

###video40
再度email_preprocess.pyをいじって、トレーニングデータ数を1/100にしても、精度は0.967

あんまり変わらないのね。

これを書くのに、こちらも参考にさせていただいた。わかりやすい！
[入門]初心者の初心者による初心者のための決定木分析

#感想
入力する特徴量が多すぎると、過学習。少なすぎると、新しいデータに対応できない。新しいデータとはbag of wordsに入っていないデータ。なので、まずはSVMを試して、Naive Bayesを試すという順番が、テキストラーニングでは王道みたい。

scikit-learn アルゴリズム・チートシート

#調べた英単語
alleviate・・・adj, 軽くする、緩和する、楽にする
ex)alleviate some of the parameters.
fraction・・・n, 端数
ex)2.345 = integer part:2 + fractional part:0.345
contamination・・・n,汚染(すること、の状態)、汚濁、汚濁物