javascript深度克隆

Introduction:

分类与回归树(classification and regression tree, CART)模型由Breiman等人在1984年提出,CART同样由特征选择、树的生成及剪枝组成,既可以用于分类也可以用于回归,以下简要讨论树生成部分,在随后的博文中再探讨树剪枝的问题。

Algorithm:

step 1. 分别计算所有特征中各个分类的基尼系数

step 2. 选择有最小基尼系数的特征作为最优切分点,因$Gini(D,A_i=j)$最小,所以$A_i=j$作为最优切割点,$A_i$作为根节点 

step 3
. 在剩余的特征中重复step 1和2,获取最优特征及最优切割点,直至所有特征用尽或者是所有值都一一归类,最后所生成的决策树与ID3算法所生成的完全一致

Formula:

Code:

  1 # -*- coding: utf-8 -*-
  2 
  3 FILENAME = decision_tree_text.txt
  4 MAXDEPTH = 10
  5 
  6 import numpy as np
  7 import plottree
  8 
  9 class Cart():
 10     def __init__(self):
 11         self.trainresult = WARNING : please trainDecisionTree first!
 12         pass
 13 
 14 
 15     def trainDecisionTree(self, filename):
 16         self.__loadDataSet(filename)
 17         self.__optimalTree(self.__datamat)
 18 
 19 
 20     def __loadDataSet(self, filename):
 21         fread   = open(filename)
 22         self.__dataset = np.array([row.strip().split(\t)  23                   for row in fread.readlines()])
 24         self.__textdic     = {}
 25         for col in self.__dataset.T:
 26             i = .0
 27             for cell in col:
 28                 if not self.__textdic.has_key(cell):
 29                     self.__textdic[cell] = i
 30                     i += 1
 31         self.__datamat = np.array([np.array([(lambda cell:self.__textdic[cell])(cell)  32                   for cell in row])  33                   for row in self.__dataset])
 34 
 35 
 36     def __getSampleCount(self, setd, col = -1, s = None):
 37         dic = {}
 38 
 39         if s is not None:
 40             newset = self.__getSampleMat(setd,col,s)[:,-1]
 41         else:
 42             newset = setd[:,col]
 43 
 44         for cell in newset:
 45             if not dic.has_key(cell):
 46                 dic[cell] =  1.
 47             else:
 48                 dic[cell] += 1
 49         return dic
 50 
 51 
 52     def __getSampleMat(self, setd, col, s):
 53         lista = []; listb = []
 54         for row in setd:
 55             if row[col] == s:
 56                 lista.append(row)
 57             else:
 58                 listb.append(row)
 59         return  np.array(lista), np.array(listb)
 60 
 61 
 62     def __getGiniD(self, setd):
 63         sample_count = self.__getSampleCount(setd)
 64         gini = 0
 65         for item in sample_count.items():
 66             gini += item[1]/len(setd) * (1- item[1]/len(setd))
 67         return gini
 68 
 69 
 70     def __getGiniDA(self, setd, a):
 71         sample_count = self.__getSampleCount(setd, a)
 72         dic = {}
 73         for item in sample_count.items():
 74             setd_part_a, setd_part_b = self.__getSampleMat(setd, a, item[0])
 75             gini = item[1]/len(setd) * self.__getGiniD(setd_part_a) +  76                    (1- item[1]/len(setd)) * self.__getGiniD(setd_part_b)
 77             dic[item[0]]=gini
 78         return min(dic.items()), dic
 79 
 80 
 81     def __optimalNode(self, setd):
 82         coln    = 0
 83         ginicol = 0
 84         mingini = {1:1}
 85         for col in setd[:,:-1].T:
 86             gini, dic = self.__getGiniDA(setd, coln)
 87             if gini[1] < mingini[1]:
 88                 mingini = gini
 89                 ginicol = coln
 90             coln += 1
 91         return ginicol, mingini[0], mingini[1]
 92 
 93 
 94     def __optimalNodeText(self, col, value):
 95         row = 0
 96         tex = None
 97         for cell in self.__dataset.T[col]:
 98             if self.__datamat[row,col] == value:
 99                 tex = cell
100                 break
101             row += 1
102         return tex
103 
104 
105     def __optimalTree(self, setd):
106         arr      = setd
107         count    = MAXDEPTH-1
108         features = np.array(range(len(arr.T)))
109         lst      = []
110         defaultc = None
111         while count > 0:
112             count               -= 1
113             ginicol, value, gini = self.__optimalNode(arr)
114             parts                = self.__getSampleMat(arr, ginicol, value)
115             args                 = [np.unique(part[:,-1]) for part in parts]
116             realvalues           = [np.unique(part[:,ginicol])[0] for part in parts]
117             realcol              = features[ginicol]
118             features             = np.delete(features, ginicol)
119             if gini == 0 or len(arr.T) == 2:
120                 if args[0] == defaultc:
121                     value  = realvalues[0]
122                 else:
123                     value  = realvalues[1]
124                 self.trainresult = self.__buildList(lst, realcol, value, gini)
125                 self.__plotTree(self.trainresult)
126                 return
127             if len(args[0]) == 1:
128                 defaultc = args[0]
129                 self.__buildList(lst, realcol, realvalues[0], gini)
130                 arr = np.concatenate((parts[1][:,:ginicol], 131                       parts[1][:,ginicol+1:]), axis=1)
132             else:
133                 defaultc = args[1]
134                 self.__buildList(lst, realcol, realvalues[1], gini)
135                 arr = np.concatenate((parts[0][:,:ginicol], 136                       parts[0][:,ginicol+1:]), axis=1)
137 
138 
139     def __plotTree(self, lst):
140         dic = {}
141         for item in lst:
142             if dic == {}:
143                 dic[item[0]] = {item[1]:c1,ELSE:c2}
144             else:
145                 dic = {item[0]:{item[1]:c1,ELSE:dic}}
146         tree = plottree.retrieveTree(dic)
147         self.trainresult = tree
148         plottree.createPlot(tree)
149 
150 
151     def __buildList(self, lst, col, value, gini):
152         print feature col:, col, 153                       feature val:, self.__optimalNodeText(col, value), 154                       Gini:, gini, \n
155         lst.insert(0,[col,str(self.__optimalNodeText(col, 156                    value))+:+str(value)])
157         return lst
158 
159 
160 
161 if __name__ == __main__:
162     cart = Cart()

Reference:

李航. 统计学习方法

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。