决策树算法python源代码_CART决策树（DecisionTree）的
Python源码实现
1. 前⾔
建议阅读顺序：先阅读源代码，再来看源码关键⽅法的讲解，源码地址RRdmlearning/Decision-Tree
2. 源码讲解
这部分我争取⽤简单易懂的语⾔，阐述源码中关键函数的作⽤与实现细节。
2.1 calculateDiffCount()
def calculateDiffCount(datas):
#将输⼊的数据汇总(input dataSet)
#return results Set{type1:type1Count,type2:type2Count ... typeN:typeNCount}
results = {}
for data in datas:
#data[-1] means dataType
if data[-1] not in results:
results[data[-1]] = 1
el:
results[data[-1]] += 1
return results
授权书英文该函数是计算gini值的辅助函数，假设输⼊的dataSet为为['A', 'B', 'C', 'A', 'A', 'D']，则输出为['A':3,' B':1, 'C':1, 'D':1]，这样分类统计dataSet中每个类别的数量
2.2 gini()
def gini(rows):
#计算gini值(Calculate GINI)
length = len(rows)
results = calculateDiffCount(rows)
英孚英语和舞动美语哪个好imp = 0.0
for i in results:
imp += results[i]/length * results[i]/length
return 1 - imp
这边我们⽤评判树纯度的⽅式为gini值，⼤家也可以使⽤信息熵等其他⽅式，只需写⼀个类似的函数即可
下⾯我们来看⼀下gini值的计算⽅式，不懂公式由来的同学可以看我上⾯推荐林轩⽥教授的视频：
obama speech in shanghai
gini()中调⽤了calculateDiffCoun()可以帮我们快速计算出gini值
2.3 splitDatas()
def splitDatas(rows,value,column):
#根据条件分离数据集(splitDatas by value,column)
#return 2 part(list1,list2)
list1 = []
list2 = []
if(isinstance(value,int) or isinstance(value,float)): #for int and float type
for row in rows:
if (row[column] >= value):list1.append(row)
el:list2.append(row)
el: #for String type
for row in rows:
if row[column] == value:list1.append(row)六级听力满分多少
el:list2.append(row)
return (list1,list2)
这个函数的作⽤是利⽤给定的数据(rows)，要利⽤哪个特征切分(column)，切分的标准(value)来将数据切分成两份，在下⾯⽣成树的过程中会⼀直循环调⽤这个函数与gini()来切分成最好的树。
if(isinstance(value,int) or isinstance(value,float))
这个if是为了判断是数值类型还是字符串类型，若是数值类型则⽐对⼤⼩作为切分标准，字符串则⽐对是否相等。
2.4 buildDecisionTree()
def buildDecisionTree(rows,evaluationFunction=gini):最新英语国际音标表
#递归建⽴决策树，当gain = 0 时停⽌递归
#bulid decision tree by recursive function
#stop recursive function when gain = 0
#return tree
currentGain = evaluationFunction(rows)
column_length = len(rows[0])
rows_length = len(rows)
best_gain = 0.0
best_value = None
best_t = None
#choo the best gain
for col in range(column_length-1):
col_value_t = t([x[col] for x in rows])
for value in col_value_t:
list1,list2 = splitDatas(rows,value,col)
p = len(list1)/rows_length
gain = currentGain - p * evaluationFunction(list1) - (1-p) * evaluationFunction(list2)
if gain > best_gain:
best_gain = gain
best_value = (col,value)
best_t = (list1,list2)
dcY = {'impurity' : '%.3f' % currentGain, 'samples' : '%d' % rows_length}
#stop or not stop
if best_gain > 0:
tubemales
trueBranch = buildDecisionTree(best_t[0],evaluationFunction)
falBranch = buildDecisionTree(best_t[1],evaluationFunction)
strength什么意思return Tree(col=best_value[0],value=best_value[1],trueBranch=trueBranch,falBranch=falBranch,summary=dcY)
el:
return Tree(results=calculateDiffCount(rows),summary=dcY,data=rows)
这是决策树中最关键的⼀个函数，我来简单讲解⼀下其中需要注意的实现细节。
for col in range(column_length-1):
这个循环是选取X中的⼀个特征，假设X是花的数据集，花的特征是：花瓣⾼度，花瓣宽度，花颜⾊。
则这个循环就是循环选取花瓣⾼度，花瓣宽度，花颜⾊。
col_value_t = t([x[col] for x in rows])
例如花瓣⾼度（x[col]）为['15', '11', '12', '12', '11']，则返回的是['15', '11', '12']
for value in col_value_t
环太平洋插曲
这个循环就是遍历上⾯得到的['15','11','12']
通过上述三个步骤遍历整个数据集的所有特征值，进⾏切分，以得到最优的gain值。
最后当得到best_gain时就继续递归调⽤buildDecisionTree()以⽣成整个决策树，当best_gain = 0 时说明已经不能再切分了，这时候停⽌就得到了决策树。
2.5 prune()
def prune(tree,miniGain,evaluationFunction=gini):
#剪枝, when gain < mini Gain，合并(merge the trueBranch and the falBranch)
sults == None:ueBranch,miniGain,evaluationFunction)
if sults == None:prune(tree.falBranch,miniGain,evaluationFunction)
sults != None and sults != None:
len1 = ueBranch.data)
ibflen2 = len(tree.falBranch.data)
len3 = ueBranch.data + tree.falBranch.data)
p = float(len1)/(len1 + len2)
gain = ueBranch.data + tree.falBranch.data) - p * ueBranch.data) - (1 -p) * evaluationFunction(tree.falBranch.data)
if(gain < miniGain):
tree.data = ueBranch.data + tree.falBranch.data
tree.falBranch = None
建树后剪枝，是⼀个正则化的过程，当节点的gain⼩于给定的 mini Gain时则合并这两个节点
2.6 loadCSV()，plot()，dotgraph()
虚拟语气练习
这三个函数负责读取数据，与画出树的形状，与算法本⾝没有很⼤的关系。
这是画出后树的形状：
3. 源码地址：
下⾯我会附上源码的地址，⼤家可以直接运⾏就可以看到效果了
此⽂章为记录⾃⼰⼀路的学习路程，也希望能给⼴⼤初学者们⼀点点帮助，如有错误，疑惑欢迎⼀起交流。
