Visualize-ML

树：图论中的特殊结构

树是图论中一种特殊的无向图，它没有闭合回路。树的任意两个节点之间都有唯一的路径。一棵有n个节点的树，恰好有n-1条边。

树在计算机科学、数据科学和机器学习中有广泛应用：从文件系统的目录结构、到决策树分类算法、再到层次聚类的树形图。

✦

22.1

树的基本性质

连通性、无环性、唯一路径性

树是一种特殊的无向图，具有三个关键性质：连通性（任意两节点间存在路径）、无环性（不存在回路）、唯一路径性（任意两节点间有唯一简单路径）。

🌲 树的性质

边数

n个节点的树有n-1条边

连通性

删除任意一条边，图不再连通

无环性

添加任意一条边，图产生环

📂 树的应用

• 文件系统：目录树结构

• 组织架构：层级关系

• 路由网络：最短路径树

• 生物分类：物种进化树

• 数据结构：二叉搜索树、堆

🎯 树的类型

• 二叉树：每节点最多2个子节点

• 完全树：所有节点度数相同

• 生成树：包含所有节点的子树

• 最小生成树：权重和最小

• 搜索树：有序二叉树

✦

22.2

最近共同祖先（LCA）

寻找两节点的最低共同祖先

最近共同祖先（Lowest Common Ancestor, LCA）是指在树中，两个节点向上移动直到找到的最小公共祖先节点。 LCA在家谱分析、文件系统路径查找等场景中有重要应用。

🔍 LCA定义

寻找路径

对于节点a和b：
1. 从a向根节点追溯
2. 从b向根节点追溯
3. 找到第一个公共节点c
4. c即为LCA(a, b)

时间复杂度：O(h)，h为树高

💡 应用场景

• 家谱分析：认祖归宗

• 文件系统：确定共同祖先目录

• 版本控制：Git分支合并点

• 生物信息：物种进化共同祖先

• 组织架构：最小共同上级

✦

22.3

最小生成树

权重和最小的生成树

最小生成树（Minimum Spanning Tree, MST）是连通图中边权重和最小的生成树。经典算法包括Kruskal算法（贪心选择最小边）和Prim算法（从节点扩展）。

🌉 实际应用：网络设计

通信网络

以最小成本连接所有节点，确保网络连通性和经济性

电路设计

最小化连接元件的总线长度或电阻

交通规划

以最小总成本建设连接所有区域的道路网络

✦

22.4

决策树

基于树结构的分类算法

决策树（Decision Tree）是一种常用的分类算法。它通过递归二分法，根据特征值将数据划分到不同区域。每个内部节点代表一个判断条件，每个叶节点代表一个分类结果。

🔑 关键问题

1. 特征选择

每个节点选择哪个特征进行分割？
通过信息增益、基尼系数等指标

2. 阈值确定

对于连续特征，如何找到最佳分割点？
穷举搜索或启发式方法

3. 停止条件

何时停止分裂？如何防止过拟合？
最大深度、最小样本数、剪枝

🌲 决策树家族

CART

分类与回归树，使用基尼指数

ID3 / C4.5

使用信息增益（比）作为分割标准

集成方法

随机森林、GBDT、XGBoost等

✦

22.5

层次聚类与树形图

自下而上构建聚类层次结构

层次聚类（Hierarchical Clustering）通过计算数据点间的距离，自下而上逐步合并最近的簇。树形图（Dendrogram）可视化整个聚类过程，通过在不同高度切割树形图，可以得到不同数量的簇。

📊 树形图的威力

可视化层次结构

树形图横轴表示样本，纵轴表示距离/相似度。树的分支揭示了数据的多尺度聚类结构。

灵活的簇数选择

通过在不同高度切割树形图，可以得到从1到n个簇的任意聚类结果，无需预先指定簇的数量。

应用：股票聚类

通过计算股票收益率的相关系数矩阵，可以用层次聚类发现同行业、同概念的股票组。

应用：基因分类

基于基因表达数据的相似性，层次聚类可以揭示基因的功能分组和调控网络。

✦

本章小结

本章介绍了图论中的特殊结构——树，以及树在算法和机器学习中的重要应用。树的三个关键性质（连通、无环、唯一路径）使其成为组织层次化数据的理想结构。

🌳 树的性质与应用

基本性质

n个节点，n-1条边；连通、无环、唯一路径

🤖 机器学习中的树

决策树

分类算法，递归二分法构建决策规则

层次聚类

自下而上合并，树形图可视化

集成方法

随机森林、GBDT、XGBoost

✨ 树：连接图论与机器学习的桥梁 ✨

从图的结构性质到算法应用

图论视角

连通、无环、唯一路径

算法视角

最优化、搜索、遍历

ML视角

分类、聚类、特征提取