【機械学習ノート27】CARTアルゴリズム-回帰木と分類木
3488 ワード
【参考資料】【1】『統計学習方法』5.5 CARTアルゴリズム【2】http://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeRegressor.html
基本概念
分類と回帰ツリー(classification and regression tree,CART)は広く応用されている決定ツリー学習方法であり、特徴選択、ツリーの生成と剪定からなり、分類としても回帰としても使用することができる.
回帰ツリー
回帰ツリーの定義
XとYをそれぞれ入出力変数とすると、では、訓練セットD={(x 1,y 1),(x 2,y 2)..(x N,y N)}D={(x_1,y_1),(x_2,y_2)…(x_N,y_N)}D={(x 1,y 1),(x 2,y 2)…(xN,yN)}1つの回帰ツリーが入力空間に対応する(特徴)の区分とこの区分の入力値.数学的定義:M個の分類が存在し、各分類の単位はR MR_M RMであり、この単位の出力はc Mc_M cMであり、回帰ツリーモデルf(x)=Σm=1 McMI(x∈R M)f(x)=sumlimits_{m=1}^{M}c_MI(xin R_M)f(x)=m=1ΣMcMI(x∈RM)であり、ここでI Iはその分類の集合を表す.
そこで,二乗誤差Σ(y i−f(x i))2sum(y_i−f(x_i)^2Σ(yi−f(xi))2を用いて回帰木訓練時の誤差を表すことができる.
回帰ツリーの生成
ステップ1:入力データを二叉決定ツリーに分割するには、特徴jと特徴上のしきい値sを選択します.このステップでは、すべてのフィーチャーとそのしきい値を遍歴し、最適解を取得する必要があります.数学的には、次のように表されます.
1)ターゲットは2つの集合をとることである:R 1(j,s)={x∣x(j)s}R_1(j,s)=\{x|x^{(j)}s}R 1(j,s)={x∣x(j)s}2)解誤差最小値minj,s[minc 1Σx∈R 1(y i−c 1)2+minc 2Σx∈R 2(y i−c 2)2]minlimits_{j,s}[minlimits_{c_1}sumlimits_{xin R_1}(y_i-c 1)^2+minlimits_{c_2}sumlimits_{xin R_2}(y_i-c 2)^2 j,smin[c 1 min x∈R 1Σ(yi−c 1)2+c 2 min x∈R 2Σ(yi−c 2)2]第2歩:ここで設定した出力値はトレーニングデータ出力の平均分散$c_1 = ave(y_i | x_i\in R_1)\quad c_2 = ave(y_i | x_i\in R_2) $
ステップ3:分割された2つのサブ領域について,再びステップ1,2を繰り返し,停止条件を満たすことを知り,M個の領域を持つ決定ツリーを生成する.
分類ツリー
キニーしすう
分類問題ではKクラスがあると仮定し,サンプル点がkクラスに属する確率はp k p_である.k pk,確率分布のキニー係数は,G i n i(p)＝Σk＝1 K pk(1−pk)＝1−Σk＝1 K pk 2 Gini(p)＝sumlimits＿{k=1}^{K}p_k(1 - p_k) = 1 -\sum\limits_{k=1}^{K}p_k^2 Gini(p)=k=1∑Kpk(1−pk)=1−k=1∑Kpk2
与えられたサンプル集合Dについて,そのキニー指数はG i n i(D)＝1−Σk＝1 K(∣C k∣∣D∣)2 Gini(D)＝1−sumlimits＿であった.{k=1}^{K}(dfrac{|C_k|}{|D|})^2 Gini(D)=1−k=1ΣK(∣D∣∣Ck∣)2,ここでC k C_k CkはDにおけるkクラスに属する数を表す.
キニー係数は集合Dの不確実性を表し,Gini(D,A)はDをAとしてD 1 D 2 D_に分割する1\quad D_2 D 1 D 2後の不確実性はキニー係数が大きいほど不確実性が大きい.ここで、G i n i(D,A)=D 1 D G i(D 1)+D 2 D G i(D 2)Gini(D,A)=dfrac{D_1}{D}Gini(D_1)+dfrac{D_2}{D}Gini(D_2)Gini(D,A)=DD 1 Gini(D 1)+DD 2 Gini(D 2)
分類木の訓練
これは回帰ツリーの方式と基本的に同じであり,損失定義が最小二乗からキニー指数に変化するだけである.
ステップ1:入力データDの各特徴と可能な取値について、分類Aを行い、Gini(D,A)を計算するステップ2:Gini(D,A)の最小のデータのセットを取り、今回の最も特徴と最適な接点とするステップ3:上記区分の結果について、反復ステップ1,2ステップ4:CART決定ツリー(分類)を生成する
コードインプリメンテーション(回帰ツリー、sklearnベース)
基本概念
分類と回帰ツリー(classification and regression tree,CART)は広く応用されている決定ツリー学習方法であり、特徴選択、ツリーの生成と剪定からなり、分類としても回帰としても使用することができる.
回帰ツリー
回帰ツリーの定義
XとYをそれぞれ入出力変数とすると、では、訓練セットD={(x 1,y 1),(x 2,y 2)..(x N,y N)}D={(x_1,y_1),(x_2,y_2)…(x_N,y_N)}D={(x 1,y 1),(x 2,y 2)…(xN,yN)}1つの回帰ツリーが入力空間に対応する(特徴)の区分とこの区分の入力値.数学的定義:M個の分類が存在し、各分類の単位はR MR_M RMであり、この単位の出力はc Mc_M cMであり、回帰ツリーモデルf(x)=Σm=1 McMI(x∈R M)f(x)=sumlimits_{m=1}^{M}c_MI(xin R_M)f(x)=m=1ΣMcMI(x∈RM)であり、ここでI Iはその分類の集合を表す.
そこで,二乗誤差Σ(y i−f(x i))2sum(y_i−f(x_i)^2Σ(yi−f(xi))2を用いて回帰木訓練時の誤差を表すことができる.
回帰ツリーの生成
ステップ1:入力データを二叉決定ツリーに分割するには、特徴jと特徴上のしきい値sを選択します.このステップでは、すべてのフィーチャーとそのしきい値を遍歴し、最適解を取得する必要があります.数学的には、次のように表されます.
1)ターゲットは2つの集合をとることである:R 1(j,s)={x∣x(j)
ステップ3:分割された2つのサブ領域について,再びステップ1,2を繰り返し,停止条件を満たすことを知り,M個の領域を持つ決定ツリーを生成する.
分類ツリー
キニーしすう
分類問題ではKクラスがあると仮定し,サンプル点がkクラスに属する確率はp k p_である.k pk,確率分布のキニー係数は,G i n i(p)＝Σk＝1 K pk(1−pk)＝1−Σk＝1 K pk 2 Gini(p)＝sumlimits＿{k=1}^{K}p_k(1 - p_k) = 1 -\sum\limits_{k=1}^{K}p_k^2 Gini(p)=k=1∑Kpk(1−pk)=1−k=1∑Kpk2
与えられたサンプル集合Dについて,そのキニー指数はG i n i(D)＝1−Σk＝1 K(∣C k∣∣D∣)2 Gini(D)＝1−sumlimits＿であった.{k=1}^{K}(dfrac{|C_k|}{|D|})^2 Gini(D)=1−k=1ΣK(∣D∣∣Ck∣)2,ここでC k C_k CkはDにおけるkクラスに属する数を表す.
キニー係数は集合Dの不確実性を表し,Gini(D,A)はDをAとしてD 1 D 2 D_に分割する1\quad D_2 D 1 D 2後の不確実性はキニー係数が大きいほど不確実性が大きい.ここで、G i n i(D,A)=D 1 D G i(D 1)+D 2 D G i(D 2)Gini(D,A)=dfrac{D_1}{D}Gini(D_1)+dfrac{D_2}{D}Gini(D_2)Gini(D,A)=DD 1 Gini(D 1)+DD 2 Gini(D 2)
分類木の訓練
これは回帰ツリーの方式と基本的に同じであり,損失定義が最小二乗からキニー指数に変化するだけである.
ステップ1:入力データDの各特徴と可能な取値について、分類Aを行い、Gini(D,A)を計算するステップ2:Gini(D,A)の最小のデータのセットを取り、今回の最も特徴と最適な接点とするステップ3:上記区分の結果について、反復ステップ1,2ステップ4:CART決定ツリー(分類)を生成する
コードインプリメンテーション(回帰ツリー、sklearnベース)
# -*- coding: utf-8 -*-
import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeRegressor
def _test_cart_regresssion():
index = np.linspace(0, 10, 200);
delta = np.random.rand()
index.shape = (200, 1)
y_test = 0.3*index + np.sin(index) + delta
clf = DecisionTreeRegressor(max_depth=4)
"""
4， 4 ， 2^4=16
"""
clf.fit(index, y_test)
y_pred = clf.predict(index)
plt.scatter(index, y_test, color='black',marker='o')
plt.plot(index, y_pred, color='blue', linewidth=2)
plt.xticks(())
plt.yticks(())
plt.show()
pass;
"""
：
CART 《CART 》
：fredric
：2018-11-4
"""
if __name__ == "__main__":
_test_cart_regresssion()
