Lesson4: Decision Tree まとめ Intro to Machine learning@Udacity

#Lesson4の概要
決定木は今回のコースの教師あり学習アルゴリズムの最後。決定木はロバスト性に優れており、結果を説明できる点が特徴。こちらも、[SVM](https://qiita.com/Allovertom/items/788d43550071df622779)と同じように、線形で決定境界を引くが、kernelトリックによって、非線形分類もできる。
決定木は複数の線形分離をひとつづく行うことができる。
![Decision_Tree.jpg](https://qiita-image-store.s3.amazonaws.com/0/333380/258cadff-6595-09d6-c47a-8198e82c1a2c.jpeg)
ちなみに、分類だけではなく回帰にも使えるらしい。
決定木を発展させたアルゴリズムとして、バギング、ブースティング、ランダムフォレスト等がある。

#決定木アルゴリズム実装の仕方
[ドキュメンテーション:1.10. Decision Trees¶](https://scikit-learn.org/stable/modules/tree.html#tree)を参照。
実装の流れは[Lesson3:SVM](https://qiita.com/Allovertom/items/788d43550071df622779)、[Lesson2:Naive Bayes](https://qiita.com/Allovertom/items/11115145d4a3ff53d1e4)とほとんど一緒。

```python
###公式ドキュメントから転載
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])

ちなみに

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

下記参照させていただきました。
[Python: 機械学習で分類問題のモデルを評価する指標について](https://blog.amedama.jp/entry/2017/12/18/005311)
[あやめの識別を行ってみる(決定木)](https://newtechnologylifestyle.net/%E3%81%82%E3%82%84%E3%82%81%E3%81%AE%E8%AD%98%E5%88%A5%E3%82%92%E8%A1%8C%E3%81%A3%E3%81%A6%E3%81%BF%E3%82%8B%E6%B1%BA%E5%AE%9A%E6%9C%A8/)

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

#パラメーターチューニング
###min_samples_split
分かれたそれぞれのノードの中にいくつのサンプルデータが入るかを定義するパラメーター。どこまで細かく分けるかという設定。デフォルトは2。
数が小さいほど、細かくなるが複雑になる。
![decision_tree.png](https://qiita-image-store.s3.amazonaws.com/0/333380/c37b6651-592c-b0b2-141a-550259f0539c.png)

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

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

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

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

```math
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。このノードのエントロピーは

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

#Information Gain
決定木アルゴリズムはInformation Gainを最大化しながら、どの特徴で分割を行うかを決める。網羅的にエントロピーを計算して、Information Gainを計算する。確か初期設定はエントロピーと同じような指標のgini係数だが。ビデオで例題が出されているが、下記のように網羅的に計算して、Info Gainが最も高い特徴量で分ける。
![svm.jpg](https://qiita-image-store.s3.amazonaws.com/0/333380/9542b1a0-f1ff-d71e-b8a4-c390432693b6.jpeg)

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

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

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


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

#Mini-project
今まで、[Lesson2:Naive Bayes](https://qiita.com/Allovertom/items/11115145d4a3ff53d1e4)、[Lesson3: SVM まとめ](https://qiita.com/Allovertom/items/788d43550071df622779)やってきたメールの分類を、今度は決定木で行う。

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

```python

#########################################################
### 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参照](https://qiita.com/Allovertom/items/788d43550071df622779))が、実はアルゴリズムに入力する、トレーニングデータ/テストデータの量を減らしても時間は早くなる。詳しくは[Lesson12: Feature Selection まとめ](https://qiita.com/Allovertom/items/24d6d67059b3b6eb1cc5)で解説してくれるようだ。一般に決定木はSVMよりも複雑のようで、時間が上記のようにかかるらしい。
ちなみにトレーニングデータの特徴量数(columnの数)は3785。rowはemailの数。

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

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

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

これを書くのに、こちらも参考にさせていただいた。わかりやすい！
[[入門]初心者の初心者による初心者のための決定木分析](https://qiita.com/3000manJPY/items/ef7495960f472ec14377)


#感想
入力する特徴量が多すぎると、過学習。少なすぎると、新しいデータに対応できない。新しいデータとはbag of wordsに入っていないデータ。なので、まずはSVMを試して、Naive Bayesを試すという順番が、テキストラーニングでは王道みたい。
![ml_map.png](https://qiita-image-store.s3.amazonaws.com/0/333380/c173a76d-0e50-3160-4259-ed4bf61bed37.png)

[scikit-learn アルゴリズム・チートシート](https://scikit-learn.org/stable/tutorial/machine_learning_map/)


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