マシン学習アルゴリズム実現(2):ID 3、C 4.5、CART分類と回帰の比較
75468 ワード
【シリーズの冒頭】このシリーズを開くのは、最近いくつかのアルゴリズムを勉強していますが、紙の上で話をするのはあまりにも長いので、アルゴリズムの流れを覚えています.このシリーズは、アルゴリズムの順序を論理回帰、決定ツリー(CART)、AdaBoost、GBDTとする.他のアルゴリズムを後続の学習状況に基づいて追加した.
本論文の主な目的は実現コードを貼ることであり、ID 3、C 4.5、CARTの3つの政策決定ツリーを比較して分類と回帰問題の違いを実現することである.
前言
ID 3とC 4.5アルゴリズムの実装はほぼ同じであり、唯一の点の違いは、ツリーの構造を決定する際にノード分裂前後の利得計算である.
暴力エニュメレーションのすべての可能なツリー構造は、損失が一番小さいものを選ぶのがNP困難な問題であるため、ここでは、1つのリーフノードを分割しようと試みるたびに、分裂前後の利得を計算し、利得が一番大きいものを選ぶ貪欲なアルゴリズムを用いている.(つまり、毎回特徴を選択して、現在のリーフノードを分裂させる)
ID 3アルゴリズムは情報ゲイン、C 4.5は情報利得比、CARTはジニ係数を採用する.
CARTアルゴリズムは後の方がいい実装ですが、分類と回帰の二つの方法を実現する時にコードはほとんど同じです.CARTの分類樹は回帰樹と言えます.
コードの総流れ
まず分類と回帰の二つの用途から見ます.【ID 3とC 4.5】分類は、情報利得／情報利得比を計算することにより、再帰的な選択情報利得が最も大きいものを最適な特徴として分割する.回帰は、各値に対応するy計算分散であり、分散の最大値を最適な特徴として分割する.【CART】分類と回帰は2分の1の特徴であり、ビキニ係数を用いて特徴的な分類純度を測定し、ビキニ指数の高いものを選ぶことに違いがある.回帰計算は、二分された両方の特徴の回帰値と平均値の二乗誤差である.
ID 3コード(分類、回帰)
分類(ベースから上のコード):は、エントロピー及び情報利得関数 を計算する.ツリーを生成する トレーニングと予測 は、指定された特徴上のカテゴリ分散 を計算する.ツリーを生成する トレーニングと予測
分類(ベースから上のコード):は、ジニ指数と二分割特徴関数 を計算する.最適な(変数、カットオフポイント) が見つかりました.分類ツリーを構築する トレーニングと予測 は、平均二乗誤差と二分データ関数 を計算する.最適(変数、カットオフポイント)を探しています. 回帰ツリーを構築する フィッティングと予測
本論文の主な目的は実現コードを貼ることであり、ID 3、C 4.5、CARTの3つの政策決定ツリーを比較して分類と回帰問題の違いを実現することである.
前言
ID 3とC 4.5アルゴリズムの実装はほぼ同じであり、唯一の点の違いは、ツリーの構造を決定する際にノード分裂前後の利得計算である.
暴力エニュメレーションのすべての可能なツリー構造は、損失が一番小さいものを選ぶのがNP困難な問題であるため、ここでは、1つのリーフノードを分割しようと試みるたびに、分裂前後の利得を計算し、利得が一番大きいものを選ぶ貪欲なアルゴリズムを用いている.(つまり、毎回特徴を選択して、現在のリーフノードを分裂させる)
ID 3アルゴリズムは情報ゲイン、C 4.5は情報利得比、CARTはジニ係数を採用する.
CARTアルゴリズムは後の方がいい実装ですが、分類と回帰の二つの方法を実現する時にコードはほとんど同じです.CARTの分類樹は回帰樹と言えます.
コードの総流れ
まず分類と回帰の二つの用途から見ます.【ID 3とC 4.5】分類は、情報利得／情報利得比を計算することにより、再帰的な選択情報利得が最も大きいものを最適な特徴として分割する.回帰は、各値に対応するy計算分散であり、分散の最大値を最適な特徴として分割する.【CART】分類と回帰は2分の1の特徴であり、ビキニ係数を用いて特徴的な分類純度を測定し、ビキニ指数の高いものを選ぶことに違いがある.回帰計算は、二分された両方の特徴の回帰値と平均値の二乗誤差である.
ID 3コード(分類、回帰)
分類(ベースから上のコード):
from sklearn.datasets import load_iris
import numpy as np
import pandas as pd
def entropy(feature):
uni_val, cnt = np.unique(feature, return_counts=True)
H = np.sum(-cnt[i]/np.sum(cnt)*np.log2(cnt[i] / np.sum(cnt)) for i in range(len(uni_val)))
return H
def InfoGain(dataset, f_test_col, Y_col=-1):
entropy_before = entropy(dataset.iloc[:, Y_col])
uni_val, cnt = np.unique(dataset.iloc[:, f_test_col], return_counts=True)
entropy_cond = np.sum([(cnt[i] / np.sum(cnt)) * entropy(dataset.where(dataset.iloc[:, f_test_col]
== uni_val[i]).dropna().iloc[:, Y_col])
for i in range(len(uni_val))])
return entropy_before - entropy_cond
def gen_tree(dataset, org_dataset, f_cols, Y_col=-1, p_node_cls=None):
#1) ;2) ;3) .
if len(np.unique(dataset.iloc[:, Y_col])) <= 1:return np.unique(dataset.iloc[:, Y_col])[0]
elif len(dataset) == 0:
uni_cls, cnt = np.unique(
org_dataset.iloc[:, Y_col], return_counts=True)
return uni_cls[np.argmax(cnt)]
elif len(f_cols) == 0:
return p_node_cls
else:
#
cur_uni_cls, cnt = np.unique(dataset.iloc[:, Y_col], return_counts=True)
cur_node_cls = cur_uni_cls[np.argmax(cnt)]
del cur_uni_cls, cnt
#
gains = [InfoGain(dataset, f_col) for f_col in f_cols]
best_f = f_cols[np.argmax(gains)]
#
f_cols = [col for col in f_cols if col != best_f]
# ，
tree = {best_f: {}}
for val in np.unique(dataset.iloc[:, best_f]):
sub_data = dataset.where(dataset.iloc[:, best_f] == val).dropna()
sub_tree = gen_tree(sub_data, dataset, f_cols, Y_col, cur_node_cls)
tree[best_f][val] = sub_tree
return tree
def fit(X_train, Y_train):
dataset = np.c_[X_train, y_train]
dataset = pd.DataFrame(dataset, columns=list(range(dataset.shape[1])))
tree = gen_tree(dataset, dataset, list(range(dataset.shape[1] - 1)))
return tree
def predict_one(X_test, tree, default=-1):
for feature in list(X_test.keys()):
if feature in list(tree.keys()):#
try:
sub_tree = tree[feature][X_test[feature]]
if isinstance(sub_tree, dict): #
return predict_one(X_test, tree=sub_tree)
else:
return sub_tree
except: # ， default
return default
def predict(X_test, tree):
X_test = pd.DataFrame(X_test, columns=list(range(X_test.shape[1]))).to_dict(orient='record')
Y_pred = list()
for item in X_test:
Y_pred.append(predict_one(item, tree=tree))
return Y_pred
import numpy as np
import pandas as pd
def Var(data, f_test_col, y_col=-1):
f_uni_val = np.unique(data.iloc[:, f_test_col])
f_var = 0
for val in f_uni_val:
cutset = data[data.iloc[:, f_test_col] == val].reset_index()
cur_var = (len(cutset) / len(data)) * np.var(cutset.iloc[:, y_col], ddof=1)
f_var += cur_var
return f_var
def gen_tree(data, org_dataset, f_cols, min_instances=5, y_col=-1, p_node_mean=None):
if len(data) <= int(min_instances):
return np.mean(data.iloc[:, y_col])
elif len(data) == 0:
return np.mean(org_dataset.iloc[:, y_col])
elif len(f_cols) == 0:
return p_node_mean
else:
p_node_mean = np.mean(data.iloc[:, y_col])
f_vars = [Var(data, f) for f in f_cols]
best_f_idx = np.argmax(f_vars)
best_f = f_cols[best_f_idx]
tree = {best_f: {}}
features = [f for f in f_cols if f != best_f]
for val in np.unique(data.iloc[:, best_f]):
subset = data.where(data.iloc[:, best_f] == val).dropna()
tree[best_f][val] = gen_tree(subset, data, features, min_instances, y_col, p_node_mean)
return tree
def fit(X_train, y_train):
dataset = np.c_[X_train, y_train]
dataset = pd.DataFrame(dataset, columns=list(range(dataset.shape[1])))
return gen_tree(dataset, dataset, list(range(dataset.shape[1] - 1)))
def predict_one(x_test, tree, default=0):
for feature in list(x_test.keys()):
if feature in list(tree.keys()):
try:
sub_tree = tree[feature][x_test[feature]]
if isinstance(sub_tree, dict):
return predict_one(x_test, tree=sub_tree)
else:
return sub_tree
except:
return default
def predict(X_test, tree):
X_test = pd.DataFrame(X_test, columns=list(range(X_test.shape[1]))).to_dict(orient='record')
print(X_test)
y_pred = []
for item in X_test:
y_pred.append(predict_one(item, tree))
return np.array(y_pred)
分類(ベースから上のコード):
import numpy as np
from scipy import stats
class DecisionTreeClassifier:
def __init__(self, max_depth=None, min_samples_split=5, min_samples_leaf=5, min_impurity_decrease=0.0):
self.__max_depth = max_depth
self.__min_samples_split = min_samples_split
self.__min_samples_leaf = min_samples_leaf
self.__min_impurity_decrease = min_impurity_decrease
self.tree = None
self.__nodes = 0
def __Gini(self, data, y_idx=-1):
K = np.unique(data[:, y_idx])
gini_idx = 1 - np.sum(np.square(np.sum(data[data[:, y_idx] == k][:, -2]) / np.sum(data[:, -2])) for k in K)
return gini_idx
def __BinSplitData(self, data, f_idx, f_val):
left = data[data[:, f_idx] <= f_val]
right = data[data[:, f_idx] > f_val]
return left, right
def __FindBestPair(self, data):
n_sample, n_feature = data.shape
n_feature -= 2
if n_sample < self.__min_samples_split or len(np.unique(data[:, -1])) == 1:
return None, stats.mode(data[:, -1])[0][0]
Gini_before = self.__Gini(data)
best_gain = 0
best_f_idx = None
best_f_val = stats.mode(np.unique(data[:, -1]))[0][0]
for f_idx in range(n_feature):
for f_val in np.unique(data[:, f_idx]):
data_left, data_right = self.__BinSplitData(data, f_idx, f_val)
if len(data_left) < self.__min_samples_leaf or len(data_right) < self.__min_samples_leaf:
continue
Gini_after = np.sum(data_left[:, -2]) / np.sum(data[:, -2]) * self.__Gini(data_left) + \
np.sum(data_right[:, -2] / np.sum(data[:, -2]) * self.__Gini(data_right))
gain = Gini_after - Gini_before
if gain < self.__min_impurity_decrease or gain < best_gain:
continue
else:
best_gain = gain
best_f_idx, best_f_val = f_idx, f_val
return best_f_idx, best_f_val
def __CART(self, data):
best_f_idx, best_f_val = self.__FindBestPair(data)
self.__nodes += 1
if best_f_idx is None:
return best_f_val
if self.__max_depth:
if self.__nodes >= 2 ** self.__max_depth:
return stats.mode(data[:, -1])[0][0]
tree = dict()
tree['cut_f'] = best_f_idx
tree['cut_val'] = best_f_val
data_left, data_right = self.__BinSplitData(data, best_f_idx, best_f_val)
tree['left'] = self.__CART(data_left)
tree['right'] = self.__CART(data_right)
return tree
def fit(self, X_train, y_train, sample_weight=None):
if sample_weight is None:
sample_weight = np.array([1 / len(X_train)] * len(X_train))
else:
sample_weight = sample_weight
data = np.c_[X_train, sample_weight, y_train]
self.tree = self.__CART(data)
def __predict_one(self, x_test, tree):
if isinstance(tree, dict):
cut_f_idx, cut_f_val = self.__FindBestPair(data)
sub_tree = tree['left'] if x_test[cut_f_idx] <= cut_f_val else tree['right']
return self.__predict_one(x_test, sub_tree)
else:
return tree
def predict(self, X_test):
return np.array([self.__predict_one(x_test, self.tree) for x_test in X_test])
import numpy as np
class DecisionTreeRegressor:
def __init__(self, max_depth=None, min_samples_split=5, min_samples_leaf=5, min_impurity_decrease=0.0):
self.__max_depth = max_depth
self.__min_samples_split = min_samples_split
self.__min_samples_leaf = min_samples_leaf
self.__min_impurity_decrease = min_impurity_decrease
self.tree = None
self.__nodes = 0
def __MSE(self, data, y_idx=-1):
n_sample = len(data)
mean = np.mean(data[:, y_idx])
return np.sum(np.square(data[:, y_idx] - mean)) / n_sample
def __BinSplitData(self, data, f_idx, f_val):
left = data[data[:, f_idx] <= f_val]
right = data[data[:, f_idx] > f_val]
return left, right
def __FindBestPair(self, data):
n_sample, n_feature = data.shape
# ，
if len(np.unique(data[:, -1])) == 1 or n_sample < self.__min_samples_split:
return None, np.mean(data[:, -1])
MSE_before = self.__MSE(data)
best_gain = 0
best_f_idx = None
best_f_val = np.mean(data[:, -1])
for f_idx in range(n_feature - 1):
for f_val in np.unique(data[:, f_idx]):
data_left, data_right = self.__BinSplitData(data, f_idx, f_val)
if len(data_left) < self.__min_samples_leaf or len(data_right) < self.__min_samples_leaf:
continue
MSE_after = len(data_left) / len(data) * self.__MSE(data_left) + \
len(data_right) / len(data) * self.__MSE(data_right)
gain = MSE_after - MSE_before
if gain < best_gain or gain < self.__min_impurity_decrease:
continue
else:
best_gain = gain
best_f_idx, best_f_val = f_idx, f_val
return best_f_idx, best_f_val
def __CART(self, data):
best_f_idx, best_f_val = self.__FindBestPair(data)
self.__nodes += 1
if best_f_idx is None:
return best_f_val
if self.__max_depth:
if self.__nodes >= 2 ** self.__max_depth:
return np.mean(data[:, -1])
tree = dict()
tree['cut_f'] = best_f_idx
tree['cut_val'] = best_f_val
data_left, data_right = self.__BinSplitData(data, best_f_idx, best_f_val)
tree['left'] = self.__CART(data_left)
tree['right'] = self.__CART(data_right)
return tree
def fit(self, X_train, y_train):
data = np.c_[X_train, y_train]
self.tree = self.__CART(data)
def __predict_one(self, x_test, tree):
if isinstance(tree, dict):
cut_f_idx, cut_val = tree['cut_f'], tree['cut_val']
sub_tree = tree['left'] if x_test[cut_f_idx] <= cut_val else tree['right']
return self.__predict_one(x_test, sub_tree)
else:#
return tree
def predict(self, X_test):
return [self.__predict_one(x_test, self.tree) for x_test in X_test]