Decision Tree - ID3(Iterative Dichotomiser 3 - 1979 John Ross Quinlan)
Decision Tree - ID3(Iterative Dichotomiser 3 - 1979 John Ross Quinlan)
(注意) これは私の勉強・備忘録のために記したものであり、間違いがあるやもしれません。どうぞご容赦ください。
はじめに
決定木のアルゴリズムに ID3 というものがあります。 ID3 は Quinlan が 1979 に発表したアルゴリズムで、この改良の C4.5 や、決定木を並列に多数構築した RandomForest、Boosting に活用した Gradient Boosted Trees など、発展型の元となったものです。
私の勉強のためにも、まずは ID3 から初めて、今 Kaggle でも最も定評・人気がある XGboost までたどってみようと思います。
ID3
Wikipediaja.wikipedia.org によると
その学習方法はオッカムの剃刀の原理に基づいている。すなわち最低限の仮説による事象の決定を行う。 「この方法は各独立変数に対し変数の値を決定した場合における平均情報量の期待値を求め、その中で最大のものを選びそれを木のノードにする操作を再帰的に行うことで実装される。」
とあります。これは ID3 に限ったことではなく決定木の基本的な考え方・原理です。
決定木は「最低限の仮説による事象の決定」とあるように、うまくコントロール*1すれば最小限の条件でその事象を表現できます。
特に、ヘテロジニアスデータ*2での適切に最適化された条件は人の感覚に合うため、人と機械のよいコンビネーションで PDCA を回せるなど、ビジネスの現場でもよく使われています。
実装
#!/usr/bin/env python # -*- coding: utf-8 -*- import sys import os import math import numpy as np import scipy as sp import matplotlib.pyplot as plt import pandas as pd import seaborn as sns """ ID3(Iterative Dichotomiser 3 - 1979 John Ross Quinlan) その学習方法はオッカムの剃刀の原理に基づいている。すなわち最低限の仮説による事象の決定を行う。 「この方法は各独立変数に対し変数の値を決定した場合における平均情報量の期待値を求め、 その中で最大のものを選びそれを木のノードにする操作を再帰的に行うことで実装される。」 https://ja.wikipedia.org/wiki/ID3 制約: 離散でないといけない S: 訓練例の集合 A: 属性の集合 default: Yes / No の既定値 """ # log の底は平均情報量の最大値が 1.0, 最小値が 0.0 になるように、分類数に合わせたほうが良い # ここでは 3 とする. def entropy(y, base=2): ''' 平均情報量の算出 y=pd.Series target bird 0.4 manmal 0.4 reptile 0.2 ''' p = y.groupby(y).count() / y.shape[0] return -1 * sum(map(lambda x: x * math.log(x, base), p)) def mean_entropy(S, c, t='target'): ent = [] for k, v in S.groupby(c).groups.items(): # weighted average y = S.ix[v, t] ent.append(entropy(y, base=3) * y.shape[0] / S.shape[0]) return np.sum(ent) """ S : Tree """ class Node(object): def __init__(self, data, parent=None, col=None, feature=None, gain=0.): self.data = data self.parent = parent self.col = col self.feat = feature # 子の分割基準 self.gain = gain self.childs = [] def entropy(self, base=2): return entropy(self.data['target'], base=base) def shape(self): return self.data.shape def add_child(self, c): self.childs.append(c) def __repr__(self): return '%s(%s)\tH:%.3f Gain:%.3f' % (self.col, self.feat, self.entropy(), self.gain) def ID3(S, A, t='target'): if S.data.shape[0] <= 0: # S が空集合 return None elif len(A) <= 0: # Aが空集合 return S elif S.entropy(base=3) <= 0.: return S else: # 1. 各説明変数で平均情報量を算出する <- このロジック mean_entropy の差し替えで C4.5 とかにできる Ms = map(lambda a: (a, mean_entropy(S.data, a)), A) # 2. 情報ゲインが最大な説明変数を選ぶ col, gain = max(map(lambda x: (x[0], S.entropy(3)-x[1]), Ms), key=lambda x:x[1]) # 3. 木を分割する #_A = list(set(A) - set([col])) for f, x in S.data.groupby(col).groups.items(): S.add_child(ID3(Node(S.data.ix[x], parent=S, col=col, feature=f, gain=gain), A)) return S def pretty_print_node(n, depth=0): if n is None: return pref = '\t' print(pref*depth, n) for _n in n.childs: pretty_print_node(_n, depth+1) if __name__ == '__main__': ''' 例題 食性（a1 ） 発生形態（a2 ） 体温（a3 ） 分類 例題1（ペンギン） 肉食 卵生 恒温 鳥類 例題2（ライオン） 肉食 胎生 恒温 哺乳類 例題3（ウシ） 草食 胎生 恒温 哺乳類 例題4（トカゲ） 肉食 卵生 変温 爬虫類 例題5（ブンチョウ） 草食 卵生 恒温 鳥類 ''' df = pd.DataFrame( [[ 'carnivorous', 'oviparity', 'homothermal', 'bird'], [ 'carnivorous', 'viviparity', 'homothermal', 'manmal'], [ 'herbivorous', 'viviparity', 'homothermal', 'manmal'], [ 'carnivorous', 'oviparity', 'cold_blooded', 'reptile'], [ 'herbivorous', 'oviparity', 'homothermal', 'bird']], columns = ['a1', 'a2', 'a3', 'target'], index = ['penguin', 'lion', 'caw', 'lizard','finch'] ) S = df A = ['a1', 'a2', 'a3'] # 属性集合 X = df[['a1', 'a2', 'a3']] y = df.target Tree = ID3(Node(df, col='top'), A) pretty_print_node(Tree)
実行結果は
:decision_tree $ python id3.py
top(None) H:1.522 Gain:0.000
a2(oviparity) H:0.918 Gain:0.613
a3(cold_blooded) H:-0.000 Gain:0.579
a3(homothermal) H:-0.000 Gain:0.579
a2(viviparity) H:-0.000 Gain:0.613
