「統計学習方法」決定ツリーCART生成アルゴリズム回帰ツリーPython実現

コードはGithub上でダウンロードできます.コードのダウンロードはまず説明してください.「統計学習方法」を見て、カールさんが木に帰ってきた時に、ぼんやりしていて、また例がありません.そして、「マシン学習の実戦」P 162はこれについて言及しています.よく見てみました.この下には「マシン学習の実戦」というコードがありますが、本には原理がありません.原理がよくわからないと、ちょっと分かりにくいです.実现は「统计学习方法」P 69のアルゴリズム5.5(最小二乗回帰树の生成アルゴリズム)である.「統計学習方法」P 69のアルゴリズム5.5を参照してください.
入力:トレーニングデータセットD;出力:回帰ツリーf(x)は、トレーニングデータセットがある入力空間で、各領域を2つのサブ領域に再帰的に分割し、各サブ領域の出力値を決定し、二叉決定ツリーを構築する.(1)最適なカット変数jとカットポイントsを選択する.m i n jを解いて、s[m i n c 1Σx i i∈R 1(j,s)(y i−c 1)2+m i n c 2Σx＿i R 2(j,s)(y i−c 2)2]mathop｛min｝_{j,s}[\mathop｛min｝_{c_1]\sum_{x i\in R_1(j,s)(y i−c_1)^2+\mamathop｛sum{u 2}{sum{u{xuuuuuuuuuuu{i/in R_2(j,s)))(j,s)))(12 cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccm{{{{{{{{{{{{{{{8712;R 2(j,s)(yi−c 2)は変数jを巡回し、固定された切分け変数jに対して切分けポイントs(2)をスキャンし、選択された対(j,s)を用いる.領域を分割し、対応する出力値を決定する:R 1(j,s)=x(j)≦s R_1(j,s)={x^{(j)}≦s｝R 1(j,s)=x≧x(j)≦s,R 2(j,s)=x≧x(j)>s R_2(j,s)={x}x^{(j)>s}R 2(j,s)=x≧x(j)>sc^m=1 N mΣx i∈R m(j,s)y i\hat c_m=\fraac{1}{Num}\sum_{xui\in Rum(j,s)}y_i c^m=Nm 1Σxi∈Rm(j,s)yi,x∈R m,m=1,2 x\in R_m=1,2 x∈Rm,m=1,2(3)は、停止条件を満たすまで、2つのサブ領域に対してステップ(1)、(2)を呼び出し続ける.(4)入力空間をM領域R 1,R 2,⋯,RMに分けて、決定ツリーを生成する:f(x)＝Σm=1 M c^m I(x∈R m)f(x)=\sum_｛m=1｝^M\hat c_mI(x\in R m)f(x)=Σm=1 M c^m I(x∈Rm)
コードを見に来ましょう.

def loadDataSet(self, fileName):    #    
        dataMat = []
        fr = open(fileName)
        for line in fr.readlines(): #     
            curLine = line.strip().split('\t')
            fltLine = map(float, curLine)   #        float,         
            dataMat.append(fltLine)
        return dataMat

この上にはファイルからデータセットのコードをロードしています.

def regLeaf(self, dataSet): #         
        return np.mean(dataSet[:, -1]) #     

コメントを見ると、上のc^m=1 N mΣx＿i＿R m(j,s)y＿i\hat c_に対応しています.m=\fraac{1}{Num}\sum_{xui\in Rum(j,s)}y_i c^m=Nm 1Σxi∈Rm(j,s)yi,x∈R m,m=1,2 x\in R_m、m=1,2 x∈Rm、m=1,2という数式があります.

def regErr(self, dataSet):#    
        return np.var(dataSet[:, -1]) * np.shape(dataSet)[0] #      

先にアプリを見てもいいです.numpy.varは計算分散です.
var=mean(abs(x-x.mean()*2)
分散に行数を掛けるとmean(abs(x-x.mean()*2)ではなく行数で、m i n c 1Σ(y i−c 1)2\mathop｛min｝_に対応します.{c_1}\sum(yui-c_1)^2 minc 1Σ(yi−c 1)2になりましたか?したがって、この関数はm i n j,s[m i n c 1Σx i i∈R 1(j,s)(y i−c 1)2+m i n c 2Σx i i i i i∈R 2(j,s)(y i−c 2)2)\mathop｛min｝_{j,s}[\mathop｛min｝_{c_1]\sum_{x i\in R_1(j,s)(y i−c_1)^2+\mamathop｛sum{u 2}{sum{u{xuuuuuuuuuuu{i/in R_2(j,s)))(j,s)))(12 cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccm{{{{{{{{{{{{{{{8712;R 2(j,s)(yi−c 2).勝ちに乗じて北を追います.

def createTree(self, dataSet, leafType=regLeaf, errType=regErr, ops=(1, 4)):
        feat, val = self.chooseBestSplit(dataSet, leafType, errType, ops)
        if feat == None:    return val  #      ，      
        retTree = {}
        retTree['spInd'] = feat #            
        retTree['spVal'] = val  #            （        ，      ，      ）
        lSet, rSet = self.binSplitDataSet(dataSet, feat, val)   #             
        retTree['left'] = self.createTree(lSet, leafType, errType, ops) #    2       ，    
        retTree['right'] = self.createTree(rSet, leafType, errType, ops)
        return retTree

これはツリーのコードです.大体の思想は、区分を継続する必要があるかどうかを判断することによって、説明が必要でなければ、すでにリーフノードであり、リーフノードの値に戻ります.分割が必要であれば、再帰的に分割し続けます.引き続きどのように一番いい特徴を選ぶかを見てください.

def chooseBestSplit(self, dataSet, leafType=regLeaf, errType=regErr, ops=(1, 4)):
        tolS = ops[0] #        
        tolN = ops[1]   #        
        if len(set(dataSet[:, -1].T.tolist()[0])) == 1: #          ，        ，    
            return None, leafType(dataSet)
        m, n = np.shape(dataSet)    #m   ，n   
        S = errType(self, dataSet)    #      
        bestS = np.inf  #np.inf       ，             ，          ，                    
        bestIndex = 0
        bestValue = 0
        for featIndex in range(n-1):    #       
            for splitVal in set(dataSet[:,featIndex].T.A.tolist()[0]): #        ，    ,  ：        ，   
                mat0, mat1 = self.binSplitDataSet(dataSet, featIndex, splitVal) #     
                if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN):    #         ，       4，        
                    continue
                newS = errType(self, mat0) + errType(self, mat1)    #    
                if newS < bestS:    #       
                    bestIndex = featIndex
                    bestValue = splitVal
                    bestS = newS
        if (S - bestS) < tolS:  #           
            return None, leafType(self, dataSet)
        mat0, mat1 = self.binSplitDataSet(dataSet, bestIndex, bestValue)
        if (np.shape(mat0)[0] < tolN) or(np.shape(mat1)[0] < tolN): #        （            4      ）
            return None, leafType(self, dataSet)
        return bestIndex, bestValue

このコードは、つまり上のアルゴリズム(1)のステップです.
［m i n c 1Σx i i i∈R1(j,s)(y i−−c 1)2+m i n c 2Σx i i i i i i i i i i i i i i i i∈R2(j,s)(y i−c 2)))[\mamamashp{m in{u{c_1}\sum_{u{uu{u{u{u{uu{u{uu{u{uu{u{u}}}}sum{uu{u{u{u{u{u{xuuuu{u{u{u{u{u}}}}}}sum{uu{u{u{uu{uu{u{uu{xuu{u{u{u{s)(yui−c_2)^2)[m in c 1Σxi＿R 1(j,s)(y i−c 1)2+minc 2Σxi R 2(j,s)(yi−c 2)2]
このコードに対応するnewS = errType(self, mat0) + errType(self, mat1).上のfor featIndex in range(n-1):および中のサイクルは、for splitVal in set(dataSet[:,featIndex].T.A.tolist()[0]):が最小の誤差値を探しています.そしてここに3つの条件があります.この集合は葉っぱのノードであると判定されます.1、クラスラベルの値は同じです.区分する必要がないと説明し、直接にNoneに戻り、葉っぱノードの値を返します.2、全体誤差から最小の誤差が許容誤差降下値(tolS=ops[0]より小さい場合、直接Noneに戻り、葉っぱノード値.3、分割された二つのサブセットのいずれかが4(tolN=ops[1]以下のサンプルであれば、直接Noneに戻り、葉っぱノード値を返します.はい、テストしてみます.

if __name__ == '__main__':
    regTree = RegressionTree()
    myMat = regTree.loadDataSet('ex0.txt')
    myMat = np.mat(myMat)
    print regTree.createTree(myMat)

成功しましたか下に完全なコードを貼り付けます.

# --*-- coding:utf-8 --*--
import numpy as np

class RegressionTree:   #   
    def loadDataSet(self, fileName):    #    
        dataMat = []
        fr = open(fileName)
        for line in fr.readlines(): #     
            curLine = line.strip().split('\t')
            fltLine = map(float, curLine)   #        float,         
            dataMat.append(fltLine)
        return dataMat

    def binSplitDataSet(self, dataSet, feature, value): #             
        mat0 = dataSet[np.nonzero(dataSet[:, feature] > value)[0], :]   #  ：        ，   
        mat1 = dataSet[np.nonzero(dataSet[:, feature] <= value)[0], :]  #np.nonzero(...)[0]      
        return mat0, mat1
    def regLeaf(self, dataSet): #         
        return np.mean(dataSet[:, -1])

    def regErr(self, dataSet):#    
        return np.var(dataSet[:, -1]) * np.shape(dataSet)[0]    #      

    def createTree(self, dataSet, leafType=regLeaf, errType=regErr, ops=(1, 4)):
        feat, val = self.chooseBestSplit(dataSet, leafType, errType, ops)
        if feat == None:    return val  #      ，      
        retTree = {}
        retTree['spInd'] = feat #            
        retTree['spVal'] = val  #            （        ，      ，      ）
        lSet, rSet = self.binSplitDataSet(dataSet, feat, val)   #             
        retTree['left'] = self.createTree(lSet, leafType, errType, ops) #    2       ，    
        retTree['right'] = self.createTree(rSet, leafType, errType, ops)
        return retTree

    def chooseBestSplit(self, dataSet, leafType=regLeaf, errType=regErr, ops=(1, 4)):
        tolS = ops[0] #        
        tolN = ops[1]   #        
        if len(set(dataSet[:, -1].T.tolist()[0])) == 1: #          ，        ，    
            return None, leafType(dataSet)
        m, n = np.shape(dataSet)    #m   ，n   
        S = errType(self, dataSet)    #      
        bestS = np.inf  #np.inf       ，             ，          ，                    
        bestIndex = 0
        bestValue = 0
        for featIndex in range(n-1):    #       
            for splitVal in set(dataSet[:,featIndex].T.A.tolist()[0]): #        ，    ,  ：        ，   
                mat0, mat1 = self.binSplitDataSet(dataSet, featIndex, splitVal) #     
                if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN):    #         ，       4，        
                    continue
                newS = errType(self, mat0) + errType(self, mat1)    #    
                if newS < bestS:    #       
                    bestIndex = featIndex
                    bestValue = splitVal
                    bestS = newS
        if (S - bestS) < tolS:  #           
            return None, leafType(self, dataSet)
        mat0, mat1 = self.binSplitDataSet(dataSet, bestIndex, bestValue)
        if (np.shape(mat0)[0] < tolN) or(np.shape(mat1)[0] < tolN): #        （            4      ）
            return None, leafType(self, dataSet)
        return bestIndex, bestValue

データセットファイル「ex 0.txt」と回帰ツリーの完全コードをマシンに見て学習します.