進化最適化アルゴリズム(1+1)-ESもどきによるkaggle Titanicアプローチ

こんにちは、kaggle初めましたFukinoです。

私はデータサイエンスの知識はからっきしなので、普通にやっても勝てない...(´・ω・`)  
というか面白みがないので、もちろん機械学習の勉強もやるけど専攻の複雑系アルゴリズムでのアプローチでも挑戦することにしました。
手始めにTitanicの生存者予想問題を(1+1)-ESという一番シンプルな進化最適化アルゴリズムで解いてみることにしました。

コードのNotebookはここに↓　
[https://www.kaggle.com/fukino010/1-1-es-solver-for-titanic/](https://www.kaggle.com/fukino010/1-1-es-solver-for-titanic/)


# 前置きというか注意

- データサイエンス的な観点からすると全くもって良いアプローチではないと思う。
- 要素がいっぱいあるので書いてたらそんなに簡単なコードでは書けないことに気がついた。(・・；)  
- 今回はとりあえずのアプローチ&シンプルにしたかったので恐ろしいほどのありとあらゆる仮定(各要素が独立。実際にはそんなわけない。)と単純化で実装。
- 真面目にやるならdeap（ライブラリ）使った方が良いです...

# 実装方法
## 問題
今回挑戦したコンペ[Titanic: Machine Learning from Disaster](https://www.kaggle.com/c/titanic)はkaggleを初めてやる初心者が最初に挑戦してみる問題です。
乗客の年齢や、性別などのデータが与えられ、それらから各乗客が生き残ったかどうかを0,1でアウトプットしたcsvを作成して提出。採点されます。
女性や子供の方が生き残ったという傾向があるらしく、性別だけで判断してもscoreが76点近くなるようです。

## データ読み込み&前処理
まず使用するトレーニングデータと、テストデータを読み込んで欠けている値なんかを埋めます。この辺はこちらのページを参考にさせていただきました。
[https://www.codexa.net/kaggle-titanic-beginner/](https://www.codexa.net/kaggle-titanic-beginner/)
ほぼ一緒なので知ってる方はこのへんは読み飛ばしてください。

まずライブラリとデータを読み込みます。

```python
import numpy as np 
import pandas as pd
import sys
import math
import random
import numpy
import copy 

import os
print(os.listdir("../input"))

pd.options.mode.chained_assignment = None # warningオフにしてて要修正 

train = pd.read_csv("../input/train.csv")
test = pd.read_csv("../input/test.csv")
```

欠けてるデータを中央値で埋めます。(この辺も本当はいろいろ考えないといけないらしい)

```python
def kesson_table(df):
    null_val = df.isnull().sum()
    percent = 100*df.isnull().sum()/len(df)
    kesson_table = pd.concat([null_val, percent], axis=1)
    kesson_table_ren_colmuns = kesson_table.rename(columns = {0:"Loss ratio", 1: "%"})
    return kesson_table_ren_colmuns

train["Age"] = train["Age"].fillna(train["Age"].median())
kesson_table(train)

train["Sex"][train["Sex"] == "male"] = 0
train["Sex"][train["Sex"] == "female"] = 1

train.head(10)

test["Age"] = test["Age"].fillna(test["Age"].median())
test["Sex"][test["Sex"] == "male"] = 0
test["Sex"][test["Sex"] == "female"] = 1
test["Fare"] = test["Fare"].fillna(test["Fare"].median())

test.head(10)
```

## 進化最適化
今回は(1+1)-ESを使います。
(1+1)-ESというのは最も簡単な進化最適化アルゴリズムの一つで、一つだけ個体を保持していて、毎回の世代で少し違う新個体を作り新個体が既存個体よりも優れていれば新個体を保持して今までのを捨てるというのを繰り返すアルゴリズムです。
こんな感じです↓
<img width="500" alt="test" src="https://qiita-image-store.s3.amazonaws.com/0/245054/fe0daa66-7794-0ccd-a65a-af6c0e2f01ad.png">

このちょっと違う個体を作るって書いてる部分で交叉をするとか組み替えとかいろいろあるんですが語り出すとキリがないので今回は単純に乱数生成にしました←

個体クラスを作成します、インスタンス変数は各要素の判断に用いるための基準値と、個体の優劣を判断するためのscoresを保持します。(変数名ミスった)

```python
class Individual:
    def __init__(self, t, s):
        self.thresholds = t
        self.scores = s   
```

トレーニングデータとテストデータを配列に入れておきます。
今回はPclassと性別、年齢、料金だけを使います。

```python
target = train["Survived"].values
features_one = train[["Pclass", "Sex", "Age", "Fare"]].values
test_features = test[["Pclass", "Sex", "Age", "Fare"]].values
```
進化最適化をします、今回の仕組みは、４種類の要素ごとに基準値を設けて、各基準値で生存の可能性を判断できたら可能性変数(possibility)に値を加算していき、possibilityが49を超えたらその乗客を生存したと判断します。
毎世代で基準値１種類を変化させ、トレーニングデータで答え合わせをしたときに、生存したかどうか合っている乗客一人につき１ポイントを加算し、ポイントの高い方を優れた個体とします。

```python
def ES():
    myIndividual = Individual([0, 25, 20, 50], 0)
    
    for features, survived in zip(features_one, target):
            possibility = 0
            survival = 0
            if features[0] == myIndividual.thresholds[0]:
                possibility += 25
            if features[1] == 0:
                possibility += myIndividual.thresholds[1]
            else:
                possibility += 25-myIndividual.thresholds[1]
                
            if features[2] < myIndividual.thresholds[2]:
                possibility += 25
            if features[3] > myIndividual.thresholds[3]:
                possibility += 25
            if possibility > 49:
                survival = 1
                
            if survival == survived:
                myIndividual.scores += 1
    
    generation = 0
    while generation < 10000:
        nextIndividual = copy.deepcopy(myIndividual)
        nextIndividual.scores = 0
        if generation%4 == 0:
            nextIndividual.thresholds[0] = random.randint(1, 3)
        elif generation%4 == 1:
            nextIndividual.thresholds[1] = random.random()*35
        elif generation%4 == 2:
            nextIndividual.thresholds[2] = random.randint(0, 100)
        else:
            nextIndividual.thresholds[3] = random.randint(0, 200)
        for features, survived in zip(features_one, target):
            possibility = 0
            survival = 0
            if features[0] == nextIndividual.thresholds[0]:
                possibility += 25
            if features[1] == 0:
                possibility += nextIndividual.thresholds[1]
            else:
                possibility += 25-nextIndividual.thresholds[1]
                
            if features[2] < nextIndividual.thresholds[2]:
                possibility += 25
            if features[3] > nextIndividual.thresholds[3]:
                possibility += 25
            
            if possibility > 49:
                survival = 1
                
            if survival == survived:
                nextIndividual.scores += 1
        if myIndividual.scores < nextIndividual.scores:
            print(myIndividual.scores)
            print(nextIndividual.scores)
            print(myIndividual.thresholds)
            print(nextIndividual.thresholds)
            myIndividual = nextIndividual
        generation+=1
    return myIndividual

myIndividual = ES()

```
実行による基準値の変化(新個体と旧個体の入れ替わりが起きた時のみ出力)

```
pre score 502
new score 512
pre thresholds [0, 25, 20, 50]
new thresholds [0, 25, 20, 158]
pre score 512
new score 551
pre thresholds [0, 25, 20, 158]
new thresholds [0, 13.869646509746763, 20, 158]
pre score 551
new score 559
pre thresholds [0, 13.869646509746763, 20, 158]
new thresholds [0, 13.869646509746763, 71, 158]
pre score 559
new score 571
pre thresholds [0, 13.869646509746763, 71, 158]
new thresholds [0, 13.869646509746763, 71, 114]
pre score 571
new score 595
pre thresholds [0, 13.869646509746763, 71, 114]
new thresholds [0, 13.869646509746763, 71, 72]
pre score 595
new score 601
pre thresholds [0, 13.869646509746763, 71, 72]
new thresholds [1, 13.869646509746763, 71, 72]
pre score 601
new score 604
pre thresholds [1, 13.869646509746763, 71, 72]
new thresholds [1, 13.869646509746763, 34, 72]
pre score 604
new score 610
pre thresholds [1, 13.869646509746763, 34, 72]
new thresholds [1, 13.869646509746763, 40, 72]
pre score 610
new score 611
pre thresholds [1, 13.869646509746763, 40, 72]
new thresholds [1, 13.869646509746763, 40, 120]
pre score 611
new score 612
pre thresholds [1, 13.869646509746763, 40, 120]
new thresholds [1, 13.869646509746763, 53, 120]
pre score 612
new score 682
pre thresholds [1, 13.869646509746763, 53, 120]
new thresholds [1, 0.17120113665188952, 53, 120]
pre score 682
new score 688
pre thresholds [1, 0.17120113665188952, 53, 120]
new thresholds [1, 0.17120113665188952, 36, 120]
pre score 688
new score 690
pre thresholds [1, 0.17120113665188952, 36, 120]
new thresholds [1, 0.17120113665188952, 44, 120]
pre score 690
new score 691
pre thresholds [1, 0.17120113665188952, 44, 120]
new thresholds [1, 0.17120113665188952, 38, 120]
pre score 691
new score 693
pre thresholds [1, 0.17120113665188952, 38, 120]
new thresholds [1, 0.17120113665188952, 37, 120]
```
### 言い訳 (飛ばしても大丈夫です)
実装がブレブレというか、ツッコミどころ満載のよろしくない部分がたくさんありまして、まず性別の基準値は、そもそも性別が男女しかないので、どちらの性別によってpossibilityにいくつ値を加算するかを最適化しています。

他の要素は例えばPclassだと３種類?なので１種類だけ固定で25ポイント加算にし、どの種類に加算するかを最適化しています。

料金は基準値を最適化してます...

まず良くないのが各要素が独立で25ポイント加算してますし、その25ポイントという値も適当に決めてます。

これ初kaggleノートだったので簡単なので試したかったんです...すいません。

本当はこんな単純加算じゃ良くないし、(1+1)-ESでもきちんと書いたらもっと上手いことできるはずです。ただ、結構複雑になるので時間かかりそうでストップしました。初kaggleなので！

## テストデータに対する答えを作成

```python
solution = np.array([], dtype="int64")
for features in test_features:
    survival = 0
    possibility = 0
    if features[0] == myIndividual.thresholds[0]:
                possibility += 25
    if features[1] == 0:
        possibility += myIndividual.thresholds[1]
    else:
        possibility += 25-myIndividual.thresholds[1]
        
    if features[2] < myIndividual.thresholds[2]:
                possibility += 25
    if features[3] > myIndividual.thresholds[3]:
                possibility += 25
    if possibility > 49:
        survival = 1
    solution = np.append(solution, int(survival))
```

## csvにアウトプット
```python
PassengerId = np.array(test["PassengerId"]).astype(int)

my_solution = pd.DataFrame(solution, PassengerId, columns = ["Survived"])

my_solution.to_csv("my_es.csv", index_label = ["PassengerId"])
```

# 結論

- submitしたら75点ぐらいでした。サンプルで用意されてる性別判断による答えが76点ぐらいなのでsolutionとしては全然良くないです。
- 細かい部分は突っ込みどころ満載ですが一応(1+1)-ESで解ける形にはなった。
- 実装が面倒なのでdeap(ライブラリ)使った方が良い。

...という感じです！実は最初にscikit-learnによる決定木も試したんですが凄いですね、fitしてpredictしただけで答えが出てくるとかどんたけ便利なんだ...
普段研究のアルゴリズムを実装するときは微調整のためにdeap使わないんですが、今回やってみてこれは使った方が早いなって気がしました。次はdeapでやってみようと思います。
ただ超シンプルな(1+1)-ESとしては参考にしていただければなと思うのでよかったら使ってやってください←
読んでくださってありがとうございました！