Python编程实现基于基尼指数进⾏划分选择的决策树（CART
决策树）算法
本⽂是周志华⽼师的《机器学习》⼀书中第4章 决策树 的课后题第4.4题的实现。原题是：
孙广信试编程实现基于基尼指数进⾏划分选择的决策树算法，为表4.2中的数据⽣成预剪枝、后剪枝决策树，并与未剪枝决策树进⾏⽐较。
本⽂主要是不进⾏剪枝的CART决策树的实现，预剪枝与后剪枝的CART决策树实现分别可见和。如果发现⽂章中的任何问题，欢迎通过进⾏交流。
与ID3算法选择信息增益作为选择最优属性的标准不同，CART决策树选择使划分后基尼指数（Gini index）最⼩的属性作为最优划分属性。假设当前样本集合中第类样本所占的⽐例为，则的纯度可以⽤基尼值来度量：
反映了从数据集中随机抽取两个样本，这两个样本不属于同⼀类的概率，因此越⼩，则数据集的纯度越⾼。jibe
假定离散的属性有个可能的取值，若使⽤来对样本集来进⾏划分，则会产⽣个分⽀结点，其中第个分⽀结点包含了中所有在属性上取值为的样本，记为，则属性的基尼指数定义为
如果数据集中有取值范围是连续数值的属性，我们仍然需要使⽤⼆分法来寻找最佳的分隔点。
西⽠数据集2.0的可⽤版本如下所⽰
def watermelon2():
train_data = [一点通教学网
['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'],
['乌⿊', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '是'],
['乌⿊', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'],
['青绿', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '是'],
['乌⿊', '稍蜷', '浊响', '稍糊', '稍凹', '软粘', '是'],
['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', '否'],
['浅⽩', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑', '否'],
['乌⿊', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '否'],
['浅⽩', '蜷缩', '浊响', '模糊', '平坦', '硬滑', '否'],
['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', '否']
]
test_data = [
['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '是'],
['浅⽩', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'],
['乌⿊', '稍蜷', '浊响', '清晰', '稍凹', '硬滑', '是'],
样本容量是什么['乌⿊', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑', '否'],
['浅⽩', '硬挺', '清脆', '模糊', '平坦', '硬滑', '否'],
['浅⽩', '蜷缩', '浊响', '模糊', '平坦', '软粘', '否'],
['青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑', '否'],
]
labels = ['⾊泽', '根蒂', '敲声', '纹理', '脐部', '触感']
return train_data, test_data, labels
我在实现CART决策树的时候，使⽤了和之前中相同的决策树结点结构TreeNode:
class TreeNode:
"""
决策树结点类
"""
current_index = 0
def __init__(lf, parent=None, attr_name=None, children=None, judge=None, split=None, data_index=None, attr_value=None, rest_attribute=None):
"""
决策树结点类初始化⽅法烹调和烹饪的区别
:param parent: ⽗节点
"""
lf.parent = parent # ⽗节点，根节点的⽗节点为 None
lf.attribute_name = attr_name # 本节点上进⾏划分的属性名
lf.attribute_value = attr_value # 本节点上划分属性的值，是与⽗节点的划分属性名相对应的
lf.children = children # 孩⼦结点列表
lf.judge = judge # 如果是叶⼦结点，需要给出判断
lf.split = split # 如果是使⽤连续属性进⾏划分，需要给出分割点
lf.data_index = data_index # 对应训练数据集的训练索引号
lf.index = TreeNode.current_index # 当前结点的索引号，⽅便输出时查看
TreeNode.current_index += 1
def to_string(lf):
"""⽤⼀个字符串来描述当前结点信息"""
this_string = 'current index : ' + str(lf.index) + ";\n"
if not (lf.parent is None):
parent_node = lf.parent
this_string = this_string + 'parent index : ' + str(parent_node.index) + ";\n"
this_string = this_string + str(parent_node.attribute_name) + " : " + str(lf.attribute_value) + ";\n"
this_string = this_string + "data : " + str(lf.data_index) + ";\n"
if not(lf.children is None):
this_string = this_string + 'lect attribute is : ' + str(lf.attribute_name) + ";\n"
child_list = []
for child in lf.children:
child_list.append(child.index)
this_string = this_string + 'children : ' + str(child_list)
if not (lf.judge is None):
this_string = this_string + 'label : ' + lf.judge
return this_string
以下是不进⾏剪枝的CART决策树的主要实现代码cart.py：
# CART决策树，使⽤基尼指数（Gini index）来选择划分属性
# 分别实现预剪枝、后剪枝和不进⾏剪枝的实现
import math
from Ch04DecisionTree import TreeNode
from Ch04DecisionTree import Datat
def is_number(s):
"""判断⼀个字符串是否为数字，如果是数字，我们认为这个属性的值是连续的"""
try:
float(s)
return True
except ValueError:
pass
return Fal
def gini(labels=[]):
"""
"""
计算数据集的基尼值
:param labels: 数据集的类别标签
:return:
"""
data_count = {}
for label in labels:康乐里小学
if data_count.__contains__(label):
data_count[label] += 1
el:
data_count[label] = 1
n = len(labels)
if n == 0:
return 0
gini_value = 1
for key, value in data_count.items():
gini_value = gini_value - (value/n)*(value/n)
return gini_value
def gini_index_basic(n, attr_labels={}):
gini_value = 0
for attribute, labels in attr_labels.items():
gini_value = gini_value + len(labels) / n * gini(labels)
return gini_value
def gini_index(attributes=[], labels=[], is_value=Fal):
"""
计算⼀个属性的基尼指数
:param attributes: 当前数据在该属性上的属性值列表
:param labels:
:param is_value:
:return:
"""
n = len(labels)
attr_labels = {}
gini_value = 0 # 最终要返回的结果
split = None #
if is_value: # 属性值是连续的数值
sorted_attributes = py()
海鸥图片sorted_attributes.sort()
split_points = []
for i in range(0, n-1):
split_points.append((sorted_attributes[i+1]+sorted_attributes[i])/2)
split_evaluation = []
for current_split in split_points:
low_labels = []
up_labels = []
for i in range(0, n):
if attributes[i] <= current_split:
low_labels.append(labels[i])
survivedel:
up_labels.append(labels[i])
attr_labels = {'small': low_labels, 'large': up_labels}
split_evaluation.append(gini_index_basic(n, attr_labels=attr_labels))
gini_value = min(split_evaluation)
split = split_points[split_evaluation.index(gini_value)]
el: # 属性值是离散的词
for i in range(0, n):
if attr_labels.__contains__(attributes[i]):
temp_list = attr_labels[attributes[i]]
temp_list.append(labels[i])
el:
temp_list = []
temp_list.append(labels[i])
attr_labels[attributes[i]] = temp_list
gini_value = gini_index_basic(n, attr_labels=attr_labels)
return gini_value, split
def finish_node(current_node=TreeNode.TreeNode(), data=[], label=[]):
"""
完成⼀个结点上的计算
:param current_node: 当前计算的结点
:param data: 数据集
:param label: 数据集的 label
:return:
"""
n = len(label)
# 判断当前结点中的数据是否属于同⼀类
one_class = True
this_data_index = current_node.data_index
for i in this_data_index:
for j in this_data_index:
if label[i] != label[j]:
one_class = Fal
break
if not one_class:
break
if one_class:
current_node.judge = label[this_data_index[0]]
return
rest_title = st_attribute # 候选属性
if len(rest_title) == 0: # 如果候选属性为空，则是个叶⼦结点。需要选择最多的那个类作为该结点的类
label_count = {}
temp_data = current_node.data_index
for index in temp_data:
if label_count.__contains__(label[index]):
label_count[label[index]] += 1
el:
label_count[label[index]] = 1
final_label = max(label_count)
current_node.judge = final_label
return
title_gini = {} # 记录每个属性的基尼指数
title_split_value = {} # 记录每个属性的分隔值，如果是连续属性则为分隔值，如果是离散属性则为None
for title in rest_title:
attr_values = []
current_label = []
for index in current_node.data_index:
this_data = data[index]
attr_values.append(this_data[title])
current_label.append(label[index])
temp_data = data[0]
this_gain, this_split_value = gini_index(attr_values, current_label, is_number(temp_data[title])) # 如果属性值为数字，则认为是连续的 title_gini[title] = this_gain
