第10章 決定木
準備
次のコードを書きなさい。
import pprint
import numpy as np
Du = np.array([
[1, 0, 0, 0, 1, 0, +1],
[0, 1, 0, 0, 1, 0, +1],
[1, 1, 0, 0, 1, 0, +1],
[1, 0, 0, 1, 1, 0, +1],
[1, 0, 0, 0, 0, 1, +1],
[0, 1, 0, 1, 0, 1, +1],
[0, 0, 1, 0, 1, 0, -1],
[0, 0, 1, 1, 1, 0, -1],
[0, 1, 0, 0, 1, 1, -1],
[0, 0, 1, 0, 0, 1, -1],
[1, 1, 0, 1, 1, 0, np.nan],
[0, 0, 1, 0, 1, 1, np.nan],
[0, 1, 1, 1, 1, 0, np.nan],
])
I = np.arange(Du.shape[0])
x = Du[:,:-1]
ru = Du[:,-1]
Iu = I[~np.isnan(ru)]
Iu_not = np.setdiff1d(I, Iu)
DuL = Du[Iu]
xL = x[Iu]
ruL = ru[Iu]
DuU = Du[Iu_not]
xU = x[Iu_not]
ジニ係数
訓練データ\(D_{u}^{L}\)のジニ係数\(G(D^{L}_{u})\)は次式で定義される。
\[G(D^{L}_{u}) = 1 - \{(p^{+})^{2} + (p^{-})^{2}\}\]ここで、\(p^{+}\)は訓練データ\(D_{u}^{L}\)における「好き」な事例が含まれる割合、\(p^{-}\)は「嫌い」な事例が含まれる割合を表し、それぞれ次式で求められる。
\[p^{+} = \frac{\mid D^{L+}_{u} \mid}{\mid D^{L}_{u} \mid}\] \[p^{-} = \frac{\mid D^{L-}_{u} \mid}{\mid D^{L}_{u} \mid}\]ここで、\(\mid D_{u}^{L} \mid\)は訓練事例数である。\(\mid D_{u}^{L+} \mid\)、\(\mid D_{u}^{L-} \mid\)はそれぞれ訓練事例に含まれる正事例数、負事例数である。これらのジニ係数を返す関数を次のコードのとおり定義する。
関数
def G(DL):
"""
訓練データDLのジニ係数を返す。
Parameters
----------
DL : ndarray
訓練データDL
Returns
-------
float
ジニ係数
ただし、DLに事例が含まれていないときは0
"""
if DL.shape[0] == 0: return 0
r = DL[:,-1]
【 問01 】
【 問02 】
【 問03 】
return gini
コード
print('G(DuL) = {:.3f}'.format(G(DuL)))
結果
G(DuL) = 0.480
このとき、次の問いに答えなさい。
01 「好き」な事例が含まれる割合
\(p^{+}\)を求めるコードを書きなさい。得られた値をppとすること。
★
- ブール値インデキシングを使う。
ndarray.shapeを使う。
02 「嫌い」な事例が含まれる割合
\(p^{-}\)を求めるコードを書きなさい。得られた値をpnとすること。
★
- ブール値インデキシングを使う。
ndarray.shapeを使う。
03 ジニ係数
ジニ係数を求めるコードを書きなさい。得られた値をginiとすること。
★
- べき乗を使う。
分割の良さ
訓練データ\(D_{u}^{L}\)を\(D_{u}^{L0}\)と\(D_{u}^{L1}\)に分割したときのジニ係数は次式で定義される。
\[G(D^{L}_{u} \rightarrow [D^{L0}_{u}, D^{L1}_{u}]) = \frac{\mid D^{L0}_{u} \mid G(D^{L0}_{u}) + \mid D^{L1}_{u} \mid G(D^{L1}_{u})}{\mid D^{L0}_{u} \mid + \mid D^{L1}_{u} \mid}\]このジニ係数を返す関数を次のコードのとおり定義する。
def G_partitioned(DL0, DL1):
"""
訓練データをDL0とDL1に分割したときのジニ係数を返す。
Parameters
----------
DL0 : ndarray
訓練データDL0
DL1 : ndarray
訓練データDL1
Returns
-------
float
ジニ係数
"""
【 問06 】
return gini
コード
# 特徴量kを含まない訓練事例集合
k = 0
【 問04 】
# 特徴量kを含む訓練事例集合
print('DuL0 = \n{}'.format(DuL0))
【 問05 】
# 特徴量kを基準に分割したときのジニ係数
print('DuL1 = \n{}'.format(DuL1))
print('G(DuL → [DuL0, DuL1]) = {:.3f}'.format(G_partitioned(DuL0, DuL1)))
結果
DuL0 =
[[ 0. 1. 0. 0. 1. 0. 1.]
[ 0. 1. 0. 1. 0. 1. 1.]
[ 0. 0. 1. 0. 1. 0. -1.]
[ 0. 0. 1. 1. 1. 0. -1.]
[ 0. 1. 0. 0. 1. 1. -1.]
[ 0. 0. 1. 0. 0. 1. -1.]]
DuL1 =
[[1. 0. 0. 0. 1. 0. 1.]
[1. 1. 0. 0. 1. 0. 1.]
[1. 0. 0. 1. 1. 0. 1.]
[1. 0. 0. 0. 0. 1. 1.]]
G(DuL → [DuL0, DuL1]) = 0.267
このとき、次の問いに答えなさい。
04 特徴量kを含まない訓練事例集合
訓練データ\(D_{u}^{L}\)から特徴量\(k\)を含まない（\(x_{i,k}=0\)となる）事例集合をndarrayとして生成するコードを書きなさい。生成したndarrayをDuL0とすること。
★★
- ブール値インデキシングを使う。
05 特徴量kを含む訓練事例集合
訓練データ\(D_{u}^{L}\)から特徴量\(k\)を含む（\(x_{i,k}=1\)となる）事例集合をndarrayとして生成するコードを書きなさい。取得したndarrayをDuL1とすること。
★★
- ブール値インデキシングを使う。
06 特徴量kを基準に分割したときのジニ係数
特徴量\(k\)を基準に分割したときのジニ係数を求めるコードを書きなさい。得られた値をginiとすること。
★★
ndarray.shapeを使う。G(DL)関数を呼ぶ。
決定木の学習
次の関数は、入力された訓練データDLを各特徴量で分割したときの(特徴量のインデックス: ジニ係数)をペアにした辞書を返す関数である。
def get_ginis(DL):
"""
訓練データDLを各特徴量で分割したときの(特徴量のインデックス: ジニ係数)をペアにした辞書を返す。
Parameters
----------
DL : ndarray
訓練データDL
Returns
-------
dict
(特徴量のインデックス: ジニ係数)をペアにした辞書
"""
ginis = {}
for k in range(0, x.shape[1]):
DL0 = DL[DL[:,k]==0]
DL1 = DL[DL[:,k]==1]
ginis[k] = G_partitioned(DL0, DL1)
return ginis
このとき、次の問いに答えなさい。
07 レベル0の選択基準
get_ginis()関数から得られたginisからジニ係数が最小となる特徴量のインデックスを取得するコードを書きなさい。得られた値をk0とすること。
コード
# レベル0（根ノード）の選択基準
ginis = get_ginis(DuL)
print('ginis = ')
pprint.pprint(ginis)
【 問07 】
print('k0 = {}'.format(k0))
DuL0 = DuL[DuL[:,k0]==0]
DuL1 = DuL[DuL[:,k0]==1]
print('DuL0 = \n{}'.format(DuL0))
print('DuL1 = \n{}'.format(DuL1))
結果
ginis =
{0: 0.26666666666666666,
1: 0.45,
2: 0.17142857142857146,
3: 0.4761904761904763,
4: 0.4761904761904763,
5: 0.4666666666666666}
k0 = 2
DuL0 =
[[ 1. 0. 0. 0. 1. 0. 1.]
[ 0. 1. 0. 0. 1. 0. 1.]
[ 1. 1. 0. 0. 1. 0. 1.]
[ 1. 0. 0. 1. 1. 0. 1.]
[ 1. 0. 0. 0. 0. 1. 1.]
[ 0. 1. 0. 1. 0. 1. 1.]
[ 0. 1. 0. 0. 1. 1. -1.]]
DuL1 =
[[ 0. 0. 1. 0. 1. 0. -1.]
[ 0. 0. 1. 1. 1. 0. -1.]
[ 0. 0. 1. 0. 0. 1. -1.]]
★★
min()を使う。
08 レベル1の選択基準
レベル0の分割で得られたDuL0からレベル1a（レベル1の左端ノード）の選択基準となる特徴量のインデックスを取得するコードを書きなさい。得られた値をk1aとすること。
コード
# レベル1a（レベル1の左端ノード）の選択基準
【 問08 】
print('k1a = {}'.format(k1a))
DuL00 = DuL0[DuL0[:,k1a] == 0]
DuL01 = DuL0[DuL0[:,k1a] == 1]
print('DuL00 = \n{}'.format(DuL00))
print('DuL01 = \n{}'.format(DuL01))
結果
k1a = 0
DuL00 =
[[ 0. 1. 0. 0. 1. 0. 1.]
[ 0. 1. 0. 1. 0. 1. 1.]
[ 0. 1. 0. 0. 1. 1. -1.]]
DuL01 =
[[1. 0. 0. 0. 1. 0. 1.]
[1. 1. 0. 0. 1. 0. 1.]
[1. 0. 0. 1. 1. 0. 1.]
[1. 0. 0. 0. 0. 1. 1.]]
★★
get_ginis()関数を呼ぶ。min()を使う。
09 レベル2の選択基準
レベル1の分割で得られたDuL00からレベル2a（レベル2の左端ノード）の選択基準となる特徴量のインデックスを取得するコードを書きなさい。得られた値をk2aとすること。
コード
# レベル2a（レベル2の左端ノード）の選択基準
【 問09 】
print('k2a = {}'.format(k2a))
DuL000 = DuL00[DuL00[:,k2a] == 0]
DuL001 = DuL00[DuL00[:,k2a] == 1]
print('DuL000 = \n{}'.format(DuL000))
print('DuL001 = \n{}'.format(DuL001))
結果
k2a = 3
DuL000 =
[[ 0. 1. 0. 0. 1. 0. 1.]
[ 0. 1. 0. 0. 1. 1. -1.]]
DuL001 =
[[0. 1. 0. 1. 0. 1. 1.]]
★★
get_ginis()関数を呼ぶ。min()を使う。
嗜好予測
次の関数は、訓練データDLから決定木を学習する関数train()およびユーザuのアイテムiに対する予測評価値を返す関数predict()である。
def train(DL, key=0):
"""
学習関数：訓練データDLから決定木を学習する。
Parameters
----------
DL : ndarray
訓練データDL
key : int
キー値
"""
if len(DL) <= 0:
return
elif np.count_nonzero(DL[:,-1]==-1) <= 0:
dtree[key] = '+1'
return
elif np.count_nonzero(DL[:,-1]==+1) <= 0:
dtree[key] = '-1'
return
ginis = get_ginis(DL)
k = min(ginis, key=ginis.get)
dtree[key] = k
DL0 = DL[DL[:,k] == 0]
DL1 = DL[DL[:,k] == 1]
train(DL0, key * 2 + 1)
train(DL1, key * 2 + 2)
def predict(u, i, key=0):
"""
予測関数：ユーザuのアイテムiに対する予測評価値を返す。
Parameters
----------
u : int
ユーザuのID（ダミー）
i : int
アイテムiのID
key : int
キー値
Returns
-------
int
ユーザuのアイテムiに対する予測評価値
"""
if type(dtree[key]) == str: return int(dtree[key])
k = dtree[key]
if x[i,k] == 0:
return predict(u, i, key * 2 + 1)
elif x[i,k] == 1:
return predict(u, i, key * 2 + 2)
コード
dtree = {}
train(DuL)
print('dtree = {}'.format(dtree))
u = 0
【 問10 】
print('ruU_pred = {}'.format(ruU_pred))
結果
dtree = {0: 2, 1: 0, 3: 3, 7: 5, 15: '+1', 16: '-1', 8: '+1', 4: '+1', 2: '-1'}
ruU_pred = {10: 1, 11: -1, 12: -1}
このとき、次の問いに答えなさい。
10 予測対象データに対する嗜好予測
予測対象データ\(D_{u}^{U}\)内の各アイテム\(i\)について予測評価値\(\hat{r}_{u,i}\)を求め、i: predict(u, i)をペアとした辞書を生成するコードを書きなさい。生成した辞書をruU_predとすること。
★★★
- 辞書内包表記を使う。
predict()関数を呼ぶ。