与机器学习算法相关的数据结构有哪些？

仅拥有机器学习技能是不够的。您还需要良好的数据结构应用知识。了解更多并解决一些问题。

因此，您决定停止使用固定算法并编写自己的机器学习方法。也许您已经开发了一种新的数据聚类方法，或者您可能对您最喜欢的统计分类包的局限性感到沮丧。

在这两种情况下，您对数据结构和算法了解得越多，编码就越容易。

我不认为机器学习中使用的数据结构与软件开发其他领域中使用的数据结构有很大不同。然而，由于许多问题的规模和难度，掌握基础知识很重要。

另外，由于机器学习是一个非常数学的领域，我们应该记住数据结构是如何用来解决数学问题的，以及它们如何以自己的方式处理数学问题。

有两种方法对数据结构进行分类：按实现分类和按操作分类。

我所说的实现是指它们如何编程和实际存储模式的具体细节。它们的外观并不重要，重要的是它们的实施方式。对于根据操作或抽象数据类型分类的数据结构，情况恰恰相反——它们的外观和操作比它们的实现方式更重要，而且事实上它们通常可以用许多不同的内部表示来实现。

数组

当我说基本数组是机器学习中最重要的数据结构时，我不是在开玩笑。该实用程序的类型比您想象的要多。数组很重要，因为它们用于线性代数 - 您可以使用的最有用和最强大的数学工具。

因此，最常见的类型是一维和二维类型，分别对应于向量和矩阵，但有时也会遇到三维或四维数组，无论是对于更高的张量还是前者的组示例。

执行矩阵运算时，您必须从令人眼花缭乱的各种库、数据类型甚至语言中进行选择。许多科学编程语言，例如 Matlab、交互式数据语言 (IDL) 和具有 Numpy 扩展的 Python，主要设计用于处理向量和矩阵。

但这些数据结构的优点是，即使在更通用的编程语言中，假设该语言中有 Fortran DNA，在 Metal 中转换向量和矩阵也很容易。考虑矩阵向量乘法的转换：

使用 C++：

for (int i=0; i<n; i++) {

  y[i]=0;

  for (int j=0; j<n; j++) y[i]+=a[i][j]*x[j]

}

在大多数情况下，可以在运行时为数组分配固定大小，或者可以计算可靠的上限。在数组需要无限扩展的情况下，可以使用可扩展数组，例如C++标准模板库（STL）中的Vector类。Matlab中的常规数组具有类似的可扩展性，可扩展数组是整个Python语言的基础。

在此数据结构中，有两个元数据与实际数据值一起存储。这些是分配给数据结构的存储空间量和数组的实际大小。如果数组大小超过存储空间，则分配两倍大小的新空间，将值复制到其中，并删除旧数组。

这是一个 O(n) 操作，其中 n 是数组的大小，但由于它只是偶尔发生，所以将新值添加到末尾所需的时间实际上取决于常数时间 O(1)分配。 。这是一种非常灵活的数据结构，具有快速平均插入和快速访问的特点。

可扩展数组非常适合组合其他更复杂的数据结构并使其可扩展。例如，要存储稀疏矩阵，您可以在末尾添加任意数量的新元素，然后按位置对它们进行排序以加快定位速度。稍后会详细介绍！

稀疏矩阵可用于文本分类问题。

链表

链表由多个单独分配的节点组成。每个节点都包含一个数据值和一个指向列表中下一个节点的指针。插入在恒定时间内非常高效，但访问值很慢并且通常需要扫描列表的大部分。

链接列表可以轻松拆分和分离。有很多变化 - 例如，可以在头部或尾部制作插入件；列表可以双向链接，并且基于相同原理的类似数据结构有很多。

主要是我发现链表可以用来解析不定长度的列表。然后可以将它们转换为定长数组以便快速访问。因此，我使用了一个链表类，其中包含转换为数组的方法。

二叉树

二叉树类似于链表，只不过每个节点有两个指向后续节点的指针，而不是一个。左侧子级的值始终小于父级的值，并且父级的值小于右侧子级的值。因此，二叉树中的数据会自动排序。 O (log n) 平均插入和访问是高效的。与链表一样，它们很容易转换为数组，这是树排序的基础。

平衡树

如果数据已经排序，那么在最坏的情况下，二叉树的 O(n) 效率较低，因为数据是线性排列的，就好像它是链表一样。虽然二叉树中的顺序是有限的，但它绝不是唯一的，并且根据插入的顺序，可以使用相同的列表来排列许多不同的配置。

为了使其更加平衡，可以对树应用一些变换。自平衡树自动执行这些操作，以保持访问和插入的最佳平均值。

机器学习中的一个常见问题是找到特定点的最近邻居。这个问题是NN算法所需要的。KD树是一种二叉树，提供了一种有效的解决方案。

堆

堆是另一种分层的、树状的有序数据结构，它具有垂直排序而不是水平排序。此顺序适用于层次结构，但不适用于整个层次结构：父级始终大于其子级，但较高的节点不一定大于其下面的节点。

插入和恢复是通过升级执行的。元素首先插入到最高的可用位置。然后将其与其父母进行比较并提升，直到达到正确的水平。要从堆中删除元素，请将两个子元素中较大的元素提升到缺失位置，然后将两个子元素中较大的元素提升，依此类推，直到所有元素都获得正确的级别。

通常，采用堆顶部排名最高的值对列表进行排序。与树不同，大多数堆只是存储在数组中，元素之间的关系只是隐式的。

堆栈

堆栈定义为“先进后出”。一个元素被推入栈顶，覆盖前一个元素。必须先折叠顶部的元素，然后才能访问所有其他元素。

栈主要用于分析语法和实现计算机语言。

在许多机器学习应用中，特定领域语言（DSL）是完美的解决方案。例如，libAGF 库使用递归控制语言将二进制分类推广到多个类。特殊字符用于重复先前的选项，但由于语言是递归的，因此必须从同一级别或更高级别选择选项。这是由堆栈实现的。

队列

队列定义为“先进先出”。想想银行柜台前的排队队伍（对于我们这些年纪足够大的人来说，还记得网上银行出现之前的时代）。队列在实时编程中非常有用，这样程序就可以维护一个正在处理的作业列表。

考虑一个记录运动​​员分段时间的应用程序。你输入号码布并按回车键，但当你这样做时，你后面的运动员也会通过。因此，您输入下一个运动员号码布的列表，然后按一个单独的键来注册队列中的下一个运动员。

集合

集合包含非重复元素的无序列表。如果您添加集合中已有的项目，则不会发生任何变化。由于机器学习的大部分数学都涉及集合，因此它们是非常有用的数据结构。

关联数组

在关联数组中，有两种成对存储的数据类型：键及其关联值。数据结构本质上是关系型的：值由它们的键解析。由于大多数训练数据也是相关的，因此这种类型的数据结构似乎非常适合机器学习问题。

在实践中，它不是很有用，部分原因是大多数关联数组只是一维的，而机器学习数据通常是多维的。

关联数组适合构建字典。

假设您正在构建一个 DSL，想要存储函数和变量的列表，并且需要区分两者。

• sin = 函数。
• var = 变量。
• exp = 函数。
• x = 变量。
• sqrt = 函数。
• a = 变量。

在“sqrt”上查询数组返回“function”。

自定义数据结构

当您处理更多问题时，您肯定会遇到标准配方框不包含最佳结构的问题。您必须设计自己的数据结构。

考虑一个多类分类器，它概括了二元分类器来处理两个以上类的分类问题。一个明显的解决方案是二分：递归地将类分成两组。但分层解决方案并不是解决多个类的唯一方法，您可以使用二叉树之类的东西来组织二元分类器。

考虑多个分区并使用它们同时求解所有类的概率。

通用的解决方案将两者结合起来，使得每个层次划分不必是二元的，而是可以通过非层次的多类分类器来解决。这是 libAGF 库中的方法。

还可以从基本结构组装出更复杂的数据结构。考虑稀疏矩阵类。在稀疏矩阵中，大多数元素为零，仅存储非零元素。我们可以将每个元素的位置和值存储为三元组，并将它们的列表存储在可扩展数组中。

结论

数据结构本身有时很有趣。让它们真正有趣的是它们可以解决各种各样的问题。

在我的大部分工作中，我使用了大量基本的定长数组。我主要是使用更复杂的数据结构，让程序运行和与外部接口交互时更加流畅，更加人性化。与以前的 Fortran 程序不同，我必须忍受近半个小时的编译周期才能更改网格大小（我实际上曾开发过这样的程序！）。

即使你想不出一个应用程序，我仍然认为了解诸如堆栈和队列之类的东西是很好的。你永远不知道什么时候有用的东西会派上用场。

真正复杂的人工智能应用程序可以使用有向图和无向图，它们只是树和链表的概括。如果你不能处理后者，你如何构建类似前者的东西？

问题

如果您想自行练习和实现ML算法的数据结构，请尝试解决以下一些问题：

1. Will矩阵向量乘法代码片段位于subroutine_ve-matrix_timenamed_matrix中。设计子程序的调用语法。
2. 使用struct、typedef或class将向量和矩阵封装成一对抽象类型，分别称为vect和matrix。为这些类型设计一个 API。
3. 在线查找至少三个图书馆。
4. 下载并安装 LIBSVM 库。考虑“svm.cpp”第 316 行的方法 kernel::k_function。用于保存向量的数据结构有哪些优点和缺点？
5. LIBSVM库中，如何重构核函数的计算？
6. 文章中描述的哪些数据结构是抽象类型？
7. 您可以使用什么内部表示/数据结构来实现抽象数据类型？还有什么没有包含在上面的列表中吗？
8. 使用二叉树设计关联数组。
9. 考虑 LIBSVM 中的向量类型。如何用它来表示稀疏矩阵？与上面描述的稀疏矩阵类进行比较。查看全系列。每种表示法的优点和缺点是什么？
10. 将树排序转换为堆排序。现在使用相同的数据结构来查找前 k 个元素。有哪些常见的机器学习算法适合这种情况？
11. 用您最喜欢的语言实现您最喜欢的数据结构。

作者信息

Luba Belokon 营销，Peter Mills 研究科学家