与机器学习算法相关的数据结构

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

此外，由于机器学习是数学领域，我们应该记住数据结构如何用来解决数学问题，以及它们本身就是数学对象的方式。

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

数组

当我说基本数组是机器学习中最重要的数据结构时，我不是在开玩笑。这种面包加黄油的类型比你想象的还要多。数组非常重要，因为它们用于线性代数，这是你可以使用的最有用和最强大的数学工具。

因此，最常见的类型将是一维和二维类型，分别对应于向量和矩阵，但是你偶尔会遇到三维或四维数组，它们要么用于较高的等级，要么用于对前者的示例进行分组。

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

但是这些数据结构的好处是，即使在更通用的编程语言中，实现向量和矩阵也是很简单的，假设语言中有任何Fortran DNA。考虑矩阵向量乘法的平移：

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)中的向量类。Matlab中的常规数组具有类似的可扩展性，可扩展数组是整个Python语言的基础。

在该数据结构中，存在与实际数据值一起存储的两个元数据。这些是分配给数据结构的存储空间量以及阵列的实际大小。一旦数组的大小超过存储空间，就会分配一个大小为两倍的新空间，将值复制到其中，并删除旧数组。

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

可扩展数组非常适合组合其他更复杂的数据结构并使其可扩展。例如，为了存储稀疏矩阵，可以在末尾添加任意数量的新元素，然后按位置对它们进行排序以使位置更快。

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

链表

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

链接列表很容易拼接在一起以及分开。有许多变化，例如，插入可以在头部或尾部进行;列表可以是双向链接的，并且有许多基于相同原理的类似数据结构，例如下面的二叉树：

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

二叉树

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

平衡树

如果数据已经被排序，则在O（n）最坏的情况下二进制树效率较低，因为数据将被线性布局，就好像它是链表一样。虽然二叉树中的排序受到约束，但它绝不是唯一的，并且根据插入的顺序，可以在许多不同的配置中排列相同的列表。

有几种转换可以应用于树，以使其更加平衡。自平衡树自动执行这些操作，以便以最佳平均值访问和插入。

机器学习中一个普遍存在的问题是找出最接近某一特定点的邻域。神经网络算法需要解决这个问题。KD树是一种二叉树，它提供了一种有效的解决方案。

堆是另一种类似于树的分层有序数据结构，除了水平排序之外，它还具有垂直排序。这种排序沿层次结构进行，但不是跨层次的：父节点总是大于其两个子节点，但是级别较高的节点不一定大于不直接位于其下面的较低的节点。

插入和检索都是通过升级完成的。元素首先插入到最高的可用位置。然后把它和它的父母进行比较，并提升到正确的等级。要从堆中取下一个元素，两个子元素中越大的子元素被提升到缺失的位置，那么这两个子元素中的更大的子元素就会被提升。

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

堆叠

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

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

有许多机器学习应用程序，其中领域特定语言(DSL)是完美的解决方案。例如，libAGF库使用递归控制语言将二进制分类推广到多类。特殊字符用于重复前面的选项，但由于该语言是递归的，因此该选项必须取自相同的层级或更高级别。这是通过堆栈实现的。

队列

队列被定义为“先入先出”。队列在实时编程中非常有用，因此程序可以维护要处理的作业列表。集合由非重复元素的无序列表组成。如果您添加了一个已经在集合中的元素，则不会有任何更改。由于机器学习的许多数学处理集，它们是非常有用的数据结构。

关联阵列

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

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

关联数组适用于构建字典。

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

sin = function

var = variable

exp = function

x = variable

sqrt = function

a = variable

查询“sqrt”上的数组将返回“函数”。

自定义数据结构

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

考虑一个多类分类器，它推广二元分类器以处理具有两个以上类的分类问题。一个明显的解决方案是二分法：递归地将类分成两组。你可以使用类似于二叉树的东西来组织二进制分类器，除了分层解决方案不是解决多类的唯一方法。

考虑几个分区，然后使用这些分区同时求解所有类的概率。

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

3乘3的等式：

结论

在我所做的大部分工作中，我使用了很多基本的固定长度数组。我使用复杂的数据结构，使程序在运行方式和与外部世界的接口方面更加流畅，也更方便用户使用。不像以前的Fortran程序，为了改变网格大小，必须忍受将近半个小时的编译周期。

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

真正复杂的人工智能应用程序可能会使用定向和无向图等事物，这些图实际上只是树和链表的概括。如果你无法应对后者，你将如何建造像前者一样的东西？

问题

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

1. 将矩阵向量乘法代码片段封装到一个名为MatrixTimeVectoral的子例程中，为子例程设计调用语法。

2. 使用struct、typedef或class，将向量和矩阵分别封装成两个抽象类型，称为Vect和矩阵。为类型设计API。

3. 在网上找到至少三个执行上述操作的库。

4. 下载并安装LIBSVM库。考虑一下“svm.cpp”第316行中的Kernel：K_Function方法。用于保存向量的数据结构的优点和缺点是什么？

5. 如何在LIBSVM库中重构核函数的计算？

6. 文本中描述的哪些数据结构是抽象类型？

7. 你可以使用什么内部表示/数据结构来实现抽象数据类型？是否有未列入上述清单的？

原文标题《Data Structures Related to Machine Learning Algorithms》

作者：Luba Belokon

译者：lemon

不代表云加社区观点，更多详情请查看原文链接