1 堆（Heap）

堆是一种特殊的树形数据结构，通常用于实现优先队列。

import heapq

# 创建堆
my_heap = [1, 3, 5, 7, 9]
heapq.heapify(my_heap)

# 添加元素
heapq.heappush(my_heap, 2)

# 弹出最小元素
min_element = heapq.heappop(my_heap)

2 队列（Queue）

队列是一种先进先出（FIFO）的数据结构，常用于任务调度等场景。

from queue import Queue

# 创建队列
my_queue = Queue()

# 入队
my_queue.put(1)
my_queue.put(2)

# 出队
first_element = my_queue.get()

3 栈（Stack）

栈是一种后进先出（LIFO）的数据结构，通常用于递归、表达式求值等场景。

# 创建栈
my_stack = []

# 入栈
my_stack.append(1)
my_stack.append(2)

# 出栈
top_element = my_stack.pop()

4 链表（Linked List）

链表是一种线性数据结构，由节点组成，每个节点包含数据和指向下一个节点的引用。链表可以分为单向链表和双向链表。

# 单向链表节点
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# 创建链表
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)

node1.next = node2
node2.next = node3

5 树（Tree）

树是一种层级结构的数据结构，由节点组成，每个节点可以有零个或多个子节点。

# 二叉树节点
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# 创建二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

6 图（Graph）

图是由节点和边组成的数据结构，节点表示实体，边表示节点之间的关系。图可以分为有向图和无向图。

# 有向图的表示
graph = {'A': ['B', 'C'],
         'B': ['D', 'E'],
         'C': ['F'],
         'D': [],
         'E': ['F'],
         'F': []}

7 字典树（Trie）

字典树是一种树形数据结构，用于存储动态集合或关联数组，常用于字符串检索操作。

# Trie节点
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

# 创建Trie
trie_root = TrieNode()
trie_root.children['a'] = TrieNode()
trie_root.children['a'].children['p'] = TrieNode()
trie_root.children['a'].children['p'].is_end_of_word = True

决策树算法如何工作

套用西瓜书上的一个图来说明决策树算法是如何工作的：

我们挑选西瓜时，都会考虑西瓜脐部、色泽、根蒂以及敲一敲听声音等因素（特征），决策树就是对这些考虑因素进行逐个拆解，从而判断西瓜（样本）是好瓜还是坏瓜（类别）。

从上面来看，这些特征好像都是离散型的，对于 Iris 数据集中数值特征来说，我们可以设定一个阈值，比如判断萼片宽度（sepal width）是否小于 2.5 厘米。

决策树算法从树根开始，选择能够产生最大信息增益（Information Gain，IG）的特征进行数据集拆分，一直到叶子节点为止，所有叶子节点中的样本都属于同一个类别，这样就可能会产生非常深的树，从而引发过拟合问题，所以就需要对树进行剪枝以限制树的深度（模型复杂度）。

最大化信息增益

信息增益的公式定义如下

f 是要执行拆分的特征，Dp 和 Dj 表示父节点 p 和第 j 个孩子节点中的样本集，Np 和 Nj 分别表示父节点 p 和第 j 个孩子节点中的训练样本数量。I 就表示节点的纯度。

所以信息增益就是衡量父节点纯度和所有孩子节点纯度加权和的差异。

包括 scikit-learn 在内的大多数机器学习库的决策树算法都会将父节点分裂成左右两个孩子节点，所以信息增益公式可以简化为：

三种纯度衡量指标

现在有 Gini 纯度、熵和分类错误三种节点纯度衡量指标。

首先我们看一下熵（entropy）：

p(i|t) 表示节点 t 中属于类别 i 的样本占该节点中所有样本的比例。如果节点 t 中所有样本都属于同一个类别，那么熵就是 0，表示这个节点没有不确定性；如果节点 t 中的每个样本都分属于不同的类别，那么此时熵最大，表示这个节点的不确定性最大。

Gini 纯度可以看作是最小化误分类概率的指标：

在实际应用中，Gini 纯度和熵表现很类似，所以不建议花很多精力去比较在选择哪种纯度衡量指标。相反更应集中精力实验不同决策树剪枝技巧。

最后一个就是分类错误：

这个指标适合用来做决策树剪枝，但是由于它对于节点中类别概率分布不敏感，所以它不适合用来生成决策树。

生成决策树

我们现在使用 scikit-learn 提供的 DecisionTreeClassifier 构建一个深度为 4，采样 Gnini 纯度的分类决策树，还是使用 Iris 数据集。

决策树算法不要求特征缩放。

可以看到这些决策边界几乎和坐标轴平行。

我们可以可视化生成的决策树，从而也能对模型的预测结果做出解释。

树分支的左孩子表示满足父节点中的判断条件，右孩子表示不满足条件。