机器学习算法的数据结构是怎样的

拥有机器学习技能是不够的。你还需要良好的数据结构的工作知识。学习更多，并解决一些问题。

因此，你已经决定不再使用固定的算法并开始编写自己的机器学习方法。也许你已经有了一种新的集群数据的新方法，或者你可能对你最喜欢的统计分类包的局限性感到失望。

无论哪种情况，你对数据结构和算法的了解越多，在代码编写时就越容易。我不认为机器学习中使用的数据结构与其他软件开发领域的数据结构有很大的不同。然而，由于许多问题的规模和难度，对基础知识的掌握非常重要。

另外，由于机器学习是一个数学性非常强的领域，我们应该记住，数据结构是如何被用来解决数学问题的，以及它们是如何以自己的方式来处理数学问题的。有两种方法可以对数据结构进行分类：通过它们的实现和它们的操作。

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

数组

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

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

在进行矩阵运算时，你将不得不从令人眼花缭乱的各种库、数据类型、甚至语言中进行选择。许多科学编程语言，如Matlab，交互式数据语言（IDL），以及带有Numpy扩展的Python，主要是为处理向量和矩阵而设计的。

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

使用C++：

for （int i=0; i0;

for （int j=0; j

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

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

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

可扩展数组非常适合组成其他更复杂的数据结构并使其可扩展。例如，要存储稀疏矩阵，可以在结尾添加任意数量的新元素，然后按位置对其进行排序以更快地定位。稍后详述！稀疏矩阵可用于文本分类问题。

链表

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

链表很容易拼接并分开。有许多变化——例如，可以在头部或尾部进行插入;该列表可以是双链接的，并且有许多类似的数据结构基于相同的原则。

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

二叉树

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

平衡树

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

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

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

堆

堆是另一个层次结构，类似于树的有序数据结构，它具有垂直排序，而不是水平排序。这种排序适用于层次结构，但不适用于整个层次：父节点总是大于它的子节点，但是更高级别的节点并不一定比下面的节点要大。

插入和检索都是通过升级来执行的。元素首先插入到最高可用位置。然后将其与其父母进行比较并提升，直至达到正确的等级。为了从堆中去掉一个元素，两个孩子中较大的一个被提升到缺失的位置，然后这两个孩子中较大的一个被提升，如此等等，直到每一个都变成正确的等级。

通常情况下，顶部的最高排名值将从堆中取出，以便对列表进行排序。 与树不同，大多数堆只是简单地存储在数组中，元素之间的关系只是隐含的。

堆栈

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

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

在许多机器学习应用程序中，领域特定语言（DSL）是完美的解决方案。例如，libAGF库使用递归控制语言将二进制分类一般化到多类。特殊字符用于重复前面的选项，但是由于语言是递归的，所以必须从相同的层次或更高的层次上选择该选项。这是由堆栈实现的。

队列

队列被定义为“先入先出”。想想银行柜员面前的队伍（对于我们这些年纪还大的人来说，还记得在网上银行出现之前的一段时间）。队列在实时编程中非常有用，因此程序可以维护要处理的作业列表。

考虑一个记录运动员分段时间的应用程序。你输入bib号码，然后按回车键，但你要做的时候，后面的运动员也通过了。所以你输入的是最近接近运动员的bib号码列表，然后按下一个单独的键来注册队列中的下一个。

集合

一个集合包含一个非重复元素的无序列表。如果添加已经在集合中的元素，则不会有任何更改。由于机器学习的许多数学知识都与集合有关，所以它们是非常有用的数据结构。

关联数组

在关联数组中，有两种类型的数据成对存储：密钥及其相关值。 数据结构本质上是关系型的：数值由其键来解决。由于大部分训练数据也是关系型的，这种类型的数据结构似乎非常适合于机器学习问题。在实践中，它的用处不大，部分原因是大多数关联数组只是一维的，而机器学习数据通常是多维的。

关联数组适用于构建字典。假设你正在构建一个DSL，想要存储一个函数和变量列表，并且需要区分这两者。

sin =函数。

var = 变量。

exp =函数。

x =变量。

sqrt =函数。

a =变量。

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

自定义数据结构

当你处理更多问题时，你肯定会遇到标准配方框不包含最佳结构的那些问题。你将需要设计自己的数据结构。考虑一个多类分类器，它概括了一个二元分类器来处理具有两个以上类的分类问题。一个明显的解决方案是平分：递归地将类分成两组。但分层解决方案并不是解决多类的唯一方法，你可以使用类似于二叉树的方法来组织二进制分类器。考虑几个分区，然后用它们同时解决所有类的概率。

最通用的解决方案将两者结合起来，因此每个分层分区不需要是二进制的，而是可以通过非分层多类分类器来解决。这是在libAGF库中采用的方法。

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

结论

数据结构本身偶尔也很有趣。令它们真正有趣的是它们可以解决的各种问题。对于大多数工作，我使用了许多基本的固定长度数组。我主要使用更复杂的数据结构来使程序在运行和与外部界面交互方面更加流畅，并且更加便于用户使用。不像以前的Fortran程序那样，为了改变网格大小，我不得不忍受一个接近半小时的编译周期（我实际上在这样的程序上工作过！）。

即使你无法想出一个应用程序，我仍然认为知道诸如栈和队列之类的东西是件好事。你永远不知道什么时候会派上用场。真正复杂的人工智能应用程序可能会使用定向和无向图，它们只是树和链表的一般化。如果你无法应对后者，你将如何建立起像前者那样的东西？

问题

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

将矩阵向量乘法代码片段封装到名为matrix_times_vector的子例程中。设计子例程的调用语法。使用struct，typedef或class，将矢量和矩阵分别封装到一对称为vect和matrix的抽象类型中。为这些类型设计一个API。在网上找到至少三个以上的库。

下载并安装LIBSVM库。考虑方法Kernel ：： k_funcTIon在“svm.cpp”的第316行。用于保存向量的数据结构有哪些优缺点？在LIBSVM库中，如何重构内核函数的计算？文中描述的哪些数据结构是抽象类型？你可以使用什么内部表示/数据结构来实现抽象数据类型？上面的列表中是否有未包含的内容？

使用二叉树，设计一个关联数组。

在LIBSVM中考虑向量类型。如何用它来表示一个稀疏矩阵？与上面描述的稀疏矩阵类进行对比。看看完整的类型。每个代表的优点和缺点是什么？实现一个treesort和一个堆排序。现在使用相同的数据结构来查找前k个元素。什么常见的机器学习算法适合这种情况？用你喜欢的语言实现你最喜欢的数据结构。