Pythonで0からディシジョンツリーを作って理解する　（4. データ構造編）

# 配列のpythonでの実装例
a = [2,6,4,5,1,8]

# テーブルのpythonでの実装例
a = [
    [2,6,4,5,1,8],
    [4,4,1,3,4,2],
    [5,3,6,6,5,3],
    [7,8,0,9,5,3],
]

# ツリーのpythonでの実装例 子ノード一覧を保持する。
# [値,子ノード一覧の配列]として、例えば上のツリーを、上から下、左から右に実装と次のようになる。
# この実装方法以外にも、クラスを使う、親ノードを保持する、などがある。
tree = \
[2,[
    [6,[]],
    [4,[
        [5,[
            [6,[]],
        ]],
        [8,[]],
        [1,[]],
    ]],
]]

# ツリー構造の文字化関数
def tstr(node,indent=""):
    s = indent+str(node[0])+"\n"
    for c in node[1]: # 子ノードでループ
        s += tstr(c,indent+"+-")
        pass
    return s
print(tstr(tree))
# 出力
# 2
# +-6
# +-4
# +-+-5
# +-+-+-6
# +-+-8
# +-+-1

# 一度にツリー全体を作らずに、1つずつ作る場合
# 子ノードが無い葉ノードをすべて作成する。変数名は、行（段）、左からの数を付けるとする。
n10 = [6,[]]
n21 = [8,[]]
n22 = [1,[]]
n40 = [6,[]]
# 子ノードがすべて生成されたノードから順に作成していく。
n20 = [5,[n40]]
n11 = [4,[n20,n21,n22]]
n00 = [2,[n10,n11]]

# ツリー構造の表示、指定したノードをルートノードとして表示する。
print(tstr(n11))
# 出力
# 4
# +-5
# +-+-6
# +-8
# +-1

# ネットワークのpythonでの実装例
import pandas as pd

# ノードの名称と、値が一致しているとする。
# 名称と値が一致していない場合には、名前から値を引くデータが必要になる。
nodes = [2,6,4,5,8,1]
# 行列の形式でノードの接続状況を定義する。ノード2(1行目)から、ノード6(2行目)へエッジがある場合には、
# 行列の1行2列の値が1、エッジが無い場合は0になる。この行列を、隣接行列という。
df = pd.DataFrame(
[
    # 2,6,4,5,8,1 のノードに接続があるか？
    [ 0,1,1,0,0,0], # 2のノードから
    [ 1,0,0,1,0,0], # 6のノードから
    [ 1,0,0,1,1,1], # 4のノードから
    [ 0,1,1,0,0,0], # 5のノードから
    [ 0,0,1,0,0,0], # 8のノードから
    [ 0,0,1,0,0,0], # 1のノードから
],columns=nodes,index=nodes)
print(df)
# 出力
#    2  6  4  5  8  1
# 2  0  1  1  0  0  0
# 6  1  0  0  1  0  0
# 4  1  0  0  1  1  1
# 5  0  1  1  0  0  0
# 8  0  0  1  0  0  0
# 1  0  0  1  0  0  0

# matplotlibと、networkxというライブラリによって、ネットワークを描画する。
import matplotlib.pyplot as plt
import networkx as nx
plt.figure(figsize=(4,4))
plt.axis("off")
nx.draw_networkx(nx.from_pandas_adjacency(df))
plt.show()

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

# 値の配分を求めるラムダ式、引数は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:ツリーのデータ構造、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

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