数组、堆、哈希表、树和图——理论观点和实用工具——使模型运行得更快、花费更少的内存并处理更繁芜的任务。
本博客涵盖了基本的数据构造，揭示了它们在各种 ML 运用中的关键浸染以及它们如何提升您的建模能力。
数组和矩阵这里，我们简要概述了必备数学知识。
定义和概述数组和矩阵是打算机科学和机器学习中最基本的数据构造之一。
数组是存储在连续内存块中的元素凑集，常日属于同一数据类型。数组是索引的，这意味着可以利用其索引（即数组中的位置）访问每个项目。
矩阵是一种二维数组，按行和列组织数据。矩阵对付在机器学习中表示数据至关主要，尤其是在处理表格数据、图像或多维数据时。数组表示单个向量（即 1D 数据），而矩阵表示更繁芜的关系（2D 数据），这使得它们在各种用例中都非常有用。
数学符号：具有m行和n列的矩阵A可以表示为：
机器学习中的运用
1.数据表示（特色向量，图像）：
特色向量。在机器学习中，我们常常将数据表示为向量。例如，我们可以将具有n 个特色（变量）的数据集描述为 n 维向量：
每个 xᵢ 都是一个特色值。
Python 中索引的大小为N的特色向量的示例视图（见下图）。
大小为N的数组（或特色向量）。请把稳，在 Python 中，索引从 0 开始，负索引从列表末端计数到开头（作者创建的图像）。
给定m 个样本向量，我们将它们组合成大小为m × n的矩阵X，个中每一行代表一个样本。
图像。在打算机视觉中，我们常常将图像表示为矩阵，个中每个条款对应一个像素值。对付灰度图像，每个元素都是一个强度值。同时，我们可以用三个值（例如 RGB 值，如下图所示）的向量来表示彩色照片的像素。
彩色图像为N x M x 3 数组。图像由作者创建。
我们可以按如下办法表示大小为 28x28 的灰度图像。
2.线性代数中的矩阵运算：
矩阵也是机器学习中许多运算的核心，特殊是线性代数，它是该领域大部分内容的根本。
矩阵乘法。最常见的运算之一是矩阵乘法。
给定A（一个m × n矩阵）和B（一个n × p矩阵），它们的乘积C是一个m × p矩阵：
此操作在神经网络中至关主要，我们将权重和输入数据表示为矩阵，它们的乘积是层操作的根本。
线性回归示例。在线性回归中，目标是找到一个系数β向量，使预测值和目标值之间的差异最小化。我们可以用以下办法表示该模型：
为了估计β，我们利用正态方程。
Python 实现示例。
这些系数分别对应于特色的截距和斜率。
import numpy as np# Example datasetX = np.array([[1, 1], [1, 2], [2, 2], [2, 3]]) # Feature matrixy = np.dot(X, np.array([1, 2])) + 3 # Target vector# Add a column of ones to X to account for the intercept termX = np.hstack([np.ones((X.shape[0], 1)), X])# Calculate beta using the normal equationbeta = np.linalg.inv(X.T @ X) @ X.T @ yprint("Estimated coefficients:", beta)效率考虑
1.基本操作的韶光繁芜度：
访问：访问数组或矩阵中的元素是O（1）操作，由于我们可以通过其索引直接访问每个组件。
遍历：遍历数组或矩阵的所有元素，对付一维数组，运算繁芜度为O ( n )，而对付m行n列的矩阵，运算繁芜度为O ( m × n ) 。
矩阵乘法：两个矩阵相乘的韶光繁芜度为O ( m × n × p )，个中第一个矩阵大小为m × n，第二个矩阵大小为 n×pn \times pn×p。
2. 内存利用和潜在的优化：
内存利用情形：数组和矩阵会花费大量内存，尤其是在处理大数据或高维数据时。例如，10,000 × 10,000 的矩阵将须要 1 亿个条款，根据数据类型的不同，这个数字可能会很大。
优化内存利用情形：
稀疏矩阵：如果矩阵包含许多零（稀疏矩阵），则仅存储非零元素更节省内存。Python 库scipy.sparse供应了处理稀疏矩阵的方法。
from scipy.sparse import csr_matrix# Create a sparse matrixdense_matrix = np.array([[0, 0, 3], [4, 0, 0], [0, 2, 0]])sparse_matrix = csr_matrix(dense_matrix)print(sparse_matrix)
批处理：分批实行操作而不是同时对全体数据集实行操作可以减少大规模数据的内存负载和打算韶光。
数据类型优化：选择得当的数据类型（例如，利用float32而不是float64）可以减少内存占用，同时为许多运用程序保持足够的精度。
总之，数组和矩阵是机器学习中数据表示和操作的支柱。理解它们的运用、操作和效率考虑对付开拓有效且可扩展的机器学习模型至关主要。
堆定义和概述堆是一种分外的基于树的数据构造，知足堆属性。在最大堆中，对付任何给定节点i ， i的值大于或即是其子节点的值。相反，在最小堆中，i 的值小于或即是其子节点的值。此属性确保根节点始终包含最大（最大堆）或最小（最小堆）元素，使堆非常适宜实现优先级行列步队。
我们常日将堆实现为二叉树，个中每个父节点最多有两个子节点。我们常常用数组表示堆的构造，这样我们就可以很随意马虎地利用索引上的大略算法来导航父子关系。
最大堆性子：对付最大堆，每个节点的值都大于或即是其子节点的值：
最小堆性子：对付最小堆，每个节点的值小于或即是其子节点的值：
机器学习中的运用
类似 A 搜索的算法中的优先级行列步队：
在 AI 方案和路径查找算法（例如A ）中，堆用于高效地实现优先级行列步队。优先级行列步队按优先级对元素进行排序，许可算法不断扩展最有希望的节点。常日利用最小堆，个中本钱最低的节点位于根部并且可以不断访问。
示例：利用最小堆进行A
import heapq# Example graph (as an adjacency list)graph = { 'A': [('B', 1), ('C', 4)], 'B': [('A', 1), ('C', 2), ('D', 5)], 'C': [('A', 4), ('B', 2), ('D', 1)], 'D': [('B', 5), ('C', 1)]}# A search functiondef a_star(graph, start, goal, h): # Priority queue, initialized with the start node pq = [(0 + h(start), 0, start, [])] # (f = g + h, g, node, path) heapq.heapify(pq) while pq: (f, g, current, path) = heapq.heappop(pq) # Path to the current node path = path + [current] if current == goal: return path, f # Return the found path and its total cost for (neighbor, cost) in graph[current]: heapq.heappush(pq, (g + cost + h(neighbor), g + cost, neighbor, path)) return None # If no path is found# Heuristic function (for simplicity, using zero heuristic as an example)def h(node): return 0# Find path from A to Dpath, cost = a_star(graph, 'A', 'D', h)print("Path:", path, "Cost:", cost)
在本例中，最小堆存储了A搜索算法中节点的各自本钱（优先级）。堆确保首先扩展本钱最低的节点，从而优化搜索过程。
2. 聚类算法（例如K-means）中大型数据集的有效管理：
堆还可用于聚类算法（如 K-means），以便在迭代过程中高效管理和更新质心。在管理大量数据点时，堆有助于优化质心的选择和更新，尤其是在确定离数据点最近的质心时。
示例：利用堆进行 K-means 初始化 (K-means++)
K-means++ 是一种初始化技能，用于选择初始质心以加快收敛速率。堆可以有效地管理点到其最近质心的间隔。
import numpy as npdef initialize_centroids(X, k): centroids = [] centroids.append(X[np.random.randint(X.shape[0])]) for _ in range(1, k): distances = np.array([min([np.linalg.norm(x - c) for c in centroids]) for x in X]) heap = [(dist, i) for i, dist in enumerate(distances)] heapq.heapify(heap) # Weighted random selection of the next centroid total_dist = sum(distances) r = np.random.uniform(0, total_dist) cumulative_dist = 0 for dist, i in heap: cumulative_dist += dist if cumulative_dist >= r: centroids.append(X[i]) break return np.array(centroids)# Example datasetX = np.array([[1, 2], [1, 4], [3, 2], [5, 6], [7, 8], [9, 10]])centroids = initialize_centroids(X, 2)print("Initial centroids:\n", centroids)
这里，我们在 k-means++ 中初始化质心时利用堆来管理数据点与其最近质心之间的间隔。这确保选择质心以最大化它们之间的最小间隔，从而得到更好的聚类结果。
效率考虑1.插入和删除操作的对数韶光繁芜度：
插入：将元素插入堆具有O（log n）的韶光繁芜度，由于它可能须要移动元向来坚持堆属性。删除：删除根元素（最大堆中的最大值或最小堆中的最小值）的韶光繁芜度也是O (log n )。删除后，我们必须重组堆以保持其属性。考虑到这些繁芜性，堆对付须要重复访问最高或最低优先级元素的场景非常高效，例如在优先级行列步队中或在机器学习中管理动态数据集时。
2.空间繁芜度：
空间效率：堆节省空间，常日利用数组实现，无需额外指针（如链接构造）。空间繁芜度为O ( n )，个中n是堆中元素的数量。我们理解到，堆是机器学习中一种强大的数据构造，尤其是在优化基于优先级的操作和管理大型数据集时。它们的插入和删除操作具有对数韶光繁芜度，因此非常适宜实时系统和大规模机器学习任务。
哈希表定义和概述哈希表是一种实现关联数组的数据构造，关联数组是一种可以将键映射到值的构造。它建立在键值对的观点之上，个中每个键都是唯一的并与特定值干系联。哈希表因其能够实行快速数据检索、插入和删除操作而广泛运用于打算领域。
哈希表的效率来自于哈希函数，它获取一个键并打算数组（常日称为哈希表）中的索引（哈希码）。然后将键值对存储在哈希码指示的数组中。当须要检索某个值时，将相同的哈希函数运用于该键，然后可以利用打算出的索引快速访问相应的值。
哈希函数：良好的哈希函数可确保：
哈希码均匀分布，最大限度地减少了多个键哈希到同一索引的机会（即冲突）。该函数是确定性的，这意味着相同的键将始终产生相同的哈希码。数学表示：给定一个键k和一个哈希函数h，索引i（键值对在哈希表中的位置）由以下公式给出：
哈希函数实际浸染的图示：不同的键（例如，名称）通过哈希函数通报以天生唯一的哈希值。当多个键映射到同一个哈希时，就会发生冲突，如“Jim Smith”和“Pete Reed”映射到哈希“01”所示，这凸显了哈希表中冲突办理议方案略的必要性。图片由作者创建。
机器学习中的运用1.实现大型数据集的高效查找：
当您须要高效地从大型数据集中检索数据时，哈希表非常方便。例如，在大量用户交互（例如点击、浏览、购买）数据集中，哈希表可以快速访问与特定用户干系的交互。
示例：高效查找。
# Example dataset: user interactions with itemsuser_interactions = { 'user1': ['item1', 'item2', 'item3'], 'user2': ['item2', 'item4'], 'user3': ['item1', 'item4', 'item5'],}# Hash table (dictionary in Python) to store interactionshash_table = {}# Insert interactions into the hash tablefor user, items in user_interactions.items(): hash_table[user] = items# Efficient lookup of a user's interactionsuser = 'user2'print(f"Items interacted with by {user}: {hash_table[user]}")
在这个例子中，哈希表许可以恒定时间检索与特定用户交互的项目，纵然数据集包含数百万个用户。
2. 局部敏感哈希（LSH）等算法中的哈希技能用于近似最近邻搜索：
局部敏感哈希 (LSH)是一种利用哈希表在高维空间中快速近似最近邻搜索的技能。当数据集太大而无法有效实行精确最近邻搜索时，这种方法非常有用。
LSH 利用哈希函数，以高概率将相似的输入项映射到同一个“存储桶”。这种映射在探求近似最近邻居时显著减少了搜索空间。
示例：Python 中的 LSH。
import numpy as npfrom sklearn.neighbors import NearestNeighborsfrom sklearn.random_projection import SparseRandomProjection# Example dataset: 2D pointspoints = np.random.rand(1000, 2)# Using random projections to approximate nearest neighborslsh = SparseRandomProjection(n_components=2)projected_points = lsh.fit_transform(points)# Using NearestNeighbors for finding approximate neighborsnbrs = NearestNeighbors(n_neighbors=3, algorithm='ball_tree').fit(projected_points)distances, indices = nbrs.kneighbors(projected_points)# Example: Finding nearest neighbors of a pointpoint_index = 0print(f"Nearest neighbors of point {point_index}: {indices[point_index]}")
在此示例中，LSH 将高维点投影到低维空间，同时保留它们之间的间隔。然后，利用类似哈希表的构造快速检索任何给定点的最近邻居。
3.在推举系统中利用哈希表：
在推举系统中，哈希表可以有效地将用户映射到他们与之交互的商品。这种技能对付处理数百万用户和商品的大型系统至关主要。
例子：
# Example hash table for user-item interactionsrecommendation_data = { 'user1': {'item1': 5, 'item2': 3, 'item3': 2}, 'user2': {'item2': 4, 'item4': 5}, 'user3': {'item1': 2, 'item4': 3, 'item5': 5},}# Efficient retrieval of items and their ratings for a specific useruser = 'user3'items = recommendation_data[user]print(f"Items and ratings for {user}: {items}")
考虑一个推举系统，它须要快速检索用户交互过的所有项目以推举类似的项目。
这里，哈希表使得推举系统能够快速访问用户已评价的项目，从而有助于天生个性化的推举。
效率考虑1.查找的均匀O (1) 韶光繁芜度：
哈希表最显著的上风之一是其查找的均匀韶光繁芜度为O (1)。这意味着，均匀而言，无论数据集的大小如何，从哈希表中检索值所需的韶光都是常数。
2. 可能发生的碰撞问题及处理策略：
当两个不同的键产生相同的哈希码并被分配到哈希表中的相同索引时，就会发生冲突。冲突会降落哈希表的性能，从而导致查找韶光增加。
可以采取多种策略来处理碰撞。
链接：在此方法中，哈希表中的每个索引都指向一个链接列表（或其他数据构造），该列表包含散列到该索引的所有键值对。如果发生冲突，我们会将新的键值对附加到该索引处的列表中。
例如：
hash_table = [[] for _ in range(10)]def hash_function(key): return key % 10def insert(hash_table, key, value): index = hash_function(key) hash_table[index].append((key, value))insert(hash_table, 15, 'value1')insert(hash_table, 25, 'value2')print(hash_table)
开放寻址：当发生冲突时，此方法会在哈希表中探求另一个开放位置。常用技能包括：
线性探测：按顺序搜索下一个可用插槽。二次探测：根据二次函数搜索插槽。双重散列：利用第二个散列函数来确定查找下一个槽的步长。例如：线性探测。
def insert_linear_probing(hash_table, key, value): index = hash_function(key) while hash_table[index] is not None: index = (index + 1) % len(hash_table) hash_table[index] = (key, value)hash_table = [None] 10insert_linear_probing(hash_table, 15, 'value1')insert_linear_probing(hash_table, 25, 'value2')print(hash_table)
哈希表对付机器学习中高效的数据检索至关主要，尤其是在处理大型数据集时。它们的均匀查找韶光繁芜度为O (1)，这使得它们在高性能运用程序中不可或缺。然而，理解和处理冲突对付在实践中保持哈希表的效率至关主要。
树（二叉树、决策树和 kd 树）定义和概述树是打算机科学中的基本数据构造，广泛运用于机器学习。树是一种分层构造，由包含值的节点和零个或多个子节点组成。树中的顶部节点称为 根，没有子节点的节点称为叶。
在机器学习中，常日利用几种类型的树，每种类型的树都有不同的用场：
二叉树：二叉树中的每个节点最多有两个子节点，即左子节点和右子节点。二叉树是决策树和二叉搜索树等更繁芜的树构造的根本。
具有七个节点的完备二叉树的直不雅观表示，展示了一种完美平衡的构造，个中每个级别都完备添补，并且所有叶节点都位于同一深度。图片由作者创建。
决策树：决策树是一种树构造，个中每个内部节点代表基于特色的决策，每个分支代表该决策的结果，每个叶节点代表类标签（在分类任务中）或连续值（在回归任务中）。
用于确定贷款资格的决策树示例。决策树评估年事、人为和子女数量等条件，以决定是否批准或谢绝贷款。图片由作者创建。
Kd-Trees： Kd-Tree（k 维树的缩写）是一种二叉树，用于组织 k 维空间中的点。因此，非叶节点充当超平面，将空间划分为两个分区。 它有利于高效的最近邻搜索，其目标是找到与给定查询点最近的点。
为大略起见，下图描述了k =2的示例。
2D KD 树及其对应树构造的图示。左图显示了点A到F在xy平面上的空间分区，右图表示 kd 树的层次构造，个中每个级别沿x轴和y轴交替进行分区。（图片来源）。
机器学习中的运用1.决策树：
决策树在机器学习中被广泛用于分类和回归任务。它们是更繁芜的集成方法（如随机森林和梯度提升机（例如 XGBoost））的基石。
分类：在分类任务中，决策树根据输入特色的值将数据集分成多个分支，旨在每次分割时尽可能地分离种别。回归：在回归任务中，树分割数据集以最小化每个节点内目标变量的方差。数学表示：
对付二叉决策树，决策过程可以表示如下：
from sklearn.datasets import load_irisfrom sklearn.tree import DecisionTreeClassifierfrom sklearn import treeimport matplotlib.pyplot as plt# Load example datasetiris = load_iris()X, y = iris.data, iris.target# Train a decision tree classifierclf = DecisionTreeClassifier(criterion='gini', max_depth=3)clf.fit(X, y)# Visualize the decision treeplt.figure(figsize=(12,8))tree.plot_tree(clf, filled=True, feature_names=iris.feature_names, class_names=iris.target_names)plt.show()
示例：构建分类决策树。此决策树模型在 Iris 数据集上进行演习，根据花瓣宽度和长度对鸢尾花品种进行可视化分类。该树利用基尼不纯度来确定分割，显示出 Setosa、Versicolor 和 Virginica 类之间的明显差异。
在此示例中，我们利用 Iris 数据集构建一个最大深度为 3 的决策树分类器。该树被可视化，显示每个节点的分割和分类决策。
2.kd树：
kd 树将点组织在 k 维空间中，使空间搜索变得高效，例如查找给定点的最近邻居。kd 树通过选择维度和值来分割数据，以递归办法将空间划分为半空间，从而创建二叉树构造。
数学表示：
对付k维空间中的一组点 { x ₁, x₂, …, x ₙ} ，kd 树的布局办法如下：
选择一个维度d来分割数据。沿维度d选择中值m将点分成两组：小于或即是 mmm 的点和大于 mmm 的点。以递归办法将相同的过程运用于每个点子集。示例：利用 kd 树进行最近邻搜索。
from sklearn.neighbors import KDTreeimport numpy as np# Create a dataset of 2D pointspoints = np.array([ [2, 3], [5, 4], [9, 6], [4, 7], [8, 1], [7, 2]])# Build a kd-treekd_tree = KDTree(points, leaf_size=2)# Query the kd-tree for the nearest neighbor of a given pointquery_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}")
在这个例子中，kd树[9, 2]通过搜索k维空间有效地找到了查询点的最近邻居。
效率考虑1.树的布局和遍历的韶光繁芜度：
二叉树：对付平衡数据，构建二叉树常日须要O ( n log n ) 韶光，个中n是元素数量。遍历（按序、前序、后序）须要O ( n ) 韶光。决策树：构建决策树常日涉及递归拆分数据，对付平衡树，其时间繁芜度为O ( n log n )。然而，在最坏的情形下，如果树不平衡，韶光繁芜度可能为O ( n ² )。Kd-Trees：构建一棵 kd-tree 须要O ( n log n ) 的韶光，而每次最近邻查询均匀须要O (log n ) 的韶光。高维数据繁芜度更高，由于树的效率会降落。2. 最佳性能的平衡和深度考虑：
树平衡：平衡树的每个节点两侧的节点数量大致相等。平衡树可确保插入、删除和搜索的韶光繁芜度尽可能低。相反，不平衡树（类似于链表）会降落性能，导致O ( n ) 操作。树的深度：树的深度会影响其性能。浅树（深度较小）遍历速率更快，但可能须要更繁芜的逻辑才能有效地实现拆分。比较之下，深树可能须要在每个节点上做出更少的繁芜决策，但可能导致更高的打算本钱。修剪：在决策树中，技能可以删除不必要的节点，减少树的深度，并防止过度拟合。示例：修剪决策树。
from sklearn.tree import DecisionTreeClassifier# Train a decision tree classifier with overfittingclf = DecisionTreeClassifier(criterion='gini', max_depth=None)clf.fit(X, y)# Prune the tree by limiting its maximum depthpruned_clf = DecisionTreeClassifier(criterion='gini', max_depth=3)pruned_clf.fit(X, y)# Compare the performance of the pruned vs. unpruned treeprint(f"Unpruned tree depth: {clf.get_depth()}")print(f"Pruned tree depth: {pruned_clf.get_depth()}")
修剪有助于降落决策树的繁芜性，提高其对未知数据的泛化性能。
总之，树是一种多功能数据构造，在机器学习中具有主要的运用，从利用决策树的分类和回归任务到利用 kd 树的高效空间搜索。理解它们的布局、遍历和性能影响对付构建有效的机器学习模型至关主要。
图表定义和概述图是一种数据构造，由一组节点（也称为顶点）和连接节点对的边组成。节点表示实体，边表示实体之间的关系或连接。图非常灵巧，可用于对各种系统进行建模，例如社交网络、生物网络和通信网络。
图表的组成部分：
节点（顶点）：表示图中的实体或工具。例如，每个节点可以代表社交网络中的一个人。边：表示节点之间的连接或关系。在社交网络中，边可以表示友情或关注关系。图形构造的视觉效果，描述了文中定义的顶点和边。图片由作者创建。
图表类型：
无向图：在无向图中，边没有方向，这意味着关系是双向的。如果节点 A 连接到节点 B，则节点 B 也连接到节点 A。
个中V是顶点集，E是边集。
有向图 (Digraph)：在有向图中，边有方向，这意味着关系是单向的。如果节点 A 连接到节点 B，并不一定意味着节点 B 连接到节点 A。
V 是顶点凑集，E是有向边（有序的顶点对）凑集。
加权图：加权图中的边具有干系的权重或本钱。这些权重有助于表示现实天下中实体之间的连接具有本钱的场景，例如间隔、韶光或容量。
W是一个为E中的每条边分配权重的函数。
机器学习中的运用图形在机器学习中越来越主要，紧张是当数据自然地以图形形式构建时。以下是一些关键运用：
1.图神经网络（GNN）
图神经网络 (GNN) 是一类旨在直接处理图构造数据的神经网络。它们将传统神经网络的观点扩展到图，使它们能够学习节点、边和全体图的表示。这在实体之间的关系与实体本身一样主要的任务中特殊有用。
数学表示
GNN 常日通过迭代聚合和转换来自节点邻居的信息来天生新的节点表示。例如，给定一个节点v及其邻居N(v)，GNN 会按如下办法更新v的表示：
GNN 的运用：
社交网络剖析：预测用户行为或检测社交网络中的社区。推举系统：通过剖析用户和物品之间的关系来推举产品或内容。分子图剖析：将分子视为图，个华夏子为节点、键为边，从而预测化学和生物学等分子的性子。2. 在社交网络、推举系统和生物网络中表示关系
图表自然适宜于表示各个领域的繁芜关系：
社交网络：节点代表用户，边代表友情或互动。图可用于查找社区和有影响力的用户或预测未来的联系。推举系统：节点代表用户和项目，边代表购买或评分等交互。图可以通过剖析相似的用户或项目向用户推举新项目。生物网络：在生物学中，图可以表示分子构造（节点是原子，边是键）、蛋白质-蛋白质相互浸染网络或基因调控网络。示例：利用图表在社交网络中进行社区检测
社区检测是识别图中内部连接比图的别的部分更紧密的节点组的过程。这常日用于社交网络中，以创造具有相似兴趣或互动的人群。
实现示例：
pip install networkx
import networkx as nximport matplotlib.pyplot as pltfrom networkx.algorithms.community import greedy_modularity_communities# Create an example social network graphG = nx.karate_club_graph()# Detect communities using the Girvan-Newman methodcommunities = greedy_modularity_communities(G)# Plot the graph with community coloringpos = nx.spring_layout(G)plt.figure(figsize=(10, 7))# Color nodes by communityfor i, community in enumerate(communities): nx.draw_networkx_nodes(G, pos, nodelist=list(community), node_color=f'C{i}', label=f'Community {i+1}')nx.draw_networkx_edges(G, pos)nx.draw_networkx_labels(G, pos)plt.legend()plt.show()
输出显示空手道俱乐部图表，个中节点根据算法检测到的社区进行着色。
效率考虑1. DFS、BFS 等图遍历算法的韶光繁芜度：
深度优先搜索 (DFS)： DFS 是一种用于遍历或搜索图的算法。它从根节点开始，尽可能地探索每个分支，然后回溯。DFS 的韶光繁芜度为O ( V + E )，个中V是顶点数，E是边数。广度优先搜索 (BFS)： BFS 从根节点开始，探索当前深度的所有邻居，然后移至下一个深度级别的节点。与 DFS 一样，BFS 的韶光繁芜度也是O ( V + E )。示例：实现 DFS 和 BFS。
# Depth-First Search (DFS) using recursiondef dfs(graph, node, visited): if node not in visited: print(node, end=" ") visited.add(node) for neighbor in graph[node]: dfs(graph, neighbor, visited)# Breadth-First Search (BFS) using a queuefrom collections import dequedef bfs(graph, start): visited = set() queue = deque([start]) while queue: node = queue.popleft() if node not in visited: print(node, end=" ") visited.add(node) queue.extend(graph[node])# Example graphgraph = { 'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': ['F'], 'F': []}print("DFS traversal:")dfs(graph, 'A', set())print("\nBFS traversal:")bfs(graph, 'A')
2.大型图和稀疏表示的内存管理：
图形可能非常弘大，尤其是在表示现实天下系统（如社交网络或生物网络）时。在这种情形下，高效的内存管理至关主要。
毗邻表：毗邻表是一种更节省内存的表示图的方法，尤其是当图很稀疏时（即与节点数比较，边很少）。它利用一个列表数组，个中每个列表包含一个节点的邻居。内存利用：毗邻表的内存利用量为O（V + E），个中V是顶点数，E是边数。毗邻矩阵：毗邻矩阵利用二维数组来表示图，个中如果节点i和j之间存在边，则位置 ( i , j )处的元素为 1 ，否则为 0。内存利用情形：毗邻矩阵利用O ( V² ) 内存。它更适宜具有多条靠近 V² 的边的密集图。示例：稀疏表示与密集表示。
import sysimport numpy as npfrom 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 representationsparse_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)}")
在这个例子中，稀疏矩阵表示显著减少了内存利用量，特殊是对付具有少量边的大型图。
总而言之，图是机器学习中强大的数据构造，尤实在用于对繁芜关系进行建模。它们的运用范围从社交网络剖析到分子构造预测，并且有各种算法可用于高效地遍历和管理大型图。理解这些操作的韶光和空间繁芜性对付优化基于图的机器学习任务至关主要。
结论我们探索了几种基本数据构造（数组和矩阵、堆、哈希表、树和图）及其在机器学习中的关键浸染。每种数据构造都有独特的上风，适宜特定类型的任务：
数组和矩阵是数据表示的支柱，尤其是在处理数值数据时。它们可以实现许多机器学习算法所需的高效数学运算。堆有效地管理优先级行列步队并优化最近邻搜索等过程，这在聚类和寻路算法中至关主要。哈希表善于快速数据检索，这使其对付处理大型数据集、实现推举系统和确保快速访问信息不可或缺。树（例如二叉树、决策树和 kd 树）对付从分类和回归到高效空间搜索等任务至关主要，并且构成了浩瀚机器学习模型的核心。图形可以对数据中的繁芜关系进行建模和剖析，支持许多任务（例如，社交网络剖析、推举系统和生物网络预测）。图神经网络 (GNN) 为图构造数据的学习供应了尖端技能。通过理解这些数据构造，您可以就有效地存储、访问和操作数据做出明智的决策，从而得到更有效、更可扩展的 ML 办理方案。
末了的想法为机器学习任务选择得当的数据构造可以显著提高韶光和内存利用效率。这些构造不仅仅是抽象的观点，它们还是实用的工具，如果利用得当，可以显著提高机器学习模型的性能。
在构建和优化 ML 模型时，考试测验不同的数据构造。深入理解它们的实现，考虑它们的利弊，并理解它们如何影响办理方案的效率和可扩展性。
参考：
https://pub.towardsai.net/data-structures-in-machine-learning-a-comprehensive-guide-to-efficiency-and-scalability-f7429919c9c5