Pythonで0からディシジョンツリーを作って理解する　（1. 概要編）

import math
import pandas as pd
from functools import reduce

# データセット
d = {
  "天気":["晴","晴","曇","雨","雨","雨","曇","晴","晴","雨","晴","曇","曇","雨"],
  "温度":["暑","暑","暑","暖","涼","涼","涼","暖","涼","暖","暖","暖","暑","暖"],
  "湿度":["高","高","高","高","普通","普通","普通","高","普通","普通","普通","高","普通","高"],
  "風":["無","有","無","無","無","有","有","無","無","無","有","有","無","有"],
  # 最後の列が、目的変数、正解データともよばれる、他の列から導き出したいデータとなる。
  "ゴルフ":["×","×","○","○","○","×","○","×","○","○","○","○","○","×"],
}
dft = pd.DataFrame(d)

# 値の配分を求めるラムダ式、引数はpandas.Series、戻り値は各値の個数が入った配列
# 入力sからvalue_counts()で各値の度数を取得し、辞書型のデータのループ items()を呼び出す。
# sortedは、実行毎に出力結果が変化しないように、度数の小さい順に並べ替えている。
# そして、要素がキー(k)と値(v)の文字列となった配列を生成する。
cstr = lambda s:[k+":"+str(v) for k,v in sorted(s.value_counts().items())]

# ディシジョンツリーのデータ構造
tree = {
  # name: このノード(幹)の名前
  "name":"decision tree "+dft.columns[-1]+" "+str(cstr(dft.iloc[:,-1])),
  # df: このノードに関連付けられるデータ
  "df":dft,
  # edges: このノードから出ているエッジ(枝)一覧、下にエッジの無い葉ノードの場合は空配列となる。
  "edges":[],
}


# ツリーの生成は、枝が伸びる可能性のある幹についてこのopenに保存しておく。
open = [tree]

# エントロピーを計算するラムダ式、引数はpandas.Series、戻り値はエントロピーの数値
entropy = lambda s:-reduce(lambda x,y:x+y,map(lambda x:(x/len(s))*math.log2(x/len(s)),s.value_counts()))

# openが空になるまで繰り返す。
while(len(open)!=0):
  # openの先頭を取り出し、そのノードが保持しているデータを取り出しておく。
  n = open.pop(0)
  df_n = n["df"]

  # このノードのエントロピーが0の場合、これ以上エッジを展開できないので、
  # このノードからの枝分かれはしない。
  if 0==entropy(df_n.iloc[:,-1]):
    continue
  # 分岐可能性の属性値一覧を保存する変数を作成しておく。
  attrs = {}
  # クラス属性の最後の列以外の属性をすべて調査する。
  for attr in df_n.columns[:-1]:
    # この属性で分岐する場合のエントロピーと、
    # 分岐後のデータと分岐する属性値を保存する変数を作成する。
    attrs[attr] = {"entropy":0,"dfs":[],"values":[]}
    # この属性の取りうる値をすべて調査する。またsortedは、属性値の重複除去された配列を、
    # 実行のたびに順番が入れ替わらないようにするためである。
    for value in sorted(set(df_n[attr])):
      # 属性値でデータをフィルタリングする。
      df_m = df_n[df_n.loc[:,attr]==value]
      # エントロピーを計算し、関連するデータ、値をそれぞれ保存しておく。
      attrs[attr]["entropy"] += entropy(df_m.iloc[:,-1])*df_m.shape[0]/df_n.shape[0]
      attrs[attr]["dfs"] += [df_m]
      attrs[attr]["values"] += [value]
      pass
    pass
  # クラス値を分離可能な属性が1つも無い場合は、このノードの調査を終了する。
  if len(attrs)==0:
    continue
  # エントロピーが最小になる属性を取得する。
  attr = min(attrs,key=lambda x:attrs[x]["entropy"])
  # 分岐する属性のそれぞれの値、分岐後のデータを、ツリーとopenにそれぞれ追加する。
  for d,v in zip(attrs[attr]["dfs"],attrs[attr]["values"]):
    m = {"name":attr+"="+str(v),"edges":[],"df":d.drop(columns=attr)}
    n["edges"].append(m)
    open.append(m)
  pass

# データセットを出力する。
print(dft,"\n-------------")
# ツリーを文字に変換するメソッド、引数は tree:ツリーのデータ構造、indent:子ノードにつくインデント、
# 戻り値は、treeの文字表現。このメソッドは、再帰的に呼ばれて、ツリーのすべてを文字に変換する。
def tstr(tree,indent=""):
  # このノードの文字表現を作成する。このノードが葉ノードの場合(edges配列の要素数が0)には、
  # treeに関連付けられたデータdfの最後の列の度数分布を文字化する。
  s = indent+tree["name"]+str(cstr(tree["df"].iloc[:,-1]) if len(tree["edges"])==0 else "")+"\n"
  # このノードからのエッジについて、すべてループする。
  for e in tree["edges"]:
    # 子ノードの文字表現を、このノードの文字表現に付け加える。
    # indentには、このノードのindentに、さらに文字を加える。
    s += tstr(e,indent+"  ")
    pass
  return s
# ツリーを文字表現して、出力する。
print(tstr(tree))

decision tree ゴルフ ['×:5', '○:9']
  天気=晴
    湿度=普通['○:2']
    湿度=高['×:3']
  天気=曇['○:4']
  天気=雨
    風=有['×:2']
    風=無['○:3']

d = {
    "天気":["晴","晴","曇","雨","雨","雨","曇","晴","晴","雨","晴","曇","曇","雨"],
    "温度":["暑","暑","暑","暖","涼","涼","涼","暖","涼","暖","暖","暖","暑","暖"],
    "湿度":["高","高","高","高","普通","普通","普通","高","普通","普通","普通","高","普通","高"],
    "ゴルフ":["×","×","○","○","○","×","○","×","○","○","○","○","○","×"],
    # 最後の列が、目的変数、正解データともよばれる、他の列から導き出したいデータとなる。
    "風":["無","有","無","無","無","有","有","無","無","無","有","有","無","有"],
}

decision tree 風 ['有:6', '無:8']
  ゴルフ=×
    天気=晴
      温度=暑
        湿度=高['有:1', '無:1']
      温度=暖['無:1']
    天気=雨['有:2']
  ゴルフ=○
    天気=晴
      温度=暖['有:1']
      温度=涼['無:1']
    天気=曇
      温度=暑['無:2']
      温度=暖['有:1']
      温度=涼['有:1']
    天気=雨['無:3']