机器学习工程师和数据科学家必须了解的5种数据结构（二）
机器学习中的应用
决策树：
决策树在机器学习中广泛用于分类和回归任务。它们是更复杂的集成方法（如随机森林和梯度提升机）的基础。
- 分类：在分类任务中，决策树根据输入特征的值将数据集划分为多个分支，力图在每次划分时尽可能地将类别区分开。
- 回归：在回归任务中，决策树通过划分数据集以最小化每个节点内目标变量的方差。
数学表示法：
对于二叉决策树，决策过程可以表示为：
from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier
from sklearn import tree
import matplotlib.pyplot as plt
# Load example dataset
iris = load_iris()
X, y = iris.data, iris.target
# Train a decision tree classifier
clf = DecisionTreeClassifier(criterion='gini', max_depth=3)
clf.fit(X, y)
# Visualize the decision tree
plt.figure(figsize=(12,8))
tree.plot_tree(clf, filled=True, feature_names=iris.feature_names, class_names=iris.target_names)
plt.show()
该决策树模型在Iris数据集上训练，展示了基于花瓣宽度和长度对Iris种类进行分类。该树使用基尼不纯度来确定划分点，展示了Setosa、Versicolor和Virginica类别的明显区分。
在这个例子中，我们使用Iris数据集构建一个最大深度为3的决策树分类器。树是可视化的，显示每个节点的分裂和分类决策。
kd树：
kd树用于组织k维空间中的点，使得空间搜索更加高效，例如查找某个点的最近邻点。kd树通过选择一个维度和一个值来划分数据，将空间递归地划分为两个部分，从而创建二叉树结构。
数学表示法：
对于一组位于k维空间中的点{x₁, x₂, …, xₙ}，kd树的构建过程如下：
- 选择一个维度d来划分数据。
- 选择沿维度d的中值m，将点分为两组：一组点小于或等于m，另一组大于m。
- 对每个子集递归应用相同的过程。
from sklearn.neighbors import KDTree
import numpy as np
# Create a dataset of 2D points
points = np.array([
[2, 3],
[5, 4],
[9, 6],
[4, 7],
[8, 1],
[7, 2]
])
# Build a kd-tree
kd_tree = KDTree(points, leaf_size=2)
# Query the kd-tree for the nearest neighbor of a given point
query_point = np.array([[9, 2]])
dist, ind = kd_tree.query(query_point, k=1)
print(f"Nearest neighbor of {query_point} is {points[ind]} with distance {dist}")
Nearest neighbor of [[9 2]] is [[[8 1]]] with distance [[1.41421356]]在此示例中，kd树通过搜索k维空间，快速找到查询点[9, 2]的最近邻。
效率考量
1.树的构建与遍历的时间复杂度：
- 二叉树：对于平衡数据，构建二叉树的时间复杂度通常为O(n log n)，其中n为元素数量。遍历（中序、先序、后序）操作的时间复杂度为O(n)。
- 决策树：构建决策树通常涉及递归划分数据，对于平衡的树，时间复杂度为O(n log n)。然而在最坏的情况下，树不平衡时时间复杂度可能达到O(n²)。
- kd树：构建kd树的时间复杂度为O(n log n)，每次最近邻查询的平均时间复杂度为O(log n)。然而，对于高维数据，kd树的效率会降低。
2.平衡性与深度的考虑以获得最佳性能：
- 树的平衡性：平衡树的两侧节点数量大致相等。平衡树能够确保插入、删除和查找操作具有最低的时间复杂度。相反，不平衡的树（类似于链表）可能导致性能下降，操作时间复杂度增至O(n)。
- 树的深度：树的深度影响其性能。浅树（深度较小）遍历速度更快，但可能需要更复杂的逻辑来实现划分。深树则可能需要更少的复杂决策，但计算成本较高。
- 剪枝：在决策树中，剪枝技术用于移除不必要的节点，减少树的深度，防止过拟合。
from sklearn.tree import DecisionTreeClassifier
# Train a decision tree classifier with overfitting
clf = DecisionTreeClassifier(criterion='gini', max_depth=None)
clf.fit(X, y)
# Prune the tree by limiting its maximum depth
pruned_clf = DecisionTreeClassifier(criterion='gini', max_depth=3)
pruned_clf.fit(X, y)
# Compare the performance of the pruned vs. unpruned tree
print(f"Unpruned tree depth: {clf.get_depth()}")
print(f"Pruned tree depth: {pruned_clf.get_depth()}")
Unpruned tree depth: 5
Pruned tree depth: 3剪枝有助于减少决策树的复杂性，提升其在未见数据上的泛化性能。
总之，树是一种功能强大的数据结构，在机器学习中的应用广泛，从使用决策树进行分类和回归任务到使用kd树进行高效的空间搜索。理解树的构建、遍历及其性能影响，对于构建有效的机器学习模型至关重要。
图
图是一种数据结构，由一组节点（也称为顶点）和连接成对节点的边组成。节点表示实体，边则表示它们之间的关系或连接。图的灵活性极高，可以用于建模多种系统，例如社交网络、生物网络和通信网络。
图的组成部分：
- 节点（顶点）：表示图中的实体或对象。例如，在社交网络中，每个节点可以代表一个人。
- 边：表示节点之间的连接或关系。在社交网络中，边可能代表好友关系或关注关系。
图示：图结构的可视化，展示了文中定义的顶点和边。
图的类型
无向图：在无向图中，边没有方向性，这意味着关系是双向的。如果节点A连接到节点B，那么节点B也连接到节点A。
其中，V是顶点集，E是边集。
有向图（有向图）：在有向图中，边具有方向性，表示关系是单向的。如果节点A连接到节点B，这不一定意味着节点B也连接到节点A。
V是顶点集，E是有向边集（有序顶点对）。
加权图：在加权图中，边具有权重或代价。这些权重帮助表示现实世界中的场景，例如距离、时间或容量。
W是一个为E中的每条边分配权重的函数。
机器学习中的应用
在机器学习中，图变得越来越重要，尤其是当数据自然地以图结构呈现时。以下是一些关键应用：
1.图神经网络（GNN）
图神经网络（GNN）是一类专门处理图结构数据的神经网络。它们将传统神经网络的概念扩展到图上，使其能够学习节点、边以及整个图的表示。这在处理实体之间关系与实体本身同等重要的任务时尤为有用。
GNN通常通过迭代聚合并转换来自节点邻居的信息来更新节点的表示。例如，给定一个节点v及其邻居N(v)，GNN将如下更新节点v的表示：
GNN的应用：
- 社交网络分析：预测用户行为或检测社交网络中的社区。
- 推荐系统：通过分析用户与物品之间的关系推荐产品或内容。
- 分子图分析：在化学和生物学中，通过将分子视为图（原子为节点，键为边）来预测分子的性质。
2.表示社交网络、推荐系统和生物网络中的关系
自然适合表示各种领域中的复杂关系：
- 社交网络：节点表示用户，边表示好友关系或互动。图可用于发现社区、重要用户或预测未来的连接。
- 推荐系统：节点表示用户和物品，边表示交互（如购买或评分）。通过分析相似用户或物品，图可以推荐新物品给用户。
- 生物网络：在生物学中，图可以表示分子结构（节点为原子，边为键）、蛋白质-蛋白质相互作用网络或基因调控网络。
示例：使用图进行社交网络中的社区检测
社区检测是识别图中内部连接更为紧密的节点组的过程。通常用于社交网络中，发现具有相似兴趣或互动的群体。
实现示例：
from sklearn.tree import DecisionTreeClassifier
# Train a decision tree classifier with overfitting
clf = DecisionTreeClassifier(criterion='gini', max_depth=None)
clf.fit(X, y)
# Prune the tree by limiting its maximum depth
pruned_clf = DecisionTreeClassifier(criterion='gini', max_depth=3)
pruned_clf.fit(X, y)
# Compare the performance of the pruned vs. unpruned tree
print(f"Unpruned tree depth: {clf.get_depth()}")
print(f"Pruned tree depth: {pruned_clf.get_depth()}")
Unpruned tree depth: 5
Pruned tree depth: 3
输出显示了Karate Club图，节点根据算法检测出的社区被着色。
效率考量
图遍历算法的时间复杂度，如DFS和BFS
- 深度优先搜索（DFS）：DFS是一种遍历或搜索图的算法，它从根节点开始，尽可能深入探索每个分支，然后回溯。DFS的时间复杂度为O(V + E)，其中V是顶点数，E是边数。
- 广度优先搜索（BFS）：BFS从根节点开始，优先探索当前深度的所有邻居，然后再探索下一层深度的节点。与DFS一样，BFS的时间复杂度也是O(V + E)。
import sys
import numpy as np
from scipy.sparse import csr_matrix
# Example graph represented as an adjacency matrix (dense)
adj_matrix = np.array([
[0, 1, 1, 0],
[1, 0, 1, 1],
[1, 1, 0, 1],
[0, 1, 1, 0]
])
# Convert dense matrix to sparse representation
sparse_matrix = csr_matrix(adj_matrix)
print(f"\nDense matrix representation:\n{adj_matrix}\nSize: {sys.getsizeof(adj_matrix)}")
print(f"\nSparse matrix representation:\n{sparse_matrix}\nSize: {sys.getsizeof(sparse_matrix)}")
Dense matrix representation:
[[0 1 1 0]
[1 0 1 1]
[1 1 0 1]
[0 1 1 0]]
Size: 256
Sparse matrix representation:
(0, 1) 1
(0, 2) 1
(1, 0) 1
(1, 2) 1
(1, 3) 1
(2, 0) 1
(2, 1) 1
(2, 3) 1
(3, 1) 1
(3, 2) 1
Size: 562.大型图与稀疏表示的内存管理
图可能非常庞大，尤其是在表示现实世界系统（如社交或生物网络）时。高效的内存管理在这种情况下至关重要。
- 邻接表：邻接表是一种更节省内存的图表示方式，特别适用于稀疏图（即与节点数量相比，边数量较少的图）。它使用一个列表数组，其中每个列表包含与该节点相邻的节点。
- 内存使用量：邻接表的内存使用量为O(V + E)，其中V是顶点数，E是边数。
- 邻接矩阵：邻接矩阵使用一个二维数组表示图，其中位置(i, j)处的元素为1表示节点i和节点j之间有边，0表示没有边。
- 内存使用量：邻接矩阵的内存使用量为O(V²)，更适合边数接近V²的密集图。
import sys
import numpy as np
from scipy.sparse import csr_matrix
# Example graph represented as an adjacency matrix (dense)
adj_matrix = np.array([
[0, 1, 1, 0],
[1, 0, 1, 1],
[1, 1, 0, 1],
[0, 1, 1, 0]
])
# Convert dense matrix to sparse representation
sparse_matrix = csr_matrix(adj_matrix)
print(f"\nDense matrix representation:\n{adj_matrix}\nSize: {sys.getsizeof(adj_matrix)}")
print(f"\nSparse matrix representation:\n{sparse_matrix}\nSize: {sys.getsizeof(sparse_matrix)}")
Dense matrix representation:
[[0 1 1 0]
[1 0 1 1]
[1 1 0 1]
[0 1 1 0]]
Size: 256
Sparse matrix representation:
(0, 1) 1
(0, 2) 1
(1, 0) 1
(1, 2) 1
(1, 3) 1
(2, 0) 1
(2, 1) 1
(2, 3) 1
(3, 1) 1
(3, 2) 1
Size: 56在此示例中，稀疏矩阵表示显著减少了内存使用，尤其是对于具有较少边的大型图。
图是机器学习中的一种强大数据结构，尤其适用于建模复杂关系。从社交网络分析到分子结构预测，图的应用范围广泛。各种算法可用于高效地遍历和管理大规模图数据。理解这些操作的时间和空间复杂度对于优化基于图的机器学习任务至关重要。
结论
我们探讨了几种基础的数据结构——数组和矩阵、堆、哈希表、树和图——以及它们在机器学习中的关键作用。每种数据结构都有其独特的优势，适用于特定类型的任务：
- 数组和矩阵 是数据表示的基础，尤其在处理数值数据时尤为重要。它们支持高效的数学运算，这是许多机器学习算法的基础。
- 堆 高效管理优先队列，优化像最近邻搜索这样的过程，这在聚类和路径规划算法中至关重要。
- 哈希表 在快速数据检索方面表现出色，使其在处理大规模数据集、实现推荐系统以及确保信息快速访问方面不可或缺。
- 树结构（如二叉树、决策树和kd树）在分类、回归以及高效的空间搜索任务中起着重要作用，并构成了许多机器学习模型的核心。
- 图结构 使得对数据中复杂关系的建模和分析成为可能，支持许多任务（如社交网络分析、推荐系统和生物网络预测）。图神经网络（GNN）提供了在图结构数据上进行学习的前沿技术。
通过理解这些数据结构，你可以更明智地决策如何高效地存储、访问和处理数据，从而开发出更有效且可扩展的机器学习解决方案。
最后的思考
为你的机器学习任务选择合适的数据结构可以显著提升时间和内存的使用效率。这些结构不仅是抽象的概念，更是实用的工具。当你正确使用它们时，能够大幅提升机器学习模型的性能。
在构建和优化机器学习模型时，尝试使用不同的数据结构。深入研究它们的实现，权衡它们的优缺点，理解它们如何影响你的解决方案的效率和可扩展性。
感谢阅读！你还可以订阅我们的YouTube频道，观看大量大数据行业相关公开课：https://www.youtube.com/channel/UCa8NLpvi70mHVsW4J_x9OeQ；在LinkedIn上关注我们，扩展你的人际网络！https://www.linkedin.com/company/dataapplab/。
原文作者：Joseph Robinson, Ph.D.
翻译作者：过儿
美工编辑：过儿
校对审稿：Jason
原文链接：https://pub.towardsai.net/data-structures-in-machine-learning-a-comprehensive-guide-to-efficiency-and-scalability-f7429919c9c5
